CF1521

C:Nastia and a Hidden Permutation

一个比较容易想的策略是，先找到 \(1\)，然后一个个求出剩下的。

如果询问 \(t=2,x=1\)，回答就是 \(min(max(1,p_i),max(2,p_j))\)。如果回答 \(≤2\)，可以断言 \(p_i,p_j\) 里面必然有 \(1\) 或 \(2\)。如果是 \(1\)，那就有 \(p_i=1\)；否则 \(i,j\) 交换再询问，如果回答是 \(1\)，那么 \(p_j=1\)。

到这里，我们找到 \(1\) 的位置 \(pos[1]\)。接下来只要询问 \(t=1,j=pos[1],x=n−1\)，所得到的值就是 \(p_i\)。

#include <bits/stdc++.h>
#define repeat(i,a,b) for(int i=(a),ib=(b);i<ib;i++)
#define repeat_back(i,a,b) for(int i=(b)-1,ib=(a);i>=ib;i--)
using namespace std;
typedef long long ll;
ll read(){ll x; if(scanf("%lld",&x)!=1)exit(0); return x;}
void print(ll x,bool e=0){printf("%lld%c",x," \n"[e]);}
const int N=200010;
int query(int t,int i,int j,int x){
	printf("? %d %d %d %d\n",t,i,j,x);
	fflush(stdout);
	return read();
}
int p,ans[N];
void find1(int x,int y){
	int t=query(2,x,y,1);
	if(t==1)p=x;
	else if(t==2){
		if(query(2,y,x,1)==1)
			p=y;
	}
}
void Solve(){
	int n=read();
	for(int i=1;i<=n;i+=2){
		find1(i,i%n+1);
	}
	repeat(i,1,n+1)if(i!=p){
		ans[i]=query(1,p,i,n-1);
	}
	ans[p]=1;
	printf("!");
	repeat(i,1,n+1)printf(" %d",ans[i]);
	puts("");
	fflush(stdout);
}
signed main(){;
	int T=1; T=read();
	repeat(ca,1,T+1){
		Solve();
	}
	return 0;
}

D:CF1521D Nastia Plays with a Tree

问题转化为链剖分，使得链的总长度最长,只是输出方案比较麻烦。

直接把每个点对应的那条链存了下来，然后直接拼接。复杂度 \(O(n)\) 。实现的时候用了 \(sort\) 图方便,因此可能会慢一点，但也能过

#include <bits/stdc++.h>
using namespace std;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long int_;
inline int readint(){
	int a = 0; char c = getchar(), f = 1;
	for(; c<'0'||c>'9'; c=getchar())
		if(c == '-') f = -f;
	for(; '0'<=c&&c<='9'; c=getchar())
		a = (a<<3)+(a<<1)+(c^48);
	return a*f;
}

const int MaxN = 100005;
vector<int> G[MaxN];

int dp[MaxN][2]; // 1:have a endpoint  0:whatever
int pre[MaxN][2], endpos[MaxN][2];

int id[MaxN];
bool cmp(const int &a,const int &b){
	return dp[a][1]-dp[a][0] > dp[b][1]-dp[b][0];
}

void dfs(int x,int fa){
	for(int y : G[x])
		if(y != fa)
			dfs(y,x);
	
	int tot = dp[x][1] = 0;
	for(int y : G[x])
		if(y != fa){
			dp[x][1] += dp[y][0];
			id[++ tot] = y;
		}
	
	if(tot == 0){ // leaf
		endpos[x][0] = x; // itself
		endpos[x][1] = x; // single
		dp[x][0] = dp[x][1] = 0;
		pre[x][0] = pre[x][1] = 0;
		return ; // nothing to do
	}
	
	sort(id+1,id+tot+1,cmp);
	id[tot+1] = 0; // if tot == 1
	memcpy(pre[x],id+1,2<<2);
	endpos[x][0] = endpos[id[1]][0];
	endpos[x][1] = endpos[id[2]][0];

	dp[x][1] += dp[id[1]][1]+1-dp[id[1]][0];
	dp[x][0] = dp[x][1]+dp[id[2]][1]+1-dp[id[2]][0];

	if(tot == 1) dp[x][0] = -1; // invalid
	if(dp[x][0] < dp[x][1]){
		dp[x][0] = dp[x][1];
		endpos[x][1] = x; // my self
	}
}

/** L for father, R for son */
void output(int x,int d,int fa,int &L,int &R){
	if(d == 1) pre[x][1] = 0; // useless
	for(int y : G[x])
		if(y != fa && y != pre[x][0] && y != pre[x][1]){
			output(y,0,x,endpos[y][0],endpos[y][1]);
			printf("%d %d %d %d\n",x,y,R,endpos[y][0]);
			R = endpos[y][1]; // joined
		}
	if(pre[x][0]) output(pre[x][0],1,x,L,R);
	if(pre[x][1]) output(pre[x][1],1,x,L,R);
}

int main(){
	for(int T=readint(); T; --T){
		int n = readint();
		rep(i,1,n) G[i].clear();
		rep(i,1,n-1){
			int a = readint();
			int b = readint();
			G[a].push_back(b);
			G[b].push_back(a);
		}
		dfs(1,0);
		printf("%d\n",n-1-dp[1][0]);
		output(1,0,0,endpos[1][0],endpos[1][1]);
	}
	return 0;
}

E:CF1521E Nastia and a Beautiful Matrix

显然是构造题，首先考虑绝对下界，也就是空格最少的情况。

一个空格能够让哪些位置为左上角的 \(2×2\) 子矩形满足条件一呢？显然就是以它为右下角的 \(2×2\) 矩形。那么这些矩形两两不重叠的时候，显然是空格数量最小的时候。手玩可以发现，将 \(( 2 k 1 , 2 k 2 )\)的格子（行和列均从 \(1\) 开始标号）都设置为空格就可以了。

我们只要证明，在这种情形下，所有格子都可以使用，那就可以直接找这个下界。而这是很简单的——首先，将图二染色，使得主对角线（包含所有 \((x,x)\) 的格子）是黑色。称 “左上-右下” 和 “左下-右上” 为相邻关系。不难发现，黑色格子没有任何相邻关系，因为已经被空格隔开了。

白格呢？将图旋转一下，发现是一个类棋盘（上下左右连边）。将这个类棋盘再二染色一次，得到红色和绿色，不难发现，红色格子不相邻，绿色格子不相邻。那么，一种数字要是只在红色、绿色中的某一个出现，它就不会导致矩阵不合法。

这是两个背包吗？假设一个背包爆了，另一个背包直接硬塞，百分百有解啊！或者更 “构造” 一点：按照顺序填 \(Red,Black,Green\) ,由于 \(|Red|=|Green|\)，所以只要 \(\max cnt\le|Red|+|Black|\)，然后按照 \(cnt\) 从大到小填。（其实只要把 \(cnt\) 最大的一个特殊填就行了。

#include <bits/stdc++.h>
using namespace std;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long int_;
inline int readint(){
	int a = 0; char c = getchar(), f = 1;
	for(; c<'0'||c>'9'; c=getchar())
		if(c == '-') f = -f;
	for(; '0'<=c&&c<='9'; c=getchar())
		a = (a<<3)+(a<<1)+(c^48);
	return a*f;
}

const int MaxN = 100005;
const int SqrtN = 500;
/*
black = (n*n+1)>>1
blank = (n>>1)*(n>>1)
free = black - blank
red = (n>>1)*((n+1)>>1)
*/
struct Node{
	int cnt, val;
	bool operator < (const Node &t) const {
		return cnt > t.cnt;
	}
};
Node num[MaxN];
int maze[SqrtN][SqrtN];

int main(){
	for(int T=readint(); T; --T){
		int m = readint(), k = readint();
		rep(i,1,k){
			num[i].cnt = readint();
			num[i].val = i;
		}
		sort(num+1,num+k+1); int n = 1;
		while(n*n-(n>>1)*(n>>1) < m) ++ n;
		while((n>>1)*((n+1)>>1) // red
			+(n*n+1)/2 // black
			-(n>>1)*(n>>1) < num[1].cnt)
				++ n; // increase
		/* step one: tackle one num */ ;
		for(int i=2; i<=n; i+=2)
		for(int j=1; j<=n&&num[1].cnt; j+=2)
			maze[i][j] = num[1].val, -- num[1].cnt;
		for(int i=1; i<=n; i+=2)
		for(int j=1; j<=n&&num[1].cnt; j+=2)
			maze[i][j] = num[1].val, -- num[1].cnt;
		/* step two: fill in all num */ ;
		int p = 2; // which num is dealt with
		for(int i=2; i<=n; i+=2)
		for(int j=1; j<=n&&p<=k; j+=2){
			if(maze[i][j]) continue;
			for(; !num[p].cnt; ++p)
				if(p == k+1) break;
			if(p != k+1){
				maze[i][j] = num[p].val;
				-- num[p].cnt;
			}
		}
		for(int i=1; i<=n; i+=2)
		for(int j=1; j<=n&&p<=k; j+=2){
			if(maze[i][j]) continue;
			for(; !num[p].cnt; ++p)
				if(p == k+1) break;
			if(p != k+1){
				maze[i][j] = num[p].val;
				-- num[p].cnt;
			}
		}
		for(int i=1; i<=n; i+=2)
		for(int j=2; j<=n&&p<=k; j+=2){
			for(; !num[p].cnt; ++p)
				if(p == k+1) break;
			if(p != k+1){
				maze[i][j] = num[p].val;
				-- num[p].cnt;
			}
		}
		printf("%d\n",n);
		/* step three: output */ ;
		for(int i=1; i<=n; ++i,puts(""))
		for(int j=1; j<=n; ++j){
			printf("%d ",maze[i][j]);
			maze[i][j] = 0; // clear
		}
	}

	return 0;
}