思路: dp水题
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb push_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define mem(a, b) memset(a, b, sizeof(a)) #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout); //head const int MOD = 1e9 + 7, N = 1e6 + 5; LL dp[N]; int main() { int T, n; dp[0] = 1; for (int i = 1; i < N; i++) { for (int j = max(0, i-8); j < i; j++) dp[i] = (dp[i] + dp[j]) % MOD; } scanf("%d", &T); for (int i = 1; i <= T; i++) { scanf("%d", &n); printf("%lld ", dp[n/3]); } return 0; }
思路:用set
n^2logn暴力枚举
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb push_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define mem(a, b) memset(a, b, sizeof(a)) #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout); //head const int N = 2e3 + 5; pair<int, pii> a[N]; multiset<pii> s1; multiset<int> s2; int main() { int n, k; scanf("%d %d", &n, &k); for (int i = 1; i <= n; i++) scanf("%d %d %d", &a[i].fi, &a[i].se.fi, &a[i].se.se); sort(a+1, a+1+n); LL ans = 1e16; for (int i = 1; i <= n; i++) { s1.insert(a[i].se); if(i >= k) { s2.clear(); for (auto it : s1) { s2.insert(it.se); if(s2.size() > k) s2.erase(--s2.end()); if(s2.size() == k) { ans = min(ans, 1LL*a[i].fi + 1LL*it.fi + 1LL*(*--s2.end())); } } } } printf("%lld ", ans); return 0; }
思路:水题, 减S取模
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb push_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define mem(a, b) memset(a, b, sizeof(a)) #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout); //head const int N = 1e3 + 10; char s[N]; bool isAlphaBete(char c){ return c>='A'&&c<='Z'||c>='a'&&c<='z'; } int main() { int n, S; scanf("%d %d", &n, &S); S %= 26; char c; c = getchar(); while((c = getchar())!=EOF){ if(isupper(c)) { int t = c - 'A'; t = (t + 26 - S) % 26; c = 'A' + t; } else if(islower(c)) { int t = c - 'a'; t = (t + 26 - S) % 26; c = 'a' + t; } putchar(c); } return 0; }
思路:贪心
假设相邻两个元素a, b, 在此之前的大象的体重为w
那么按a前b后的顺序的花费是 w*a.c + w*a.r*b.c
按b前a后的顺序的花费是 w*b.c + w*b.r*a.c
无论什么顺序,经过这两个元素后大象的体重都是w*a.r*b.r
那么a在b前的条件是w*a.c + w*a.r*b.c < w*b.c + w*b.r*a.c
即 a.c + a.r*b.c < b.c + b.r*a.c
按这个条件写个cmp函数排个序即可
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb push_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define mem(a, b) memset(a, b, sizeof(a)) #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout); //head const int N = 1e5 + 10; const LL INF = (1ll<<60); struct node { int c; double r; }a[N]; int n, w; bool cmp(node a, node b) { return a.c + b.c*a.r < b.c + a.c*b.r; } void solve() { double ans = INF; sort(a+1, a+1+n, cmp); double tw = w, tans = 0; for (int i = 1; i <= n; i++) { tans += tw * a[i].c; tw *= a[i].r; } ans = min(ans, tans); printf("%.10f ", ans); } int main() { scanf("%d %d", &n, &w); for (int i = 1; i <= n; i++) scanf("%d %lf", &a[i].c, &a[i].r); solve(); return 0; }
思路:一个向量旋转乘以下面的旋转矩阵即可(Θ > 0 表示逆时针)
然后多边形旋转的话就一个点不动,其他点绕改点旋转
旋转好后将多边形左下角移动到与x轴正半轴和y正半轴相切,然后按w*h等比例缩放
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb push_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define mem(a, b) memset(a, b, sizeof(a)) #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout); //head const int N = 1e5 + 5; const int INF = 0x7f7f7f7f; const double eps = 1e-8; //考虑误差的加法 double add(double a, double b) { if(fabs(a + b) < eps * (fabs(a) + fabs(b))) return 0; return a + b; } //考虑误差的与0比较 int dcmp(double x) { if(fabs(x) < eps) return 0; else return x<0?-1:1; } struct P { double x, y; P(){} P(double x, double y) :x(x), y(y){} bool operator == (P p) { return dcmp(x - p.x) == 0 && dcmp(y - p.y) == 0; } P operator + (P p) { return P(add(x, p.x), add(y, p.y)); } P operator - (P p) { return P(add(x, -p.x), add(y, -p.y)); } P operator * (double p) { return P(x * p, y * p); } P operator / (double p) { return P(x / p, y / p); } //点积 double dot(P p) { return add(x * p.x, y * p.y); } //叉积 double cross(P p) { return add(x * p.y, -y * p.x); } }p[N]; typedef P Vector; //向量逆时针旋转 Vector Rotate(Vector a,double rad) { return Vector(a.x * cos(rad) - a.y * sin(rad), a.x * sin(rad) + a.y * cos(rad)); } int main() { int a, w, h, n; scanf("%d %d %d %d", &a, &w, &h, &n); double A = a*pi/180; for (int i = 1; i <= n; i++) scanf("%lf %lf", &p[i].x, &p[i].y); for (int i = 2; i <= n; i++) p[i] = p[1] + Rotate(p[i] - p[1], A); double mnx = INF, mny = INF; for (int i = 1; i <= n; i++) mnx = min(mnx, p[i].x), mny = min(mny, p[i].y); for (int i = 1; i <= n; i++) p[i].x -= mnx, p[i].y -= mny; double mxx = 0, mxy = 0; for (int i = 1; i <= n; i++) mxx = max(mxx, p[i].x), mxy = max(mxy, p[i].y); for (int i = 1; i <= n; i++) p[i].x = p[i].x*w/mxx, p[i].y = p[i].y*h/mxy; for (int i = 1; i <= n; i++) printf("%.10f %.10f ", p[i].x, p[i].y); return 0; }
思路:首先将给的小数乘以10000得到式子 d / 100000 中的 d, 然后10000/gcd(10000, d) 就是答案
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb push_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define mem(a, b) memset(a, b, sizeof(a)) #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout); //head char s[105]; int main() { int T; scanf("%d", &T); for (int i = 1; i <= T; i++) { scanf("%s", s); int n = strlen(s); int t = 0; for (int i = 2; i < n; i++) { t = t*10 + s[i] - '0'; } for (int i = n; i < 6; i++) { t = t*10; } int d = __gcd(t, 10000); printf("%d ", 10000/d); } return 0; }
G A+B+C
思路:水题, (a*d*f + c*b*f + e*b*d) / (b*d*f) 约分后即是答案
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb push_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define mem(a, b) memset(a, b, sizeof(a)) #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout); //head int main() { int T; LL a, b, c, d, e, f; scanf("%d", &T); for (int i = 1; i <= T; i++) { scanf("%lld/%lld %lld/%lld %lld/%lld", &a, &b, &c, &d, &e, &f); LL up = a*d*f + c*b*f + e*b*d; LL down = b*d*f; LL d = __gcd(up, down); up /= d; down /= d; printf("%lld/%lld ", up, down); } return 0; }
思路:水题, 题意难懂, 把a drink理解为一瓶酒
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb push_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define mem(a, b) memset(a, b, sizeof(a)) #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout); //head const int MOD = 1e9 + 7, N = 1e6 + 5; LL dp[N]; int main() { int T, n, k; scanf("%d", &T); for (int i = 1; i <= T; i++) { scanf("%d %d", &n, &k); int b = n*(n+1)/2; if(k < b) puts("Too drunk to count"); else if((k-b) % n == 0) printf("%d ", n+1+(k-b)/n); else puts("Too drunk to count"); } return 0; }
思路: 最大流, 要拆点
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb push_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define mem(a, b) memset(a, b, sizeof(a)) #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout); //head const int N = 2e3 + 5, M = 6e3 + 10; const int INF = 0x3f3f3f3f; pii a[N]; piii b[N]; struct edge { int to, cap, rev; }; vector<edge> g[M]; int level[M], iter[M], mxv = 0; void add_edge(int from, int to, int cap) { g[from].pb({to, cap, g[to].size()}); g[to].pb({from, 0, g[from].size()-1}); } void bfs(int s) { for (int i = 0; i <= mxv; i++) level[i] = -1; queue<int> q; level[s] = 0; q.push(s); while(!q.empty()) { int v = q.front(); q.pop(); for (edge &e : g[v]) { if(e.cap > 0 && level[e.to] < 0) { level[e.to] = level[v] + 1; q.push(e.to); } } } } int dfs(int v, int t, int f) { if (v == t) return f; for (int &i = iter[v]; i < g[v].size(); i++) { edge &e = g[v][i]; if(e.cap > 0 && level[v] < level[e.to]) { int d = dfs(e.to, t, min(f, e.cap)); if(d > 0) { e.cap -= d; g[e.to][e.rev].cap += d; return d; } } } return 0; } int max_flow(int s, int t) { int flow = 0; for(;;) { bfs(s); if(level[t] < 0) return flow; for (int i = 0; i <= mxv; i++) iter[i] = 0; int f; while((f = dfs(s, t, INF)) > 0) { flow += f; } } } int main() { int n, m; LL s; scanf("%d %d %lld", &n, &m, &s); if(s < 10) return 0*puts("NO"); s -= 10; for (int i = 1; i <= n; i++) scanf("%d %d", &a[i].fi, &a[i].se); for (int i = 1; i <= m; i++) scanf("%d %d %d", &b[i].fi.fi, &b[i].fi.se, &b[i].se); int st = 0; for (int i = 1; i <= n; i++) add_edge(st, i, 1); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { int dx = abs(b[j].fi.fi - a[i].fi), dy = abs(b[j].fi.se - a[i].se); if(1ULL*dx*dx + 1ULL*dy*dy <= 1ULL*s*s) { add_edge(i, n+j, 1); } } } for (int i = 1; i <= m; i++) { add_edge(i+n, i+n+m, b[i].se); } mxv = m+n+m+1; for (int i = 1; i <= m; i++) { add_edge(i+n+m, mxv, INF); } if(max_flow(st, mxv) == n) puts("YES"); else puts("NO"); return 0; }
思路:线段树, 用long double
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb push_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define mem(a, b) memset(a, b, sizeof(a)) #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout); //head const int N = 1e5 + 5; const long double up = pow((long double)2.0, 100); long double tree[N<<2]; void push_up(int rt) { tree[rt] = tree[rt<<1] * tree[rt<<1|1]; } void build(int rt, int l, int r) { if(l == r) { cin >> tree[rt]; return ; } int m = l+r >> 1; build(ls); build(rs); push_up(rt); } void update(int p, double x, int rt, int l, int r) { if(l == r) { tree[rt] = (long double)x; return ; } int m = l+r >> 1; if(p <= m) update(p, x, ls); else update(p, x, rs); push_up(rt); } long double query(int L, int R, int rt, int l, int r) { if(L <= l && r <= R) return tree[rt]; int m = l+r >> 1; long double ans = 1; if(L <= m) ans *= query(L, R, ls); if(R > m) ans *= query(L, R, rs); return ans; } int main() { int n; scanf("%d", &n); build(1, 1, n); int q, ty, l, r, x; double p; scanf("%d", &q); for (int i = 1; i <= q; i++) { scanf("%d", &ty); if(ty == 1) { scanf("%d %lf", &x, &p); update(x, p, 1, 1, n); } else { scanf("%d %d", &l, &r); long double t = query(l, r, 1, 1, n); if(t >= up) printf("INFINITE! "); else cout << fixed << setprecision(10) << t << ' '; } } return 0; }