火车站（station）
分析
将有交集的线段合并，会得到一些无交的区间，若存在某个区间包括 \(x\)，输出所有小于 \(x\) 的左端点和大于 \(x\) 的右端点即可。
Code
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=2e5+10,inf=1e9;
int n,m,K;
struct node{
int l,r;
}seg[N];
bool cmp(node x,node y){
return x.l==y.l?x.r<y.r:x.l<y.l;
}
vector<pii>ans;
signed main(){
#ifdef luoshen
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#else
// freopen("1.out","w",stdout);
#endif
read(n),read(m),read(K);
for(int i=1;i<=m;i++){
read(seg[i].l),read(seg[i].r);
}
sort(seg+1,seg+m+1,cmp);
seg[m+1].l=inf;
bool flag=0;
for(int i=1,j;i<=m;i=j+1){
vector<pii>().swap(ans);
ans.pb(mp(seg[i].l,0));
ans.pb(mp(seg[i].r,1));
j=i;
int r=seg[i].r;
while(j<=m&&seg[j+1].l<=r){
j++;
ans.pb(mp(seg[j].l,0));
ans.pb(mp(seg[j].r,1));
r=max(r,seg[j].r);
}
if(seg[i].l<=K&&r>=K){
flag=1;
break;
}
}
if(!flag){
return 0;
}
sort(ans.begin(),ans.end());
int tot=unique(ans.begin(),ans.end())-ans.begin();
for(int i=0;i<tot;i++){
if(ans[i].second==1&&ans[i].first>K){
write_space(ans[i].first);
}
if(ans[i].second==0&&ans[i].first<K){
write_space(ans[i].first);
}
}
putchar('\n');
// cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
return 0;
}
城市建造（cities）
简明题意
询问有多少点集 \(V\)，使得在原图中删去 \(V\) 的导出子图后，形成了 \(|V|\) 个连通块，且连通块大小的极差不超过 \(k\)。
分析
既然去掉 \(V\) 的导出子图后会形成 \(|V|\) 个连通块，显然 \(V\) 的导出子图必然连通，即选出的点必须连通。若不连通，则必然存在两点在同一联通块内的情况，可以自己画几张图看看。这是个特别重要的性质，后面会反复用到。
根据简明题意，我们很容易想到点双上面。有一个性质，一个点双上点，要么不选，要么只选一个，要么全选，这个性质很容易证明。
对于全选，若某点双中存在 \(p_1,p_2,p_3\) 三点，若选择 \(p_1,p_2\)，不选 \(p_3\)，那么去掉 \(p_1,p_2\) 间的边后，根据点双的定义，一定能找到一条路径使得从 \(p_1\) 出发，经过 \(p_3\)，到达 \(p_2\)。
对于只选一个点的点双，那么选出来的这个点一定是割点，因为只有割点才与其它的点双有连边，因为选出的点要连通。既然被选出的点一定是割点，那么它一定会存在于另一个点双中，且这个点双一定被全选，因为选出的点要连通。那么这个性质就变成了：一个点双要么不选，要么全选。
和点双有关，求连通块计数，想到一个叫做圆方树的东西。建出原图的圆方树，一个点双要么选，要么不选就转化为了一个方点要么选要么不选，又因为选出的点要连通，所以选出的方点必然是连通的，此处方点连通的定义为若方点 \(u,v\) 均被选择，则 \(u\) 到 \(v\) 的路径上不得出现未被选择的方点。
终于能够保证前半部分题目的任务完成了，那么题意就转化为了询问有多少个方点集合 \(S\)，使得 \(S\) 中的点相连通且在圆方树上删去 \(S\) 中的点后，树上的每个连通块中圆点数量的极差不超过 \(k\)。
首先想想，有没有必选的点，肯定是有的。令圆点 \(siz=1\)，方点 \(siz=0\)，令带权重心为一个方点，那么圆方树带权重心必然被选。
考虑反证法，若该点不选，那么包含重心的连通块中圆点数量必然大于 \(n/2\)，不包含的连通块中圆点数量必然小于 \(n/2\)，不符合题意，所以必然包括该方点。
任选一个与带权重心相连的点为根，求出每个点的 \(siz\)。
先做 \(k=0\)。枚举连通块大小 \(x\)，对于方点 \(u\)，若 \(siz_u<x\) 或 \(siz_u=x\text{且}deg_u\not=2\)，则 \(u\not\in S\)，否则 \(u\in x\)。对于上面满足上述两个条件之一的方点 \(u\)，若 \(u\in S\)，则必然会产生圆点数小于 \(x\) 的连通块；对于均不满足的方点 \(u\)，若 \(u\not\in S\)，则必然产生圆点数大于 \(x\) 的连通块。感性理解一下，当 \(k=0\) 时，每个 \(x\) 最多只有一种方案。
再考虑 \(k=1\)。这里可以用一个容斥，枚举 \(x\)，统计出所有块内圆点数 \(sz\in\{x,x+1\}\) 的方案数，再去掉大小全为 \(x+1\) 的方案数，此时我们就已经得到了块内圆点数的最小值为 \(x\) 的方案数，求和即可。如何求块内圆点数 \(sz\in \{x,x+1\}\) 的方案数，类似于求 \(k=0\) 的方案数，唯一不同的是对于 \(deg_u=2\) 的方点的处理。若 \(fa_u\) 有 \(deg_v\not=2\text{或}siz_v\not= x\) 的儿子 \(v\)，那么 \(u\in S\)。否则 \(fa_u\) 所有儿子中有且只有一个儿子可以不选。
以上所有过程可以用一个桶统计有哪些点的 \(siz=x\)，用一个并查集维护每个点所在连通块的大小和每个大小连通块的数量。在枚举过程中，对于一个已经不满足所有可能选的条件的方点，将其所有的相邻的点合并，这些点在块内圆点数量增多时，必然还在一个连通块内，所以直接合并。此时可以算出块内圆点数全为 \(x\) 的方案数，若 \(cnt_x\times x=n\) 为 \(1\)，否则为 \(0\)。接下来处理 \(deg_u=2\) 的点，因为已经有过合并操作，不会对方案数造成贡献的 \(fa_u\)，它会被合并过。所以统计每一个 \(fa_u\) 有多少 \(deg_v=2\) 的儿子，记这个数字为 \(sum_x\)，只有当 \(fa_u\) 还未被合并过，才会进行合并，形成一个内有 \(x+1\) 个圆点的连通块，令这些 \(fa_u\) 的集合为 \(s\)。如果 \(cnt_x\times x+cnt_{x+1}\times (x+1)=n\)，方案数为 \(\prod\limits_{y\in s}(sum_y+\left[x=1\right])\)，因为当 \(x=1\) 时，可以选择不合并。
Code
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=2e5+10,inf=1e9+10,mod=998244353;
int n,m,k,dfn[N],low[N],idx,stk[N],tot,top;
int siz[N],mx[N],rt,fa[N],ans[N],Ans[N],sum[N];
vector<int>e[N],G[N],buc[N];
bool vis[N];
namespace dsu{
int fa[N],siz[N],cnt[N];
void init(){
for(int i=1;i<=n;i++){
fa[i]=i;
siz[i]=1;
}
cnt[1]=n;
}
int getfa(int u){
if(fa[u]!=u){
fa[u]=getfa(fa[u]);
}
return fa[u];
}
void merge(int u,int v){
u=getfa(u),v=getfa(v);
--cnt[siz[u]];
--cnt[siz[v]];
fa[u]=v;
siz[v]+=siz[u];
++cnt[siz[v]];
}
void debug(){
for(int i=1;i<=n;i++){
cerr<<cnt[i]<<' ';
}
cerr<<endl;
}
}
void tarjan(int u){
dfn[u]=low[u]=++idx;
stk[++top]=u;
for(auto v:e[u]){
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
if(low[v]==dfn[u]){
tot++;
G[tot].pb(u);
G[u].pb(tot);
while(1){
int x=stk[top--];
G[x].pb(tot);
G[tot].pb(x);
if(x==v){
break;
}
}
}
}
else{
low[u]=min(low[u],dfn[v]);
}
}
}
void get_rt(int u,int father){
if(u<=n){
siz[u]=1;
}
for(auto v:G[u]){
if(v==father){
continue;
}
get_rt(v,u);
mx[u]=max(mx[u],siz[v]);
siz[u]+=siz[v];
}
mx[u]=max(mx[u],n-siz[u]);
if(u>n&&mx[u]<mx[rt]){
rt=u;
}
}
void dfs(int u,int father){
if(u<=n){
siz[u]=1;
}
else{
siz[u]=0;
}
fa[u]=father;
for(auto v:G[u]){
if(v==father){
continue;
}
dfs(v,u);
siz[u]+=siz[v];
}
if(u>n){
buc[siz[u]].pb(u);
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
read(n),read(m),read(k);
tot=n;
for(int u,v,i=1;i<=m;i++){
read(u),read(v);
e[u].pb(v);
e[v].pb(u);
}
tarjan(1);
mx[0]=inf;
get_rt(1,0);
if(rt>n){
rt=G[rt][0];
}
dfs(rt,0);
dsu::init();
for(int i=1;i<n;i++){
for(auto x:buc[i]){
if(G[x].size()>2){
for(int j=1;j<G[x].size();j++){
dsu::merge(G[x][j-1],G[x][j]);
}
}
}
if(dsu::cnt[i]*i==n){
ans[i]=1;
}
vector<int>s;
for(auto x:buc[i]){
if(G[x].size()==2){
if(dsu::siz[dsu::getfa(fa[x])]==1){
vis[x]=vis[fa[x]]=1;
s.pb(fa[x]);
dsu::merge(fa[x],G[x][G[x][0]==fa[x]]);
sum[fa[x]]=1;
}
else if(vis[fa[x]]){
++sum[fa[x]];
}
}
}
if(dsu::cnt[i]*i+dsu::cnt[i+1]*(i+1)==n){
Ans[i]=1;
for(auto x:s){
Ans[i]=1ll*Ans[i]*(sum[x]+(i==1))%mod;
}
}
for(auto x:buc[i]){
if(G[x].size()==2&&!vis[x]){
dsu::merge(G[x][0],G[x][1]);
}
}
}
if(!k){
int res=0;
for(int i=1;i<n;i++){
res+=ans[i];
}
write_endl(res);
}
else{
int res=mod-1;
for(int i=1;i<n;i++){
res=(res+Ans[i])%mod;
}
for(int i=2;i<n;i++){
res=(res-ans[i]+mod)%mod;
}
write_endl(res);
}
return 0;
}
过河卒（zu）
分析
记录两个红棋的位置，黑棋的位置，当前这步谁走，可以发现不重复的状态总共不会超过 \(2\times 10^6\) 种，每个状态最多会有 \(11\) 种后继状态，并不是太多，所以可以连一条从状态 \(x\) 到它的后继 \(y\) 的边。这就变成了一张有向图，只需要跑有向图博弈论即可。
对于有向图博弈论，一个状态的后继中只要有必败态，该状态就是必胜态；一个状态的后继如果全是必胜态，该状态就是必败态。可以建反图，跑拓扑，得到每个状态的结果。如果起始态为必胜态则红赢；如果起始态为必败态则黑赢；如果都不是则为平局。求步数也非常简单，因为拓扑用到了队列，队列前面的点肯定步数小于后面的点，所以每个点可以用状态转移来的那个点的步数转移得到步数，转移后将点丢入队列中，这样就可以得到在满足两个人的博弈策略的同时的最小步数。
但这是不够的，因为算一下可以发现转移边数有 \(T\times 11\times 2e6\) 条，如果都跑很容易超时。可以发现一件事，开始说的是记录两个红棋的位置，因为两颗棋子本质相同，所以可以令第一颗棋子不在第二颗棋子下方，这样状态数直接砍一半，边数自然也就减少了
Code
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
const int N=11;
const int MX=2e6+10;
int idx,id[N][N][N][N][N][N][2],dx[4]={0,-1,0,1},dy[4]={1,0,-1,0},n,m,st;
string ch[N];
struct point{
int x,y;
}str[2],stb;
inline bool chk(int x,int y,int xx,int yy,int X,int Y){
if(x<1||x>n||y<1||y>m){
return 0;
}
if(xx<1||xx>n||yy<1||yy>m){
return 0;
}
if(X<1||X>n||Y<1||Y>m){
return 0;
}
if(ch[x][y]=='#'||ch[xx][yy]=='#'||ch[X][Y]=='#'){
return 0;
}
if(x==xx&&y==yy){
return 0;
}
return 1;
}
int tot,head[MX],deg[MX],type[MX],step[MX];
struct edge{
int v,nxt;
}e[MX<<3];
inline void clear(){
for(int i=1;i<=idx;i++){
deg[i]=head[i]=type[i]=step[i]=0;
}
idx=tot=0;
}
inline void add(int u,int v){
e[++tot].v=v;
e[tot].nxt=head[u];
head[u]=tot;
deg[v]++;
}
inline void topo(){
queue<int>q;
for(int i=1;i<=idx;i++){
if(type[i]!=0){
q.push(i);
}
}
while(!q.empty()){
int u=q.front();
q.pop();
if(u==st){
return;
}
if(type[u]==-1){
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(!type[v]){
type[v]=1;
step[v]=step[u]+1;
q.push(v);
}
}
}
else if(type[u]==1){
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(!type[v]){
deg[v]--;
if(!deg[v]){
type[v]=-1;
step[v]=step[u]+1;
q.push(v);
}
}
}
}
}
}
inline int get_id(int x,int y,int xx,int yy,int X,int Y,int opt){
if(x<xx){
return id[x][y][xx][yy][X][Y][opt];
}
return id[xx][yy][x][y][X][Y][opt];
}
inline void solve(){
str[0].x=str[0].y=str[1].x=str[1].y=stb.x=stb.y=0;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>ch[i];
ch[i]=' '+ch[i];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
while(ch[i][j]!='.'&&ch[i][j]!='#'&&ch[i][j]!='O'&&ch[i][j]!='X'){
ch[i][j]=getchar();
}
if(ch[i][j]=='O'){
if(str[0].x==0&&str[0].y==0){
str[0].x=i,str[0].y=j;
}
else{
str[1].x=i,str[1].y=j;
}
}
else if(ch[i][j]=='X'){
stb.x=i,stb.y=j;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int i1=i;i1<=n;i1++){
for(int j1=1;j1<=m;j1++){
for(int i2=1;i2<=n;i2++){
for(int j2=1;j2<=m;j2++){
if(!chk(i,j,i1,j1,i2,j2)){
continue;
}
id[i][j][i1][j1][i2][j2][0]=++idx;
id[i][j][i1][j1][i2][j2][1]=++idx;
}
}
}
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int i1=i;i1<=n;i1++){
for(int j1=1;j1<=m;j1++){
for(int i2=1;i2<=n;i2++){
for(int j2=1;j2<=m;j2++){
if(!chk(i,j,i1,j1,i2,j2)){
continue;
}
int cur=get_id(i,j,i1,j1,i2,j2,0);
for(int k=0;k<4;k++){
int x,y;
x=i+dx[k],y=j+dy[k];
if(chk(x,y,i1,j1,i2,j2)){
add(get_id(x,y,i1,j1,i2,j2,1),cur);
}
x=i1+dx[k],y=j1+dy[k];
if(chk(i,j,x,y,i2,j2)){
add(get_id(i,j,x,y,i2,j2,1),cur);
}
}
for(int k=0;k<3;k++){
int x,y;
x=i2+dx[k],y=j2+dy[k];
if(chk(i,j,i1,j1,x,y)){
add(get_id(i,j,i1,j1,x,y,0),cur+1);
}
}
if(i2==1){
type[cur]=-1,type[cur+1]=1;
}
else if((i==i2&&j==j2)||(i1==i2&&j1==j2)){
type[cur]=type[cur+1]=-1;
}
else{
if(deg[cur]==0){
type[cur]=-1;
}
if(deg[cur+1]==0){
type[cur+1]=-1;
}
}
}
}
}
}
}
}
st=id[str[0].x][str[0].y][str[1].x][str[1].y][stb.x][stb.y][0];
topo();
if(type[st]==0){
cout<<"Tie"<<'\n';
}
else if(type[st]==1){
cout<<"Red "<<step[st]<<'\n';
}
else{
cout<<"Black "<<step[st]<<'\n';
}
clear();
return;
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int opt,t;
cin>>opt>>t;
while(t--){
solve();
}
return 0;
}
