您的位置: 首页 > IT文章 > Codeforces Round 554 (Div.2)

Codeforces Round 554 (Div.2)

分类: IT文章 • 2025-01-07 16:44:14

A.奇数配偶数。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #define rep(i,l,r) for (int i=(l); i<=(r); i++)
 6 typedef long long ll;
 7 using namespace std;
 8 
 9 int n,m,x,s1,s2;
10 
11 int main(){
12     scanf("%d%d",&n,&m);
13     rep(i,1,n) scanf("%d",&x),s1+=x&1;
14     rep(i,1,m) scanf("%d",&x),s2+=x&1;
15     printf("%d
",min(s1,m-s2)+min(s2,n-s1));
16     return 0;
17 }

B.每次将二进制最高位异或掉，实时判断是否符合条件即可。由于数最多有20位所以总操作次数显然不会超过40。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define rep(i,l,r) for (int i=(l); i<=(r); i++)
 5 using namespace std;
 6 
 7 int x,s[50],t[50],a[45],ans,cnt;
 8 
 9 void work(int x){
10     int tmp=x; cnt=0;
11     while (tmp) t[++cnt]=tmp&1,tmp>>=1;
12 }
13 
14 bool pd(int x){
15     rep(i,0,30) if (x==s[i]-1) return 1;
16     return 0;
17 }
18 
19 int main(){
20     scanf("%d",&x); s[0]=1;
21     rep(i,1,30) s[i]=1<<i;
22     work(x); int flag=0;
23     for(int i=cnt; i; i--){
24         if (!t[i]){
25             x^=(s[i]-1);
26             if (pd(x)){ a[++ans]=i; flag=1; break; }
27             x++; a[++ans]=i; memset(t,0,sizeof(t)); work(x);
28         }
29     }
30     printf("%d
",ans*2-flag);
31     rep(i,1,ans) printf("%d ",a[i]);
32     return 0;
33 }

C.lcm(a+k,b+k)=(a+k)(b+k)/gcd(a+k,b+k)=(a+k)(b+k)/gcd(|a-b|,a+k)。枚举|a-b|的所有因子作为gcd计算出a+k的最小值从而得到答案。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #define rep(i,l,r) for (ll i=(l); i<=(r); i++)
 6 typedef long long ll;
 7 using namespace std;
 8 
 9 int a,b;
10 ll kk,ans=1e18;
11 
12 int main(){
13     scanf("%d%d",&a,&b); ll t=abs(a-b);
14     for (ll i=1; i*i<=t; i++){
15         ll k=((a-1)/i+1)*i-a,s=(a+k)*(b+k)/__gcd(a+k,b+k);
16         if (s<ans || (s==ans && kk>k)) ans=s,kk=k;
17         k=((a-1)/(t/i)+1)*(t/i)-a,s=(a+k)*(b+k)/__gcd(a+k,b+k);
18         if (s<ans || (s==ans && kk>k)) ans=s,kk=k;
19     }
20     cout<<kk<<endl;
21     return 0;
22 }

D.观察发现每个偶数层（根算第0层）节点一定比它上面那层多，也就是将所有奇数层的点随便选一个儿子匹配就能得到最大匹配。于是问题就是求这棵Trie中所有奇数层的点数和。

另外有一个这个题可能并没有用到的性质：对一个括号序列来说，在很多情况下，“左括号数-右括号数”是它的唯一属性。也就是说如果两个括号序列的“左括号数-右括号数”相等，那么它们在Trie上的子树一定长得一模一样。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define rep(i,l,r) for (int i=(l); i<=(r); i++)
 4 typedef long long ll;
 5 using namespace std;
 6 
 7 const int N=1010,mod=1e9+7;
 8 int n,ans,f[N],g[N];
 9 
10 int main(){
11     scanf("%d",&n); f[0]=1;
12     rep(i,1,2*n){
13         rep(j,0,n) g[j]=0;
14         rep(j,0,n){
15             if (j) g[j-1]=(g[j-1]+f[j])%mod;
16             if (2*n-i>j) g[j+1]=(g[j+1]+f[j])%mod;
17         }
18         rep(j,0,n) f[j]=g[j];
19         if (i&1) rep(j,0,n) ans=(ans+f[j])%mod;
20     }
21     printf("%d
",ans);
22     return 0;
23 }

Codeforces Round 554 (Div.2)

相关推荐