本来上上一周就该写的，但最近没心情写题解也没心情写题。嘛。人生被困在一望无垠的荒草里咯！
1.CF1305F
link && submission
本来想放在考试的 T4 的。没做过的同学有福辣！天才随机化
第一个结论是最终操作次数不会超过 n 。因为你可以把所有的奇数全部 +1 这样 gcd 至少是 2 然后这个操作最多 n 次。第二个结论是至少有一半的元素最多被操作了一次。超过一半的话总次数就超过 n 了一定不优。那么如果说你随机在序列中找一个数他在最终的操作序列中被操作的次数不超过 1 的概率是 \(\frac{1}{2}\)。那么我们就随便找 50 次，然后补充一个结论就是最后的 gcd 是质数的操作次数不劣于合数，所以每次把找出来的数 x、x-1、x+1 分别质因数分解再把质因数放进一个 set 暴力统计每一个质数的最终答案就好了。
2.CF1839E
link && submission
首先我们考虑能找到一种操作方法使得最后依次操作能够同时吧两个数同时消掉，如果能达成这种状态后手就赢了。而且后手决定操作次序所以这种方案一定能实现。考虑什么时候存在这种方法，就是能够把序列分成两个集合满足两个集合的和相同。
现在来证明如果一开始不能把序列分成两个和相同的集合，进行了数次操作后依旧不行。不妨设第一轮选择了两个数 x,y 且满足 x>y 。那么剩下的数如果能分出来那么一定有 x-y+s1=s2，移项发现 x+s1=y+s2，说明一开始就可以。但一开始不可以，所以不存在。
那么如果能吧原序列分成两个和相同的集合后手必胜，否则先手必胜。判断能不能用个背包就好了。
3.luoguP4899
link
为你我变成狼人模样😭😭😭🤪
还是挺妙的吧。首先所有点编号+1。给所有边的边权定为两点的较小值，跑一颗 kruskal 最大重构树，发现一个点的子树内点可以在满足不经过 [1,l] 的点的情况下互相到达。同理可以求一颗边权为较大值的 kruskal 最小重构树这样子树内的点可以互达。然后给每棵树一个字典序，然后每个子树的字典序是连续的,设两个字典序 p1,p2 表示 第1/2棵树的字典序为 i 的为 \(p1/2_i\)，问题就转换成了 p1 和 p2 的某个子区间是否有交。显然的是 p1,p2 都是排列啊，然后你处理一下 p2_i 在 p1 里面出现的位置，然后建一棵主席树应该就行了。
#include<bits/stdc++.h>
using namespace std;
int n,m,q;
struct Tree{
int tot=0;
int L[400005],R[400005],pos[400005];
int qwq[400005];
int fa[400005][21];
vector<int> v[400005];
void DFS(int x){
for(int i=1;i<=20;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
if(x<=n) return L[x]=R[x]=++tot,pos[tot]=x,qwq[x]=x,void();
L[x]=tot+1;
for(int i=v[x].size()-1,y=v[x][i];i>=0;i--,y=v[x][i]) fa[y][0]=x,DFS(y);
R[x]=tot;
}
int Find_Pre(int x,int val){
for(int i=20;i>=0;i--) if(qwq[fa[x][i]]>=val) x=fa[x][i];
return x;
}
int Find_Nxt(int x,int val){
for(int i=20;i>=0;i--) if(qwq[fa[x][i]]<=val&&fa[x][i]) x=fa[x][i];
return x;
}
}T1,T2;
struct zz{
int x,y,w;
}t[3][400005];
bool cmp(zz x,zz y){ return x.w<y.w; }
bool smp(zz x,zz y){ return x.w>y.w; }
int pre[400005];
int Find(int x){
if(pre[x]!=x) pre[x]=Find(pre[x]);
return pre[x];
}
void Solve(Tree &T,zz *t){
for(int i=1;i<=2*n;i++) pre[i]=i;
int tot=n;
for(int i=1;i<=m;i++){
int x=t[i].x,y=t[i].y;
if(Find(x)==Find(y)) continue;
tot++;
int fx=Find(x),fy=Find(y);
T.qwq[tot]=t[i].w;
T.v[tot].push_back(fx),T.v[tot].push_back(fy);
pre[fx]=pre[fy]=tot;
}
T.DFS(tot);
}
struct ss{
int lc,rc,sz;
};
int rt[400005];
struct Treee{
ss t[10000005];
int tot=0;
void Change_Tree(int &x,int y,int l,int r,int pos,int val){
// printf("%d %d %d %d %d %d\n",x,y,l,r,pos,val);
x=++tot;t[x]=t[y];
if(l==r) return t[x].sz+=val,void();
int mid=(l+r)>>1;
if(pos<=mid) Change_Tree(t[x].lc,t[y].lc,l,mid,pos,val);
else Change_Tree(t[x].rc,t[y].rc,mid+1,r,pos,val);
t[x].sz=t[t[x].lc].sz+t[t[x].rc].sz;
}
int Find_Tree(int x,int y,int l,int r,int L,int R){
// printf("%d %d %d %d %d %d\n",x,y,l,r,L,R);
if(L<=l&&r<=R) return t[y].sz-t[x].sz;
int mid=(l+r)>>1,sum=0;
if(L<=mid) sum+=Find_Tree(t[x].lc,t[y].lc,l,mid,L,R);
if(mid+1<=R) sum+=Find_Tree(t[x].rc,t[y].rc,mid+1,r,L,R);
return sum;
}
}T;
int xpx[400005];
int main(){
cin>>n>>m>>q;
for(int i=1,x,y;i<=m;i++) scanf("%d%d",&x,&y),x++,y++,t[1][i]=(zz){x,y,min(x,y)},t[2][i]=(zz){x,y,max(x,y)};
sort(t[1]+1,t[1]+m+1,smp),sort(t[2]+1,t[2]+m+1,cmp);
Solve(T1,t[1]),Solve(T2,t[2]);
for(int i=1;i<=n;i++) xpx[T1.pos[i]]=i;
for(int i=1;i<=n;i++) T.Change_Tree(rt[i],rt[i-1],1,n,xpx[T2.pos[i]],1);
while(q--){
int x,y,l,r;
scanf("%d%d%d%d",&x,&y,&l,&r);x++,y++,l++,r++;
int xx=T1.Find_Pre(x,l),yy=T2.Find_Nxt(y,r);
printf("%d\n",T.Find_Tree(rt[T2.L[yy]-1],rt[T2.R[yy]],1,n,T1.L[xx],T1.R[xx])>0);
}
return 0;
}
4.CF1779F
link && submission
定义 \(b_i\) 表示子树 i 的异或和。如果存在一个时刻满足 \(b_1=0\) 那么直接操作 \(b_1\) 就好了。现在考虑操作每个子树对于 \(b_1\) 的影响，发现如果子树大小是偶数对于 \(b_1\) 是没有影响的，而操作子树大小为奇数的某个点 x，会让 b_1 变成 \(b_i \oplus b_x\)。
然后你还发现如果操作了一个点，就不可能操作他子树内的点了，因为如果子树内的点的 size 为偶数那么操作没用，为奇数那么这两次操作操作就相当于是 \(b_1 \oplus b_x \oplus b_x\) 没有任何作用不如不操作。
那么问题就转换成了选择几个节点并且先选择的节点不是后选择节点的父亲，使得他们的异或和为 \(b_1\) 然后 dp 处理这个就完了。
其实后面这些性质根本没啥卵用，因为在题解区看到了直接暴力操过去的做法🥲
5.CF1693F
link && submission
首先答案的上限是一次操作整个序列。
不妨假设 0 的个数比 1 多，否则可以将序列翻转然后每个值取反。观察后有个显而易见的贪心是每次操作第一个从前缀开始的 s0=s1 的区间，如果 0 多了就把往右移。这样操作的答案一定不劣于一次操作整个序列，s0 表示区间内 0 的个数，因为这样每次至少有一个 0 能归位。
按照这个证明思路，我们只需要让每一次能够归位的 0 更多就好了。我们先假设最后一次操作能让所有的 1 归位，那么前面的操作就至少要让最前面的 s0-s1 个 0 归位。考虑暴力执行这个操作，因为排序后对于排序后面的位置来说前缀和是不会改变的，我们可以利用这个性质把 0 看成 1，1 看成 -1 做前缀和。因为每次操作过后前面 id 个一定都是 0，那么下次能操作到的区间前缀和一定是 id。利用这个性质写个桶就行了。
6.CF1491G
link && submission
这道题得先手玩一下再看题解。。因为这题太他吗傻逼了。主要是luogu题解区没一个讲清楚的。
首先你肯定得把他放在环上，然后你发现颜色这个限制被转换到了边上。然后你每次处理环上相邻的两个点就是把两点的出边先反色，然后靠前的出边和后面那个点形成自环跑出去了，后面那条边和前面的点继续留在环上。一直这样换那么一个长度为 m 的环就被我们转换成了 m 个自环，其中有两个自环的边的颜色变为反色。显然再对这两个自环处理是会超操作次数限制的。发现我们可以先把两个环挼（rua）成一个大环，这时候环上有两条边是反色。你每次操作都把这两条边向下递进颜色，这样两个长度为 m1,m2 的环就在 m1+m2 次操作下变成了全部都是原色的自环，也就是归位成功了。
那么如果说环的个数是奇数呢？前面先两两匹配最后剩下一个环，然后你发现把一个自环放进这个环里之后这个环上刚好有两条反色边。这样你有条边处理了两次，所以总操作次数为 n+1
如果一来环就只有一个呢？你按照老样子相邻两个点依次换，当最后剩下了两个点，这时环上有一条反色边，还有一个边反色的自环。然后你把那个自环上的反色边和环上的原色边挼在一起，这样环上就变成了两条反色边一条原色边。再操作即可。应该是 n+1 次。
7.CF1599A
link && submission
记录一个性质。你把物体排序，然后一边放一个。这样放下去两堆玩意儿就有一个美妙的性质：每次取出最小的物品两堆的相对大小不会改变；每次取出最大的物品两堆的相对物品一定改变。然后利用这个性质做就好了。算是一个构造的性质吧。构造是不是太多了？
8.CF1572B
link && submission
总感觉这篇我写过题解的？但是就是找不到诶。。。
首先异或和得为 0。然后分类讨论。对于 n 为奇数，我们从后往前操作 n-2,n-4,……,1 然后这个时候 a1 一定等于 0 因为所有的异或和为0，其他的都是两个相同的放在一起。这时候操作 1,3,……,n-4,n-2 就好了。对于偶数，找到两个分别异或和为 0 的长度为奇数的段就好了，否则无解。
9.CQBZOJ4357A
题目大意：
一个人参加赌博，带了 A 块钱，可以赌博任意次。每次赌博投入 x (实数) 有 P 的概率获胜返回 2x， 1-P 的概率啥也不返。 P<=0.5
这个人希望赢钱直到 B 块钱。
问这个人采取最优策略最后胜利的概率是多少。
题解
随便讲讲吧，户厕题就不放链接了。
如果说操作次数是一定的，那么假设操作次数为 m，发现把 A 分成 \(2^m\) 段，每一段的概率是相同的。考虑将 A/B 用二进制小数表示
定义 dp[x] 表示第 x 位向第 x-1 为进位成功的概率是多少。显然答案为 dp[1] 。转移分为当前位小数位 0/1 分类讨论。
但是有可能转移是个无限循环小数，把循环部分找到，然后规定一个位置遍历整个环可以找到一个方程，求解然后回代即可。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll Mod=998244353;
ll Pow(ll a,ll b){
ll ans=1;
while(b){
if(b&1) ans*=a,ans%=Mod;
a*=a,a%=Mod,b>>=1;
}
return ans;
}
ll dp[1000005],vis[1000005];
ll k[1000005],b[1000005];
ll a[1000005];
ll tot=0;
ll A,B,Q;
signed main(){
freopen("money.in","r",stdin);
freopen("money.out","w",stdout);
cin>>A>>B>>Q;Q*=Pow(1000000,Mod-2),Q%=Mod;
ll x=A;
while(!vis[x]){
tot++,vis[x]=tot,a[tot]=x;
if(x*2<B) k[tot]=Q,x=x*2;
else k[tot]=(1-Q+Mod)%Mod,b[tot]=Q,x=x*2-B;
}
ll K=1,M=0;
for(int i=tot;i>=vis[x];i--) M=((k[i]*M)%Mod+b[i])%Mod,K=K*k[i]%Mod;
dp[vis[x]]=M*Pow((1-K+Mod)%Mod,Mod-2)%Mod;
for(int i=vis[x]-1;i>=1;i--) dp[i]=dp[i+1]*k[i]%Mod+b[i],dp[i]%=Mod;
cout<<dp[1]<<endl;
return 0;
}
//只有过完今天明天才会到来！
10.CQBZOJ4357D
题目大意
给你两个长度为 n 的 1 到 n 的排列 A,B。
初始的时候你手里有两个长度为 n 的 1 到 n 的排列 C，D 其中 C[i]=D[i]=i;
你可以选择任意个互不相同的 i 将 C[i] 替换成 A[i]。然后你又可以选出任意多个互不相同的 j，将 D[j] 替换成 B[j]。
你需要保证替换后 C,D 依旧是排列，最终求 \(\sum_{i=1}^{n} [C[i]=D[i]]\) 的最小值。
题解
最小割。其实知道最小割就挺好做了。
放了张题解。这道题重要的是学习最后一个 b---->a 的建图方式。为什么是从 b 联向 a 啊
2030183586 2023/10/29 16:45:42
想问一个问题关于最小割的问题，二分图建图，左部和右部有 n 对相对的点，每个点不选也有代价，选了也有代价，相对的点都不选有额外代价，都选了有额外代价，然后求最小代价
2030183586 2023/10/29 16:45:47
请问这个能做吗
退役老年菜鸡 2023/10/29 17:01:19
你把一边的点取反
退役老年菜鸡 2023/10/29 17:01:30
就好了
退役老年菜鸡 2023/10/29 17:02:32
左边的点选就是 x-T，不选就是 S-x
退役老年菜鸡 2023/10/29 17:02:49
右边的点选就是 S-y，不选就是 y-T
退役老年菜鸡 2023/10/29 17:03:14
同时选就是 x-y，同时不选就是 y-x
2030183586 2023/10/29 17:05:31
我想过，但是这样是不是会有，我同时选了两点，但是同时选的额外代价我用不选一个点把他代替了
2030183586 2023/10/29 17:05:51
相当于就是我同时选了 x选 x不选 y选 三个状态
2030183586 2023/10/29 17:06:06
然后避免选择 xy同时选的额外代价
2030183586 2023/10/29 17:06:15
这样是不是就有问题
退役老年菜鸡 2023/10/29 17:06:16
没有这么多状态啊
退役老年菜鸡 2023/10/29 17:06:20
x 就是一个点
退役老年菜鸡 2023/10/29 17:06:31
x 要么在 S 要么在 T
退役老年菜鸡 2023/10/29 17:06:51
就严格按照割的定义
2030183586 2023/10/29 17:07:22
就是可能出现我不割中间的边，一个点联向s和t都被割了
退役老年菜鸡 2023/10/29 17:07:46
按照割的定义
[保留][辣辣催婚协]被删两次背单词 2023/10/29 17:07:55
DDDD
@[保留]D_D_D_D 不能吧，最小割树需要的是mst的边，sw只保证会最后拿到一条mst的边，前面没有强保证
退役老年菜鸡 2023/10/29 17:08:21
割的定义不是删边
退役老年菜鸡 2023/10/29 17:08:31
是划分点集
2030183586 2023/10/29 17:08:33
2030183586 2023/10/29 17:08:44
差不多图应该张这个样子吧？
退役老年菜鸡 2023/10/29 17:09:03
啥啊
退役老年菜鸡 2023/10/29 17:09:07
没有 inf
2030183586 2023/10/29 17:09:15
那个没关系的，，，
退役老年菜鸡 2023/10/29 17:09:29
除了 S T 就只有 n 个点
2030183586 2023/10/29 17:09:30
我一开始想多了，加上应该也没问题
退役老年菜鸡 2023/10/29 17:09:45
加上有问题啊
2030183586 2023/10/29 17:09:55
？？不应该是 2n 个点吗
退役老年菜鸡 2023/10/29 17:10:14
你有 n 个变量，就只有 n 个点啊
2030183586 2023/10/29 17:10:35
我是n对点啊
退役老年菜鸡 2023/10/29 17:10:45
哦哦对不起
退役老年菜鸡 2023/10/29 17:11:36
那个 inf 是什么来着，你刚刚没说
2030183586 2023/10/29 17:11:51
inf是我想多了，可以不用柴电
2030183586 2023/10/29 17:11:53
拆点
退役老年菜鸡 2023/10/29 17:12:10
拆的话就不对了吧
2030183586 2023/10/29 17:12:24
2030183586 2023/10/29 17:12:27
这样吗
退役老年菜鸡 2023/10/29 17:13:07
你现在画的这个就没问题
2030183586 2023/10/29 17:13:08
就是我把两条 0 0 割了，如果我再把一条 1 割了也是满足割的定义的
退役老年菜鸡 2023/10/29 17:15:08
你割的是哪几条
2030183586 2023/10/29 17:15:23
2030183586 2023/10/29 17:15:24
这样
2030183586 2023/10/29 17:15:36
红色表示割
退役老年菜鸡 2023/10/29 17:15:48
那你为什么
退役老年菜鸡 2023/10/29 17:15:58
不止割右边那两条
退役老年菜鸡 2023/10/29 17:16:02
只
2030183586 2023/10/29 17:16:51
woc这样的吗
退役老年菜鸡 2023/10/29 17:17:16
反正这个建模是严格按照最小割定义的
退役老年菜鸡 2023/10/29 17:17:29
所以别去考虑删边的事情
2030183586 2023/10/29 17:18:32
谢谢！
2030183586 2023/10/29 17:18:48
这个 按照最小割定义的建模 是什么意思呢
2030183586 2023/10/29 17:18:55
有什么资料可以学习一下吗
保留 myee 2023/10/29 17:19:45
今晚7点，UR#26马上开始，参赛即有概率达成抱枕条件获得UOJ抱枕，欢迎来玩~
比赛地址：https://uoj.ac/contest/86
退役老年菜鸡 2023/10/29 17:19:48
其实就是 n 个 0/1 的变量
退役老年菜鸡 2023/10/29 17:19:58
每个变量 0/1 有个代价
退役老年菜鸡 2023/10/29 17:20:04
x=0，y=1 有个代价
退役老年菜鸡 2023/10/29 17:20:11
分别对应三种边
2030183586 2023/10/29 17:22:58
大概明白了
2030183586 2023/10/29 17:22:59
谢谢文章来源：https://www.toymoban.com/news/detail-719304.html
这样就好了。文章来源地址https://www.toymoban.com/news/detail-719304.html
到了这里，关于To_Heart—题集——给我一瓶酒再给我一支烟的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
