比赛链接：http://acm.hdu.edu.cn/contests/contest_show.php?cid=772
昨天嘴巴了5题，结果今天错了2个。真弱啊。。
1001.水
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 15; 5 int n, m; 6 int vis[maxn]; 7 int solve[maxn]; 8 char st[22]; 9 10 int main() { 11 // freopen("in", "r", stdin); 12 int T; 13 scanf("%d", &T); 14 while(T--) { 15 scanf("%d%d", &n,&m); 16 int id, a, b; 17 memset(vis, 0, sizeof(vis)); 18 memset(solve, 0, sizeof(solve)); 19 for(int i = 0; i < m; i++) { 20 scanf("%d", &id); 21 id -= 1000; 22 scanf("%d:%d",&a,&b); 23 scanf("%s", st); 24 if(solve[id]) continue; 25 if(st[0] == 'A') { 26 solve[id] = 1; 27 vis[id] += a * 60 + b; 28 } 29 else vis[id] += 20; 30 } 31 int tot = 0, ret = 0; 32 for(int i = 1; i <= n; i++) { 33 if(solve[i]) { 34 tot++; 35 ret += vis[i]; 36 } 37 } 38 printf("%d %d ", tot, ret); 39 } 40 return 0; 41 }
1002. f(i,j)代表1~i个教室，并且在i上建了一共j个shop的最小花费，更新从f(i-1,j)更新来，在j!=i的时候则是i到x(j)的花费+f(i-1,j)的花费和，最后记录下最小的花费，更新在i点建shop的时候的花费。
小心给的数据可能不是坐标递增的，所以排个序。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 #define x first 5 #define c second 6 typedef long long LL; 7 typedef pair<LL, LL> pll; 8 const int maxn = 3030; 9 const LL inf = 1LL << 61; 10 int n; 11 pll p[maxn]; 12 LL f[maxn][maxn]; 13 14 int main() { 15 // freopen("in", "r", stdin); 16 while(~scanf("%d", &n)) { 17 memset(f, 0, sizeof(f)); 18 for(int i = 1; i <= n; i++) { 19 scanf("%I64d%I64d",&p[i].x,&p[i].c); 20 } 21 sort(p+1, p+n+1); 22 f[1][1] = p[1].c; 23 for(int i = 2; i <= n; i++) { 24 LL cur = f[i-1][1]; 25 for(int j = 1; j < i; j++) { 26 cur = min(cur, f[i-1][j]); 27 f[i][j] = f[i-1][j] + p[i].x - p[j].x; 28 } 29 f[i][i] = cur + p[i].c; 30 } 31 LL ret = f[n][1]; 32 for(int i = 2; i <= n; i++) { 33 ret = min(ret, f[n][i]); 34 } 35 cout << ret << endl; 36 } 37 return 0; 38 }
1003.维护前缀gcd和后缀gcd，删的时候求某点两侧gcd的gcd就行了。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 100100; 5 int n, ret; 6 int a[maxn]; 7 int f[3][maxn]; 8 int gcd(int x, int y) { 9 return y == 0 ? x : gcd(y, x%y); 10 } 11 12 int main() { 13 // freopen("in", "r", stdin); 14 int T; 15 scanf("%d", &T); 16 while(T--) { 17 scanf("%d", &n); 18 for(int i = 1; i <= n; i++) { 19 scanf("%d", &a[i]); 20 } 21 ret = 0; 22 f[0][1] = a[1]; f[1][n] = a[n]; 23 for(int i = 2; i <= n; i++) f[0][i] = gcd(f[0][i-1], a[i]); 24 for(int i = n - 1; i >= 1; i--) f[1][i] = gcd(f[1][i+1], a[i]); 25 ret = max(f[1][2], f[0][n-1]); 26 for(int i = 2; i <= n - 1; i++) { 27 ret = max(ret, gcd(f[0][i-1], f[1][i+1])); 28 } 29 printf("%d ", ret); 30 } 31 return 0; 32 }
1004.相当于问删掉一条一条边以后，仍然能构成原图一样的最小树形图，问一共可以有多少种删边情况。先跑最短路，选中某点的属于最短路上的入边，将这些入边组合起来便是最小树形图。相当于问有多少种入边权值相同但是边不同的情况。统计某点所有和最短路长度相同的边的个数作为贡献，最后将所有点的贡献乘起来就行。注意有不连通的情况。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef long long LL; 5 typedef pair<LL, int> pli; 6 const LL mod = (LL)1e9+7; 7 const LL inf = 1LL << 62; 8 const int maxn = 55; 9 priority_queue<pli, vector<pli>, greater<pli> > pq; 10 int n; 11 char G[maxn][maxn]; 12 bool vis[maxn]; 13 int to[maxn][maxn]; 14 LL d[maxn]; 15 LL mut[maxn]; 16 17 int dij(int s) { 18 for(int i = 0; i < n; i++) d[i] = inf; 19 memset(vis, 0, sizeof(vis)); 20 while(!pq.empty()) pq.pop(); 21 vis[s] = 1; d[s] = 0; 22 pq.push(pli(0, s)); 23 while(!pq.empty()) { 24 pli tmp = pq.top(); pq.pop(); 25 LL pw = tmp.first; 26 int u = tmp.second; 27 for(int v = 0; v < n; v++) { 28 if(vis[v]) continue; 29 if(G[u][v] == '0') continue; 30 if(d[v] > d[u] + G[u][v] - '0') { 31 d[v] = d[u] + G[u][v] - '0'; 32 pq.push(pli(d[v], v)); 33 } 34 } 35 } 36 for(int i = 0; i < n; i++) if(d[i] == inf) return 0; 37 return 1; 38 } 39 40 void dfs(int u) { 41 for(int v = 0; v < n; v++) { 42 if(G[u][v]-'0' && d[v] == d[u]+G[u][v]-'0') { 43 if(to[u][v]) continue; 44 to[u][v] = 1; mut[v]++; 45 dfs(v); 46 } 47 } 48 } 49 50 int main() { 51 // freopen("in", "r", stdin); 52 while(~scanf("%d", &n)) { 53 memset(mut, 0, sizeof(mut)); 54 memset(to, 0, sizeof(to)); 55 for(int i = 0; i < n; i++) { 56 scanf("%s", G[i]); 57 } 58 int ok = dij(0); 59 dfs(0); 60 LL ret = 1; 61 for(int i = 1; i < n; i++) ret = ret * mut[i] % mod; 62 if(!ok) puts("0"); 63 else printf("%I64d ", ret); 64 } 65 return 0; 66 }
1005.快速幂水过。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef long long LL; 5 const LL mod = (LL)1e9+7; 6 LL n, k; 7 8 LL mul(LL i, LL k) { 9 LL ret = 1; 10 while(k) { 11 if(k & 1) ret = (ret * i) % mod; 12 i = (i * i) % mod; 13 k >>= 1; 14 } 15 return ret; 16 } 17 18 int main() { 19 // freopen("in", "r", stdin); 20 int T; 21 scanf("%d", &T); 22 while(T--) { 23 scanf("%I64d%I64d",&n,&k); 24 LL ret = 0; 25 for(LL i = 1; i <= n; i++) { 26 ret = (ret + mul(i, k)) % mod; 27 } 28 cout << ret % mod << endl; 29 } 30 return 0; 31 }
1007.贪心，从左往右扫，遇到2则记录值+1，希望让后面的1与它匹配。假如没有2的边却出现了1的边，则暂时不计数。最后看计数结果是不是0。注意奇数点直接输出No。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 100100; 5 int n; 6 7 int main() { 8 // freopen("in", "r", stdin); 9 int T, v; 10 scanf("%d", &T); 11 while(T--) { 12 scanf("%d", &n); 13 int two = 0; 14 for(int i = 2; i <= n; i++) { 15 scanf("%d", &v); 16 if(v == 1) { 17 if(two) two--; 18 } 19 else two++; 20 } 21 if(n & 1) { 22 printf("No "); 23 continue; 24 } 25 if(!two) printf("Yes "); 26 else printf("No "); 27 } 28 return 0; 29 }
1008.打表发现递推式f(n)=f(n-1)+f(n-3)，f(2)=3，f(3)=4，f(4)=6。
构造矩阵：
1 0 1
1 0 0
0 1 0
快速水过。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef long long LL; 5 6 const LL mod = (LL)1E9+7; 7 const LL maxn = 11; 8 typedef struct Matrix { 9 LL m[maxn][maxn]; 10 LL r; 11 LL c; 12 Matrix() { 13 r = c = 0; 14 memset(m, 0, sizeof(m)); 15 } 16 } Matrix; 17 Matrix mul(Matrix m1, Matrix m2) { 18 Matrix ans = Matrix(); 19 ans.r = m1.r; ans.c = m2.c; 20 for(LL i = 1; i <= m1.r; i++) { 21 for(LL j = 1; j <= m2.r; j++) { 22 for(LL k = 1; k <= m2.c; k++) { 23 if(m2.m[j][k] == 0) continue; 24 ans.m[i][k] = ((ans.m[i][k] + (m1.m[i][j] * m2.m[j][k]) % mod) % mod) % mod; 25 } 26 } 27 } 28 return ans; 29 } 30 Matrix quickmul(Matrix m, LL n) { 31 Matrix ans = Matrix(); 32 for(LL i = 1; i <= m.r; i++) ans.m[i][i] = 1; 33 ans.r = m.r; 34 ans.c = m.c; 35 while(n) { 36 if(n & 1) ans = mul(m, ans); 37 m = mul(m, m); n >>= 1; 38 } 39 return ans; 40 } 41 42 LL n; 43 44 inline bool scan_d(LL &num) { 45 char in;bool IsN=false; 46 in=getchar(); 47 if(in==EOF) return false; 48 while(in!='-'&&(in<'0'||in>'9')) in=getchar(); 49 if(in=='-'){ IsN=true;num=0;} 50 else num=in-'0'; 51 while(in=getchar(),in>='0'&&in<='9'){ 52 num*=10,num+=in-'0'; 53 } 54 if(IsN) num=-num; 55 return true; 56 } 57 58 59 int main() { 60 // freopen("in", "r", stdin); 61 LL T; 62 scan_d(T); 63 while(T--) { 64 scan_d(n); 65 if(n == 2) { 66 printf("3 "); 67 continue; 68 } 69 if(n == 3) { 70 printf("4 "); 71 continue; 72 } 73 if(n == 4) { 74 printf("6 "); 75 continue; 76 } 77 Matrix a; a.r = a.c = 3; 78 a.m[1][1] = 1; a.m[1][2] = 0; a.m[1][3] = 1; 79 a.m[2][1] = 1; a.m[2][2] = 0; a.m[2][3] = 0; 80 a.m[3][1] = 0; a.m[3][2] = 1; a.m[3][3] = 0; 81 Matrix b = quickmul(a, n-4); 82 Matrix p; p.r = 3; p.c = 1; 83 p.m[1][1] = 6; p.m[2][1] = 4; p.m[3][1] = 3; 84 p = mul(b, p); 85 printf("%I64d ", (p.m[1][1]) % mod); 86 } 87 return 0; 88 }