Div2 T1

不就是把(0)设成(1)，把(1)设成(-1)，然后求最大非空字段和。

最大字段和的做法上网查吧。

非空特判就行了。

#include<cstdio>
#include<cstring>
#define  N  110000
using  namespace  std;
char  st[N];
int  f[N],n;
int  main()
{
	scanf("%s",st+1);n=strlen(st+1);
	int  sum=0,ans=0;bool  bk=0;
	for(int  i=1;i<=n;i++)f[i]=(st[i]=='0'?1:-1);
	for(int  i=1;i<=n;i++)
	{
		if(f[i]==1)bk=1;
		sum+=f[i];
		if(sum>ans)ans=sum;
		if(sum<0)sum=0;
	}
	if(bk==0)ans=-1;//特判
	printf("%d
",ans);
	return  0;
}

Div2 T2

这道题目乍一看很难，但是仔细一看，环的异或和都是(0)，那么意味着什么呢：

我们设(a) (xor) (b=0)，(a=)~(b)，所以(ans) (xor) (a)(=)~((ans) (xor) ~ (a)=)~((ans) (xor) (b))

所以我们只要固定一个根(1)，用(BFS)算出每个点的(dis_{i})，然后对于(l,r)，只要取(dis_l) (xor) (dis_{r})和他的取反值的最大值就行了。

#include<cstdio>
#include<cstring>
#define  N  110000
#define  NN  410000
using  namespace  std;
struct  node
{
	int  y,c,next;
}tr[NN];int  len,last[N];
inline  void  ins(int  x,int  y,int  c){len++;tr[len].y=y;tr[len].c=c;tr[len].next=last[x];last[x]=len;}
int  a[N],n,m,q;bool  v[N];
int  list[N],head,tail;
int  main()
{
	scanf("%d%d%d",&n,&m,&q);
	for(int  i=1;i<=m;i++)
	{
		int  x,y,c;scanf("%d%d%d",&x,&y,&c);
		ins(x,y,c);ins(y,x,c);
	}
	v[1]=1;a[1]=0;list[++tail]=1;
	while(head<=tail)
	{
		int  x=list[head++];
		for(int  k=last[x];k;k=tr[k].next)
		{
			int  y=tr[k].y;
			if(!v[y])
			{
				v[y]=1;
				list[++tail]=y;
				a[y]=a[x]^tr[k].c;
			}
		}
	}
	for(int  i=1;i<=q;i++)
	{
		int  x,y;scanf("%d%d",&x,&y);
		printf("%d
",a[x]^a[y]);
	}
	return  0;
}

Div1 T1

这道题目当时想到了正解，但是做题太少否定了QAQ。

我们定一个数组(b)，表示先手取到这个数字的输赢状态，(1)表示必赢，(0)表示必输。

首先对于(l,r)，我们观察(r)，如果(a[r]\%2==1)，那么很明显先到(r)的会赢，那么(b[r]=1)，反之为(0)。

而对于一个数字(b[i]=1)，那么很明显(b[i-m])~(b[i-1])都是(0)。（因为后手可以取这个，然后赢掉）。

而对于(b[i+1])~(b[i+m])都是(0)的位置(i)而言，如果他的数字为偶数的话，那么先手取他也肯定是先手取后面的(0)，所以是(0)，反之（奇数）为(1)，然后重复此操作。

然后(b[l])就是答案。

但是这样是(O(frac{n^2}{m}))的，很明显的爆炸。

那么我们分析一下做法。

就是对于一个数字(1)，前面(m)个数字都是(0)，然后(m)个之前的第一个奇数就是(1)。

对于一个位置(i)，他的(m)个之前的第一个奇数是固定的。

所以我们对于位置(i)，可以向前面的那个奇数连一条边，那么就是如果(a[l])是偶数的话那么肯定无解，而(a[l])是奇数的话，就看(l)的子树内有没有(r)，这个我们可以记录每个数字的(DFS)序以及子树(DFS)区间，然后(O(1))查询。

顺便提一下，由于没有一个统一的根，所以我们设一个根，连向那些森林的跟，也就向从数列第一个奇数开始的后面(m-1)减一范围内的奇数都连一条边。

口胡无代码。

时间复杂度：(O(n))

Div1 T2

这道题目我们要明白一个惯用的套路，就是我们很难处理负数的情况，我们就要通过加(k)操作把每个数字的活动区间变成([0,2k])，而(a_i'=a_i+i*k)。（下面的题解皆按照这个条件。）

讲真这样子化简这道题目就真的是道纯纯粹粹的SB题了。

很明显对于(a_{i}>a_{j}(i<j))，由于我们加的数字是自然数，所以肯定如果前面到了(a_j+1)，后面就肯定倒不回去了。

所以我们设(a_i=a_j)，也就是维护(a)数组递增，每个(a_i)等于后面的(a)的最小值。

然后我们发现这道题目是很明显的贪心，我们先化化式子QMQ。

设(b_{i})是第(i)次加的数字

(sumlimits_{i=1}^{n}sumlimits_{j=i}^{n}b_{i}w_{j})

然后我们设(c_{i}=sumlimits_{j=i}^{n}w_{j})（其实就是把后效性消除了）。

那么式子就化成了(sumlimits_{i=1}^{n}b_{i}w_{i})，那么对于大的(w)，我们就可以给他分(2k)个。

但是我们又意识到了还有(a)的限制，所以对于(w_{i})加的数字，我们需要在([i,n])一起减去（对于第(i)个位置初始值为(a_{i})），同时每次要给(i)加数字的时候，我们设([i,n])的最小值为(x)，那么就是(min(x,2k))。

支持这种操作的数据结构就是我们可爱的线段树啦！！！！

时间复杂度：(O(nlogn))

Div1 T3&T4

不会