Codeforces Round#297 div2

题意：给定一个字符串，然后给定m个数字

对于每个数字ai的含义是，将ai到n-ai+1的字符串给翻转一遍。

要求输出m次翻转之后的字符串。

想法就是判断第i个位置的字符是翻转了奇数次，还是偶数次就可以了，翻转了偶数次代表没翻转

自己的思想的是：将m个数字存储下来，然后排序。对于每个str[i], 1<=i<strlen(str),

使用index=upper_bound(a,a+m,i)，upper_bound(a,a+m,i)的返回值是返回数组中第一个比i大的元素迭代器，如果没有，则返回指向最后一个元素后面的迭代器

所以index-a代表在数组a中，比i小的数字有多少个。

所以如果index-a是奇数，那么代表位置i翻转了奇数次，输出str[n-i+1]

如果是偶数，代码位置i翻转了偶数次，输出str[i]

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 using namespace std;
 5 const int N = 200000 + 10;
 6 char str[N];
 7 int a[N];
 8 bool vis[N];
 9 
10 int main()
11 {
12     int m,i,x,n;
13     scanf("%s",str+1);
14     scanf("%d",&m);
15     n = strlen(str+1);
16     for(i=1; i<=m; ++i)
17         scanf("%d",&a[i]);
18     sort(a+1,a+m+1);
19     int nn = n/2,*index;
20     for(i=1; i<=nn; ++i)
21     {
22         
23         index = upper_bound(a+1,a+m+1,i);
24         if((index-a-1)%2==1)
25         {
26             printf("%c",str[n-i+1]);
27             vis[n-i+1] = true;
28         }
29         else
30             printf("%c",str[i]);
31         
32     }
33     for(i=nn+1; i<=n; ++i)
34     {
35         if(vis[i])
36             printf("%c",str[n-i+1]);
37         else
38             printf("%c",str[i]);
39     }
40     puts("");
41 }

View Code

但是看了别人的代码，只要维护一个前缀和就够了，深感自己还是太年轻

 1 #include <stdio.h>
 2 #include <string.h>
 3 char str[200000+10];
 4 int a[200000+10];
 5 int main()
 6 {
 7     int i,m,x;
 8     scanf("%s",str+1);
 9     scanf("%d",&m);
10     for(i=0; i<m; ++i)
11     {
12         scanf("%d",&x);
13         a[x]++;
14     }
15     int n = strlen(str+1);
16     m = n / 2;
17     for(i=1; i<=m; ++i)
18         a[i] += a[i-1];//前缀和
19     
20     for(i=1; i<=n; ++i)
21     {
22         if(a[i]%2==0)//小于等于下标i修改了奇数还是偶数次
23         {
24             a[n-i+1] = 0;
25             printf("%c",str[i]);
26         }
27         else
28         {
29             printf("%c",str[n-i+1]);
30             a[n-i+1] = 1;
31         }            
32     }
33     puts("");
34     return 0;
35 }

View Code

C：

给n条木棍，4条木棍构成一个矩形，问怎么构造，使得所有矩形的面积和最大，有个规则是木棒的长度能减去1，但仅限一次

矩形的长和宽当然是越大越好，所以我们将木棒从小到大排序，然后从后面开始处理

因为矩阵的长和宽都需要两条，所以我们每次选出两条木板构成成长或者宽

a[i]==a[i-1]||a[i]==a[i-1]+1 那么第i根木棒就能和第i-1根木棒构成长或者宽，然后i-=2

否则第i条木棒无用，i-=1.

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 using namespace std;
 5 typedef __int64 LL;
 6 const int N = 100000 + 10;
 7 int a[N];
 8 int main()
 9 {
10     int n,i;
11     scanf("%d",&n);
12     for(i=0; i<n; ++i)
13         scanf("%d",&a[i]);
14     sort(a,a+n);
15     LL t = 0,ans = 0;
16     for(i=n-1; i>0;)
17     {
18         if(a[i]==a[i-1] || a[i-1]==a[i]-1)
19         {
20             if(t==0)
21             {
22                 t = a[i-1];
23             }
24             else
25             {
26                 ans += t * a[i-1];
27                 t = 0;
28             }    
29             i-=2;
30         }
31         else
32             i-=1;
33     }
34     printf("%I64d
",ans);
35     return 0;
36 }

View Code