Codeforces Round #351 (VK Cup 2016 Round 3, Div. 2 Edition)

A. Bear and Game

题意：一个体育节目，它可能在某一分钟是很有趣的，其他时间都是很无聊的，如果持续十五分钟都很无聊的话那么Bear就会关掉电视，问什么时候会关掉电视。

题解：用第i个有趣的时间减去第i-1个有趣的时间，如果差值大于十五分钟那就输出第i个有趣的时间+15。注意第一个有趣的时间要为0，最后一个为90。

代码：

 1 /*A*/
 2 #include<cstdio>
 3 using namespace std;
 4 
 5 const int maxn=95;
 6 
 7 int main()
 8 {
 9     int n;
10     while(scanf("%d",&n)!=EOF)
11     {
12         int a[maxn];
13         a[0]=0;
14         for(int i=1;i<=n;i++)
15             scanf("%d",&a[i]);
16         a[n+1]=90;
17         int ans=90;
18         for(int i=1;i<=n+1;i++)
19         {
20             if((a[i]-a[i-1])>15)
21             {
22                 ans=a[i-1]+15;
23                 break;
24             }
25         }
26         if(ans>90)    ans=90;
27         printf("%d
",ans);
28     }
29     return 0;
30 }

View Code

B. Problems for Round

题意：有一些题目，要分成div1和div2两个部分。同时要满足这些条件：

1.每个部分的题目数都不能为0 。

2.每个题目只用属于一个部分。

3.每个div1的题目都要比div2的题目难。

4.如果两个题目是相似的，那么他们要分别属于两个部分。

给出题目数量n，相似的题目对数。n个题目的难度系数为1~n。

题解：根据给的相似的题目，我们可判断出这两个中简单的在div2,难的在div1同时还可以知道，比简单的那个题目更简单的所有题目都会在div2,难的同理。比如：有5个题目，那么难度系数分别为1,2,3,4,5现在给出4,2,是相似的，那么2肯定在div2,4肯定在div1,因为每个div1的题目都要比div2的题目简单，所以 1肯定也是在div2 的，5肯定在div1。也就是说我们只要找到div2 中最难的题目max和div1中最简单的题目min，然后就可以确定比max简单的都在div2,比min难的都在div1。如果max>=min,说明有交叉，肯定是不行的，那么输出0。如果max<min我们可以求出d=min-max-1，就是中间还没有确定在哪个部分的题目，用隔板法可以知道有d+1种方法。不过因为每个部分都要有题目，所以当d==n的时候答案要-2。

代码：

 1 /*B*/
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 const int maxn=100000+100;
 7 
 8 int main()
 9 {
10     int n,m;
11     while(scanf("%d%d",&n,&m)!=EOF)
12     {
13         int a,b;
14         int max=0;
15         int min=n+1;
16         int flag=1;
17         for(int i=0;i<m;i++)
18         {
19             scanf("%d%d",&a,&b);
20             if(a>b)
21             {
22                 a=a+b;
23                 b=a-b;
24                 a=a-b;
25             }
26             if(a>max)
27                 max=a;
28             if(b<min)
29                 min=b;
30             if(min<=max)
31                 flag=0;
32         }
33         if(flag==0)
34             printf("0
");
35         else
36         {
37             int d=min-max-1;
38             int ans=d+1;
39             if(d==n)
40                 ans-=2;
41             printf("%d
",ans);
42         }    
43     }
44     return 0;
45  }

View Code

C. Bear and Colors

题意：有个不同颜色的球，每个颜色就是一个编号。现在定义一段（子序列）中的主色，就是一段中颜色数量最多的那个颜色，如果数量相同，那么就是编号最小的那个。现在求每个颜色在多少个段中为主色。

题解：用两个for循环，计算从i到j 这个段中的主色。用一个数组来记录每个颜色是数量，同时更新maxt(数量），和maxp(颜色），得出一段中的主色，最后更新到ans数组。

代码：

 1 /*C*/
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 const int maxn=5000+10;
 7 
 8 int main()
 9 {
10     int n;
11     while(scanf("%d",&n)!=EOF)
12     {
13         int t[maxn];
14         for(int i=0;i<n;i++)
15             scanf("%d",&t[i]);
16         int ans[maxn];
17         int a[maxn];
18         memset(ans,0,sizeof(ans));
19         int maxt=0,maxp;
20         for(int i=0;i<n;i++)
21         {
22             memset(a,0,sizeof(a));
23             maxt=0;maxp=0;
24             for(int j=i;j<n;j++)
25             {
26                 a[t[j]]++;
27                 if(a[t[j]]>maxt)
28                 {
29                     maxt=a[t[j]];
30                     maxp=t[j];
31                 }
32                 else if(a[t[j]]==maxt)
33                 {
34                     if(t[j]<maxp)
35                         maxp=t[j];
36                 }
37                 ans[maxp]++;
38             } 
39         }
40         printf("%d",ans[1]);
41         for(int i=2;i<=n;i++)
42             printf(" %d",ans[i]);
43         printf("
");
44     }
45     return 0;
46 }

View Code