作者：成就未来7368 | 来源：互联网 | 2023-09-15 12:52
本文由编程笔记#小编为大家整理，主要介绍了9.10模拟赛相关的知识，希望对你有一定的参考价值。
T1：
一道比较漂亮的数学题。
30分暴力，40分可以直接化简 。
i%j怎么办？只能i%j=i-[i/j]*j
对于正解：
Ci=∑a[i/j]*b(i-[i/j]*j)
[i/j]有一个特点，一共只有根号i种可能。
j<根号，可以直接枚举，
j大于根号，[i/j]是连续的区间，区间左右端点 l , r 可以计算。这时，a[i/j]固定。
考虑b会是哪些，[i/j]固定，发现，b的下标，这是一个等差数列。
所以，f[i][j]表示，从bi开始，每j个算一个和，到不能减为止，前缀和的值。
那么，对于[i/j]的所在区间，，b可以直接算出：f[ i-[i/j]*l ][ [i/j] ] - f[ i-[i/j]*(r+1) ][ [i/j] ] 前缀差分。
所以，复杂度O(n根号n）
代码：
#include
#define ri register int
using namespace std;
typedef long long ll;
const int N=100000+3;
const int M=320;
const int mod=123456789;
ll a[N],b[N],c[N];
int n,m;
ll f[N][M];
int main(){
scanf("%d",&n);
for(ri i=1;i<=n;i++)scanf("%d",&a[i]);
for(ri i=1;i<=n;i++)scanf("%d",&b[i-1]);
for(ri i=0;i<=n-1;i++){
for(ri j=1;j<=318;j++){
if(i-j>=0) f[i][j]=(f[i-j][j]+b[i])>=mod?f[i-j][j]+b[i]-mod:f[i-j][j]+b[i];
else f[i][j]=b[i];
}
}
for(ri i=1;i<=n;i++){
//cout<<"iiii "<
int j;
for(j=1;j*j<=i;j++){
(c[i]+=a[i/j]*b[i-(i/j)*j])%=mod;
}
//cout<<" before "<
int las=j-1;
for(ri an=i/j;an;an--){
//cout<<" an "<
int mx=i/an;
int len=mx-las;
//cout< //cout<
(c[i]+=a[an]*(f[i-an*(las+1)][an]-((i-an*(mx+1)>=0)?f[i-an*(mx+1)][an]:0)))%=mod;
las=mx;
}
printf("%d
",c[i]);
}
// for(int i=1;i<=n;i++)
return 0;
}
T3：
题解：
其实就是不大于k个不同的，就是出现过一次。
正解后缀数组+RMQ 滚。
暴力能AC？？？ 需要：
1.register int 竟然优化很多？？
2.如果已经有k个不同的，就break
原本70pts 的哈希：
k很小，直接二分LCP，然后跳k次。复杂度O(n logm * k)
优化：
1.register int 不管用了。
2.如果当前位置不同，就手动往后走一步，理论可以省几次logm二分。
但是，优化很明显（数据太水）
然后AC了。
代码：
#include<iostream>
#include
#include
#include
#include
#include
#define ri register int
#define numb ch-‘0‘
using namespace std;
typedef long long ll;
typedef unsigned long long ui;
//typedef register int ri;
const int N=200000+5;
const int M=100000+5;
const int P=31;
ui mi[N];
ui h1[N];
ui h2[M];
char s1[N],s2[M];
int n,m;
int k;
int ans;
int main()
{
//freopen("mo.in","r",stdin);
//freopen("mo.out","w",stdout);
scanf("%s",s1+1);
scanf("%s",s2+1);
n=strlen(s1+1);
m=strlen(s2+1);
scanf("%d",&k);
mi[0]=1;
int up=max(n,m);
if(up<=1005){
for(int i=1;i<=n-m+1;i++){
int cnt=0;
int r=i;
for(int j=1;j<=m;j++){
if(s1[r]!=s2[j]) cnt++;
r++;
if(cnt>k) break;
}
//cout<
if(cnt<=k) ans++;
}
printf("%d",ans);
return 0;
}
for(int i=1;i<=up;i++){
mi[i]=mi[i-1]*P;
}
for(int i=1;i<=n;i++){
h1[i]=h1[i-1]*P+s1[i]-‘a‘;
}
for(int j=1;j<=m;j++){
h2[j]=h2[j-1]*P+s2[j]-‘a‘;
}
for(int i=1;i<=n-m+1;i++){
//cout<<" iii "<
int cnt=0;
int l1=i,l2=1,r1=i+m-1,r2=m;
while(cnt<=k&&l1<=i+m-1){
if(s1[l1]!=s2[l2]){
l1++;l2++;
cnt++;
}
else{
int L=l1,R=r1;
int mx=l1-1;
while(L<=R){
int mid=(L+R)>>1;
int an=mid-i+1;
ui hsh1=h1[mid]-h1[l1-1]*mi[mid-l1+1];
ui hsh2=h2[an]-h2[l2-1]*mi[an-l2+1];
if(hsh1==hsh2){
mx=mid,L=mid+1;
}
else R=mid-1;
}
if(mx==r1){
break;
}
else{
cnt++;
l1=mx+2;
l2=mx-i+3;
}
}
//cout<<" l1 "<
}
//cout<
if(cnt<=k){
ans++;
}
}
printf("%d",ans);
return 0;
}
京公网安备 11010802041100号