20230706
T1.骰子游戏（dice）
题目大意
给你两个正整数 \(n\) 和 \(d\)，你需要构造 \(n\) 组数据，每组6个整数
满足整数都在 \([0, 10^6]\) 范围内，每组数据中两两不同，
在每组数据中分别随机选一个数所得到的异或和为\(d\)的倍数
如果能构造出这样的 \(n\) 组数据，请先输出 ‘Yes’，随后输出你的构造。
如果无法构造出这样的 \(n\) 组数据，请输出 ‘No’。
\(1 \le n \le 100 ,2 \le d \le 60\)
考场思路
由于花在T2的时间过多，所以这道题也就没有什么时间的
发现\(d\)很小，我也尝试着去把它转化成了二进制
同时我也拿\((5)_ {10}=(101)_ 2\) 进行了举例
发现\(101101\)是5的倍数，就想着把\(d\)向左移动几位
到目前为止的想法还是正确的
但是我慌了，于是与正确的做法擦肩而过
心里还惦记着没调出来的T2
等我回来再思考时就换了一种想法
只打了个暴力，还打错了QAQ
Solution
考虑到\(d\)很小，不超过60
我们把\(d\)转化成二进制，就只有6位
而每个数不超过\(10^6\)，转化成二进制有20位
我们考虑如何构造\(d\)的倍数
发现把\(d\)进行左移后得到的都是它的倍数
如果我们把它左移6位，与其异或就还是会得到\(d\)的倍数
就顺着这个思路想下去
我们的目的是构造6个数使得它们不管怎么异或都会得到\(d\)的倍数
这样我们每一个骰子都用这6个数即可
说得更简洁一点
我们可以把它们转化到64位进制去构造
使得每一位都是\(0\)或\(d\)即可
这样一个骰子的六个面分别是\(0,d,64d,65d,4096d,4097d\)
就是要保证对于前面两位都相同是
第三位一个是0一个是\(d\)
这样\(d\)就不会被异或掉
代码就很简单了（伤害性不大，侮辱性极强）
#include <bits/stdc++.h>
using namespace std;
int n,d;
int main(){
freopen("dice.in","r",stdin);
freopen("dice.out","w",stdout);
scanf("%d%d",&n,&d);
printf("Yes\n");
for(int i=1;i<=n;i++)
printf("0 %d %d %d %d %d\n",d,d*64,d*65,d*4096,d*4097);
return 0;
}
T2.裁剪彩带（cut）
题目大意
长度为\(n\)的序列，把它分割成若干部分
每一部分的美丽值为这个区间的mex
整个序列的美丽度为区间美丽值之和
求最大的美丽度
\(1 \le n \le 5* 10^5,0 \le a_i \le 20\)
考场思路
可能是因为这段时间数据结构写得太多了，尤其是线段树
于是乎，看到mex就想到用主席树去维护
然后再想到一个dp去完成
在发现了\(a_i \le 20\)时依旧很固执地去用主席树维护mex
然后写了一个dp
\(dp[i]=max_{0 \le j \lt i}{dp[j]+query(j+1,i)}\)
然后开始考虑如何优化dp
我先推了个斜率优化（我的脑洞真大……草稿纸写了整整一页）
发现好像是每个数只会被淘汰一次
用单调队列来维护
于是又写了一个自以为很正确的代码
发现过不了大一点的样例，答案错误
于是乎，我开始写暴力
\(n^2\)的dp与前面的代码进行对拍
终于发现哪里不太对了——
\(query(j+1,i)\)不一定单调
所以说我错了
前前后后一共用了两个小时
最后还是用了暴力的代码
结果——MLE（我笑了）
（有一种可能是我写了inline，用空间换时间，再也不写了。。。）
这个经历告诉我们：
不要死磕一道题，其他题说不定更能突破！
Solution
山重水复疑无路，柳暗花明又一村。
有些时候啊
要学会换一种方式来思考问题
好久没打模拟赛，这种思维方式都要忘了
想到dp是没有问题的
我的想法是枚举\(j\)去找每一个\(query(j+1,i)\)
可是发现\(1 \le a_i \le 20\)
mex最大也才21呀
也就是你枚举那么多个\(j\)
可是\(query(j+1,i)\)永远都小于等于21
那就有很多没有用的
这个时候我们就应该想到换一种思路来做
为什么不可以枚举mex?
而又因为\(dp[i]\)一定是单调不下降的
所以我们只要找到满足\(mex= 0 \sim 21\)的每一个最大的\(j\)即可
对于每一个数，我们记录它上一次出现的位置\(lst[a[i]]\)
我们假设现在要去找到\(mex=6\)
那么最大的\(j=min(lst[0],lst[1] \dots lst[5])-1\)
这样再更新答案即可
而对于\(j\)的求解
我们可以再维护一个前缀min即可O(1)得到
所以总复杂度是\(O(22* n)\)
代码也是比较好写的，哎~
#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
int n,x,dp[maxn],lst[maxn],sum[maxn],l[maxn],cnt=0,ans[maxn];
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
int main(){
freopen("cut.in","r",stdin);
freopen("cut.out","w",stdout);
n=read();
for(int i=1;i<=n;i++){
x=read();
lst[x]=i;sum[0]=lst[0];
for(int j=1;j<=21;j++) sum[j]=min(sum[j-1],lst[j]);
for(int j=1;j<=21;j++)
if(sum[j-1]>0)
if(dp[sum[j-1]-1]+j>dp[i])
dp[i]=max(dp[i],dp[sum[j-1]-1]+j),l[i]=sum[j-1]-1;
}
x=n;
while(x!=0) ans[++cnt]=l[x]+1,x=l[x];
printf("%d %d\n",dp[n],cnt);
for(int i=cnt;i>=1;i--) printf("%d ",ans[i]);
printf("\n");
return 0;
}
T3.挑战NPC（hamilton）
题目大意
给你 \(n\) 个点，\(m\) 条边的有向图，求出若干两两不交（没有公共点或公共边）的简单回路的并，使得经过每个点恰好一次。或报告无解。
如果有解，输出任意一个即可。
\(1 \lt n \le 10^5,n \le m \le 2* 10^5\)
考场思路
输出\(NO\)有15分
我是真的在自己很慌的情况下不知道怎么下手……
Solution
网络流（啊这）
我们可以把题意转化成
选出一些边使得每个点的入度和出度都为1
这样就可以进行拆点的网络流
（虽然还没做过数据这么大的网络流，反正网络流的复杂度是\(O(跑得过)\)）
我们对于每一个点把它拆成两个点\(i\)和\(i+n\)
一个作为出点，一个作为入点
从而防止一个单独的点误认为环
对于每一条\(a \to b\)的有向边
我们考虑在网络流的图上建立\(a \to b+n\)的边
最后在建立一个超级原点和超级汇点
每一条边的最大流量都为1来跑网络最大流即可
而如果最大流等于\(n\)
说明有解，记录一下用过的边来找答案
反之，就无解
（这么就没写网络流都要不会了……但还是写出来了）
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10,inf=0x3f3f3f3f;
int n,m,head[maxn],tot=0,u,v,ans=0,cur[maxn],lv[maxn],t[maxn],st,ed,a[maxn],cnt;
bool vis[maxn];
struct edge{
int u,v,nxt,val,flag;
}e[maxn];
void add(int u,int v){
e[++tot]=(edge){u,v,head[u],1,true};
head[u]=tot;
e[++tot]=(edge){v,u,head[v],0,false};
head[v]=tot;
}
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
bool bfs(){
queue<int >q;
q.push(st);
memset(lv,-1,sizeof(lv));
lv[st]=0;cur[st]=head[st];
while(!q.empty()){
int nw=q.front();q.pop();
for(int i=head[nw];i!=-1;i=e[i].nxt){
int v=e[i].v,val=e[i].val;
if(val>0&&lv[v]==-1){
lv[v]=lv[nw]+1;
q.push(v);
}
}
}
return lv[ed]!=-1;
}
int dfs(int nw,int flow){
if(nw==ed) return flow;
int res=flow;
for(int i=head[nw];i!=-1;i=e[i].nxt){
int v=e[i].v,val=e[i].val;
if(val>0&&lv[v]==lv[nw]+1){
int c=dfs(v,min(res,val));
res-=c;
e[i].val-=c;
e[i^1].val+=c;
}
}
return flow-res;
}
void dinic(){
ans=0;
while(bfs()) ans+=dfs(st,inf);
}
void dfsans(int x){
if(vis[x]) return;
vis[x]=true;
a[++cnt]=x;
dfsans(t[x]);
return;
}
int main(){
freopen("hamilton.in","r",stdin);
freopen("hamilton.out","w",stdout);
memset(head,-1,sizeof(head));tot=-1;
n=read();m=read();
st=0;ed=n*2+1;
for(int i=1;i<=m;i++){
u=read();v=read();
add(u,v+n);
}
for(int i=1;i<=n;i++) add(st,i),add(i+n,ed);
dinic();
if(ans<n) printf("NO\n");
else{
printf("YES\n");
for(int i=0;i<=tot;i++)
if(e[i].flag==true&&e[i].val==0&&e[i].u!=st&&e[i].v!=ed) t[e[i].u]=e[i].v-n;
for(int i=1;i<=n;i++)
if(!vis[i]){
cnt=0;
dfsans(i);
printf("%d ",cnt);
for(int i=1;i<=cnt;i++) printf("%d ",a[i]);
printf("\n");
}
}
return 0;
}
T4.无聊的问题
题目大意
有一个长度为 \(n\) 的序列，每个数为 \(a_i\)。
现在有 \(q\) 个询问，每个询问先给出一个数 \(k\)，然后给出一些区间 \(l_i, r_i\) 求：
\(lcm_{1 \le x \le k}(lcm_{l_x \le i \le r_x} a_i) mod 998244353\)
\(1\le n,q,a_i \le 10^5,1 \le \sum k \le 2.2 * 10^5\)
考场思路
就说我吧
考场上甚至没有反应过来lcm是什么
我以为成了lcp，求两个字符串的最长公共前缀
我挺纳闷的，咋就和字符串扯上关系了……
唉，是完蛋了……
科普一个冷知识：
lcm是最小公倍数
（其实我以前是知道的）
于是我什么都没打
Solution
对于有关lcm的题
我们有一个套路：
分解质因数来考虑
比如，有两个数\(a,b\)
\(a=p_1^{c_1} * p_2^{c_2} * \dots * p_n^{c_n}\)
\(b=p_1^{d_1} * p_2^{d_2} * \dots * p_n^{d_n}\)
那么
\(lcm(a,b)=p_1^{max(c_1,d_1)} * p_2 ^{max(c_2,d_2)} * \dots * p_n^{max(c_n,d_n)}\)
同理，我们可以用这种方法算到\(k\)个数的lcm
而注意到分解质因数\(n\)
有一个很有用的性质——$ \gt \sqrt{n}$的质因数只有一个
先来讨论\(\le \sqrt{n}\)的质数
由于\(a_i \le 10^5\)
所以小于\(sqer{10^5}=316\)的质数只有65个
所以可以直接暴力枚举每一个数出现次数的max
可以直接用线段树或ST表（虽然我不会）维护即可
再来讨论大于316的质数
由于每一个数里这样的质因数只会存在一个
考虑用bitset来维护
我是真的没看懂题解，而且不配代码……
但是前面的思路大概还是懂了，收货还是挺大的
总结
- 打模拟赛要合理安排时间，想清楚一道题再动手，而且不能死磕一道题
否则就会打出这场很可怕的，非常可怕的，极其可怕的模拟赛 - 有些时候要学会换个思维方式来思考，考虑去枚举比较小的
- 关于lcm的套路——分解质因数（见T4）
- 遇到不会的题可以考虑网络流，先把所有暴力打了