\[\text{NOIP模拟赛-2023.11.12} \]
T1 马
有 \(n\) 匹马，\(m\) 个人来骑马。有三个项目，分别是骑小圈、骑大圈、过河，三个项目对马的疲劳值的影响分别是 \(+20,+50,\times 2\)。初始时每匹马的疲劳值是 \(1\)，且每匹马的疲劳值不能超过 \(100\)。给定每个项目的人数 \(c_1,c_2,c_3(c_1+c_2+c_3=m)\)，问最多能满足多少人的需求
\(1\leq n\leq 150\)，\(m\leq 300\)
一开始想贪心，令每匹马能满足最多的人，但是这样是错误的
于是考虑 dp，设 \(f_{i,j,k}=0/1\) 表示能否满足只剩下 \(i+j+k\) 个人，答案即为 \(\max\limits_{f_{i,j,k}=1}\{m-i-j-k\}\)。
考虑转移，枚一匹马所有的可能情况进行转移，有个大约 \(\mathcal{O}(24)\) 的转移常数
分析复杂度，枚举每匹马 \(\mathcal{O}(n)\)，共有最多 \(\left(\dfrac{m}{3}\right)^3=10^6\) 个状态，这样算是 \(\mathcal{O}(150\times 10^6\times 24)\) 的。但是由于并不是每个状态都可以达到，我们直接枚举会产生很多无用状态，于是写个 bfs，把有用的状态入队进行转移，加点剪枝，可以通过
code
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
const int N=150+10,M=310;
int n,m,a[N],c[5],f[M][M][M];
struct node{int c1,c2,c3,t;};
// int id(int c1,int c2,int c3)
// {
// return c1*c[2]*c[3]+c2*c[1]+c1;
// }
int main()
{
freopen("horse.in","r",stdin);
freopen("horse.out","w",stdout);
// double st=clock();
scanf("%d%d%d%d%d",&n,&m,&c[1],&c[2],&c[3]);
queue <node> q;
q.push({c[1],c[2],c[3],0});
f[c[1]][c[2]][c[3]]=1;
while(q.size())
{
if(q.front().t>=n)
break;
node x=q.front(); q.pop();
for(int _1=min(x.c1,1); _1>=0; _1--)
{
for(int _2=min(x.c2,4); _2>=0; _2--)
{
bool flag=0;
for(int _3=min(x.c3,6),pw=pow(2,_3); _3>=0; _3--,pw>>=1)
{
if(pw+_1*50+_2*20<=100 && !f[x.c1-_1][x.c2-_2][x.c3-_3])
q.push({x.c1-_1,x.c2-_2,x.c3-_3,x.t+1}),f[x.c1-_1][x.c2-_2][x.c3-_3]=1,flag=1;
if(flag)
break;
}
}
}
}
int ans=0;
for(int i=0; i<=c[1]; i++)
{
for(int j=0; j<=c[2]; j++)
{
for(int k=0; k<=c[3]; k++)
if(f[i][j][k])
ans=max(ans,m-i-j-k);
}
}
printf("%d\n",ans);
// double ed=clock();
// fprintf(stderr, "%lfms\n",ed-st);
return 0;
}
/*
150 300
150 120 30
*/
T2 可爱捏
考虑将 \(a_i\) 分解质因数，并将所有的指数 \(\bmod 3\)，将结果记为 \(val_i\)，记 \(S_{v}\) 为 \(val_i=v\) 的个数。不难发现，对于 \(val\) 值相同的一群 \(a_i\)，和它们相乘为完全立方数的所有 \(a_j\) 的 \(val_j\) 是一样的，所以对于一个 \(val_i\)，与其对应的 \(val_j\) 是唯一的，所以统计答案时，只要选择 \(S\) 大的那个即可。注意完全里立方数只能选择一个进去
这样的时间复杂度是 \(\mathcal{O}(n\sqrt{V}+n\log n)\) 的，过不去。瓶颈在于分解质因数，考虑对这个过程进一步根号分治
我们每次只筛出 \(\sqrt[3]{a_i}\) 以内的质因数，对于剩下的数我们记为 \(m\)，此时的 \(m\) 只有三种取值情况，\(p,pq,p^2\)，其中 \(p,q\) 都是质数。对 \(m\) 进行分类讨论
- 若 \(m\leq (\sqrt[3]{a_i})^2\)，则 \(m\) 只能为 \(p\)，否则会有小于等于 \(\sqrt[3]{a_i}\) 的质因子
- 否则
- 若 \(m=p\) 或 \(m=pq\)，则对应的 \(val\) 大于 \(p^2\) 或 \((pq)^2\) 已经大于 \(10^{10}\)，这时这个数肯定可以加入
- 若 \(m=p^2\)，则正常操作即可
时间复杂度 \(\mathcal{O}(n\sqrt[3]{V}+n\log n)\)
code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e5+10,M=2160+10;
const LL V=1e10+10;
int n,t[N<<1],vv[M],prime[M],tot;
LL a[N],p[M],c[M],val[N],mt[N];
map <LL,int> v; int tv;
bool iscub[N],isok[N],vis[N];
void prework()
{
for(int i=2; i<=2160; i++)
{
if(!vv[i])
{
vv[i]=i;
prime[++tot]=i;
}
for(int j=1; j<=tot; j++)
{
if(prime[j]>vv[i] || prime[j]>2160/i)
break;
vv[i*prime[j]]=prime[j];
}
}
}
LL ksm(LL x,LL y)
{
LL res=1;
while(y)
{
if(y&1)
res*=x;
x*=x;
y>>=1;
}
return res;
}
void divide(LL x,int id)
{
int cnt=0; LL res=1,ress=1;
bool flag=1;
for(int j=1; j<=tot; j++)
{
if(prime[j]>x)
break;
if(x%prime[j]!=0)
continue;
int i=prime[j];
p[++cnt]=i; c[cnt]=0;
while(x%i==0 && x>1)
x/=i,c[cnt]++;
c[cnt]%=3;
res*=ksm(p[cnt],c[cnt]);
ress*=ksm(p[cnt],(3-c[cnt])%3);
flag&=(c[cnt]==0);
}
if(x>1)
{
flag=0;
if(x<=1e5)
res*=x,ress*=x*x;
else
{
LL sq=sqrt(x);
if(sq*sq==x)
res*=x,ress*=sq;
else
return isok[id]=1,void();
}
}
if(flag)
return iscub[id]=1,void();
val[id]=res; mt[id]=ress;
if(v.find(res)==v.end())
v[res]=++tv;
if(v.find(ress)==v.end())
v[ress]=++tv;
t[v[res]]++;
}
int main()
{
freopen("lovely.in","r",stdin);
freopen("lovely.out","w",stdout);
prework();
scanf("%d",&n);
for(int i=1; i<=n; i++)
scanf("%lld",&a[i]),divide(a[i],i);
int ans=0; bool flag=1;
for(int i=1; i<=n; i++)
{
if(iscub[i] && flag)
{
ans++; flag=0;
continue;
}
if(isok[i])
{
ans++;
continue;
}
if(vis[v[val[i]]])
continue;
int s1=t[v[val[i]]],s2=t[v[mt[i]]];
ans+=max(s1,s2);
vis[v[val[i]]]=vis[v[mt[i]]]=1;
}
printf("%d\n",ans);
return 0;
}
T3 诗
给定一个长度为 \(n\) 的字符串 \(S\)，\(q\) 次询问，每次给定字符串 \(T\)，求 \(T\) 在 \(S\) 中的出现次数
\(n\leq 10^5\)，\(q\leq 10^5\)，\(\sum{|T_i|}\leq 10^5\)，\(\max\{|T_i\}\leq 10^5\)
部分分有很多做法，考场 KMP 拿了 \(20\) 分，还有ACAM、哈希等
部分分中有一档 \(\max\{|T_i|\}\leq 50\) 给了我们提示，可以预先将 \(S\) 中长度小于等于 \(\max\{|T_i|\}\) 的子串的哈希值全部求出，然后询问时直接二分
但是当 \(\max\{|T_i|\}\) 变大之后，这种做法是不行的。考虑数据分治，设定一个阈值 \(B\)，对于长度在 \(B\) 以内的询问串使用上述做法，在 \(B\) 以上的直接枚举 \(S\) 所有长度为 \(|T_i|\) 的子串进行哈希匹配
第一种做法的时间复杂度为 \(\mathcal{O}(Bn\log n+q\log n)\)。由于长度在 \(B\) 以上的字符串最多 \(\dfrac{\sum |T_i|}{B}\)个，因此第二种复杂度为 \(\mathcal{O}\left(\dfrac{q\sum|T_i|}{B}\right)\)。将 \(n,q,\sum|T_i|\) 视作同阶，则 \(B=\sqrt{\dfrac{n}{\log n}}\) 时最优。实测 \(B=100\) 最优
code
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define ULL unsigned long long
#define pll pair <ULL,ULL>
using namespace std;
bool Mbe;
const int N=1e5+10,B=100,M=1e7+10;
const ULL base1=1e9+7,base2=998244353;
int n,q,op,a[N],b[N],siz[M];
ULL pw1[N],pw2[N];
pll ha[N],h[N];
pll tmp[M]; int cnt=0;
bool Med;
int main()
{
freopen("poem.in","r",stdin);
freopen("poem.out","w",stdout);
// fprintf(stderr, "%.3lfMB\n",(&Med-&Mbe)/1048576.0);
scanf("%d%d%d",&op,&n,&q);
for(int i=1; i<=n; i++)
scanf("%d",&a[i]);
pw1[0]=pw2[0]=1;
for(int i=1; i<=n; i++)
pw1[i]=pw1[i-1]*base1,pw2[i]=pw2[i-1]*base2;
ha[0]={0,0};
for(int i=1; i<=n; i++)
ha[i]={ha[i-1].first*base1+(ULL)a[i],ha[i-1].second*base2+(ULL)a[i]};
for(int j=1; j<=B; j++)
for(int i=1; i+j-1<=n; i++)
tmp[++cnt]={ha[i+j-1].first-ha[i-1].first*pw1[j],ha[i+j-1].second-ha[i-1].second*pw2[j]};
sort(tmp+1,tmp+1+cnt);
int lst=1; tmp[cnt+1]={0,0};
for(int i=1; i<=cnt+1; i++)
{
if(tmp[i]==tmp[lst])
continue;
for(int j=lst; j<i; j++)
siz[j]=i-1-lst+1;
lst=i;
}
int last=0;
while(q--)
{
int len,ans=0;
scanf("%d",&len);
for(int i=1; i<=len; i++)
{
scanf("%d",&b[i]);
if(op==1)
b[i]^=last;
}
if(len>n)
{
last=0;
puts("0");
continue;
}
h[0]={0,0};
for(int i=1; i<=len; i++)
h[i]={h[i-1].first*base1+(ULL)b[i],h[i-1].second*base2+(ULL)b[i]};
if(len<=B)
{
int x=lower_bound(tmp+1,tmp+1+cnt,h[len])-tmp;
if(h[len]==tmp[x])
ans=siz[x];
}
else
{
for(int i=1; i+len-1<=n; i++)
{
pll cur={ha[i+len-1].first-ha[i-1].first*pw1[len],ha[i+len-1].second-ha[i-1].second*pw2[len]};
if(cur==h[len])
ans++;
}
}
printf("%d\n",last=ans);
}
// cout<<clock()<<"ms";
return 0;
}