Codeforces Round #857 Div.1/Div.2 CF1801/1802 2A~2F 题解
Div 2A. Likes
如果要赞最多，肯定是先放所有的点赞，再放所有移除的操作。如果要最少，那就先把赞分成两种：最后被移除的和没被移除的；最后先放所有被移除的，放一个移除一个，然后再把所有没被移除的接在最后即可。
时间复杂度\(O(n)\)。
点击查看代码
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define fi first
#define se second
#define pb push_back
#define mpr make_pair
void fileio()
{
#ifdef LGS
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
}
void termin()
{
#ifdef LGS
std::cout<<"\n\nEXECUTION TERMINATED";
#endif
exit(0);
}
using namespace std;
int t,n,a[110],ans1[110],ans2[110];
int main()
{
fileio();
cin>>t;
rep(tn,t)
{
cin>>n;
int posi=0,nega=0;
rep(i,n) cin>>a[i];
rep(i,n) if(a[i]>0) ++posi;else ++nega;
int bigp=posi,bign=nega,smlp=posi,smln=nega,ansbig=0,anssml=0;
repn(i,n)
{
if(bigp)
{
--bigp;
++ansbig;
}
else
{
--bign;
--ansbig;
}
if(i<=nega*2)
{
if(i%2==1) ++anssml;
else --anssml;
}
else ++anssml;
ans1[i]=ansbig;ans2[i]=anssml;
}
repn(i,n) cout<<ans1[i]<<' ';cout<<endl;
repn(i,n) cout<<ans2[i]<<' ';cout<<endl;
}
termin();
}
Div 2B. Settlement of Guinea Pigs
对每个时刻求出可能需要的最大猪圈数，然后取max即可。对于一个时刻，可以把猪分成两类，已经认证性别的和没认证的。没认证的只能自己住一个猪圈，因为和任意其他猪住一个都可能不合法。已经认证的，如果总数是>0的偶数，肯定是两类都是奇数个的情况最费猪圈；如果是奇数，那就是一类奇数一类偶数，猪圈数是固定的；总数是0那就是0个猪圈。
时间复杂度\(O(n)\)。
点击查看代码
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define fi first
#define se second
#define pb push_back
#define mpr make_pair
void fileio()
{
#ifdef LGS
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
}
void termin()
{
#ifdef LGS
std::cout<<"\n\nEXECUTION TERMINATED";
#endif
exit(0);
}
using namespace std;
int t,n,a[100010];
int calc(int pre)
{
if(pre==0) return 0;
if(pre==1) return 1;
if(pre==2) return 2;
if(pre%2==0) return (pre-2)/2+2;
return (pre+1)/2;
}
int main()
{
fileio();
cin>>t;
rep(tn,t)
{
cin>>n;
int pre=0,nxt=0,ans=0;
rep(i,n)
{
int x;scanf("%lld",&x);
if(x==1)
{
++nxt;
ans=max(ans,nxt+calc(pre));
}
else
{
pre+=nxt;nxt=0;
ans=max(ans,calc(pre));
}
}
cout<<ans<<endl;
}
termin();
}
Div 1A/2C. The Very Beautiful Blanket
怎么每场都有猜谜题呢。。。
首先猜一个：不同数的最大个数是n*m，很多这种题都是先猜能达到最大值的
观察题目中的那个两个田字格异或和相等的限制，其实只要对\(2^0\cdots 2^{63}\)的每个bit都满足就行了。对于每个bit，发现如果我们只把一些行中所有的数都刷上这个bit，其他的行不刷，是满足限制的。比如我们令第1,3,5,6行所有的数都含有\(2^3\)，其他的行都不含有，是符合限制的，这时每个田字格的异或和都是0。发现使用这种刷一行或一列的方式，我们可以让矩阵中的所有数都不同。比如我们令数组\(a=\{0,1,2,\cdots 9\},b=\{10,11,12\cdots 19\}\)。矩阵中第i行j列的数含有\(2^{a_k}\)当且仅当i中含有\(2^k\)，含有\(2^{b_k}\)当且仅当j中含有\(2^k\)。这么操作其实就是给一些行和一些列都刷上了某一个bit，且成功区别开了所有行和所有列，使得矩阵中每一个数都不同。
时间复杂度\(O(nmlognlogm)\)。
点击查看代码
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define fi first
#define se second
#define pb push_back
#define mpr make_pair
void fileio()
{
#ifdef LGS
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
}
void termin()
{
#ifdef LGS
std::cout<<"\n\nEXECUTION TERMINATED";
#endif
exit(0);
}
using namespace std;
int t,n,m,ans[210][210];
vector <int> r,c;
int main()
{
fileio();
rep(i,10) r.pb(1<<i);
for(int i=10;i<20;++i) c.pb(1<<i);
cin>>t;
rep(tn,t)
{
cin>>n>>m;
rep(i,n) rep(j,m)
{
ans[i][j]=0;
rep(k,r.size()) if(i&(1<<k)) ans[i][j]|=r[k];
rep(k,c.size()) if(j&(1<<k)) ans[i][j]|=c[k];
}
cout<<n*m<<endl;
rep(i,n)
{
rep(j,m) printf("%d ",ans[i][j]);
puts("");
}
}
termin();
}
Div 1B/2D. Buying gifts
先把所有department按\(a_i\)从小到大排序，枚举给第一个人买的礼物最大值\(a_i\)，此时i右侧的必须全买给第二个人，左侧的可以给第一个人也可以给第二个人。首先令i右侧的\(b_i\)最大值为\(mx\)，如果\(mx\ge a_i\)，此时的答案就是\(mx-a_i\)；否则可以在i左侧的\(b_i\)中找一个与\(a_i\)最接近的再次更新答案，可以用multiset实现。需要特判一下\(i=n\)的情况。
时间复杂度\(O(nlogn)\)。
点击查看代码
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <LL,LL>
#define fi first
#define se second
#define pb push_back
#define mpr make_pair
void fileio()
{
#ifdef LGS
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
}
void termin()
{
#ifdef LGS
std::cout<<"\n\nEXECUTION TERMINATED";
#endif
exit(0);
}
using namespace std;
LL t,n;
vector <pii> a;
multiset <LL> l,r;
LL findNearL(LL x)
{
auto it=l.lower_bound(x);
pii ret=mpr(1e18,1e18);
if(it!=l.end()) ret=min(ret,mpr(llabs(*it-x),*it));
if(it!=l.begin())
{
--it;
ret=min(ret,mpr(llabs(*it-x),*it));
}
return ret.se;
}
int main()
{
fileio();
cin>>t;
rep(tn,t)
{
cin>>n;
a.clear();
LL x,y;
rep(i,n)
{
scanf("%lld%lld",&x,&y);
a.pb(mpr(x,y));
}
sort(a.begin(),a.end());
l.clear();r.clear();
rep(i,a.size()) r.insert(a[i].se);
LL ans=1e18;
rep(i,a.size())
{
r.erase(r.lower_bound(a[i].se));
if(i-1>=0) l.insert(a[i-1].se);
if(i==a.size()-1) break;
LL mx2=*r.rbegin();
ans=min(ans,llabs(mx2-a[i].fi));
if(mx2<a[i].fi&&l.size())
{
LL val=findNearL(a[i].fi);
ans=min(ans,llabs(val-a[i].fi));
}
}
LL val=findNearL(a.back().fi);
ans=min(ans,llabs(val-a.back().fi));
cout<<ans<<endl;
}
termin();
}
Div 1C/2E. Music Festival
首先令\(mx_i\)表示第i个专辑中的最大值，发现如果一个mx小的专辑排在一个mx大的专辑后面(mx相等也一样)，那这个专辑是不能产生任何贡献的。所以可以先把所有专辑按\(mx_i\)从小到大排序，我们现在要在其中选一些使得前缀最大值的个数最多。可以用dp实现，\(dp_{i,j}\)表示处理到第i个专辑，此时被选的专辑中mx的最大值为j的最大前缀最大值个数。这状态是\(O(n^2)\)的，但是在处理每个i时改变的状态数都很少，所以可以用线段树维护j这一维，转移时枚举当前专辑中得到的前缀最大值个数，就能得到可以从其转移的j的范围，在线段树上询问即可。注意事项：每个测试点不能直接清空整个线段树，会TLE，要先把值域离散化后清空要用的部分。
时间复杂度\(O(nlogn)\)。
点击查看代码
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define fi first
#define se second
#define pb push_back
#define mpr make_pair
void fileio()
{
#ifdef LGS
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
}
void termin()
{
#ifdef LGS
std::cout<<"\n\nEXECUTION TERMINATED";
#endif
exit(0);
}
using namespace std;
int t,n;
vector <pair <int,vector <int> > > v;
vector <int> dsc;
int getDSC(int x){return lower_bound(dsc.begin(),dsc.end(),x)-dsc.begin();}
namespace st
{
int n2,dat[800010];
void upd(int k,int val)
{
dat[k]=max(dat[k],val);
while(k>0)
{
k=(k-1)/2;
dat[k]=max(dat[k],val);
}
}
int qry(int k,int lb,int ub,int tlb,int tub)
{
if(ub<tlb||tub<lb) return 0;
if(tlb<=lb&&ub<=tub) return dat[k];
return max(qry(k+k+1,lb,(lb+ub)/2,tlb,tub),qry(k+k+2,(lb+ub)/2+1,ub,tlb,tub));
}
}
int main()
{
fileio();
cin>>t;
rep(tn,t)
{
cin>>n;
v.clear();dsc.clear();
rep(i,n)
{
int x,y,mx=-1e9;vector <int> tmp;
scanf("%d",&x);
rep(j,x)
{
scanf("%d",&y);
mx=max(mx,y);tmp.pb(y);dsc.pb(y);
}
v.pb(mpr(mx,tmp));
}
sort(v.begin(),v.end());
sort(dsc.begin(),dsc.end());dsc.erase(unique(dsc.begin(),dsc.end()),dsc.end());
rep(i,v.size()) rep(j,v[i].se.size()) v[i].se[j]=getDSC(v[i].se[j]);
st::n2=1;while(st::n2<dsc.size()) st::n2*=2;
rep(i,st::n2*2+3) st::dat[i]=0;
rep(i,v.size())
{
vector <int> premx;
int mx=-1;
rep(j,v[i].se.size()) if(v[i].se[j]>mx)
{
mx=v[i].se[j];
premx.pb(mx);
}
int opt=-1;
rep(i,premx.size())
{
int lb=(i==0 ? 0:premx[i-1]),ub=premx[i]-1;
int val=st::qry(0,0,st::n2-1,lb,ub)+premx.size()-i;
opt=max(opt,val);
}
st::upd(premx.back()+st::n2-1,opt);
}
cout<<st::dat[0]<<endl;
}
termin();
}
Div 1D/2F. The way home
无论是cf还是atc，这种用比较复杂的状态跑最短路的题还是经常有的。
先明确我们走的思路：当要坐某趟航班钱不够时，就在我们走到过的报酬最高的城市不断补表演，直到钱够做这次航班为止。
令\(dist_{i,j}\)表示当前走到i号点，在这次走到i号点之前经过的\(w\)最大的点的编号为j，此时的最小表演数和最大剩余钱数(先按最小表演数从小到大排序，相同的再按剩余钱数从大到小排序)。我们来证明：如果\(dist_{i,j}\)有两个可能的状态\(\{a,b\}\)和\(\{c,d\}\)(ac表示最小表演数，bd表示钱数)，且a<c，b<d，此时第一个状态一定优于第二个。用一种类似归纳的思想，我们假设已经对这两个状态转移过来的路径上的所有\(dist_{i,j}\)都证明了其最优状态唯一。由于这两个状态在这次到i之前经过的报酬最高的点都是j，因此它们是从同一个\(dist_{j,*}\)转移过来的，在那之后它们的表演数才变得不同。因此第二个状态的d肯定\(<w_j\)，因为我们补表演是补到能坐航班就停了，所以剩下的一定\(<w_j\)。因此如果给第一个状态补\(c-a\)次表演，使两个状态表演次数相同，第一个的钱数一定比第二个多，所以第一个一定更优。
然后就用上面的状态跑一个Dijkstra就行了，时间复杂度\(O(nmlog(n^2))\)(可能？没仔细算)。
点击查看代码
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <LL,LL>
#define fi first
#define se second
#define pb push_back
#define mpr make_pair
void fileio()
{
#ifdef LGS
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
}
void termin()
{
#ifdef LGS
std::cout<<"\n\nEXECUTION TERMINATED";
#endif
exit(0);
}
using namespace std;
LL t,n,m,p,w[810];
vector <pii> g[810];
pii dist[810][810];
priority_queue <pair <pii,pii> > q;
int main()
{
fileio();
cin>>t;
rep(tn,t)
{
cin>>n>>m>>p;
repn(i,n) scanf("%lld",&w[i]);
rep(i,n+3) g[i].clear();
LL x,y,z;
rep(i,m)
{
scanf("%lld%lld%lld",&x,&y,&z);
g[x].pb(mpr(y,z));
}
rep(i,n+3) rep(j,n+3) dist[i][j]=mpr(-1e18,-1e18);
dist[1][0]=mpr(0,p);
q.push(mpr(mpr(0,p),mpr(1,0)));
while(!q.empty())
{
auto fr=q.top();q.pop();
pii val=fr.fi;LL pos=fr.se.fi,opt=fr.se.se;
if(dist[pos][opt]>val) continue;
if(w[pos]>w[opt]) opt=pos;
rep(i,g[pos].size())
{
pii nval=val;
if(nval.se<g[pos][i].se)
{
LL add=(g[pos][i].se-nval.se+w[opt]-1)/w[opt];
nval.fi-=add;nval.se+=add*w[opt];
}
nval.se-=g[pos][i].se;
if(dist[g[pos][i].fi][opt]<nval)
{
dist[g[pos][i].fi][opt]=nval;
q.push(mpr(nval,mpr(g[pos][i].fi,opt)));
}
}
}
pii ans=mpr(-1e18,-1e18);
repn(i,n) ans=max(ans,dist[n][i]);
if(ans.fi< -1e17) puts("-1");
else cout<< -ans.fi<<endl;
}
termin();
}
由于我用小号打的Div2，所以看不到过了一车的那个1F，1E也不会。后面如果有时间会更新1E和1F的题解