比赛链接：http://acm-software.hrbust.edu.cn/contest.php?cid=1082
A.好SB啊真是，还以为lis…数有多少个数不一样。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef long long LL; 5 const int maxn = 100100; 6 int ret; 7 int n; 8 set<int> s; 9 int main() { 10 // freopen("in", "r", stdin); 11 int T; 12 scanf("%d", &T); 13 while(T--) { 14 scanf("%d", &n); 15 int x; 16 s.clear(); 17 ret = 0; 18 for(int i = 0; i < n; i++) { 19 scanf("%d", &x); 20 if(s.find(x) == s.end()) { 21 ret++; 22 s.insert(x); 23 } 24 } 25 printf("%d ", ret); 26 } 27 return 0; 28 }
B.顺着求和就行。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef long long LL; 5 const int maxn = 100100; 6 LL ret; 7 char s[maxn]; 8 9 int main() { 10 // freopen("in", "r", stdin); 11 int T; 12 scanf("%d", &T); 13 while(T--) { 14 scanf("%s", s); 15 ret = 0; 16 for(int i = 0; s[i]; i++) { 17 ret += s[i] - 'A' + 1; 18 } 19 cout << ret << endl; 20 } 21 return 0; 22 }
C.折半1000-9999，然后对称过来。注意前导零。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef long long LL; 5 6 int main() { 7 // freopen("in", "r", stdin); 8 for(LL i = 1000; i <= 9999; i++) { 9 printf("%d", i); 10 int y = 0; 11 int t = i; 12 int cnt = 4; 13 while(cnt--) { 14 printf("%d", t % 10); 15 t /= 10; 16 } 17 printf(" "); 18 } 19 return 0; 20 }
D.并查集找到所有跟1能接触的人，做01背包。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef long long LL; 5 typedef struct P { 6 int a, b, id; 7 }P; 8 9 const int maxn = 10100; 10 int n, m, c; 11 P p[maxn]; 12 int pre[maxn]; 13 int dp[maxn]; 14 int id[maxn]; 15 16 int find(int x) { 17 return pre[x] == x ? x : pre[x] = find(pre[x]); 18 } 19 20 void unite(int x, int y) { 21 x = find(x); y = find(y); 22 if(x != y) pre[x] = y; 23 } 24 25 int main() { 26 // freopen("in", "r", stdin); 27 int T, u, v; 28 scanf("%d", &T); 29 while(T--) { 30 scanf("%d%d%d",&n,&m,&c); 31 memset(dp, 0, sizeof(dp)); 32 for(int i = 1; i <= n; i++) pre[i] = i; 33 for(int i = 2; i <= n; i++) { 34 scanf("%d %d", &p[i].a, &p[i].b); 35 p[i].id = i; 36 } 37 for(int i = 0; i < m; i++) { 38 scanf("%d %d", &u, &v); 39 unite(u, v); 40 } 41 int rt = find(1); 42 for(int i = 1; i <= n; i++) { 43 if(rt != find(i)) continue; 44 for(int j = c; j >= p[i].a; j--) { 45 dp[j] = max(dp[j], dp[j-p[i].a]+p[i].b); 46 } 47 } 48 printf("%d ", dp[c]); 49 } 50 return 0; 51 }
E.防ak不会…
F.双指针扫，卡住LOVE都出现的最短，然后向后扩展数一共有多少个。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef long long LL; 5 const int maxn = 100100; 6 char s[maxn]; 7 int vis[256]; 8 int n; 9 int ret; 10 int l, o, v, e; 11 12 bool ok() { 13 return l&&o&&v&&e; 14 } 15 16 void update(int i) { 17 if(s[i]=='L')l++; 18 if(s[i]=='O')o++; 19 if(s[i]=='V')v++; 20 if(s[i]=='E')e++; 21 } 22 23 int main() { 24 // freopen("in", "r", stdin); 25 int T; 26 scanf("%d", &T); 27 while(T--) { 28 memset(s, 0, sizeof(s)); 29 scanf("%s", s+1); 30 n = strlen(s+1); 31 ret = 0; 32 int lo, hi; 33 for(lo = 1; lo <= n; lo++) { 34 // memset(vis, 0, sizeof(vis)); 35 l=o=v=e=0; 36 for(hi = lo; hi <= n; hi++) { 37 // vis[s[hi]]++; 38 update(hi); 39 if(ok()) break; 40 } 41 if(hi <= n && ok()) ret = ret + n - hi + 1; 42 } 43 printf("%d ", ret); 44 } 45 return 0; 46 }
G.BFS，实现得有点SB。。。先特判第一步人能走到哪里。然后更新，在循环里先更新火的状态，这个时候在对内同一层的所有的人的状态面对的地图都是一样的。就可以用一个队列来做了。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef pair<int, int> pii; 5 typedef struct P { 6 int x, y, s; 7 P() {} 8 P(int x, int y, int s) : x(x), y(y), s(s) {} 9 }P; 10 const int inf = 0x7f7f7f; 11 const int maxn = 33; 12 const int fdx[9] = {-1,-1,-1,0,0,1,1,1}; 13 const int fdy[9] = {-1,0,1,-1,1,-1,0,1}; 14 const int pdx[5] = {-1,0,0,1}; 15 const int pdy[5] = {0,1,-1,0}; 16 int n, m, ret; 17 int sx, sy, ex, ey, fx, fy; 18 int fcnt, pcnt; 19 bool vis[maxn][maxn]; 20 char G[maxn][maxn]; 21 queue<P> q; 22 23 bool ok(int x, int y) { 24 return x >= 0 && x < n && y >= 0 && y < m; 25 } 26 27 bool nigero(int x, int y) { 28 return x == ex && y == ey; 29 } 30 31 void bfs() { 32 while(!q.empty()) q.pop(); 33 q.push(P(fx, fy, 0)); vis[fx][fy] = 1; fcnt = 1; 34 int tmp = 0; 35 for(int i = 0; i < 4; i++) { 36 int xx = sx + pdx[i]; 37 int yy = sy + pdy[i]; 38 if(nigero(xx, yy)) { 39 ret = 1; 40 return; 41 } 42 if(ok(xx, yy) && G[xx][yy] != '*' && G[xx][yy] != '#' && !vis[xx][yy]) { 43 vis[xx][yy] = 1; 44 q.push(P(xx, yy, 1)); tmp++; 45 } 46 } 47 pcnt = tmp; tmp = 0; 48 while(!q.empty()) { 49 for(int k = 0; k < fcnt; k++) { 50 P f = q.front(); q.pop(); 51 for(int i = 0; i < 8; i++) { 52 int xx = f.x + fdx[i]; 53 int yy = f.y + fdy[i]; 54 if(ok(xx, yy) && G[xx][yy] != '*') { 55 G[xx][yy] = '*'; 56 q.push(P(xx, yy, f.s+1)); tmp++; 57 } 58 } 59 } 60 fcnt = tmp; tmp = 0; 61 for(int k = 0; k < pcnt; k++) { 62 P p = q.front(); q.pop(); 63 if(nigero(p.x, p.y)) { 64 ret = p.s; 65 return; 66 } 67 if(G[p.x][p.y] == '*') continue; 68 for(int i = 0; i < 4; i++) { 69 int xx = p.x + pdx[i]; 70 int yy = p.y + pdy[i]; 71 if(ok(xx, yy) && G[xx][yy] != '*' && G[xx][yy] != '#' && !vis[xx][yy]) { 72 vis[xx][yy] = 1; 73 q.push(P(xx, yy, p.s+1)); tmp++; 74 } 75 } 76 } 77 pcnt = tmp; tmp = 0; 78 } 79 } 80 81 int main() { 82 // freopen("in", "r", stdin); 83 int T; 84 scanf("%d", &T); 85 while(T--) { 86 scanf("%d%d",&n,&m); 87 ret = inf; 88 for(int i = 0; i < n; i++) scanf("%s", G[i]); 89 memset(vis, 0, sizeof(vis)); 90 for(int i = 0; i < n; i++) { 91 for(int j = 0; j < m; j++) { 92 if(G[i][j] == 'S') { 93 sx = i; sy = j; 94 } else if(G[i][j] == 'E') { 95 ex = i; ey = j; 96 } else if(G[i][j] == '*') { 97 fx = i; fy = j; 98 } 99 } 100 } 101 bfs(); 102 if(ret == inf) puts("T_T"); 103 else printf("%d ", ret); 104 } 105 return 0; 106 }
H.递推发现是个斐波那契，矩阵加速一下就行了。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef long long LL; 5 const LL mod = 1000000007; 6 const int maxn = 5; 7 LL n; 8 9 typedef struct Matrix { 10 LL m[maxn][maxn]; 11 int r; 12 int c; 13 Matrix(){ 14 r = c = 0; 15 memset(m, 0, sizeof(m)); 16 } 17 } Matrix; 18 19 Matrix mul(Matrix m1, Matrix m2) { 20 Matrix ans = Matrix(); 21 ans.r = m1.r; 22 ans.c = m2.c; 23 for(int i = 1; i <= m1.r; i++) { 24 for(int j = 1; j <= m2.r; j++) { 25 for(int k = 1; k <= m2.c; k++) { 26 if(m2.m[j][k] == 0) continue; 27 ans.m[i][k] = ((ans.m[i][k] + m1.m[i][j] * m2.m[j][k] % mod) % mod) % mod; 28 } 29 } 30 } 31 return ans; 32 } 33 34 Matrix quickmul(Matrix m, LL n) { 35 Matrix ans = Matrix(); 36 for(int i = 1; i <= m.r; i++) { 37 ans.m[i][i] = 1; 38 } 39 ans.r = m.r; 40 ans.c = m.c; 41 while(n) { 42 if(n & 1) { 43 ans = mul(m, ans); 44 } 45 m = mul(m, m); 46 n >>= 1; 47 } 48 return ans; 49 } 50 51 int main() { 52 // freopen("in", "r", stdin); 53 int T; 54 scanf("%d", &T); 55 while(T--) { 56 scanf("%lld", &n); 57 Matrix p, q; 58 p.r = p.c = 2; 59 p.m[1][1] = 1; p.m[1][2] = 1; 60 p.m[2][1] = 1; p.m[2][2] = 0; 61 q.r = 2; q.c = 1; 62 if(n <= 2) { 63 printf("%lld ", n); 64 continue; 65 } 66 q = quickmul(p, n-1); 67 printf("%lld ", (q.m[1][1] + q.m[1][2]) % mod); 68 } 69 return 0; 70 }
I.求n次最短路，每次求最短路的时候是以那个点为枢纽。给所有的最短路排序，然后从大到小找两个点，把两条最长的最短路加起来更新答案。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef pair<int, int> pii; 5 const int inf = 0x7f7f7f7; 6 const int maxn = 1010; 7 vector<pii> G[maxn]; 8 bool vis[maxn]; 9 queue<int> q; 10 int d[maxn]; 11 int n, m, ret; 12 13 void spfa(int s) { 14 for(int i = 1; i <= n; i++) d[i] = inf; 15 memset(vis, 0, sizeof(vis)); 16 while(!q.empty()) q.pop(); 17 d[s] = 0; q.push(s); 18 while(!q.empty()) { 19 int u = q.front(); q.pop(); 20 vis[u] = 0; 21 for(int i = 0; i < G[u].size(); i++) { 22 int& v = G[u][i].first; 23 int& w = G[u][i].second; 24 if(d[v] > d[u] + w) { 25 d[v] = d[u] + w; 26 if(vis[v]) continue; 27 vis[v] = 1; q.push(v); 28 } 29 } 30 } 31 sort(d+1, d+n+1); 32 int cnt = 0, x = 0; 33 for(int i = n; i >= 1; i--) { 34 if(cnt >= 2) break; 35 if(d[i] == 0) continue; 36 if(d[i] != inf) { 37 x += d[i]; 38 cnt++; 39 } 40 } 41 if(cnt == 2) ret = max(ret, x); 42 } 43 44 int main() { 45 // freopen("in", "r", stdin); 46 int u, v, w, T; 47 scanf("%d", &T); 48 while(T--) { 49 ret = -1; 50 scanf("%d%d",&n,&m); 51 for(int i = 1; i <= n; i++) G[i].clear(); 52 for(int i = 0; i < m; i++) { 53 scanf("%d%d%d", &u,&v,&w); 54 G[u].push_back(pii(v, w)); 55 G[v].push_back(pii(u, w)); 56 } 57 for(int i = 1; i <= n; i++) spfa(i); 58 printf("%d ", ret); 59 } 60 return 0; 61 }