Codeforces Round 964 (Div. 4) A~G

封面原图 画师ideolo

A - A+B Again?

题意

给你一个两位数，把他的个位和十位加起来

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;void solve()
{int n;scanf("%d",&n);printf("%d\n",n/10+n%10);
}int main()
{int T=1;scanf("%d",&T);while(T--){solve();}return 0;
}

B - Card Game

题意

两个人每人两张牌，以任意顺序轮流翻开比大小，问a获胜的可能性种数

思路

一共就4种 枚举一下就行了

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
bool play(int a1,int b1,int a2,int b2)
{int A=0,B=0;if(a1>b1) A++;else if(a1<b1) B++;if(a2>b2) A++;else if(a2<b2) B++;if(A>B) return true;else return false;
}void solve()
{int a1,a2,b1,b2;scanf("%d%d%d%d",&a1,&a2,&b1,&b2);int cnt=0;if(play(a1,b1,a2,b2)) cnt++;if(play(a1,b2,a2,b1)) cnt++;if(play(a2,b1,a1,b2)) cnt++;if(play(a2,b2,a1,b1)) cnt++;printf("%d\n",cnt);
}int main()
{int T=1;scanf("%d",&T);while(T--){solve();}return 0;
}

C - Showering

题意

一个人每天有很多段时间有不同的工作，问他能否挤出连续m分钟的空闲时间

思路

对所有工作时间排个序然后找中间的空有没有大于m的即可

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;void solve()
{int n,s,m;scanf("%d%d%d",&n,&s,&m);vector<pii> task;for(int i=0;i<n;i++){int l,r;scanf("%d%d",&l,&r);task.push_back({l,r});}task.push_back({0,0});task.push_back({m,m});sort(task.begin(),task.end());for(int i=0;i<=n;i++){if(task[i+1].first-task[i].second>=s){printf("YES\n");return ;}}printf("NO\n");
}int main()
{int T=1;scanf("%d",&T);while(T--){solve();}return 0;
}

D - Slavic’s Exam

题意

问s里面有没有子串t，其中的问号可以改成任意字母

思路

直接贪心，找到问号就直接变成t的下一个，因为就算后面有我提前变也不会让事情变得更糟糕的

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;void solve()
{string s,t;cin>>s>>t;int n=s.size(),m=t.size();int i=0,j=0;for(;i<n and j<m;i++){if(s[i]==t[j]){j++;}else if(s[i]=='?'){s[i]=t[j];j++;}}if(j<m){cout<<"NO\n";return ;}for(i=0;i<n;i++){if(s[i]=='?'){s[i]='a';}}printf("YES\n");cout<<s<<endl;
}int main()
{int T=1;scanf("%d",&T);while(T--){solve();}return 0;
}

E - Triple Operations

题意

每次给一个区间，问要做多少次操作才能把区间内所有数变成0，操作是每次选两个数，一个数乘三，一个数除三（向下取整）

思路

任何数乘3肯定都会变大，除了0，所以一开始我一定要创造一个0然后一直薅这一个羊毛就可以了，在他变成0的过程当中就会有一个数字乘了同样多的3，然后后续要把这个变回来，所以第一个数变成0需要的操作数其实是翻倍的，后面的都是只要知道除多少次3变成0就行
一个一个计算太慢了会TLE，我们发现数据范围不大，所以可以提前预处理每个数变成0需要的操作个数，每次给一个区间的话我们还可以对这个预处理的答案跑一遍前缀和，这样的话我们就可以用$O(1)$解决每一次询问了

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int pre[200010];
ll sum[200010];
void ini()
{memset(pre,0,sizeof(pre));for(int i=0;i<=200000;i++){int t=i;while(t>0){t/=3;pre[i]++;}}sum[0]=pre[0];for(int i=1;i<=200000;i++){sum[i]=sum[i-1]+pre[i];}
}void solve()
{int l,r;scanf("%d%d",&l,&r);ll ans=sum[r]-sum[l-1];ans+=pre[l];printf("%lld\n",ans);
}int main()
{int T=1;scanf("%d",&T);ini();while(T--){solve();}return 0;
}

F - Expected Median

题意

给一个0,1构成的数组，问所有长度为k的子串的中位数之和

思路

因为只由0,1构成，而且题目给了k一定是奇数，所以这个数组只要1多中位数就是1，反之也是一样，但0作为中位数没有任何意义，对答案没有贡献，那么有多少子串的1比较多呢？
我们可以使用组合数，假设一共是长度为k，那就在1里面选$(k-1)/2,(k-1)/2+1,......,k$个，剩下的选0，这一个过程直接用组合数计算即可

组合数的计算

因为赛时就是这个我不会使得没能拿下ak所以单独拿出来讲一下 我之前用的一直是开二维数组然后用二项式定理预处理 所以赛时写的是这样 喜提WA3

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
ll Combine[2010][2010];
void ini()
{memset(Combine,0,sizeof(Combine));for(int i=0;i<=2000;i++){Combine[i][0]=1;for(int j=1;j<=i;j++){Combine[i][j]=Combine[i-1][j]+Combine[i-1][j-1];}}
}
ll C(int n,int m)
{if(m>n)return 0;if(n>=2000 or m>=2000){return C(n-1,m-1)+C(n-1,m);}return Combine[n][m];
}void solve()
{int n,k;scanf("%d%d",&n,&k);int zero=0,one=0;for(int i=0;i<n;i++){int x;scanf("%d",&x);if(x==0)zero++;elseone++;}ll hlf=k/2+1;ll ans=0;for(;hlf<=min(k,one);hlf++){ans+=C(one,hlf)%MOD*C(zero,k-hlf)%MOD;ans%=MOD;}printf("%lld\n",ans);
}int main()
{int T=1;scanf("%d",&T);ini();while(T--){solve();}return 0;
}

至于更高级的算法，我三言两语讲不清楚，丢个acwing的链接吧

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const int N=2e6+10;
ll fact[N],infact[N];ll qpow(ll a,ll b)
{ll res=1;while(b){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;
}void ini()
{fact[0]=infact[0]=1;for(int i=1;i<N;i++){fact[i]=fact[i-1]*i%MOD;infact[i]=qpow(fact[i],MOD-2);}
}ll C(ll a,ll b)
{if(a<b)return 0;return fact[a]*infact[b]%MOD*infact[a-b]%MOD;
}void solve()
{int n,k;scanf("%d%d",&n,&k);int zero=0,one=0;for(int i=0;i<n;i++){int x;scanf("%d",&x);if(x==0)zero++;elseone++;}ll hlf=k/2+1;ll ans=0;for(;hlf<=min(k,one);hlf++){ans+=C(one,hlf)%MOD*C(zero,k-hlf)%MOD;ans%=MOD;}printf("%lld\n",ans);
}int main()
{int T=1;scanf("%d",&T);ini();while(T--){solve();}return 0;
}

G - Ruler

题意

隐藏一个数，输入比他小的数不变，但是大于等于它的数的返回值都会加1，现在每次可以问两个数，告诉你他们返回值的乘积，需要在7次询问之内找到隐藏的这个数

思路

问的次数这么少肯定是二分，但是发现这题二分还不够，但是我们每次其实相当于可以问两个数字，所以我们可以直接三分区间，注意写的时候边界处理好就可以了，不要向我一样还wa了一发

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;void solve()
{int l=0,r=1000;while(l<r){int mid=(r-l)/3;int quart1=l+mid,quart2=r-mid;cout<<"? "<<quart1<<" "<<quart2<<"\n";cout.flush();int res;cin>>res;if(res==quart1*quart2)l=quart2+1;else if(res==quart1*(quart2+1)){l=quart1+1,r=quart2;}else if(res==(quart1+1)*(quart2+1)){r=quart1;}}cout<<"! "<<l<<"\n";cout.flush();
}int main()
{int T=1;scanf("%d",&T);while(T--){solve();}return 0;
}