打完这个赛季（上个青岛铜牌），刷刷蓝书
题目合集：
https://cn.vjudge.net/article/737
eg1:
https://cn.vjudge.net/problem/UVA-11292
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<algorithm> #include<iostream> #include<math.h> #include<ctime> #include<string> #include<vector> using namespace std; typedef long long ll; const int MAXN = 2e4 + 5; const int maxn = MAXN; const long long MOD = 1e8 + 7; #define rep(i,t,n) for(int i =(t);i<=(n);++i) #define per(i,n,t) for(int i =(n);i>=(t);--i) #define mmm(a,b) memset(a,b,sizeof(a)) int phi[MAXN], prime[MAXN]; int isntp[maxn]; void sieve(int n) { int m = (int)sqrt(n + 0.5); mmm(isntp, 0); rep(i, 2, m)if (!isntp[i])for (int j = i * i; j <= n; j += i)isntp[j] = 1; } int ans[maxn]; int smain(); #define ONLINE_JUDGE int main() { //ios::sync_with_stdio(false); #ifndef ONLINE_JUDGE FILE *myfile; myfile = freopen("C:\Users\acm-14\Desktop\test\b.in", "r", stdin); if (myfile == NULL) fprintf(stdout, "error on input freopen "); FILE *outfile; outfile = freopen("C:\Users\acm-14\Desktop\test\out.txt", "w", stdout); if (outfile == NULL) fprintf(stdout, "error on output freopen "); long _begin_time = clock(); #endif smain(); #ifndef ONLINE_JUDGE long _end_time = clock(); printf("time = %ld ms.", _end_time - _begin_time); #endif return 0; } int head[maxn]; int cost[maxn]; int smain() { int n, m; while (cin >> n >> m&&n) { rep(i, 1, n)cin >> head[i]; rep(i, 1, m)cin >> cost[i]; sort(head + 1, head + 1 + n); sort(cost + 1, cost + 1 + m); int p = 1; long long ans = 0; int f = 1; rep(i, 1, n) { if (p > m) { f = 0; break; } while (head[i] > cost[p])p++; ans += cost[p],p++; } if (!f)puts("Loowater is doomed!"); else cout << ans << endl; } /*don't delete*/ return 0; } /*, 2 3 5 4 7 8 4 2 1 5 5 10 0 0 */
算法：无脑贪心+排序
坑：本来想少写一个flag，结果想错了。。
ps:静电容键盘到了，敲敲水题试一下。打字只要轻轻压（摸）一下就行，以至于手指经过别的键总是会碰到，也很容易打两次同一个字母，感觉习惯了的话代码速度可以上天。
eg2
https://cn.vjudge.net/problem/UVA-11729
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<algorithm> #include<iostream> #include<math.h> #include<ctime> #include<string> #include<vector> using namespace std; typedef long long ll; const int MAXN = 1e3 + 5; const int maxn = MAXN; const long long MOD = 1e8 + 7; #define rep(i,t,n) for(int i =(t);i<=(n);++i) #define per(i,n,t) for(int i =(n);i>=(t);--i) #define mmm(a,b) memset(a,b,sizeof(a)) #define x first #define y second int phi[MAXN], prime[MAXN]; int isntp[maxn]; void sieve(int n) { int m = (int)sqrt(n + 0.5); mmm(isntp, 0); rep(i, 2, m)if (!isntp[i])for (int j = i * i; j <= n; j += i)isntp[j] = 1; } int ans[maxn]; int smain(); #define ONLINE_JUDGE int main() { //ios::sync_with_stdio(false); #ifndef ONLINE_JUDGE FILE *myfile; myfile = freopen("C:\Users\acm-14\Desktop\test\b.in", "r", stdin); if (myfile == NULL) fprintf(stdout, "error on input freopen "); FILE *outfile; outfile = freopen("C:\Users\acm-14\Desktop\test\out.txt", "w", stdout); if (outfile == NULL) fprintf(stdout, "error on output freopen "); long _begin_time = clock(); #endif smain(); #ifndef ONLINE_JUDGE long _end_time = clock(); printf("time = %ld ms.", _end_time - _begin_time); #endif return 0; } int b[maxn], j[maxn]; pair<int, int> p[maxn]; int smain() { int n; int kase = 0; while (cin >> n && n) { printf("Case %d: ", ++kase); rep(i, 1, n) { cin >> p[i].y >> p[i].x; } sort(p + 1, p + 1 + n); int cur = 0;; int ans = 0; per(i,n,1) { cur += p[i].y; ans = max(ans, cur + p[i].x); } cout << ans << endl; } /*don't delete*/ return 0; } /*, 3 2 5 3 2 2 1 3 3 3 4 4 5 5 0 0 */
算法：直觉贪心+排序
ps:贪心的依据：ans=max(ans,cur+army[i].job)答案有这样的形式，cur是当前交待的总时间，考虑相邻的两个，总的cur是一样的，显然army.job短的人放在后面更优，所以就按照job降序排序了。
电容键盘可以光速连按啊prprprprprprprprprrprprprprpprprprprprprprrprprrprprprprrprpprrpprprpr
eg3‘
https://cn.vjudge.net/problem/UVA-11300
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<algorithm> #include<iostream> #include<math.h> #include<ctime> #include<string> #include<vector> using namespace std; typedef long long ll; const int MAXN = 1e6 + 5; const int maxn = MAXN; const long long MOD = 1e9 + 7; #define rep(i,t,n) for(int i =(t);i<=(n);++i) #define per(i,n,t) for(int i =(n);i>=(t);--i) #define mmm(a,b) memset(a,b,sizeof(a)) #define x first #define y second int smain(); #define ONLINE_JUDGE int main() { //ios::sync_with_stdio(false); #ifndef ONLINE_JUDGE FILE *myfile; myfile = freopen("C:\Users\acm-14\Desktop\test\b.in", "r", stdin); if (myfile == NULL) fprintf(stdout, "error on input freopen "); FILE *outfile; outfile = freopen("C:\Users\acm-14\Desktop\test\out.txt", "w", stdout); if (outfile == NULL) fprintf(stdout, "error on output freopen "); long _begin_time = clock(); #endif smain(); #ifndef ONLINE_JUDGE long _end_time = clock(); printf("time = %ld ms.", _end_time - _begin_time); #endif return 0; } long long A[maxn], C[maxn], tot, M; int smain() { int n; while (cin >> n) { tot = 0; rep(i, 1, n)scanf("%lld", &A[i]), tot += A[i]; M = tot / n; C[0] = 0; rep(i, 1, n)C[i] = C[i - 1] + A[i] - M; sort(C, C + n); long long x1 = C[n / 2], ans = 0; for (int i = 0; i < n; i++) { ans += abs(x1 - C[i]); } printf("%lld ", ans); } /*don't delete*/ return 0; } /*, 3 100 100 100 4 1 2 5 4 */
算法：代数分析题 。中位数求方程组目标函数最值
ps：第一道代数题，，用一个for递推地算出系数，把系数存在数组c里，想不到想不到，
eg4:
https://cn.vjudge.net/problem/UVALive-3708
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<algorithm> #include<iostream> #include<math.h> #include<ctime> #include<string> #include<vector> using namespace std; typedef long long ll; const int MAXN = 1e6 + 5; const int maxn = MAXN; const long long MOD = 1e9 + 7; #define rep(i,t,n) for(int i =(t);i<=(n);++i) #define per(i,n,t) for(int i =(n);i>=(t);--i) #define mmm(a,b) memset(a,b,sizeof(a)) #define x first #define y second int smain(); #define ONLINE_JUDGE int main() { //ios::sync_with_stdio(false); #ifndef ONLINE_JUDGE FILE *myfile; myfile = freopen("C:\Users\acm-14\Desktop\test\b.in", "r", stdin); if (myfile == NULL) fprintf(stdout, "error on input freopen "); FILE *outfile; outfile = freopen("C:\Users\acm-14\Desktop\test\out.txt", "w", stdout); if (outfile == NULL) fprintf(stdout, "error on output freopen "); long _begin_time = clock(); #endif smain(); #ifndef ONLINE_JUDGE long _end_time = clock(); printf("time = %ld ms.", _end_time - _begin_time); #endif return 0; } int smain() { int n, m; while (cin >> n >> m) { double ans = 0; rep(i, 1, n - 1) { double pos = (double)(n + m) / n * i; ans += abs(pos - floor(pos + 0.5))/(n+m); } printf("%.4lf ", ans * 10000); } /*don't delete*/ return 0; } /*, 3 100 100 100 4 1 2 5 4 */
算法：几何想法
ps：四舍五入找最近点是真的sao
eg5
https://cn.vjudge.net/problem/UVA-10881
算法：完全弹性碰撞的想法题（两个完全弹性碰撞的粒子可以看成互相穿过去！）+rank记录顺序技巧
坑：sample output复制到vs里面被过滤掉了回车，然后输出格式错了orz。另外turning细节，前后两个一起赋值。
#include <iostream> #include <vector> #include <cstdlib> #include <algorithm> #include <cstring> #include <cmath> #include<cstdio> #include<vector> #include<ctime> #include<string> #include<map> #define rep(i,t,n) for(int i =(t);i<=(n);++i) #define per(i,n,t) for(int i =(n);i>=(t);--i) #define mmm(a,b) memset(a,b,sizeof(a)) using namespace std; typedef long long ll; const int maxn = 1e4 + 5; const double PI = acos(-1.0); struct ant { int x, rk; int dir; }a[maxn],b[maxn]; bool cmp(ant a, ant b) { return a.x < b.x; } bool cmp2(ant a, ant b) { return a.rk < b.rk; } int main() { int kase = 0; int t; cin >> t; while (t--) { int l, time, n; cin >> l >> time >> n; rep(i, 1, n) { string S; int x; cin >> x >> S; a[i].x = x; a[i].dir = S == "R" ? 1 : -1; a[i].rk = i; } sort(a + 1, a + 1 + n,cmp); rep(i, 1, n) { b[i].x = a[i].x + a[i].dir * time; b[i].dir = a[i].dir; } sort(b + 1, b + 1 + n,cmp); rep(i, 1, n)b[i].rk = a[i].rk; rep(i, 1, n - 1)if (b[i].x == b[i + 1].x)b[i].dir =b[i+1].dir= 0; sort(b + 1, b + 1 + n, cmp2); printf("Case #%d: ", ++kase); rep(i, 1, n) { if (b[i].x<0 || b[i].x>l)puts("Fell off"); else { cout << b[i].x << ' '; if (b[i].dir == 0)puts("Turning"); else puts(b[i].dir == 1 ? "R" : "L"); } } cout << endl; } //cin >> t; } /* Sample Input 2 10 1 4 1 R 5 R 3 L 10 R 10 2 3 4 R 5 L 8 R Sample Output Case #1: 2 Turning 6 R 2 Turning Fell off Case #2: 3 L 6 R 10 R*/
eg6
算法：贪心地做，蓝书上有证明，不怎么看得懂
坑：i写成j，WF到底是WF
#include<algorithm> #include<iostream> #include<stdlib.h> #include<string.h> #include<math.h> #include<stdio.h> #include<vector> #include<queue> #include<string> #include<ctime> #include<stack> #include<map> #include<set> #include<list> using namespace std; #define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++) #define per(i,j,k) for(int i = (int)j;i >= (int)k;i --) #define debug(x) cerr<<#x<<" = "<<(x)<<endl #define mmm(a,b) memset(a,b,sizeof(a)) #define pb push_back //#define x first //#define y second typedef double db; typedef long long ll; const int MAXN = 12;; const int maxn = MAXN; const double eps = 1e-8; const double PI = acos(-1.0); string view[maxn][maxn]; int pos[maxn][maxn][maxn]; int n; void get(int k, int i, int j, int len, int &x, int &y, int &z) { int nn = n - 1; if (k == 0) { x = len, z = i, y = j; } if (k == 1) { y = len, x = nn - j; z = i; } if (k == 2) { z = i, x = nn - len, y = nn - j; } if (k == 3) { z = i; x = j; y = nn - len; } if (k == 4) { x = nn - i, y = j, z = len; } if (k == 5) { y = j, x = i, z = nn - len; } } int main() { while (cin >> n && n) { rep(i, 0, n - 1)rep(k, 0, 5) { cin >> view[k][i]; } int nn = n - 1; rep(i, 0, nn)rep(j, 0, nn)rep(k, 0, nn)pos[i][j][k] = '#'; int x = 0, y = 0, z = 0; rep(k, 0, 5)rep(i, 0, nn)rep(j, 0, nn) { if (view[k][i][j] == '.') { rep(d, 0, nn) { get(k, i, j, d, x, y, z); pos[x][y][z] = '.'; } } } while (1) { bool done = 1; rep(k, 0, 5)rep(i, 0, nn)rep(j, 0, nn)if (view[k][i][j] != 0) { int bug = 1; rep(d, 0, nn) { get(k, i, j, d, x, y, z); if (pos[x][y][z] == '.')continue; if (pos[x][y][z] == '#') { pos[x][y][z] = view[k][i][j]; {bug = 0; break; } } if (pos[x][y][z] == view[k][i][j]) { bug = 0; break; } pos[x][y][z] = '.'; done = 0; } if (0) { rep(i, 0, nn) { rep(j, 0, nn) { rep(k, 0, nn)cout << (char)pos[j][k][i]; cout << endl; }cout << endl; } rep(i, 0, nn)cout << "---"; cout << endl; } } if (done)break; } int ans = 0; rep(i, 0, nn)rep(j, 0, nn)rep(k, 0, nn)if (pos[i][j][k]!='.')ans++; //cout << ans << endl; printf("Maximum weight: %d gram(s) ", ans); } } /* 3 .R. YYR .Y. RYY .Y. .R. GRB YGR BYG RBY GYB GRB .R. YRR .Y. RRY .R. .Y. 2 ZZ ZZ ZZ ZZ ZZ ZZ ZZ ZZ ZZ ZZ ZZ ZZ 0 */
eg7
https://cn.vjudge.net/problem/UVA-11464
算法：暴力枚举n*n棋盘的第一行，然后递推地得出下面的每一行。
坑：暴力算法写错*3 orz
#include<algorithm> #include<iostream> #include<stdlib.h> #include<string.h> #include<math.h> #include<stdio.h> #include<vector> #include<queue> #include<string> #include<ctime> #include<stack> #include<map> #include<set> #include<list> using namespace std; #define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++) #define per(i,j,k) for(int i = (int)j;i >= (int)k;i --) #define debug(x) cerr<<#x<<" = "<<(x)<<endl #define mmm(a,b) memset(a,b,sizeof(a)) #define pb push_back //#define x first //#define y second typedef double db; typedef long long ll; const int MAXN = 20;; const int maxn = MAXN; const double eps = 1e-8; const double PI = acos(-1.0); const int INF = 1e9+10; int n; int a[maxn][maxn]; int b[maxn][maxn]; int check(int s) { int ret = 0; rep(i, 0, n-1) { if (((s&(1 << i)) != 0))b[1][i + 1] = 1; else b[1][i + 1] = 0; if (b[1][i + 1] == 0 && a[1][i + 1] == 1)return INF; else if (b[1][i + 1] != a[1][i + 1])ret++; } rep(i,2,n) rep(j, 1, n) { int prt = 0; //if (i - 2 < 1 || j - 1 < 1 || i + 1 > n)continue; if(i-1>=1&&j-1>=1)prt += b[i - 1][j - 1]; if(i-1>=1&&j+1<=n)prt += b[i - 1][j + 1]; if(i-2>=1)prt += b[i - 2][j]; if (prt % 2 == 0) { if (a[i][j] == 1)return INF; b[i][j] = 0; } else { if (a[i][j] == 0)ret++,b[i][j]=1; else b[i][j] = 1; } } return ret; } int main() { int t; cin >> t; int kase = 0; while (t--) { cin >> n; rep(i, 1, n)rep(j, 1, n)cin >> a[i][j]; int ans = INF; rep (s, 0, (1 << n) - 1) { ans = min(ans, check(s)); } if (ans == INF)ans = -1; printf("Case %d: %d ", ++kase, ans); } //cin >> t; } /* 2 3 0 0 0 1 0 0 0 0 0 3 3 0 0 0 0 0 0 0 0 0 3 0 0 0 1 0 0 0 0 0 3 1 1 1 1 1 1 0 0 0 */
eg8
套路：骰子类的题套路（polya的群）。pose处理：写程序打表记录所有状态，动态地写。
打表代码：
#include<algorithm> #include<iostream> #include<stdlib.h> #include<string.h> #include<assert.h> #include<math.h> #include<stdio.h> #include<vector> #include<queue> #include<string> #include<ctime> #include<stack> #include<map> #include<set> #include<list> using namespace std; #define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++) #define per(i,j,k) for(int i = (int)j;i >= (int)k;i --) #define debug(x) cerr<<#x<<" = "<<(x)<<endl #define mmm(a,b) memset(a,b,sizeof(a)) #define pb push_back //#define x first //#define y second typedef double db; typedef long long ll; const int MAXN = 100010;; const int maxn = 12e4; const db eps = 1e-7; const double PI = acos(-1.0); int l[] = { 4,0,2,3,5,1 }; int up[] = { 2,1,5,0,4,3 }; void rot(int * T, int * p) { int q[6]; memcpy(q, p, sizeof(q)); rep(i, 0, 5)p[i] = T[q[i]]; } void print() { int p0[6] = { 0,1,2,3,4,5 }; printf("int dice24[24][6]={ "); rep(i, 0, 5) { int p[6]; memcpy(p, p0, sizeof(p0)); if (i == 0)rot(up, p); if (i == 1)rot(l, p), rot(up, p); if (i == 2); if (i == 3)rot(up, p), rot(up, p); if (i == 4)rot(l, p), rot(l, p), rot(l, p), rot(up, p); if (i == 5)rot(l, p), rot(l, p), rot(up, p); rep(i, 0, 3) { printf("{%d, %d, %d, %d, %d, %d}, ", p[0], p[1], p[2], p[3], p[4], p[5]); rot(l, p); } } printf("}; "); } int main() { int n; print(); cin >> n; } /* */
AC代码：
#include<algorithm> #include<iostream> #include<stdlib.h> #include<string.h> #include<assert.h> #include<math.h> #include<stdio.h> #include<vector> #include<queue> #include<string> #include<ctime> #include<stack> #include<map> #include<set> #include<list> using namespace std; #define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++) #define REP(i,j,k) for(int i = (int)j;i < (int)k;i ++) #define per(i,j,k) for(int i = (int)j;i >= (int)k;i --) #define debug(x) cerr<<#x<<" = "<<(x)<<endl #define mmm(a,b) memset(a,b,sizeof(a)) #define pb push_back //#define x first //#define y second typedef double db; typedef long long ll; const int MAXN = 100010;; const int maxn = 1005; const db eps = 1e-7; map<string,int>names; int dice[maxn][6]; int n,ans,r[maxn]; int color[maxn][6]; int idx = 0; int dice24[24][6] = { { 2, 1, 5, 0, 4, 3 }, { 2, 0, 1, 4, 5, 3 }, { 2, 4, 0, 5, 1, 3 }, { 2, 5, 4, 1, 0, 3 }, { 4, 2, 5, 0, 3, 1 }, { 5, 2, 1, 4, 3, 0 }, { 1, 2, 0, 5, 3, 4 }, { 0, 2, 4, 1, 3, 5 }, { 0, 1, 2, 3, 4, 5 }, { 4, 0, 2, 3, 5, 1 }, { 5, 4, 2, 3, 1, 0 }, { 1, 5, 2, 3, 0, 4 }, { 5, 1, 3, 2, 4, 0 }, { 1, 0, 3, 2, 5, 4 }, { 0, 4, 3, 2, 1, 5 }, { 4, 5, 3, 2, 0, 1 }, { 1, 3, 5, 0, 2, 4 }, { 0, 3, 1, 4, 2, 5 }, { 4, 3, 0, 5, 2, 1 }, { 5, 3, 4, 1, 2, 0 }, { 3, 4, 5, 0, 1, 2 }, { 3, 5, 1, 4, 0, 2 }, { 3, 1, 0, 5, 4, 2 }, { 3, 0, 4, 1, 5, 2 }, }; int ID(const char* name) { string s(name); if (names.count(s))return names[s]; names[s] = ++idx; return names[s]; } void check() { rep(i, 0, n-1)rep(j, 0, 5)color[i][dice24[r[i]][j]] = dice[i][j]; int tot = 0; rep(j, 0, 5) { int cnt[maxn]; mmm(cnt, 0); int maxface = 0; rep(i, 0, n-1)maxface = max(maxface, ++cnt[color[i][j]]); tot += n - maxface; } ans = min(ans, tot); } void dfs(int x) { if (x == n)check(); else rep(i, 0, 23) { r[x] = i; dfs(x + 1); } } int main() { while (cin >> n && n) { names.clear(); idx = 0; rep(i, 0, n-1)rep(j, 0, 5) { char name[30]; scanf("%s", name); dice[i][j] = ID(name); } ans = n * 6; r[0] = 0; dfs(1); cout << ans << endl; } } /* 3 scarlet green blue yellow magenta cyan blue pink green magenta cyan lemon purple red blue yellow cyan green 2 red green blue yellow magenta cyan cyan green blue yellow magenta red 2 red green gray gray magenta cyan cyan green gray gray magenta red 2 red green blue yellow magenta cyan magenta red blue yellow cyan green 3 red green blue yellow magenta cyan cyan green blue yellow magenta red magenta red blue yellow cyan green 3 blue green green green green blue green blue blue green green green green green green green green sea-green 3 red yellow red yellow red yellow red red yellow yellow red yellow red red red red red red 4 violet violet salmon salmon salmon salmon violet salmon salmon salmon salmon violet violet violet salmon salmon violet violet violet violet violet violet salmon salmon 1 red green blue yellow magenta cyan 4 magenta pink red scarlet vermilion wine-red aquamarine blue cyan indigo sky-blue turquoise-blue blond cream chrome-yellow lemon olive yellow chrome-green emerald-green green olive vilidian sky-blue 0 4 2 0 0 2 3 4 4 0 16 */
eg9
套路：经典爆搜dfs。
#include<algorithm> #include<iostream> #include<stdlib.h> #include<string.h> #include<assert.h> #include<math.h> #include<stdio.h> #include<vector> #include<queue> #include<string> #include<ctime> #include<stack> #include<map> #include<set> #include<list> using namespace std; #define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++) #define REP(i,j,k) for(int i = (int)j;i < (int)k;i ++) #define per(i,j,k) for(int i = (int)j;i >= (int)k;i --) #define debug(x) cerr<<#x<<" = "<<(x)<<endl #define mmm(a,b) memset(a,b,sizeof(a)) #define pb push_back //#define x first //#define y second typedef double db; typedef long long ll; const int MAXN = 100010;; const int maxn = 1005; const db eps = 1e-7; const char* mahjong[] = { "1T","2T","3T","4T","5T","6T","7T","8T","9T", "1S","2S","3S","4S","5S","6S","7S","8S","9S", "1W","2W","3W","4W","5W","6W","7W","8W","9W", "DONG","NAN","XI","BEI", "ZHONG","FA","BAI" }; int convert(char *s) { REP(i, 0, 34) { if (strcmp(mahjong[i], s) == 0)return i; } return -1; } int cnt[34]; bool search(int dep) { REP(i, 0, 34)if (cnt[i] >= 3) { if (dep == 3)return 1; cnt[i] -= 3; if (search(dep + 1))return 1; cnt[i] += 3; } rep(i, 0, 24)if (i % 9 <= 6 && cnt[i] >= 1 && cnt[i + 1] >= 1 && cnt[i + 2] >= 1) { if (dep == 3)return 1; cnt[i] -= 1, cnt[i + 1] -= 1, cnt[i + 2] -= 1; if (search(dep + 1))return 1; cnt[i] += 1, cnt[i + 1] += 1, cnt[i + 2] += 1; } return 0; } bool check() { REP(i, 0, 34) if (cnt[i] >= 2) { cnt[i] -= 2; if (search(0))return 1; cnt[i] += 2; } return 0; } int main() { int kase = 0; char s[100]; int mj[15]; bool ok=0; while (cin >> s) { if (s[0] == '0')break; printf("Case %d:", ++kase); mj[0] = convert(s); rep(i, 1, 12) { cin >> s; mj[i] = convert(s); } ok = 0; REP(i, 0, 34) { mmm(cnt, 0); REP(j, 0, 13)cnt[mj[j]]++; if (cnt[i] >= 4)continue; cnt[i]++; if (check()) { ok = 1; cout << ' '<<mahjong[i]; } cnt[i]--; } if (!ok)puts(" Not ready"); else cout << endl; } } /* */
eg10:
https://cn.vjudge.net/problem/UVA-11384
int f(int n) { return n == 1 ? 1 : f(n / 2) + 1; } int smain() { int n; while (cin >> n)cout << f(n) << endl; /*don't delete*/ return 0; }
算法：经典瞎搞（想法）题
ps:瞎搞入门啊
eg11:
套路：构建递归函数。汉诺塔类问题从最大的那个盘子考虑。
#include<algorithm> #include<iostream> #include<stdlib.h> #include<string.h> #include<assert.h> #include<math.h> #include<stdio.h> #include<vector> #include<queue> #include<string> #include<ctime> #include<stack> #include<map> #include<set> #include<list> using namespace std; #define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++) #define REP(i,j,k) for(int i = (int)j;i < (int)k;i ++) #define per(i,j,k) for(int i = (int)j;i >= (int)k;i --) #define debug(x) cerr<<#x<<" = "<<(x)<<endl #define mmm(a,b) memset(a,b,sizeof(a)) #define pb push_back //#define x first //#define y second typedef double db; typedef long long ll; const int MAXN = 100010;; const int maxn = 1005; const db eps = 1e-7; int start[maxn], finish[maxn]; ll f(int *P, int i, int final) { if (i == 0)return 0; if (P[i] == final)return f(P, i - 1, final); return f(P, i - 1, 6 - P[i] - final) + (1LL << (i - 1)); } int main() { int kase = 0; int n; while (cin >> n && n) { rep(i, 1, n)cin >> start[i]; rep(i, 1, n)cin >> finish[i]; int k = n; while (k >= 1 && start[k] == finish[k])k--; long long ans = 0; if (k >= 1) { int other = 6 - start[k] - finish[k]; ans = f(start, k - 1, other) + f(finish, k - 1, other) + 1; } printf("Case %d: %lld ", ++kase, ans); } } /* */
eg12:
套路：最小值最大用二分。用map里套vector简化代码。还有注意二分的两种写法(表示自己并不明白）。
坑：没买全 二分的判断函数要返回false，另外本题没有点明单调性（价格越高，品质越高） 虽然是常识，但也可能导致二分算法错（青岛的教训）
#include<algorithm> #include<iostream> #include<stdlib.h> #include<string.h> #include<assert.h> #include<math.h> #include<stdio.h> #include<vector> #include<queue> #include<string> #include<ctime> #include<stack> #include<map> #include<set> #include<list> using namespace std; #define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++) #define REP(i,j,k) for(int i = (int)j;i < (int)k;i ++) #define per(i,j,k) for(int i = (int)j;i >= (int)k;i --) #define debug(x) cerr<<#x<<" = "<<(x)<<endl #define mmm(a,b) memset(a,b,sizeof(a)) #define pb push_back //#define x first //#define y second typedef double db; typedef long long ll; const int MAXN = 100010;; const int maxn = 1005; const db eps = 1e-7; map<string, vector<pair<int, int> > >mmp; int n, b; bool ok(int x) { int tot = 0; for (auto t : mmp) { int mn = 1e9 + 5; for (auto tt : t.second)if(tt.second>=x) { mn = min(mn, tt.first); } if (mn == 1e9 + 5)return false; tot += mn; } if (tot <= b)return true; else return false; } int main() { int T; cin >> T; while (T--) { mmp.clear(); cin >> n >> b; int maxq = 0; rep(i, 1, n) { string s,ss; int p, q; cin >> s>>ss>>p>>q; maxq = max(maxq, q); mmp[s].push_back({ p,q }); } int L = 0, R = maxq; while (L < R) { int mid = L + (R - L + 1) / 2; if (ok(mid))L = mid; else R = mid - 1; } cout << L << endl; } //cin >> T; } /* 1 18 800 processor 3500_MHz 66 5 processor 4200_MHz 103 7 processor 5000_MHz 156 9 processor 6000_MHz 219 12 memory 1_GB 35 3 memory 2_GB 88 6 memory 4_GB 170 12 mainbord all_onboard 52 10 harddisk 250_GB 54 10 harddisk 500_FB 99 12 casing midi 36 10 monitor 17_inch 157 5 monitor 19_inch 175 7 monitor 20_inch 210 9 monitor 22_inch 293 12 mouse cordless_optical 18 12 mouse microsoft 30 9 keyboard office 4 10 */
eg13:
https://cn.vjudge.net/problem/UVALive-3635
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<algorithm> #include<iostream> #include<math.h> #include<ctime> #include<string> using namespace std; typedef long long ll; const int MAXN = 1e5 + 5; const int maxn = MAXN; const long long MOD = 1e8 + 7; #define rep(i,t,n) for(int i =(t);i<=(n);++i) #define per(i,n,t) for(int i =(n);i>=(t);--i) #define mmm(a,b) memset(a,b,sizeof(a)) int phi[MAXN], prime[MAXN]; int isntp[maxn]; void sieve(int n) { int m = (int)sqrt(n + 0.5); mmm(isntp, 0); rep(i, 2, m)if (!isntp[i])for (int j = i * i; j <= n; j += i)isntp[j] = 1; } int ans[maxn]; int smain(); #define ONLINE_JUDGE int main() { //ios::sync_with_stdio(false); #ifndef ONLINE_JUDGE FILE *myfile; myfile = freopen("C:\Users\acm-14\Desktop\test\b.in", "r", stdin); if (myfile == NULL) fprintf(stdout, "error on input freopen "); FILE *outfile; outfile = freopen("C:\Users\acm-14\Desktop\test\out.txt", "w", stdout); if (outfile == NULL) fprintf(stdout, "error on output freopen "); long _begin_time = clock(); #endif smain(); #ifndef ONLINE_JUDGE long _end_time = clock(); printf("time = %ld ms.", _end_time - _begin_time); #endif return 0; } double a[maxn]; int n, f; bool ok(double x) { int cnt = 0; rep(i, 1, n) { cnt += floor(a[i] / x); } return cnt >= f; } int smain() { int t; cin >> t; while (t--) { cin >> n >> f; f++; rep(i, 1, n)scanf("%lf", &a[i]),a[i]=a[i]*a[i]*acos(-1); double l = 0, r = 1e8*acos(-1); while (abs(l-r)> 1e-5) { double mid = (l + r) / 2; if (ok(mid))l = mid; else r = mid; } printf("%.5lf ", l); } return 0; } /* 4 3 3 4 3 3 1 24 5 10 5 1 4 2 3 4 5 6 5 4 2 */
算法：经典eps二分，
坑点：输出cout会wa。改成了printf后忘记换行了orz
ps：第一发写完发现和书上代码基本一样！
eg14
https://cn.vjudge.net/problem/UVA-11520
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<algorithm> #include<iostream> #include<math.h> #include<ctime> #include<string> using namespace std; typedef long long ll; const int MAXN = 1e5 + 5; const int maxn = MAXN; const long long MOD = 1e8 + 7; #define rep(i,t,n) for(int i =(t);i<=(n);++i) #define per(i,n,t) for(int i =(n);i>=(t);--i) #define mmm(a,b) memset(a,b,sizeof(a)) int phi[MAXN], prime[MAXN]; int isntp[maxn]; void sieve(int n) { int m = (int)sqrt(n + 0.5); mmm(isntp, 0); rep(i, 2, m)if (!isntp[i])for (int j = i * i; j <= n; j += i)isntp[j] = 1; } int ans[maxn]; int smain(); #define ONLINE_JUDGE int main() { //ios::sync_with_stdio(false); #ifndef ONLINE_JUDGE FILE *myfile; myfile = freopen("C:\Users\acm-14\Desktop\test\b.in", "r", stdin); if (myfile == NULL) fprintf(stdout, "error on input freopen "); FILE *outfile; outfile = freopen("C:\Users\acm-14\Desktop\test\out.txt", "w", stdout); if (outfile == NULL) fprintf(stdout, "error on output freopen "); long _begin_time = clock(); #endif smain(); #ifndef ONLINE_JUDGE long _end_time = clock(); printf("time = %ld ms.", _end_time - _begin_time); #endif return 0; } string s[11]; int cnt[256]; int n; char get(int x,int y) { mmm(cnt, 0); char ret = 0; rep(i,-1,1) rep(j, -1, 1)if(abs(i)+abs(j)<2) { int dx = x + i, dy = y + j; if (dx >= 0 && dx < n&&dy >= 0 && dy < n) { //if (s[dx][dy] == '.')ret = max((int)ret, 'A' - 1); cnt[s[dx][dy]]++; } } rep(i, 'A', 'Z')if (!cnt[i])return i; } int smain() { int t; cin >> t; int kase = 0; while (t--) { printf("Case %d: ", ++kase); cin >> n; rep(i, 0, n-1) { cin >> s[i]; } rep(i, 0, n-1) rep(j, 0, n-1)if(s[i][j]=='.') { s[i][j] = get(i,j); } rep(i, 0, n-1)cout << s[i] << endl; } return 0; } /* 3 3 ..B ... ... 3 B.. ... ..A 3 3 ... .C. Z.. 3 ... A.X ... */
算法：了解一下字典序，书上的get函数有一点剪枝的
坑点：string输入 循环是到n-1！
ps：Morass 大佬也刷uva， 另外uva不把文件输入删掉也能ac啊？
eg15
https://cn.vjudge.net/problem/UVALive-3902
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<algorithm> #include<iostream> #include<math.h> #include<ctime> #include<string> #include<vector> using namespace std; typedef long long ll; const int MAXN = 1e3 + 5; const int maxn = MAXN; const long long MOD = 1e8 + 7; #define rep(i,t,n) for(int i =(t);i<=(n);++i) #define per(i,n,t) for(int i =(n);i>=(t);--i) #define mmm(a,b) memset(a,b,sizeof(a)) int phi[MAXN], prime[MAXN]; int isntp[maxn]; void sieve(int n) { int m = (int)sqrt(n + 0.5); mmm(isntp, 0); rep(i, 2, m)if (!isntp[i])for (int j = i * i; j <= n; j += i)isntp[j] = 1; } int ans[maxn]; int smain(); #define ONLINE_JUDGE int main() { //ios::sync_with_stdio(false); #ifndef ONLINE_JUDGE FILE *myfile; myfile = freopen("C:\Users\acm-14\Desktop\test\b.in", "r", stdin); if (myfile == NULL) fprintf(stdout, "error on input freopen "); FILE *outfile; outfile = freopen("C:\Users\acm-14\Desktop\test\out.txt", "w", stdout); if (outfile == NULL) fprintf(stdout, "error on output freopen "); long _begin_time = clock(); #endif smain(); #ifndef ONLINE_JUDGE long _end_time = clock(); printf("time = %ld ms.", _end_time - _begin_time); #endif return 0; } vector<int> E[maxn], nodes[maxn]; int n, s, k, fa[maxn]; bool covered[maxn]; void dfs(int u, int f, int d) { fa[u] = f; int nc = E[u].size(); if (nc == 1 && d > k)nodes[d].push_back(u); for (int i = 0; i < nc; i++) { int v = E[u][i]; if (v != f)dfs(v, u, d + 1); } } void dfs2(int u, int f, int d) { covered[u] = 1; int nc = E[u].size(); for (int i = 0; i < nc; i++) { int v = E[u][i]; if (v != f && d < k)dfs2(v, u, d + 1); } } int solve() { int ans = 0; mmm(covered, 0); for(int d=n-1;d>k;d--) for (int i = 0; i < nodes[d].size(); i++) { int u = nodes[d][i]; if (covered[u])continue; int v = u; for (int j = 0; j < k; j++)v = fa[v]; dfs2(v, -1, 0); ans++; } return ans; } int smain() { int t; cin >> t; while (t--) { cin >> n >> s >> k; rep(i, 1, n)E[i].clear(), nodes[i].clear(); rep(i, 1, n-1) { int x, y; cin >> x >> y; E[x].push_back(y); E[y].push_back(x); } dfs(s, -1, 0); cout << solve() << endl; } cin >> t; return 0; } /* 2 14 12 2 1 2 2 3 3 4 4 5 5 6 7 5 8 5 4 9 10 3 2 12 12 14 13 14 14 11 14 3 4 1 2 2 3 3 4 4 5 5 6 7 5 8 5 4 9 10 3 2 12 12 14 13 14 14 11 */
算法：树上贪心dfs暴力
ps：蓝书的代码还是舒服啊
eg16
套路：想法+二分题收尾。二分是礼物种类越多越能满足分礼物约束，
想法1是：先让第一个人取[1,a[i] ] 的礼物，然后在不取前一个人的前提下，偶数尽量往前取，奇数往后取，这样（当总人数为奇数时）最后一个是往后取的，判一下他有没有取到[1,a[i] ]的礼物就行。
想法2是：如果我们建一个vis数组表示前一个人拿了几个，那算法就n^2logn 了 。我们考虑每一个人具体选了哪些不重要，重要的是选了几个，more precisely,要表达尽量往前取和往后取，我们只要把礼物分成前半部分与后半部分，以a[1]为分界，这样二分的judge函数就变成线性了
#include<algorithm> #include<iostream> #include<stdlib.h> #include<string.h> #include<assert.h> #include<math.h> #include<stdio.h> #include<vector> #include<queue> #include<string> #include<ctime> #include<stack> #include<map> #include<set> #include<list> using namespace std; #define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++) #define REP(i,j,k) for(int i = (int)j;i < (int)k;i ++) #define per(i,j,k) for(int i = (int)j;i >= (int)k;i --) #define debug(x) cerr<<#x<<" = "<<(x)<<endl #define mmm(a,b) memset(a,b,sizeof(a)) #define pb push_back //#define x first //#define y second typedef double db; typedef long long ll; const int MAXN = 100010;; const int maxn = 1e5+5; const db eps = 1e-7; int n, b; int a[maxn]; int vis[maxn] ; int l[maxn], r[maxn]; bool ok(int p) { int x = a[1], y = p - x; l[1] = x; r[1] = 0; rep(i, 2, n) { if (i % 2 == 0) { l[i] = min(x - l[i - 1],a[i]); r[i] = a[i] - l[i]; } else { r[i] = min(a[i], y - r[i - 1]); l[i] = a[i] - r[i]; } } return l[n] == 0; } int main() { while (cin >> n && n) { int maxa=0; rep(i, 1, n)scanf("%d", &a[i]),maxa=max(maxa,a[i]); if (n == 1)cout << a[1] << endl; else{ int ans = a[n] + a[1]; rep(i, 1, n - 1)ans = max(ans, a[i] + a[i + 1]); int L = ans, R = maxa*4; if (n % 2) { while (L <= R) { int mid = L + R >> 1; if (ok(mid))R = mid - 1; else L = mid + 1; } } cout << L << endl; } } //cin >> T; }
eg17
加速：计数排序
#include<algorithm> #include<iostream> #include<stdlib.h> #include<string.h> #include<assert.h> #include<math.h> #include<stdio.h> #include<vector> #include<queue> #include<string> #include<ctime> #include<stack> #include<map> #include<set> #include<list> using namespace std; #define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++) #define REP(i,j,k) for(int i = (int)j;i < (int)k;i ++) #define per(i,j,k) for(int i = (int)j;i >= (int)k;i --) #define debug(x) cerr<<#x<<" = "<<(x)<<endl #define mmm(a,b) memset(a,b,sizeof(a)) #define pb push_back //#define x first //#define y second typedef double db; typedef long long ll; const int MAXN = 100010;; const int maxn = 1e5+5; const db eps = 1e-7; int cnt[101]; int n; int main() { while (cin >> n && n) { int x; mmm(cnt, 0); rep(i, 1, n) { scanf("%d", &x); cnt[x]++; } int first = 1; rep(i, 1, 100) { while (cnt[i]--) { if (first)printf("%d", i), first = 0; else printf(" %d", i); } } cout << endl; //cin >> T; } } /* */
eg18
加速：线性算法。O（1）存储动态维护max
#include<algorithm> #include<iostream> #include<stdlib.h> #include<string.h> #include<assert.h> #include<math.h> #include<stdio.h> #include<vector> #include<queue> #include<string> #include<ctime> #include<stack> #include<map> #include<set> #include<list> using namespace std; #define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++) #define REP(i,j,k) for(int i = (int)j;i < (int)k;i ++) #define per(i,j,k) for(int i = (int)j;i >= (int)k;i --) #define debug(x) cerr<<#x<<" = "<<(x)<<endl #define mmm(a,b) memset(a,b,sizeof(a)) #define pb push_back //#define x first //#define y second typedef double db; typedef long long ll; const int MAXN = 100010;; const int maxn = 1e5+5; const db eps = 1e-7; int cnt[101]; int n; int main() { int T; cin >> T; while(T--){ int n; cin >> n; int a; int ans = -1e9; cin >> a; int maxa = a; rep(i, 2, n) { cin >> a; ans = max(ans, maxa - a); maxa = max(maxa, a); } cout << ans << endl; //cin >> T; } //cin >> T; } /* */
eg19
加速:stl找循环节，截取技巧。
套路：floyd判圈找循环节：比set快，O（1）。
#include<algorithm> #include<iostream> #include<sstream> #include<stdlib.h> #include<string.h> #include<assert.h> #include<math.h> #include<stdio.h> #include<vector> #include<queue> #include<string> #include<ctime> #include<stack> #include<map> #include<set> #include<list> using namespace std; #define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++) #define REP(i,j,k) for(int i = (int)j;i < (int)k;i ++) #define per(i,j,k) for(int i = (int)j;i >= (int)k;i --) #define debug(x) cerr<<#x<<" = "<<(x)<<endl #define mmm(a,b) memset(a,b,sizeof(a)) #define pb push_back //#define x first //#define y second typedef double db; typedef long long ll; const int MAXN = 100010;; const int maxn = 1e5+5; const db eps = 1e-7; int cnt[101]; int n; int next(int n, int k) { stringstream ss; ss << (long long)k*k; string s = ss.str(); if (s.length() > n)s = s.substr(0, n); int ans; stringstream ss2(s); ss2 >> ans; return ans; } set<int>S; int main() { int T; cin >> T; while(T--){ int n,k; cin >> n>>k; S.clear(); int ans = k; while (!S.count(k)) { S.insert(k); k = next(n, k); ans = max(ans, k); } cout << ans << endl; } //cin >> T; } /* 2 1 6 2 99 */
#include<algorithm> #include<iostream> #include<sstream> #include<stdlib.h> #include<string.h> #include<assert.h> #include<math.h> #include<stdio.h> #include<vector> #include<queue> #include<string> #include<ctime> #include<stack> #include<map> #include<set> #include<list> using namespace std; #define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++) #define REP(i,j,k) for(int i = (int)j;i < (int)k;i ++) #define per(i,j,k) for(int i = (int)j;i >= (int)k;i --) #define debug(x) cerr<<#x<<" = "<<(x)<<endl #define mmm(a,b) memset(a,b,sizeof(a)) #define pb push_back //#define x first //#define y second typedef double db; typedef long long ll; const int MAXN = 100010;; const int maxn = 1e5+5; const db eps = 1e-7; int cnt[101]; int n; int next(int n, int k) { stringstream ss; ss << (long long)k*k; string s = ss.str(); if (s.length() > n)s = s.substr(0, n); int ans; stringstream ss2(s); ss2 >> ans; return ans; } set<int>S; int main() { int T; cin >> T; while(T--){ int n,k; cin >> n>>k; S.clear(); int k1 = k, k2 = k; int ans = k; do { k1 = next(n, k1); k2 = next(n, k2); ans = max(ans, k2); k2 = next(n, k2); ans = max(ans, k2); } while (k1 != k2); cout << ans << endl; } //cin >> T; }
一下是一系列递推维护区间（一维二维三维，单调性）信息的线性优化。，可以说是dp了
eg20
加速：线性找区间某点最大覆盖线段数。
套路：解不等式组
#include<algorithm> #include<iostream> #include<sstream> #include<stdlib.h> #include<string.h> #include<assert.h> #include<math.h> #include<stdio.h> #include<vector> #include<queue> #include<string> #include<ctime> #include<stack> #include<map> #include<set> #include<list> using namespace std; #define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++) #define REP(i,j,k) for(int i = (int)j;i < (int)k;i ++) #define per(i,j,k) for(int i = (int)j;i >= (int)k;i --) #define debug(x) cerr<<#x<<" = "<<(x)<<endl #define mmm(a,b) memset(a,b,sizeof(a)) #define pb push_back //#define x first //#define y second typedef double db; typedef long long ll; const int MAXN = 100010;; const int maxn = 1e5+5; const db eps = 1e-7; //0<x+at<w void update(int x, int a, int w, double& L, double& R) { if (a == 0) { if (x <= 0 || x >= w)R = L - 1; } else if (a > 0) { L = max(L, -(double)x / a); R = min(R, (double)(w - x) / a); } else { L = max(L, (double)(w-x) / a); R = min(R, -(double)x / a); } } struct Event { double x; int type; bool operator <(const Event& a) const { return x < a.x || (x == a.x&&type > a.type); } }events[maxn*2]; int main() { int T; cin >> T; while(T--){ int w, h, n, e = 0; scanf("%d%d%d", &w, &h, &n); for (int i = 0; i < n; i++) { int x, y, a, b; scanf("%d%d%d%d", &x, &y, &a, &b); double L = 0, R = 1e9; update(x, a, w, L, R); update(y, b, h, L, R); if (R > L) { events[e++] = { L, 0 }; events[e++]= { R, 1 }; } } sort(events, events + e); int cnt = 0; int ans = 0; REP(i, 0, e) { if (events[i].type == 0)ans = max(ans, ++cnt); else cnt--; } cout << ans << endl; } cin >> T; } /* 2 4 2 2 -1 1 1 -1 5 2 -1 -1 13 6 7 3 -2 1 3 6 9 -2 -1 8 0 -1 -1 7 6 10 0 11 -2 2 1 -2 4 6 -1 3 2 -5 -1 */
eg21
加速：利用单调性，二分nlogn 再到线性 n
#include<algorithm> #include<iostream> #include<sstream> #include<stdlib.h> #include<string.h> #include<assert.h> #include<math.h> #include<stdio.h> #include<vector> #include<queue> #include<string> #include<ctime> #include<stack> #include<map> #include<set> #include<list> using namespace std; #define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++) #define REP(i,j,k) for(int i = (int)j;i < (int)k;i ++) #define per(i,j,k) for(int i = (int)j;i >= (int)k;i --) #define debug(x) cerr<<#x<<" = "<<(x)<<endl #define mmm(a,b) memset(a,b,sizeof(a)) #define pb push_back //#define x first //#define y second typedef double db; typedef long long ll; const int MAXN = 100010;; const int maxn = 1e5+5; const db eps = 1e-7; //0<x+at<w int a[maxn],s[maxn]; int main() { int n, S; while (cin >> n >> S) { int ans = 1e6; rep(i, 1, n)scanf("%d", &a[i]); rep(i, 1, n)s[i] = s[i - 1] + a[i]; rep(j, 1, n) { int i = lower_bound(s, s + j, s[j] - S) - s; if (i > 0)ans = min(ans, j - i + 1); } if (ans == 1e6)ans = 0; cout << ans<<endl; } } /* 10 15 5 1 3 5 10 7 4 9 2 8 5 11 1 2 3 4 5 */
#include<algorithm> #include<iostream> #include<sstream> #include<stdlib.h> #include<string.h> #include<assert.h> #include<math.h> #include<stdio.h> #include<vector> #include<queue> #include<string> #include<ctime> #include<stack> #include<map> #include<set> #include<list> using namespace std; #define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++) #define REP(i,j,k) for(int i = (int)j;i < (int)k;i ++) #define per(i,j,k) for(int i = (int)j;i >= (int)k;i --) #define debug(x) cerr<<#x<<" = "<<(x)<<endl #define mmm(a,b) memset(a,b,sizeof(a)) #define pb push_back //#define x first //#define y second typedef double db; typedef long long ll; const int MAXN = 100010;; const int maxn = 1e5+5; const db eps = 1e-7; //0<x+at<w int a[maxn],s[maxn]; int main() { int n, S; while (cin >> n >> S) { int ans = 1e6; rep(i, 1, n)scanf("%d", &a[i]); rep(i, 1, n)s[i] = s[i - 1] + a[i]; int i = 1; rep(j, 1, n) { if (s[i - 1] > s[j] - S)continue; while (s[i] < s[j] - S)i++; ans = min(ans,j - i + 1); } if (ans == 1e6)ans = 0; cout << ans<<endl; } } /* 10 15 5 1 3 5 10 7 4 9 2 8 5 11 1 2 3 4 5 */
eg22
加速：维护二维网格里的最大矩阵：维护每个各点向上延申最远点，以及这条线段左右移动的最远点。
#include<algorithm> #include<iostream> #include<sstream> #include<stdlib.h> #include<string.h> #include<assert.h> #include<math.h> #include<stdio.h> #include<vector> #include<queue> #include<string> #include<ctime> #include<stack> #include<map> #include<set> #include<list> using namespace std; #define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++) #define REP(i,j,k) for(int i = (int)j;i < (int)k;i ++) #define per(i,j,k) for(int i = (int)j;i >= (int)k;i --) #define debug(x) cerr<<#x<<" = "<<(x)<<endl #define mmm(a,b) memset(a,b,sizeof(a)) #define pb push_back //#define x first //#define y second typedef double db; typedef long long ll; const int MAXN = 1010;; const int maxn = 1e3+5; const db eps = 1e-7; int a[maxn],s[maxn]; int mat[maxn][maxn], up[maxn][maxn], l[maxn][maxn], r[maxn][maxn]; int main() { int t; cin >> t; while (t--) { int n, m; cin >> n >> m; rep(i, 1, n) rep(j, 1, m) { char c = getchar(); while (c != 'F'&&c != 'R') { c = getchar(); } mat[i][j] = c == 'F' ? 0 : 1; } int ans = 0; rep(i, 1, n) { int lo = 0, ro = m+1; rep(j, 1, m)if (mat[i][j] == 1)up[i][j] = l[i][j] = 0, lo = j; else { up[i][j] = i == 1 ? 1 : up[i - 1][j] + 1; l[i][j] = i == 1 ? lo + 1 : max(l[i - 1][j], lo + 1); } per(j, m, 1) if (mat[i][j] == 1)r[i][j] = m + 1, ro = j; else { r[i][j] = i == 1 ? ro - 1 : min(r[i - 1][j], ro - 1); ans = max(ans, up[i][j] * (r[i][j] - l[i][j] + 1)); } } cout << ans * 3<<endl; } //cin >> t; } /* 2 5 6 R F F F F F F F F F F F R R R F F F F F F F F F F F F F F F 5 5 R R R R R R R R R R R R R R R R R R R R R R R R R */
eg23
题意：给你一堆点，计算在一个矩形边长上的点数最大值。
加速：y坐标离散化。把矩形拆成两条横线两条竖线。横线用前缀和维护，竖线暴力维护。线性时间，再加上枚举上下界，O（n^3）.
#include<algorithm> #include<iostream> #include<sstream> #include<stdlib.h> #include<string.h> #include<assert.h> #include<math.h> #include<stdio.h> #include<vector> #include<queue> #include<string> #include<ctime> #include<stack> #include<map> #include<set> #include<list> using namespace std; #define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++) #define REP(i,j,k) for(int i = (int)j;i < (int)k;i ++) #define per(i,j,k) for(int i = (int)j;i >= (int)k;i --) #define debug(x) cerr<<#x<<" = "<<(x)<<endl #define mmm(a,b) memset(a,b,sizeof(a)) #define pb push_back //#define x first //#define y second typedef double db; typedef long long ll; const int MAXN = 110;; const int maxn = 1e2+5; const db eps = 1e-7; struct Point { int x, y; bool operator<(const Point& a)const { return x < a.x; } }p[maxn]; int n, m, y[maxn], on[maxn], on2[maxn], l[maxn]; int solve() { sort(p, p + n); sort(y, y + n); m = unique(y, y + n) - y;//离散化 if (m <= 2)return n; int ans = 0; REP(a, 0, m) REP(b, a + 1, m) { int ymin = y[a], ymax = y[b]; int k = 0; REP(i, 0, n) { if (i == 0 || p[i].x != p[i - 1].x) { k++; on[k] = on2[k] = 0; l[k] = l[k - 1] + on2[k - 1] - on[k - 1]; } if (p[i].y > ymin&&p[i].y < ymax) on[k]++; if (p[i].y >= ymin && p[i].y <= ymax) on2[k]++; } if (k <= 2)return n; int M = 0; rep(j, 1, k) { ans = max(ans, l[j] + on2[j] + M); M=max(M, on[j] - l[j]); } } return ans; } int main() { int kase = 0; while (cin >> n && n) { REP(i, 0, n) { cin >> p[i].x >> p[i].y; y[i] = p[i].y; } printf("Case %d: %d ", ++kase, solve()); } } /* 10 2 3 9 2 7 4 3 4 5 7 1 5 10 4 10 6 11 4 4 6 0 */
eg24
加速：三维前缀和 ， 具体原理也不怎么明白，当个板子用就好了
#include<algorithm> #include<iostream> #include<sstream> #include<stdlib.h> #include<string.h> #include<assert.h> #include<math.h> #include<stdio.h> #include<vector> #include<queue> #include<string> #include<ctime> #include<stack> #include<map> #include<set> #include<list> using namespace std; #define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++) #define REP(i,j,k) for(int i = (int)j;i < (int)k;i ++) #define per(i,j,k) for(int i = (int)j;i >= (int)k;i --) #define debug(x) cerr<<#x<<" = "<<(x)<<endl #define mmm(a,b) memset(a,b,sizeof(a)) #define pb push_back //#define x first //#define y second typedef double db; typedef long long ll; const int MAXN = 30;; const int maxn = 1e2+5; const db eps = 1e-7; ll S[maxn][maxn][maxn]; ll INF = 1ll << 60; void expand(int i, int& b0, int& b1, int& b2) { b0 = i & 1; i >>= 1; b1 = i & 1; i >>= 1; b2 = i & 1; } int sign(int b0, int b1, int b2) { return (b0 + b1 + b2) % 2 == 1 ? 1 : -1; } ll sum(int x1, int x2, int y1, int y2, int z1, int z2) { int dx = x2 - x1 + 1; int dy = y2 - y1 + 1; int dz = z2 - z1 + 1; ll s = 0; rep(i, 0, 7) { int b0, b1, b2; expand(i, b0, b1, b2); s -= S[x2 - b0 * dx][y2 - b1 * dy][z2 - b2 * dz] * sign(b0, b1, b2); } return s; } int main() { int t; cin >> t; while (t--) { int a, b, c, b1, b2, b0; cin >> a >> b >> c; mmm(S, 0); rep(x, 1, a)rep(y, 1, b)rep(z, 1, c)scanf("%lld", &S[x][y][z]); rep(x, 1, a)rep(y, 1, b)rep(z, 1, c)rep(i, 1, 7) { expand(i, b0, b1, b2); S[x][y][z] += S[x - b0][y - b1][z - b2] * sign(b0, b1, b2); } long long ans = -INF; rep(x1, 1, a)rep(x2, x1, a)rep(y1,1,b)rep(y2, y1, b) { long long M = 0; rep(z, 1, c) { long long s = sum(x1, x2, y1, y2, 1, z); ans = max(ans, s - M); M = min(M, s); } } cout << ans << endl; if (t)cout << endl; } //cin >> t; } /* 1 2 2 2 -1 2 0 -3 -2 -1 1 5 */
eg25
套路：用异或和压缩字符串，然后状压地2^n暴力,用map降低复杂度（中途相遇）O(2^(N/2)*logn)
#include<algorithm> #include<iostream> #include<sstream> #include<stdlib.h> #include<string.h> #include<assert.h> #include<math.h> #include<stdio.h> #include<vector> #include<queue> #include<string> #include<ctime> #include<stack> #include<map> #include<set> #include<list> using namespace std; #define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++) #define REP(i,j,k) for(int i = (int)j;i < (int)k;i ++) #define per(i,j,k) for(int i = (int)j;i >= (int)k;i --) #define debug(x) cerr<<#x<<" = "<<(x)<<endl #define mmm(a,b) memset(a,b,sizeof(a)) #define pb push_back //#define x first //#define y second typedef double db; typedef long long ll; const int MAXN = 30;; const int maxn = 24; const db eps = 1e-7; map<int, int>table; int bitcount(int x) { return x == 0 ? 0 : bitcount(x /2) + (x & 1); }//popcount int A[maxn]; int main() { int n; while (cin >> n) { REP(i, 0, n) { string s; cin >> s; A[i] = 0; for (auto t : s) {A[i] ^= (1 << (t - 'A'));} } table.clear(); int n1 = n / 2, n2 = n - n1; for (int i = 0; i < (1 << n1); i++) { int x = 0; REP(j, 0, n1)if (i & (1 << j))x ^= A[j]; if (!table.count(x) || bitcount(table[x]) < bitcount(i))table[x] = i; } int ans = 0; for (int i = 0; i < (1 << n2); i++) { int x = 0; for (int j = 0; j < n2; j++)if (i&(1 << j))x ^= A[n1+j]; if (table.count(x) && bitcount(ans) < bitcount(table[x]) + bitcount(i))ans = (i << n1) ^ table[x]; } cout << bitcount(ans) << endl; REP(i, 0, n)if (ans&(1 << i))cout << i + 1<<' '; cout << endl; } //cin >> t; } /* 1 ABC 6 ABD EG GE ABE AC BCD */
eg26
dp：约瑟夫递推地做
#include<algorithm> #include<iostream> #include<sstream> #include<stdlib.h> #include<string.h> #include<assert.h> #include<math.h> #include<stdio.h> #include<vector> #include<queue> #include<string> #include<ctime> #include<stack> #include<map> #include<set> #include<list> using namespace std; #define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++) #define REP(i,j,k) for(int i = (int)j;i < (int)k;i ++) #define per(i,j,k) for(int i = (int)j;i >= (int)k;i --) #define debug(x) cerr<<#x<<" = "<<(x)<<endl #define mmm(a,b) memset(a,b,sizeof(a)) #define pb push_back //#define x first //#define y second typedef double db; typedef long long ll; const int MAXN = 30;; const int maxn = 1e4+2; const db eps = 1e-7; int f[maxn]; int main() { int n, m, k; while (cin >> n >> k >> m && n) { f[1] = 0; rep(i, 2, n)f[i] = (f[i - 1] + k) % i; int ans = (m - k + 1 + f[n]) % n; if (ans <= 0)ans += n; cout << ans << endl; } } /* 8 5 3 100 9999 98 10000 10000 10000 0 0 0 */
eg27
dp：LCS转化为LIS 具体做法是对第一个序列离散化，然后在第二个里LIS
#include<algorithm> #include<iostream> #include<sstream> #include<stdlib.h> #include<string.h> #include<assert.h> #include<math.h> #include<stdio.h> #include<vector> #include<queue> #include<string> #include<ctime> #include<stack> #include<map> #include<set> #include<list> using namespace std; #define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++) #define REP(i,j,k) for(int i = (int)j;i < (int)k;i ++) #define per(i,j,k) for(int i = (int)j;i >= (int)k;i --) #define debug(x) cerr<<#x<<" = "<<(x)<<endl #define mmm(a,b) memset(a,b,sizeof(a)) #define pb push_back //#define x first //#define y second typedef double db; typedef long long ll; const int MAXN = 30;; const int maxn = 250*250+2; const int INF = 1e9; const db eps = 1e-7; int S[maxn], g[maxn], d[maxn]; int num[maxn]; int main() { int T; cin >> T; rep(k, 1, T) { int N, p, q, x; cin >> N >> p >> q; rep(i, 1, p + 1) { scanf("%d", &x); num[x] = i; } int n = 0; rep(i, 0, q) { scanf("%d", &x); if (num[x])S[n++] = num[x]; } rep(i, 1, n)g[i] = INF; int ans = 0; REP(i, 0, n) { int k = lower_bound(g + 1, g + n + 1, S[i]) - g; d[i] = k; g[k] = S[i]; ans = max(ans, d[i]); } printf("Case %d: %d ", k, ans); } } /* 1 3 6 7 1 7 5 4 8 3 9 1 4 3 5 6 2 8 9 */
eg28
dp:d(i,j)=sum(i,j)-min{rep(x,i+1,j)d(x,j);per(x,j-1,i)d(i,x);0;}.
优化：区间N*N dp 预处理成O（N）
记忆化搜索：
#include<algorithm> #include<iostream> #include<sstream> #include<stdlib.h> #include<string.h> #include<assert.h> #include<math.h> #include<stdio.h> #include<vector> #include<queue> #include<string> #include<ctime> #include<stack> #include<map> #include<set> #include<list> using namespace std; #define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++) #define REP(i,j,k) for(int i = (int)j;i < (int)k;i ++) #define per(i,j,k) for(int i = (int)j;i >= (int)k;i --) #define debug(x) cerr<<#x<<" = "<<(x)<<endl #define mmm(a,b) memset(a,b,sizeof(a)) #define pb push_back //#define x first //#define y second typedef double db; typedef long long ll; const int MAXN = 30;; const int maxn = 100+2; const int INF = 1e9; const db eps = 1e-7; int n; int S[maxn], A[maxn], d[maxn][maxn], vis[maxn][maxn]; int dp(int i, int j) { if (vis[i][j])return d[i][j]; vis[i][j] = 1; int m = 0; rep(k, i + 1, j)m = min(m, dp(k,j)); rep(k, i, j - 1)m = min(m, dp(i, k)); d[i][j] = S[j] - S[i - 1] - m; return d[i][j]; } int main() { while (cin >> n && n) { S[0] = 0; rep(i, 1, n){ cin >> A[i]; S[i] = S[i - 1] + A[i]; } mmm(vis, 0); cout << 2 * dp(1, n) - S[n] << endl;; } } /* 4 4 -10 -20 7 4 1 2 3 4 0 */
预处理：
#include<algorithm> #include<iostream> #include<sstream> #include<stdlib.h> #include<string.h> #include<assert.h> #include<math.h> #include<stdio.h> #include<vector> #include<queue> #include<string> #include<ctime> #include<stack> #include<map> #include<set> #include<list> using namespace std; #define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++) #define REP(i,j,k) for(int i = (int)j;i < (int)k;i ++) #define per(i,j,k) for(int i = (int)j;i >= (int)k;i --) #define debug(x) cerr<<#x<<" = "<<(x)<<endl #define mmm(a,b) memset(a,b,sizeof(a)) #define pb push_back //#define x first //#define y second typedef double db; typedef long long ll; const int MAXN = 30;; const int maxn = 100+2; const int INF = 1e9; const db eps = 1e-7; int n; int S[maxn], A[maxn], d[maxn][maxn], vis[maxn][maxn]; int f[maxn][maxn], g[maxn][maxn]; int dp(int i, int j) { if (vis[i][j])return d[i][j]; vis[i][j] = 1; int m = 0; rep(k, i + 1, j)m = min(m, dp(k,j)); rep(k, i, j - 1)m = min(m, dp(i, k)); d[i][j] = S[j] - S[i - 1] - m; return d[i][j]; } int main() { while (cin >> n && n) { S[0] = 0; rep(i, 1, n){ cin >> A[i]; S[i] = S[i - 1] + A[i]; } rep(i, 1, n)f[i][i] = g[i][i] = d[i][i] = A[i]; rep(len, 1, n) rep(i, 1, n - len) { int j = i + len; int m = 0; m = min(m, f[i + 1][j]); m = min(m, g[i][j - 1]); d[i][j] = S[j] - S[i - 1] - m; f[i][j] = min(d[i][j], f[i + 1][j]); g[i][j] = min(d[i][j], g[i][j - 1]); } //mmm(vis, 0); //cout << 2 * dp(1, n) - S[n] << endl;; cout << 2 * d[1][n] - S[n] << endl;; } } /* 4 4 -10 -20 7 4 1 2 3 4 0 */
eg29
存储方法：状压集合，
dp:f(S)=max{f(S-S0)|S0是S的子集，cover[S0]为全集}+1；
#include<algorithm> #include<iostream> #include<sstream> #include<stdlib.h> #include<string.h> #include<assert.h> #include<math.h> #include<stdio.h> #include<vector> #include<queue> #include<string> #include<ctime> #include<stack> #include<map> #include<set> #include<list> using namespace std; #define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++) #define REP(i,j,k) for(int i = (int)j;i < (int)k;i ++) #define per(i,j,k) for(int i = (int)j;i >= (int)k;i --) #define debug(x) cerr<<#x<<" = "<<(x)<<endl #define mmm(a,b) memset(a,b,sizeof(a)) #define pb push_back //#define x first //#define y second typedef double db; typedef long long ll; const int MAXN = 30;; const int maxn = 100+2; const int INF = 1e9; const db eps = 1e-7; int P[20]; int cover[(1<<20)]; int f[(1 << 20)]; int n; int kase = 0; int main() { while (cin >> n && n) { REP(i, 0, n) { int m, x; scanf("%d", &m); P[i] = 1 << i; while (m--) { scanf("%d", &x); P[i] |= (1 << x); } } REP(S, 0, (1 << n)) { cover[S] = 0; REP(i, 0, n) { if (S&(1 << i))cover[S] |= P[i]; } } f[0] = 0; int ALL = (1 << n) - 1; rep(S, 1, (1 << n) - 1) { f[S] = 0; for (int S0 = S; S0; S0 = (S0 - 1)&S) if (cover[S0] == ALL)f[S] = max(f[S], f[S^S0] + 1); } printf("Case %d: %d ", ++kase, f[ALL]); } } /* 3 2 1 2 2 0 2 2 0 1 4 1 1 1 0 1 3 1 2 0 */
eg30
双目标优化+树形dp
dp方程比较复杂。
#include<algorithm> #include<iostream> #include<sstream> #include<stdlib.h> #include<string.h> #include<assert.h> #include<math.h> #include<stdio.h> #include<vector> #include<queue> #include<string> #include<ctime> #include<stack> #include<map> #include<set> #include<list> using namespace std; #define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++) #define REP(i,j,k) for(int i = (int)j;i < (int)k;i ++) #define per(i,j,k) for(int i = (int)j;i >= (int)k;i --) #define debug(x) cerr<<#x<<" = "<<(x)<<endl #define mmm(a,b) memset(a,b,sizeof(a)) #define pb push_back //#define x first //#define y second typedef double db; typedef long long ll; const int MAXN = 30;; const int maxn = 100+2; const int INF = 1e9; const db eps = 1e-7; vector<int> adj[1010]; int vis[1010][2], d[1010][2], n, m; int dp(int i, int j, int f) { if (vis[i][j])return d[i][j]; vis[i][j] = 1; int & ans = d[i][j]; ans = 2000; for (int k = 0; k < adj[i].size(); k++) if (adj[i][k] != f)ans += dp(adj[i][k], 1, i); if (!j&&f >= 0)ans++; if (j || f < 0) { int sum = 0; for (int k = 0; k < adj[i].size(); k++)if (adj[i][k] != f) sum += dp(adj[i][k], 0, i); if (f >= 0)sum++; ans = min(ans, sum); } return ans; } int main() { int T, a, b; cin >> T; while (T--) { cin >> n >> m; REP(i, 0, n)adj[i].clear(); REP(i, 0, m) { cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } mmm(vis, 0); int ans = 0; REP(i, 0, n)if (!vis[i][0])ans += dp(i, 0, -1); cout << ans / 2000 << ' ' << m - ans % 2000 << ' ' << ans % 2000<<endl; } } /* 2 4 3 0 1 1 2 2 3 5 4 0 1 0 2 0 3 0 4 */
eg