GJ Round
前言：
GJ Round 为学校内部模拟赛
记 7.13 为 Round 1，在此之前的模拟赛较为混乱以后再说（可能记为 Round 1 之前或者其他的）
目前正在倒序更新
博客园 可能食用更佳
Round 18 (9.10)
A
洛谷 P10059 Choose
不难发现结论：记长度为 \(L\) 时对应的 \(X\) 最大值为 \(f(L)\)，则 \(f(L)\) 单调不降
那么就可以考虑使用二分求出最小的 \(L\)，区间静态最值可以考虑使用 ST 表预处理或者使用单调队列，这里笔者使用了 ST 表
时间复杂度 \(\mathcal O(T n \log^2 n)\)，若使用单调队列则时间复杂度为 \(\mathcal O(T n \log n)\)
到这里可能需要卡卡常才能过，其实还有更优的时间复杂度
瓶颈在求 \(L\) 的最小值，对于每个长度 \(L\)，考虑记极差不小于 \(X\) 最大值的区间数为 \(c_L\)
不难发现，当左端点固定，右端点从左到右移动时，\(c_L\) 具有单调性，那是因为区间极差具有单调性
将左端点排序后，右端点具有单调性，那么可以考虑使用单调队列+双指针求解，因为每次都是连续的区间，故可以考虑使用差分数组辅助统计，最后再累加前缀和即可
时间复杂度 \(\mathcal O(Tn)\)
代码略
B
咕咕咕
C
咕咕咕
Round 19 (9.12)
A
形式化题意：给定两个长度分别为 \(n,m\) 的 \(0,1\) 序列 \(a,b\)
定义 \(c_{i,j}=a_i \times b_j\)，问 \(c\) 矩阵中有多少个子矩形满足其中 \(1\) 的个数恰好为 \(k\)
题目显然是问：有多少种方案，使得在 \(a\) 中连续选一段区间，包含 \(x\) 个 \(1\)，在 \(b\) 中连续选一个区间，包含 \(y\) 个 \(1\)，\(x \times y = k\)
考虑分别记录 \(1 \leq i \leq n,a_i=1\) 和\(1 \leq j \leq m,b_j=1\) 的位置，显然可以枚举 \(k\) 的因数，然后上桶和前缀和，做完了
时间复杂度（记 \(n,m\) 同阶） \(\mathcal O(n \times d(k))\)，其中，\(d(k)\) 表示 \(k\) 的因数的个数
const int N=1e5+5,mod=998244353;
int n,m,k,last,x[N],xlen,y[N],ylen,A[N],B[N];
signed main()
{
freopen("rain.in","r",stdin);
freopen("rain.out","w",stdout);
n=read(),m=read(),k=read();
last=0;
for(int i=1;i<=n;i++) if(read()) x[++xlen]=i-last,last=i;
x[xlen+1]=n+1-last;
last=0;
for(int i=1;i<=m;i++) if(read()) y[++ylen]=i-last,last=i;
y[ylen+1]=m+1-last;
int ans=0;
for(int i=1;i<=sqrt(k);i++)
{
if(k%i) continue;
int Len=k/i;
if(xlen<i&&ylen<Len&&xlen<Len&&ylen<i) break;
if(xlen>=i&&ylen>=Len)
{
int sumx=0,sumy=0;
for(int l=1,r=i;r<=xlen;l++,r++) sumx=(sumx+x[l]*x[r+1]%mod)%mod;
for(int l=1,r=Len;r<=ylen;l++,r++) sumy=(sumy+y[l]*y[r+1]%mod)%mod;
ans=(ans+sumx*sumy)%mod;
}
if(i*i==k) continue;
if(xlen>=Len&&ylen>=i)
{
int sumx=0,sumy=0;
for(int l=1,r=Len;r<=xlen;l++,r++) sumx=(sumx+x[l]*x[r+1]%mod)%mod;
for(int l=1,r=i;r<=ylen;l++,r++) sumy=(sumy+y[l]*y[r+1]%mod)%mod;
ans=(ans+sumx*sumy)%mod;
}
}
printf("%lld",ans);
return 0;
}
B
\(B\) 国有 \(n\) 座城市，有 \(m\) 条双向道路连接着这些城市。城市编号为 \(1\) 到 \(n\)，道路编号为 \(1\) 到 \(m\)。经由这些道路，从 \(B\) 国中任意一个城市出发，均能到达其他所有城市。特别地，这里保证 \(m \leq n\)。
由于能源不足，\(B\) 国的第 \(í\) 条道路只能正常运行 \(d_i\) 个时刻。现在云浅需要给每一条道路选择一个开始运行的时间 \(s_i\)，那么这条道路就会在 \([s_i，s_i+d_i-1]\) 这些时刻内正常运行。保证 \(d_i \geq 1\)
\(B\) 国的大守护者布洛妮娅想要让国家在尽可能长的一段时间内保持连通。形式化地，对于云浅选择的一种方案 \(s_1,s_2,\dots,s_m\)，定义其连通度为最大的正整数 \(A\)，使得对任意的 \(i=1,2,\dots,A\)，在第 \(i\) 个时刻，从 \(B\) 国的任意一个城市出发，只通过当前时刻仍在正常运行的道路，仍然可以到达任意另一个城市。大守护者希望找到连通度最大的方案。
随着 \(B\) 国的发展，现在 \(B\) 国已经可以对道路进行有限的能源扩充。具体地，大守护者可以给第 \(i\) 条道路扩充 \(a_i\) 个单位的能源，使得其最大运行时间 \(d_i\) 增大为 \(d_i+a_i\)。由于能源有限，\(a_1+a_2+\dots+a_m\) 的值不能超过给定的正整数 \(L\)。大守护者想让你协助她找到一种扩充能源的方案 \(a_1,a_2,\dots,a_m\)，使得在扩充能源后，可能的最大连通度尽可能大。你只需要输出可能的最大连通度即可。
观察到题目给出的条件 \(m \leq n\)，那么这个图就只可能是森林（和树）或者是基环树
不难发现，在树上的时候，所能得到的最大连通度为其最小的边权，在环上时，所得到的的最大连通度为其最小与次小的边权之和
那么，我们可以考虑二分答案，check 函数里面补齐边权小于 \(mid\) 的边至 \(mid\)，计算花费即可
预处理找环用 dfs 即可，时间复杂度 \(\mathcal O(T n \log L)\)，注意开 long long 即可
const int N=4e5+5,INF=3e9;
int testid,T,n,m,L,fa[N],head[N],cnt;
bool vis[N],fc,inc[N];
struct Edge
{
int v,w,nxt;
}e[N];
void add(int u,int v,int w)
{
e[++cnt]=(Edge){v,w,head[u]},head[u]=cnt;
}
void dfs(int u)
{
vis[u]=1;
for(int i=head[u];i;i=e[i].nxt)
{
if((i^1)==fa[u]) continue;
int v=e[i].v;
if(!vis[v]) fa[v]=i,dfs(v);
else if(!fc)
{
int cur=u;fc=1,inc[i]=inc[i^1]=1;
while(cur^v) inc[fa[cur]]=inc[fa[cur]^1]=1,cur=e[fa[cur]^1].v;
}
}
}
vector<int> c,t;
int check(int x)
{
int res=0;
for(int y:t) if(y<x) res+=x-y;
if(!c.empty())
{
for(int i=2;i<c.size();i++) if(c[i]<x) res+=x-c[i];
if(c[0]+c[1]<x) res+=x-c[0]-c[1];
}
return res;
}
void solve()
{
n=read(),m=read(),L=read();
for(int i=1;i<=m;i++)
{
int u=read(),v=read(),w=read();
add(u,v,w),add(v,u,w);
}
dfs(1);
for(int i=2;i<=cnt;i+=2) inc[i]?c.push_back(e[i].w):t.push_back(e[i].w);
sort(c.begin(),c.end()),sort(t.begin(),t.end());
int l=0,r=INF,ans=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid)<=L) ans=mid,l=mid+1;
else r=mid-1;
}
printf("%lld\n",ans);
}
void init()
{
c.clear(),t.clear();
for(int i=1;i<=n;i++) vis[i]=fa[i]=0;
for(int i=1;i<=cnt;i++) head[i]=inc[i]=0,e[i]=(Edge){0,0,0};
cnt=1,fc=0;
}
signed main()
{
freopen("wildfire.in","r",stdin);
freopen("wildfire.out","w",stdout);
testid=read(),T=read();
while(T--) init(),solve();
return 0;
}
C
Yoimiya 有一个 \(n\) 个点的有向图，对每个 \(1 \leq i \leq n\)，图中都存在一条有向边 \(i \to i+1\)。
此外，Yoimiya 从这 \(n\) 个点中选出了若干个点构成了一个集合 \(S\)，然后对于 \(S\) 中的任意两个元素 \(x,y\) 满足 \(x<y\)，她在图中新加了一条边 \(x \to y\)。
现在云浅会选出一个 \(1,2,\dots,n\) 的排列 \(p\)，对于这个排列，云浅会构建一个长为 \(n\) 的序列 \(w\)，其中 \(w_i\) 的值为：如果删掉图中的 \(p_1,p_2,\dots,p_{i-1}\) 这些点以及和它们相邻的所有连边，当前图中满足 \(x<y\) ，且\(x\) 能够只通过此时剩下的点和边到达 \(y\) 的点对 \((x,y)\) 的个数。
对于排列 \(p\)，云浅定义 \(f(p)\) 为其对应的 \(w_1,w_2,\dots,w_n\) 之和。现在云浅想要求出所有排列 \(p\) 的 \(f(p)\) 之和对 \(998244353\) 取模的值。
咕咕咕
D
对于正整数 \(n\)，Elysia 定义 \(f(n)\) 为：将 \(n\) 在十进制下的每一位取出，并分成两个集合 \(S,T\)，使得每个数位恰好被分在 \(S,T\) 中的一个里，要求最小化 \(S\) 中元素的和与 \(T\) 中元素的和之差。
例如，\(f(123)=0\)，最优方案是取 \(S=\lbrace 1,2 \rbrace,T=\lbrace 3\rbrace\)；\(f(1235)=1\)，最优方案是取 \(S=\lbrace 1,5 \rbrace,T=\lbrace 2,3 \rbrace\)。
现在 Elysia 给了你 \(Q\) 次问，每次问给出 \(l,r,k\)，你需要输出有多少个正整数 \(x\) 满足 \(l \leq x \leq r\)，且 \(f(x) \leq k\)。
咕咕咕
Round 20 (9.18)
A
下面给出一些定义：
- \(sort(a)\) 表示将序列 \(a\) 重排后的新序列
- 对于一个长度为 \(k\) 的序列，\(f(a)=\sum_{i=1}^{k} [a_i=i]\)
给定一个长度为 \(n\) 的序列 \(A\)，求 \(A\) 的所有非空子序列 \(S\) 的 \(f(sort(S))\) 之和
第一眼：串串题，第二眼：简单数学题
考虑将每一个 \(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;
}
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)\)
C
CF875F Royal Questions
考虑将平面内的每一行每一列连边
求最大权值基环森林
跟最大生成树差不多，用 Kruskal 跑再稍微改一下就差不多了
时间复杂度 \(O(nm (\log n+\log m))\)
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)
A
给定序列 \(a_{1 \dots n},b_{1 \dots n}\)，求：
\[\sum_{i=n}^{n} \sum_{j=1}^{n} \sqrt{\lfloor |a_i-b_j| \rfloor} \]其中，\(\sum a_i,\sum b_i \leq 10^7\)
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 3
12
*/
B
CF623C Electric Charges
二分答案，转化为判定性问题
预处理前后缀最大最小值，分别对于 \(x\) 和 \(y\) 得到极长段来求答案，然后就没了
C
定义 \(Prime\) 为质数
求：\[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=2,a_2=6 ,\dots $
\(a_i\) 是杨辉三角中间对称轴的那一列
数论题，不会做
咕咕咕
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)
A
小模拟麻将题
-
先考虑 \(n=14\)
若 \(k=2\) 只考虑顺子和雀头
若 \(k=3,4\) 枚举雀头再检验剩下的牌是刻子还是顺子
-
在考虑 \(n=13\)
显然可以枚举最后一张牌，然后就用 \(n=14\) 时的方法做就好
B
有 \(n\) 个点，第 \(i\) 个点的坐标为 \((x_i,y_i)\)，连接两点 \(i,j\) 的代价为 \((x_i-x_j)^2+(y_i-y_j)^2\)，求连同所有点花费的最小代价
\(1 \leq n \leq 10^5,0 \leq x_i \leq 10^5,0 \leq y_i \leq 10\)
人类智慧题
发现 \(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;
}
C
喵喵喵幼儿园有 \(n\) 名同学,现在有 \(n\) 个礼物要分配给他们, 但是每个同学的喜好不同，具体地，第 \(i\) 名同学最喜欢第 \(p_{i,1}\) 个礼物，其次喜欢第 \(p_{i,2}\) 个礼物……最不喜欢第 \(p_{i,n}\) 个礼物，保证 \(p_i\) 是一个 \(1\) 到 \(n\) 的排列。
现在懒惰的老师只给第 \(i\) 名同学分配了第 \(i\) 个礼物，他们自然希望通过交换来得到自己更喜欢的礼物，也就是说，交换结束之后每个人都不会拿到自己更不喜欢的礼物。
现在你需要帮助同学们完成交换礼物的过程，好奇的他们希望知道有多少种方法可以使得交换之后每个人都不会拿到自己更不喜欢的礼物。
正当你开始准备解决这个问题时，老师告诉你，同学们之间被分为了两个阵营，只有同一个阵营的同学之间才能交换礼物；并且这个阵营情况是会发生变化的，你需要对于 \(q\) 种阵营情况分别求出只在同阵营的同学之间交换礼物，且交换之后合法的方案数，由于答案可能很大，所以你不需要取模再输出。
咕咕咕
D
给定有向图 \(G=(V,E)\)，其中 \(V\) 为点集，\(E\) 为边集。设 \(G\) 包含 \(n\) 个结点，用正整数 \(1,2,\dots,n\) 表示，即 \(V=\lbrace 1,2,\dots,n \rbrace\)
对于 \(V\) 的任意非空子集 \(S \subseteq V\)，如果 \(S\) 中任意点的任意后继均属于 \(S\)，即对任意 \(u \in S\) 及 \(u\) 的出边 \((u,v) \in E\) 均满足 \(v \in S\)，则称 \(S\) 是 \(G\) 的一个闭合子图。
你的任务是，求出有多少个 \(G\) 的非空闭合子图 \(S\)，满足 \(S\) 中的点编号是连续的。连续的定义：对任意整数 \(i<k<j\)，若 \(i,j \in S\),则 \(k \in S\)。
答案对 \(10^9+7\) 取模
咕咕咕
Round 23 (9.27)
A
求概率题，也就模数换成了 \(147744151\) (还好是质数)
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e6+5,mod=147744151;
int T,p,q,x,y;
int fac[N],inv[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;
}
void init()
{
fac[0]=1;
for(int i=1;i<N;i++) fac[i]=fac[i-1]*i%mod;
inv[N-1]=fpm(fac[N-1],mod-2);
for(int i=N-1;i>=1;i--) inv[i-1]=inv[i]*i%mod;
}
int C(int n,int k)
{
return n<0||k<0||k>n?0:fac[n]*inv[n-k]%mod*inv[k]%mod;
}
signed main()
{
// freopen("A.in","r",stdin);
// freopen("A.out","w",stdout);
init();
scanf("%lld",&T);
while(T--)
{
scanf("%lld%lld%lld%lld",&p,&q,&x,&y);
int ans1=fac[x+p-1]*inv[x-1]%mod*fac[y+q-1]%mod*inv[y-1]%mod;
int ans2=fac[x+y-1]*inv[x+y+p+q-1]%mod;
printf("%lld\n",ans1*ans2%mod*C(p+q,p)%mod);
}
return 0;
}
/*
4
1 1 1 1
1 3 1 2
2 3 1 1
153 376 4743 2633
*/
B
树有 \(n\) 个节点，边带边权且具有方向，定义两个点之间的距离是两个点间的简单路径边权和。在每个节点上都有一位游客，游客只能沿着边的方向走，将一条边的方向翻转需要花费 \(1\) 代价，游客经过一条边花费的时间是边的权。
庆典可以在任意一个节点举办，我们希望所有游客都能够前往庆典所在的节点。所以请你帮他挑选一个节点，使得所有游客都能在 \(D\) 的时间内前往庆典所在的节点，并且花费的代价最少。
类似于是换根 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
*/
C
共 \(Q\) 次询问，在序列 \(a\) 的区间 \([l_i,r_i]\) 中选 \(k\) 个数，最大化 \(\gcd(b_1,b_2,\dots,b_k)\)
其中，\(k \geq (r-l+1)-3\)
咕咕咕
D
在一个一位数轴上，有两个吃豆人，起始位置都在原点。任意时刻它们可以以不超过 \(V\) 的速度移动或静止不动
已知第 \(i\) 颗豆子在时刻 \(t_i\) 出现在位置 \(x_i\)，吃豆人能吃掉它当且仅当在时刻 \(t_i\) 位置在 \(x_i\)
求在吃豆人能吃完所有豆子的前提下，最小化速度上限 \(V\)
咕咕咕
Round 24 (9.29)
A
给定一个元素互不相同的序列 \(A\)，以及一个整数 \(k\)，保证 \(k \in [0,1] \cap \mathbb N\)
求有多少种重排 \(A\) 的方式满足：
\(\forall i,j \in [1,n],i<j\) 且 \(i+j=2k+1,k \in \mathbb N\)
都有 \(A_i+A_j \equiv k \pmod 2\)
答案
又是对 \(147744151\) 取模
结论题，不过一开始没能立刻看出条件其实推下去就是对于 \(\forall i \in [1,n]\) 都满足
就跟奇偶性有关
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,mod=147744151;
int T,n,k,odd,even,fac[N];
void init()
{
fac[0]=1;
for(int i=1;i<N;i++) fac[i]=fac[i-1]*i%mod;
}
signed main()
{
init();
scanf("%lld",&T);
while(T--)
{
scanf("%lld%lld",&n,&k);
odd=even=0;
for(int i=1;i<=n;i++)
{
int x;
scanf("%lld",&x);
if(x&1) odd++;
else even++;
}
if(!k)
{
if(odd==n||even==n) printf("%lld\n",fac[n]);
else puts("0");
continue;
}
if(n&1)
{
if(abs(odd-even)==1) printf("%lld\n",fac[odd]*fac[even]%mod);
else puts("0");
continue;
}
if(odd==even) printf("%lld\n",fac[odd]*fac[even]%mod*2%mod);
else puts("0");
}
return 0;
}
/*
3
5 0
6 10 1 4 8
4 0
17 13 21 3
3 1
1 2 3
*/
B
给定一个长度为 \(n\) 的数组 \(A\)，解决该问题前可以任意重排该数组
定义数组的一个区间 \([l.r]\) 是美丽的当且仅当 \(\forall l \leq i \leq j \leq r\)，都满足 \(A_i \mid A_j\) 或 \(A_j \mid A_i\)，此时区间 \([L,R]\) 的分数为 \(\min(A_l,A_{l+1},\dots ,A_r) \times (r-l+1)\)
最大化 \(A\) 数组的美丽区间分数的最大值
较为简单的数论题，从最大值 \(maxa\) 到 \(1\) 一直枚举，然后进 dfs 剪枝求答案即可
C
\(A\) 国拥有 \(n\) 个城市，有 \(m\) 条双向道路，每条道路的通行时间都为 \(1\)
某人想在满足能在不超过 \(l_1\) 的时间从 \(s_1\) 到 \(t_1\) 且能在不超过 \(l_2\) 的时间从 \(s_2\) 到 \(t_2\) 的时间，最大化摧毁道路的数量
咕咕咕
D
开派对咯！有 \(n\) 个人，起初他们两两之间的关系度都为 \(0\)。在接下来 \(m\) 天，每天都会发生一个事件，事件分三种类型：
第 \(x\) 个人和第 \(y\) 个人的关系度增加了 \(1\)。
第 \(x\) 个人发起了一次聚会，邀请了所有认识 \(x\) 的人，每个被邀请的人也会叫上自己认识的人……然后所有参加聚会的人两两之间的关系度都会增加 \(1\)。
请输出当前第 \(x\) 个人和第 \(y\) 个人之间的关系度。
定义两个人互相认识当且仅当他们之间的关系度不小于 \(1\)。
咕咕咕
E
对于一个大小为 \(n\) 的序列 \(A=(A1,A2,\dots,A_n)\) 和两个整数 \(L,R\) 满足 \(1 \leq L \leq R \leq n\) 和两个整数 \(S,T\) 满足 \(S \neq T\)。
定义：
\[F^k(i)= \begin{cases} F^{k-1}(F(i)) &\text{if}(k \neq 1) \\ A_i &\text{if}(k=1) \end{cases}\]现在有一个 \(n\) 个点，\(0\) 条边的有向图 \(G\)，按照如下规则给这个图添加边：
对于 \(1 \leq i \leq n,L \leq k \leq R\)，添加一条 \((i,F^k(i))\)，长度为 \(1\) 的有向边。
询问从 \(S\) 出发到达 \(T\) 的最短距离，若不能到达则输出 \(—1\)。
咕咕咕
Round 25 (10.5)
A
给定 \(n\) 个区间，每个区间 \([l_i,r_i]\)，最大化选取区间对数，使得每对区间 \([l_i,r_i],[l_j,r_j]\) 满足 \([l_i,r_i] \cap [l_j,r_j] =\varnothing\)
先按 \(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;
}
B
你有一个从 \(1\) 到 \(n\) 的排列 \(a_1,a_2,\dots,a_n\)、一个空的序列 \(b\)，和一个空的大根堆
你需要进行 \(2 \times n\) 次操作，每次操作有两种选择：
- 从堆中取出最大的数字，加入序列 \(b\) 的末尾（仅当大根堆不为空）
- 从序列 \(a\) 中最靠前的数加入堆中并从 \(a\) 中删除
最终，你显然会得到一个从 \(1\) 到 \(n\) 的序列 \(b_1,b_2,\dots,b_n\)
求总共能有多少种不同的序列 \(b\) 可以生成，答案对 \(8580287\) 取模
咕咕咕
C
定义平衡序列：一个 \(01\) 序列是平衡序列当且仅当不存在一个子区间，其中 \(01\) 的个数差的绝对值大于 \(k\)
计算由 \(x\) 个 \(0\)，\(y\) 个 \(1\) 构成的平衡 \(01\) 序列的个数，答案对 \(998244353\) 取模
咕咕咕
D
有 \(n\) 的 \(01\) 变量组成的序列 \(x\)，我们称 \(01\) 序列 \(x\) 是美丽的当且仅当满足以下 \(m\) 条限制：
每一条限制都可以表达为：形如 \(u,v\) 不能同时是 \(1\)，即：
- \(u=x_i\) 或 \(u= \neg x_i\)
- \(v=x_j\) 或 \(v= \neg x_j\)
求满足美丽序列的前提下，这 \(n\) 个变量的取值
咕咕咕
Round 26 (10.6)
A
求方程有整数解 \(x^2-2Bx+C=0,(B,C)\) 的对数
其中，\(C \in [L,R] \cap \mathbb N^{*},B \in \mathbb N^{*}\)
简单数学题
暴力肯定会挂，考虑变形（柿子）式子
利用求根公式可得：\(x=B \pm \sqrt{B^2-C}\)
\(x \in \mathbb Z \Leftrightarrow \sqrt{B^2-C} \in \mathbb Z\)
即 \(B^2-C\) 为完全平方数
那不妨可以将 \(C\) 对于值域 \(V\) 内所有的方案数都算出来，设 \(B^2-C=A^2\)，变形后为 \(B^2-A^2=C\)，枚举 \(A,B\) 即可，注意剪枝，再弄个前缀和即可
#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
*/
B
给定一个从 \(1\) 到 \(n\) 的排列 \(a_1,a_2,\dots,a_n\)
每次可以交换相邻的两个元素 \(a_x,a_y,1 \leq x,y \leq n,|x-y|=1\) 当且仅当 \(a_x \neq x\) 且 \(a_y \neq y\)
你的目标是能否用不超过 \(m\) 步将排列 \(a\) 重排至一一对应，即 \(\forall i,a_i=i\)
如果有解，输出
YES，并构造出一种交换操作的方案，如果无解，输出NO特别地，当 \(m=-1\) 时只需要判断是否有解，不用输出构造方案
考虑归纳，因为 \(a_i=i\) 会变成不动点，所以在交换的过程中可能需要错排，而错排是有解的
#pragma GCC optimize (3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int n,m,a[N],ans[N*N][2],res;
void modify(int x,int y)
{
ans[++res][0]=x,ans[res][1]=y;
swap(a[x],a[y]);
}
void solve(int l,int r)
{
if(l>=r) return;
for(int i=r;i>l;i--)
if(a[i]==l)
{
int j=i-1;
while(j>=l&&a[j]==j+1) j--;
if(j>=l)
{
for(int k=j;k<i-1;k++) modify(k,k+1);
for(int k=i-1;k>=j;k--) modify(k,k+1);
}
else for(int k=i-1;k>=l;k--) modify(k,k+1);
}
solve(l+1,r);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",a+i);
for(int l=1,r;l<=n;l=r+1)
{
r=l;
if(a[l]==l) continue;
while(r<n&&a[r+1]!=r+1) r++;
for(int i=l;i<=r;i++)
if(a[i]>r)
{
puts("NO");
return 0;
}
solve(l,r);
}
puts("YES");
if(!~m) return 0;
printf("%d\n",res);
for(int i=1;i<=res;i++) printf("%d %d\n",ans[i][0],ans[i][1]);
return 0;
}
/*
4 3
2 4 1 3
*/
C
洛谷 P6864 [RC-03] 记忆
很好的一道数据结构（DS）题
这题最重要是考虑到如何拆分序列以便于统计与更新答案
发现答案会与某些东西在每个操作都存在一定关系，那么可以试着上矩阵来维护，每次用线段树单点修改、区间查询即可
D
你是一个物流公司的调度员，你所在的城市有 \(0,1,2,\dots,x_{max}\) 这 \(max+1\) 个配送点。
假设货物当前在配送点 \(x\) ，你一次操作可以花费 \(c(x)\) 的代价将其运送到 \(\lfloor \frac{x}{2} \rfloor,\lfloor \frac{x}{3} \rfloor,\dots,\lfloor \frac{x}{w} \rfloor\) 中的任意一个配送点，其中 \(w\) 是给定常数。
初始时，\(c(x)=d_0(x)\)，其中 \(d_0(x)\) 为 \(x\) 的因子个数。你需要执行 \(q\) 次询问或修改操作。
- 对于一次修改操作，给定正整数 \(x\)，令 \(c(x) \gets c(x)-1\)，数据保证任意时刻任意 \(c(x) \geq 0\)。
- 对于一次询问操作，给定正整数 \(x\)，求将货物从配送点运送到配送点 \(0\) 的最小代价。
真看不懂给的题解，咕咕咕
Round 27 (10.9)
A
简单数论分块，过
B
形式化题意：定义 \(Fib\) 为斐波那契数列，其中：
\[Fib_i= \begin{cases} 1 &\text{if}(i=1\ \text{or}\ i=2) \\ Fib_{i-2}+Fib_{i-1} &\text{if}(i \geq 3) \end{cases} \]求 \(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\)，笑死，笔者觉得不如观察输出对应的 \((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
*/
C
AT_joisc2014_e 水筒
先跑一次 bfs 建图，然后跑 Kruskal 最小生成树得到重构树，最后在树上跳倍增 LCA 求答案即可
（思路与 洛谷 P1967 [NOIP2013 提高组] 货车运输 相似，就多了个 bfs 建图个过程）
D
洛谷 P7363 [eJOI2020 Day2] Dots and Boxes
咕咕咕
Round 28 (10.10)
谴责 GJ 今天一开始只放一道题，名字叫做 \(5\) 道题
A
CF1375C Element Extermination
简单结论题，\(a_1<a_n\) 就符合了，过
B
普通树论题，但是不知道这个结论：划分成大小为 \(k\) 的连通块，当且仅当树上有 \(n/k\) 个点的 \(size\) 是 \(k\) 的倍数
C
思路有点巧妙，暴力是 dp，发现每个物品的价值都很小，考虑大小约为 \(100 \times 100\) 矩阵快速幂加快递推
D
不会，咕咕咕
E
数论题，更加不会，看到答案是对 \(2^{32}\) 取模就知道不简单
挂个柿子以后再来补：
似乎要拆分贡献？
咕咕咕
Round 29 (10.11)
A
傻波一小明就会做亏本买卖是吧
题目在下面写了个 \(u<v\)，才发现是有向无向图 \(DAG\),虽然不一定联通
考虑拓扑排序 + dp，时间复杂度 \(\mathcal O(n+m)\)
B
找规律题，与杨辉三角挂钩
求的就是每一行前 \(a_i+1\) 个数的和，即第 \(a_i\) 列的值
答案为 $ \sum_{i=1}^{n+1} {i+a_i-1 \choose i} $
C
AT_joisc2017_c 手持ち花火 (Sparklers)
所有人都向 \(k\) 号跑最优，考虑时光倒流，二分，check 里贪心，后面不会，咕咕咕
D
CF526G Spiders Evil Plan
有一棵 \(n\) 个点的树，带有边权。现有 \(m\) 个询问如下：在树上选取 \(k_i\) 条路径（树上任意两点的连接通路视为一条路径），其中至少要有一条路径覆盖到点 \(a_i\)，问所有被路径覆盖的边权的和最大是多少。注意重复覆盖的边只会计算一次。
nmd CF *3300
树上问题，不容易发现答案包含直径某一端点，长链剖分，后面不会，咕咕咕
Round 30 (10.14)
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 题，不会，咕咕咕
B
CF1310E Strange Function
模拟赛上 CF *2900 dp 也是只有 GJ 敢这么干的
（题外话：赛时 puts("1"); 有 \(28\) pts 真不错「伏笔」）
考虑分类讨论
-
\(k=1\) 时，将 \(n\) 个元素划分，上个背包就好
-
\(k=2\) 时，对最终序列从大到小排序，差分再上背包就好
-
\(k>2\) 时，因为答案已经不多了，所以直接搜索剪枝就过了（这就是为啥能总司令了~）
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;
}
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\) 打模拟赛时间
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;
}
B
不仅 \(200\) 个点还绑包？
构造题，可参考 AT_abc358_f Easiest Maze，但不是完全一样，还是有点差异的
上下界还是有一定难度想到，毕竟赛后才知道那个 \(2 \mid n, 2 \mid m\) 会使下界 \(+1\)
上界可以考虑直接螺转，下界可以考虑弄一些竖线，然后横着来一刀就差不多了
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;
}
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)
又是绑包。。。
A
诈骗题，经过 \(\mathcal O(\log k)\) 次操作之后每个数变为 \(2k\) 或 \(2k+1\)
暴力枚举前 \(50\) 次总和即可，\(m>50\) 的基本都可以看做 \(m=50\)
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
*/
C
咕咕咕
D
咕咕咕
Round 33 (10.19)
Summary
GJ 设成了 IOI 赛制 😃
真的没意思，没到两个小时就 AC 前三题了
前面 \(3\) 题比较简单，甚至 \(T3\) 我都做过原了。。。
\(T4\) 没看，puts("0"); 总司令 \(15\) 分走了，然后就去补题了
赛时 \(100+100+100+15=315\)，打得最爽也是最高分的一集
A
AT_abc103_c Modulo Summation
入机数学题
显然对于每一个 \(b_i\) 取模，必有一个数 \(x\) 使得 \(\forall i \in [1,n],x \bmod b_i=b_i-1\)
那么答案就为 \(ans=\sum (b_i-1)\)
B
洛谷 P3106 [USACO14OPEN] Dueling GPSs S
考虑反向建边，从 \(n\) 开始跑三次 Dijkstra做完了
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 / 花神游历各国
D
有一个 \(N\) 个点的无向图，你现在要从这个图中选出一条游行路线，具体就是选择一个点作为开始点，走 \(5\) 条连续的边，这 \(5\) 条边不能有重复的边，但可以经过相同的点。问有多少种不同的取法。
这个图的边是根据如下伪代码产生的：
给出参数：\(seed,threshold\)，和数组 \(toggle_{0..L-1}\)。
state seed for x = 0 .. N-1: for y = x+l .. N-1: state =(state * 1103515245 +12345) modulo 2^31 if state threshold: add edge x-y L= length(toggle)/2 for i in 0.. L-1: x = toggle[2*i] y = toggle[2*i+1] if we have the edge x-y: remove edge x-y else: add edge x-y
咕咕咕
Round 34 (10.21)
题头：本次测试要用文件读入输出！
然而，事实上是，\(4\) 题都不用文件读入输出……
A
有两个长度为 \(n\) 的序列 \(a,b\)，每次可让 \(a_i \gets a_i+1\)，代价为 \(b_i\)，求最小代价使得 \(a\) 序列中所有的元素互不相等
贪心，按 \(a_i\) 从小到大排序，考虑使用大根堆维护修改价值，然后似乎就没了（）
时间复杂度 \(\mathcal O(n \log n)\)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,INF=0x3f3f3f3f3f3f3f3f;
int n,sum[N];
struct dat
{
int val,cst;
}a[N];
priority_queue<int> q;
signed main()
{
// freopen("resource.in","r",stdin);
// freopen("resource.out","w",stdout);
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i].val);
for(int i=1;i<=n;i++) scanf("%lld",&a[i].cst);
sort(a+1,a+1+n,[](dat a,dat b){return a.val^b.val?a.val<b.val:a.cst<b.cst;});
a[n+1].val=INF;
int ans=0,sum=0;
for(int i=1;i<=n;i++)
{
q.push(a[i].cst),sum+=a[i].cst;
if(a[i].val^a[i+1].val)
{
sum-=q.top(),q.pop();
for(int j=a[i].val+1;j<a[i+1].val&&q.size();j++)
ans+=sum,sum-=q.top(),q.pop();
ans+=sum;
}
}
printf("%lld",ans);
return 0;
}
B
定义最小生成树的权值为其所有边权按位或得到的值
\(n\) 个点，\(m\) 条边，\(Q\) 次单独操作询问，互不影响，每次加入一条 \((u,v)\) 权值为 \(0\) 的边求新的答案，即每次在原图加边后询问
咕咕咕
C
在一个充满学术氛围的小镇上，有一家图书馆，以其庞大的藏书量和高效的索引系统而闻名。图书馆的索引系统基于一系列索引卡片，每张卡片代表一本书，其上记录了书籍的标题和与之相关的数值。
为了优化检索过程，图书馆引入了一种新的索引机制，其中涉及到对字符串的前缀操作。在这个机制中，前缀指的是字符串从开头开始的一部分，可以是整个字符串。例如，对于字符串 \(S=\text{example}\)，其前缀 \(S[1:3]\) 就是 \(\text{exa}\)。
初始有 \(n\) 本书，第 \(i\) 本书的标题是 \(S_i\)，初始其数值 \(a_i=0\)。
图书馆管理员现在需要处理来自读者的请求，这些请求分为三种类型（假设执行这次请求前的书籍数量是 \(M\)):
1 i K x：对于每个 \(1 \leq j \leq M\)，如果 \(S_j[1:K]=S_i[1:K]\)，则需要为这些书籍 \(j\) 索引卡片上的数值 \(a_j\) 增加一个特定的量 \(x\)。
2 i K T：加入一本编号为 \(M+1\)，标题为 \(S_{M+1}=S[1:K]+T\) 的书，其索引卡片上的数值为\(0\)，之后 \(M\) 增加 \(1\)。
3 i：查询第 \(i\) 本书的索引卡片上的数值 \(a_i\)。你需要编写一个程序来响应这些查询，确保索引系统既准确又高效。
发现该题没有强制在线，考虑离线将所有字符串建在 Trie 树上，用数据结构维护操作即可，适当用倍增加速递归
其实区间修改单点查询可以使用树状数组，但是笔者懒干脆就打了线段树，也就码量和常数大了点
#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=1e6+5;
int n,Q,cnt=1,a[N],b[N],lst[N],R[N],L[N];
int fa[N][21],f[N],opt[N],tcnt;
char st[N];
struct Trie
{
int a[26],dep;
}tr[N];
void insert(int cur,int x)
{
int len=strlen(st+1);
for(int i=1;i<=len;i++)
{
int x=st[i]-'a';
if(!tr[cur].a[x])
{
fa[++cnt][0]=cur;
tr[cnt].dep=tr[cur].dep+1;
for(int j=1;j<=19;j++)
fa[cnt][j]=fa[fa[cnt][j-1]][j-1];
tr[cur].a[x]=cnt;
}
cur=tr[cur].a[x];
}
f[x]=cur;
}
int query(int x,int k)
{
x=f[x];
for(int i=19;~i;i--)
if(tr[fa[x][i]].dep>=k)
x=fa[x][i];
return x;
}
void dfs(int u)
{
L[u]=++tcnt;
for(int i=0;i<26;i++)
{
if(!tr[u].a[i]) continue;
dfs(tr[u].a[i]);
}
R[u]=tcnt;
}
int t[N<<2],tag[N<<2];
void push_up(int u)
{
t[u]=t[ls]+t[rs];
}
void push_down(int u,int l,int r)
{
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)
{
tag[u]+=k;
t[u]+=(r-l+1)*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);
}
int query(int u,int l,int r,int x)
{
if(x<l||r<x) return 0;
if(l==r) return t[u];
push_down(u,l,r);
int mid=(l+r)>>1;
if(x<=mid) return query(ls,l,mid,x);
else return query(rs,mid+1,r,x);
}
signed main()
{
// freopen("book.in","r",stdin);
// freopen("book.out","w",stdout);
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",st+1);
insert(1,i);
}
scanf("%lld",&Q);
for(int i=1,x,y;i<=Q;i++)
{
scanf("%lld",&opt[i]);
if(opt[i]==1)
{
scanf("%lld%lld%lld",&x,&y,&b[i]);
a[i]=query(x,y);
}
if(opt[i]==2)
{
scanf("%lld%lld%s",&x,&y,st+1);
a[i]=++n;
insert(query(x,y),n);
}
if(opt[i]==3) scanf("%lld",&a[i]);
}
dfs(1);
for(int i=1;i<=Q;i++)
{
if(opt[i]==1) update(1,1,tcnt,L[a[i]],R[a[i]],b[i]);
if(opt[i]==2) lst[a[i]]=query(1,1,tcnt,L[f[a[i]]]);
if(opt[i]==3) printf("%lld\n",query(1,1,tcnt,L[f[a[i]]])-lst[a[i]]);
}
return 0;
}
D
在一次聚会上，你被邀请参加一个有趣的数字游戏。游戏的规则是这样的：你手中有一串数字卡片，每张卡片上都写着一个数字。你的任务是通过一系列简单的操作，使得存在两张卡片上的数字相乘后，结果是一个完全平方数。
你可以进行的操作有两种：
将某张卡片上的数字乘以一个质数。
如果某张卡片上的数字能被某个质数整除，你可以将这个数字除以这个质数。
现在，你面前有一串数字卡片，上面写着 \(a_1,a_2,\dots,a_n\)。你的朋友提出了 \(q\) 次挑战，他们想知道在不同的数字卡片组合中，你需要进行多少次操作才能达到目标。
每个挑战都以两个参数 \(l_i\) 和 \(r_i\) 来定义，表示从 \(a_{l_i}\) 到 \(a_{r_i}\) 的一系列卡片。你需要告诉他们，对于每个挑战，最少需要进行多少次操作。
形式化题意：
给你一个长度为 \(n\) 的序列 \(a\)，定义 \(P\) 为任意质数，共 \(Q\) 次询问，每次询问一个区间 \([L,R]\)，你可以进行以下操作：
- \(a_i \gets a_i \times P\)
- \(a_i \gets \frac{a_i}{P},P \mid a_i\)
求最小化操作次数，使得 \(\exists i,j \in [L,R] \cap \mathbb Z,a_i \times a_j = X^2,X \in \mathbb N\)
咕咕咕
Round 35 (10.23)
Summary
我们都是冠军！（全员保龄了owo，原因是 GJ 并未告诉我们文件名是啥 😃）
还是 本次测试要用文件读入输出
看了眼下发大样例的名字，是 bag/profit/bing/array，但因为 GJ 搬题会大改所以没啥参考价值？
题目名为 魔法袋/数学作业/手牌收益/音乐变奏，经过机房的实验得出文件读入输出名分别为 maigc/homework/hand/music （不是 hand 是什么鬼）
合理怀疑考的是 OE(English Olympic)
A
小明是一个数学魔法师，他有一个神奇的魔法球，里面可以装很多魔法数，相等的数可以出现多次。一开始，魔法球中只有一个魔法数 \(1\)。小明要念一条包含 \(n\) 个神奇数学音符的咒语，咒语上的音符有两种：
1.发生：小明念到发生音符时，球里会增加一个新的魔法数，其值为 \(1\)。
2.合并：小明念到合并音符时，可以任意选择球中的两个魔法数 \(a\) 和 \(b\)，这两个数会在球中合并为一个新的魔法数 \(a+b\)，原来的两个数将被消耗。但是如果念到合并音符的时候球中魔法数的个数小于 \(2\) 个，魔法球就会爆裂！小明的咒语长度固定为 \(n\) 个音符，有些位置必须是发生音符，有些位置必须是合并音符，剩下的位置小明可以任选一种音符。
小明希望在不让魔法球爆裂的情况下，通过一系列数学操作，让球中留下的魔法数的平均值尽可能大。请你找出这个最大的平均值。
形式化并简化题意：
初始时你有一个分数 \(\frac{S}{N}\)，其中 \(S=N=1\)，你共有 \(n\) 次操作，每次操作有三种操作：
- 操作一：\(S \gets S+1,N \gets N+1\)
- 操作二：\(N \gets N-1,N \geq 2\)
- 操作三：可进行上述两种操作之一
注意你每次进行操作 \(2\) 都要保证 \(N \geq 2\)，若无法保证，请输出
-1，最大化 \(\frac{S}{N}\)
显然发生音符（操作一）对答案的贡献要么不变，要么减小，那么需要尽可能最小化操作一的次数，将自由音符（操作三）尽可能转合并音符（操作二），在不爆裂的情况下尽可能合并
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int T,n,a[N];
int main()
{
freopen("magic.in","r",stdin);
freopen("magic.out","w",stdout);
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
int ans1=1,ans2=1,cnt=0;
bool flag=false;
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
if(x==1) ans1++,ans2++;
if(!x||x==-1)
{
if(!x) cnt++;
if(ans2<2) cnt--,ans1++,ans2+=2;
if(cnt<0) flag=true;
ans2--;
}
}
if(flag) {puts("-1");continue;}
int g=__gcd(ans1,ans2);
printf("%d %d\n",ans1/g,ans2/g);
}
return 0;
}
B
共有 \(n\) 个学生 \(m\) 个城市，第 \(i\) 个学生要选择去 \(a_i\) 和 \(b_i\) 中的一个。若有奇数个人去同一个城市，那么就需要仆从随行。最小化需要的仆从数。
结论题，对于一个连通块，仆从所需要的数量等于这个连通块内的边数模二的值
显然，对于一个学生，选择其中一个点，那么点 \(a_i\) 和 \(b_i\) 的奇偶性变化只会有 \(4\) 种情况：
那么每次操作只会减少/增加两个 \(1\)，或者不变，那么自然花费最小为 \(x \bmod 2\)
考虑用并查集即可，时间复杂度 \(\mathcal O(m + n \alpha (m))\)，其中 \(\alpha(m)\) 为反阿克曼函数
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=1e5+5;
int n,m,k,fa[N],siz[N];
int find(int x)
{
return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main()
{
freopen("homework.in","r",stdin);
freopen("homework.out","w",stdout);
scanf("%d%d%d",&m,&n,&k);
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
int x=find(u),y=find(v);
siz[x]++;
if(x==y) continue;
if(siz[x]<siz[y]) swap(x,y);
siz[x]+=siz[y],siz[y]=0;
fa[y]=x;
}
for(int i=1;i<=n;i++) k-=siz[i]&1;
printf("%d",k);
return 0;
}
C
给定一个长度为 \(n\) 的序列 \(a\)，求：
\[\sum_{1 \leq i<j<k \leq n} (a_i \oplus a_j) \lor a_k \]其中，\(\oplus\) 是二进制按位异或，\(\lor\) 是二进制按位或，答案对 \(2^{64}\) 取模，\(a_i\) 由随机数生成器产生
考虑拆位求贡献，那么显然可以统计 \(0\) 的个数和 \(1\) 的个数，然后随便搞搞就过了
时间复杂度 \(\mathcal O(64n)\)
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int N=4e6+5;
int n,K;
ull a[N],U,seed,ans;
int main()
{
freopen("hand.in","r",stdin);
freopen("hand.out","w",stdout);
scanf("%d%llu%d",&n,&seed,&K);
srand(seed);
U=(K==64?0ull:(1ull<<K))-1ull;
mt19937_64 rnd(seed);
for(int i=1;i<=n;i++) a[i]=rnd()&U;
for(int j=0;j<64;j++)
{
ull cnt0=0,cnt1=0,sum=0;
for(int i=1;i<=n;i++)
{
sum+=cnt0*cnt1;
if(a[i]&(1ull<<j))
{
sum+=cnt0*(cnt0-1)/2;
sum+=cnt1*(cnt1-1)/2;
cnt1++;
}
else cnt0++;
}
ans+=sum*(1ull<<j);
}
printf("%llu",ans);
return 0;
}
D
你有一个长度为 \(n\) 的序列 \(a\)，可以选择在序列上一段长度为 \(m\) 的连续区间加上一个首项为 \(c\)，公差为 \(d\) 的等差数列，最大化序列的第 \(k\) 大
咕咕咕
Round 36 (10.24)
有点难
A
给定一个无向图，求本质不同的最小环的个数
感觉我这写的代码常数太大了不开 O3 T 飞了
显然可以用 bfs 求一下最小环的长度，然后这里我就跑了 \(n\) 次 bfs 了
具体地，维护 \(dis_y\) 为点 \(x\) 到点 \(y\) 的最短距离，当我们从 \(u\) 结点第一次访问到 \(v\) 结点时，更新其对应的 \(dis\) 值，否则我们就可以找到一个长度为 \(dis_u+dis_v+1\) 的环
然后就可以开始计数啦，结果这里我有用了 \(n\) 次 bfs
记最小环的长度为 \(L\)，则：
- 以环上任意一点为起点均会统计该环一次，答案故需要除以 \(L\)
- 似乎有的写法当 \(L\) 为奇数的时候会被统计成两个方向上的环，答案需要除以 \(2\)，（要看个人写法）
时间复杂度 \(\mathcal O(n(n+m))\)，总共跑了 \(2n\) 次 \(bfs\) 被题解的 \(n\) 次 bfs 狠狠暴拉了
代码就不建议参考了，毕竟还会多个二倍常数
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;
const int N=3e3+5,INF=0x3f3f3f3f;
int n,m,dis[N],cnt[N],mindis=INF,ans;
vector<int> g[N];
void bfs1(int s)
{
memset(dis,-1,sizeof(dis));
queue<int> q;
q.push(s),dis[s]=0;
while(!q.empty())
{
int u=q.front();q.pop();
for(auto v:g[u])
{
if(~dis[v])
{
if(dis[v]>=dis[u]) mindis=min(mindis,dis[u]+dis[v]+1);
continue;
}
dis[v]=dis[u]+1,q.push(v);
}
}
}
void bfs2(int s)
{
memset(dis,-1,sizeof(dis));
queue<int> q;
q.push(s),dis[s]=0,cnt[s]=1;
while(!q.empty())
{
int u=q.front();q.pop();
for(auto v:g[u])
{
if(~dis[v])
{
if(dis[v]>=dis[u]&&dis[u]+dis[v]+1==mindis)
{
ans+=cnt[v];
if(!(mindis&1)) cnt[v]+=cnt[u];
}
continue;
}
dis[v]=dis[u]+1,q.push(v),cnt[v]=cnt[u];
}
}
}
signed main()
{
freopen("cycre.in","r",stdin);
freopen("cycre.out","w",stdout);
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%lld%lld",&u,&v);
g[u].pb(v);g[v].pb(u);
}
bfs1(1);
for(int i=1;i<=n;i++) bfs1(i);
for(int i=1;i<=n;i++) bfs2(i);
if(mindis&1) ans>>=1;
ans/=mindis;
printf("%lld",ans);
return 0;
}
B
给定 \(N,N_3,P\) 求满足 \(((N^2+1) \bmod a+b) \bmod c=N_3\) 的三元组 \((a,b,c)\) 的方案数，其中 \(1 \leq a,c \leq P,0 \leq b \leq P\)，设方案数为 \(Q\)，则还需要按照字典序从小到大输出前 \(\min(P,5 \times 10^5)\) 个三元组
数学题
先把原题面的定义放出来便于记录
定义：
考虑逆递推得到 \(N_2\) 的值以及对应的 \(c\)，然后就可以得到所有 \(N_1\) 的取值以及对应的 \(a\)
易得 \(\lfloor N_2 / c \rfloor \times c + N_3 = N_2,\sum_{c=1}^{P} \lfloor P/c \rfloor = \mathcal O (P \lg P)\)，那么就可以枚举 \(c\) 的取值和 \(\lfloor N_2 /C \rfloor\) 的取值来得到 \(N_2\)，且只有 \(\mathcal O(P \lg P)\) 种取值，然后可以使用二分或者前缀和求出 \(b\) 的取值，故时间复杂度为 \(\mathcal O(P \lg P)\)
代码略
C
给定一个长度为 \(n\) 的字符串 \(S\)，定义符合 \(u\) 审美的字符串是恰好由两个不同的字母交替组成的字符串，给出 \(Q\) 次询问，每次询问 \(S\) 的子串 \(S[l_i \dots r_i]\) 中，符合 \(u\) 审美的最长子序列长度是多少，并输出字典序最小的子序列对应的两个组成的字符
咕咕咕
D
咕咕咕
Round 37 (10.25)
A
小 \(A\) 发现了一张神秘的星际地图，描绘了宇宙中天体的分布地图可以被抽象为一个 \(n \times m\) 的网格，每个格子可能上都可能存在一个天体、也可能不存在天体。
他注意到在这个星际地图中，存在着一种奇特的天体排列模式，小 \(A\) 称其为“星际螺旋结构”。一个 \(k\) 层 \((k \geq 2)\) 的"星际螺旋结构"的第 \(1\) 行有 \(1\) 个天体，第 \(2\) 行有 \(3\) 个天体……第 \(k-1\) 行有 \((2k-3)\) 个天体，第 \(k\) 行有 \(1\) 个天体，这些行的天体必须以中间的天体对齐。
小 \(A\) 被这个神秘的星际排列模式深深吸引，他想知道在整个星际地图存在多少个“星际螺旋结构” （每个结构可以有任意层，解释见样例）。请你帮助小 \(A\) 计算满足条件的“星际螺旋结构”的数量。
小模拟题，不过需要稍微预处理下就好了
记 \(L_{i,j}\) 表示 \(a_{i,j}\) 这个天体能到达连续区间最左端的位置，\(R_{i,j}\) 同理
时间复杂度 \(\mathcal O(n^3)\)
#include<bits/stdc++.h>
using namespace std;
const int N=505;
int n,m,L[N][N],R[N][N],ans;
bool a[N][N];
int main()
{
freopen("map.in","r",stdin);
freopen("map.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
scanf("%d",a[i]+j),L[i][j]=R[i][j]=j;
for(int j=1;j<=m;j++) if(a[i][j-1]) L[i][j]=L[i][j-1];
for(int j=m;j>=1;j--) if(a[i][j+1]) R[i][j]=R[i][j+1];
}
for(int i=1;i<n;i++)
for(int j=1;j<=m;j++)
{
if(!a[i][j]||!a[i+1][j]) continue;
ans++;
for(int k=i+1;k<n;k++)
{
if(!a[k][j]||!a[k+1][j]) break;
if(j-L[k][j]<k-i||R[k][j]-j<k-i) break;
ans++;
}
}
printf("%d",ans);
return 0;
}