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;
}