10.20

把最近的题都放到一天整理原因是只在想写这个的时候写/dk。

我咋这么菜，还是整理一下吧。

[WC2007] 剪刀石头布 && Beautiful League

题意

给定 \(n\)，你需要对一张 \(n\) 个点的完全图定向，其中有一些边需要按照给定方向定向，其余可以自行选择方向，求定向后得到有向图三元环数量最大值。

solution

竞赛图三元环个数等于 \(\binom{n}{3}-\sum\limits_{i=1}^{n} \binom{d_i}{2}\)，其中 \(d_i\) 表示点 \(i\) 的出度。

考虑给一个点 \(u\) 增加 \(1\) 的出度带来的代价：\(\binom{d_u+1}{2}-\binom{d_u}{2}=d_u\) ，相当于增加 \(d_u\) 的代价后 \(d_u\) 自增。

费用流，源点连向每条未定向边，容量为 \(1\)，边连向两端点，流入一个点代表这条边给这个点带来 \(1\) 的出度，每个点 \(i\) 向汇点连 \(n-d'_i\) 条边，每条边费用为 \(d'_i\sim n\)，容量为 \(1\)，其中 \(d'_i\) 为点 \(i\) 初始出度。

由于跑最小费用最大流，所以一定优先选择费用更小的边，就可以刻画出来最小代价了。

Code
#include
#include
#include
#include
using namespace std;
#define ll long long
#define qwq Ff472130
#define f(i,l,r) for (int i=l;i<=r;i++)
#define F(i,l,r) for (int i=l;i>=r;i--)
constexpr int N=100+10;
constexpr int inf=1e9+10;inline void read(int &x) {x=0;char ch=getchar();while (ch<48) ch=getchar(); while (ch>=48) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
}int n;
int E[N][N],id[N],d[N],ide[N][N];int s,t,cnt;
namespace Flow {constexpr int N=1e5+10;constexpr int M=1e6+10;constexpr int inf=1e9+10;int head[N],in[N],tot=1;struct Edge{int next,to,w,c;}e[M];inline void add(int u,int v,int w,int c) {e[++tot]={head[u],v,w,c};head[u]=tot;e[++tot]={head[v],u,0,-c};head[v]=tot;in[v]++;}int h[N],dis[N],del[N];bitset vis;struct Node {int id,val;inline bool operator <(const Node &x)const {return val>x.val;}};inline void topu() {queue q;f(i,1,cnt) h[i]=inf;h[s]=0;q.push(s);while (!q.empty()) {int now=q.front();q.pop();for (int i=head[now];i;i=e[i].next) {int v=e[i].to,w=e[i].w,c=e[i].c;if (!w) continue;h[v]=min(h[v],h[now]+c);in[v]--;if (!in[v]) q.push(v);}}}inline bool dij() {priority_queue q;f(i,1,cnt) dis[i]=inf;q.push({s,dis[s]=0});del[s]=head[s];while (!q.empty()) {int now=q.top().id;q.pop();if (vis[now]) continue;vis.set(now,1);for (int i=head[now];i;i=e[i].next) {int v=e[i].to,w=e[i].w,c=e[i].c+h[now]-h[v];if (!w||dis[v]<=dis[now]+c) continue;del[v]=head[v];q.push({v,dis[v]=dis[now]+c});}}f(i,1,cnt) vis.set(i,0);return dis[t]!=inf;}int maxflow,mincost;inline int dfs(int now,int sum) {if (now==t) return sum;int res=0;vis.set(now,1);for (int i=del[now];i&∑i=e[i].next) {del[now]=i;int v=e[i].to,w=e[i].w,c=e[i].c;if (!w||h[v]!=h[now]+c||vis[v]) continue;int k=dfs(v,min(sum,w));if (!k) dis[v]=inf;e[i].w-=k;e[i^1].w+=k;sum-=k;res+=k;mincost+=k*e[i].c;}vis.set(now,0);return res;}inline int ZKW() {topu();while (dij()) {f(i,1,cnt) if (dis[i]!=inf) h[i]+=dis[i];maxflow+=dfs(s,inf);}return mincost;}inline void solve() {f(i,1,n) f(j,i+1,n) {if (E[i][j]||E[j][i]) continue;int now=ide[i][j];for (int x=head[now];x;x=e[x].next) {if (e[x].w==0&&e[x].to==id[i]) E[i][j]=1;if (e[x].w==0&&e[x].to==id[j]) E[j][i]=1;}}}
}
using Flow::add;int main() {read(n);f(i,1,n) f(j,1,n) {int x;read(x);if (i==j) continue;if (x==1) E[i][j]=1,d[i]++;}s=++cnt;t=++cnt;f(i,1,n) {id[i]=++cnt;f(j,d[i],n) add(cnt,t,1,j);}f(i,1,n) f(j,i+1,n) {if (E[i][j]||E[j][i]) continue;ide[i][j]=++cnt;add(cnt,id[i],1,0);add(cnt,id[j],1,0);add(s,cnt,1,0);}Flow::ZKW();Flow::solve();int ans=0;f(i1,1,n) f(i2,i1+1,n) f(i3,i2+1,n) ans+=((E[i1][i2]&&E[i2][i3]&&E[i3][i1])||(E[i1][i3]&&E[i3][i2]&&E[i2][i1]));printf("%d\n",ans);f(i,1,n) {f(j,1,n) printf("%d ",E[i][j]);putchar(10);}return 0;
}

【XR-3】系统设计

solution

神秘哈希。。

考虑处理出根节点到每个点所需 \(a\) 数组的哈希值，于是对于询问 \((x,l,r)\) 等价于根节点走到 \(x\) 得到的 \(a\) 序列再拼上在区间中走的 \(a\) 序列，需要这个 \(a\) 序列的哈希值等于某个节点的哈希值。

直接线段树二分即可。

时间复杂度 \(O(n\log n)\)。

Code
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define ull unsigned long long
#define qwq Ff472130
#define f(i,l,r) for (int i=l;i<=r;i++)
#define F(i,l,r) for (int i=l;i>=r;i--)
const int N=5e5+10;
const int inf=1e9+10;
constexpr int Base=2e6-1;inline void read(int &x) {x=0;char ch=getchar();while (ch<48) ch=getchar(); while (ch>=48) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
}int n,m,q,rt;
int a[N];
vector e[N];mt19937_64 rnd(time(0));
struct My_Hash {inline ull operator ()(ull x)const {static ull s1=rnd(),s2=rnd(),s3=rnd();x+=s1;x=((x^(x>>33))*s2);x=((x^(x>>30))*s3);return x;}
};
ull pw[N],b[N];
__gnu_pbds::gp_hash_table mp;inline void dfs(int now,ull H) {mp[H]=now;b[now]=H;H*=Base;for (int i=0,sz=e[now].size();i>1;build(l,mid,ls(now));build(mid+1,r,rs(now));s[now]=s[ls(now)]*pw[siz[rs(now)]]+s[rs(now)];}inline void update(int x,int l,int r,int now,int k) {if (l==r) return s[now]=k,void();int mid=l+r>>1;if (x<=mid) update(x,l,mid,ls(now),k);else update(x,mid+1,r,rs(now),k);s[now]=s[ls(now)]*pw[siz[rs(now)]]+s[rs(now)];}inline int query(int x,int y,int l,int r,int now,ull &H) {if (x<=l&&y>=r) {ull nxt=(H*pw[siz[now]]+s[now]);if (mp.find(nxt)!=mp.end()) return H=nxt,1;if (l==r) return 0;int mid=l+r>>1;if (query(x,y,l,mid,ls(now),H)) return query(x,y,mid+1,r,rs(now),H);return 0;}int mid=l+r>>1;if (x>mid) return query(x,y,mid+1,r,rs(now),H);int ret=query(x,y,l,mid,ls(now),H);if (!ret) return 0;return (y>mid)?query(x,y,mid+1,r,rs(now),H):0;}
}tr;inline int query(int x,int l,int r) {if (e[x].size()

Hydra

solution

考虑令 \(f(k)\) 为进行 \(k\) 次操作 \(1\) 后的最小代价。

我一开始也以为 \(f\) 是单谷的，但它不是。。

考虑固定 \(k\) 如何求 \(f(k)\)，将所有 \(b\) 减去 \(k\)，从左向右扫，若一个位置 \(b>0\) 则用操作 \(2\) 将其解决，由于前面的位置可能带来一些贡献，所以只需要考虑前面的贡献后，将这里需要的贡献补齐即可。

令 \(t\) 为当前需要进行补齐的 \(b\) 的个数，那么显然有 \(f(k+1)-f(k)=x-t\times y\) 也就是增加一次操作 \(1\) 的贡献，在减少 \(t\) 次操作 \(2\) 的贡献。

\(t\) 变化对应的 \(x\) 只有 \(O(n)\) 种，考虑每种可能的 \(x\) 并排序，维护 \(t\) 的变化即可维护 \(f(x)\) 的变化。

时间复杂度 \(O(n\log n)\)。

Code
#include
#include
#include
using namespace std;
#define ll long long
#define qwq Ff472130
#define f(i,l,r) for (int i=l;i<=r;i++)
#define F(i,l,r) for (int i=l;i>=r;i--)
constexpr int N=2e6+10;
constexpr int inf=1e9+10;inline void read(int &x) {x=0;char ch=getchar();while (ch<48) ch=getchar(); while (ch>=48) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
}int n,X,Y,T;
int a[N],b[N],mp[N];
ll sum;int lst_k;
vector pb,pt;inline ll solve(int k) {sum-=1ll*(k-lst_k)*T;lst_k=k;while (!pb.empty()&&pb.back()<=k) pb.pop_back(),T--;while (!pt.empty()&&pt.back()<=k) pt.pop_back(),T++;return 1ll*X*k+sum*Y;
}inline void solve() {read(n);read(X);read(Y);T=0;sum=0;pb.clear();pt.clear();f(i,1,n) read(a[i]),read(b[i]);int lst=0,cnt=0,L=0;f(i,1,n) {mp[++L]=b[i];int now=lst-(a[i]-a[i-1]);if (now>=b[i]) {lst=now;continue;}if (now<=0) {cnt++;lst=b[i];sum+=b[i];pb.push_back(b[i]);T++;}else {sum+=b[i]-now;lst=b[i];mp[++L]=now;mp[++L]=now-1;pb.push_back(b[i]);pt.push_back(now);}}mp[++L]=0;sort(mp+1,mp+1+L);L=unique(mp+1,mp+1+L)-mp-1;sort(pb.begin(),pb.end(),[](int x,int y){return x>y;});sort(pt.begin(),pt.end(),[](int x,int y){return x>y;});ll ans=3e18;lst_k=0;f(i,1,L) ans=min(ans,solve(mp[i]));printf("%lld\n",ans);
}int main() {int T;read(T);while (T--) solve();return 0;
}

Gungnir Fracture

solution

捣鼓两个消失贪心结果还是要整个刻画出代价。。

考虑操作 \((m,k)\) 中 \(k\) 的最高位 \(1\)，它以下的所有位置是随意的，那么 \(m\) 在这些位上也都是随意的，需要 \(m\) 在这些位上任意一种碎片所需数量都不超过 \(1\)。

等价于放到一个字典树（或分治结构）上，有两种可能的情况：覆盖整个子树或不覆盖整个子树，在处理一个节点时，左边覆盖整个子树的操作可以和右边的任意一种操作搭配，右边同理，但是不覆盖整个子树的操作不能相互搭配。

令 \(F_u(t)\) 表示考虑 \(u\) 的子树，定义域 \([0,m]\)，\(m\) 为最多可以取出整个子树操作数，相当于子树内叶子节点 \(a\) 最小值，取出 \(t\) 个整个子树的操作后（这些操作在祖先节点被使用），其余操作在子树内任意搭配，其最小操作数，不难发现 \(F_u(t)\) 由一段斜率为 \(-1\) 的直线和一段平台构成（考虑 \(F_u(0)\)，取出一个整个子树操作，如果最优策略本身就有这样的操作则直接取出，代价减 \(1\)，否则取出两个拼起来，然后这两个对应不完整覆盖的操作分裂开来，代价均为 \(2\)）。

用 \((F_u(0),F_u(m),m)\) 来刻画一个 \(F_u\)。

考虑分治结构上合并两个 \(F\)，令左右子树分别为 \(L,R\)，\(f_L=F_L(0),f_R=F_R(0),g_L=F_L(m_L),g_R=F_R(m_R)\)，不难得到 \(F_u(t)=\max(F_L(t),F_R(t),g_L+g_R)\)（等价于左右不完全覆盖数量之和，左右两边取出后所得值）。

于是合并出 \(F_u(0),F_u(m)\) 向上传递即可。

时间复杂度 \(O(n)\)。

Code
#include
#include
using namespace std;
#define ll long long
#define qwq Ff472130
#define f(i,l,r) for (int i=l;i<=r;i++)
#define F(i,l,r) for (int i=l;i>=r;i--)
constexpr int N=(1<<19)+10;
constexpr int inf=1e9+10;inline void read(int &x) {x=0;char ch=getchar();while (ch<48) ch=getchar(); while (ch>=48) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
}int n,S;
int a[N];struct Node{ll f,g,m;};
inline Node solve(int l,int r) {if (l==r) return {a[l],0,a[l]};int mid=l+r>>1;Node L=solve(l,mid),R=solve(mid+1,r);ll m=min(L.m,R.m);return {max({L.f,R.f,L.g+R.g}),max({L.f-m,R.f-m,L.g+R.g}),m};
}inline void solve() {read(n);S=(1<

Tourist

题意

给定一张 \(n\) 阶竞赛图，求从每个点出发简单路径经过点数最大值并输出一条路径。

\(1\le n\le 2000\)。

solution

首先肯定需要拿出一个哈密瓜哈密顿路径，然后考虑所有与路径相反的边，形成若干强连通分量。

由于强连通竞赛图一定存在哈密顿回路，所以一个点最长路径就是它所在强连通分量以及在哈密顿路径后面的强连通分量的所有点，于是处理出每个强连通分量的一条哈密顿回路即可。

增量法，拿出一条哈密顿路径，假设我们已经得到了这个路径的前缀 \(1\sim x\) 的环，我们希望加入一些点。

初始环可以找到第一个连向哈密顿回路起点的点。

按照哈密顿路径顺序，考虑一个点 \(j\)，它连向了当前环某个点，令这个点为 \(t\)，那么我们可以得到环：\(t-1\rightarrow x+1\rightarrow x+2\rightarrow \dots \rightarrow j \rightarrow t \rightarrow t+1 \rightarrow \dots \rightarrow x \rightarrow 1\rightarrow 2\rightarrow \dots\rightarrow t-1\)，其中 \(t-1 \rightarrow x+1\) 是因为 \(j\) 是哈密顿路径上第一个连向环的点，所以它之前的点都被环上任意一点指向。

需要处理一些边界情况。

时间复杂度 \(O(n^2)\)。

Code
#include
#include
#include
#include
#include
using namespace std;
#define ll long long
#define qwq Ff472130
#define f(i,l,r) for (int i=l;i<=r;i++)
#define F(i,l,r) for (int i=l;i>=r;i--)
constexpr int N=2e3+10;
constexpr int inf=1e9+10;inline void read(int &x) {x=0;char ch=getchar();while (ch<48) ch=getchar(); while (ch>=48) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
}int n;
bitset e[N];int scc_idx,col[N],siz[N];
vector pt[N];int dfn[N],low[N],dfn_idx;
int st[N],vis[N],top;inline void tarjan(int now) {dfn[now]=low[now]=++dfn_idx;st[++top]=now;vis[now]=1;for (int v=e[now]._Find_first();v<=n;v=e[now]._Find_next(v)) {if (!dfn[v]) {tarjan(v);low[now]=min(low[now],low[v]);}else if (vis[v]) low[now]=min(low[now],dfn[v]);}if (dfn[now]==low[now]) {scc_idx++;for (int v=0;v!=now;) {v=st[top--];col[v]=scc_idx;vis[v]=0;pt[scc_idx].push_back(v);}}
}int dp[N],mp[N],t[N],nxt[N];
inline void topu() {f(i,1,scc_idx) {int x=pt[i].back();dp[i]++;static bitset vis;vis.reset();vis.set(i);f(j,1,n) if (e[x][j]&&!vis[col[j]]) dp[col[j]]++,vis.set(col[j]);}f(i,1,scc_idx) mp[dp[i]]=i,siz[i]=pt[i].size();
}inline void solve(int c) {if (siz[c]==1) return;vector p;for (int x:pt[c]) {int flag=0;if (p.empty()||e[x][p.front()]) p.insert(p.begin(),x),flag=1;for (int i=1,sz=p.size();i tmp;int cnt=id;f(i,0,id) tmp.push_back(p[i]);f(T,id+1,len) {int t=-1,x=p[T],hd=p[cnt+1];f(j,0,cnt) {int pre=(j?tmp[j-1]:tmp[cnt]);if (e[x][tmp[j]]&&e[pre][hd]) {t=j;break;}}if (t==-1) continue;vector tnxt;if (t==0) {f(j,0,cnt) tnxt.push_back(tmp[j]);f(j,cnt+1,T) tnxt.push_back(p[j]);}else {tnxt.push_back(tmp[t-1]);f(j,cnt+1,T) tnxt.push_back(p[j]);f(j,t,cnt) tnxt.push_back(tmp[j]);f(j,0,t-2) tnxt.push_back(tmp[j]);}cnt=tnxt.size()-1;tmp=tnxt;}f(i,1,cnt) nxt[tmp[i-1]]=tmp[i];nxt[tmp[cnt]]=tmp[0];
}vector vec;
inline void dfs(int now) {vec.push_back(now);int c=col[now];t[c]++;if (t[c]==siz[c]) {if (dp[c]==scc_idx) return;dfs(pt[mp[dp[c]+1]].back());}else dfs(nxt[now]);
}int main() {read(n);f(i,2,n) f(j,1,i-1) {int x;read(x);e[j].set(i,x);e[i].set(j,x^1);}f(i,1,n) if (!dfn[i]) tarjan(i);topu();f(i,1,scc_idx) solve(i);f(i,1,n) {vec.clear();f(j,1,scc_idx) t[j]=0;dfs(i);printf("%d ",(int)(vec.size()));for (int x:vec) printf("%d ",x);putchar(10);}return 0;
}

Graph Game

solution

神秘补图来了。这个结论根本不是人猜的。太难了/dk。

给出结论：\(\texttt{A}\) 获胜当且仅当补图连通，\(\texttt{B}\) 获胜当且仅当补图不连通。

我觉得这个结论很反人类，我一直在考虑图的直径直接寄了。

\(\texttt{A}\) 构造方式

首先搞出补图一棵生成树，然后进行 bfs，令当前 bfs 到节点为 \(v\)，其父亲为 \(u\)，那么考虑所有已经 bfs 过的节点，我们要处理掉这些节点与 \(v\) 之间的连边。

分成两组，一组颜色为 \(u\) 的颜色，一组不为 \(u\) 的颜色，先处理掉不为 \(u\) 颜色的点与 \(v\) 之间的连边，再处理其他有连边的节点。

这样做可以得到：若 bfs 过的节点有至少两种颜色，则处理完一个节点后仍然至少有两种颜色，因为 \(u\) 的颜色必然存在（\(u,v\) 无连边），且 \(u\) 的颜色不可能扩展到全局，那么归纳至 \(n=2\) 即可证明。

\(\texttt{B}\) 构造方式

随意回答询问，一直到询问一条边 \((u,v)\) 使得 \(u,v\) 在补图中不连通，钦定 \(u\) 的颜色需要扩展至全局，补图上由于 \(u\) 与 \(v\) 侧点在原图都存在一条边，\(v\) 与 \(u\) 侧点同理，都不连通则与 \(u,v\) 均有边，所以必然可以扩展至全局。

Code
#include
#include
#include
#include
#include
using namespace std;
#define ll long long
#define qwq Ff472130
#define f(i,l,r) for (int i=l;i<=r;i++)
#define F(i,l,r) for (int i=l;i>=r;i--)
constexpr int N=2e5+10;
constexpr int inf=1e9+10;inline void read(int &x) {scanf("%d",&x);}
inline void out(int x) {printf("%d\n",x);fflush(stdout);}int n,m;
int col[N],c[N];
struct Edge{int u,v;}es[N];
vector e[N],T[N],G[N];inline void clear() {f(i,1,n) {col[i]=c[i]=0;e[i].clear();T[i].clear();G[i].clear();}
}inline int get_c() {set s;f(i,1,n) s.insert(i);int cnt=0;static int did[N];while (!s.empty()) {int hd=(*s.begin());s.erase(s.begin());queue q;cnt++;q.push(hd);while (!q.empty()) {int u=q.front();q.pop();col[u]=cnt;vector tmp;for (int v:e[u]) did[v]=1;for (int x:s) if (!did[x]) tmp.push_back(x);for (int v:e[u]) did[v]=0;for (int x:tmp) {s.erase(x);q.push(x);T[u].push_back(x);T[x].push_back(u);}}}return cnt;
}inline void solve_A() {puts("A");fflush(stdout);queue q;static int vis[N];f(i,1,n) vis[i]=0;q.push(1);vis[1]=1;while (!q.empty()) {int u=q.front();q.pop();for (int v:T[u]) if (!vis[v]) {q.push(v);vis[v]=1;int d=c[u];vector v1,v2;for (int id:G[v]) {int x=(es[id].u^es[id].v^v);if (!vis[x]) continue;if (c[x]==d) v1.push_back(id);else v2.push_back(id);}for (int id:v2) {out(id);int x;read(x);int u=es[id].u,v=es[id].v;if (u==x) c[u]=c[v];else c[v]=c[u];}for (int id:v1) {out(id);int x;read(x);int u=es[id].u,v=es[id].v;if (u==x) c[u]=c[v];else c[v]=c[u];}}}
}inline void solve_B() {puts("B");fflush(stdout);int d=0;f(i,1,m) {int id;read(id);int u=es[id].u,v=es[id].v;if (col[u]!=col[v]&&!d) {d=c[v];out(u);c[u]=c[v];continue;}if (c[v]==d) out(u),c[u]=d;else out(v),c[v]=c[u];}
}inline void solve() {read(n);read(m);f(i,1,n) c[i]=i;f(i,1,m) {int u,v;read(u);read(v);es[i]={u,v};e[u].push_back(v);e[v].push_back(u);G[u].push_back(i);G[v].push_back(i);}if (get_c()==1) solve_A();else solve_B();int x;read(x);if (x==-1) exit(0);clear();
}int main() {int T;read(T);while (T--) solve();return 0;
}

Merging Vertices in a Graph

solution

Kotlin Hero。

除了初始时就不能操作的情况，连向所有点的点只可能是合并后产生的点。

特判掉初始时就不能操作的情况。

不难发现最大操作数一定为 \(n-1\)，因为产生连向所有点的 \((u,v)\) 对数至多有 \(n\) 对，而可选的 \((u,v)\) 有 \(\binom{n}{2}\) 对。

最小操作相当于找到一个点集 \(S\)，使得 \(S\) 内的所有点与 \(S\) 外所有点均有连边。

不难发现其实就是在求补图最小连通块。

这里给出一个求补图的方法：

  • 用 set 维护当前未被划分到任意一个补图的所有节点，set 空时算法结束；
  • 取出 set 内一个点，考虑补图上与其在同一连通块的点；
  • 维护一个队列表示需要扩展的点，初始时放入上一步取出的点；
  • 取出队首，令其为 \(u\)，标记原图所有与 \(u\) 有连边的点，然后遍历 set 内所有点，若这个点未被标记，则将其放入队列并移出 set，否则跳过；
  • 最终放入过队列的点即为补图的一个连通块。

显然一个点只会被放入队列一次，而遍历 set 时如果被标记则说明被原图上的一条边作用，而每条边至多作用 \(O(1)\) 次，所以这个算法复杂度是 \(O(n\log n+m)\) 的。

这个算法可以在过程中处理补图各种信息，如得到一棵生成树。

Code
#include
#include
#include
#include
#include
using namespace std;
#define ll long long
#define qwq Ff472130
#define f(i,l,r) for (int i=l;i<=r;i++)
#define F(i,l,r) for (int i=l;i>=r;i--)
constexpr int N=2e5+10;
constexpr int inf=1e9+10;inline void read(int &x) {x=0;char ch=getchar();while (ch<48) ch=getchar(); while (ch>=48) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
}int n,m;
int did[N];
vector e[N];int main() {read(n);read(m);f(i,1,m) {int u,v;read(u);read(v);e[u].push_back(v);e[v].push_back(u);}f(i,1,n) if (e[i].size()==n-1) return puts("0 0"),0;unordered_set s;f(i,1,n) s.insert(i);int ans=inf;while (!s.empty()) {int hd=(*s.begin());s.erase(s.begin());queue q;q.push(hd);int siz=1;while (!q.empty()) {int now=q.front();q.pop();for (int v:e[now]) did[v]=1;vector tmp;for (int v:s) if (!did[v]) tmp.push_back(v);for (int v:e[now]) did[v]=0;for (int x:tmp) s.erase(x),q.push(x),siz++;}ans=min(ans,siz);}printf("%d %d\n",ans-1,n-1);return 0;
}

Guess the Graph

solution

令 \(d\) 为 \(u\) 的度数，\(N\) 为 \(u\) 的邻域。

注意到对于一个不含 \(u\) 的集合 \(S\)，令 \(S\) 加入 \(u\) 后得到集合 \(T\)，则有 \(cut(T)-cut(S)=d-2\left\lvert S\cap N\right\rvert\)。

比较 \(cut(T)\) 与 \(cut(S)\) 等价于比较 \(d\) 于 \(2\left\lvert S\cap N\right\rvert\)，定义一个集合 \(S\) 的价值为 \(cut(T)-cut(S)\)。

于是二分出一个集合 \(P\) 使其权值恰好为 \(\left\lfloor \frac{d}{2} \right\rfloor\)，然后对于每个点尝试加入它至 \(P\) 内，根据得到的集合权值判定这个点是否在邻域内。

Code
#include
#include
#include
using namespace std;
#define ll long long
#define qwq Ff472130
#define f(i,l,r) for (int i=l;i<=r;i++)
#define F(i,l,r) for (int i=l;i>=r;i--)
constexpr int N=2e5+10;
constexpr int inf=1e9+10;int n,u;
int d1[N],d2[N];inline int ask() {printf("? ");f(i,1,n) putchar(d1[i]+'0');putchar(32);f(i,1,n) putchar(d2[i]+'0');putchar(10);fflush(stdout);static char op[3];scanf("%s",op);char ret=op[0];return ret=='<'?-1:(ret=='='?0:1);
}int main() {scanf("%d%d",&n,&u);int l=0,r=n-2,res=0,op=0;vector vec;f(i,1,n) if (i!=u) vec.push_back(i);while (l<=r) {int mid=l+r>>1;f(i,0,n-2) d1[vec[i]]=d2[vec[i]]=(i<=mid);d1[u]=1;d2[u]=0;int ret=ask();if (ret!=1) res=mid,op=ret,r=mid-1;else l=mid+1;}vector ans;f(c,0,n-2) {int x=vec[c];if (c<=res) {f(i,0,n-2) d1[vec[i]]=d2[vec[i]]=(i<=res);d1[u]=1;d2[u]=0;d1[x]=d2[x]=0;if (ask()!=op) ans.push_back(x);}else {if (op==-1) {f(i,0,n-2) d1[vec[i]]=d2[vec[i]]=(i<=res-1);d1[u]=1;d2[u]=0;d1[x]=d2[x]=1;if (ask()==op) ans.push_back(x);}else {f(i,0,n-2) d1[vec[i]]=d2[vec[i]]=(i<=res);d1[u]=1;d2[u]=0;d1[x]=d2[x]=1;if (ask()!=op) ans.push_back(x);}}}printf("! %d ",(int)ans.size());for (int x:ans) printf("%d ",x);putchar(10);fflush(stdout);return 0;
}

10.22

我居然能在 \(******\) 中通过 T2，真是不可思议。

T1 太简单了不想写，题面是模拟赛题面，与原题略有差异。

删除

solution

删除了多测并将 \(n\) 开大到 \(150\)。

首先不难发现最终不被删除的元素就是前缀最大值和后缀最大值。

对于位置 \(i\)，找到左边第一个大于它的位置 \(l\) 和右边第一个大于它的位置 \(r\)，那么位置 \(i\) 的删除时间 \(t_i\) 就是 \(\max(\max\limits_{j=l+1}^{i-1}t_j,\max\limits_{j=i+1}^{r-1}t_j)+1\)。

考虑令 \(f_{l,r,k}\) 表示若 \(l-1,r+1\) 都是前缀或后缀最大值且 \([l,r]\) 内无前缀最大值或后缀最大值时，\([l,r]\) 中最大值删除时间为 \(k\) 且符合给定删除时间的方案数，令 \(pre_i\) 表示 \(i\) 为一个前缀最大值时符合给定删除时间的方案数，\(suf_i\) 表示 \(i\) 为一个后缀最大值时符合给定删除时间的方案数，注意这里的定义是钦定了区间内是一个长度为区间长度的排列的，因为我们只关心其中大小关系，转移时使用组合数进行分配转移即可。

\(f\) 的转移就是枚举区间最大值所在位置，并要求左右区间最大时间小于 \(k\)，且至少有其中一个区间最大时间为 \(k-1\)，利用前缀和优化即可。

\(pre\) 和 \(suf\) 的转移只需要枚举上一个前后缀最大值所在位置，中间用 \(f\) 配合算出方案数，乘上分配区间的组合数即可。

时间复杂度 \(O(n^4)\)，空间复杂度 \(O(n^3)\)。

Code
#include
#include
using namespace std;
#define ll long long
#define qwq Ff472130
#define f(i,l,r) for (int i=l;i<=r;i++)
#define F(i,l,r) for (int i=l;i>=r;i--)
constexpr int N=150+10;
constexpr int inf=1e9+10;inline void read(int &x) {x=0;int f=1;char ch=getchar();while (ch<48) {if(ch=='-')f=-1;ch=getchar();} while (ch>=48) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();x*=f;
}constexpr int mod=1e9+7;
inline int ad(int x,int y) {return ((x+y>=mod)?(x+y-mod):(x+y));}
inline void add(int &x,int y) {x=ad(x,y);}int Tc[N][N];
inline ll C(int n,int m) {if (n<0||m<0||nn) break;f(k,2,len) {if (a[l]==-1||a[l]==k) add(f[l][r][k],f[l+1][r][k-1]);if (a[r]==-1||a[r]==k) add(f[l][r][k],f[l][r-1][k-1]);f(p,l+1,r-1) if (a[p]==-1||a[p]==k) {ll sum=0;sum+=1ll*f[l][p-1][k-1]*s[p+1][r][k-1]%mod;sum+=1ll*s[l][p-1][k-1]*f[p+1][r][k-1]%mod;sum-=1ll*f[l][p-1][k-1]*f[p+1][r][k-1]%mod;sum=(sum%mod+mod)%mod*C(len-1,p-l)%mod;add(f[l][r][k],sum);}}f(k,1,n) add(s[l][r][k]=s[l][r][k-1],f[l][r][k]);}g1[1]=g2[n]=1;f(i,2,n) {if (a[i]!=0&&a[i]!=-1) continue;ll sum=g1[i-1];f(j,1,i-2) {int len=i-j-1;sum+=1ll*g1[j]*C(i-2,len)%mod*s[j+1][i-1][len]%mod;}g1[i]=sum%mod;}F(i,n-1,1) {if (a[i]!=0&&a[i]!=-1) continue;ll sum=g2[i+1];f(j,i+2,n) {int len=j-i-1;sum+=1ll*g2[j]*C(n-i-1,len)%mod*s[i+1][j-1][len]%mod;}g2[i]=sum%mod;}ll ans=0;f(i,1,n) {if (a[i]!=0&&a[i]!=-1) continue;ans+=1ll*g1[i]*g2[i]%mod*C(n-1,i-1)%mod;}printf("%d\n",(int)(ans%mod));return 0;
}

故事

solution

最终答案相邻两个字符一定不同，并且手完一些基本的操作可以发现限制主要来自形如 \(1010101\) 的串。

一个特别关键的性质是：将其划分为若干段极长的形如 \(1010101\) 的串，要求两端是 \(1\) 且相邻两个位置不同，每次操作等价于从相邻两个不同的极长串中消掉一个 \(1\)。

令 \(1\) 的总数为 \(S\)，最长的串中有 \(M\) 个 \(1\)，那么最终剩余 \(1\) 的数量最少是 \(\max(S\bmod 2,2M-S)\)，下界和构造都是显然的。

于是考虑一下两端能否保留 \(1\) 即可，保留的 \(1\) 一定是初始时就有的，所以只需要判断删去第一个位置或最后一个位置后得到的串剩余 \(1\) 最少个数是否与原串最少剩余个数减去删去 \(1\) 位置个数相等即可。

时间复杂度线性，空间复杂度 \(O(1)\)。

Code
#include
#include
using namespace std;
#define ll long long
#define qwq Ff472130
#define f(i,l,r) for (int i=l;i<=r;i++)
#define F(i,l,r) for (int i=l;i>=r;i--)struct Node{int sum,mx,len,lst;};
inline int D(Node x) {int sum=x.sum,mx=x.mx;return max(sum&1,(mx<<1)-sum);
}inline void push_back(char c,Node &x) {int sum=x.sum,mx=x.mx,len=x.len,lst=x.lst;int d=c-'0';if (d==lst) len=0;sum+=d;len+=d;mx=max(mx,len);lst=d;x={sum,mx,len,lst};
}inline void solve() {char ch=getchar();if (ch==10) ch=getchar();Node tmp1={0,0,0,0},tmp2={0,0,0,0};int flag1=(ch=='1');push_back(ch,tmp1);ll ans=1,T=1;while ((ch=getchar())!=10) {int flag2=(ch=='1'),num=0;T++;Node tmp3=tmp1,tmp4=tmp2;push_back(ch,tmp3);push_back(ch,tmp4);if (flag1&&(D(tmp3)-1==D(tmp4))) num=1;if (flag2&&(D(tmp3)-1==D(tmp1))) num=1;if (flag1&&flag2&&(D(tmp3)-2==D(tmp2))) num=2;ans^=T*max(1,D(tmp3)*2+1-num);tmp1=tmp3;tmp2=tmp4;}printf("%lld\n",ans);
}int main() {int T;scanf("%d",&T);while (T--) solve();return 0;
}