模拟赛1006 T3
可以发现交集点选的边一定是它的最小生成树上的，2^n爆算即可
模拟赛1006 T4
这种题做过好多遍了，一个广为人知的结论就是k选的区间一定是k+1选的区间的前缀，线段树上二分即可
模拟赛1007 T3
考虑每个不同的字符串前缀都会作为一个trie树上的节点，于是表示出每个前缀t至少出现一次的概率，加起来就是期望了。柿子用背包算。
设T中字符分别出现(T0,..Tn)次
P(T是S前缀)=
$\frac {A_{\sum Si}^{\sum ti}}{\prod A_{Si}^{Ti}}$
模拟赛1007 T4
自己看题解
计蒜客1007 T4
i=k时候，答案不超过n/k
线段树上二分即可
CF 1572D
建出二分图。
考虑每加入一条边，删去相邻边2n-1条，所以k-1次之后一定可以选第(2n-1)(k-1)+1大的边，这个数可以直接跑BM
模拟赛1011 T1
dp方程列出来，然后发现肯定是越往远处扩展越好。
考虑到[i,j]与[i+1,j]不同的地方只有多了[i]...j]
于是变长的那部分只能是与i往右的部分匹配了，否则[i+1，j]也会拓展到它。
双指针即可
模拟赛1011 T2
直接容斥会挂，考虑到把柿子写出来，相当于把Ci->Cj边权为-F[Ci][Cj],于是就是求从超级源到超级汇的路径乘积和了。
容斥不一定要2^n的啊啊啊
模拟赛1013 T1
把(a,b,c)钦定选a，于是变成选择y个(b-a)和z个(c-a)使得和最大。
微扰一下
设(b-a)=e,(c-a)=f
Ei+Fj>Ej>Fi
Ei-Fi>Ej-Fj
按Ei-Fi排序，记录前后缀和，枚举分界点取最大答案即可。
Ohhhhh傻逼题
Complete the MST
显然发现除了一条边填x之外其他都填0
肯定是想办法把0全部加入，x不加
当图比较稠密的时候，暴力枚举x填在哪条边，跑kruscal
O(nsqrt(n))
当图比较稀疏的时候，补图必定有环，环边上的0没有用，随便取一条换成x，最后再跑一遍kruscal。（相当于把0放下来到别的地方了。）
CF1031D Minium Path
模拟赛里做到了这种题。
总结一下套路:分层、BFS，贪心
求网格图中到某点路径字典序最小:
对于每层点，把右边和下面的点加入，这些是下一层可能用到的。
这些点里选最小的那些，所以每层点之间都是相等的
把这些点入队，一直做是N^2的
模拟赛1016 T1
给图分层，枚举前导0（即只通过0边BFS到的点），把最低的前导0加入，每层到下一层的贪心取最小的边（u,v），把v入队。
模拟赛1018 T2
记inv[i]为i前面比i大的个数，不难发现一个inv数组与一个排列一一对应，于是直接用某题做就行了。
模拟赛1020 T2
对每个k，求$ \max(A_i+B_j) (i|j=k)$
k<=2^18
yjj的算法很NB,就是一起一位一位填(i,j,k)，保证i|j==k并且i,j无交集。填满n位之后算a[i]+B[j] (此处B[j]表示B的超集中的k的子集的b的最大值)
在dfs的时传入三个指针(a,b,ans)每次+mid就是移动指针，结束时填到相应位置。当(a+mid,b,ans+mid)时可以加入包含b的数，用它们+mid的位置的b更新超集最大值。
回望过去，当年那场联合省选给我的启示意义太大了
无论如何要看清题面，模拟样例
无论如何要敢于尝试、相信自己的水平
无论如何要善于转化题面，相信一切都是可做的！
如果发现不是很可做，那一定有结论！
最重要的:无论如何，不能畏难！
遥想当年我Day1再次高估难度，降智得连T1都不会，一出考场发现大家都200+，很震惊，很难过。
于是Day2考场上就以为都是傻逼题（虽然这题真是傻逼题），没看清楚题面就开始写，白写了两个小时错题。
这题我想出了2^nnn*m 的做法，还过了大样例，但官方数据挂成了60分（md我2.5h写的和别人0.5h写的分数一样），并且至今不知道错在哪（也许是没开ll？还是边界问题？还是常数太大？）考场代码早就不知道放哪去了，反正至今都是一个大遗憾。
于是，今天，我决定复盘那场完全失败的联合省选！
鉴于D1T1、D1T3、D2T1之前已经复盘过了，而这道满载着遗憾的D2T2还没过，于是决定复盘。
显然打N！暴力的时候发现只要贪心$B_i=B_{i-1}+(A_i-A_{i-1})+(i-1<i)$ 最后$\sum Bi \le M$ 就OK了
于是差分一下
$\sum [(A_i-A_{i-1})+(i-1<i)]*(n-i+1) <= M$
于是这题就做完了，$O(2^N \times N \times N \times M)$
tmd要开ll
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=15,M=505;
int a[N];
// \sum max(a_i-1-a_i,0) * (n-i+1)
typedef long long ll;
ll f[1<<N][N][M];
int main(){
int i,j,k,p,mx=0,mxf;
cin>>n>>m;
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]>mx){
mx=a[i];
mxf=i;
}
}
for(i=1;i<=n;i++)
if(n*(mx-a[i]+(mxf<i))<=m)f[1<<i-1][i][n*(mx-a[i]+(mxf<i))]=1;
for(i=0;i<(1<<n);i++){
int cnt=0,o=i;
while(o)cnt++,o-=o&-o;
if(cnt<=1)continue;
for(j=1;j<=n;j++)
if(i>>j-1&1)
for(k=1;k<=n;k++)
if((i^(1<<(j-1)))>>k-1&1){
int del_cur=(n-cnt+1)*(max(a[k]-a[j]+(k<j),0));
for(p=del_cur;p<=m;p++)
f[i][j][p]+=f[i^(1<<(j-1))][k][p-del_cur];
}
}
ll ans=0;
for(i=1;i<=n;i++)
for(j=0;j<=m;j++)
ans+=f[(1<<n)-1][i][j];
cout<<ans<<endl;
return 0;
}
马上AFO了集齐九九八十一篇题解说不定能渡劫。。。
看到这题然后不会做，怎么办
合并操作啊
一个巧妙的建模是把操作转换成等腰直角三角形的覆盖。
一开始所有点都是底边为[i-a[i],i+a[i]]的等腰直角三角形。
很显然，当两区间有交的时候合并是优的，没交的时候合并是不优的
于是就做完了
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2000005;
int n;
int L,R,top,sl[N],sr[N];
int main(){
int i;
cin>>n;
for(i=1;i<=n;i++){
int x,l,r;
scanf("%d",&x);
if(!x)continue;
l=i-x,r=i+x;
if(l>R){
sl[++top]=L;
sr[top]=R;
L=l,R=r;
}else{
L=min(L,l),R=max(R,r);
while(top&&L<=sr[top])
L=min(L,sl[top--]);
}
}
sl[++top]=L,sr[top]=R;
int ans=0;
for(i=1;i<=top;i++)ans+=(sr[i]-sl[i]+1)>>1;
cout<<ans<<endl;
return 0;
}
这可能是OI生涯最后的文章了
upd：渡劫失败，但复活了
MOMENT OF BLOSSOM
无向图，数据还那么大，还是异或，答案很显然是在随便一颗生成树上的。
感性理解一下，如果所有操作都集中在一条路径上，那抵销的肯定更多，所以结论是对的。
如果可以，直接暴力跳LCA即可。
否则，异或出来为1的那些路径所组成的连通块（是一片森林），每次选择一条路径删去，最少删几次？
这是个经典问题，ans=奇数点个数/2
code:
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=6e5+5;
int cnt,h[N],nxt[N],to[N],f[N],fa[N],a[N],X[N],Y[N],b[N],dep[N];
void add(int x,int y){
nxt[++cnt]=h[x];
h[x]=cnt;
to[cnt]=y;
}
int gf(int x){
return x==f[x]?x:f[x]=gf(f[x]);
}
void dfs(int u,int pa){
int i;
fa[u]=pa;dep[u]=dep[pa]+1;
for(i=h[u];i;i=nxt[i]){
int v=to[i];
if(v!=pa)dfs(v,u);
}
}
int du[N],ans,dao[N],opt;
int cmp(int x,int y){
return dep[x]<dep[y];
}
int main(){
cin>>n>>m;
int i;
for(i=1;i<=n;i++)f[i]=i;
for(i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
int fx=gf(x),fy=gf(y);
if(fx^fy){
f[fx]=fy;
add(x,y),add(y,x);
}
}
dfs(1,0);
int q;cin>>q;
for(int j=1;j<=q;j++){
scanf("%d%d",&X[j],&Y[j]);
for(i=X[j];i;i=fa[i])a[i]^=1;
for(i=Y[j];i;i=fa[i])a[i]^=1;
}
int tt=0;
for(i=2;i<=n;i++)tt+=a[i];
if(tt){
puts("NO");
for(i=1;i<=n;i++)du[i]^=a[i],du[fa[i]]^=a[i];
for(i=1;i<=n;i++)ans+=du[i]&1;
cout<<ans/2<<endl;
}else{
puts("YES");
for(int j=1;j<=q;j++){
int x=X[j],y=Y[j];
if(dep[x]>dep[y])swap(x,y);
int p=1,opt=0;
for(i=1;i<=n;i++)b[i]=0;
for(i=x;i;i=fa[i])b[i]^=1;
int LCA=0;
for(i=y;i;i=fa[i]){
b[i]^=1;
if(b[i]==0&&!LCA)LCA=i;
}
for(i=x;i!=LCA;i=fa[i])p++;
for(i=y;i!=LCA;i=fa[i])p++;
printf("%d\n",p);
for(i=X[j];i!=LCA;i=fa[i])
printf("%d ",i);
printf("%d ",LCA);
for(i=Y[j];i!=LCA;i=fa[i])dao[++opt]=i;
for(i=opt;i>=1;i--)
printf("%d ",dao[i]);
puts("");
}
}
return 0;
}
SPANNING TREE QUERIES
肉眼可见，答案在很少几段区间内都是等差数列,为什么呢？
因为对于任意的两条边$(i,j)$,当且仅当$2x < A_i+A_j+1 $时，kruscal的时候会先尝试选$i$,否则先选$j$
这样答案就与小于x的边数线性相关，所以是等差数列。
所以称任意$(i,j)$的中点为关键点，只有$m2$个点，可以$m3$暴力算出这几个点的答案。而所有询问的答案一定是以这些答案为首项的等差数列的第几项。
所以对于每个q，它的答案容易通过lowerbound对应的关键点的答案算出来。
注意求的是所有答案的异或和，于是排个序再双指针算就可以做到线性了
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200005,M=1e7+5;
ll n,m;
struct node{
ll x,y,z,zz;
}a[N],b[N];
ll cmp(node u,node v){
if(u.z==v.z)return u.zz>v.zz;
return u.z<v.z;
}
ll h,c[N],f[N];
ll gf(ll x){
if(f[x]==x)return x;
return f[x]=gf(f[x]);
}
ll s[N],ans,q[M],t[N],F[M];
int main(){
cin>>n>>m;
int i,j;
c[++h]=0;
for(i=1;i<=m;i++){
scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].z),a[i].zz=a[i].z;
c[++h]=a[i].z;
}
c[++h]=2e9;
for(i=1;i<=m;i++)
for(j=1;j<i;j++)
c[++h]=(a[i].z+a[j].z+1)/2;
sort(c+1,c+h+1);
h=unique(c+1,c+h+1)-c-1;
sort(a+1,a+m+1,cmp);
for(i=1;i<=h;i++){
for(j=1;j<=m;j++){
b[j]=a[j];
b[j].z=abs(c[i]-b[j].z);
}
sort(b+1,b+m+1,cmp);
for(j=1;j<=n;j++)f[j]=j;
int tot=0;
for(int j=1;j<=m;j++){
int fx=gf(b[j].x),fy=gf(b[j].y);
if(fx!=fy){
f[fx]=fy;
if(tot<n-1){
tot++;
if(b[j].zz<=c[i])s[i]-=b[j].zz,t[i]++;
if(b[j].zz>c[i])s[i]+=b[j].zz,t[i]--;
}
}
}
}
ll pos,k,A,B,C;
cin>>pos>>k>>A>>B>>C;
for(i=1;i<=pos;i++)scanf("%lld",&q[i]);
for(i=pos+1;i<=k;i++)q[i]=(q[i-1]*A+B)%C;
sort(q+1,q+k+1);
ll ans=0;int p=1;
for(i=1;i<=k;i++){
while(p<h&&c[p+1]<=q[i])p++;
ans^=(s[p]+t[p]*q[i]);
}
cout<<ans<<endl;
return 0;
}
CF1632E
mmd怎么现场比赛的2500+每次都不会做
加边肯定是加(1,x),如果二分一个答案A,那dep>A的一定要被影响到
那这些dep[u]=X+dis(u,x)，而dep[u]<=A,所以dis(u,x)<=A-X
总之，要在树上一堆点中找到一个x使得max(dis(u,x))最小。
这是个经典结论，x取直径中点就行了，所以要找到最小的A使得$A-\frac{D+1}{2} >=X$
显然，由于可二分性，不等式左随着A的增大而增大,右随X增大而增大
于是双指针搞定。至于维护直径这事，枚举LCA，显然一定是选最深和次深的链（最早且最长）。
code(Starline):
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N = 3e5 + 5;
vector <int> adj[N];
int T, n, ans, d[N], mx[N], mx2[N], f[N];
void dfs(int u, int fa) {
mx[u] = mx2[u] = 0;
for (auto v : adj[u]) if (v != fa) {
d[v] = d[u] + 1, dfs(v, u);
if (mx[v] + 1 > mx[u]) mx2[u] = mx[u], mx[u] = mx[v] + 1;
else if (mx[v] + 1 > mx2[u]) mx2[u] = mx[v] + 1;
}
f[d[u] + mx2[u]] = max(f[d[u] + mx2[u]], mx2[u] + mx[u]);
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) adj[i].clear();
fill(f, f + 1 + n, 0);
for (int i = 1, x, y; i < n; i++)
scanf("%d%d", &x, &y), adj[x].pb(y), adj[y].pb(x);
dfs(1, 0);
for (int i = mx[1] - 1; i >= 0; i--) f[i] = max(f[i + 1], f[i]);
for (int i = 1, j = 0; i <= n; i++) {
while (j < mx[1] && (f[j + 1] + 1) / 2 + i > j) j++;
printf("%d ", j);
}
printf("\n");
}
return 0;
}
CF1634E&F 题解
E没什么好解的，注意欧拉回路只能搜一个连通块（因为这个我调了n年）看来以后还是要冷静冷静再冷静。
code:
#include<bits/stdc++.h>
using namespace std;
const int M=200005;
int T;
vector<int> g[M<<2];
int tot,cnt[M<<2],a[M<<2],tmp[M<<3],ans[M<<4],top,vis[M<<3];
map<pair<int,int>,int> mp;
vector<int> edge[M<<3],res[M<<3];
vector<int> lac[2][M<<3];
void Euler(int u){
while(1){
while(tmp[u]<edge[u].size()&&!mp[make_pair(u,edge[u][tmp[u]])])tmp[u]++;
if(tmp[u]>=edge[u].size())break;
int v=edge[u][tmp[u]];
mp[make_pair(u,v)]--;
mp[make_pair(v,u)]--;
++tmp[u];
Euler(v);
}
ans[++top]=u;
vis[u]=1;
}
int main(){
cin>>T;
int i,j;
for(i=1;i<=T;i++){
int n;
scanf("%d",&n);
for(j=1;j<=n;j++){
int x;
scanf("%d",&x);
g[i].push_back(x);
a[++tot]=x;
}
}
sort(a+1,a+tot+1);
tot=unique(a+1,a+tot+1)-a-1;
for(i=1;i<=T;i++){
for(j=0;j<g[i].size();j++){
int w=g[i][j];
g[i][j]=lower_bound(a+1,a+tot+1,w)-a;
cnt[g[i][j]]++;
edge[i].push_back(T+g[i][j]);
edge[T+g[i][j]].push_back(i);
mp[make_pair(i,T+g[i][j])]++,mp[make_pair(T+g[i][j],i)]++;
lac[0][g[i][j]].push_back(i);
lac[1][g[i][j]].push_back(j);
}
}
for(i=1;i<=tot;i++){
if(cnt[i]&1){
puts("NO");
return 0;
}
}
puts("YES");
for(i=1;i<=T+tot;i++)
sort(edge[i].begin(),edge[i].end());
for(i=1;i<=T+tot;i++)
if(!vis[i])Euler(i);
for(i=top;i>=2;i--)
if(ans[i]<=T&&ans[i-1]>T)
res[ans[i-1]-T].push_back(ans[i]);
for(i=1;i<=tot;i++){
sort(res[i].begin(),res[i].end());
int k=0;
for(j=0;j<lac[0][i].size();j++){
if(lac[0][i][j]==res[i][k]){
g[lac[0][i][j]][lac[1][i][j]]=-1;
if(k<res[i].size()-1)k++;
else{break;}
}
}
}
for(i=1;i<=T;i++){
for(j=0;j<g[i].size();j++)
putchar(g[i][j]==-1?'L':'R');
putchar('\n');
}
return 0;
}
F
惊了，原来根本不用ds
设$C_i=A_i-B_i$
$D_i=C_i-C_{i-1}-C_{i-2}$
当且仅当D_i全为0时，答案为YES
考虑加一段对D_i的影响
Dl will increase by 1,
Dr+1 will decrease by Fr−l+2, and
Dr+2 will decrease by Fr−l+1.
Fibonacci addition on B can be handled in a similar way.
看来ds题还是要先想差分
P8118
其实不用左偏树，看一下三倍经验(P4331、P2893)的第一篇题解，发现DP过程可以通过大根堆来优化。这样不仅更好写，而且更加方便后续的min。
读入的时候把Ai -= k*i,就是原题了
然后每次要取个后缀最小值，这个直接做显然T飞（当然我不知道有没有什么高明做法）。于是反过来对每个ai，求取到哪个前缀的时候可以使ai开始小于bi,差分一下就行了。
线段树上二分，直接单log解决
[JRKSJ R4] risrqnis 题解
人在西安，刚下高铁qwq。
暴力算法（sub0）:
离散化，用并查集维护当前值域连续段，新增的一段值域暴力加入这个值对应的下标，树状数组上+1，询问内直接区间求和。
O(nmlogq)
根号分治：
- 对于连续段数<= sqrt q 的, 离线二维数点，使用O(sqrt)修改，O(1)查询的分块
- 对于连续段数> sqrt q 的，用暴力算法，将树状数组换成O（1）修改,O(sqrt)查询的分块。
O((n+q)(sqrt n+ sqrt q))
人在西安，刚下高铁qwq。
暴力算法（sub0）:
离散化，用并查集维护当前值域连续段，新增的一段值域暴力加入这个值对应的下标，树状数组上+1，询问内直接区间求和。
O(nmlogq)
根号分治：
- 对于连续段数<= sqrt q 的, 离线二维数点，使用O(sqrt)修改，O(1)查询的分块
- 对于连续段数> sqrt q 的，用暴力算法，将树状数组换成O（1）修改,O(sqrt)查询的分块。
O((n+q)(sqrt n+ sqrt q))
其实不用左偏树，看一下三倍经验(P4331、P2893)的第一篇题解，发现DP过程可以通过大根堆来优化。这样不仅更好写，而且更加方便后续的min。
读入的时候把Ai -= k*i,就是原题了
然后每次要取个后缀最小值，这个直接做显然T飞（当然我不知道有没有什么高明做法）。于是反过来对每个ai，求取到哪个前缀的时候可以使ai开始小于bi,差分一下就行了。
线段树上二分，直接单log解决