Codeforces Round #693 (Div. 3)
前言:
期末考试重修还更博客= - =)
A. Cards for Friends
直接按题意模拟,看可以分成多少个2的次幂.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+500;
int w[N];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
int x,y;
cin>>x>>y>>n;
int res=1;
while(x%2==0)
{
res*=2;
x/=2;
}
while(y%2==0)
{
res*=2;
y/=2;
}
if(res>=n) puts("YES");
else puts("NO");
}
return 0;
}B. Fair Division
方法1:直接模拟,因为糖果一定是2/1的,就两种情况,所以你先把2的分析完奇偶讨论下即可.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
int cnt[3];memset(cnt,0,sizeof cnt);
scanf("%d",&n);int x;
for(int i=1;i<=n;i++) scanf("%d",&x),cnt[x]++;
if(cnt[2]&1)
{
cnt[1]-=2;
if(cnt[1]<0) puts("NO");
else if(cnt[1]&1) puts("NO");
else puts("YES");
}
else
{
if(cnt[1]&1) puts("NO");
else puts("YES");
}
}
return 0;
}方法2:假如不止1,2两种糖果咋办,题目要你平分,所以假如一个数在%sum/2之前出现过,就必然会有种平分方案.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+500;
ll w[N];
map<ll,bool>mp;
int main()
{
int T;
//T=1;
scanf("%d",&T);
while(T--)
{
mp.clear();
int n;
ll sum=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&w[i]);
sum+=w[i];
}int flag=0;
if(sum%2!=0)
{
puts("NO");flag=1;
}sum/=2;ll res=0;
for(int i=1;i<=n;i++)
{
if(sum==0) break;
res+=w[i];
res%=sum;
if(mp[res]&&!flag)
{
puts("YES");
flag=1;break;
}mp[res]=true;
}
if(!flag) puts("NO");
}
return 0;
}C. Long Jumps
题目已知这个方程,直接写个for就好了.
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+500;
typedef long long ll;
ll f[N];int a[N];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),f[i]=a[i];
ll ans=0;
for(int i=1;i<=n;i++)
{
ans=max(f[i],ans);
if(i+a[i]>n) continue;
f[i+a[i]]=max(f[i+a[i]],f[i]+a[i+a[i]]);
}cout<<ans<<'\n';
}
return 0;
} D. Even-Odd Game
把奇偶分开,然后我们站在Alice和BOb的角度进行选择,假如你是Alice,Bob选下一个获得比你多,那么你肯定是不让Bob加分,Alice同理.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+500;
int even[N],odd[N];
bool cmp(int A,int B)
{
return A>B;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
ll res_A=0,res_B=0;
int idA=0,idB=0;
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
if(x&1) odd[++idB]=x;
else even[++idA]=x;
}
sort(even+1,even+1+idA,cmp);
sort(odd+1,odd+1+idB,cmp);
int nA=1,nB=1;
for(int i=1;i<=n;i++)
{
if(i&1)//Alice选择
{
if(nB<=idB&&nA<=idA)
{
if(even[nA]>odd[nB]) res_A+=even[nA],nA++;
else nB++;
}
else if(nB<=idB) nB++;
else res_A+=even[nA],nA++;
}
else//Bob选择.
{
if(nB<=idB&&nA<=idA)
{
if(even[nA]<odd[nB]) res_B+=odd[nB],nB++;
else nA++;
}
else if(nA<=idA) nA++;
else res_B+=odd[nB],nB++;
}
}
if(res_A>res_B) puts("Alice");
else if(res_A==res_B) puts("Tie");
else puts("Bob");
}
return 0;
}E. Correct Placement
无法就是让你在二维平面找到两维都比自己小的数,另一种方案就是x,y交换一下放入数组,然后我们维护一维,另外一维维护一个min即可.
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+500;
int ans[N<<1];
struct Tree{
int l,r,idx;
}w[N<<1];
bool cmp(Tree A,Tree B)
{
if(A.l==B.l) return A.r<B.r;
else return A.l<B.l;
}
int _val[N<<1],_id[N<<1];//维护到了i,r的最小值以及下标即可.
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int n;scanf("%d",&n);
int id=n;
for(int i=1;i<=n;i++)
{
ans[i]=0;
scanf("%d%d",&w[i].l,&w[i].r);w[i].idx=i;
w[++id].l=w[i].r;w[id].r=w[i].l,w[id].idx=i;
}sort(w+1,w+1+id,cmp);
int last=-1;//维护前一个r的最小值即可.
_val[0]=2e9,_id[0]=-1;
for(int i=1;i<=id;i++)
{
_val[i]=_val[i-1],_id[i]=_id[i-1];
if(w[i].r<_val[i]) _val[i]=w[i].r,_id[i]=w[i].idx;
if(w[i].l>w[i-1].l)
{
last=i-1;
if(w[i].r>_val[i]) ans[w[i].idx]=_id[i];
else ans[w[i].idx]=-1;
}
else//只能找last前面的数.
{
if(w[i].r>_val[last]) ans[w[i].idx]=_id[last];
else ans[w[i].idx]=-1;
}
}
for(int i=1;i<=n;i++) printf("%d ",ans[i]);
puts("");
}
}F. New Year's Puzzle
简单模拟即可.模拟每个障碍下你是不是能填完,然后假如可以填完就是YES,否则就是NO.
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+500;
struct Graph
{
int r,c;
}w[N];
bool cmp(Graph A,Graph B)
{
if(A.c==B.c) return A.r<B.r;
else return A.c<B.c;
}
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) scanf("%d%d",&w[i].r,&w[i].c);
int r1=0,r2=0;//设置我已经填到哪里了.
bool flag=true;sort(w+1,w+1+m,cmp);
w[++m].r=1,w[m].c=n+1;
w[++m].r=2,w[m].c=n+1;
for(int i=1;i<=m;i++)
{
//cout<<r1<<' '<<r2<<endl;
if(w[i].c==w[i+1].c)//两个一起处理.
{
//cout<<r1<<' '<<w[i].c<<endl;
if((max(r2,r1)-min(r2,r1))&1) flag=false;
r1=r2=w[i].c;
i++;
}
else//单个处理
{
int p=w[i].r;//在第p行.
if(p==1)
{
if((w[i].c-r1)%2!=1&&((max(r2,r1)-min(r2,r1))%2!=0)) flag=false;
if((w[i].c-r1)%2==1) r1=w[i].c;
else if((w[i].c-r1)%2!=1&&((max(r2,r1)-min(r2,r1))%2==0)) r1=w[i].c,r2=w[i].c-1;
}
else
{
if((w[i].c-r2)%2!=1&&((max(r2,r1)-min(r2,r1))%2!=0)) flag=false;
if((w[i].c-r2)%2==1)
{
r2=w[i].c;
}
else if(((w[i].c-r2)%2!=1)&&((max(r2,r1)-min(r2,r1))%2==0))
{
r2=w[i].c,r1=w[i].c-1;
}
}
}
}//cout<<flag<<endl;
if(flag) puts("YES");
else puts("NO");
}
return 0;
}
/*
1
6 3
2 1
1 3
2 5 NO
1
5 2
2 2
2 3 YES
*/G. Moving to the Capital
dp,先跑出题意要求的d[]数组,然后我们获得了一个bfs序,然后我们更新一次f[i],最后按bfs序更新一次即可.
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+50;
int f[N],d[N];
vector<int>v[N];
vector<int>q;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) v[i].clear(),d[i]=-1;
d[1]=0;q.clear();
for(int i=1;i<=m;i++)
{
int x,y;scanf("%d%d",&x,&y);
v[x].push_back(y);
}q.push_back(1);
for(int i=0;i<n;i++)
{
int u=q[i];
for(int x:v[u])
{
if(d[x]==-1)
{
d[x]=d[u]+1;
q.push_back(x);
}
}
}//跑出所有d[i].
for(int i=1;i<=n;i++)
{
f[i]=d[i];
for(int x:v[i])
{
f[i]=min(f[i],d[x]);
}
}//预处理出来每个f[i].
for(int i=n-1;i>=0;i--)
{
int u=q[i];
for(int x:v[u])
{
if(d[u]<d[x])f[u]=min(f[u],f[x]);
}
}//按时间来dp.
for(int i=1;i<=n;i++) printf("%d ",f[i]);
puts("");
}
return 0;
}lpt的小屋 文章被收录于专栏
我想要一份甜甜的爱情
