Codeforces Round #587 (Div. 3)

A. Prefixes

因为是对于每个偶数个的前缀“a“,”b“数量都相等,于是可以得出,只要从头开始每两个字母都是一个”a","b"就满足答案

所以将字符串从头遍历,每两个check一下,相等则修改,因为对修改没什么要求,我是始终修改第一个,并记录次数就行了

Codeforces Round #587 (Div. 3)
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 string a;
 5 
 6 int main()
 7 {
 8     int n;
 9     while(cin>>n)
10     {
11         cin>>a;
12         int cnt=0;
13         for(int i=0;i<n;i+=2)
14         {
15             if(a[i]+a[i+1]=='a'+'a')
16                 a[i]='b',cnt++;
17             else if(a[i]+a[i+1]=='b'+'b')
18                 a[i]='a',cnt++;
19         }
20         cout<<cnt<<endl;
21         cout<<a<<endl;
22     }
23     return 0;
24 }
View Code

B. Shooting

每个瓶子有个耐久值ai,已经击倒的瓶子数是x,对于每个瓶子,射击击倒需要的射击次数是(ai*x+1),现有一堆瓶子,求最少射击次数

由此可见对于一个ai,x越大,则最后射击次数越大,所以在x较小的时候先击倒耐久度大的瓶子,这样次数才较少,是个简单的贪心。

Codeforces Round #587 (Div. 3)
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef struct
 5 {
 6     int id;
 7     int v;
 8 }can;
 9 
10 bool cmp(can a,can b)
11 {
12     return a.v>b.v;
13 }
14 
15 can a[1005];
16 
17 int main()
18 {
19     int n;
20     while(cin>>n)
21     {
22         for(int i=1;i<=n;i++)
23         {
24             cin>>a[i].v;
25             a[i].id=i;
26         }
27         sort(a+1,a+1+n,cmp);
28         int sum=0;
29         for(int i=0;i<n;i++)
30         {
31             sum+=i*a[i+1].v+1;
32         }
33         cout<<sum<<endl;
34         for(int i=1;i<=n;i++)
35         {
36             cout<<a[i].id<<" ";
37         }
38         cout<<endl;
39     }
40     return 0;
41 }
View Code

C. White Sheet

题意很好理解,求第一个矩形(白)是否被后两个矩形(黑)所覆盖。数据大小为1e6所以不能直接二维数组。

这道题可以用简单的暴力法过,由于这些矩形的顶点都是正整数点,所以我直接对白矩形边上的点,从顶点开始按+0.5的速度沿着边遍历,对每个点check他是否再黑矩形的内部,只要有一个点不在,则没有完全覆盖(按+1的话会漏点)。

Codeforces Round #587 (Div. 3)
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 double x1,x2,x3,x4,x5,x6;
 5 double yy1,yy2,yy3,yy4,yy5,yy6;
 6 
 7 bool check1(double x,double y)
 8 {
 9     if(x>=x3&&x<=x4&&y>=yy3&&y<=yy4)
10         return 1;
11     else
12         return 0;
13 }
14 
15 bool check2(double x,double y)
16 {
17     if(x>=x5&&x<=x6&&y>=yy5&&y<=yy6)
18         return 1;
19     else
20         return 0;
21 }
22 
23 int main()
24 {
25     while(cin>>x1>>yy1>>x2>>yy2)
26     {
27         cin>>x3>>yy3>>x4>>yy4;
28         cin>>x5>>yy5>>x6>>yy6;
29         for(double i=0.0;x1+i<=x2;i+=0.5)
30         {
31             if(check1(x1+i,yy1)||check2(x1+i,yy1))
32                 continue;
33             else
34             {
35                  cout<<"YES"<<endl;
36                  return 0;
37             }
38         }
39         for(double i=0.0;yy1+i<=yy2;i+=0.5)
40         {
41             if(check1(x1,yy1+i)||check2(x1,yy1+i))
42                 continue;
43             else
44             {
45                  cout<<"YES"<<endl;
46                  return 0;
47             }
48         }
49         for(double i=0.0;yy1+i<=yy2;i+=0.5)
50         {
51             if(check1(x2,yy1+i)||check2(x2,yy1+i))
52                 continue;
53             else
54             {
55                  cout<<"YES"<<endl;
56                  return 0;
57             }
58         }
59         for(double i=0.0;x1+i<=x2;i+=0.5)
60         {
61             if(check1(x1+i,yy2)||check2(x1+i,yy2))
62                 continue;
63             else
64             {
65                  cout<<"YES"<<endl;
66                  return 0;
67             }
68         }
69             cout<<"NO"<<endl;
70     }
71     return 0;
72 }
View Code

D. Swords

有n种剑每种x把,来了y个人,每个人会挑选有且仅有一种剑,拿z把。

现在早上得到每种剑的剩余数量,求最少的可能的人数y。

(以下均为猜想没有证明过)

找到剩余数量最多的剑,假定它没被拿过,记为x;计算分别其余的剑被拿走的数量,另存一数组,求这些数的gcd,记为z;然后拿走的剑数量/z求和,即为y。

这样找到的就是最小的y(感觉是),然后就a了。(证明挖个坑先( ̄△ ̄;))

Codeforces Round #587 (Div. 3)
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 
 5 int a[200005],b[200005];
 6 
 7 int ngcd(int n)
 8 {
 9     if (n == 1)  return *b;
10     return __gcd(b[n-1], ngcd(n-1));
11 }
12 
13 int main()
14 {
15     int n;
16     while(cin>>n)
17     {
18         int maxx=-1;
19         for(int i=0;i<n;i++)
20         {
21             cin>>a[i];
22             if(a[i]>maxx)
23                 maxx=a[i];
24         }
25         int j=0;
26         for(int i=0;i<n;i++)
27         {
28             b[j]=maxx-a[i];
29             if(b[j]==0)
30                 continue;
31             else
32                 j++;
33         }
34         int z=ngcd(j);
35         ll y=0;
36         for(int i=0;i<j;i++)
37             y+=(b[i]/z);
38         cout<<y<<" "<<z<<endl;
39     }
40     return 0;
41 }
View Code

 

上一篇:剑指 Offer 25. 合并两个排序的链表


下一篇:Codeforces Round #587 White Sheet(几何覆盖)