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