湖南集训 Day4

这几天一直和去湖南的同学换着题考试，考的也就那么回事，这几天有点懒，恕罪，博客少了好几篇。。。

T1 Count

正解：配对+拉格朗日插值法，，根本不是NOIP的范围，，，，，

我给你题解你拒绝接受！！

这题看看也就那么回事。。

//std代码 实话 丑的一批 #include <cstring> #include <ctime> #include <cmath> #include <cstdio> #include <cstdlib> #include <iostream> #include <algorithm> using namespace std; const int Mod=998244353; const int MAXK=1000000; int power(int x,int k) { int ret=1; while (k) { if (k&1) ret=1LL*ret*x%Mod; x=1LL*x*x%Mod; k>>=1; } return ret; } int k; int f[MAXK+10]; int pre[MAXK+10],suf[MAXK+10]; int jc[MAXK+10],K[MAXK+10]; int cnt(int n) { if (n==0) return 0; int ans=0; if (n<=k+10 || n<=MAXK) { for (int i=1;i<=n;i++) ans=(K[i]+ans)%Mod; } else { pre[0]=1; for (int i=1;i<=k+2;i++) pre[i]=1LL*pre[i-1]*(n-i)%Mod; suf[k+3]=1; for (int i=k+2;i>=1;i--) suf[i]=1LL*suf[i+1]*(n-i)%Mod; int l=k+1,r=0,flag=((k+1)&1)?(-1):(1); for (int i=1;i<=k+2;i++) { int s=1LL*pre[i-1]*suf[i+1]%Mod,m=1LL*(flag*jc[l]+Mod)*jc[r]%Mod; ans=(1LL*f[i]*s%Mod*power(m,Mod-2)%Mod+ans)%Mod; l--; r++; flag*=-1; } } ans=((ans+K[2])%Mod-1+Mod)%Mod; return ans; } int L,R; void init() { cin>>L>>R>>k; for (int i=1;i<=MAXK+5;i++) K[i]=power(i,k); jc[0]=1; for (int i=1;i<=k+2;i++) jc[i]=1LL*jc[i-1]*i%Mod; for (int i=1;i<=k+2;i++) f[i]=(f[i-1]+K[i])%Mod; cout<<(cnt(R)-cnt(L-1)+Mod)%Mod; return ; } int main() { freopen("count.in","r",stdin); freopen("count.out","w",stdout); init(); fclose(stdin); fclose(stdout); //fprintf(stderr,"%.3lf\n",1.0*clock()/(1.0*CLOCKS_PER_SEC)); return 0; }

T2 Blocks

题解：

//无良出题人 #include<cstring> #include<cstdio> #include<algorithm> #include<iostream> #define MAXN 1000005 using namespace std; typedef long long LL; int a[MAXN],st[MAXN],n; LL sum[MAXN]; inline void read(int &x){ x = 0; register char c = getchar(); while(c>'9'||c<'0') c = getchar(); while(c>='0'&&c<='9'){ x=x*10+c-'0'; c=getchar(); } } int Solve(int k) { int top = 1,ret = 0; for(int i=1; i<=n; i++) { sum[i] = sum[i - 1] + a[i] - k; if(!top || sum[i] < sum[st[top]]) st[++top] = i; } for(int i=n; i>=1; i--) { while(top && sum[st[top]] <= sum[i] ) --top; ret = max(ret, i - st[top + 1]); } return ret; } int main(int agrc,char *argv[]) { freopen("blocks.in","r",stdin); freopen("blocks.out","w",stdout); int m,k; read(n),read(m); for(int i=1; i<=n; ++i) read(a[i]); while(m--) { read(k); printf("%d ",Solve(k)); } fclose(stdin); fclose(stdout); return 0; }

T3 Biology

把字符串翻过来 – > 公共前缀 —-> Trie树

#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #define MAXN 1000005 using namespace std; int num[MAXN],dep[MAXN],Node = 1,nxt[MAXN][26],fa[MAXN][20]; char str[MAXN]; struct Trie { inline int NewNode(int fat){ ++Node; fa[Node][0] = fat,dep[Node] = dep[fat] + 1; for(int i=1; i<=17; ++i) fa[Node][i] = fa[ fa[Node][i-1] ][i-1]; return Node; } void Insert(char *s,int Num){ int cur = 1; int len = strlen(s); for(int i=0; i<(len >> 1); ++i) swap(s[i],s[len - i - 1]); for(int i=0; i<len; ++i) { if(!nxt[cur][s[i] - 'a']) nxt[cur][s[i] - 'a'] = NewNode(cur); cur = nxt[cur][s[i] - 'a']; } num[Num] = cur;//第Num个字符串在Trie树上的结束点 } } T; inline void read(int &x){ x=0; register char c = getchar(); while(c>'9' || c<'0') c = getchar(); while(c>='0' && c<='9'){ x=x*10+c-'0'; c = getchar(); } } int LCA(int u,int v){ int i = 17; if(dep[u] < dep[v]) swap(u,v); while (dep[u] != dep[v]) { while (dep[fa[u][i]] < dep[v] && i) i--; u = fa[u][i]; } i = 17; while (u != v){ while (fa[u][i] == fa[v][i] && i) i--; u = fa[u][i], v = fa[v][i]; } return u; } int main(int argc,char *argv[]){ freopen("biology.in","r",stdin); freopen("biology.out","w",stdout); int n,m,opt,x,P; read(n),read(m); Node = 1,dep[1] = 0; for(int i=1; i<=n; ++i){ scanf("%s",str); T.Insert(str,i); } while(m--){ read(opt); if(opt == 1) { scanf("%s",str); T.Insert(str,++n); } else { read(P),read(x); int Ans_Node = num[x]; for(int i=2; i<=P; ++i) read(x),Ans_Node = LCA(Ans_Node,num[x]); printf("%d\n",dep[Ans_Node]); } } fclose(stdin); fclose(stdout); return 0; }