Codeforces Round #354 (Div. 2)

A. Nicholas and Permutation

题意：给一个序列，移动一个数字，使得这个序列中最大的数字和最小的数字相距最远

分析：先找到最大最小的数字及其下表，将它们分别移动到第一个和最后一个，看哪种情况距离最远。

代码：

 1 /*A*/
 2 #include<cstdio>
 3 #include<cmath> 
 4 using namespace std;
 5 
 6 const int maxn=100+10;
 7 int main()
 8 {
 9     int n;
10     while(scanf("%d",&n)!=EOF)
11     {
12         int a[maxn];
13         int max=0,maxp;
14         int min=1000,minp;
15         for(int i=0;i<n;i++)
16         {
17             scanf("%d",&a[i]);
18             if(a[i]>max)
19             {
20                 max=a[i];maxp=i;
21             }
22             if(a[i]<min)
23             {
24                 min=a[i];minp=i;
25             }
26         }
27         int ans=0;
28         if(((abs)(maxp-0))>ans)
29             ans=(abs)(maxp-0);
30         if(((abs)(maxp-(n-1)))>ans)
31             ans=(abs)(maxp-(n-1));
32         if(((abs)(minp-0))>ans)
33             ans=(abs)(minp-0);
34         if(((abs)(minp-(n-1)))>ans)
35             ans=(abs)(minp-(n-1));
36         printf("%d
",ans);
37     }
38     return 0;
39 }

View Code

B. Pyramid of Glasses

题意：n层酒杯放置成金字塔形，往最上面的酒杯倒酒，没秒倒一杯。问t秒后有多少杯满了。

分析：用double来模拟整个过程。

代码：

 1 /*B*/
 2 #include<cstdio>
 3 using namespace std;
 4 
 5 int n,t;
 6 double a[15][15];
 7 
 8 void Pour()
 9 {
10     a[1][1]+=1;
11     for(int i=1;i<=n;i++)
12     {
13         for(int j=1;j<=i;j++)
14         {
15             if(a[i][j]<=1)    continue;
16             double p=a[i][j]-1;
17             a[i][j]=1;
18             a[i+1][j]+=p/2;
19             a[i+1][j+1]+=p/2;
20         }
21     }
22 }
23 int main()
24 {
25     while(scanf("%d%d",&n,&t)!=EOF)
26     {
27         for(int i=1;i<=t;i++)
28             Pour();
29         int ans=0;
30         for(int i=1;i<=n;i++)
31             for(int j=1;j<=i;j++)
32                 if(a[i][j]>=0.999)
33                     ans++;
34         printf("%d
",ans);
35     }
36     return 0;
37 }

View Code

C. Vasya and String

题意：给一个长度为n，由a,b组成的字符串，你可以改变其中k个字符（a->b,b->a）,问只由一种字符组成的字串长度最长为多少。

分析：我们可以枚举每一个字符，以这个字符作为字串的最后一个字符。然后在这个字符前二分查找，使得字串长度最长。不过在这个之前我们需要预处理一下每个字符前面a或b的个数，来作为二分的判断。

代码：

 1 /*C*/
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 const int maxn=100000+100;
 8 
 9 int main()
10 {
11     int n,k;
12     char s[maxn];
13     while(scanf("%d%d",&n,&k)!=EOF)
14     {
15         memset(s,0,sizeof(s));
16         scanf("%s",s+1);
17         int sum[maxn];
18         sum[0]=0;
19         for(int i=1;i<=n;i++)
20         {
21             sum[i]=sum[i-1];
22             if(s[i]=='a')
23                 sum[i]++;
24         }
25         int ans=0;
26         for(int i=1;i<=n;i++)
27         {
28             int l=1,r=i,res=i;
29             while(l<=r)
30             {
31                 int mid=(l+r)/2;
32                 if(sum[i]-sum[mid-1]<=k)
33                     r=mid-1,res=mid;
34                 else l=mid+1;
35             }
36             if(sum[i]-sum[res-1]<=k)
37                 ans=max(ans,i-res+1);
38         }
39         
40         sum[0]=0;
41         for(int i=1;i<=n;i++)
42         {
43             sum[i]=sum[i-1];
44             if(s[i]=='b')
45                 sum[i]++;
46         }
47         for(int i=1;i<=n;i++)
48         {
49             int l=1,r=i,res=i;
50             while(l<=r)
51             {
52                 int mid=(l+r)/2;
53                 if(sum[i]-sum[mid-1]<=k)
54                     r=mid-1,res=mid;
55                 else l=mid+1;
56             }
57             if(sum[i]-sum[res-1]<=k)
58                 ans=max(ans,i-res+1);
59         }
60         printf("%d
",ans);
61     }
62     return 0;
63 }

View Code