NOIP2017提高组 模拟赛 27（总结）
NOIP2017提高组 模拟赛 27（总结）
第一题 回文数 （推公式+快速幂）
【题目描述】
【解题思路】
长度为1的字符串，s[1]=9。
长度为3的字符串，s[3]=10*9。
长度为5的字符串，s[5]=10*10*9。
长度为7的字符串，s[7]=10*10*10*9。
……
所以，长度为2k+1的字符串，s[]=9*10^k
先把9忽略掉。
那么就是他们的系数就是
| k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | …… |
|---|---|---|---|---|---|---|---|---|---|
| 系数x | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | …… |
| 系数x(乘以10) | 0 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 |
最后
根据等比数列求和：
p=233333不是质数，用欧拉函数求出phi(p)
9的逆元(%p)=
或者是枚举i(1~p)，9*i%p==1，那么i就是9的逆元(%p)。
用快速幂随便搞搞……
【代码】
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
int T,n;
const ll mods=233333;
ll s,ni;
char ch;
int st[50];
ll Pow(ll x,ll y)
{
ll s=1ll;
for(;y;y>>=1,x=x*x%mods)
if(y&1) s=(s*x)%mods;
return s;
}
/*int read()
{
int yu=0;
while((ch=getchar())!='\n')
{
yu=(yu<<3)+(yu<<1)+ch-'0';
}
return yu;
}
void print()
{
int le=0;
while(s)
{
st[++le]=s%10;
s/=10;
}
for(int i=le;i>=1;i--) putchar('0'+st[i]);
putchar('\n');
}*/
int main()
{
freopen("2255.in","r",stdin);
freopen("2255.out","w",stdout);
scanf("%d",&T);
//T=read();
ni=Pow(9,232320-1);
for(register int h=1;h<=T;++h)
{
scanf("%d",&n);
//n=read();
n=(n+1)>>1;
ll ty=Pow(10,n);
ll cy=ty*((n-1)<<1|1)%mods;
ty=2*(ty-1+mods)%mods;
ty=(ty*ni%mods-1+mods)%mods;
s=(cy-ty+mods)%mods;
//print();
printf("%lld\n",s);
}
return 0;
}第二题 购物 （DP）
【题目描述】
【解题思路】
一开始，看错题了，额，把题目想复杂了，以为是行动的总和（第一次扫）的平方（也就是不必连续，其实是要求连续的）……
首先，若一段区间A，完全包含区间B，那么区间B是完全没有的。
那么，预处理出左端点为L，所能延伸的最长的R，即far[L]。
所以最多也只会有n区间而已（n=5000）。
预处理出前缀和sum[]
假设，先选区间[3,5]，再选区间[1,4]，那么就是[1,2][3,5]。
如果先选区间[1,4]，再选区间[3,5]，那就是[1,4][5]。
因为happy值是非负的，所以，若存在区间[a,far[a]]，那么就可以选区间[a,a]~[a,far[a]]。
为什么？
平方的和不大于和的平方。所以转移之后所得到的最优解中的某个断点(即这个点之前是一次购买，之后是另一次购买)一定是对应的两个区间中的某一个的端点。这样是一定可以找到一种符合要求的购买顺序的。
【代码】
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define imax(a,b) ((a>b)?(a):(b))
using namespace std;
typedef long long ll;
const int N=6000;
int n,m,a[N],far[N];
ll sum[N],ans,f[N];
int main()
{
freopen("2256.in","r",stdin);
freopen("2256.out","w",stdout);
scanf("%d%d",&n,&m); ans=0ll;
for(int i=1;i<=n;i++) scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
for(int i=1;i<=m;i++)
{
int al,ar;
scanf("%d%d",&al,&ar);
far[al]=imax(far[al],ar);
}
for(int i=1;i<=n;i++)
if(far[i])
{
for(int j=i+1;j<=far[i];j++)
if(far[j]<=far[i]) far[j]=0;
}
f[0]=0ll; int mx=0ll;
for(int i=1;i<=n;i++)
{
f[i]=imax(f[i],f[i-1]);
far[i]=imax(far[i],far[i-1]);
for(int j=i;j<=far[i];j++)
{
ll yu=sum[j]-sum[i-1];
f[j]=imax(f[j],f[i-1]+yu*yu);
}
ans=imax(f[i],ans);
}
/*for(int i=1;i<=n;i++)
{
ll mx=0ll; int mi=0;
for(int j=1;j<=n;j++)
{
ll yu=sum[far[j]]-sum[j-1];
if(yu>mx)
{
mx=yu;
mi=j;
}
}
ans+=mx*mx;
for(int j=1;j<=n;j++)
{
if(j<mi && far[j]>=mi) far[j]=mi-1;
}
int fl=0;
for(int j=1;j<=n;j++)
if(j>mi && j<=far[mi])
{
fl=imax(fl,far[j]);
far[j]=0;
}
far[far[mi]+1]=fl;
far[mi]=0;
}*/
printf("%lld\n",ans);
return 0;
}第三题 宗教 （SAM+LCA(RMQ优化)）
【题目描述】
【解题思路】
①将s2串反过来，那么，设st是s1的子串且长度与s2相同，st的结尾串的位置为len（下标从0开始）。
st与s2的相同字符数就是
这显然是一个卷积的形式。
那么，直接枚举26个字符，把等于当前枚举的字符的位置设为1，其他为0。做一次FFT，每一个len就对应着不同st串，累加相同的次数。
时间复杂度：O(26*n log n)
②再次观察，k≤100。
判断st与s2时，直接找k次的最长公共前缀。
那么，如何快速找出最长的公共前缀呢？
因为SAM的parents树就是反串的后缀树
那么，只需要把s1的反串和s2的反串连起来，中间加个特殊符号。跑一次SAM。
因此，s1[now1]和s2[now2]开始匹配。
若s1[now1]!=s2[now2]，则now1++,now2++（直到相同为止）
用原串的位置所对应的在SAM的状态，找到parents树上的LCA，也就是最长的公共前缀，长度为dep[LCA]。
下一次从s1[now1+dep[LCA]]和s2[now2+dep[LCA]]处开始匹配。
至于LCA，可以用RMQ优化到O(1)。
遍历整棵树的每一条边。如上图，遍历的结果就是1 2 4 2 5 6 7 6 5 2 1 3
边数为m，则最多遍历的点数为2m。
假设w[x]＜w[y]（w[i]为第一次遍历到点i的时间戳）
那么，点x和点y的LCA就是遍历结果中的w[x]~w[y]之间的dep最小的点。
例如，x=4，y=6时。w[x]=3，w[y]=6。之间的点为2 5，点2的dep最小，因此，点2是x和y的LCA。
因为w[x]~w[y]就是x走到y的路经+路径上的点的子树。路径上的点的子树是没用的（子树的dep必定大于路径上的点的dep），所以dep最小的点必定是x和y的LCA。
也就是RMQ维护区间最小值。
时间复杂度：O(n*100+n log n)
Accept（额，加了register和inline才过）
【代码】
//SAM+LCA(RMQ优化)
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define imax(a,b) ((a>b)?(a):(b))
#define imin(a,b) ((a<b)?(a):(b))
using namespace std;
typedef long long ll;
const int M=600600;
const int N=201000;
char s1[N],s2[N];
int n,m,kk,ans;
int Td,root,last;
int to[M],ne[M],h[M],tt;
int wei[M];
int tis[55],lg2[M<<1];
int rmq[M<<1][22],tim[M],dfstime;
int op[M],tail;
struct state { int par,val,go[27]; } T[M];
void Insert(int w,int yi)
{
int p=last;
T[++Td].val=T[p].val+1;
int np=Td;
last=wei[yi]=np;
for(;p && T[p].go[w]==0;p=T[p].par) T[p].go[w]=np;
if(p==0) T[np].par=root; else
{
int q=T[p].go[w];
if(T[p].val+1==T[q].val) T[np].par=q; else
{
T[++Td].val=T[p].val+1;
int nq=Td;
memcpy(T[nq].go,T[q].go,sizeof(T[q].go));
T[nq].par=T[q].par;
T[q].par=nq;
T[np].par=nq;
for(;p && T[p].go[w]==q;p=T[p].par) T[p].go[w]=nq;
}
}
}
void addedge(int a,int b) { to[++tt]=b; ne[tt]=h[a]; h[a]=tt; }
/*void dfs(int x)
{
tim[x]=++dfstime;
rmq[dfstime][0]=x;
for(int p=h[x];p;p=ne[p])
{
dfs(to[p]);
rmq[++dfstime][0]=x;
}
}*/
void dfs(int x)
{
tail=1; op[1]=x;
while(tail)
{
rmq[++dfstime][0]=op[tail];
if(h[op[tail]])
{
int yt=op[tail];
op[++tail]=to[h[yt]];
h[yt]=ne[h[yt]];
} else tail--;
}
for(int i=1;i<=dfstime;i++)
if(!tim[rmq[i][0]]) tim[rmq[i][0]]=i;
}
inline int ance(int x,int y) { return ((T[x].val<T[y].val)?(x):(y)); }
inline int len(int x,int y)
{
x=tim[wei[n-x]];
y=tim[wei[n+m-y]];
if(x>y) swap(x,y);
int ly=lg2[y-x];
return (T[ance(rmq[x][ly],rmq[y-tis[ly]+1][ly])].val);
}
void ready()
{
scanf("%s",s1); Td=1; tt=1;
T[1].val=0; root=1; last=1;
n=strlen(s1);
for(int i=n-1;i>=0;i--) Insert(s1[i]-'a',n-i);
scanf("%s",s2);
m=strlen(s2);
Insert(26,0);
for(int i=m-1;i>=0;i--) Insert(s2[i]-'a',n+m-i);
scanf("%d",&kk);
for(int i=2;i<=Td;i++) addedge(T[i].par,i);
dfstime=0; dfs(1);
tis[0]=1;
for(int i=1;i<=25;i++) tis[i]=tis[i-1]<<1;
lg2[1]=0;
for(int i=2;i<=dfstime;i++)
if(tis[lg2[i-1]+1]<=i) lg2[i]=lg2[i-1]+1; else lg2[i]=lg2[i-1];
for(int j=1;j<=21;j++)
for(int i=1;i<=dfstime;i++)
{
rmq[i][j]=rmq[i][j-1];
if(i+tis[j-1]<=dfstime) rmq[i][j]=ance(rmq[i][j-1],rmq[i+tis[j-1]][j-1]);
}
}
int main()
{
freopen("2257.in","r",stdin);
freopen("2257.out","w",stdout);
ready();
for(register int i=0;i<=n-m;i++)
{
int now1=i,now2=0,df=0;
while(now2<m)
{
while(s1[now1]!=s2[now2] && now2<m)
{
df++;
if(df>kk) break;
now1++; now2++;
}
if(df>kk || now2==m) break;
int go=len(now1,now2);
now1+=go; now2+=go;
}
if(df<=kk) ans++;
}
printf("%d\n",ans);
return 0;
}//FFT 常数太大 TLE
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define imax(a,b) ((a>b)?(a):(b))
#define imin(a,b) ((a<b)?(a):(b))
using namespace std;
typedef long long ll;
const ll mods=1000000007;
const int N=201000;
const double pi=acos(-1.0);
char st[N];
int d[N],w[N],n,m,kk,k,th[N<<1],sum;
struct Complex
{
double real,image;
Complex() {}
Complex(double _real,double _image)
{
real=_real; image=_image;
}
friend Complex operator + (Complex A,Complex B) { return Complex(A.real+B.real,A.image+B.image); }
friend Complex operator - (Complex A,Complex B) { return Complex(A.real-B.real,A.image-B.image); }
friend Complex operator * (Complex A,Complex B) { return Complex(A.real*B.real-A.image*B.image,A.image*B.real+A.real*B.image); }
} A[N<<2],B[N<<2];
int rev[N<<2];
void FFT(Complex *A,int n,int DFT)
{
for(int i=0;i<n;i++) if(i<rev[i]) swap(A[i],A[rev[i]]);
for(int s=1;(1<<s)<=n;s++)
{
int mi=(1<<s);
Complex wn=Complex(cos(2*pi/mi),DFT*sin(2*pi/mi));
for(int t=0;t<n;t+=mi)
{
Complex w=Complex(1,0);
for(int j=0;j<(mi>>1);j++)
{
Complex u=A[t+j],v=w*A[t+j+(mi>>1)];
A[t+j]=u+v; A[t+j+(mi>>1)]=u-v;
w=w*wn;
}
}
}
if(DFT==-1) for(int i=0;i<n;i++) A[i].real/=n,A[i].image/=n;
}
int main()
{
freopen("2257.in","r",stdin);
freopen("2257.out","w",stdout);
scanf("%s",st);
n=strlen(st);
for(int i=0;i<n;i++) d[i]=st[i]-'a'+1;
scanf("%s",st);
m=strlen(st);
for(int i=0;i<m;i++) w[i]=st[i]-'a'+1;
scanf("%d",&kk);
for(int i=1;i<=(m>>1);i++) swap(w[i-1],w[m-i]);
n--; m--;
int yn=n+m,nn; k=0;
for(nn=1;nn<=yn;nn<<=1) k++;
for(int i=0;i<nn;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(k-1));
for(int h=1;h<=26;h++)
{
for(int i=0;i<=nn;i++)
{
A[i].real=(d[i]==h)?1:0;
B[i].real=(w[i]==h)?1:0;
A[i].image=B[i].image=0;
}
FFT(A,nn,1); FFT(B,nn,1);
for(int i=0;i<=nn;i++) A[i]=A[i]*B[i];
FFT(A,nn,-1);
for(int i=m;i<=n;i++)
th[i]+=(int)(A[i].real+0.4);
}
for(int i=m;i<=n;i++)
if(th[i]>=(m+1-kk)) sum++;
printf("%d\n",sum);
return 0;
}