正题
A. Balanced Bitstring
这样来考虑:当前区间k合法,那么要往右移一位依然合法,那么必须要保证加进来的位置=弹出去的位置,也就是说对于i,我们判断一下输入的式子是否满足这样的性质就可以了,如果一个相等集合内只有问号,那么我们就待定它,最后看一下01个数是否都没有超过k/2即可.
#include
using namespace std;
const int N=300010;
char s[N];
int T,n,k;
int main(){
scanf("%d",&T);
while(T--){
scanf("%d %d",&n,&k);
scanf("%s",s+1);
bool tf=true;
for(int i=1;i
B. Tree Tag
比赛的时候想的并不是很清楚,以Alice为根建树,首先如果da*2>=db,那么肯定是Alice赢,因为它可以走到一个刚好距离Bob db的位置,然后Bob往外跳一定是输.考虑da*22*da,如果没有这样的直径,那么输出Alice,因为只要Alice站在直径的中心点,下一步肯定可以抓到Bob.如果有这样的直径,而且Alice第一步抓不到Bob,那么我们先让Bob往子树里最深的点跳,知道跳不动,如果Alice下一步可以抓到Bob,那么Bob就往外跳,可以分类讨论Bob初始点是否为直径端点,来证明Bob一定可以跳到一个Alice抓不到的地方,然后让bob反复横跳就可以了.
#include
using namespace std;
const int N=100010;
struct edge{
int y,nex;
}s[Nmx) mx=dep,p=x;
if(x==b) op=dep;
for(int i=first[x];i!=0;i=s[i].nex) if(s[i].y!=fa) dfs(s[i].y,x,dep+1);
}
void ga(int x,int fa,int dep){
if(dep>mx) mx=dep,q=x;
for(int i=first[x];i!=0;i=s[i].nex) if(s[i].y!=fa) ga(s[i].y,x,dep+1);
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d %d %d %d %d",&n,&a,&b,&da,&db);
for(int i=1;i=db){printf("Alicen");continue;}
dfs(a,0,0);
if(op2*da?"Bobn":"Alicen");
}
}
C. Fixed Point Removal
考虑一次怎么做,d[i]表示[1,i]被删除的个数,如果i,否则.可以发现,考虑y=0的情况,我们发现对于i,可以使i产生贡献的是一个前缀,那么我们要找到这个前缀最右是多少,定义ans[i]为当x=mid的个数>=b[i],那么mid就是可行的ans,将二分放到线段树上即可.
发现询问只要满足x
#include
using namespace std;
const int N=300010;
int n,q;
int a[N],rt[N],ans[N];
vector V[N];
int t[N
D. Game of Pairs
首先n为偶数很simple.前n个中间划一刀,后n个中间划一刀,两两连边就可以,可以证明无论怎么取%n!=0
其次是n为奇数,首先要证明一个东西,如果选出一些数mod 2n=n,那么可以转化为mod 2n=0,因为总和mod2n = n,所以每个pair选另外一个就可以满足.
我们考虑构造一种方案使得%n下选出的是1到n,一个pair两个中只能选一个,%n同余的两个数只能选一个,那么就有2n个点2n条边,且每个点度数为2,两条边的种类不同,所以必定形成了多个简单偶数环,在这些偶数环中,我们只要隔一个选一个出来就可以/
#include
using namespace std;
const int N=1000010;
int n;
int b[N];
pair a[N];
struct edge{
int y,nex;
}s[N0){
printf("Firstn");fflush(stdout);
for(int i=1;i
E. Bricks
赛后看到就识别原题了.
直接考虑网络流,S连到i表示割掉这条边 i选横着,i连到T表示割掉这条边 i选竖着,流量为o,o是一个足够大的数,对于两个横着相邻的点,我们先加上他们的贡献(也就是-1),然后在网络流里面新建一个点,将两个点连向它流量为inf,这个点连向汇点,表示如果有一个点选了竖着,那么这两点的贡献就不算数,要减去他们的贡献,也就是加上1,最后答案就是dinic()-点数*o+贡献.
实验证明不连o也是可以的,因为连o主要是为了保证两边不会同时被割,但是一个点要么属于S集要么属于T集,两边不可能同时被割,然后这个本质上就是其他题解的最大独立集?
#include
using namespace std;
const int N=120010;
int n,m;
struct edge{
int y,nex,c;
}s[N*8];
char ch[210][210];
bool tf[210][210];
int first[N],head[N],len=1,tot,bg,ed,op,d[N],o;
int fx[4]={-1,1,0,0};
int fy[4]={0,0,-1,1};
queue q;
void ins(int x,int y,int c){
s[++len]=(edge){y,first[x],c};first[x]=len;
s[++len]=(edge){x,first[y],0};first[y]=len;
}
int pos(int x,int y){
return (x-1)*m+y;
}
bool bfs(){
memset(d,0,sizeof(d));d[bg]=1;
q.push(bg);
for(int i=1;i
总结
这次比赛只做了前三题,因为第三题想到一半,后面都想错了,最后5分钟才发现可以直接看前面ans[i]来二分,所以后面两题看都没看,以后要吸取经验,想清楚点,t4赛后一个半小时莽出来了,t5也是赛后才看到题发现是原题,但网络流最小割的思想也有待复习.
本文由 @鲁小强 发布于 职涯宝 ,未经作者许可,禁止转载,欢迎您分享文章