写在题解之前:刷了也有一百道的div2题目,可以发现A,B两道题目,往往需要发现题目给出的很妙的性质,特点即可解决.代码偏简单,只需要会语法即可.C题及后面开始,C题会涉及到一些简单算法,代码难度大大提高,并且不再拘泥于发现一个性质就可以解决,这个性质往往只是突破口,还需要严谨的数学逻辑和证明才能解决.
A
Description:有n支球队,起初都在胜者组,只有有组的队数>=2就可以进行比赛,胜者组输的队掉到败者组,败者组输的淘汰.问决出冠军打了几场比赛?
Solution:注意到胜者组输的队掉到败者组,且需要判断当前队数为奇偶时模拟逻辑稍有不同.两个一起模拟会很乱,我们可以先对胜者组进行模拟,输的队加到败者组,最后再对败者组模拟即可得到比赛场数.
code:
#define int long long
#define endl "\n"
using namespace std;
const int N=5e5+7;
const int mod=998244353;
void solve(){
int n;
cin>>n;
if(n==2){
cout<<"2\n";
return;
}
int ans=0,win=0,lose=0;
if(n%2) win=n/2+1,lose=n/2;
else win=lose=n/2;
ans+=n/2;
while(win!=1){
lose+=win/2,ans+=win/2;
if(win%2) win=win/2+1;
else win/=2;
}
while(lose!=1){
ans+=lose/2;
if(lose%2) lose=lose/2+1;
else lose/=2;
}
cout<<ans+1<<'\n';
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T=1;
cin>>T;
while(T--)solve();
return 0;
}
B
Description:有n*n的迷宫,每个格子都可以设置上下左右四个方向,给定k,问如何设计格子的方向使得有k个格子走出迷宫?
Solution:一个关键的发现:只需要让其左右或者上下来回移动即可使得这两个格子陷入无限循环而无法走出.于是得到结论:最少要有两个格子无法走出,不存在一个格子无法走出的情况.感性思考一下:其它格子都可以走出迷宫,而那个假设走不出的格子无论哪个方向都要走到其它走出的格子上,与假设矛盾.当然特判一下全部走出的情况.那么我们可以设置一个左右循环,让其它格子的方向都指到这个循环上,再从外围往里推,把k个格子的方向指向迷宫外.
Code:
#define int long long
#define endl "\n"
using namespace std;
const int N=5e5+7;
const int mod=998244353;
void solve(){
int n,k;
cin>>n>>k;
if(n*n-1==k){
cout<<"NO\n";
return;
}
cout<<"YES\n";
if(n*n==k){
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
cout<<'U';
}
cout<<'\n';
}
return;
}
vector<vector<char>>ans(n+1,vector<char>(n+1));
//最低循环需要两个:"RL"感性思考一下发现只要有两个循环就可以让其它格子都往这两个格子跑.反之不往这儿跑就可以出去
ans[1][1]='R',ans[1][2]='L';
for(int i=1;i<=n;++i){
for(int j=n;j>=3;--j){
ans[i][j]='L';
if(k==0) continue;
ans[i][j]='R';
k--;
}
}
for(int i=n;i>=2;--i){
for(int j=1;j<=2;++j){
ans[i][j]='U';
if(k==0) continue;
ans[i][j]='L';
k--;
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
cout<<ans[i][j];
}
cout<<'\n';
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T=1;
cin>>T;
while(T--)solve();
return 0;
}
C
需要的算法知识:差分,前缀和
Description:有n个巫师从左到右排成一排,每个巫师可以选择把自己的斗篷放在左边或者右边,如果巫师i把斗篷放在左边,那么1-i-1的巫师都看不到巫师i,i+1-n的巫师能看到巫师i,放在右边反之亦然.给长度为n的数组a,ai表示第i个巫师能看到其它巫师的数量(包括自己,自己肯定是能看到的).问斗篷放置方式的合理方案数.
Solution:一个关键的观察:相邻巫师能看到的数量<=1.证明:假设巫师i能看到ai个,巫师[i+1]能看到a[i+1]个,那么对于这两个巫师,从1-i-1,i+2-n的可见性是不变的,其差值就出现在i是否能看到i+1,i+1是否能看到i上.那么我们有:i左i+1左,a[i+1]-a[i]=1;i左i+1右,i右i+1左,a[i+1]-a[i]=0;i右i+1右,a[i+1]-a[i]=-1;于是我们发现,只要确定第一个人的状态就能确定第二个人的状态,以此类推确定所有人的状态.而第一个人的状态只有两种,所以斗篷的放置方式只有两种.我们分别假设第一个人的状态,构造出相应的斗篷放置方式,再去验证a数组,如果满足这就是一种合法的方案.
Code:
#define int long long
using namespace std;
const int N=5e5+7;
const int mod=998244353;
void solve(){
int n;
cin>>n;
vector<int>a(n+1);
for(int i=1;i<=n;++i){
cin>>a[i];
}
if(n==1){
if(a[1]==0) cout<<"0\n";
else cout<<"2\n";
return;
}
for(int i=1;i<n;++i){
if(abs(a[i]-a[i+1])>1){
cout<<"0\n";
return;
}
}
vector<int>b(n+1);
for(int i=1;i<n;++i){
b[i]=a[i+1]-a[i];
}
int ans=0;
bool flag=true;
vector<bool>st(n+1);
st[1]=0;
for(int i=1;i<n;++i){
if(b[i]==1){
if(st[i]){
flag=false;
break;
}
st[i+1]=0;
}
else if(b[i]==-1){
if(!st[i]){
flag=false;
break;
}
st[i+1]=1;
}
else{
st[i+1]=!st[i];
}
}
vector<int>cnt(n+2);
for(int i=1;i<=n;++i){
if(st[i]){
cnt[1]++,cnt[i+1]--;
}
else{
cnt[i]++,cnt[n+1]--;;
}
}
bool check=true;
for(int i=1;i<=n;++i){
cnt[i]=cnt[i-1]+cnt[i];
if(cnt[i]!=a[i]){
check=false;
break;
}
}
if(flag&&check) ans++;
flag=check=true;
for(int i=1;i<=n;++i) cnt[i]=0;
st[1]=1;
for(int i=1;i<n;++i){
if(b[i]==1){
if(st[i]){
flag=false;
break;
}
st[i+1]=0;
}
else if(b[i]==-1){
if(!st[i]){
flag=false;
break;
}
st[i+1]=1;
}
else{
st[i+1]=!st[i];
}
}
for(int i=1;i<=n;++i){
if(st[i]){
cnt[1]++,cnt[i+1]--;
}
else{
cnt[i]++,cnt[n+1]--;
}
}
for(int i=1;i<=n;++i){
cnt[i]=cnt[i-1]+cnt[i];
if(cnt[i]!=a[i]){
check=false;
break;
}
}
if(flag&&check) ans++;
cout<<ans<<'\n';
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T=1;
cin>>T;
while(T--)solve();
return 0;
}
D
Description:有n节电池,我们两节两节的找,询问哪一组有电.
Trick:交互题的询问次数是需要用完的.
Solution:a我们是没有知道的,因此这倒不是交互题了,而是一道神秘构造题.我们暴力枚举需要询问n*n次,显然超过了最大询问次数.假设有电的电池都在后面,那么前面的所有询问都无效.因此我们需要一个高效的寻找有电电池的方法.
关键trick:一对好电池的距离最大为[n/a],因此我们可以遍历长度为1,2,3,...,[n/a].我们一定能在遍历到长度<=[n/a]的时候找到一对好电池
Code:
#define int long long
using namespace std;
const int N=5e5+7;
const int mod=998244353;
void solve(){
int n;
cin>>n;
for(int i=1;i<n;++i){
for(int j=1;j+i<=n;++j){
cout<<j<<" "<<j+i<<endl;
int x;
cin>>x;
if(x) return;
}
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T=1;
cin>>T;
while(T--)solve();
return 0;
}
京公网安备 11010502036488号