GJ Round

前言：

GJ Round 为学校内部模拟赛

记 7.13 为 Round 1，在此之前的模拟赛较为混乱以后再说（可能记为 Round 0 或者负数）

目前正在倒序更新

https://www.luogu.com.cn/article/a30ffmdb

Round 20 (9.18)

\(\mathcal A\)

简单数学题

考虑将每一个 \(a_i\) 分别拆开计算贡献计算对应的 \(a_i=i\) 时所产生的贡献即可

答案即为 \(ans=\sum_{i=1}^{n} ({i-1 \choose a_i-1} \times 2^{n-i}) \pmod {10^9+7}\)

#include<bits/stdc++.h>
#define int long long
#define lowbit(x) (x&-x)
using namespace std;
const int N=2e5+5,mod=1e9+7;
int n,a[N],fac[N],inv[N],pw2[N];
int fpm(int a,int b)
{int res=1;while(b){if(b&1) res=res*a%mod;a=a*a%mod;b>>=1;}return res;
}
int C(int n,int k)
{return (k>n||n<0||k<0)?0:fac[n]*inv[n-k]%mod*inv[k]%mod;
}
void init()
{fac[0]=pw2[0]=1;for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod,pw2[i]=pw2[i-1]*2%mod;inv[n]=fpm(fac[n],mod-2);for(int i=n;i;i--) inv[i-1]=inv[i]*i%mod;
}
signed main()
{
//	freopen("ex_seq.in","r",stdin);
//	freopen("ex_seq.out","w",stdout);scanf("%lld",&n);init();for(int i=1;i<=n;i++) scanf("%lld",a+i);sort(a+1,a+1+n);int ans=0;for(int i=1;i<=n;i++) ans=(ans+C(i-1,a[i]-1)*pw2[n-i]%mod)%mod;printf("%lld",ans);return 0;
}

\(\mathcal B\)

按顺序从 \(1\) 到 \(n\) 拿盘子，对于每个盘子，你可以选择不要，也可以拿走，但拿走盘子需要满足下面三个条件至少一个：

• 之前没有拿过盘子；

• 这个盘子的尺寸比之前拿走的盘子的都大，这样你就可以把之前买的盘子叠在它的上面；

• 这个盘子的尺寸比之前拿走的盘子的都小，这样你就可以把它叠在之前买的盘子的上面。

最后，你想知道，你最多能拿走多少个盘子？

从结尾开始做最长上升和最长下降子序列，二分或线段树优化 dp 即可

#include<bits/stdc++.h>
#define ls u<<1
#define rs u<<1|1
using namespace std;
const int N=1e5+5;
int n,f[N],g[N],a[N],b[N];
struct SGT
{int t[N<<2];void push_up(int u){t[u]=max(t[ls],t[rs]);}void update(int u,int l,int r,int x,int k){if(x<l||r<x) return;if(x==l&&r==x){t[u]=k;return;}int mid=(l+r)>>1;if(x<=mid) update(ls,l,mid,x,k);else update(rs,mid+1,r,x,k);push_up(u);}int query(int u,int l,int r,int x,int y){if(y<l||r<x) return 0;if(x<=l&&r<=y) return t[u];int mid=(l+r)>>1,res=0;if(x<=mid) res=max(res,query(ls,l,mid,x,y));if(y>mid) res=max(res,query(rs,mid+1,r,x,y));return res;}	
}T1,T2;
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",a+i),b[i]=a[i];sort(b+1,b+1+n);int len=unique(b+1,b+1+n)-b-1;for(int i=n;i;i--){a[i]=lower_bound(b+1,b+1+len,a[i])-b;int x=(1<=a[i]-1?T1.query(1,1,n,1,a[i]-1):0);int y=(a[i]+1<=n?T2.query(1,1,n,a[i]+1,n):0);f[i]=x+1,g[i]=y+1;T1.update(1,1,n,a[i],f[i]);T2.update(1,1,n,a[i],g[i]);}int ans=0;for(int i=1;i<=n;i++) ans=max(ans,f[i]+g[i]-1);printf("%d",ans);return 0;
}

时间复杂度 \(\mathcal O(n \log n)\)

\(\mathcal C\)

CF875F Royal Questions

考虑将平面内的每一行每一列连边

求最大权值基环森林

跟最大生成树差不多，用 Kruskal 跑再稍微改一下就差不多了

时间复杂度 \(O(nm (\log n+\log m))\)

\(\mathcal D\)

天道酬勤，你已经精通了 OI。

你认为 OI 的学习可以分为 \(n\) 个阶段，在经历第 \(i\) 个阶段时，如果自身能力值大于 \(a_i\)，那么就可以得到 \(b_i\) 的进步，也就是能力值累加上 \(b_i\)。

并不是每个 Oler 都会完整的走完 \(n\) 个阶段，你观察了 \(q\) 个 Oler，第 \(i\) 个 Oler 会带着 \(x_i\) 的初始能力值依次经历第 \(l_i,l_{i+1},\dots,r_i\) 个阶段。

他们都还在路上，而你想知道他们最终会变得多强，也就是经历完这些阶段后的能力值。

由于某些原因，有时候你急切的想知道答案。

数据结构（DS）题

咕咕咕

Round 21 (9.19)

\(\mathcal A\)

SB 题，还什么困难卷积

不同的 \(a_i,b_i\) 只有 \(\mathcal O(\sqrt{sum})\) 个，排序去重模拟即可

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e6+5;
int n,a[N],b[N],f[N],g[N];
signed main()
{scanf("%lld",&n);for(int i=1;i<=n;i++) scanf("%lld",a+i),f[a[i]]++;for(int i=1;i<=n;i++) scanf("%lld",b+i),g[b[i]]++;sort(a+1,a+1+n),sort(b+1,b+1+n);int A=unique(a+1,a+1+n)-a-1,B=unique(b+1,b+1+n)-b-1;int ans=0;for(int i=1;i<=A;i++)for(int j=1;j<=B;j++)ans+=(int)sqrt(abs(a[i]-b[j]))*f[a[i]]*g[b[j]];printf("%lld",ans);return 0;
}
/*
4
1 2 3 4
2 3 3 312
*/

\(\mathcal B\)

CF623C Electric Charges

二分答案，预处理前后缀最大最小值，分别对于 \(x\) 和 \(y\) 得到极长段来求答案

\(\mathcal C\)

数论题，不会做

\[ans=\sum_{i=0}^{p-1} a_i \times m^i \pmod p\\ p \in {Prime},m \in [1,p),a_0=1,a_1=1,a_2=6 ,\dots \]

\(a_i\) 是杨辉三角中间对称轴的那一列

咕咕咕

\(\mathcal D\)

红茶国有 \(m\) 个部落，为了争夺 \(n\) 个有灵气的矿洞里的资源，部落之间经常发生冲突。矿洞被标号为 \(1\) 到 \(n\)，每个矿洞初始都被至多一个部落所占领。平时的矿洞里没有任何有价值的资源，珍贵之物只有在特定的时候才会出现，具体地，依次会有 \(q\) 次事件发生，每次事件形如：

• 1 l r x：\(x\) 号部落发起战争，占领了编号为 \(l\) 到 \(r\) 的矿洞，原先占有这些矿洞的部落将会失去它们，转而由 \(x\) 号部落来占领；

• 2 l r x：编号为 \(l\) 到 \(r\) 的矿洞灵气爆发，都出现了价值为 \(x\) 的宝物。

一旦一个部落占领的矿洞里有宝物，宝物会立即被全部取走。为了知道哪些部落能成为王，你需要求出 \(q\) 次事件发生之后，每个部落分别得到的宝物的价值总和。

数据结构（DS）题

赛时着真做结果因为复杂度写假了T飞了

听说正着写能用 set 维护颜色段，但笔者不会

由于没有强制在线，可以考虑时光倒流，这样就不用考虑正着做部落具有占领权这一问题，那就基本上是区间加、区间覆盖、区间查询的模板线段树题

最后再把一开始部落占有的矿洞再 query \(m\) 次就好了

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define int long long
#define ls u<<1
#define rs u<<1|1
using namespace std;
const int N=5e5+5;
int a[N],ans[N];
int n,m,Q;
int t[N<<2],tag[N<<2],cov[N<<2];
void push_up(int u)
{t[u]=t[ls]+t[rs];
}
void build(int u,int l,int r)
{cov[u]=-1;if(l==r) return;int mid=(l+r)>>1;build(ls,l,mid);build(rs,mid+1,r);push_up(u);
}
void push_down(int u,int l,int r)
{if(~cov[u]){cov[ls]=cov[rs]=cov[u];tag[ls]=tag[rs]=0;t[ls]=t[rs]=cov[u];cov[u]=-1;}if(!tag[u]) return;tag[ls]+=tag[u],tag[rs]+=tag[u];int mid=(l+r)>>1;t[ls]+=tag[u]*(mid-l+1);t[rs]+=tag[u]*(r-mid);tag[u]=0;
}
void update(int u,int l,int r,int x,int y,int k)
{if(y<l||r<x) return;if(x<=l&&r<=y){t[u]+=(r-l+1)*k;tag[u]+=k;return;}push_down(u,l,r);int mid=(l+r)>>1;if(x<=mid) update(ls,l,mid,x,y,k);if(y>mid) update(rs,mid+1,r,x,y,k);push_up(u);
}
void modify(int u,int l,int r,int x,int y,int k)
{if(y<l||r<x) return;if(x<=l&&r<=y){t[u]=cov[u]=k;tag[u]=0;return;}push_down(u,l,r);int mid=(l+r)>>1;if(x<=mid) modify(ls,l,mid,x,y,k);if(y>mid) modify(rs,mid+1,r,x,y,k);push_up(u);
}
int query(int u,int l,int r,int x,int y)
{if(y<l||r<x) return 0;if(x<=l&&r<=y) return t[u];push_down(u,l,r);int mid=(l+r)>>1,res=0;if(x<=mid) res+=query(ls,l,mid,x,y);if(y>mid) res+=query(rs,mid+1,r,x,y);return res;
}
struct dat
{int opt,x,y,k;
}p[N];
signed main()
{
//	freopen("king.in","r",stdin);
//	freopen("king.out","w",stdout);scanf("%lld%lld%lld",&n,&m,&Q);for(int i=1;i<=n;i++) scanf("%lld",a+i);build(1,1,n);for(int i=1;i<=Q;i++) scanf("%lld%lld%lld%lld",&p[i].opt,&p[i].x,&p[i].y,&p[i].k);for(int i=Q;i;i--){int opt=p[i].opt,x=p[i].x,y=p[i].y,k=p[i].k;if(opt&1){ans[k]+=query(1,1,n,x,y);modify(1,1,n,x,y,0);continue;}update(1,1,n,x,y,k);}for(int i=1;i<=n;i++) ans[a[i]]+=query(1,1,n,i,i);for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);return 0;
}

Round 22 (9.24)

\(\mathcal A\)

小模拟麻将题

• 先考虑 \(n=14\)

  若 \(k=2\) 只考虑顺子和雀头

  若 \(k=3,4\) 枚举雀头再检验剩下的牌是刻子还是顺子

• 在考虑 \(n=13\)

  显然可以枚举最后一张牌，然后就用 \(n=14\) 时的方法做就好

\(\mathcal B\)

人类智慧题

发现 \(0 \leq y_i \leq 10\)，可以先按 \(x_i\) 从小到大排序，然后发动人类智慧，每个点只连它前面的 \(20\) 个点，然后跑最小生成树，做完了

时间复杂度 \(\mathcal O(n \log n)\)

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,M=2e6+5;
int n,cnt,fa[N],siz[N];
struct dat
{int x,y;
}p[N];
bool cmp(const dat &a,const dat &b)
{return a.x^b.x?a.x<b.x:a.y<b.y;
}
int dis(int a,int b,int x,int y)
{return (a-x)*(a-x)+(b-y)*(b-y);
}
struct Edge
{int u,v,w;
}e[M];
bool cmpe(const Edge &a,const Edge &b)
{return a.w<b.w;
}
int find(int x)
{return fa[x]==x?x:fa[x]=find(fa[x]);
}
int Kruskal()
{int tot=0,mst=0;for(int i=1;i<=n;i++) fa[i]=i,siz[i]=1;sort(e+1,e+1+cnt,cmpe);for(int i=1;i<=cnt;i++){int x=find(e[i].u),y=find(e[i].v);if(x==y) continue;if(siz[x]<siz[y]) swap(x,y);fa[y]=x;siz[x]+=siz[y];mst+=e[i].w;if(++tot==n-1) break;}return mst;
}
signed main()
{
//	freopen("ant.in","r",stdin);
//	freopen("ant.out","w",stdout);scanf("%lld",&n);for(int i=1;i<=n;i++) scanf("%lld%lld",&p[i].x,&p[i].y);sort(p+1,p+1+n,cmp);for(int i=1;i<=n;i++)for(int j=i+1;j<=min(i+20,n);j++)e[++cnt]=(Edge){i,j,dis(p[i].x,p[i].y,p[j].x,p[j].y)};printf("%lld",Kruskal());return 0;
}

\(\mathcal C\)

咕咕咕

\(\mathcal D\)

咕咕咕

Round 23 (9.27)

\(\mathcal A\)

求概率题，也就模数换成了 \(147744151\) (还好是质数)

\(\mathcal B\)

类似于是换根 dp

先跑两次 dfs 求一下树的直径，先以 \(1\) 为根跑一次统计转向边的数量，再跑一次 dfs 换根就贡献即可

时间复杂度 \(\mathcal O(n)\)，不知道题解在干什么搞倍增带一只 \(\log\)

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define eb emplace_back
using namespace std;
const int N=2e5+5,INF=0x3f3f3f3f;
int n,D,dis1[N],dis2[N],cst[N],ans,sum;
struct Edge
{int v,w,c;
};
vector <Edge> g[N];
void dfs1(int u,int fa)
{for(auto [v,w,c]:g[u]){if(v==fa) continue;dis1[v]=dis1[u]+w;dfs1(v,u);}
}
void dfs2(int u,int fa)
{for(auto [v,w,c]:g[u]){if(v==fa) continue;sum+=c;dfs2(v,u);}
}
void dfs3(int u,int fa,int s)
{if(dis1[u]<=D&&dis2[u]<=D) ans=min(ans,s);for(auto [v,w,c]:g[u]){if(v==fa) continue;dfs3(v,u,s+(c==1?-1:1));}
}
int main()
{
//	freopen("ex_b1.in","r",stdin);
//	freopen("ex_b1.out","w",stdout);scanf("%d%d",&n,&D);for(int i=1;i<n;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);g[u].eb((Edge){v,w,1});g[v].eb((Edge){u,w,0});}int x=0;dfs1(1,0);for(int i=1;i<=n;i++)if(dis1[i]>dis1[x]) x=i;dis1[x]=0;dfs1(x,0);memcpy(dis2,dis1,sizeof(dis1));for(int i=1;i<=n;i++)if(dis1[i]>dis1[x]) x=i;dis1[x]=0;dfs1(x,0);dfs2(1,0);ans=INF;dfs3(1,0,sum);printf("%d",ans==INF?-1:ans);return 0;
}
/*
6 8
2 1 1
2 3 3
2 4 6
1 5 5
6 1 3
*/

\(\mathcal C\)

神秘题，在序列 \(a\) 的区间 \([l,r]\) 中选 \(k\) 个数，最大化 \(\gcd(b_1,b_2,\dots,b_k)\)

令 \(k^\prime \gets (r-l+1)-k\)，然后不会

\(\mathcal O(n \log^4 V)\) 真能过吗

咕咕咕

\(\mathcal D\)

咕咕咕

Round 24 (9.29)

\(\mathcal A\)

结论题，不过一开始没能立刻看出条件其实推下去就是对于 \(\forall i \in [1,n]\) 都满足

就跟奇偶性有关

\(\mathcal B\)

有点意思，需要选出来的数中 \(\forall i,j \in [L,R],a_i \mid a_j \lor a_j \mid a_i\)

较为简单的数论题，从最大值 \(maxa\) 到 \(1\) 一直枚举，然后进 dfs 剪枝求答案即可

\(\mathcal C\)

咕咕咕

\(\mathcal D\)

咕咕咕

\(\mathcal E\)

咕咕咕

Round 25 (10.5)

\(\mathcal A\)

先按 \(l_i\) 从小到大排序，再按 \(r_i\) 从小到大排序

考虑贪心，维护两个小根堆，一个是已匹配的，一个是未匹配的

能匹配的就匹配（废话），不能匹配的从已匹配的中找一个小一点 \(r_j\) 来匹配就好

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define VI vector<int>::iterator
#define PII pair<int,int>
#define mp make_pair
using namespace std;
const int N=4e5+5,INF=0x3f3f3f3f;
int n,ans;
struct dat
{int l,r;
}a[N];
bool cmp(dat a,dat b)
{return a.l^b.l?a.l<b.l:a.r<b.r;
}
priority_queue<PII,vector<PII>,greater<PII>> X,Y;
int main()
{
//	freopen("a.in","r",stdin);
//	freopen("a.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d%d",&a[i].l,&a[i].r);sort(a+1,a+1+n,cmp);for(int i=1;i<=n;i++){if(!Y.empty()&&Y.top().first<a[i].l){Y.pop();X.push(mp(a[i].r,a[i].l));}else if(!X.empty()&&X.top().first<a[i].r){Y.push(X.top()),X.pop();X.push(mp(a[i].r,a[i].l));}else Y.push(mp(a[i].r,a[i].l));}printf("%d",X.size());return 0;
}

\(\mathcal B\)

咕咕咕

\(\mathcal C\)

咕咕咕

\(\mathcal D\)

咕咕咕

Round 26 (10.6)

\(\mathcal A\)

简单数学题，求方程有整数解 \(x^2-2Bx+C=0,(B,C)\) 的对数

#pragma GCC optimize (3,"Ofast","inline")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int T,a[N];
signed main()
{
//	freopen("equation.in","r",stdin);
//	freopen("equation.out","w",stdout);for(int i=0;i<=1e6;i++)for(int j=i;j>=0;j--){if(i*i-j*j>1e6) break;a[i*i-j*j]++;}for(int i=1;i<=1e6;i++) a[i]+=a[i-1];scanf("%lld",&T);while(T--){int L,R;scanf("%lld%lld",&L,&R);printf("%lld\n",a[R]-a[L-1]);}return 0;
}
/*
sqrt(B^2-C) = Z
B^2-C=x^2
*/

\(\mathcal B\)

考虑归纳，因为 \(a_i=i\) 会变成不动点，所以在交换的过程中可能需要错排，而错排是有解的

\(\mathcal C\)

洛谷 P6864 [RC-03] 记忆

很好的一道数据结构（DS）题

这题最重要是考虑到如何拆分序列以便于统计与更新答案

发现答案会与某些东西在每个操作都存在一定关系，那么可以试着上矩阵来维护，每次用线段树单点修改、区间查询即可

\(\mathcal D\)

真看不懂给的题解，咕咕咕

Round 27 (10.9)

\(\mathcal A\)

简单数论分块，过

\(\mathcal B\)

确实有点难推出结论

求 \(ax+by=c\) 非负整数对 \((x,y)\) 的个数，其中 \(a \in [0,N],y \in [0,M],x=Fib_{2k+1},y=_{2k+2},k \in \mathbb{N}\)

扩展欧几里得算法(exgcd)即可

用归纳法证明出 \(-Fib_iFib_{i-1}+Fib_{i+1}Fib_{i-2}=1\) 省去 exgcd 的 \(\log\)，笑死，笔者觉得不如观察输出对应的 \(\sout{(x,y)}\) 得出结论简单

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=105;
int T,n,Fib[maxn],X,N,M; 
int solve(int A,int B,__int128 x,__int128 y)
{x*=X,y*=X; x-=(-y+A-1)/A*B,y+=(-y+A-1)/A*A;if(x<0||y<0) return 0;if(x>N) y+=(x-N+B-1)/B*A,x-=(x-N+B-1)/B*B;if(y>M) x+=(y-M+A-1)/A*B,y-=(y-M+A-1)/A*A;if(x<0||y<0) return 0;if(x>N||y>M) return 0;return min(x/B,(M-y)/A)+min((N-x)/B,y/A)+1;
} 
signed main()
{int T;scanf("%lld",&T);Fib[1]=Fib[2]=1;for(int i=3;i<=100;i++) Fib[i]=Fib[i-1]+Fib[i-2];while(T--){scanf("%lld%lld%lld",&X,&N,&M);if(!X){puts("1");continue;}int ans=0;for(int i=1;i<=43;i++) ans+=solve(Fib[i*2-1],Fib[i*2],Fib[i*2-1],-Fib[i*2-2]); printf("%lld\n",ans);}return 0;
}
/*
6
10 6 9
11 9 2
17 7 5
183 54 20
1919 810 114514
1121135 421443 428543
*/

\(\mathcal C\)

AT_joisc2014_e 水筒

先跑一次 bfs 建图，然后跑 Kruskal 最小生成树得到重构树，最后在树上跳倍增 LCA 求答案即可

（思路与 洛谷 P1967 [NOIP2013 提高组] 货车运输 相似，就多了个 bfs 建图个过程）

\(\mathcal D\)

洛谷 P7363 [eJOI2020 Day2] Dots and Boxes

咕咕咕

Round 28 (10.10)

谴责 GJ 今天一开始只放一道题，名字叫做 \(\sout 5\) 道题

\(\mathcal A\)

简单结论题，\(a_1<a_n\) 就符合了，过

\(\mathcal B\)

普通树论题，但是不知道这个结论：划分成大小为 \(k\) 的连通块，当且仅当树上有 \(n/k\) 个点的 \(size\) 是 \(k\) 的倍数

\(\mathcal C\)

思路有点巧妙，暴力是 dp，发现每个物品的价值都很小，考虑大小约为 \(100 \times 100\) 矩阵快速幂加快递推

\(\mathcal D\)

不会，咕咕咕

\(\mathcal E\)

数论题，更加不会，看到答案是对 \(2^{32}\) 取模就知道不简单

挂个柿子以后再来补：

\[\begin{aligned} G(n) &= \prod_{i=1}^{n} (2i-1),G(0)=0 \\ ans &= \sum_{i=0}^{n} \sum_{j=0}^{m} G(i \operatorname{xor} j \operatorname{xor} x) \pmod {2^{32}} \end{aligned} \]

似乎要拆分贡献？

咕咕咕

Round 29 (10.11)

\(\mathcal A\)

傻波一小明就会做亏本买卖是吧

题目在下面写了个 \(u<v\)，才发现是有向无向图 \(DAG\),虽然不一定联通

考虑拓扑排序 + dp，时间复杂度 \(\mathcal O(n+m)\)

\(\mathcal B\)

找规律题，与杨辉三角挂钩

求的就是每一行前 \(a_i+1\) 个数的和，即第 \(a_i\) 列的值

答案为 $ \sum_{i=1}^{n+1} {i+a_i-1 \choose i} $

\(\mathcal C\)

AT_joisc2017_c 手持ち花火 (Sparklers)

所有人都向 \(k\) 号跑最优，考虑时光倒流，二分，check 里贪心，后面不会，咕咕咕

\(\mathcal D\)

有一棵 \(n\) 个点的树，带有边权。现有 \(m\) 个询问如下：在树上选取 \(k_i\) 条路径（树上任意两点的连接通路视为一条路径），其中至少要有一条路径覆盖到点 \(a_i\)，问所有被路径覆盖的边权的和最大是多少。注意重复覆盖的边只会计算一次。

树上问题，不容易发现答案包含直径某一端点，长链剖分，后面不会，咕咕咕

Round 30 (10.14)

\(\mathcal A\)

你作为一名寻宝者，来到了一个古老而神奇的城堡。城堡由多个房间组成，房间之间由墙壁隔开，从一个房间到另一个房间唯一的方法就是任意门传送。

城堡的地图可以由一个 \(n\) 行 \(m\) 列的网格图表示，每个格子可能是空间区域（用 \(1\) 表示）或墙壁区域（用 \(0\) 表示）。任意两个共享一边的空间区域被认为属于同一个房间。

你可以由一个空间区域 \((x_1,y_1)\) 前往另一个空间区域 \((x_2,y_2)\)。

• 操作 \(1\) - 步行：如果 \((x_1,y_1)\) 和 \((x_2,y_2)\) 属于同一个房间，那么你可以花费 \(0\) 体力直接从 \((x_1,y_1)\) 走到 \((x_2,y_2)\)

• 操作 \(2\) - 任意门传送：如果 \((x_1,y_1)\) 和 \((x_2,y_2)\) 不属于同一个房间，那么你可以花费 \(|x_1-x_2|+|y_1-y_2|\) 的体力从 \((x_1,y_1)\) 传送至 \((x_2,y_2)\)

注意，如果 \((x_1,y_1)\) 和 \((x_2,y_2)\) 属于同一个房间，你只能选择步行前往，不能通过传送前往。

现在，你计划从位置 \((x_s,y_s)\) 前往位置 \((x_t,y_t)\)，你可以进行任意多次步行和任意门传送。你可以重复经过同一个房间、也可以重复经过同一个空间区域。

为了更好的体验任意门的奇妙感觉，你希望使用传送的次数尽可能多。同时，你所消耗的体力值不能超过直接传送体力值：定义直接传送体力值为至多经过一次传送到达 \((x_t,y_t)\) 的最小体力值消耗。

你想知道，从 \((x_s,y_s)\) 前往任意一个空间区域，在所消耗的体力值不超过直接传送体力值的前提下，最多能够使用多少次传送？

难绷，上来就搞神秘 bfs 题，不会，咕咕咕

\(\mathcal B\)

CF1310E Strange Function

模拟赛上 CF *2900 dp 也是只有 GJ 敢这么干的

（题外话：赛时 puts("1"); 有 \(28\) pts 真不错「伏笔」）

考虑分类讨论

• \(k=1\) 时，将 \(n\) 个元素划分，上个背包就好

• \(k=2\) 时，对最终序列从大到小排序，差分再上背包就好

• \(k>2\) 时，因为答案已经不多了，所以直接搜索剪枝就过了（这就是为啥能总司令了~）

\(\mathcal C\)

构造题

构造每一行形如 $\underline{ryxy} \dots \underline{ryxy} $、大小为 \(40 \times 40\) 的矩阵就好了再把最后一列也这样搞，刚好是 \(2223\) 个，比法定最大 \(n\) 还多 \(1\) 个

然后就交给随机化每次随机更改一个位置求贡献就好了

时间复杂度：\(\mathcal O(Tm^2)\)，其中 \(T=rand(),m=40\)，理论上 \(T ∝ \frac{1}{n}\)

#include<bits/stdc++.h>
#define R 1
#define Y 2
#define X 3
using namespace std;
const int N=45;
const int dx[8]={-1,1,0,0,-1,1,-1,1};
const int dy[8]={0,0,-1,1,-1,1,1,-1};
int n,a[N][N],b[N][N];
int query()
{int res=0;for(int i=1;i<=40;i++)for(int j=1;j<=40;j++)for(int k=0;k<=6;k+=2){if(a[i][j]!=Y) break;int A=a[i+dx[k]][j+dy[k]];int B=a[i+dx[k+1]][j+dy[k+1]];if(A==R&&B==X) res++;if(A==X&&B==R) res++;}return res;
}
mt19937 rd(time(NULL));
int rnd(int l,int r)
{return rd()%(r-l+1)+l;
}
void init()
{for(int i=1;i<=40;i++)for(int j=1;j<=37;j+=4)a[i][j]=R,a[i][j+1]=Y,a[i][j+2]=X,a[i][j+3]=Y;for(int i=1;i<=37;i+=4)a[i][40]=R,a[i+1][40]=Y,a[i+2][40]=X,a[i+3][40]=Y;
}
int main()
{scanf("%d",&n);init();memcpy(b,a,sizeof(a));printf("40 40\n");while(query()>n){int x=rnd(1,40),y=rnd(1,40);a[x][y]=X;if(query()<n) a[x][y]=b[x][y];}for(int i=1;i<=40;i++){for(int j=1;j<=40;j++)	printf("%c",a[i][j]==R?'r':a[i][j]==Y?'y':'x');printf("\n");}return 0;
}

\(\mathcal D\)

对排列 \(\lbrace s_n \rbrace\)，定义 \(g(k,i)=\min(s_i,s_{i+1}, \dots ,s_{i+k-1}),G(k)=\max_{i=1}^{n-k+1} g(k,i)\)

现给出 \(G(1),G(2), \dots ,G(n)\)，求有多少个满足要求的排列。

注：排列 \(\lbrace s_n \rbrace\) 指 \(1\) 到 \(n\) 的 \(n\) 个整数按照任意顺序排成一列后得到的序列，\(s_i\) 表示排在第个位置的数字。例如当 \(n=3\) 时表示长度为 \(3\) 的排列，共有 \(6\) 种可能，分别是：

\(\lbrace1,2,3\rbrace,\lbrace1,3,2\rbrace,\lbrace2,1,3\rbrace,\lbrace2,3,1\rbrace,\lbrace3,1,2\rbrace,\lbrace3,2,1\rbrace\)

咕咕咕

Round 31 (10.17)

我生活在一个绑包的世界里

谴责 GJ 不通知有模拟赛，\(-1.5h\) 打模拟赛时间

\(\mathcal A\)

入机题，模拟即可

一开始还被求最大操作次数给诈骗了

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n;
char st[N];
int main()
{scanf("%s",st+1),n=strlen(st+1);int ans=0;for(int i=2;i<=n;i++){int x=st[i-1]-'0'+st[i]-'0';if(x<=9) st[i]='0'+x,ans++;else st[i-1]='0'+x/10,st[i]='0'+x%10,ans++,i--;}printf("%d",ans);return 0;
}

\(\mathcal B\)

不仅 \(200\) 个点还绑包？

构造题，可参考 AT_abc358_f Easiest Maze，但不是完全一样，还是有点差异的

上下界还是有一定难度想到，毕竟赛后才知道那个 \(2 \mid n, 2 \mid m\) 会使下界 \(+1\)

上界可以考虑直接螺转，下界可以考虑弄一些竖线，然后横着来一刀就差不多了

\(\mathcal C\)

表达式求值的方案数

甚至觉得比 [CSP-J 2022] 逻辑表达式 那题会简单一点，根本不用考虑优先级，全部运算似乎都会用一对 () 包着

开两个栈，一个记 \(0\) 和 \(1\) 的方案数，另一个记运算符，每遇到一个 ) 就计算一次贡献即可

做完了，时间复杂度 \(\mathcal O(n)\)

可以不用像题解那样建表达式树

#include<bits/stdc++.h>
#define int long long
#define mp make_pair
#define PII pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=1e6+5,mod=998244353;
int n;
char st[N];
stack<PII> ans;
stack<char> opt;
int mul(int x,int y)
{return x*y%mod;
}
int add(int x,int y)
{return x+y>=mod?x+y-mod:x+y;
}
signed main()
{scanf("%s",st+1),n=strlen(st+1);for(int i=1;i<=n;i++){if(st[i]=='0') ans.push(mp(1,0));if(st[i]=='1') ans.push(mp(0,1));if(st[i]=='?') ans.push(mp(1,1));if(st[i]=='&'||st[i]=='|'||st[i]=='^'||st[i]=='#') opt.push(st[i]);if(st[i]==')'){PII x=ans.top();ans.pop();PII y=ans.top();ans.pop();char op=opt.top();opt.pop();PII res={0,0};if(op=='&'||op=='#'){res.fi=add(add(res.fi,mul(x.fi,y.fi)),add(mul(x.fi,y.se),mul(x.se,y.fi)));res.se=add(res.se,mul(x.se,y.se));}if(op=='|'||op=='#'){res.fi=add(res.fi,mul(x.fi,y.fi));res.se=add(add(res.se,mul(x.fi,y.se)),add(mul(x.se,y.fi),mul(x.se,y.se)));}if(op=='^'||op=='#'){res.fi=add(res.fi,add(mul(x.fi,y.fi),mul(x.se,y.se)));res.se=add(res.se,add(mul(x.fi,y.se),mul(x.se,y.fi)));}ans.push(res);}}printf("%lld",ans.top().se);return 0;
}

\(\mathcal D\)

在二维平面上有 \(n\) 个点，第 \(i\) 个点 \((x_i,y_i)\) 有权值 \(w_i\)。

可以进行若干次这样的操作：选择两个点 \(u,v\)，将 \(u\) 的权值一部分 \(\Delta w\) 加给 \(v\)，但是要承受 \(d=\sqrt{(x_u-x_v)^2+(y_u-y_v)^2}\) 的损失，即两点间的欧几里得距离。也就是 \(w_u-= \Delta w,w_v+= \max(0,\Delta w-d)\)。

现在你希望所有点中最小的权值的最大，并求出该值。

两点间每操作一次，显然全局点权总和会减少，即 \(\sum w \gets \sum w - \sqrt{(x_u-x_v)^2+(y_u-y_v)^2}\)，那么两点间显然只会操作最多一次

进一步地，操作可以形成一棵树或是森林，且同一个连通块 \(\lvert V \rvert\) 内的最大值为 \(\frac{\sum_{u \in V} w_u - mst}{\lvert V \rvert }\)，其中 \(mst\) 为连通块 \(\lvert V \rvert\) 的最小生成树，上界易证

那么可以先状压求出每个连通块的点权，再 dp 即可

时间复杂度 \(\mathcal O(2^n (n^2+n \log n))\)

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define double long double
using namespace std;
const int N=21,M=N*N;
int n,fa[N];
double dis[N][N],dp[(1<<16)+5];
struct dat
{int x,y;double w;
}a[N];
int cnt;
struct Edge
{int u,v;double w;
}e[M];
bool cmp(Edge a,Edge b)
{return a.w<b.w;
}
int find(int x)
{return fa[x]==x?x:fa[x]=find(fa[x]);
}
double distance(dat a,dat b)
{return sqrt(1.0*(a.x-b.x)*(a.x-b.x)+1.0*(a.y-b.y)*(a.y-b.y));
}
double Kruskal()
{int tot=0;double mst=0;for(int i=1;i<=n;i++) fa[i]=i;sort(e+1,e+1+cnt,cmp);for(int i=1;i<=cnt;i++){int x=find(e[i].u),y=find(e[i].v);if(x==y) continue;fa[y]=x,mst+=e[i].w;if(++tot==n-1) break;}return mst;
}
int main()
{
//	freopen("desert.in","r",stdin);
//	freopen("desert.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d%d%Lf",&a[i].x,&a[i].y,&a[i].w);for(int i=1;i<n;i++)for(int j=i+1;j<=n;j++) dis[i][j]=distance(a[i],a[j]);int S=(1<<n)-1;for(int i=0;i<=S;i++){double sum=0;int siz=0;cnt=0;for(int j=1;j<=n;j++)if(i&(1<<(j-1))) sum+=a[j].w,siz++;for(int j=1;j<n;j++)for(int k=j+1;k<=n;k++)if(i&(1<<(j-1))&&i&(1<<(k-1)))e[++cnt]=(Edge){j,k,dis[j][k]};double mst=Kruskal();dp[i]=(sum-mst)/siz;}for(int i=0;i<=S;i++)for(int j=i;j;j=(j-1)&i)dp[i]=max(dp[i],min(dp[j],dp[j^i]));printf("%.10Lf",dp[S]);return 0;
}
/*
3
0 0 10
2 0 5
0 5 8
*/

Round 32 (10.18)

又是绑包。。。

\(\mathcal A\)

诈骗题，经过 \(\mathcal O(\log k)\) 次操作之后每个数变为 \(2k\) 或 \(2k+1\)

暴力枚举前 \(50\) 次总和即可，\(m>50\) 的基本都可以看做 \(m=50\)

\(\mathcal B\)

诈骗题，并且成功在赛时把我骗了

因为题目说保证有解且唯一，所以除了 \(s_0\) 会出现奇数次，其他会出现偶数次

所以直接输出出现奇数次的字符，开个桶计数即可

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n,len,cnt[31];
char st[N];
int main()
{
//	freopen("history.in","r",stdin);
//	freopen("history.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n<<1;i++){scanf("%s",st+1),len=strlen(st+1);for(int j=1;j<=len;j++) cnt[st[j]-'a'+1]++;}scanf("%s",st+1),len=strlen(st+1);for(int i=1;i<=len;i++) cnt[st[i]-'a'+1]--;for(int i=1;i<=26;i++)if(cnt[i]&1) return putchar('a'+i-1),0;
}
/*
2
abcabc
a
abc
b
abcb
*/

\(\mathcal C\)

咕咕咕

\(\mathcal D\)

咕咕咕

Round ? (10.19)

GJ 设成了 IOI 赛制 😃

真的没意思，没到两个小时就 AC 前三题了

前面 \(3\) 题比较简单，甚至 \(T3\) 我都做过原了。。。

\(T4\) 没看，puts("0"); 总司令 \(15\) 分走了

\(100+100+100+15=315\)，打得最爽也是最高分的一集

\(\mathcal A\)

入机数学题

显然对于每一个 \(b_i\) 取模，必有一个数 \(x\) 使得 \(\forall i \in [1,n],x \bmod b_i=b_i-1\)

那么答案就为 \(ans=\sum (b_i-1)\)

\(\mathcal B\)

洛谷 P3106 [USACO14OPEN] Dueling GPSs S

考虑反向建边，从 \(n\) 开始跑三次 Dijkstra做完了

\(\mathcal C\)

CF920F SUM and REPLACE

线段树板题

考虑先用线性筛 \(\mathcal O(N)\) 预处理 \(d(i)\)，然后每次暴力修改 \(a_i \gets d(a_i)\)

线段树再记个区间最大值 \(maxl\)，显然当 \(maxl \leq 2\) 时就不用再往下递归了

应该是要势能分析的，但是笔者不会，考虑到一个数被修改很少次就会变成 \(1\) 或 \(2\)，每个数最多会被修改 \(\mathcal O(\log n)\) 次

所以时间复杂度 \(O(n \log n)\)

同类型题目推荐：

• CF438D The Child and Sequence
• 洛谷 P4145 上帝造题的七分钟 2 / 花神游历各国

\(\mathcal D\)

咕咕咕