Codeforces Round 1046 (Div. 2) vp补题

只是签了三道题就燃尽了…
原题连接

A

//不可能连续进三球 得分值差最多的只有00X00X00X00 
bool jud(int a,int b){if(a!=0&&b!=0&&max(a,b)-2*(min(a,b)+1)>=1)return 0;if(a==0||b==0){if(abs(a-b)>=3)return 0;}return 1;
}
void solve()
{int a,b,c,d;cin>>a>>b>>c>>d;if(jud(a,b)==0)return cout<<"no"<<endl,void();int d1=c-a,d2=d-b;	cout<<(jud(d1,d2)?"yes":"no")<<endl;
}

B 构造

void solve()
{int n,k;cin>>n>>k;string s;cin>>s;int cnt=0,id=0;while (id<n){if(s[id]!='1'){id++;continue;}int st=id;id++;while (id<n&&s[id]=='1'){id++;}cnt=max(cnt,id-st);}if(cnt>=k)cout<<"no"<<endl;//连续的1不能长于k 否则区间内不能满足没有最大值else{cout<<"yes"<<endl;int f=1,e=n;forr(i,0,n-1){if(s[i]=='0')cout<<e--<<' ';else cout<<f++<<' ';//不能是最大值的位置往小了填}cout<<endl;}
}

C dp 定长滑动窗口

一开始没理解好子序列的意思，以为是从头尾删去得到序列，导致第五个样例看不明白
看明白了转用dp，但是只记录了整洁数组的起始位置，没有注意到像333333这样的，可以取中间部分当作整洁数组，使用定长窗口处理

void solve()
{int n;cin>>n;forr(i,1,n)v[i].clear();vector<int>a(n+1),dp(n+1,0);// vector<int>cnt(n+1,0),st(n+1,-1);forr(i,1,n)cin>>a[i];forr(i,1,n){v[a[i]].push_back(i);//把位置放进去dp[i]=dp[i-1];if(v[a[i]].size()>=a[i]){//窗口dp[i]=max(a[i]+dp[v[a[i]][v[a[i]].size()-a[i]]-1],dp[i]);}// if(st[a[i]]==-1)st[a[i]]=i;//最优的可能不是开头 就好像滑动窗口// cnt[a[i]]++;// if(cnt[a[i]]==a[i]){// 	dp[i]=dp[st[a[i]]-1]+a[i];// 	st[a[i]]=-1;// 	cnt[a[i]]=0;// }else dp[i]=dp[i-1];}int ans=0;forr(i,1,n)ans=max(ans,dp[i]);// forr(i,1,n)cout<<dp[i]<<' ';cout<<endl;cout<<ans<<endl;
}

D 交互题 思维

首先要确定是离哪个点的曼哈顿距离
$-1e9<x_i,y_i<1e9$

• 先移到右上角，$X+2e9,Y+2e9$，得到离$m1=max(x_i+y_i)$位置点的曼哈顿距离$d1$，$X+2e9-x_i+Y+2e9-y_i=X+Y+4e9-m1=d1$
• 再移到右下角，$X+2e9,Y-2e9$，得到离$m2=max(x_i-y_i)$位置点的曼哈顿距离$d2$，$(X+2e9-x_i)+(y_i-(Y-2e9))=X-Y+4e9-m2=d2$
• 解方程$X=\frac{d1+d2+m1+m2-8e9}{2},Y=\frac{d1-d2+m1-m2}{2}$

const int N=1e6+10,M=6e3+10,mod=998244353,inf=1e9;
void solve(){int n;cin>>n;int m1,m2;m1=m2=-1e18;forr(i,1,n){int x,y;cin>>x>>y;m1=max(x+y,m1);m2=max(x-y,m2);}//右上int d1=0,d2=0;cout<<"? U "<<inf<<endl;fls;cin>>d1;cout<<"? U "<<inf<<endl;fls;cin>>d1;cout<<"? R "<<inf<<endl;fls;cin>>d1;cout<<"? R "<<inf<<endl;fls;cin>>d1;forr(i,1,4){cout<<"? D "<<inf<<endl;fls;cin>>d2;}int x=(d1+d2+m1+m2-8e9)/2,y=(d1-d2+m1-m2)/2;cout<<"! "<<x<<' '<<y<<endl;
}

$X+Y=sm1,X-Y=sm2\Rightarrow X=\frac{sm1+sm2}{2},Y=\frac{sm1-sm2}{2}$

E

需要tarjan 学习中…