写在前面
之前给牛客的提高组验过几次题，作为出题人还是第一次，中间有一些小锅，包括B题的样例不满足y<=n等等（实际上原来的第一组数据就是样例，后面修改重判了），但是最终还算比较完美 的结束了。
由于个人比较喜欢思维题，因此四道题的实现难度都不是很大，除了C题稍微有点套路（是数学题套数据结构）。
简单提要：A题比较简单，读懂题意基本就能AC了；B题其实是双向链 表，但是没有卡平衡树做法，因此不想动脑筋直接敲平衡树也是能AC的；C题是线段树维护矩阵 / 多项式等，由于不想卡常时限给了std的10倍，因此不管维护什么都是能AC的（除非常数真的巨大）；D题是一道难度较高的思维题，会KMP就能得到40%，而要拿100%需要发现某种类似倍增的结构。
赛中有四位选手AC了C题，有一位选手成功AK，并且是唯一一位AC了D题的选手。（感谢你们>_<）
以下是详细的题解和std。
Problem A. 语言
题意
每个字母有A,N,V三种可能的词性，NP:=N | A+N | NP1+NP2，S:=NP+V+NP，判断某个字符串能不能成为S。
做法
其实就是看能不能组成 X...XNVX...XN 的结构，其中X可以是N或A。
直接暴力，复杂度为 。期望通过30%。
预处理可以构成前一个X...XN的位置和后一个X...XN的位置，复杂度为 。期望通过100%。
std
#include <bits/stdc++.h>
using namespace std;
char s[100100];
int w[30], ok[100100];
int main(void) {
int T; scanf("%d",&T);
assert(T <= 10);
while (T--) {
memset(ok,0,sizeof(ok));
for (int i=0;i<26;i++) scanf("%d",&w[i]);
for (int i=0;i<26;i++) assert(1 <= w[i] && w[i] <= 7);
scanf("%s",s);
for (int i=0;s[i];i++) assert('a' <= s[i] && s[i] <= 'z');
int n = strlen(s);
for (int i=0;i<n;i++) {
if (w[s[i]-'a']&2) ok[i]=1;
if (w[s[i]-'a']==4) break;
}
if (!(w[s[n-1]-'a']&2)) {
printf("No\n");
continue;
}
bool f=0;
for (int i=n-2;i>=1;i--) {
if ((w[s[i]-'a']&4) && ok[i-1]) {
f=1;
break;
}
if (w[s[i]-'a']==4) break;
}
if (f) printf("Yes\n");
else printf("No\n");
}
return 0;
}
Problem B. 色球
题意
n个位置，m个操作。操作1，把x个颜色为y的球放到z位置的顶部；操作2，从z位置顶部取出x个球，输出最后一个球的颜色；操作3，把位置u的球倒过来放到位置v顶部。
以下假设与
同阶。
做法一
每个位置一个vector顺序记录放的球的颜色和个数，所有询问暴力进行。
复杂度 ，期望通过30%~50%。
做法二
每个位置用双向链表顺序记录放的球的个数和颜色。
对于询问1，往位置z的链表上加一个结点 。
对于询问2，从位置z的链表头取，如果当前需要取 个而当前结点拥有的球
个，则整个结点删掉，
更新为
。如果
，那么输出当前的颜色
，并且把
更新为
。
对于询问3，把位置u的链表头直接拼接到位置v的链表头上，位置u的链表尾作为位置v新的链表头。
考虑这个做法的复杂度，询问1和3很显然是 的，询问2中每次碰到
的情况就会删掉一个结点，而每次询问最多碰到一次
的情况。因为结点最多增加
次，因此整体的复杂度是
。期望通过100%。
std
#include <bits/stdc++.h>
using namespace std;
const int maxn = 301001;
struct node {
int c,num,ch[2];
} buf[maxn];
int n,m,h[maxn],t[maxn],tot;
int main(void) {
scanf("%d%d",&n,&m);
for (int i=0;i<m;i++) {
char op[6];
int x,y,z;
scanf("%s%d%d",op,&x,&y);
if (op[2]=='s') {
scanf("%d",&z);
buf[++tot]=(node){y,x,h[z],0};
if (h[z]) buf[h[z]].ch[0]?(buf[h[z]].ch[1]=tot):(buf[h[z]].ch[0]=tot);
else t[z]=tot;
h[z]=tot;
} else if (op[2]=='p') {
while (buf[h[y]].num<x) {
x-=buf[h[y]].num;
int lch=buf[h[y]].ch[0]|buf[h[y]].ch[1];
if (lch) buf[lch].ch[0]==h[y]?(buf[lch].ch[0]=0):(buf[lch].ch[1]=0);
h[y]=lch;
}
buf[h[y]].num-=x;
printf("%d\n",buf[h[y]].c);
} else {
if (!h[x]) continue;
if (h[y]) {
buf[h[y]].ch[0]?(buf[h[y]].ch[1]=h[x]):(buf[h[y]].ch[0]=h[x]);
buf[h[x]].ch[0]?(buf[h[x]].ch[1]=h[y]):(buf[h[x]].ch[0]=h[y]);
} else {
t[y]=h[x];
}
h[y]=t[x];
h[x]=t[x]=0;
}
}
return 0;
}
Problem C. 斐波
题意
给定序列 ，
操作1，把a_p修改为v;
操作2，计算
其中 。
做法一
预处理fib的数列，修改操作直接修改，询问时按公式枚举答案相加。
复杂度 或
。预计都是通过10%。
做法二
首先观察到其实 也是符合线性递推的，递推式为
所以可以写出矩阵形式的递推式
即 。
这里 可以根据递推式反推出来，用这种形式比较方便之后的推导。
对于可重集合，
，可以把
也向量化，变成
，最终答案就是
的第一项。
如果给增加一个数
，可以得到
因此假设，则
。
令 ，其实问题就是单点更新
，询问
。
使用这个式子进行暴力，复杂度为 。期望通过50%。
做法三
线段树可以维护 。具体就是考虑合并两个区间
,
时，增加的答案是
和
这些区间合并产生的。使劲地维护这些信息就可以了。
不使用线段树，但使用类似的思想，可以达到 。期望通过70%。
使用线段树，复杂度为 。期望通过100%。
生成函数的做法
首先要知道一个结论：
假设线性递推
令
令
然后有 ，其中
是
的
项的次数。
所以我们可以预处理每个 。
线段树每个位置维护 ，后面的做法基本是一样的。这样的好处是常数会从
降到
。复杂度为
。期望通过100%。
std
#include <bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define ull unsigned ll
using namespace std;
const int mod = 998244353;
const int maxn = 100100;
struct node {
int x,y,z;
node operator + (const node & a) const {
return (node){(x+a.x)%mod,(y+a.y)%mod,(z+a.z)%mod};
}
node operator * (const node & a) const {
int A=x*(ll)a.x%mod;
int B=(x*(ll)a.y%mod+y*(ll)a.x%mod)%mod;
int C=(x*(ll)a.z%mod+y*(ll)a.y%mod+z*(ll)a.x%mod)%mod;
int D=(y*(ll)a.z%mod+z*(ll)a.y%mod)%mod;
int E=z*(ll)a.z%mod;
return (node){(int)(((A-D+mod)%mod-2ll*E%mod+mod)%mod),
(int)((B+2ll*D%mod+3ll*E%mod)%mod),
(int)((C+2ll*D%mod+6ll*E%mod)%mod)};
}
} f[maxn], sum[maxn*4], msum[maxn*4], lsum[maxn*4], rsum[maxn*4];
void pushup(int rt) {
int l=rt<<1, r=rt<<1|1;
msum[rt]=msum[l]*msum[r];
sum[rt]=sum[l]+sum[r]+rsum[l]*lsum[r];
lsum[rt]=lsum[l]+msum[l]*lsum[r];
rsum[rt]=rsum[r]+msum[r]*rsum[l];
}
void build(int l, int r, int rt) {
if (l == r) {
int u; scanf("%d",&u);
assert(1 <= u && u <= 100000);
sum[rt]=lsum[rt]=rsum[rt]=msum[rt]=f[u]+(node){1,0,0};
return ;
}
int mid=(l+r)/2;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
pushup(rt);
}
void upd(int p, int u, int l, int r, int rt) {
if (l == r) {
sum[rt]=lsum[rt]=rsum[rt]=msum[rt]=f[u]+(node){1,0,0};
return ;
}
int mid=(l+r)/2;
if (p <= mid) upd(p,u,l,mid,rt<<1);
else upd(p,u,mid+1,r,rt<<1|1);
pushup(rt);
}
node ms,s,ls,rs;
void ask(int L, int R, int l, int r, int rt) {
if (L <= l && r <= R) {
if (l == L) {
ms = msum[rt];
s = sum[rt];
ls = lsum[rt];
rs = rsum[rt];
} else {
s = s + sum[rt] + rs*lsum[rt];
ls = ls + ms*lsum[rt];
rs = rsum[rt] + msum[rt]*rs;
ms = ms * msum[rt];
}
return ;
}
int mid=(l+r)/2;
if (L <= mid) ask(L,R,l,mid,rt<<1);
if (mid < R) ask(L,R,mid+1,r,rt<<1|1);
}
int main(void) {
int N = 100001;
f[0]=(node){1,0,0};
for (int i=1;i<=N;i++) f[i]=f[i-1]*(node){0,1,0};
int n,q; scanf("%d%d",&n,&q);
assert(1 <= n && n <= 100000);
assert(1 <= q && q <= 100000);
build(1,n,1);
for (int i=0;i<q;i++) {
int op,x,y;
scanf("%d%d%d",&op,&x,&y);
assert((op==1 && 1<=x&&x<=n && 1<=y&&y<=100000)
|| (op==2 && 1<=x&&x<=y&&y<=n));
if (op == 1) {
upd(x,y,1,n,1);
} else {
ask(x,y,1,n,1);
int ans = (s.y+s.z)%mod;
printf("%d\n",ans);
}
}
return 0;
}
Problem D. 偶数
题意
定义“偶数”为数字的位数为偶数，且数字前一半和后一半完全一致的数。任意的“偶数”可以添加（至少一个）最少的数字使之成为新的“偶数”。一直按照这种方式添加，直到位数超过n，然后多次询问最终“偶数”的[l,r]位模998244353是多少。
做法一
枚举下一个“偶数”的位数，必然是把的某个后缀放到
后。因此确定位数后，可以
的判断能不能成为新的偶数。得到最终的“偶数”后，暴力的处理每个查询。
复杂度 。预计通过10%。
做法二
假设 是
，那么新的“偶数”必然是
的形式，其中
是
的一个前缀，且是
的一个周期。可以证明
应该取
最短的周期。因此使用KMP求
的周期，每次得到
后，新的
作为
继续求周期，直到
的长度超过
为止。
询问时预处理 为区间
的答案，则
的答案为
。
复杂度 。预计通过40%。
做法三
在做法二的基础上。如果 是
的一个因子，那么最终的
将会是
。
比较难的是 不是
的因子的情况，这时候可以证明
的最短的周期只能是
，因此新的
是
。（证明见最下）
我们令 ,
,
。最终的“偶数”将是
的一个前缀。注意到这个性质不管
是否是
的因子都是成立的，且
的长度一定不小于两倍的
，因此实际上只需要求
次即可达到要求。
实现时维护 个
的长度和值（模mod)，求区间
时每次取最长的不超过
的
填进去，维护好对应的长度和值（模mod）即可。
复杂度 。预计通过100%。
证明：
是 
的最短周期，且 &preview=true)
不是 &preview=true)
的因子，则 
的最短的周期是 。
假设 的最短的周期是
，
。
如果 ，
也是
的周期，矛盾。
如果 ，
是
的周期，从而是
的周期，矛盾。
std
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 998244353;
const int maxn = 1000100;
char s[maxn];
int n, lim, nxt[maxn], fs[maxn], f[100], ten[100];
ll len[100];
void get_nxt() {
int i=0, j=nxt[0]=-1;
while (i<n) {
while (j!=-1 && s[i]!=s[j]) j = nxt[j];
nxt[++i] = ++j;
}
}
int qpow(int a, ll n) {
int ans = 1;
for (;n;n>>=1,a=(ll)a*a%mod) if (n&1) ans=(ll)ans*a%mod;
return ans;
}
int gao(ll m) {
ll sum = 0;
int ans = 0;
for (int i=lim;i>=0;i--) {
if (sum + len[i] <= m) {
ans = (ans * (ll)ten[i] + f[i])%mod;
sum += len[i];
}
}
ans = (ans * (ll)qpow(10, m-sum) + fs[m-sum])%mod;
return ans;
}
int main(void) {
int T; scanf("%d",&T);
assert(T <= 10);
int sum_q = 0;
while (T--) {
scanf("%s",s);
n = strlen(s);
assert(n % 2 == 0 && 1 <= n && n <= 100000);
n /= 2;
for (int i=0;i<n;i++) assert('1' <= s[i] && s[i] <= '9' && s[i] == s[i+n]);
get_nxt();
for (int i=1;i<=n;i++) {
fs[i] = (fs[i-1]*10ll + s[i-1]-'0')%mod;
}
ll m; int q; scanf("%lld%d",&m,&q), sum_q += q;
assert(1 <= m && m <= (ll)1e18);
assert(1 <= q && q <= 100000);
len[0] = n - nxt[n], f[0] = fs[len[0]];
len[1] = n, f[1] = fs[n];
lim = 1;
for (int i=2;i<100;i++) {
len[i] = len[i-1] + len[i-2];
f[i] = (f[i-1]*(ll)qpow(10, len[i-2]) + f[i-2])%mod;
if (len[i] >= m) { lim=i; break; }
}
for (int i=0;i<=lim;i++) ten[i] = qpow(10, len[i]);
for (int t=0;t<q;t++) {
ll l, r;
scanf("%lld%lld",&l,&r);
assert(1 <= l && l <= r && r <= m);
int ans = (gao(r) - gao(l-1)*(ll)qpow(10, r-l+1)%mod + mod) % mod;
printf("%d\n", ans);
}
}
assert(sum_q <= 100000);
return 0;
}
全部评论
(3) 回帖