20230902 B 组模拟赛 题解
前言
我是超级大傻逼。
前排提示：这篇题解里面的语言可能会有点抽象，因为我爆大零，现在很烦躁。
T1
很有趣又好玩还有意思还很好而且很适合放在 T1 并且思路清晰条理清楚的诈骗题。
首先可以自己手动模拟一下小数据，发现无论如何 Alice 都能获胜。
然后就可以猜结论了：所有情况均为 Alice 获胜。
恭喜你，获得一百分。
考虑证明结论（或者构造方案）。
首先，假设数列不动，是一个指针在动（其实是等价的，但这样更好理解）。
如果全是 $0$，Alice 直接就获胜了，所以我们只考虑有 $1$ 的情况。
那么容易发现，假如数列中有且仅有一段连续的 $1$，那么在这一段 $1$ 之前 Bob 不得不翻转一个 $0$，不然 Alice 直接就赢了。
那么 Alice 可以每次只留第一段 $1$，把后面的全变成 $0$，这样下一轮 Bob 就不得不在这一段 $1$ 之前放一个 $1$。
容易发现假如把数列看成一个二进制数，那么每两轮这个数必定增加一定值。最终到达全 $1$ 状态。
但全 $1$ 状态 Alice 就可以一波全翻转直接获胜了。
所以所有 $2^n$ 种情况均为 Alice 获胜。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1e5+5,inf=0x3f3f3f3f,mod=998244353;
int n;
int ksm(int a,int b){
int c=1;
while(b){
if(b&1) c=1ll*a*c%mod;
a=1ll*a*a%mod;
b>>=1;
}
return c;
}
signed main(){
n=read();
printf("%d\n",ksm(2,n));
}
T2
考虑建图。
具体来说，把每个数当成一个结点，然后把每张扑克牌当成一条边，每条边表示“在每条边的两个端点里选其中一个”，那么容易发现，建出来的图是若干个连通块，而一个连通块假如不是树，那么必然每个点都能选（因为边数大于等于点数，而每条边都有一个名额），反之，如果是树，那么整个连通块中有一个点是选不了的。容易发现这个点取树中的最大值或最小值是必定不劣的。
那么把每棵树的最大最小值对 $(x,y)$ 单独存起来，就成了一个区间覆盖问题，假如询问区间 $[l,r]$ 包含了任何一对 $(x,y)$（即 $l\le x < y \le r$），那么答案就是 No，反之就是 Yes。
做法有很多，再次略过了，最优能做到线性。
参考代码（非最优）
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1e5+5,inf=0x3f3f3f3f;
int n,m,q;
vector<int> e[N];
int vis[N];
vector<pii> tr;
struct Node{
int l,r,pos;
bool operator <(const Node &p)const{return l<p.l;}
}que[N];
bool ans[N];
multiset<int> sr;
pii dfs(int x,int fa){
vis[x]=1;
pii res=mkp(x,x);
for(auto i:e[x]){
if(i==fa) continue;
if(vis[i]){
res=mkp(-1,-1);
continue;
}
pii cc=dfs(i,x);
if(res.fi!=-1){
res.fi=min(res.fi,cc.fi);
res.se=max(res.se,cc.se);
}
}
return res;
}
signed main(){
n=read();m=read();
forup(i,1,m){
int a=read(),b=read();
e[a].push_back(b);
e[b].push_back(a);
}
forup(i,1,n){
if(!vis[i]){
pii res=dfs(i,0);
// forup(i,1,n){
// printf("%d ",vis[i]);
// }
// puts("");
// printf("%d %d\n",res.fi,res.se);
if(res.fi!=-1){
tr.push_back(res);
sr.insert(res.se);
}
}
}
q=read();
forup(i,1,q){
que[i].l=read();que[i].r=read();
que[i].pos=i;
}
sort(tr.begin(),tr.end());
sort(que+1,que+q+1);
int l=0;
forup(i,1,q){
while(l<(int)tr.size()&&tr[l].fi<que[i].l){
sr.erase(sr.find(tr[l].se));
++l;
}
if(sr.empty()||*sr.begin()>que[i].r){
ans[que[i].pos]=true;
}else{
ans[que[i].pos]=false;
}
}
forup(i,1,q){
puts(ans[i]?"Yes":"No");
}
}
T3
四元环计数变种。
首先考虑类似于 Meet In Middle 的做法，现枚举一个点 $u$，然后找所有由 $u$ 出发的长度为 $2$ 的路径，然后假如两条路径终点相同就统计答案，因为每个环会被统计四次所以最后除以 $4$，复杂度上界大概是 $O(n^2)$。
考虑优化，发现每个环会被统计四次很不好，那么我们将点按边权从大到小排序，然后统计一个点删一个点，这样就不会重复了。假如你把这份代码交上去，恭喜你，通过此题。
乂？刚刚不是只优化了常数吗，为什么能 $n$ 方过十万。
因为其实这个上界过于松了，考虑算一个更紧的上界，用类似整除分块的思路。
具体来说，设点 $i$ 的度数为 $d_i$，考虑分 $d_i>\sqrt{m}$ 和 $d_i \le \sqrt{m}$ 考虑。
首先每个点计算次数就是 $d_i^2$（这个显然吧？考虑每个点作为路径中间点会被 $d_i$ 个起点访问，然后访问 $d_i$ 个终点）
对于 $d_i\le\sqrt{m}$，显然有 $\sum d_i\le 2m$（因为只有 $m$ 条边，一条边提供 $2$ 的度数），那么 $\sum d_i^2\le\left(\sum d_i\right)\max\begin{Bmatrix}d_i\end{Bmatrix}\le 2m\sqrt{m}$，就是 $O(m\sqrt{m})$ 级别的。
然后对于 $d_i>\sqrt{m}$，由于同样有 $\sum d_i\le 2m$，所以这样的点至多有 $\sqrt{m}$ 个，然后考虑一条路径 $a\to b \to c$ 中，假如这样的店作为 $b$，那么 $c$ 的度数显然也大于 $\sqrt{m}$，所以也属于这样的点，至多有 $\sqrt{m}$ 个，然后边 $b\to c$ 至多有 $2m$ 条，对应 $\sqrt{m}$ 个点 $c$，复杂度也是 $O(m\sqrt{m})$。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1e5+5,mod=1e9+7;
int n,m,a[N],ans,vis[N],rh[N],ct[N];
vector<int> e[N];
int seq[N];
bool cmp(int a,int b){
return e[a].size()>e[b].size();
}
signed main(){
n=read();m=read();
forup(i,1,n){
a[i]=read();
seq[i]=i;
}
forup(i,1,m){
int u=read(),v=read();
e[u].push_back(v);
e[v].push_back(u);
}
sort(seq+1,seq+n+1,cmp);
forup(i,1,n){
int u=seq[i];
vis[u]=1;
for(auto x:e[u]){
if(vis[x]) continue;
for(auto y:e[x]){
if(vis[y]) continue;
if(ct[y]!=0){
(ans+=(rh[y]+1ll*a[x]*ct[y]%mod)%mod)%=mod;
(ans+=1ll*(a[u]+a[y])*ct[y]%mod)%=mod;
}
(rh[y]+=a[x])%=mod;ct[y]++;
}
}
for(auto x:e[u]){
if(vis[x]) continue;
for(auto y:e[x]){
if(vis[y]) continue;
rh[y]=ct[y]=0;
}
}
}
printf("%d\n",ans);
}