2023.08.12 codeforces round 893 div2

年轻人的第四场div2

rank:8217

solved:2

rating change:+31

new rating:1354

A.Buttons

题意：给定a,b,c三种按钮的数量，a按钮只能被Anna按，b按钮只能被Katie按，两个人都可以按c按钮，最后没有按钮可以按的人输，Anna先手，问谁是赢家；

两个人肯定优先按c按钮，且Anna是先手，只需比较两人能按的按钮数量即可；

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 ll read(){
 5     char ch=getchar();ll x=0,f=1;
 6     while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
 7     while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
 8     return x*f;
 9 }
10 ll T;
11 ll a,b,c;
12 int main(){
13     T=read();
14     while(T--){
15         a=read();b=read();c=read();
16         if(c%2==0){
17             a+=c/2;b+=c/2;
18         }
19         if(c%2==1){
20             a+=c/2;a++;
21             b+=c/2;
22         }
23         if(a>b){
24             cout<<"First"<<endl;
25             continue;
26         }
27         cout<<"Second"<<endl;
28     }
29     return 0;
30 }

B.The Walkway

题意：有编号为 1 ~ N 的 N 个长椅，一共 M 个 seller ，第 i 个位于 S[i] ，当满足以下三种条件之一时 Petya 会吃一块饼干：

1.当前位置有 seller ；2.在编号为1的长椅处；3. D 小时没有吃饼干了；

现在我们要移走一个 seller 使得 Petya 吃的饼干数目最少，输出最少数目以及让 Petya 吃到最少饼干的方案数；

枚举每个 seller ，计算删除该 seller 之后吃到的饼干数即可；为了方便计算，我们不妨增加两个虚拟的 seller ：S [ 0 ] = - D + 1，S [ M + 1 ] = N + 1 （赛时想到了增加两个 seller 但是写的 S [ 0 ] = 1 ，S [ M + 1 ] = N 加上在第一次遍历seller的时候就把在seller处吃的饼干加上了，然后一直没调出来，寒心）；

计算两个 seller 之间吃饼干的个数放在 work 函数，由于当前位置有 seller 时会吃一次，在编号为1的长椅要吃一次，S [ 0 ] = - D +  1可以保证不论是否有 S [ 1 ] = 1 都不重复；

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 ll read(){
 5     char ch=getchar();ll x=0,f=1;
 6     while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
 7     while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
 8     return x*f;
 9 }
10 const int maxm=1e9+7;
11 const int maxn=1e5+5;
12 ll T,N,M,D,now,ans,sum,cnt;
13 ll S[maxn];
14 ll work(ll x,ll y){
15     return (y-x-1)/D;
16 }
17 int main(){
18     T=read();
19     while(T--){
20         N=read();M=read();D=read();
21         for(int i=1;i<=M;i++){
22             S[i]=read();
23         }
24         S[0]=-D+1;S[M+1]=N+1;
25         sum=0;
26         for(int i=0;i<=M;i++){
27             sum+=work(S[i],S[i+1]);
28         } 
29         ans=maxm;cnt=0;
30         for(int i=1;i<=M;i++){
31             now=sum;
32             now-=work(S[i-1],S[i]);now-=work(S[i],S[i+1]);
33             now+=work(S[i-1],S[i+1]);now+=M-1;
34             if(now==ans){
35                 cnt++;continue;
36             }
37             if(now<ans){
38                 ans=now;cnt=1;continue;
39             }
40         }
41         cout<<ans<<" "<<cnt<<endl;
42         for(int i=0;i<=M+1;i++)S[i]=0;
43     }
44     return 0;
45 }

C.Yet Another Permutation Problem

题意：给定序列的长度 N ，求一个 N 的排列使得所有 gcd（ A[ i ] ，A[ i+1 ] ）（注：i==N 时令A[ i+1 ] = A[ 1 ] ）的取值最多；

看了样例，考虑对于一个数 x 后面一直取 2*x 直到超出范围，可以使得 gcd（ x ，2*x ）= x ；

 1 #include<bits/stdc++.h>
 2 #define ll long long 
 3 using namespace std;
 4 int read(){
 5     char ch=getchar();int x=0,f=1;
 6     while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
 7     while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
 8     return x*f;
 9 }
10 const int maxn=1e5+5;
11 ll T,N;
12 ll vis[maxn];
13 int main(){
14     T=read();
15     while(T--){
16         N=read();
17         for(int i=1;i<=N;i++)vis[i]=0;
18         
19         for(int i=1;i<=N;i++){
20             if(vis[i])continue;
21             cout<<i<<" ";
22             vis[i]=1;
23             int j=i;
24             while(2*j<=N){
25                 if(vis[2*j]==0){
26                     vis[2*j]=1;j=2*j;
27                     cout<<j<<" ";
28                     continue;
29                 }
30                 break;
31             }
32         }
33         cout<<endl;
34     }
35     return 0;
36 }

D.Trees and Segments

题意：给定一个01串 s ，最长连续 0 串的长度 L0 ，最长连续 1 串的长度 L1 ，（ 如果没有0，则L0=0，如果没有1，则L1 = 1 ），最后计算美感 = A * L0 + L1，1 <= A <= N ；可以改变01串中的不超过K个数为相反的值，

问对于每一个 A ，最大的美感是多少；

有空补（）