Ric_shooter
Table_bottom

Petrozavodsk Summer-2017. Moscow IPT Contest.

Remilia posted @ 2019年3月16日 19:16 in 涂字 , 48 阅读

ABCDEFGHIJK


复盘人: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)\)。


 

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter