抽屉原理
在构造题中，若我们遇到了 \(n/k\) 这样的操作次数的时候，可以考虑将所有数划分为 \(k\) 个集合。这样，最小的那个集合的大小就一定小于等于 \(n/k\) 了。
CF1198C
给定一张有 \(3n\) 个点，\(m\) 条边的无向图。请找到一个大小为 \(n\) 的点独立集或边独立集。
\(n \leq 10^5,m \leq 5 \times 10^5\)
思路
维护一个点集和边集。初始时点集为全集，边集为空。
遍历 \(m\) 条边，若其两端点都在点集中，则将两点删去，并将边加入边集。
点集的大小设为 \(x\)，边集的大小设为 \(y\)，那么边集中的点数为 \(2y\)，且与点集中的点无交集。满足 \(x+2y=3n\)，那么根据抽屉原理，\(\min{x,y} \geq n\)。
code：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5e5+10;
int n,m,x,y,u[N],v[N],id[N];bool del[N];
void solve()
{
scanf("%d%d",&n,&m);x=3*n,y=0;for(int i=1;i<=3*n;i++) del[i]=false;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u[i],&v[i]);if(del[u[i]]||del[v[i]]) continue;
del[u[i]]=del[v[i]]=true;x-=2,id[++y]=i;
}
if(x>=n)
{
puts("IndSet");int cnt=0;
for(int i=1;i<=3*n&&cnt<n;i++) if(!del[i]) printf("%d ",i),cnt++;
puts("");
}
else
{
puts("Matching");
for(int i=1;i<=n;i++) printf("%d ",id[i]);
puts("");
}
}
int main()
{
int T;scanf("%d",&T);while(T--) solve();
return 0;
}
CF1534D
这是一道交互题。
目标：你需要求出一棵树的形态。
询问：一个数 \(x\)，然后将得到 \(n\) 个数表示各个点到 \(x\) 的距离。限 \(⌈n/2⌉\) 次。
思路
不难发现，一个点和与其距离为 \(1\) 的点相邻。考虑询问出所有相邻的点得到树的形态。
首先询问根节点，将其余所有的节点分为两类，一类到根节点距离为偶数，另一类到根节点距离为奇数。根据抽屉原理，这两类节点的最小值不超过 \(⌈n/2⌉\)。那么只需对较小的那类节点进行询问，将距离为 \(1\) 的点连边即可。
code：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=2023;
int n,x[N],y[N],u[N],v[N],d[N],tot,tx,ty;
int main()
{
cin>>n;cout<<"? 1"<<endl;fflush (stdout);
for(int a,i=1;i<=n;i++)
{
cin>>a;if(i==1) continue;d[i]=a;
if(a%2) x[++tx]=i;else y[++ty]=i;
}
if(tx>ty)
{
for(int i=2;i<=n;i++) if(d[i]==1) u[++tot]=1,v[tot]=i;
swap(x,y),swap(tx,ty);
}
for(int i=1;i<=tx;i++)
{
cout<<"? "<<x[i]<<endl;
fflush(stdout);
for(int j=1;j<=n;j++)
{
int a;cin>>a;
if(a==1) u[++tot]=x[i],v[tot]=j;
}
}
cout<<"!"<<endl;
for(int i=1;i<n;i++) cout<<u[i]<<" "<<v[i]<<endl;
return 0;
}
CF1450C
给定一张 \(n\) 行 \(n\) 列的棋盘，每个格子可能是空的或包含一个标志，标志有 \(\text{X}\) 和 \(\text{O}\) 两种。
如果有三个相同的标志排列在一行或一列上的三个连续的位置，则称这个棋盘是一个 胜局， 否则称其为 平局。
在一次操作中，你可以将一个 \(\text X\) 改成 \(\text O\)，或将一个 \(\text O\) 改成 \(\text X\)。
设棋盘中标志的总数为 \(k\)，你需要用不超过 \(\lfloor \frac{k}{3}\rfloor\) 次操作把给定的局面变成平局。
\(n \leq 300\)。
思路
注意到能够构成胜局的三个位置，它们的横纵坐标和模 \(3\) 的余数各不相同。考虑将所有格子依照模 \(3\) 的余数分为 \(3\) 类。
此时只需要保证其中两类格子互不相同，剩下一类格子不变，也就不会出现胜局了。根据这种思路，一共有 \(6\) 种修改方案。每一个包含标志的格子，更改其颜色的方案有两种，那么总的更改次数就是 \(2k\)。根据抽屉原理，其中最小的修改次数不超过 \(\lfloor \frac{k}{3}\rfloor\)。
code：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=310;
char a[N][N],s[N][N];int n,m;
bool check(char t[])
{
int cnt=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(t[(i+j)%3]=='O'&&s[i][j]=='X') cnt++,a[i][j]='O';
else if(t[(i+j)%3]=='X'&&s[i][j]=='O') cnt++,a[i][j]='X';
else a[i][j]=s[i][j];
}
return cnt<=m/3;
}
void print(){for(int i=1;i<=n;i++,puts("")) for(int j=1;j<=n;j++) putchar(a[i][j]);}
void solve()
{
scanf("%d",&n);m=0;for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) m+=(s[i][j]!='.');
if(check(".XO")) return print(),void();
if(check(".OX")) return print(),void();
if(check("X.O")) return print(),void();
if(check("O.X")) return print(),void();
if(check("XO.")) return print(),void();
if(check("OX.")) return print(),void();
}
int main()
{
int T;scanf("%d",&T);while(T--) solve();
return 0;
}
归纳法
考虑找到有解的充要条件，然后试图将原问题转为规模减一的一定有解的子问题。
CF1470D
给你一张图，你需要给一些点染色，要求：
1.一条边两端不能都染色了。
2.仅保留有一端染色了的边，图仍然连通。
判断是否有解，若是给出构造
思路
假设当前已经将一个大小为 \(k\) 的点集合法染色。考虑将点 \(i\) 加入到点集中。
如果点集中存在一个点 \(j\)，满足点 \(j\) 与点 \(i\) 有边直接相连，且点 \(j\) 被染色了，那么直接将点 \(i\) 加入点中，仍然合法；
若点集中不存在这样的点 \(j\)，那么将点 \(i\) 染色后加入点集中，仍然合法。
按照这样的步骤逐步扩大点集，如果原图联通，那么必定有解。
同时为了保证新枚举的点与点集中的点有边直接相连，可以按照 dfs 枚举图上的所有点。
code：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=3e5+10,M=6e5+10;
int h[N],tot,cnt,n,m,idx,q[N];bool vis[N],col[N];
struct edge{int v,nex;}e[M];
void add(int u,int v){e[++idx]=edge{v,h[u]};h[u]=idx;}
void dfs(int u)
{
vis[u]=true,cnt++;bool used=0;
for(int v,i=h[u];i;i=e[i].nex) if(vis[v=e[i].v]) used|=col[v];col[u]=used^1;tot+=col[u];
for(int v,i=h[u];i;i=e[i].nex) if(!vis[v=e[i].v]) dfs(v);
}
void solve()
{
scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) h[i]=col[i]=vis[i]=0;idx=tot=cnt=0;
for(int u,v,i=1;i<=m;i++) scanf("%d%d",&u,&v),add(u,v),add(v,u);dfs(1);
if(cnt<n) return puts("NO"),void();puts("YES");printf("%d\n",tot);
for(int i=1;i<=n;i++) if(col[i]) printf("%d ",i);puts("");
}
int main()
{
int T;scanf("%d",&T);while(T--) solve();
return 0;
}
CF1515F
给定一张图，点带权，初始为 \(
标签：10,int,++,构造,学习,vis,笔记,include,节点 From： https://www.cnblogs.com/ListenSnow/p/17138574.html