一.闲话
最近准备省选，好久没写题解了qwq，今天的比赛挺有意思的，就来写几道题吧,qwq
二.题解
G.Mathematical Modelling Class
这道题只要读懂题其实挺简单的。但是貌似没几个人读然后被我这个菜鸡拿了一血（大雾）
题目大意：
有n个人，将每个人划分进A,B两组中的一组，第i个人划分进A组后，对A组的贡献为ai；划分进B组后，对B组的贡献为bi(ai,bi={0,1}),求是否存在一种方案，使得A组划分进了个人，B组划分进剩下的人，且A，B组的总贡献一样。若存在输出任意一种划分方式，若不存在输出-1。
读题后，我们发现，其实，一共只有四种人，即:
1.ai=0,bi=0
2.ai=0,bi=1
3.ai=1,bi=0
4.ai=1,bi=1
那么，我们只需要分别统计下这四种人分别有几个，再来看怎么划分，题目就会简单许多。
设第i种人有s[i]个,m=
那么，我们考虑枚举最终两组的总贡献，设为S。
那么，我们就有，对于A组的人来说,一定有:
A组中，第一种人的个数+第二种人的个数=m-S,第三种人的个数+第四种人的个数=S
这样，我们只需要找到一种方案数，使得A组满足上述条件，并且剩下的人对B组的贡献也等于S即可
那么，我们只要分别枚举下第一/二种人和第三/四种人的个数，就可以知道A组中所有类型的人的数量了，然后我们再判断下是否成立，就可以了。
但是，如果我们同时枚举第一/二种人和第三/四种人的个数的话，复杂度就会上升至,再加上一开始的枚举最终总贡献，复杂度就变成了
,显然不可行
那么，该怎么办呢？
一个简单的办法，我们参考折半搜索。先枚举第一/二种人的数量，然后记录下当前数量下第一/二种人对B组的总贡献，然后，我们再枚举第三/四种人的数量，算出当前数量下对B的总贡献，判断是否存在两个贡献和为S的情况即可。
复杂度
代码:
#include<bits/stdc++.h>
using namespace std;
const int N=5001;
bool dp[N];
int main(){
int T;
scanf("%d",&T);
while(T--){
int n,T=n,m;
scanf("%d",&n);
m=n/2+(n&1);
string x,y;
cin>>x>>y;
int one=0,two=0,thr=0,fou=0;
for(int i=0;i<n;++i){
if(x[i]=='0'&&y[i]=='0')++one;
if(x[i]=='0'&&y[i]=='1')++two;
if(x[i]=='1'&&y[i]=='0')++thr;
if(x[i]=='1'&&y[i]=='1')++fou;
}
int a=-1,b=-1,c=-1,d=-1;bool flag=0;
for(int i=0;i<=m;++i){//上午班学生1的个数
int l=m-i,r=i;//one和two一共选l个,thr和fou一共选r个
//两边分别枚举
memset(dp,0,sizeof(dp));
for(int j=min(l,one);~j;--j){//枚举选j个one
if(l-j>two)break;
dp[two-l+j]=1;
}
for(int j=min(r,thr);~j;--j){//枚举选j个thr
if(r-j>fou)break;
int T=i-(fou-r+j);
if(T>=0&&dp[T]){
flag=1;
c=j,d=r-j;b=two-T,a=l-b;
break;
}
}
if(flag)break;
}
if(!flag){
puts("-1");
continue;
}
for(int i=0;i<n;++i){
if(x[i]=='0'&&y[i]=='0'&&a){
--a;
printf("%d ",i+1);
}
if(x[i]=='0'&&y[i]=='1'&&b){
--b;
printf("%d ",i+1);
}
if(x[i]=='1'&&y[i]=='0'&&c){
--c;
printf("%d ",i+1);
}
if(x[i]=='1'&&y[i]=='1'&&d){
--d;
printf("%d ",i+1);
}
}
puts("");
}
return 0;
} L.Yet Another Bracket Sequence
注意到，一个括号匹配序列是否合法的充要条件是：
对于任意一个前缀，'('的个数大于等于')',且对于整体，'('的个数等于')'
那么，我们将题目变为维护每个前缀中'('的个数-')'的个数的值。
如果我们维护出来了，只有所有前缀中的值最小的那个>=0，且最后的前缀的值为0，那么这就是一个合法的括号匹配了。
如果我们把第x个括号改变了的话，那么，相当于把x-n的前缀的值+2/-2,那么，用线段树维护区间修改+区间最值即可。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
char ch[N];int W[N<<2],laz[N<<2];
int s[N];
inline void down(int now){
W[now<<1]+=laz[now],W[now<<1|1]+=laz[now];
laz[now<<1]+=laz[now],laz[now<<1|1]+=laz[now];
laz[now]=0;
}
inline void update(int now){
W[now]=min(W[now<<1],W[now<<1|1]);
}
inline void build(int now,int l,int r){
if(l==r){
W[now]=s[l];
return;
}
int mid=(l+r)>>1;
build(now<<1,l,mid),build(now<<1|1,mid+1,r);
update(now);
}
inline void insert(int now,int l,int r,int lc,int rc,int x){
if(lc<=l&&r<=rc){
W[now]+=x,laz[now]+=x;
return;
}
down(now);
int mid=(l+r)>>1;
if(lc<=mid)insert(now<<1,l,mid,lc,rc,x);
if(rc>mid)insert(now<<1|1,mid+1,r,lc,rc,x);
update(now);
}
inline int find(int now,int l,int r,int x){
if(l==r){
return W[now];
}
down(now);
int mid=(l+r)>>1;
if(x<=mid)return find(now<<1,l,mid,x);
return find(now<<1|1,mid+1,r,x);
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
scanf("%s",ch+1);
for(int i=1;i<=n;++i){
int val;
if(ch[i]=='(')val=1;
else val=-1;
s[i]=s[i-1]+val;
}
build(1,1,n);
while(m--){
int x;
scanf("%d",&x);
if(ch[x]=='('){
ch[x]=')';
insert(1,1,n,x,n,-2);
}else{
ch[x]='(';
insert(1,1,n,x,n,2);
}
if(W[1]==0&&find(1,1,n,n)==0){
puts("Yes");
}else{
puts("No");
}
}
return 0;
} M.Yet Another Stones Game
这题用SG函数推的。。。
n=2大家都会做就不多说了。
当n=4时，
我们假设有两个数，l=r，
那么，我们明显有如果我们拿这个点对(l,r)
当l=0时
sg(l,r)=0 [无法拿，必败]
当l=1时
sg(l,r)=1(算mex即可)
当l=2时
sg(l,r)=2
...
于是，我们有sg(l,r)=l
更一般的，对于操作点对(a1,a2...ak)我们不难得出
sg(a1,a2...ak)=min(a1,a2...ak)
那么，根据nim游戏的性质，因为每次我们取n/2个点，那么如果我们确定了取的n/2个点，整个游戏的sg值即为
有nim游戏的结论可知，若整个局面的sg值为0，则先手必败,否则先手必胜,那么我们只要判断下是否存在一种情况使得整个局面sg值不为0即可。
又因为两个部分的sg值是各个部分的最小值，所以，最佳的划分方法是，我们将最小的n/2的数划为一组，剩下的划为另一组，然后，我们判断他们的sg是否相等即可。
代码:
#include<bits/stdc++.h>
using namespace std;
int a[51];
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]);
}
sort(a+1,a+n+1);
if(a[n/2+1]!=a[1]){
puts("Happy Little Gyro");
}else{
puts("Sad Little Gyro");
}
}
return 0;
} 
京公网安备 11010502036488号