A. Hall of Fame
先把不用操作就合法的情况判掉。然后发现交换LL,RR,RL都是没用的，只有交换LR是有用的，这样可以照亮相邻的两个位置。所以我们就是要找到一个位置i，满足\(s_i=L,s_{i+1}=R\)，且除了i和i+1，其他位置初始没有没被照亮的(其实这个条件必然满足)。所以随便找一个"LR"交换就行了，找不到就是无解。
时间复杂度\(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 pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
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];
string s;
int main()
{
fileio();
cin>>t;
rep(tn,t)
{
cin>>n>>s;
rep(i,n+3) a[i]=0;
int hv=0;
rep(i,n)
{
if(hv) a[i]=1;
if(s[i]=='R') hv=1;
}
hv=0;
for(int i=n-1;i>=0;--i)
{
if(hv) a[i]=1;
if(s[i]=='L') hv=1;
}
int tot=0;
rep(i,n) if(a[i]==0) ++tot;
if(tot==0) puts("0");
else
{
bool bad=true;
rep(i,n-1) if((int)(a[i]==0)+(int)(a[i+1]==0)==tot&&s[i]=='L'&&s[i+1]=='R')
{
cout<<i+1<<endl;
bad=false;break;
}
if(bad) puts("-1");
}
}
termin();
}
B. MKnez's ConstructiveForces Task
首先n为偶数的时候很容易构造出解，\(1,-1,1,-1\cdots\)就行了。样例里n=3是无解，看起来奇数都是无解。但真的是这样吗？由于任意相邻两个数的和都相等，所以最终序列奇数位置上的数都相同，偶数位置上的数也都相同。令\(m=\lfloor \frac n2\rfloor\)。则我们需要找到两个数a,b满足\((m+1)a+mb=a+b\)。发现除了n=3无解，其他n为奇数的情况都很容易找到满足要求的ab，\(a=-m,b=m+1\)即可。
时间复杂度\(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 pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
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;
int main()
{
fileio();
cin>>t;
rep(tn,t)
{
cin>>n;
if(n%2==0)
{
puts("YES");
rep(i,n/2) cout<<1<<' '<<-1<<' ';
cout<<endl;
}
else
{
if(n==3) puts("NO");
else
{
puts("YES");
int nn=n/2,a=-(nn-1),b=nn;
rep(i,n)
{
if(i%2==0) cout<<a<<' ';
else cout<<b<<' ';
}
cout<<endl;
}
}
}
termin();
}
C. Least Prefix Sum
令最终的前缀和数组为\(b_1\cdots b_n\)。发现\(b_m\)前面的数和后面的数是完全独立的(前面的\(a_i\)是否取反不影响后面的\(b_i\)与\(b_m\)的大小关系)，可以分开处理。
以\(b_1\cdots b_{m-1}\)为例。首先如果\(a_m>0\)肯定是不行的，会导致\(b_m>b_{m-1}\)，需要取反。我们可以用这种思路从\(m-1\)到0枚举，令当前枚举到i。同时维护一个数val表示\(b_m=b_i+val\)。枚举到i时我们先偷个懒，\(a_{i+1}\)先不取反，\(val+=a_{i+1}\)。如果此时\(val>0\)就有问题了，我们应该在\(a_{i+1}\cdots a_m\)中选一个没取过反的最大的正数去取反，这样是最优的。不断选没取过反的最大的正数取反，直到\(val\le 0\)为止。没取过反的正数集合可以用multiset维护。
\(b_{m+1}\cdots b_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 <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
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,a[200010];
int main()
{
fileio();
cin>>t;
rep(tn,t)
{
cin>>n>>m;--m;
rep(i,n) scanf("%lld",&a[i]);
multiset <LL> candel;
candel.insert(a[m]);
LL mo=a[m];//b[m]=当前+mo
LL ans=0;
for(int i=m-1;i>=0;--i)
{
while(mo>0)
{
LL val=*candel.rbegin();
++ans;
mo-=val+val;
candel.erase(--candel.end());
}
mo+=a[i];candel.insert(a[i]);
}
if(m+1<n)
{
candel.clear();mo=0;
//当前=b[m]+mo
for(int i=m+1;i<n;++i)
{
mo+=a[i];candel.insert(a[i]);
while(mo<0)
{
LL val=*candel.begin();
++ans;
mo-=val+val;
candel.erase(candel.begin());
}
}
}
cout<<ans<<endl;
}
termin();
}
D. Boris and His Amazing Haircut
首先如果存在\(b_i>a_i\)肯定无解，先把这个判掉。
对于一个位置i，如果\(a_i=b_i\)，那这个位置不需要特意来剪，只要所有剪到这个位置的刀的大小都\(\ge b_i\)就行了。否则，这个位置需要一个大小为\(b_i\)的刀特意来剪，且不能被\(<b_i\)的刀剪过。
对于每个\(v\)，把所有需要大小为v的刀特意去剪的位置统一处理。令这些位置为\(p_1\cdots p_k\)。如果每个位置都单独剪，那需要k把刀。对于相邻的两个位置，\(p_i,p_{i+1}\)，如果\([p_i+1,p_{i+1}-1]\)中所有的\(b_i\)都\(\le v\)，那它们就可以合并，用同一把刀剪，省下了一把刀。最后判一下大小为v的刀够不够用即可。
时间复杂度\(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 <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
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,a[200010],b[200010],x[200010];
map <int,vector <int> > needs;
map <int,int> hvs;
namespace st
{
int n2=1,dat[800010];
void build(int k,int lb,int ub)
{
if(lb==ub)
{
if(lb<n) dat[k]=b[lb];else dat[k]=-1e9;
return;
}
build(k+k+1,lb,(lb+ub)/2);build(k+k+2,(lb+ub)/2+1,ub);
dat[k]=max(dat[k+k+1],dat[k+k+2]);
}
int qry(int k,int lb,int ub,int tlb,int tub)
{
if(ub<tlb||tub<lb) return -1e9;
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)
{
scanf("%d",&n);
needs.clear();hvs.clear();
rep(i,n) scanf("%d",&a[i]);
rep(i,n) scanf("%d",&b[i]);
bool bad=false;
rep(i,n) if(a[i]!=b[i])
{
if(b[i]>a[i]) bad=true;
else needs[b[i]].pb(i);
}
scanf("%d",&m);
rep(i,m) scanf("%d",&x[i]),++hvs[x[i]];
if(bad){puts("NO");continue;}
st::n2=1;while(st::n2<n) st::n2*=2;
rep(i,st::n2*2+3) st::dat[i]=-1e9;
st::build(0,0,st::n2-1);
for(auto it:needs)
{
int tot=it.se.size();
rep(i,it.se.size()-1)
{
int l=it.se[i],r=it.se[i+1],res=st::qry(0,0,st::n2-1,l+1,r-1);
if(res<=it.fi) --tot;
}
if(hvs.find(it.fi)==hvs.end()||hvs[it.fi]<tot)
{
bad=true;
break;
}
}
puts(bad ? "NO":"YES");
}
termin();
}
E. Anya's Simultaneous Exhibition
对于两个人(a,b)，如果a能赢b，我们就连一条\(a\to b\)的有向边。连出所有这样的边我们就获得了一个竞赛图。但是我们不知道这个图长什么样，只能询问一个点到一个点集的出度大小。
众所周知竞赛图一定存在哈密顿路径，所以一定有至少一个点可以到达其它所有的点，而这题中能成为candidate master(CM)的点就是这个点以及与它在同一个强连通分量内的点。
我们先用n次询问问出每个点(在整个图中)的出度。把这些点按出度从大到小排序，观察发现出度最大的点一定是CM，如果有多个出度最大的点则它们全都是。证明：假设有一个点y是CM，而出度最大的点x不是(\(out_y\ge out_x\))。那么x和y直接相连的那条边肯定是\(y\to x\)。对于x能打赢的所有点，y都必须打赢那个点，不然y就会被x间接打败，这样x就也是CM了。但y不可能打败x能打败的每个点，因为出度不够了，证毕。
现在我们要找出与出度最大的点x在同一个SCC内的所有点。我们先把整个竞赛图强连通分量分解，把每个分量看成一整个节点并拓扑排序。对于拓扑序中任意两个分量\(s_i,s_j\)，显然\(s_i\)中的任意一个点都到\(s_j\)中的任意一个点有边。假设一共有k个连通分量，令x为\(s_i\)中的一个点，y为\(s_j\)中的一个点(i<j)，发现x到\(s_{i+1}\cdots s_k\)中的任意点都有边；而y只可能到\(s_{j}\cdots s_k\)中的点有边，且不能到自己有边。所以x的出度一定大于y。因此，拓扑序中最靠前的那个连通块，也就是能成为CM的连通块，是由出度最大的一些点组成的。
考虑用一种类似"归纳"的方法求出这个连通块内的所有点。把所有点按照出度从大到小排序后，假设现在我们已经确定了序列的前i个点是CM。如果第\(i+1\cdots n\)个点到前i个点都没有边，那最后的答案就是前i个点。否则我们找出后面的点中第一个到\(1\cdots i\)有边的点，令其为第j个点，则它也是CM，因此第\(1\cdots j\)个点都是CM(因为CM是这个序列的一个前缀)。用这种方法不断拓展CM的边界，直到不能拓展即可。这一步最多用n-1次询问。
所以总询问数不会超过2n。
我一开始想的是能不能逐步加入每个节点，同时维护哈密顿路径，但是需要维护的信息太多了没法做
点击查看代码
#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 <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
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 n,ans[260],mark[260];
vector <pii> v;
int main()
{
fileio();
cin>>n;
repn(i,n)
{
cout<<"? "<<i<<' ';
repn(j,n) if(j!=i) cout<<1;else cout<<0;
cout<<endl;
cout.flush();
int val;cin>>val;
v.pb(mpr(val,i));
}
sort(v.begin(),v.end());reverse(v.begin(),v.end());
int cur=1;
repn(i,v.size()-1)
{
cout<<"? "<<v[i].se<<' ';
memset(mark,0,sizeof(mark));
rep(j,cur) mark[v[j].se]=1;
repn(j,n) cout<<mark[j];cout<<endl;
cout.flush();
int val;cin>>val;
if(val) cur=i+1;
}
rep(i,cur) ans[v[i].se]=1;
cout<<"! ";repn(i,n) cout<<ans[i];
cout<<endl;
cout.flush();
termin();
}
F. Xorcerer's Stones
发现一旦我们对某一个点x操作过一次，再对它子树内的点操作就没有意义了。因为我们已经把x子树内所有点的权值都变成了一样的，子树怎么操作也玩不出什么花样来。唯一的问题是当x的子树大小为奇数时，无法再通过一次操作把子树中所有点的权值都变成0。但是发现对子树进行一些操作之后同样无法做到这一点。
所以我们从下往上操作。令\(dp_{i,j}\)表示对i的子树内部进行一些操作后，能不能使得子树权值异或和为j。转移的时候最所有儿子做背包即可。背包做完之后，再决定当前点要不要操作：如果此时异或和已经为0，一次操作即可把所有节点权值全变为0；如果此时异或和不为0，一次可以把所有节点权值变成一样的，两次可以全变为0。dp完了之后再倒着来一遍，构造一下方案即可。每个节点最多操作两次，所以总操作数不超过2n。
时间复杂度\(O(32^2n)\)。
点击查看代码
#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 <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
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 n,a[200010],dp[200010][40],sz[200010],dp2[200010][40],fr[200010][40];
vector <int> g[200010],ans;
void dfs(int pos)
{
sz[pos]=1;
rep(i,g[pos].size()) dfs(g[pos][i]),sz[pos]+=sz[g[pos][i]];
rep(i,g[pos].size()+3) rep(j,35) dp2[i][j]=0;
dp2[0][a[pos]]=1;
rep(i,g[pos].size()) rep(j,32) if(dp2[i][j])
rep(k,32) if(dp[g[pos][i]][k]) dp2[i+1][j^k]=1;
rep(i,32) dp[pos][i]=dp2[g[pos].size()][i];
if(sz[pos]%2==0) dp[pos][0]=1;
}
void dfs2(int pos,int to)
{
rep(i,g[pos].size()+3) rep(j,35) dp2[i][j]=0;
dp2[0][a[pos]]=1;
rep(i,g[pos].size()) rep(j,32) if(dp2[i][j])
rep(k,32) if(dp[g[pos][i]][k]) dp2[i+1][j^k]=1,fr[i+1][j^k]=j;
if(to==0&&dp2[g[pos].size()][0]==0)
{
repn(i,31) if(dp2[g[pos].size()][i])
{
to=i;
ans.pb(pos);ans.pb(pos);
break;
}
}
else if(to==0) ans.pb(pos);
vector <int> nxts;
int cur=to;
for(int i=g[pos].size();i>0;--i)
{
int lstj=fr[i][cur],xx=lstj^cur;
nxts.pb(xx);
cur=lstj;
}
reverse(nxts.begin(),nxts.end());
rep(i,g[pos].size()) dfs2(g[pos][i],nxts[i]);
}
int main()
{
fileio();
cin>>n;
repn(i,n) scanf("%d",&a[i]);
int x;
for(int i=2;i<=n;++i)
{
scanf("%d",&x);
g[x].pb(i);
}
dfs(1);
if(dp[1][0]==0) puts("-1");
else
{
dfs2(1,0);
cout<<ans.size()<<endl;
for(int i=(int)(ans.size())-1;i>=0;--i) printf("%d ",ans[i]);
puts("");
}
termin();
}
