9.8考试
题面
T1
T2
T3
三道原题所以没密码。题解。。。
T1
设f[i][j]为放i个数j种数的方案。然后转移方程求法：
1.最后一个数以前没出现过。有(n-j+1)种。\(f[i][j]+=f[i-1][j-1×(n-j+1)]\) 2.最后一个数以前出现过。有j种，但前面有m种不能选，所以是(j-m)种。\(f[i][j]=f[i-1][j]×(j-m)\) 然鹅j-m可能爆负，所以先求出f[m][m]。\(f[m][m]=P_m^n\)。// It is made by XZZ#include#include #define Fname "pf"using namespace std;#define rep(a,b,c) for(rg int a=b;a<=c;a++)#define drep(a,b,c) for(rg int a=b;a>=c;a--)#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])#define il inline#define rg register#define vd voidtypedef long long ll;il int gi(){ rg int x=0,f=1;rg char ch=getchar(); while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar(); while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*f;}ll f[1010][1010];//f[i][j]://放i个数j种数的方案ll mod=1e9+7;int main(){ freopen(Fname".in","r",stdin); freopen(Fname".out","w",stdout); int n=gi(),m=gi(),p=gi(); if(p==n){ll prt=1;rep(i,2,n)prt=prt*i%mod;printf("%lld\n",prt);return 0;} if(p
T2
裸dp。然鹅考场上没调出来，不知道为什么，然后稍稍调一下上界就过了。。。
设f[i][j][k]为当前挑战完第i场，共胜利j场，背包容量k（可负）的获胜概率。 方程： 1.胜利，\(f[i][j][k]×p[i+1]->f[i+1][j+1][k+a[i]]\) 2.失败，\(f[i][j][k]×(1-p[i+1])->f[i+1][j][k]\) k可负就整体加一个值 先与n取min，剩下的没用// It is made by XZZ#include#include #define Fname "guard"using namespace std;#define rep(a,b,c) for(rg int a=b;a<=c;a++)#define drep(a,b,c) for(rg int a=b;a>=c;a--)#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])#define il inline#define rg register#define vd voidtypedef long long ll;il int gi(){ rg int x=0,f=1;rg char ch=getchar(); while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar(); while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*f;}#define db doubledb p[210];int a[210];db F[201][201][401];#define f(a,b,c) (F[a][b][min((c)+n,n*2)]) int main(){ freopen(Fname".in","r",stdin); freopen(Fname".out","w",stdout); int n=gi(),L=gi(),K=gi(); rep(i,1,n)scanf("%lf",&p[i]),p[i]/=100.00; rep(i,1,n)a[i]=gi(); f(0,0,K)=1; rep(i,0,n-1)rep(j,0,i)rep(k,-i,n) f(i+1,j+1,k+a[i+1])+=f(i,j,k)*p[i+1], f(i+1,j,k)+=f(i,j,k)*(1-p[i+1]); db ans=0; rep(i,L,n)rep(j,0,n)ans+=f(n,i,j); printf("%.6lf\n",ans); return 0;}
T3
选若干个数，不能取连续的k+1个，求最大和
反过来也是可以的，选若干个数，相邻两数距离不超过k，求最小和 设f[i]表示1~i区间里选若干个数，相邻两数距离不超过k的最小和(f[0]=0)\(f[i]=min{f[i-j]}+e[i](j\in[i-k,i-1])\) 这就有70了。再弄个单调队列优化一下// It is made by XZZ#include#include #ifndef lemon#define Fname "mowlawn"#else#define Fname "cg"#endifusing namespace std;#define rep(a,b,c) for(rg int a=b;a<=c;a++)#define drep(a,b,c) for(rg int a=b;a>=c;a--)#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])#define il inline#define rg register#define vd voidtypedef long long ll;il ll gi(){ rg ll x=0;rg char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x;}ll f[100010],e[100010];int que[100010],hd=0,tl=0;int main(){ freopen(Fname".in","r",stdin); freopen(Fname".out","w",stdout); int n=gi(),k=gi();ll sum=0; rep(i,1,n)e[i]=gi(),sum+=e[i]; e[n+1]=0;++n; f[0]=0; rep(i,1,n){ f[i]=2e18; while(hd^tl&&que[hd]