比赛链接：http://oj.jxust.edu.cn/contest.php?cid=1159
A.暴力
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 1010; 5 char s[maxn]; 6 int n; 7 8 int main() { 9 // freopen("in", "r", stdin); 10 int T; 11 scanf("%d", &T); 12 while(T--) { 13 memset(s, 0, sizeof(s)); 14 scanf("%s", s+1); 15 n = strlen(s+1); 16 int ret = 0; 17 for(int i = 1; i <= n; i++) { 18 if(s[i]=='j'&&s[i+1]=='x'&&s[i+2]=='u'&&s[i+3]=='s'&&s[i+4]=='t') ret++; 19 } 20 printf("%d ", ret); 21 } 22 return 0; 23 }
B.从大到小取模
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 506000; 5 int dp[maxn]; 6 int n; 7 8 int main() { 9 // freopen("in", "r", stdin); 10 int T; 11 scanf("%d", &T); 12 while(T--) { 13 scanf("%d", &n); 14 int ret = 0; 15 ret += n / 2000; 16 n %= 2000; 17 ret += n / 500; 18 n %= 500; 19 ret += n / 200; 20 n %= 200; 21 ret += n / 100; 22 n %= 100; 23 if(n != 0) puts("-1"); 24 else printf("%d ", ret); 25 } 26 return 0; 27 }
C.正着存一遍倒着存一遍求lcs，然后用总长减掉lcs。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 1010; 5 char s[maxn], e[maxn]; 6 int dp[maxn][maxn]; 7 int n; 8 9 int main() { 10 // freopen("in", "r", stdin); 11 int T; 12 scanf("%d", &T); 13 while(T--) { 14 memset(dp, 0, sizeof(dp)); 15 scanf("%s", s+1); 16 n = strlen(s+1); 17 for(int i = 1; i <= n; i++) e[i] = s[n-i+1]; 18 for(int i = 1; i <= n; i++) { 19 dp[i][0] = 0; 20 for(int j = 1; j <= n; j++) { 21 if(s[i] == e[j]) { 22 dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1); 23 } 24 dp[i][j] = max(dp[i][j], max(dp[i-1][j], dp[i][j-1])); 25 } 26 } 27 printf("%d ", n-dp[n][n]); 28 } 29 return 0; 30 }
D.展开后KMP
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 21111; 5 const int maxm = 98888888; 6 int na, nb; 7 char s[maxn]; 8 char a[maxm], b[maxn]; 9 int pre[maxn]; 10 11 void getpre(char *b, int *pre) { 12 int j, k; 13 pre[0] = -1; 14 j = 0; 15 k = -1; 16 while(j < nb) { 17 if(k == -1 || b[j] == b[k]) { 18 j++; 19 k++; 20 pre[j] = k; 21 } 22 else k = pre[k]; 23 } 24 } 25 26 int kmp() { 27 int ans = 0; 28 int i = 0; 29 int j = 0; 30 getpre(b, pre); 31 while(i < na) { 32 if(j == -1 || a[i] == b[j]) { 33 i++; 34 j++; 35 } 36 else j = pre[j]; 37 if(j == nb) ans++; 38 } 39 return ans; 40 } 41 int main() { 42 // freopen("in" ,"r", stdin); 43 while(~scanf("%s", s)) { 44 memset(a, 0, sizeof(a)); 45 na = 0; 46 scanf("%s", b); 47 nb = strlen(b); 48 int len = strlen(s); 49 int i = 0; 50 int cnt; 51 while(i < len) { 52 if(s[i] >= '0' && s[i] <= '9') { 53 cnt = 0; 54 while(s[i] >= '0' && s[i] <= '9') { 55 cnt *= 10; 56 cnt += s[i] - '0'; 57 i++; 58 } 59 } 60 else { 61 for(int j = 0; j < cnt; j++) a[na++] = s[i]; 62 i++; 63 } 64 } 65 printf("%d ", kmp()); 66 } 67 return 0; 68 }
E.二维bitset<50000>(i,j)保存的是第i行，数字为j的列号状态，查询的时候把它们与起来count一下。
1 #include <algorithm> 2 #include <iostream> 3 #include <iomanip> 4 #include <cstring> 5 #include <climits> 6 #include <complex> 7 #include <cassert> 8 #include <cstdio> 9 #include <bitset> 10 #include <vector> 11 #include <deque> 12 #include <queue> 13 #include <stack> 14 #include <ctime> 15 #include <set> 16 #include <map> 17 #include <cmath> 18 using namespace std; 19 20 typedef pair<int, int> pii; 21 const int maxm = 50500; 22 const int maxn = 22; 23 int G[maxm][maxn]; 24 int n, m, f, q; 25 char query[1111]; 26 pii pos[1111]; 27 bitset<50000> status[maxn][maxn]; 28 29 inline bool scan_d(int &num) { 30 char in; bool IsN = false; 31 in = getchar(); 32 if (in == EOF) return false; 33 while (in != '-' && (in<'0' || in>'9')) in = getchar(); 34 if (in == '-'){ IsN = true; num = 0; } 35 else num = in - '0'; 36 while (in = getchar(), in >= '0'&&in <= '9'){ 37 num *= 10, num += in - '0'; 38 } 39 if (IsN) num = -num; 40 return true; 41 } 42 43 int main() { 44 // freopen("test.in", "r", stdin); 45 // freopen("out" ,"w", stdout); 46 int T; 47 scan_d(T); 48 while (T--) { 49 scan_d(n); scan_d(m); 50 for (int i = 0; i < maxn; i++) { 51 for (int j = 0; j < maxn; j++) { 52 status[i][j] = 0; 53 } 54 } 55 for (int i = 1; i <= m; i++) { 56 for (int j = 1; j <= n; j++) { 57 scan_d(G[i][j]); 58 status[j][G[i][j]][i] = 1; 59 } 60 } 61 scan_d(f); 62 int num, tmp; 63 for (int i = 1; i <= f; i++) { 64 scan_d(num); 65 for (int j = 1; j <= num; j++) { 66 scan_d(tmp); 67 } 68 } 69 scan_d(q); 70 bitset<50000> cur; 71 while (q--) { 72 scanf("%s", query); 73 int i = 0, len = strlen(query); 74 int cnt = 0; 75 while (i < len) { 76 if (query[i] >= '0' && query[i] <= '9') { 77 pii tmp = pii(0, 0); 78 while (query[i] >= '0' && query[i] <= '9') { 79 tmp.first *= 10; 80 tmp.first += query[i] - '0'; 81 i++; 82 } 83 i++; 84 while (query[i] >= '0' && query[i] <= '9') { 85 tmp.second *= 10; 86 tmp.second += query[i] - '0'; 87 i++; 88 } 89 pos[cnt++] = tmp; 90 } 91 i++; 92 } 93 cur = status[pos[0].first][pos[0].second]; 94 for (int j = 1; j < cnt; j++) { 95 cur &= status[pos[j].first][pos[j].second]; 96 } 97 printf("%d ", cur.count()); 98 } 99 } 100 return 0; 101 }
F.判断两个矩形的距离，符合条件并查集并起来，计数。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef struct Square { 5 int x, y, w, h; 6 }Square; 7 8 const double eps = 1e-8; 9 const int maxn = 1010; 10 int n; 11 double m; 12 Square s[maxn]; 13 14 int pre[maxn]; 15 int find(int x) { 16 return x == pre[x] ? x : pre[x] = find(pre[x]); 17 } 18 void unite(int x, int y) { 19 x = find(x); y = find(y); 20 if(x != y) pre[x] = y; 21 } 22 23 double pp(int x1, int y1, int x2, int y2) { 24 int xx = x1 - x2; 25 int yy = y1 - y2; 26 return sqrt(xx*xx+yy*yy); 27 } 28 29 double dis(Square a, Square b) { 30 int x11 = a.x, x12 = a.x + a.w; 31 int y11 = a.y, y12 = a.y + a.h; 32 int x21 = b.x, x22 = b.x + b.w; 33 int y21 = b.y, y22 = b.y + b.h; 34 double ret = 1e9; 35 if((x11 >= x21 && x11 <= x22)||(x21 >= x11 && x21 <= x12)) { 36 ret = min(ret, (double)abs(y11-y21)); 37 ret = min(ret, (double)abs(y11-y22)); 38 ret = min(ret, (double)abs(y12-y21)); 39 ret = min(ret, (double)abs(y12-y22)); 40 } 41 if((y11 >= y21 && y11 <= y22)||(y21 >= y11 && y21 <= y12)) { 42 ret = min(ret, (double)abs(x11-x21)); 43 ret = min(ret, (double)abs(x11-x22)); 44 ret = min(ret, (double)abs(x12-x21)); 45 ret = min(ret, (double)abs(x12-x22)); 46 } 47 ret = min(ret, pp(x11, y11, x21, y21)); 48 ret = min(ret, pp(x11, y11, x22, y21)); 49 ret = min(ret, pp(x11, y11, x21, y22)); 50 ret = min(ret, pp(x11, y11, x22, y22)); 51 ret = min(ret, pp(x12, y11, x21, y21)); 52 ret = min(ret, pp(x12, y11, x22, y21)); 53 ret = min(ret, pp(x12, y11, x21, y22)); 54 ret = min(ret, pp(x12, y11, x22, y22)); 55 ret = min(ret, pp(x11, y12, x21, y21)); 56 ret = min(ret, pp(x11, y12, x22, y21)); 57 ret = min(ret, pp(x11, y12, x21, y22)); 58 ret = min(ret, pp(x11, y12, x22, y22)); 59 ret = min(ret, pp(x12, y12, x21, y21)); 60 ret = min(ret, pp(x12, y12, x22, y21)); 61 ret = min(ret, pp(x12, y12, x21, y22)); 62 ret = min(ret, pp(x12, y12, x22, y22)); 63 // cout << ret << endl; 64 return ret; 65 } 66 67 bool ok(int i, int j) { 68 return dis(s[i], s[j]) <= m; 69 } 70 71 int main() { 72 // freopen("in", "r", stdin); 73 while(~scanf("%d%lf",&n,&m)) { 74 for(int i = 1; i <= n; i++) { 75 scanf("%d%d%d%d",&s[i].x,&s[i].y,&s[i].w,&s[i].h); 76 } 77 for(int i = 1; i <= n; i++) pre[i] = i; 78 for(int i = 1; i <= n; i++) { 79 for(int j = i+1; j <= n; j++) { 80 if(ok(i, j)) unite(i, j); 81 } 82 } 83 int ret = 0; 84 for(int i = 1; i <= n; i++) { 85 if(i == find(i)) ret++; 86 } 87 printf("%d ", ret); 88 } 89 return 0; 90 }