Petrozavodsk Summer-2017. Moscow IPT Contest.

复盘人：rxd

开场我看了G，稍微想了下不太会。
gt告诉我J是个签到题，于是我写了。

0h23min：J(+0)。

我想了会儿K，不太会。
gt告诉我G直接欧拉回路上就行了。
于是我去抄了个欧拉回路板子过了。n=2没特判WA了一发。

1h18min：G(+1)。

然后以为K会了，写到一半发现是错的。写了个打表观察了下，又写了个O(n^2)暴力观察了下。
gt说了下I的题意，我会了。写完炸内存了。把外层线段树换成树状数组还是炸内存了。于是把两个long long的哈希换成一个long long就过了。
期间B也大家都不会。

2h10min：I(+2)。

又罗干了半天，我发现K直接考虑最后一列就可以了，5分钟写了下就过了。

3h14min：K(+0)。

又罗干了半天，我发现B直接拿个Trie把1并到0上求个min就行了，10分钟写了下就过了。

3h48min：B(+0)。

期间gt罗干出了一点H，于是他上机打表找规律，我干了下D。
想了会儿发现D是个傻逼题，和gt检查了一下以后开写。写到差不多最后。最后的时候发现负的时候可能要特判，先交了一发WA了，特判以后过了。

4h51min：D(+1)。

A：

B：相当于对每个前缀\(S_i\)，求\(S_j+(S_i~xor~S_j)\)的最大值。如果\(S_i\)某位是1，则答案一定是1，如果是0要优先选1+1。考虑Trie套线段树维护位置集合，把1的子树合并到0上面然后贪心走一下就行了。然后发现不用线段树，只要维护个最小下标就可以了。复杂度\(O(n \log n)\)。

C：

D：设执行s后的位移量是w，如果w=0，那我们除了平移之外啥都干不了，直接KMP下看看是否和目标串一样。否则我们改一个i就相当于同时改i和i+w。这样的话只要所有%w同余类都有偶数个1就行。而考虑执行完s时所有%w同余类的1的个数，把这个串和目标串所有同余类1的个数KMP一下得到t的位移。然后从最左到最右（w负的时候是最右到最左）贪心消一下就可以了。复杂度\(O(n)\)。

E：

F：考虑k,2k,3k-1,3k四种情况,分10种情况讨论所有的答案.3k-1的时候是无解的.

G：注意到n是偶数，那么所有2*i和2*i+1的入边都是一样的，出边可能不同。把它们缩起来，这样就变成了n/2个点，n条边的有向图，求个欧拉回路，从0（1）出发走到0（0）就可以了。

#include<bits/stdc++.h>

#define For(i,x,y) for (int i=x;i<y;i++)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define lf else if

#define dprintf(...) fprintf(stderr,__VA_ARGS__)
using namespace std;

typedef long long ll;
typedef double db;
typedef pair<int,int> PII;
typedef vector<int> VI;

int IN(){
	int c,f,x;
	while (!isdigit(c=getchar())&&c!='-');c=='-'?(f=1,x=0):(f=0,x=c-'0');
	while (isdigit(c=getchar())) x=(x<<1)+(x<<3)+c-'0';return !f?x:-x;
}

const int N=10000+19;

struct Edge{
	int x,y,nxt;
} E[N*2];
int las[N],stk[N],ans[N];
int n,cnt,top;

void Add_Edge(int x,int y){
	E[cnt]=(Edge){x,y,las[x]};las[x]=cnt++;
}
void dfs(int x){
	for (int i=las[x];~i;i=las[x]){
		las[x]=E[i].nxt;
		dfs(E[i].y);
		stk[++top]=i;
	}
}

int main(){
	memset(las,-1,sizeof(las));
	n=IN();
	if (n==2){
		puts("10");
		return 0;
	}
	For(i,0,n){
		Add_Edge(i/2,(2*i)%n/2);
	}
	dfs(0);
	for (int i=top;i;i--){
		int x=E[stk[i]].x,y=E[stk[i]].y;
		if (2*(2*x)%n/2==y) ans[++*ans]=2*x;else ans[++*ans]=2*x+1;
	}
	For(i,1,*ans+1){
		printf("%d",(ans[i-1]*2%n)==ans[i]?0:1);
	}
	puts("");
}

H：考虑每次操作,可以理解为是先把所有格子都变成0,然后再做行列操作.那么第一轮操作过后,可以调整行列顺序使得其变为对角形式,后面通过分类讨论可以得出合法性以及之后需要的操作次数.

I：权值树状数组套线段树，给每个数随一个long long范围内的数，假装异或=0\(\Leftrightarrow\)没有出现奇数次的数。\(O(q \log^2 n)\)。

J：两个序列求最长上升子序列加起来。

K：问题可以转化成n-(k-m)个数选m个时最后一列的答案。直接考虑最后一列有贡献的情况，可能是\((i,i+1)\)，这样方案数是\(\binom{i-1}{n-1}\)，也可能是\((n,i)\)，这样方案数是\(\binom{i-2}{n-2}\)。复杂度\(O(n)\)。