比赛链接：http://acm.hdu.edu.cn/contests/contest_show.php?cid=772

昨天嘴巴了5题，结果今天错了2个。真弱啊。。

 

1001.水

1 #include 
     
       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\n", 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 
     
       2 using namespace std; 3  4 #define x first 5 #define c second 6 typedef long long LL; 7 typedef pair
      
        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 
     
       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\n", ret);30     }31     return 0;32 }
     

 

1004.相当于问删掉一条一条边以后，仍然能构成原图一样的最小树形图，问一共可以有多少种删边情况。先跑最短路，选中某点的属于最短路上的入边，将这些入边组合起来便是最小树形图。相当于问有多少种入边权值相同但是边不同的情况。统计某点所有和最短路长度相同的边的个数作为贡献，最后将所有点的贡献乘起来就行。注意有不连通的情况。

1 #include 
     
       2 using namespace std; 3  4 typedef long long LL; 5 typedef pair
      
        pli; 6 const LL mod = (LL)1e9+7; 7 const LL inf = 1LL << 62; 8 const int maxn = 55; 9 priority_queue
       
        , greater
        
          > 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\n", ret);64     }65     return 0;66 }
        
       
      
     

 

1005.快速幂水过。

1 #include 
     
       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 
     
       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\n");23             continue;24         }25         if(!two) printf("Yes\n");26         else printf("No\n");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 
     
       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\n");67             continue;68         }69         if(n == 3) {70             printf("4\n");71             continue;72         }73         if(n == 4) {74             printf("6\n");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\n", (p.m[1][1]) % mod);86     }87     return 0;88 }