持续更新中，目前只有 \(\texttt{A,D,G,H,I,M}\) 题题解。
A.骑行计划
题目描述
小 Rei 有 \(n\) 天的假期，第 \(i\) 天她要骑行 \(s_i\) 分钟，每分钟骑行费用为 \(c\) 元。
有 \(m\) 种骑行卡，第 \(i\) 种骑行卡售价 \(w_i\) 元，有效期 \(d_i\) 天，免费时间 \(t_i\) 分钟。
小 Rei 可以在任意一天购买任意骑行卡，当天的免费时间为有效期内的骑行卡的 \(t_i\) 最大值，超出部分仍按每分钟 \(c\) 元计算。
求完成骑行计划的最小总支出。
数据范围
- \(1\le n\le 150,1\le m,c\le 10^4,1\le s_i\le 150\) 。
- \(1\le w_i\le 10^9,1\le d_i\le n,1\le t_i\le 150\) 。
时间限制 \(\texttt{2s}\) ，空间限制 \(\texttt{512MB}\) 。
分析
在二维平面上考虑这个问题，横坐标 \(i\) 的位置有 \(s_i\) 个格子需要被覆盖，而第 \(i\) 种骑行卡花费 \(w_i\) 的代价覆盖了一个长为 \(d_i\) ，高为 \(t_i\) 的矩形，显然我们要做的事情就是对矩形并的形状进行 \(\texttt{dp}\) 。
如果不考虑矩形横坐标 \(\in[1,n]\) 的限制，容易发现两张骑行卡有效期成交叉关系一定不优，把 \(t_i\) 较小的骑行卡往旁边挪一挪一定不劣。
因此两张骑行卡如果有效期有交，则一定是包含关系。
包含关系是可以出现的，比如下面这组数据：
input: 3 2 100 1 2 1 5 3 1 10 1 2 output: 15
发现这一点后线性 \(\texttt{dp}\) 就基本可以否决了，考虑区间 \(\texttt{dp}\) 。
\(f_{l,r,x}\) 表示仅考虑横坐标 \([l,r]\) ，钦定区间内不超过 \(x\) 的高度已经被其他矩形覆盖时的最小代价。
转移考虑第 \(l\) 天的决策，注意最优决策下每天至多会购买一张骑行卡。
- 不购买任何骑行卡： \(f_{l,r,x}\gets f_{l+1,r,x}+\max(s_i-x,0)\cdot c\) 。
- 购买第 \(i\) 种骑行卡： \(f_{l,r,x}\gets f_{l,l+d_i-1,t_i}+f_{l+d_i,r,x}+w_i\) ，要求 \(d_i\) 要对区间长度取 \(\min\) ，并且 \(t_i\gt x\) 。
至此可以做到 \(\mathcal O(n^2sm)\) ，由于状态数 \(\mathcal O(n^2s)\) 已经砍不掉了，只能从转移想点办法。
第二类转移本质上是枚举一个长为 \(d_i\) ，高为 \(t_i\) 的矩形。抽象一下，预处理 \(g_{i,j}\) 表示构造一个长为 \(i\) ，高为 \(j\) 的矩形的最小代价，则第二类转移可以写成：
\[f_{l,r,x}\gets\min_{l\le i\le r}\min_{j\gt x}(f_{l,i,j}+f_{i+1,r,x}+g_{i-l+1,j})\\ \]看似我们用 \(\mathcal O(ns)\) 代替 \(\mathcal O(m)\) ，时间复杂度变得更高了。但由于转移过程中本来就要倒序枚举 \(x\) ，因此我们可以顺便维护 \(h_i=\min\limits_{j\gt x}(f_{l,i,j}+g_{i-l+1,j})\) ，这样可以省去枚举 \(j\) 的代价。
预处理显然可以做到 \(\mathcal O(ns+m)\) ，完整时间复杂度 \(\mathcal O(n^3s+m)\) 。
#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
int c,m,n;
int f[155][155][155],g[155][155],h[155],s[155];
void chmin(int &x,int y)
{
if(x>y) x=y;
}
int main()
{
scanf("%d%d%d",&n,&m,&c);
for(int i=1;i<=n;i++) scanf("%d",&s[i]);
for(int i=1;i<=n;i++) for(int j=1;j<=150;j++) g[i][j]=inf;
for(int w=0,d=0,t=0;m--;) scanf("%d%d%d",&w,&d,&t),chmin(g[d][t],w);
for(int i=n;i>=1;i--) for(int j=150;j>=1;j--) chmin(g[i-1][j],g[i][j]),chmin(g[i][j-1],g[i][j]);
for(int l=n;l>=1;l--)
for(int r=l;r<=n;r++)
{
for(int i=l;i<=r;i++) h[i]=inf;
for(int x=150;x>=0;x--)
{
f[l][r][x]=f[l+1][r][x]+max(s[l]-x,0)*c;
for(int i=l;i<=r;i++) chmin(f[l][r][x],h[i]+f[i+1][r][x]),chmin(h[i],f[l][i][x]+g[i-l+1][x]);
}
}
printf("%d\n",f[1][n][0]);
return 0;
}
D.摊位分配
题目描述
\(n\) 个社团，每个社团有初始值 \(u_i\) ，将 \(h\) 个格子按照如下规则分配给 \(n\) 个社团。
-
\(\forall 1\le i\le n\) ，计算 \(u_i,\frac{u_i}2,\cdots,\frac{u_i}{2^{h-1}}\) 。
-
从这 \(n\times h\) 个数中，每次选择最大的一个并删去。
如果有多个最大值：
- 若有社团尚未分到格子，则优先分配给这样的社团。
- 如果仍有多个社团可以分配，选择编号最小的社团。
求每个社团能分配到多少个格子。
数据范围
- \(1\le n\le 10^5,1\le h\le 10^9,1\le u_i\le 10^9\) 。
时间限制 \(\texttt{1s}\) ，空间限制 \(\texttt{512MB}\) 。
分析
类似超级钢琴、异或粽子的套路，用优先队列维护每个社团的信息，每次取堆顶。
注意优先队列重载小于号却是较大元素放在堆顶，代码实现需要稍微细心一点。
如果每个社团都得到至少分到一个格子就会进入循环，在此之前每个社团至多分到 \(\log u+1\) 个格子。
手动模拟直到进入循环，再模拟一轮循环的结果即可，时间复杂度 \(\mathcal O(n\log n\log u)\) 。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
int h,n,num;
struct node
{
int u,x,id;
bool operator<(const node &a)const
{
int v=min(x,a.x);
ll s=((ll)u)<<(a.x-v),t=((ll)a.u)<<(x-v);
if(s!=t) return s<t;
if((x==0)!=(a.x==0)) return a.x==0;
if(u!=a.u) return u<a.u;
return id>a.id;
}
}o[maxn];
priority_queue<node> q;
void print()
{
for(int i=1;i<=n;i++) printf("%d%c",o[i].x," \n"[i==n]);
exit(0);
}
int main()
{
scanf("%d%d",&n,&h);
for(int i=1;i<=n;i++) scanf("%d",&o[i].u),o[i].id=i,q.push(o[i]);
for(;num!=n;)
{
int i=q.top().id;q.pop();
num+=!(o[i].x++),q.push(o[i]);
if(!--h) print();
}
for(int i=1;i<=n;i++)
{
int j=q.top().id;q.pop();
o[j].x+=h/n+(i<=h%n);
}
print();
return 0;
}
G.Imyourfan
题目描述
\(T\) 组数据，给定长为 \(n\) 的字符串 \(s\) ， \(s_i\in\{\texttt X,\texttt W,\texttt M\}\) ，保证至少存在一个 \(\texttt W\) 和一个 \(\texttt M\) 。
Water 和 Menji 轮流操作，Water 先手，每次操作选择一个不含 \(\texttt X\) 的区间 \([l,r]\) ，并将区间内
若某次操作后 \(\texttt W\) 和 \(\texttt M\) 都被拿走，则结果为平局；若 \(\texttt W\) 全部被拿走，则 Water 获胜，若 \(\texttt M\) 全部被拿走，则 Menji 获胜。
假设两人绝顶聪明，对每组数据，输出获胜的一方，平局输出 Draw 。
数据范围
- \(1\le T\le 10^5,2\le|s|\le 10^5,\sum|s|\le 5\cdot 10^5\) 。
时间限制 \(\texttt{1s}\) ，空间限制 \(\texttt{512MB}\) 。
分析
显然 \(\texttt{X}\) 将 \(s\) 分成了独立的若干连续段。
由于每次取的是整个区间，所以可以把连续的相同字符视为一个字符，于是只剩下了如下三类字符串：
- 左右均为 \(\texttt W\) ，如 \(\texttt W,\texttt{WMW},\cdots\) 。
- 左右均为 \(\texttt M\) ，如 \(\texttt M,\texttt{MWM},\cdots\) 。
- 左右一个为 \(\texttt W\) 一个为 \(\texttt M\) ，如 \(\texttt{WM},\texttt{MW},\cdots\) 。
最优策略下 Water 每次拿走 \(\texttt W\) 的个数恰好比 \(\texttt M\) 的个数多 \(1\) ，而 Menji 正好相反。
注意如果能从边上拿一定会从边上拿，除非两端全为对手的字符（当然这种情况自己已经获胜）。
比如 \(\texttt{WMW}\) 拿走中间的 \(\texttt M\) 后两侧的 \(\texttt W\) 会合并，因此等价于只剩下一个 \(\texttt W\) 。对于 Menji 而言花费了一步操作，但是 \(\texttt W\) 和 \(\texttt M\) 的数量差值没有变，如果两端有 \(\texttt M\) 的话，这并不是最优选择。
似乎如果 \(\texttt W\) 的个数小于等于 \(\texttt M\) 的个数就是 Water 获胜，否则就是 Menji 获胜，那么平局从何而来？
假如 \(\texttt W\) 恰好比 \(\texttt M\) 多一个，并且刚好剩下一个形如 \(\texttt{WMW..W}\) 的字符串，那么 Water 可以 "垂死挣扎" 一下，把整个字符串全部拿走，把败局挽回成平局。
事实上，只要初始盘面上存在长度 \(\ge 3\) 的首尾均为 \(\texttt W\) 的字符串， Water 就可以把这个字符串留到最后，然后使用上述策略。前面已经证明过 Menji 提前操作这个子串并不优，所以最终会以平局收场。
同理，如果 \(\texttt W\) 和 \(\texttt M\) 数量相等，并且存在长度 \(\ge 3\) 的首尾均为 \(\texttt M\) 的字符串，那么 Menji 可以将败局挽回成平局。
时间复杂度 \(\mathcal O(\sum|s|)\) 。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n,t,flg1,flg2,res;
char s[maxn];
int main()
{
for(scanf("%d",&t);t--;)
{
scanf("%s",s+1),n=strlen(s+1),flg1=flg2=res=0;
for(int l=1,r=0;l<=n;)
{
if(s[l]=='X') l++;
else
{
for(r=l;r+1<=n&&s[r+1]!='X';r++) ;
if(s[l]==s[r])
{
if(s[l]=='W') res++,flg2|=count(s+l,s+r+1,'M')>0;
if(s[l]=='M') res--,flg1|=count(s+l,s+r+1,'W')>0;
}
l=r+1;
}
}
if(res<0) printf("Water\n");
if(res==0) printf(flg1?"Draw\n":"Water\n");
if(res==1) printf(flg2?"Draw\n":"Menji\n");
if(res>1) printf("Menji\n");
}
return 0;
}
H.waht 先生的法阵
题目描述
给定长为 \(n\) 的序列 \(a\) ， \(q\) 次操作：
1 l r c：对 \(\forall i\in[l,r]\) ，令 \(a_i\gets c\cdot a_i\) 。2 x：从 \(x\) 出发，若当前在位置 \(i\) ，则下一步跳到 \(i+\gcd(i,a_i)\) ，直到 \(i\gt n\) 为止，求所有经过位置的 \(a\) 之和，对 \(998244353\) 取模。
数据范围
- \(1\le n,q\le 2.5\cdot 10^5,1\le a_i\lt 998244353\) 。
- \(1\le l\le r\le n,2\le c\le 2.5\cdot 10^5\) 。
- \(1\le x\le n\) 。
时间限制 \(\texttt{4s}\) ，空间限制 \(\texttt{512MB}\) 。
分析
显然我们无法维护 \(a\) 的真实值，令 \(u_i=\frac i{\gcd(i,a_i)}\) ，则 \(i\) 会跳到 \(i+\frac i{u_i}\) 的位置。
考虑操作 \(1\) 对数组 \(u\) 的影响，对 \(\forall i\in[l,r]\) ，若 \(\gcd(u_i,c)\neq 1\) ，则 \(u_i\gets\frac{u_i}{\gcd(u_i,c)}\) 。
显然 \(u_i\) 至多只会被修改 \(\log i\) 次，第一个问题是如何找到需要修改的 \(u_i\) 。
线段树维护区间 \(\gcd\) 是错误的，应该维护的是 \(\texttt{lcm}\) ，但是做不到。
那就另辟蹊径，注意到对素数 \(p\) ， \(p\mid u_i\) 的必要条件是 \(p\mid i\) ，线段树维护 \(u_{pi}\) 含 \(p\) 的幂次的区间 \(\min\) 即可。
以上是博主赛时做法，不过不用这么麻烦。用一个长为 \(\lfloor\frac np\rfloor\) 的数组维护 \(u_{pi}\) 含 \(p\) 幂次，同时用并查集指向下一个幂次不为零的位置，码量和常数都会小很多。
接下来就变成了加强版的弹飞绵羊。支持权值区间乘， \(\mathcal O(n\log n)\) 次单点修改后继，求路径权值和。
设块长为 \(B\) ，区间乘的散块和修改后继涉及到的块暴力重构，整块打乘法标记。
时间复杂度 \(\mathcal O((n\log n+q)B+q\cdot\frac nB)\) ，取 \(B=\sqrt\frac q{\log n}\) ，时间复杂度 \(\mathcal O(n\sqrt{q\log n})\) 。
#include<bits/stdc++.h>
using namespace std;
const int B=150,maxn=2.5e5+5,mod=998244353;
int l,n,q,r,x,op,cnt;
int a[maxn],p[maxn],u[maxn],L[maxn];
int bel[maxn],st[maxn],ed[maxn];
bitset<maxn> b;
vector<int> vec;
void init(int n)
{
for(int i=2;i<=n;i++)
{
if(!b[i]) p[++cnt]=i,L[i]=i;
for(int j=1;j<=cnt&&i*p[j]<=n;j++)
{
b[i*p[j]]=1,L[i*p[j]]=p[j];
if(i%p[j]==0) break;
}
}
}
int add(int x,int y)
{
if((x+=y)>=mod) x-=mod;
return x;
}
namespace block
{
int to[maxn],sum[maxn],tag[maxn];
void update(int l,int r)
{
if(bel[l]==bel[r])
{
for(int i=l;i<=r;i++) a[i]=1ll*a[i]*x%mod;
vec.push_back(bel[l]);
}
else
{
for(int i=l;i<=ed[bel[l]];i++) a[i]=1ll*a[i]*x%mod;
for(int i=st[bel[r]];i<=r;i++) a[i]=1ll*a[i]*x%mod;
for(int i=bel[l]+1;i<=bel[r]-1;i++) tag[i]=1ll*tag[i]*x%mod;
vec.push_back(bel[l]),vec.push_back(bel[r]);
}
}
void modify(int x)
{
for(int i=ed[x];i>=st[x];i--)
{
int j=i+i/u[i];
if(j<=ed[x]) to[i]=to[j],sum[i]=add(a[i],sum[j]);
else to[i]=j,sum[i]=a[i];
}
}
int query(int x)
{
int res=0;
while(x<=n) res=(res+1ll*sum[x]*tag[bel[x]])%mod,x=to[x];
return res;
}
}
struct dsu
{
int p;
vector<int> f,v;
int find(int x)
{
return f[x]==x?x:f[x]=find(f[x]);
}
void init(int _p)
{
p=_p,f.resize(n/p+5),v.resize(n/p+5),f[n/p+1]=n/p+1;
for(int i=1;i<=n/p;i++)
{
for(int x=u[p*i];x%p==0;) x/=p,v[i]++;
f[i]=i+!v[i];
}
}
void work(int l,int r,int x)
{
l=(l-1)/p+1,r=r/p;
for(int i=find(l);i<=r;i=find(i+1))
{
for(int j=1;j<=min(v[i],x);j++) u[p*i]/=p;
v[i]=max(v[i]-x,0),vec.push_back(bel[p*i]);
if(!v[i]) f[i]=i+1;
}
}
}t[maxn];
int main()
{
scanf("%d%d",&n,&q),init(maxn-5);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),u[i]=i/__gcd(i,a[i]);
for(int i=1;i<=n;i++) bel[i]=(i-1)/B+1;
for(int i=1;i<=bel[n];i++) st[i]=(i-1)*B+1,ed[i]=min(i*B,n),block::tag[i]=1,block::modify(i);
for(int i=1;i<=cnt&&p[i]<=n;i++) t[p[i]].init(p[i]);
while(q--)
{
scanf("%d",&op);
if(op==1)
{
scanf("%d%d%d",&l,&r,&x),vec.clear(),block::update(l,r);
for(int y=x;y!=1;)
{
int p=L[y],cnt=0;
while(y%p==0) y/=p,cnt++;
if(p<=n) t[p].work(l,r,cnt);
}
sort(vec.begin(),vec.end());
vec.erase(unique(vec.begin(),vec.end()),vec.end());
for(auto p:vec) block::modify(p);
}
else
{
scanf("%d",&x);
printf("%d\n",block::query(x));
}
}
return 0;
}
I.乒乓球赛
题目描述
\(T\) 局乒乓球赛，每一局的每个回合恰有一个胜者，并且胜者得 \(1\) 分。当任意一名选手得分达到 \(11\) 分且领先对手至少 \(2\) 分时，比赛结束。
已知每一局的回合数 \(n\) ，以及部分时刻的比分 \(a_i:b_i\) 。若 \(a_i=b_i=-1\) 则表示不知道第 \(i\) 回合结束后的分数，否则表示一个选手 \(a_i\) 分，另一个选手 \(b_i\) 分，但不知道谁 \(a_i\) 分谁 \(b_i\) 分。
求对局结果的方案数，对 \(998244353\) 取模。
数据范围
- \(1\le T\le 10^5,1\le n\le 5\cdot 10^5,\sum n\le 5\cdot 10^5\) 。
- \(a_i=b_i=-1\) 或 \(0\le a_i,b_i\le n\) 。
分析
本题细节有点多，手算组合数转移非常容易出错，用代码模拟每一局进行转移则可以避开很多细节。
首先是一些基本要求， \(n\gt 11,a_i+b_i=i\) ，如果不满足答案显然为零。
对于前 \(20\) 局，不允许出现 \(\max(a_i,b_i)\gt 11\) 的情况。
对于 \(20\) 局之后的情况，每局比分已知，且 \(11:10,12:11\) 等每个比分恰有两种，贡献可以直接算。
\(f_{i,j}\) 表示前 \(i\) 局，第一个人分数为 \(j\) ，第二个人分数为 \(i-j\) 的方案数。如果 \(\max(j,i-j)\ge 11\) 则停止转移，碰到 \(a_i\neq -1\) 的回合将不符合要求的位置清零即可。
时间复杂度 \(\mathcal O(T\cdot 20^2+n)\) 。
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n,t;
int a[100005],b[100005],f[25][25];
void add(int &x,int y)
{
if((x+=y)>=mod) x-=mod;
}
void solve()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a[i],&b[i]);
if(a[i]<b[i]) swap(a[i],b[i]);
}
if(n<11) return printf("0\n"),void();
for(int i=1;i<=n;i++) if(a[i]!=-1&&a[i]+b[i]!=i) return printf("0\n"),void();
if(n>20)
{
if(n&1) return printf("0\n"),void();
for(int i=20;i<n;i++) if(a[i]!=-1&&a[i]!=(i+1)/2) return printf("0\n"),void();
if(a[n]!=-1&&a[n]!=n/2+1) return printf("0\n"),void();
}
memset(f,0,sizeof(f));
f[0][0]=1;
for(int i=1;i<=min(n,20);i++)
{
for(int j=0;j<i;j++) if(max(j,i-1-j)<11) add(f[i][j+1],f[i-1][j]),add(f[i][j],f[i-1][j]);
if(a[i]!=-1) for(int j=0;j<=i;j++) if(j!=a[i]&&i-j!=a[i]) f[i][j]=0;
}
if(n<=20) printf("%d\n",(f[n][11]+f[n][n-11])%mod);
else
{
int res=f[20][10];
for(int j=1;j<=(n-20)/2;j++) res=2*res%mod;
printf("%d\n",res);
}
}
int main()
{
for(scanf("%d",&t);t--;) solve();
return 0;
}
M.好成绩
题目描述
求一个 \([0,150]\) 中的整数满足，除以 \(3\) 余 \(2\) ，除以 \(5\) 余 \(3\) ，除以 \(7\) 余 \(6\) 。
数据范围
无输入。
分析
签到题，答案为 \(83\) 。
#include<bits/stdc++.h>
using namespace std;
int main()
{
printf("83\n");
return 0;
}