寒假练习题解第二周 1.25-1.31

每日一练

1.25

题意：给 n 个数 a[i],问使得 a[i] 为 [i,n] 最大值的时候需要给 a[i] 增加多少

简析：可以倒着扫一遍，维护一个 Max[i] 表示从[i,n] 的最大值，如果 a[i] > Max[i+1] ,就是0，否则就是 Max[i+1]+1-a[i]

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const int maxn = 100000 + 10;
 8 
 9 int a[maxn], maxh[maxn];
10 
11 int main()
12 {
13     int n; scanf("%d", &n);
14     for(int i = 1; i <= n; i++) scanf("%d", a + i);
15     for(int i = n; i > 0; i--) maxh[i] = max(a[i], maxh[i+1]);
16 
17     for(int i = 1; i < n; i++) {
18         if(a[i] > maxh[i+1]) printf("0 ");
19         else printf("%d ", maxh[i+1] + 1 - a[i]);
20     }
21     printf("0\n");
22 
23     return 0;
24 }

参考代码

还可以用一个更笨的办法，每次直接用线段树查询[i,n] 的最大值

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7 
 8 #define getmid(l,r) ((l) + ((r) - (l)) / 2)
 9 
10 const int maxn = 200005;
11 int w[maxn],h[maxn],res[maxn];
12 int n;
13 int nmax;
14 
15 struct node{
16     int l,r,maxx;
17 }t[4*maxn];
18 
19 void Push_up(int p){
20     t[p].maxx = max(t[p<<1].maxx,t[p<<1|1].maxx);
21 }
22 
23 void Build_tree(int p,int l,int r){
24     t[p].l = l;
25     t[p].r = r;
26     if(l == r){
27         t[p].maxx = h[l];
28         return;
29     }
30     int mid = getmid(l,r);
31     Build_tree(p<<1,l,mid);
32     Build_tree(p<<1|1,mid+1,r);
33     Push_up(p);
34 }
35 
36 void update(int idx,int p,int w){
37     if(t[p].l == t[p].r){
38         t[p].maxx = w;
39         return;
40     }
41     int mid = getmid(t[p].l,t[p].r);
42     if(idx <= mid) update(idx,p<<1,w);
43     else update(idx,p<<1|1,w);
44     Push_up(p);    
45 }
46 
47 void Query(int p,int l,int r){
48     if(t[p].maxx <= nmax) return;
49     if(t[p].l == l && t[p].r == r){
50         nmax = max(nmax,t[p].maxx);
51         return;
52     }
53     int mid = getmid(t[p].l,t[p].r);
54     if(r <= mid) Query(p<<1,l,r);
55     else if(l > mid) Query(p<<1|1,l,r);
56     else{
57         Query(p<<1,l,mid);
58         Query(p<<1|1,mid+1,r);
59     }
60 }
61 
62 int main(){
63     while(scanf("%d",&n) != EOF){
64         memset(h,0,sizeof(h));
65         for(int i = 1;i <= n;i++) scanf("%d",&h[i]);
66         Build_tree(1,1,n);
67         
68     //    for(int i = 1;i <= 2*n;i++)
69     //    printf("t[%d].l = %d  t[%d].r = %d  t[%d].maxx = %d\n",i,t[i].l,i,t[i].r,i,t[i].maxx);
70         
71         for(int i = 1;i <= n;i++){
72             if(i == n) res[i] = 0;
73             else{
74                 nmax = -1;
75                 Query(1,i+1,n);
76                 int b = nmax;//printf("i = %d  b = %d\n",i,b);
77                // printf("i = %d  nmaxx = %d\n",i,nmax);
78                 if(b < h[i]) res[i] = 0;
79                 else res[i] = b+1-h[i];
80             }    
81         }
82         
83         for(int i = 1;i <= n;i++) printf("%d ",res[i]);
84         printf("\n");
85     }
86     return 0;
87 }

参考代码

Problem B Developing Skills

题意：给出 n 个数 a[i],k次操作，每次操作可以将a[i] 增加1，每个数的收益是floor(a[i]/10)，问最大的收益

简析：可以贪心的想，离整十更近的数需要的操作数更少，所以按照 a[i]%10排序后，扫一遍就可以了

代码挫

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7 
 8 const int maxn = 1e5+5;
 9 int n,k;
10 
11 struct node{
12     int x,y;
13 }p[maxn];
14 
15 int cmp(node n1,node n2){
16     return n1.y < n2.y;
17 }
18 
19 int cmp0(node n1,node n2){
20     return n1.x < n2.x;
21 }
22 
23 int a[105];
24 
25 void solve(){
26     for(int i = 1;i <= n;i++){
27         int pos = lower_bound(a+1,a+10,p[i].x) - a;
28         if(a[pos] == p[i].x) pos++;
29         p[i].y = a[pos] - p[i].x;
30      //  printf("a[%d] = %d  p[%d].x = %d\n",pos,a[pos],i,p[i].x);
31     }
32    /* for(int i = 1;i <= n;i++){
33         printf("p[%d].x = %d  y = %d\n",i,p[i].x,p[i].y);
34     }*/
35     sort(p+1,p+n+1,cmp);
36     int ans = 0;
37     for(int i = 1;i <= n;i++){
38         if(k >= p[i].y){
39             ans += (p[i].x + p[i].y)/10;
40             k -= p[i].y;
41             p[i].x = p[i].x + p[i].y;
42         }
43         else {
44             ans += p[i].x/10;
45         }
46        // printf("i = %d  k = %d  ans = %d\n",i,k,ans);
47     }
48     if(k){
49         for(int i = 1;i <= n;i++){
50             int l = 10 - p[i].x/10;
51             int r = k/10;
52             if(r >= l){
53                 ans += l;
54                 k = k-l*10;
55             }
56             else{
57                 ans += k/10;
58                 k = k%10;
59             }
60             if(k < 10) break;
61             //printf("l = %d  r = %d  k = %\n",l,r,k);
62         }
63     }
64     printf("%d\n",ans);
65 }
66 
67 int main(){
68     for(int i = 1;i <= 10;i++) a[i] = i*10;
69     a[11] = 100;
70   //  freopen("in.txt","r",stdin);
71    // freopen("out.txt","w",stdout);
72     while(scanf("%d %d",&n,&k) != EOF){
73         for(int i = 1;i <= n;i++){
74             scanf("%d",&p[i].x);
75         }
76         solve();
77     }
78     return 0;
79 }

参考代码

Problem C Three Logos

题意：给出 3 个矩形，问能否拼成一个正方形，如果能的话，输出正方形的边长和正方形

简析：暴力。可以先扫出最大的一条矩形边，这条边肯定作为正方形的边长，再枚举剩下的两个矩形的组合方式

代码挫

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<iostream>
  4 #include<algorithm>
  5 #include<vector>
  6 using namespace std;
  7 
  8 char g[105];
  9 char res[105][105];
 10 
 11 struct node{
 12     int x,y;
 13 }a[5];
 14 
 15 int x2,y2,x3,y3,x1,y1;
 16 int flag;
 17 
 18 void work(int x2,int y2,int x3,int y3,char c1,char c2){
 19 //    printf("x2 = %d  y2 = %d  x3 = %d  y3 = %d  c1 = %c  c2 = %c\n",x2,y2,x3,y3,c1,c2);
 20     if((y3 == y2) && (y3 + x1) == y1 && (x2 + x3) == y1){
 21         flag = 1;
 22         for(int i = 1;i <= x2;i++){
 23             for(int j = x1+1;j <= y1;j++) res[i][j] = c1;
 24         }
 25         for(int i = x2+1;i <= y1;i++){
 26             for(int j = x1+1;j <= y1;j++) res[i][j] = c2;
 27         }
 28     }
 29     
 30     if((y2 == y3) && (y2 == y1) && (x1 + x2 + x3) == y1){
 31         flag = 1;
 32         for(int i = 1;i <= y1;i++){
 33             for(int j = x1 +1;j <= x1+x2;j++) res[i][j] = c1;
 34         }
 35         for(int i = 1;i <= y1;i++){
 36             for(int j = x1+x2+1;j <= y1;j++) res[i][j] = c2;
 37         }
 38     }
 39 }
 40 
 41 void print(){
 42     printf("%d\n",y1);
 43     for(int i = 1;i <= y1;i++){
 44         for(int j = 1;j <= y1;j++) printf("%c",res[i][j]);
 45         printf("\n");
 46     }
 47     printf("\n");
 48 }
 49 
 50 void solve(){
 51     g[1] = 'A'; g[2] = 'B'; g[3] = 'C';
 52     int maxx = -1;
 53     for(int i = 1;i <= 3;i++) {
 54         maxx = max(maxx,a[i].x);
 55         maxx = max(maxx,a[i].y);
 56     }
 57 
 58     int pos = 0;
 59     for(int i = 1;i <= 3;i++){
 60         if(a[i].x == maxx || a[i].y == maxx){
 61             pos = i;
 62             break;
 63         }
 64     }
 65     if(a[pos].x > a[pos].y) swap(a[pos].x,a[pos].y);
 66     
 67     x1 = a[pos].x; y1 = a[pos].y;
 68 //    printf("x1 = %d  y1 = %d\n",x1,y1);
 69     
 70     for(int i = 1;i <= y1;i++){
 71         for(int j = 1;j <= x1;j++) res[i][j] = g[pos];
 72     }
 73 //    print();
 74     
 75     int ok = 0;
 76     char c1,c2;
 77     for(int i = 1;i <= 3;i++){
 78         if(i != pos && ok == 0) {
 79             x2 = a[i].x;
 80             y2 = a[i].y;
 81             c1 = g[i];
 82             ok = 1;
 83         } 
 84         if(i != pos && ok){
 85             x3 = a[i].x;
 86             y3 = a[i].y;
 87             c2 = g[i];
 88         }
 89     }
 90     flag = 0;
 91     work(x2,y2,x3,y3,c1,c2);
 92     if(flag) {
 93         print();
 94         return;
 95     }
 96     work(x2,y2,y3,x3,c1,c2);
 97     if(flag) {
 98         print();
 99         return;
100     }
101     work(y2,x2,x3,y3,c1,c2);
102     if(flag) {
103         print();
104         return;
105     }
106     work(y2,x2,y3,x3,c1,c2);
107     if(flag) {
108         print();
109         return;
110     }
111     puts("-1");
112 }
113 
114 int main(){
115     while(scanf("%d %d %d %d %d %d",&a[1].x,&a[1].y,&a[2].x,&a[2].y,&a[3].x,&a[3].y) != EOF){
116         solve();
117     }
118     return 0;
119 }

参考代码

一神的简洁的代码

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 int a[6][3] = { 0, 1, 2,  0, 2, 1,  1, 0, 2,  1, 2, 0,  2, 0, 1,  2, 1, 0 };
 5 int b[8][6] = {
 6     0, 1, 0, 1, 0, 1,  0, 1, 0, 1, 1, 0,  0, 1, 1, 0, 0, 1,  0, 1, 1, 0, 1, 0,
 7     1, 0, 0, 1, 0, 1,  1, 0, 0, 1, 1, 0,  1, 0, 1, 0, 0, 1,  1, 0, 1, 0, 1, 0,
 8 };
 9 char c[3] = {'A', 'B', 'C'};
10 inline void pl(int x, int y){for(int i = 0; i < x; i++) putchar(c[y]);}
11 int d[3][2];
12 
13 int main(void)
14 {
15     for(int i = 0; i < 3; i++) scanf("%d %d", &d[i][0], &d[i][1]);
16     for(int i = 0; i < 6; i++)
17     {
18         for(int j = 0; j < 8; j++)
19         {
20             int A = a[i][0], B = a[i][1], C = a[i][2];
21             int xa = d[A][b[j][0]], ya = d[A][b[j][1]];
22             int xb = d[B][b[j][2]], yb = d[B][b[j][3]];
23             int xc = d[C][b[j][4]], yc = d[C][b[j][5]];
24             if(ya == yb && xa + xb == xc && ya + yc == xc)
25             {
26                 printf("%d\n", xc);
27                 for(int p = 1; p <= ya; p++) pl(xa, A), pl(xb, B), puts("");
28                 for(int p = 1; p <= yc; p++) pl(xc, C), puts("");
29                 return 0;
30             }
31             if(ya == yb && yb == yc && xa + xb + xc == ya)
32             {
33                 printf("%d\n", ya);
34                 for(int p = 1; p <= ya; p++) pl(xa, A), pl(xb, B), pl(xc, C), puts("");
35                 return 0;
36             }
37         }
38     }
39     puts("-1");
40     return 0;
41 }

参考代码

1.26

Problem A Robot's Task

题意：一个机器人来回走采集信息，已知在i点采集信息需要已经有ai份信息，求最少转向次数。

简析：模拟这个过程，每次都走到头，直到取完为止。

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 int a[1010];
 5 
 6 int main(void)
 7 {
 8     int n;
 9     scanf("%d", &n);
10     for(int i = 1; i <= n; i++) scanf("%d", a + i);
11     int s = 0, cnt = 0, ans = 0, dir = 1, pos = 1;
12     while(cnt < n)
13     {
14         if(a[pos] >= 0 && cnt >= a[pos]) cnt++, a[pos] = -1;
15         if(s && cnt < n)
16         {
17             if(pos == n) dir = -1, ans++;
18             if(pos == 1) dir = 1, ans++;
19         }
20         s = 1, pos += dir;
21     }
22     printf("%d\n", ans);
23     return 0;
24 }

参考代码

Problem B GCD Table

题意：有一个n元数列a[]，令g(i,j) = gcd(ai, aj)得到一个n2的矩阵，让你由矩阵还原数列。

简析：考虑到矩阵主对角线上的元素都是a[]的元素，同时一个数的因子小于等于它本身，也即是说，一个数最大的因子是自己。

　　　我们可以将矩阵的元素全部丢进一个Multiset多重集（不去重的set），

　　　第一次的时候，我们先去找里面最大的元素，该元素必然是a[]的元素，记录为a[0]，再在多重集中删除它。

　　　然后我们再在多重集中找最大的元素，这个元素也一定是a[]的元素，因为比它大的数只有a[0]一个，所以它不是某两个不同数的公因子，而是某个数本身。

　　　把这个数记录为a[1]，这次不仅要删除该数，还要把该数和刚才记录的a[0]的最大公因数也删除，需要注意的是要删除两次，因为g(i,j) = g(j,i)。

　　　接着我们再次在多重集中找最大的元素，这个元素又是a[]的元素，因为a[0]与a[1]的gcd已经被删除了，其它数的gcd小于自己，不可能最大。

　　　于是我们循环这个过程，不断的找多重集的最大值，然后删除它和我们已经找出的a[]中的数的gcd，直到找到全部n个数。

　　　看到有人用了map之类的搞，其实是一样的拉，不嫌麻烦也可以学一下这个multiset姿势。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <set>
 7 using namespace std;
 8 multiset<int> S;
 9 multiset<int>::iterator it;
10 vector<int> ans;
11 
12 int gcd(int a, int b)
13 {
14     return a % b ? gcd(b, a % b) : b;
15 }
16 
17 int main(void)
18 {
19     int n, x;
20     scanf("%d", &n);
21     for(int i = 0; i < n * n; i++) scanf("%d", &x), S.insert(x);
22     while(!S.empty())
23     {
24         it = S.end(), it--;
25         int cur = (*it);
26         S.erase(it);
27         for(int i = 0; i < ans.size(); i++)
28         {
29             int t = gcd(ans[i], cur);
30             for(int i = 0; i < 2; i++) it = S.find(t), S.erase(it);
31         }
32         ans.push_back(cur);
33     }
34     for(int i = 0; i < ans.size(); i++) printf("%d ", ans[i]);
35     puts("");
36     return 0;
37 }

参考代码

1.27

Problem A Kolya and Tanya

题意：有3n 个小人坐在一个圆环上，每个小人的硬币数为 a[i],(1 <= a[i] <= 3),问满足 a[i]+a[i+n]+a[i+2n] != 6 的硬币分法有多少种

简析：如果没有不等于 6 的限制的话，总的分法一共 3^3n，为6的情况共有（123，132，213，222，231，312，321）7种

所以是 3^3n-7^n

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 typedef long long LL;
 8 const int mod = 1e9+7;
 9 int n;
10 
11 LL Q_pow(LL x,LL y){
12     LL res = 1;
13     x %= mod;
14     while(y){
15         if(y&1) res = res*x%mod;
16         x = x*x%mod;
17         y >>= 1;
18     }
19     return res;
20 }
21 
22 void solve(){
23     LL ans = (Q_pow(3,3*n) - Q_pow(7,n)+mod)%mod;
24     printf("%I64d\n",ans);
25 }
26 
27 int main(){
28     while(scanf("%d",&n) != EOF){
29         solve();
30     }
31     return 0;
32 }

参考代码

Problem B Marina and Vasya

题意：给出两个长度为 n 的字符串 s1,s2,构造一个与 s1 有t个字符不同，与 s2 有t个字符不同的字符串

简析：比较笨的办法，先算出 s1,s2 有 k 个位置不同

如果 k = t ,那么在这 k 个位置填上分别和 s1,s2不同的字母就可以了

如果 k > t,那么在这k个位置里面，分别有 k-t个和s1相同，k-t和s2相同，剩下的t 个填上和s1,s2不同的

如果 k < t,那么在这k个位置都填上与s1,s2不同的字母，剩下的t-k个再填上和s1或者s2不同的

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<iostream>
  4 #include<algorithm>
  5 #include<vector>
  6 using namespace std;
  7 
  8 
  9 typedef long long LL;
 10 const int maxn = 100005;
 11 
 12 char s[maxn],t[maxn],p[maxn];
 13 int n,T,m;
 14 
 15 int check(){
 16     int c1 = 0,c2 = 0;
 17     for(int i = 1;i <= n;i++){
 18         if(s[i] != p[i]) c1++;
 19         if(t[i] != p[i]) c2++;
 20     }
 21     if(c1 != T || c2 != T) return 0;
 22     return 1;
 23 }
 24 
 25 void solve(){
 26     m = 0;    
 27     for(int i = 1;i <= n;i++){
 28         if(s[i] != t[i]) m++;
 29     }    
 30 //    printf("m = %d\n",m);
 31     
 32     if(m <= T){
 33         int cnt = 0;
 34         for(int i = 1;i <= n;i++){
 35             int u = s[i]-'a'+1;
 36             int v = t[i]-'a'+1; 
 37             if(s[i] != t[i]){        
 38             for(int j = 1;j <= 26;j++){
 39                     if(j != u && j != v){
 40                         p[i] = j-1+'a';
 41                         break;
 42                     }
 43                 }
 44             }
 45             else if(s[i] == t[i] && (cnt < T-m) ){
 46                 for(int j = 1;j <= 26;j++){
 47                     if(j != u && j != v){
 48                         p[i] = j-1+'a';
 49                         cnt++;
 50                         break;
 51                     }
 52                 }
 53                 
 54             }
 55             else p[i] = t[i];
 56         }
 57         printf("%s\n",p+1);        
 58     }
 59     
 60     else{
 61         if(T == 0 && m != 0) puts("-1");
 62         else{
 63             int c1 = 0;
 64             int c2 = 0;
 65             int f1 = 0,f2 = 0;
 66             for(int i = 1;i <= n;i++){
 67                 if(s[i] != t[i] &&(c1 < (m-T))) {
 68                     p[i] = s[i];
 69                     c1++;
 70                 }
 71                 
 72                 if(c1 == (m-T) && f1 == 0) {
 73                     f1 = 1;
 74                     continue;
 75                 }
 76                 
 77                 if(s[i] != t[i] && f1 && (c2 < m-T)){
 78                     p[i] = t[i];
 79                     c2++;
 80                 }
 81                 
 82                 if(c2 == (m-T) && f2 == 0){
 83                     f2 = 1;
 84                     continue;
 85                 }
 86                 
 87                 if(s[i] != t[i] && (c1 == m-T) && (c2 == m-T)){
 88                     int u = s[i]-'a'+1;
 89                     int v = t[i]-'a'+1;         
 90                     for(int j = 1;j <= 26;j++){
 91                     if(j != u && j != v){
 92                         p[i] = j-1+'a';
 93                         break;
 94                     }
 95                     }
 96                 }
 97                 
 98                 if(s[i] == t[i] ) p[i] = t[i];
 99                 
100             //    printf("p[%d] = %c  c1 = %d  c2 = %d\n",i,p[i],c1,c2);
101             }    
102             if(check()) printf("%s\n",p+1);
103             else puts("-1");
104         }    
105     }
106 }
107 
108 int main(){
109     while(scanf("%d %d",&n,&T) != EOF){
110         cin >> (s+1);
111         cin >> (t+1);
112         solve();
113     }
114     return 0;
115 }

参考代码

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 const int maxn = 1e5 + 10;
 7 char a[maxn], b[maxn], c[maxn];
 8 char no(char a)        {for(char i = 'a'; i <= 'z'; i++) if(i != a) return i; }
 9 char no(char a, char b){for(char i = 'a'; i <= 'z'; i++) if(i != a && i != b) return i;}
10 
11 int main(void)
12 {
13     int n, t;
14     scanf("%d %d %s %s", &n, &t, a, b);
15     int len = strlen(a), same = 0;
16     for(int i = 0; i < len; i++) same += ( a[i] == b[i] );
17     int dif = len - same, ok = 1;
18     if( (dif + 1) / 2 > t ) ok = 0;
19     else
20     {
21         int p = max(0, t-dif), q = dif - min(t, dif), r = min(t, dif) - q;
22         for(int i = 0; i < len; i++)
23         {
24             if(a[i] == b[i])
25             {
26                 if(p) c[i] = no(a[i]), p--;
27                 else c[i] = a[i];
28             }
29             else
30             {
31                 if(r) r--, c[i] = no(a[i], b[i]);
32                 else if(q) q--, c[i] = a[i];
33                 else c[i] = b[i];
34             }
35         }
36     }
37     if(ok) for(int i = 0; i < len; i++) putchar(c[i]);
38     else printf("-1");
39     puts("");
40     return 0;
41 }

参考代码

1.28

Problem A Secret Combination

题意：给出一串长度为 n 的数字，每一次操作，可以将每个数字加 1，或者将每个数字右移一位（最右边的数字移到最左端），问得到的最小的数字

简析：可以暴力来做，因为每一个数字最多变化9次，最多只会有1000个数字，枚举每一种情况，取最小值

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7 
 8 const int maxn = 1e5+5;
 9 int n;
10 char s[maxn],t[maxn];
11 char p[10][maxn];
12 
13 void solve(){
14     vector<string> c;
15 
16     for(int i = 0;i <= 9;i++){
17         for(int j = 1;j <= n;j++){
18             p[i][j] = ((s[j]-'0')+i)%10+'0';
19         }
20     }
21 
22   /*  for(int i = 0;i <= 9;i++){
23         printf("i = %d  p = %s\n",i,p[i]+1);
24     }*/
25 
26 
27     for(int i = 0;i <= 9;i++){
28         for(int k = 0;k <= n-1;k++){
29             int cnt = 0;
30             for(int l = k+1;l <= n;l++){
31                 t[++cnt] = p[i][l];
32             }
33             for(int l = 1;l <= k;l++){
34                 t[++cnt] = p[i][l];
35             }
36           //  printf("i = %d  k = %d  t = %s\n",i,k,t+1);
37             c.push_back(t+1);
38         }
39     }
40     sort(c.begin(),c.end());
41     printf("%s\n",c[0].c_str());
42 }
43 
44 int main(){
45     while(scanf("%d",&n) != EOF){
46         scanf("%s",s+1);
47         solve();
48     }
49     return 0;
50 }

参考代码

还可以贪心的来做(司老大的博客)

寒假练习题解第二周 1.25-1.31

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 const int maxn = (1000 + 10)*3;
 7 char s[maxn], s1[maxn], s2[maxn];//输入的数字，当前最小数字，要比较的数字
 8 int n;
 9 
10 struct Queue
11 {
12     int pos, len;
13     Queue(int p=0, int l=0):pos(p), len(l) {}
14 }q[maxn]; //记录下连续相同数字的其实位置和个数
15 
16 bool lessthan(char* a, char* b)
17 {//比较数字a是否小于b
18     int i = 0;
19     while(i < n && a[i] == b[i]) i++;
20     if(i >= n) return false;
21     return a[i] < b[i];
22 }
23 
24 int main()
25 {
26     scanf("%d", &n);
27     scanf("%s", s);
28     strcpy(s1, s);
29     for(int i = 0; i < n; ++i) s[i+n] = s[i+2*n] = s[i];
30     int lx = 1, p = 0;
31     for(int i = 0; i < 2*n; i++)
32     {
33         int st = i;
34         int temp = 1;
35         while(i < 2*n-1 && s[i] == s[i+1])
36         {
37             temp++;
38             i++;
39         }
40         q[p++] = Queue(st, i+1-st);
41         if(temp > lx)
42             lx = temp;  //记录最长相同数字
43     }
44 
45     for(int i = 0; i < p; ++i)
46     {
47         if(q[i].len == lx)
48         {
49             int add = ('9' + 1 - s[q[i].pos]) % 10;//将这些相同数字加上add然后全部变为前导0
50             for(int j = 0; j < n; ++j)
51             {
52                 s2[j] = '0' + (s[q[i].pos+j]-'0'+add)%10;
53             }
54             if(lessthan(s2, s1))
55             {
56                 for(int k = 0; k < n; ++k) s1[k] = s2[k];
57             }
58         }
59     }
60 
61     for(int i = 0; i < n; ++i) printf("%c", s1[i]);
62     printf("\n");
63 
64     return 0;
65 }
66 
67 代码君

参考代码

Problem B Removing Columns

题意：给出一个 n*m 的由小写字母构成的字母表，问至少删去几列，使得字母表中从上到下，是字典序递增的（不是严格递增）

简析：如果是像这样的"a b c d e f g "这样严格上升的一列，后面不管是什么都不会再影响到字典序大小，就可以不管了

　　　如果是像"a b b b b c d e f" 这样有相同字母的一列，在"b b b b "这一段就无法判断，比较笨的一种办法是，把这种连续的相同字母的起点st，终点ed丢进一个vector里

　　　等到判断下一列的时候，就只需要再接着判断 st 到 ed 这一段

　　　如果是像 "g f e d c b a "这样字典序减小的一列，就必须删掉了

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7 
 8 typedef pair<int,int> pii;
 9 char s[105][105];
10 int n,m;
11 int lie;
12 
13 int check(int st,int ed){
14     int flag = 0;
15     for(int j = st;j <= ed;j++){
16             if(j == st) continue;
17             if(s[j][lie] < s[j-1][lie]) return 0;
18             if(s[j][lie] == s[j-1][lie]) flag = 1;
19 
20     }
21     if(flag == 1) return 2;
22     return 1;
23 }
24 
25 void solve(){
26     if(n == 1){
27         puts("0");
28         return;
29     }
30     int res = 0;
31     vector<pii> c[3];
32     lie = 1;
33     int l = 1,r = n;
34     c[0].push_back(make_pair(l,r));
35     int key = 0;
36     int tot = 0;
37     while(1){
38         int cnt = 0;
39         int lb = 0,ub = 0;
40         for(int i = 0;i < c[key].size();i++){
41             int x = c[key][i].first;
42             int y = c[key][i].second;
43           // printf("i = %d  res = %d lie = %d x = %d  y = %d\n",i,res,lie,x,y);
44             if(check(x,y) == 1) cnt++;
45             if(check(x,y) == 0){
46                 lb = 1;
47             }
48             if(check(x,y) == 2){
49                 ub = 1;
50             }
51         }
52         //printf("---cnt = %d\n",cnt);
53         if(cnt == c[key].size()) break;
54         if(lb){
55             res++;
56             c[1-key] = c[key];
57         }
58         else{
59             for(int i = 0;i < c[key].size();i++){
60                 int x = c[key][i].first;
61                 int y = c[key][i].second;
62             //   printf("i = %d  res = %d lie = %d x = %d  y = %d\n",i,res,lie,x,y);
63                 if(check(x,y) == 1) continue;
64                 if(check(x,y) == 2){
65                     for(int p = x;p <= y;){
66                         int q = p;
67                         while(q<=y && s[q][lie] == s[p][lie])q++;
68                         if(q-p > 1){
69                             c[1-key].push_back(make_pair(p,q-1));
70                         }
71                         p = q;
72                     }
73                 }
74             }
75         }
76         c[key].clear();
77         key = !key;
78         lie++;
79         if(lie == m+1) break;
80     }
81     printf("%d\n",res);
82 }
83 
84 int main(){
85     while(scanf("%d %d",&n,&m) != EOF){
86         for(int i = 1;i <= n;i++){
87             scanf("%s",s[i]+1);
88         }
89         solve();
90     }
91     return 0;
92 }

参考代码

另外可以有一种更简单的处理的办法，每判断一列的时候，严格递增的行标记成 1，之后判断到已经标记为 1 的行的时候就跳过了

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7 
 8 int n,m;
 9 char s[105][105];
10 
11 void solve(){
12     int c[105];
13     memset(c,0,sizeof(c));
14     int ans = 0;
15 
16     if(n == 1){
17         puts("0");
18         return;
19     }
20     for(int i = 1;i <= m;i++){
21         int ok = 0;
22         for(int j = 2;j <= n;j++){
23             if(c[j]) continue;
24             if(s[j][i] < s[j-1][i]){
25                 ok = 1;
26                 break;
27             }
28         }
29         if(ok){
30             ans++;
31         }
32         else{
33             for(int j=2;j <= n;j++){
34                 if(s[j][i] > s[j-1][i]){
35                     c[j] = 1;
36                 }
37             }
38         }
39     }
40     printf("%d\n",ans);
41 }
42 
43 int main(){
44     while(scanf("%d %d",&n,&m) != EOF){
45         for(int i = 1;i <= n;i++){
46             scanf("%s",s[i]+1);
47         }
48         solve();
49     }
50     return 0;
51 }

View Code

1.29

Problem A Modular Equations

题意：求模方程$a$ % $x = b$解个数。

简析：$a < b$显然无解，$a = b$时$x$可取无穷大，$infinity$。

　　　$a > b$时问题转化为求$(a - b)$大于$b$的因子个数。

　　　用$O(n^{0.5})$的复杂度枚举一下因子就可以啦。

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 
 5 int main(void)
 6 {
 7     int a, b;
 8     scanf("%d %d", &a, &b);
 9     if(a == b) puts("infinity");
10     else if(a < b) puts("0");
11     else
12     {
13         int c = a - b, ans = 0;
14         for(int i = 1; i * i <= c; i++)
15             if(c % i == 0) ans += (i > b) + (c / i > b) - (i > b && i * i == c);
16         printf("%d\n", ans);
17     }
18     return 0;
19 }

参考代码

Problem B Treasure

题意：在'#'处填任意个')'使满足：① 所有前缀'('个数大于等于')'个数 ②整个串'('个数等于')'个数。

简析：如果存在解，肯定可以构造成前面的所有'#'均填一个')'最后一个'#'将')'补至与'('相等。

　　　所以为了方便，可以先这样构造，然后check一下是否可行。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 char s[111111];
 6 
 7 int main(void)
 8 {
 9     scanf("%s", s);
10     int l = strlen(s), ok = 1, L = 0, R = 0, f = 0, last;
11     for(int i = 0; i < l; i++)
12     {
13         if(s[i] == '(') L++; else R++;
14         if(s[i] == '#') f++, last = i;
15         if(L < R) ok = 0;
16     }
17     int r = L - R;
18     for(int i = L = R = 0; i < l; i++)
19     {
20         if(s[i] == '(') L++; else R++;
21         if(i == last) R += r;
22         if(L < R) ok = 0;
23     }
24     if(!ok) puts("-1");
25     else
26     {
27         for(int i = 1; i < f; i++) puts("1");
28         printf("%d\n", r + 1);
29     }
30     return 0;
31 }

参考代码

1.30

Problem A Vasya and Wrestling

题意：给出n场比赛分别的得分，得分总数多的赢，得分总数相同的情况下，得分序列字典序大的赢，得分序列字典序相同的情况下，最后一场比赛赢的赢

简析：按照题意模拟就可以了

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7 
 8 typedef long long LL;
 9 const int maxn = 2e5+5;
10 int n;
11 int a[maxn];
12 LL lb,ub;
13 vector<int>l,r;
14 
15 void solve(){
16     if(lb > ub) {
17         puts("first");
18     }
19     else if(lb < ub){
20         puts("second");
21     }
22     else{
23         for(int i = 0;i < min(l.size(),r.size());i++){
24             if(l[i] > r[i]){
25                 puts("first");
26                 return;
27             }
28             if(r[i] > l[i]){
29                 puts("second");
30                 return;
31             }
32         }
33         if(l.size() > r.size()){
34             puts("first");
35         }
36         else if(r.size()>l.size()){
37             puts("second");
38         }
39         else{
40             if(a[n] > 0){
41                 puts("first");
42             }
43             else puts("second");
44         }
45     }
46 }
47 
48 
49 int main(){
50     while(scanf("%d",&n) != EOF){
51         lb = 0;
52         ub = 0;
53         l.clear();r.clear();
54         for(int i = 1;i <= n;i++){
55             scanf("%d",&a[i]);
56             if(a[i] > 0){
57                 lb += 1LL*a[i];
58                 l.push_back(a[i]);
59             }
60             else{
61                 ub += 1LL*(-a[i]);
62                 r.push_back(-a[i]);
63             }
64         }
65         solve();
66     }
67     return 0;
68 }

参考代码

Problem B Vasya and Basketball

题意：给出两支球队a 和 b 的投篮距离，确定三分线d（<= d得两分，>d 得三分），使得球队a 的总分 suma - sumb 尽量大（如果多解，输出 suma最大的情况）

简析：枚举所有的投篮距离作为 d 值，再二分求出 a 和 b 的得分，维护一个最大值（注意d 值可以为0，a 队，b队此时都是三分球）

 1 #include<iostream>  
 2 #include<cstdio>  
 3 #include<cstring> 
 4 #include <cmath> 
 5 #include<stack>
 6 #include<vector>
 7 #include<map> 
 8 #include<set>
 9 #include<queue> 
10 #include<algorithm>  
11 using namespace std;
12 
13 typedef long long LL;
14 const int INF = (1<<30)-1;
15 const int mod=1000000007;
16 const int maxn=1000005;
17 
18 int n,m;
19 int a[maxn],b[maxn],c[maxn];
20 
21 int main(){
22     int cnt=0;
23     c[++cnt]=0;
24     scanf("%d",&n);
25     for(int i=0;i<n;i++) scanf("%d",&a[i]),c[++cnt]=a[i];
26     scanf("%d",&m);
27     for(int i=0;i<m;i++) scanf("%d",&b[i]),c[++cnt]=b[i];
28     
29     sort(a,a+n);
30     sort(b,b+m);
31     sort(c,c+cnt);
32     int tmp=-INF,L,R;
33 
34     int lb,ub;
35     for(int i=1;i<=cnt;i++){
36         int x=upper_bound(a,a+n,c[i]) - a;
37         int y=upper_bound(b,b+m,c[i]) - b;        
38         
39         lb = x*2 + (n-x)*3;
40         ub = y*2 + (m-y)*3;
41         if(lb - ub > tmp){
42             tmp=lb-ub;
43             L=lb;R=ub;
44         }
45         if(lb - ub == tmp && lb > L) L = lb;
46         
47         }
48     printf("%d:%d\n",L,R);
49     return 0;
50 }

参考代码

1.31

Problem A Vanya and *s

题意：求最小的光照范围d，使得路灯覆盖整条路。

简析：对路灯排序后，考虑覆盖左右两端，再考虑每两路灯相邻距离的一半，取最大值即可。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 int a[1111];
 6 
 7 int main(void)
 8 {
 9     int n, l;
10     scanf("%d %d", &n, &l);
11     for(int i = 0; i < n; i++) scanf("%d", a + i);
12     sort(a, a + n);
13     double ans = max(a[0], l - a[n-1]);
14     for(int i = 1; i < n; i++) ans = max(ans, 0.5 * ( a[i] - a[i-1] ) );
15     printf("%.9lf", ans);
16     return 0;
17 }

参考代码

Problem B Vanya and Exams

题意：每门考试得分${a}_{i}$，多交${b}_{i}$份essay可以多得1分(最高r分)，要均分达到avg，最少要交几篇essay。

简析：对$b$排序，从小到大，贪心的取至avg即可。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 typedef long long LL;
 6 
 7 struct exam
 8 {
 9     LL a, b;
10 }E[111111];
11 
12 bool cmp(exam A, exam B)
13 {
14     return A.b < B.b;
15 }
16 
17 int main(void)
18 {
19     LL n, r, avg;
20     scanf("%I64d %I64d %I64d", &n, &r, &avg);
21     for(int i = 0; i < n; i++) scanf("%I64d %I64d", &E[i].a, &E[i].b);
22     sort(E, E + n, cmp);
23     LL ans = 0LL, tot = avg * n, sum = 0LL;
24     for(int i = 0; i < n; i++) sum += E[i].a;
25     for(int i = 0; i < n; i++)
26     {
27         if(sum >= tot) break;
28         LL x = min(r - E[i].a, tot - sum);
29         sum += x, ans += E[i].b * x;
30     }
31     printf("%I64d\n", ans);
32     return 0;
33 }

参考代码

regular

M题挂错。致歉。

Problem A HDU 1257 最少拦截系统

保存当前系统数和每台的最低高度，每次扫一遍已有系统，如果有比它高的，就挑其中最低的用，没有则新增一台。

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 const int INF = 233333;
 5 int H[11111];
 6 
 7 int main(void)
 8 {
 9     int N, h;
10     while(~scanf("%d", &N))
11     {
12         int cnt = 0;
13         for(int i = 0; i < N; i++)
14         {
15             int tmp = INF, pos;
16             scanf("%d", &h);
17             for(int j = 0; j < cnt; j++)
18             {
19                 if(H[j] < h) continue;
20                 if(tmp > H[j]) tmp = H[j], pos = j;
21             }
22             if(tmp == INF) H[cnt++] = h;
23             else H[pos] = h;
24         }
25         printf("%d\n", cnt);
26     }
27     return 0;
28 }

参考代码

Problem B HDU 1003 Max Sum

用dp[i]表示以i结尾的连续和最大值，如果dp[i-1]是负数，dp[i] = a[i]，否则dp[i] = dp[i-1] + a[i].

dp的同时顺便记录一下左端点即可。最后找出最大值即为答案。

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 const int maxn = 1e5 + 10;
 5 int M[maxn], l[maxn];
 6 
 7 int main(void)
 8 {
 9     int T;
10     scanf("%d", &T);
11     for(int kase = 1; kase <= T; kase++)
12     {
13         int N, x, tmp = -1111, pos;
14         scanf("%d", &N);
15         for(int i = 1; i <= N; i++)
16         {
17             scanf("%d", &x);
18             if(i == 1 || M[i-1] < 0) M[i] = x, l[i] = i;
19             else M[i] = M[i-1] + x, l[i] = l[i-1];
20             if(M[i] > tmp) tmp = M[i], pos = i;
21         }
22         if(kase != 1) puts("");
23         printf("Case %d:\n%d %d %d\n", kase, tmp, l[pos], pos);
24     }
25     return 0;
26 }

参考代码

Problem C HDU 1024 Max Sum Plus Plus

用dp[i][j]表示前j个元素取i段且包含第j个元素的最大值。

用一个辅助数组M[j]来保存dp[i-1][1]~dp[i-1][j]的最大值。

考虑到每次可以将a[j]连到前一段后面，或者中间隔开增加一段。

dp[i][j] = max( dp[i][j-1] + a[j], M[j-1] + a[j])

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 const int maxn = 1e5 + 10;
 7 typedef long long LL;
 8 LL s[maxn], dp[maxn], M[maxn];
 9 
10 int main(void)
11 {
12     int m, n;
13     while(~scanf("%d %d", &m, &n))
14     {
15         for(int i = 1; i <= n; i++) scanf("%I64d", s + i);
16         memset(dp, 0, sizeof(dp));
17         memset(M, 0, sizeof(M));
18         for(int k = 1; k <= m; k++)
19         {
20             for(int i = k; i <= n; i++)
21             {
22                 if(i == k) dp[i] = dp[i-1] + s[i];
23                 else dp[i] = max(dp[i-1] + s[i], M[i-1] + s[i]);
24             }
25             for(int i = k; i <= n; i++)
26             {
27                 if(i == k) M[i] = dp[i];
28                 else M[i] = max(M[i-1], dp[i]);
29             }
30         }
31         printf("%I64d\n", M[n]);
32     }
33     return 0;
34 }

参考代码

Problem D HDU 1176 免费馅饼

定义dp[x][T]为T时在x处最大值。

dp[x][T] = max(dp[x-1][T+1], dp[x][T+1], dp[x+1][T+1]) + a[x][T]

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 int dp[11][111111];
 7 
 8 int main(void)
 9 {
10     int n;
11     while(~scanf("%d", &n) && n)
12     {
13         memset(dp, 0, sizeof(dp));
14         for(int i = 0; i < n; i++)
15         {
16             int x, T;
17             scanf("%d %d", &x, &T);
18             dp[x][T]++;
19         }
20         for(int j = 99998; j >= 0; j--)
21         {
22             for(int i = 0; i <= 10; i++)
23             {
24                 int x = dp[i][j];
25                 dp[i][j] = dp[i][j+1] + x;
26                 if(i > 0) dp[i][j] = max(dp[i][j], dp[i-1][j+1] + x);
27                 if(i < 10) dp[i][j] = max(dp[i][j], dp[i+1][j+1] + x);
28             }
29         }
30         printf("%d\n", dp[5][0]);
31     }
32     return 0;
33 }

参考代码

Problem E HDU 1029 Ignatius and the Princess IV

这题可以用各种O(nlogn)的方法，题目没给数范围，实际不大，导致桶排也可以水过。

给一个O(n)的神奇方法。

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 
 5 int main(void)
 6 {
 7     int n;
 8     while(~scanf("%d", &n))
 9     {
10         int x, cnt = 0, tmp;
11         for(int i = 0; i < n; i++)
12         {
13             scanf("%d", &x);
14             if(!cnt) cnt++, tmp = x;
15             else if(x == tmp) cnt++;
16             else cnt--;
17         }
18         printf("%d\n", tmp);
19     }
20     return 0;
21 }

参考代码

Problem F HDU 1069 Monkey and Banana

每个block三条边分别作为高当成三个block，按底边排序后dp[i]表示第i个block为底层的最高高度。

每次遍历底边比i小的block取最高的放在上面。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 struct block
 7 {
 8     int x, y, h;
 9 }b[111];
10 
11 bool cmp (block A, block B)
12 {
13     if(A.x != B.x) return A.x < B.x;
14     return A.y < B.y;
15 }
16 
17 int main(void)
18 {
19     int n, kase = 0;
20     while(~scanf("%d", &n) && n)
21     {
22         int cnt = 0;
23         for(int i = 0; i < n; i++)
24         {
25             int x, y, z;
26             scanf("%d%d%d", &x, &y, &z);
27             b[cnt].h = x, b[cnt].x = min(y, z), b[cnt++].y = max(y, z);
28             b[cnt].h = y, b[cnt].x = min(x, z), b[cnt++].y = max(x, z);
29             b[cnt].h = z, b[cnt].x = min(x, y), b[cnt++].y = max(x, y);
30         }
31         sort(b, b + cnt, cmp);
32         int ans = 0;
33         for(int i = 0; i < cnt; i++)
34         {
35             int H = b[i].h;
36             for(int j = 0; j < i; j++)
37             {
38                 if(b[j].x == b[i].x || b[j].y >= b[i].y) continue;
39                 b[i].h = max(b[i].h, b[j].h + H);
40             }
41             ans = max(ans, b[i].h);
42         }
43         printf("Case %d: maximum height = %d\n", ++kase, ans);
44     }
45     return 0;
46 }

参考代码

Problem G HDU 1078 FatMouse and Cheese

题意略坑。老鼠只能跑直线，不能跑L形路线。记搜即可。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 int G[111][111];
 7 int n, k, dp[111][111];
 8 
 9 int DP(int i, int j)
10 {
11     if(dp[i][j]) return dp[i][j];
12     int tmp = 0;
13     for(int x = -k; x <= k; x++)
14     {
15         if(x == 0 || i + x < 0 || i + x >= n) continue;
16         if(G[i+x][j] <= G[i][j]) continue;
17         tmp = max(tmp, DP(i+x, j));
18     }
19     for(int y = -k; y <= k; y++)
20     {
21         if(y == 0 || j + y < 0 || j + y >= n) continue;
22         if(G[i][j+y] <= G[i][j]) continue;
23         tmp = max(tmp, DP(i, j+y));
24     }
25     return dp[i][j] = tmp + G[i][j];
26 }
27 
28 int main(void)
29 {
30     while(~scanf("%d %d", &n, &k) && n != -1)
31     {
32         memset(dp, 0, sizeof(dp));
33         for(int i = 0; i < n; i++)
34             for(int j = 0; j < n; j++)
35                 scanf("%d", &G[i][j]);
36         printf("%d\n", DP(0, 0));
37     }
38     return 0;
39 }

参考代码

Problem H HDU 1160 FatMouse's Speed

排序求个LIS即可。n2就好。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 struct node
 7 {
 8     int id, w, s;
 9     int pre, x;
10 }m[1111];
11 
12 bool cmp(node A, node B)
13 {
14     return A.w < B.w;
15 }
16 
17 void ans_print(int pos)
18 {
19     if(m[pos].pre != pos) ans_print(m[pos].pre);
20     printf("%d\n", m[pos].id);
21 }
22 
23 int main(void)
24 {
25     int cnt = 0, M = 0, pos;
26     while(~scanf("%d%d", &m[cnt].w, &m[cnt].s)) cnt++;
27     for(int i = 0; i < cnt; i++) m[i].id = i + 1;
28     sort(m, m + cnt, cmp);
29     for(int i = 0; i < cnt; i++)
30     {
31         m[i].x = 1, m[i].pre = i;
32         for(int j = 0; j < i; j++)
33         {
34             if(m[i].w == m[j].w || m[i].s >= m[j].s) continue;
35             if(m[j].x >= m[i].x) m[i].x = m[j].x + 1, m[i].pre = j;
36         }
37         if(m[i].x > M) M = m[i].x, pos = i;
38     }
39     printf("%d\n", m[pos].x);
40     ans_print(pos);
41     return 0;
42 }

参考代码

Problem I HDU 1087 Super Jumping! Jumping! Jumping!

dp[i]为以i结尾的最大值，n2搞即可。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 int a[1111], dp[1111];
 6 
 7 int main(void)
 8 {
 9     int n;
10     while(~scanf("%d", &n) && n)
11     {
12         for(int i = 0; i < n; i++) scanf("%d", a + i);
13         int ans = 0;
14         for(int i = 0; i < n; i++)
15         {
16             dp[i] = a[i];
17             for(int j = 0; j < i; j++)
18                 if(a[j] < a[i]) dp[i] = max(dp[i], dp[j] + a[i]);
19             ans = max(ans, dp[i]);
20         }
21         printf("%d\n", ans);
22     }
23     return 0;
24 }

参考代码

Problem J HDU 1260 Tickets

dp[i]表示前i个顾客买完票的时间，dp[i] = min(dp[i-1] + s[i], dp[i-2] + d[i])

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 int s[2222], d[2222], dp[2222];
 6 
 7 int main(void)
 8 {
 9     int N;
10     scanf("%d", &N);
11     while(N--)
12     {
13         int k;
14         scanf("%d", &k);
15         for(int i = 0; i < k; i++) scanf("%d", s + i);
16         for(int i = 1; i < k; i++) scanf("%d", d + i);
17         dp[0] = s[0], dp[1] = min(d[1], dp[0] + s[1]);
18         for(int i = 2; i < k; i++) dp[i] = min(dp[i-1] + s[i], dp[i-2] + d[i]);
19         int h = 8, m = 0, sec = dp[k-1];
20         m += sec / 60, sec %= 60;
21         h += m / 60, m %= 60;
22         printf("%02d:%02d:%02d ", h % 12, m, sec);
23         puts( h > 11 ? "pm" : "am");
24     }
25     return 0;
26 }

参考代码

Problem K HDU 1421 搬寝室

首先要知道一定是重量相邻的两件配对，否则必有更优。

所以先sort一下，然后定义dp[i][j]为前i件凑j对的最优解。

dp[i][j] = min(dp[i-1][j], dp[i-2][j-1] + (a[j] - a[j-1])^2)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 typedef long long LL;
 6 LL a[2222], dp[2222][1111];
 7 
 8 int main(void)
 9 {
10     int n, k;
11     while(~scanf("%d%d", &n, &k))
12     {
13         for(int i = 1; i <= n; i++) scanf("%d", a + i);
14         sort(a + 1, a + n + 1);
15         for(int i = 1; i <= k; i++)
16         {
17             dp[2*i][i] = dp[2*(i-1)][i-1] + (a[2*i-1] - a[2*i]) * (a[2*i-1] - a[2*i]);
18             for(int j = 2 * i + 1; j <= n; j++)
19                 dp[j][i] = min(dp[j-1][i], dp[j-2][i-1] + (a[j] - a[j-1]) * (a[j] - a[j-1]));
20         }
21         printf("%I64d\n", dp[n][k]);
22     }
23     return 0;
24 }

参考代码

Problem L HDU 2859 Phalanx

$O({n}^{3})$的做法。用l表示一个位置往上和往右延伸，字符相同的最大长度，

dp[i][j]表示以(i, j)为左下角的对称矩阵最大边长，dp[i][j] = min(dp[i-1][j+1] + 1, l)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 char G[1111][1111];
 6 int dp[1111][1111];
 7 
 8 int main(void)
 9 {
10     int n;
11     while(~scanf("%d", &n) && n)
12     {
13         for(int i = 1; i <= n; i++) scanf("%s", G[i] + 1);
14         int ans = 1;
15         for(int i = 1; i <= n; i++)
16         {
17             for(int j = 1; j <= n; j++)
18             {
19                 int l = 1;
20                 while( i - l > 0 && j + l <= n && G[i-l][j] == G[i][j+l] ) l++;
21                 dp[i][j] = min(l, dp[i-1][j+1] + 1);
22                 ans = max(ans, dp[i][j]);
23             }
24         }
25         printf("%d\n", ans);
26     }
27     return 0;
28 }

参考代码

Problem N HDU 1158 Employment Planning

题目没给人数，其实很小。

dp[i][j]表示前i个月，最后一个月雇j个人花费。考虑雇人和裁人。

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 const int INF = 2147483647;
 5 int a[13], dp[13][222];
 6 
 7 int main(void)
 8 {
 9     int n;
10     while(~scanf("%d", &n) && n)
11     {
12         int h, s, f;
13         scanf("%d%d%d", &h, &s, &f);
14         for(int i = 1; i <= n; i++) scanf("%d", a + i);
15         for(int j = a[1]; j <= 200; j++) dp[1][j] = (h + s) * j;
16         for(int i = 2; i <= n; i++)
17         {
18             for(int j = a[i]; j <= 200; j++)
19             {
20                 dp[i][j] = INF;
21                 for(int k = a[i-1]; k <= 200; k++)
22                 {
23                     if(j > k) dp[i][j] = min(dp[i][j], dp[i-1][k] + (j - k) * h + s * j);
24                     else dp[i][j] = min(dp[i][j], dp[i-1][k] + (k - j) * f + s * j);
25                 }
26             }
27         }
28         int ans = INF;
29         for(int i = a[n]; i <= 200; i++) ans = min(ans, dp[n][i]);
30         printf("%d\n", ans);
31     }
32     return 0;
33 }

参考代码

Problem O HDU 1159 Common Subsequence

经典的LCS问题。转移见代码。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 char a[1111], b[1111];
 7 int dp[1111][1111];
 8 
 9 int main(void)
10 {
11     while(~scanf("%s%s", a + 1, b + 1))
12     {
13         int n = strlen(a + 1), m = strlen(b + 1);
14         for(int i = 1; i <= n; i++)
15         {
16             for(int j = 1; j <= m; j++)
17             {
18                 dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
19                 if(a[i] == b[j]) dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1);
20             }
21         }
22         printf("%d\n", dp[n][m]);
23     }
24     return 0;
25 }

参考代码

Problem P HDU 1165 Eddy's research II

本来应该想记搜的？好像推推就出来了？

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 typedef long long LL;
 5 
 6 int main(void)
 7 {
 8     LL m, n;
 9     while(~scanf("%I64d %I64d", &m, &n))
10     {
11         if(m == 1) printf("%I64d\n", n + 2LL);
12         else if(m == 2) printf("%I64d\n", n * 2 + 3LL);
13         else printf("%I64d\n", ( 8LL << n ) - 3LL );
14     }
15     return 0;
16 }

参考代码

Problem Q HDU 1208 Pascal's Travels

记搜。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 typedef long long LL;
 6 LL dp[35][35];
 7 int n, G[35][35];
 8 
 9 LL DP(int i, int j)
10 {
11     if(i == n && j == n) return 1LL;
12     if(dp[i][j] != -1) return dp[i][j];
13     dp[i][j] = 0LL;
14     int x = G[i][j];
15     if(x == 0) return 0LL;
16     if(i + x <= n) dp[i][j] += DP(i + x, j);
17     if(j + x <= n) dp[i][j] += DP(i, j + x);
18     return dp[i][j];
19 }
20 
21 int main(void)
22 {
23     while(~scanf("%d", &n) && n != -1)
24     {
25         memset(dp, -1, sizeof(dp));
26         for(int i = 1; i <= n; i++)
27         {
28             getchar();
29             for(int j = 1; j <= n; j++)
30             {
31                 char c = getchar();
32                 G[i][j] = c - '0';
33             }
34         }
35         printf("%I64d\n", DP(1, 1));
36     }
37     return 0;
38 }

参考代码

Problem R HDU 1331 Function Run Fun

记搜。注意题意有坑，要严格按题意写函数。

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 int w[22][22][22];
 5 
 6 int W(int a, int b, int c)
 7 {
 8     if(a <= 0 || b <= 0 || c <= 0) return 1;
 9     if(a > 20 || b > 20 || c > 20) return W(20, 20, 20);
10     if(w[a][b][c]) return w[a][b][c];
11     if(a < b && b < c) return w[a][b][c] = W(a, b, c-1) + W(a, b-1, c-1) - W(a, b-1, c);
12     return w[a][b][c] = W(a-1, b, c) + W(a-1, b-1, c) + W(a-1, b, c-1) - W(a-1, b-1, c-1);
13 }
14 
15 int main(void)
16 {
17     int a, b, c;
18     while(~scanf("%d%d%d", &a, &b, &c))
19     {
20         if(a == -1 && b == -1 && c == -1) break;
21         printf("w(%d, %d, %d) = %d\n", a, b, c, W(a, b, c));
22     }
23     return 0;
24 }

参考代码

Problem S POJ 1015 Jury Compromise

dp[i][j]表示取i个双方总差值为j-400的双方总分和。

考虑每一个人，同时要检查之前有没有放过这个人。

因为要输出路径，所以每一步都要保存选的是哪个人。

输出答案的时候每个人前面要一个空格，要升序，每一组答案要空一行。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <vector>
 5 #include <algorithm>
 6 using namespace std;
 7 int dp[22][888], mark[22][888];
 8 int sum[222], dif[222];
 9 
10 bool Find(int cur, int d, int t)
11 {
12     if(cur == 0) return false;
13     return ( t == mark[cur][d] ) || Find(cur - 1, d - dif[mark[cur][d]], t);
14 }
15 
16 int main(void)
17 {
18     int n, m, kase = 0;
19     while(~scanf("%d %d", &n, &m) && n)
20     {
21         for(int i = 1; i <= n; i++)
22         {
23             int A, B;
24             scanf("%d %d", &A, &B);
25             sum[i] = A + B, dif[i] = A - B;
26         }
27         memset(dp, -1, sizeof(dp));
28         dp[0][400] = 0;
29         for(int i = 1; i <= m; i++)
30         {
31             for(int j = 0; j <= 800; j++)
32             {
33                 if(dp[i-1][j] == -1) continue;
34                 for(int k = 1; k <= n; k++)
35                 {
36                     if(Find(i-1, j, k)) continue;
37                     int x = j + dif[k];
38                     if(dp[i][x] < dp[i-1][j] + sum[k]) dp[i][x] = dp[i-1][j] + sum[k], mark[i][x] = k;
39                 }
40             }
41         }
42         int M = 9999, S = -1, p;
43         for(int i = 0; i <= 800; i++)
44         {
45             if(dp[m][i] == -1) continue;
46             int tmp = i > 400 ? i - 400 : 400 - i;
47             if(tmp < M || tmp == M && S < dp[m][i]) M = tmp, S = dp[m][i], p = i;
48         }
49         printf("Jury #%d\nBest jury has value %d for prosecution and value %d for defence:\n", ++kase, (dp[m][p] + p - 400) / 2, (dp[m][p] - p + 400) / 2);
50         vector<int> ans;
51         while(m)
52         {
53             ans.push_back(mark[m][p]);
54             p -= dif[mark[m][p]], m--;
55         }
56         sort(ans.begin(), ans.end());
57         for(int i = 0; i < ans.size(); i++) printf(" %d", ans[i]);
58         puts("\n");
59     }
60     return 0;
61 }

参考答案

Problem T POJ 1661 Help Jimmy

考虑每个台阶从最左端到达地面和从最右端到达地面所用时间。

排序后从最小面往上dp。注意直接到地面的情况。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 const int INF = 1e9;
 6 
 7 struct plat
 8 {
 9     int l, r, h;
10     int tl, tr;
11 }p[1111];
12 
13 bool cmp(plat A, plat B)
14 {
15     return A.h < B.h;
16 }
17 
18 int main(void)
19 {
20     int T;
21     scanf("%d", &T);
22     while(T--)
23     {
24         int n, X, Y, M;
25         scanf("%d %d %d %d", &n, &X, &Y, &M);
26         for(int i = 0; i < n; i++) scanf("%d %d %d", &p[i].l, &p[i].r, &p[i].h);
27         sort(p, p + n, cmp);
28         for(int i = 0; i < n; i++)
29         {
30             p[i].tl = p[i].tr = INF;
31             int pl = -1, pr = -1;
32             for(int j = i - 1; j >= 0; j--)
33             {
34                 if(pl == -1 && p[j].l <= p[i].l && p[j].r >= p[i].l && p[j].h + M >= p[i].h) pl = j;
35                 if(pr == -1 && p[j].l <= p[i].r && p[j].r >= p[i].r && p[j].h + M >= p[i].h) pr = j;
36             }
37             if(pl != -1) p[i].tl = p[i].h - p[pl].h + min(p[pl].tl + p[i].l - p[pl].l, p[pl].tr + p[pl].r - p[i].l);
38             else if(p[i].h <= M) p[i].tl = p[i].h;
39             if(pr != -1) p[i].tr = p[i].h - p[pr].h + min(p[pr].tl + p[i].r - p[pr].l, p[pr].tr + p[pr].r - p[i].r);
40             else if(p[i].h <= M) p[i].tr = p[i].h;
41         }
42         int ans = Y;
43         for(int i = n - 1; i >= 0; i--) if(p[i].h <= Y && p[i].l <= X && p[i].r >= X)
44             {ans = Y - p[i].h + min(p[i].tl + X - p[i].l, p[i].tr + p[i].r - X); break;}
45         printf("%d\n", ans);
46     }
47     return 0;
48 }

参考代码

Problem U POJ 2533 Longest Ordered Subsequence

经典LIS。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 int a[1111], dp[1111];
 6 
 7 int main(void)
 8 {
 9     int n, ans = 0;
10     scanf("%d", &n);
11     for(int i = 0; i < n; i++) scanf("%d", a + i);
12     for(int i = 0; i < n; i++)
13     {
14         dp[i] = 1;
15         for(int j = 0; j < i; j++)
16             if(a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1);
17         ans = max(ans, dp[i]);
18     }
19     printf("%d\n", ans);
20     return 0;
21 }

参考代码

Problem V POJ 3186 Treats for the Cows

dp[i][j]表示左边取i个右边取j个的最大值。

dp[i][j] = max(dp[i-1][j] + (i + j) * v[i], dp[i][j-1] + (i + j) * v[N+1-j])

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 int v[2222], dp[2222][2222];
 6 
 7 int main(void)
 8 {
 9     int N, ans = 0;
10     scanf("%d", &N);
11     for(int i = 1; i <= N; i++) scanf("%d", v + i);
12     for(int i = 1; i <= N; i++)
13     {
14         for(int j = 0; j <= i; j++)
15         {
16             if(i != j) dp[j][i-j] = max(dp[j][i-j], dp[j][i-j-1] + i * v[N+1-i+j]);
17             if(j) dp[j][i-j] = max(dp[j][i-j], dp[j-1][i-j] + i * v[j]);
18             ans = max(ans, dp[j][i-j]);
19         }
20     }
21     printf("%d\n", ans);
22     return 0;
23 }

参考代码

Problem W POJ 3616 Milking Time

dp[i]表示前i小时最大值。先按照右端点排序。

对于长度为l的，收益为e的区间，如果右端点是i。

dp[i] = max(dp[i-1], dp[i - R - l] + e)

注意区间是可以重叠的。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 const int maxn = 1e6 + 10;
 6 typedef long long LL;
 7 LL dp[maxn];
 8 
 9 struct node
10 {
11     int l, r;
12     LL e;
13 }I[1111];
14 
15 bool cmp (node A, node B)
16 {
17     if(A.r != B.r) return A.r < B.r;
18 }
19 
20 int main(void)
21 {
22     int N, M, R;
23     scanf("%d %d %d", &N, &M, &R);
24     for(int i = 0; i < M; i++) scanf("%d %d %I64d", &I[i].l, &I[i].r, &I[i].e);
25     sort(I, I + M, cmp);
26     int pos = 0;
27     LL ans = 0LL;
28     for(int i = 1; i <= N; i++)
29     {
30         if(pos == M) break;
31         dp[i] = max(dp[i-1], dp[i]);
32         while(i == I[pos].r)
33         {
34             int st = max(0, I[pos].l - R);
35             dp[i] = max(dp[i], dp[st] + I[pos].e);
36             pos++;
37         }
38         ans = max(ans, dp[i]);
39     }
40     printf("%I64d\n", ans);
41     return 0;
42 }

参考代码

Problem X POJ 3666 Making the Grade

首先要知道无论要递增还是递减，如果要修改某个值，必然是改成它左边或者右边的相邻值才最优。

虽然数值的范围很大，但是只有2000个，我们可以先按将它排序存入b[]。

只考虑递增的，定义dp[i][j]为将前i个数改成递增，且最后一个数为b[j]的最优解。

dp[i][j] = min(dp[i-1][k]) + abs(a[i] - b[j]) ， k < j

我们可以在dp的过程中维护min的值，总的复杂度就是n2。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 typedef long long LL;
 6 LL a[2005], b[2005];
 7 LL dp[2][2005][2005];
 8 LL ABS(LL a){return a > 0LL ? a : -a;}
 9 
10 int main(void)
11 {
12     int N;
13     scanf("%d", &N);
14     for(int i = 0; i < N; i++) scanf("%I64d", a + i), b[i] = a[i];
15     sort(b, b + N);
16     for(int i = 1; i <= N; i++)
17     {
18         LL tmp = dp[0][i-1][0];
19         for(int j = 0; j < N; j++)
20         {
21             tmp = min(tmp, dp[0][i-1][j]);
22             dp[0][i][j] = tmp + ABS(a[i-1] - b[j]);
23         }
24         tmp = dp[1][i-1][N-1];
25         for(int j = N - 1; j >= 0; j--)
26         {
27             tmp = min(tmp, dp[1][i-1][j]);
28             dp[1][i][j] = tmp + ABS(a[i-1] - b[j]);
29         }
30     }
31     LL ans = dp[0][N][0];
32     for(int i = 0; i < N; i++) ans = min(ans, min(dp[0][N][i], dp[1][N][i]));
33     printf("%I64d\n", ans);
34     return 0;
35 }

参考代码

Problem Y POJ 1036 Gangsters

dp[i][j]i时刻state为j的最优解。

dp[i][j] = max(dp[i+1][j-1], dp[i+1][j], dp[i+1][j+1]) + sum{P( T == i && S == j )}

因为题目卡了内存。所以必须要滚动数组了。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 int dp[105], cpy[105];
 7 
 8 struct G
 9 {
10     int T, P, S;
11 }g[111];
12 
13 bool cmp(G A, G B)
14 {
15     if(A.T != B.T) return A.T > B.T;
16     return A.S < B.S;
17 }
18 
19 int main(void)
20 {
21     int N, K, T;
22     scanf("%d %d %d", &N, &K, &T);
23     for(int i = 0; i < N; i++) scanf("%d", &g[i].T);
24     for(int i = 0; i < N; i++) scanf("%d", &g[i].P);
25     for(int i = 0; i < N; i++) scanf("%d", &g[i].S);
26     sort(g, g + N, cmp);
27     int pos = 0;
28     for(int i = 30000; i > 0; i--)
29     {
30         memcpy(cpy, dp, sizeof(cpy));
31         for(int j = 1; j <= 100; j++)
32         {
33             dp[j] = max(cpy[j], max(cpy[j-1], cpy[j+1]));
34             while(pos < N && g[pos].T == i && g[pos].S == j)
35                 dp[j] += g[pos].P, pos++;
36         }
37     }
38     printf("%d\n", dp[1]);
39 }

参考代码

Problem Z POJ 1088 滑雪

好像是OI的dp经典题。记搜会比较好写。

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 int dir[][2] = {0, 1, 1, 0, 0, -1, -1, 0};
 5 int R, C, h[111][111], dp[111][111];
 6 
 7 bool out(int x, int y)
 8 {
 9     return x < 1 || x > R || y < 1 || y > C;
10 }
11 
12 int DP(int x, int y)
13 {
14     if(dp[x][y]) return dp[x][y];
15     dp[x][y] = 1;
16     for(int d = 0; d < 4; d++)
17     {
18         int xx = x + dir[d][0], yy = y + dir[d][1];
19         if(out(xx, yy) || h[x][y] <= h[xx][yy] ) continue;
20         dp[x][y] = max(dp[x][y], DP(xx, yy) + 1);
21     }
22     return dp[x][y];
23 }
24 
25 int main(void)
26 {
27     scanf("%d %d", &R, &C);
28     for(int i = 1; i <= R; i++)
29         for(int j = 1; j <= C; j++)
30             scanf("%d", &h[i][j]);
31     int ans = 0;
32     for(int i = 1; i <= R; i++)
33         for(int j = 1; j <= C; j++)
34             ans = max(ans, DP(i, j));
35     printf("%d\n", ans);
36     return 0;
37 }

参考代码

bonus

Problem A POJ 3320 Jessica's Reading Problem

用p1,p2维护读的书所在的区间。

每次p1向右移动一页，然后p2向右移动直至p1，p2之间有所有的知识点，更新答案。

知识点的范围是int，数组存不下，但是其个数最多只有1e6个，所以可以用map做一个映射，当然其他方法也可以。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <map>
 4 using namespace std;
 5 const int maxn = 1e6 + 10;
 6 map<int, int> M;
 7 int p[maxn];
 8 
 9 int main(void)
10 {
11     int P;
12     scanf("%d", &P);
13     for(int i = 1; i <= P; i++) scanf("%d", p + i), M[p[i]] = 0;
14     int p2 = 0, cnt = 0, ans = P, sz = M.size();
15     for(int p1 = 1; p1 <= P; p1++)
16     {
17         while(p2 < P && cnt < sz)
18         {
19             M[p[++p2]]++;
20             if(M[p[p2]] == 1) cnt++;
21         }
22         if(cnt < sz) break;
23         ans = min(ans, p2 - p1 + 1);
24         M[p[p1]]--;
25         if(M[p[p1]] == 0) cnt--;
26     }
27     printf("%d\n", ans);
28     return 0;
29 }

参考代码

Problem B POJ 2566 Bound Found

先将前缀和排序(注意有n+1个前缀和)，然后维护双指针。

如果前缀和之差(表示某个连续区间和的绝对值)小于t，则移右指针，反之移左。

最后答案输出区间的时候注意端点顺序，因为前缀和端点是无序的。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 typedef long long LL;
 6 const int maxn = 1e5 + 10;
 7 
 8 LL ABS(LL x)
 9 {
10     return x > 0 ? x : -x;
11 }
12 
13 struct range
14 {
15     int id;
16     LL sum;
17 }r[maxn];
18 
19 bool cmp(range A, range B)
20 {
21     return A.sum < B.sum;
22 }
23 
24 int main(void)
25 {
26     int n, k;
27     while(~scanf("%d %d", &n, &k) && n)
28     {
29         for(int i = 1; i <= n; i++) scanf("%I64d", &r[i].sum);
30         r[0].sum = 0LL, r[0].id = 0;
31         for(int i = 1; i <= n; i++) r[i].sum += r[i-1].sum, r[i].id = i;
32         sort(r, r + 1 + n, cmp);
33         while(k--)
34         {
35             int P1, P2, p1 = 0, p2 = 0;
36             LL t, M = 1e18;
37             scanf("%I64d", &t);
38             while(p1 < n)
39             {
40                 if(p2 == n) p1++;
41                 else if(p1 == p2) p2++;
42                 else if(r[p2].sum - r[p1].sum < t) p2++;
43                 else p1++;
44                 if(p1 != p2 && ABS(r[p2].sum - r[p1].sum - t) < ABS(M - t))
45                     M = r[p2].sum - r[p1].sum, P1 = p1, P2 = p2;
46             }
47             printf("%I64d %d %d\n", M, min(r[P1].id, r[P2].id) + 1, max(r[P1].id, r[P2].id));
48         }
49     }
50     return 0;
51 }

参考代码

Problem C POJ 2100 Graveyard Design

双指针从1扫到${n}^{0.5}$维护一个区间平方和。

答案放到vector里比较方便。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <vector>
 4 using namespace std;
 5 typedef long long LL;
 6 typedef pair<int, int> pii;
 7 vector<pii> ans;
 8 
 9 int main(void)
10 {
11     LL n;
12     scanf("%I64d", &n);
13     LL p2 = 0, sum = 0;
14     for(LL p1 = 1; p1 * p1 <= n; sum -= p1 * p1, p1++)
15     {
16         while(p2 < p1 || sum < n) p2++, sum += p2 * p2;
17         if(sum == n) ans.push_back(pii(p1, p2));
18     }
19     printf("%d\n", ans.size());
20     for(int i = 0; i < ans.size(); i++)
21     {
22         int s = ans[i].first, e = ans[i].second;
23         printf("%d ", e - s + 1);
24         for(int j = s; j <= e; j++) printf("%d ", j);
25         puts("");
26     }
27     return 0;
28 }

参考代码

Problem D POJ 2739 Sum of Consecutive Prime Numbers

先打出素数，再用双指针处理出每个数的答案。

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 int p[2222], ans[11111];
 5 
 6 int main(void)
 7 {
 8     for(int i = 2; i <= 11111; i++)
 9     {
10         int ok = 1;
11         for(int j = 2; j * j <= i; j++)
12             if(i % j == 0) ok = 0;
13         if(ok) p[++p[0]] = i;
14     }
15     for(int i = 2; i <= 10000; i++)
16     {
17         int p2 = 0, sum = 0;
18         for(int p1 = 1; p[p1] <= i; sum -= p[p1], p1++)
19         {
20             while(p2 < p1 || sum < i) p2++, sum += p[p2];
21             if(sum == i) ans[i]++;
22         }
23     }
24     int n;
25     while(~scanf("%d", &n) && n) printf("%d\n", ans[n]);
26     return 0;
27 }

参考代码

Problem E POJ 3061 Subsequence

双指针维护一下区间和，找到可行解更新答案，注意无解情况。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 int a[111111];
 6 
 7 int main(void)
 8 {
 9     int T;
10     scanf("%d", &T);
11     while(T--)
12     {
13         int N, S;
14         scanf("%d%d", &N, &S);
15         for(int i = 1; i <= N; i++) scanf("%d", a + i);
16         int p2 = 0, sum = 0, ans = N + 1;
17         for(int p1 = 1; p1 <= N; sum -= a[p1], p1++)
18         {
19             while( p2 < N && (p2 < p1 || sum < S) ) p2++, sum += a[p2];
20             if(sum >= S) ans = min(ans, p2 - p1 + 1);
21         }
22         printf("%d\n", ans == N + 1 ? 0 : ans);
23     }
24     return 0;
25 }

参考代码

Problem F CodeForces 616D Longest k-Good Segment

前面都做了这题就不难了。希望做题的时候都能想到尺取法。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 const int maxn = 1e6 + 10;
 6 int num[maxn], cnt[maxn];
 7 
 8 int main(void)
 9 {
10     int n, k;
11     scanf("%d%d", &n, &k);
12     for(int i = 1; i <= n; i++) scanf("%d", num + i);
13     int len = 1, p2 = 1, tmp = 1, L = 1, R = 1;
14     cnt[num[1]] = 1;
15     for(int p1 = 1; p1 <= n; p1++)
16     {
17         while(p2 < n)
18         {
19             if(!cnt[num[p2+1]] && tmp == k) break;
20             if(!cnt[num[p2+1]]) tmp++;
21             cnt[num[++p2]]++;
22         }
23         if(p2 - p1 + 1 > len)
24         {
25             len = p2 - p1 + 1;
26             L = p1, R = p2;
27         }
28         cnt[num[p1]]--;
29         if(!cnt[num[p1]]) tmp--;
30     }
31     printf("%d %d\n", L, R);
32     return 0;
33 }

参考代码

秒客网

寒假练习题解第二周 1.25-1.31

相关文章

寒假练习题解 第二周 1.25-1.31

相关文章

寒假练习题解第二周 1.25-1.31