2016 Multi – University Training Contest 5
本场抱住卓神大腿最后过了7题。。。感觉把PKU的牌子砸了。。。
我做了1001 1005 1011
随便口胡几句。。。
1010看起来像后缀数组。。。但是交wa了几发不知道什么情况
1001 ATM Mechine
这题似乎0元钱也要取1次1元的来确认一下，不然没法解释样例
\(f(i,j)\)表示有i元以内的钱，j次warning的机会
然后枚举询问点k，有t种可能warning，那么转移给\(f(t-1,j-1)\)
有i-k+1种可能取钱，转移给\(f(i-t,t)\)
边界j为1的情况，有k元钱需要询问k+1次
发现warning次数太多也没什么用，直接将其对30取min即可
也可以用决策的单调性加速转移
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include<map> #include<set> #include<ctime> #include<queue> #include<stack> #include<cmath> #include<vector> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define lb long double #define mod 1000000007 #define inf 9000000000000000000LL using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } double f[2005][35]; int g[2005][35]; double cal(int i,int j,int t) { return (double)(i-t+1)/(i+1)*f[i-t][j]+(double)t/(i+1)*f[t-1][j-1]+1; } int main() { for(int i=1;i<=2000;i++) for(int j=1;j<=30;j++) { if(j==1) { double x=i; f[i][j]=(3+x)*x/2/(x+1); } else { f[i][j]=inf; for(int t=1;t<=i;t++) if(cal(i,j,t)<f[i][j]) f[i][j]=cal(i,j,t); } } int n,m; while(scanf("%d%d",&n,&m)!=EOF) { m=min(m,30); printf("%.6lf\n",f[n][m]); } return 0; } |
1005 Interesting
回文自动机裸题
求出以i结尾的回文串个数和回文串总长度
枚举j计算
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long using namespace std; #define mod 1000000007 #define N 1000005 int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; char ch[N]; int a[N][26],fa[N]; int l[N],ans[N],num[N]; int id[N],tmp[N]; int cnt,last; void ini() { last=0;cnt=1;fa[0]=fa[1]=1;l[1]=-1; } void clear() { for(int i=0;i<=n;i++)fa[i]=l[i]=ans[i]=num[i]=0; for(int i=0;i<=n;i++) for(int j=0;j<26;j++) a[i][j]=0; } int extend(int c,int n) { int p=last; while(ch[n-l[p]-1]!=ch[n])p=fa[p]; if(!a[p][c]) { int now=++cnt,k=fa[p]; l[now]=l[p]+2; while(ch[n-l[k]-1]!=ch[n])k=fa[k]; fa[now]=a[k][c];a[p][c]=now; } last=a[p][c]; return last; } void solve() { for(int i=1;i<=cnt;i++) { ans[i]=l[i]; num[i]=1; ans[i]+=ans[fa[i]]; num[i]+=num[fa[i]]; ans[i]%=mod; } } bool check(int l,int r) { for(int i=1;i<=(r-l+1);i++) if(ch[i+l-1]!=ch[r-i+1]) return 0; return 1; } int main() { while(scanf("%s",ch+1)!=EOF) { ini(); ll res=0; n=strlen(ch+1); for(int i=1;i<=n;i++) id[i]=extend(ch[i]-'a',i); solve(); for(int i=1;i<=n;i++) { ll t=(ll)(i+1)*num[id[i]]-ans[id[i]]; tmp[i]=t%mod; } clear(); ini(); for(int i=1;i<=n/2;i++)swap(ch[i],ch[n-i+1]); for(int i=1;i<=n;i++) id[n-i+1]=extend(ch[i]-'a',i); solve(); for(int i=1;i<n;i++) { ll t1=(ans[id[i+1]]+(ll)i*num[id[i+1]])%mod; res+=tmp[i]*t1%mod; res%=mod; } clear(); cout<<res<<endl; } return 0; } |
1011 Two
\(f(i,j)表示\)第一个序列以a[i]结尾，第二个以b[j]结尾的方案数
用前缀和加速转移
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include<map> #include<set> #include<ctime> #include<queue> #include<stack> #include<cmath> #include<vector> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define lb long double #define mod 1000000007 #define inf 9000000000000000000LL using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,ans; int a[1005],b[1005]; ll f[1005][1005],sum[1005][1005]; int main() { while(scanf("%d%d",&n,&m)!=EOF) { memset(f,0,sizeof(f)); memset(sum,0,sizeof(sum)); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=m;i++)b[i]=read(); for(int i=0;i<=1000;i++)sum[i][0]=sum[0][i]=1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(a[i]==b[j])f[i][j]=sum[i-1][j-1]; sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+f[i][j]; sum[i][j]%=mod; if(sum[i][j]<0)sum[i][j]+=mod; } sum[n][m]--; if(sum[n][m]<0)sum[n][m]+=mod; cout<<sum[n][m]<<endl; } return 0; } |
计数器 9854578
OI 课件=>
OI 课件=>
学~