10.8 模拟赛
分类:
IT文章
•
2022-02-28 19:23:27
非常的菜 被初中踩成了弱智
T1 game
题目大意：
n轮游戏 在第$i$轮已经获胜$j$轮继续获胜的概率为 p i j
每一轮可以选择放弃（即100%失败）
求最优策略下 获胜场数的期望
思路：
可以发现并不需要放弃
直接dp即可
![]()
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cstdlib>
5 #include<cmath>
6 #include<algorithm>
7 #include<queue>
8 #include<vector>
9 #include<map>
10 #define inf 2139062143
11 #define ll long long
12 #define MAXN 1100
13 using namespace std;
14 inline int read()
15 {
16 int x=0,f=1;char ch=getchar();
17 while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
18 while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
19 return x*f;
20 }
21 //yyc score=0
22 int n;
23 double a[MAXN][MAXN],dp[MAXN][MAXN],ans;
24 int main()
25 {
26 freopen("game.in","r",stdin);
27 freopen("game.out","w",stdout);
28 n=read();
29 for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) scanf("%lf",&a[i][j]);
30 dp[1][1]=1.0;
31 for(int i=2;i<=n+1;i++) for(int j=1;j<=i;j++)
32 dp[i][j]=dp[i-1][j]*(1.0-a[i-1][j])+dp[i-1][j-1]*a[i-1][j-1];
33 for(int i=1;i<=n+1;i++) ans+=(i-1)*dp[n+1][i];
34 printf("%.2lf",ans);
35 }
View Code
T2 cake
题目大意：
n个物品 每个物品体积即背包$le 10^9$ 求背包内最大体积
思路：
本来是一个折半搜索裸题
![]()
1 #include<bits/stdc++.h>
2 #define LL long long
3 #define M 1200020
4 using namespace std;
5 namespace IO{
6 const int BS=(1<<20)+5; int Top=0;
7 char Buffer[BS],OT[BS],*OS=OT,*HD,*TL,SS[20]; const char *fin=OT+BS-1;
8 char Getchar(){if(HD==TL){TL=(HD=Buffer)+fread(Buffer,1,BS,stdin);} return (HD==TL)?EOF:*HD++;}
9 void flush(){fwrite(OT,1,OS-OT,stdout);}
10 void Putchar(char c){*OS++ =c;if(OS==fin)flush(),OS=OT;}
11 void write(int x){
12 if(!x){Putchar('0');return;} if(x<0) x=-x,Putchar('-');
13 while(x) SS[++Top]=x%10,x/=10;
14 while(Top) Putchar(SS[Top]+'0'),--Top;
15 }
16 int read(){
17 int nm=0,fh=1; char cw=getchar();
18 for(;!isdigit(cw);cw=getchar()) if(cw=='-') fh=-fh;
19 for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');
20 return nm*fh;
21 }
22 }using namespace IO;
23 int n,m,val[50][2],p[2][M],maxn,tp[2],sz[2],ans;
24 void dfs(int pos,int now,int kd){
25 if(now>m) return;
26 if(pos==tp[kd]+1){p[kd][++sz[kd]]=now;return;}
27 dfs(pos+1,now,kd),dfs(pos+1,now+val[pos][kd],kd);
28 }
29 int main(){
30 freopen("cake.in","r",stdin);
31 freopen("cake.out","w",stdout);
32 n=read(),m=read(),ans=m;
33 for(int i=1;i<=n;i++) val[++tp[i&1]][i&1]=read();
34 dfs(1,0,0),sort(p[0]+1,p[0]+sz[0]+1);
35 dfs(1,0,1),sort(p[1]+1,p[1]+sz[1]+1);
36 for(int i=0,j=sz[1];i<=sz[0];i++){
37 while(j>0&&p[0][i]+p[1][j]>m) j--;
38 ans=min(ans,m-p[0][i]-p[1][j]);
39 }printf("%d
",ans);return 0;
40 }
View Code
但是我非常菜的直接dfs剪枝得了90分
![]()
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cstdlib>
5 #include<cmath>
6 #include<algorithm>
7 #include<queue>
8 #include<vector>
9 #include<map>
10 #define inf 2139062143
11 #define ll long long
12 #define MAXN 50
13 #define MOD 1000000007
14 using namespace std;
15 inline int read()
16 {
17 int x=0,f=1;char ch=getchar();
18 while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
19 while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
20 return x*f;
21 }
22 //yyc score=0
23 int n,m,a[MAXN],ans=inf,s[MAXN];
24 map <int,bool> vis;
25 void dfs(int x,int sum)
26 {
27 //cout<<x<<" "<<sum+a[x]<<endl;
28 if(sum+a[x]>m||vis[sum+a[x]]) return ;vis[sum+a[x]]=1,ans=min(ans,m-sum-a[x]);
29 if(x==1) {ans=min(ans,m-sum-a[x]);return ;}
30 if(sum+s[1]-s[x+1]<=m) {ans=min(ans,m-sum-s[1]+s[x+1]);return ;}
31 for(int i=x-1;i;i--)
32 if(sum+a[x]+a[i]<=m) dfs(i,sum+a[x]);
33 }
34 int main()
35 {
36 freopen("cake.in","r",stdin);
37 freopen("cake.out","w",stdout);
38 n=read(),m=read();
39 for(int i=1;i<=n;i++) a[i]=read();
40 sort(a+1,a+n+1);
41 for(int i=n;i;i--) s[i]=s[i+1]+a[i];
42 vis[0]=1;
43 for(int i=n;i;i--) dfs(i,0);
44 printf("%d
",ans);
45 }
View Code
T3 grid
题目大意：
一个矩阵 规定一些子矩阵内最大值为k 求满足条件矩阵的方案数
思路：
离散化之后处理每个矩阵的大小
然后容斥
（std）
![]()
1 #include<bits/stdc++.h>
2 typedef long long i64;
3 const int P=1e9+7;
4 int T,h,w,m,n;
5 int xs[33],ys[33],xp,yp,vs[33],vp,ts[33];
6 int rc[33][5],mv[33][33],as[33][33];
7 void mins(int&a,int b){if(a>b)a=b;}
8 int pw(int a,int n){
9 int v=1;
10 for(;n;n>>=1,a=i64(a)*a%P)if(n&1)v=i64(v)*a%P;
11 return v;
12 }
13 int main(){
14 int ans=0;
15 scanf("%d%d%d%d",&h,&w,&m,&n);
16 xp=yp=vp=0;
17 xs[xp++]=1;
18 xs[xp++]=h+1;
19 ys[yp++]=1;
20 ys[yp++]=w+1;
21 vs[vp++]=m;
22 for(int i=0;i<n;++i){
23 for(int j=0;j<5;++j)scanf("%d",rc[i]+j);
24 xs[xp++]=rc[i][0];
25 xs[xp++]=rc[i][2]+1;
26 ys[yp++]=rc[i][1];
27 ys[yp++]=rc[i][3]+1;
28 vs[vp++]=rc[i][4];
29 vs[vp++]=rc[i][4]-1;
30 }
31 std::sort(xs,xs+xp);
32 xp=std::unique(xs,xs+xp)-xs-1;
33 std::sort(ys,ys+yp);
34 yp=std::unique(ys,ys+yp)-ys-1;
35 std::sort(vs,vs+vp);
36 vp=std::unique(vs,vs+vp)-vs;
37 for(int i=0;i<xp;++i)
38 for(int j=0;j<yp;++j)as[i][j]=(xs[i+1]-xs[i])*(ys[j+1]-ys[j]);
39 for(int t=0;t<n;++t){
40 rc[t][0]=std::lower_bound(xs,xs+xp,rc[t][0])-xs;
41 rc[t][2]=std::lower_bound(xs,xs+xp,rc[t][2]+1)-xs;
42 rc[t][1]=std::lower_bound(ys,ys+yp,rc[t][1])-ys;
43 rc[t][3]=std::lower_bound(ys,ys+yp,rc[t][3]+1)-ys;
44 rc[t][4]=std::lower_bound(vs,vs+vp,rc[t][4])-vs;
45 }
46 for(int S=0;S<(1<<n);++S){
47 for(int i=0;i<xp;++i)
48 for(int j=0;j<yp;++j)mv[i][j]=vp-1;
49 int s=1;
50 for(int t=0;t<n;++t){
51 int v=rc[t][4];
52 if(S>>t&1)s=-s,--v;
53 for(int i=rc[t][0];i<rc[t][2];++i)
54 for(int j=rc[t][1];j<rc[t][3];++j)mins(mv[i][j],v);
55 }
56 for(int i=0;i<vp;++i)ts[i]=0;
57 for(int i=0;i<xp;++i)
58 for(int j=0;j<yp;++j)ts[mv[i][j]]+=as[i][j];
59 for(int i=0;i<vp;++i)s=i64(s)*pw(vs[i],ts[i])%P;
60 ans=(ans+s)%P;
61 }
62 printf("%d
",(ans+P)%P);
63 return 0;
64 }
View Code
![]()
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cstdlib>
5 #include<algorithm>
6 #include<cmath>
7 #include<queue>
8 #include<vector>
9 #define ll long long
10 #define MAXN 200100
11 #define inf 2139062143
12 using namespace std;
13 inline int read()
14 {
15 int f=1,x=0;char ch=getchar();
16 while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
17 while(isdigit(ch)) {x=x*10+ch-'0',ch=getchar();}
18 return x*f;
19 }
20 int n,q,s,cnt,tot,fst[MAXN],nxt[MAXN<<1],to[MAXN<<1],val[MAXN<<1];
21 int dep[MAXN],f[MAXN][22],g[MAXN][22],dis[MAXN],sz[MAXN],hsh[MAXN];
22 void add(int u,int v,int w) {nxt[++cnt]=fst[u],fst[u]=cnt,to[cnt]=v,val[cnt]=w;}
23 void dfs(int x,int fa)
24 {
25 sz[x]=1,hsh[x]=++tot;
26 for(int i=1;(1<<i)<=dep[x];i++) f[x][i]=f[f[x][i-1]][i-1];
27 for(int i=1;(1<<i)<=dep[x];i++) g[x][i]=min(g[x][i-1],dis[x]-dis[f[x][i-1]]+g[f[x][i-1]][i-1]);
28 for(int i=fst[x];i;i=nxt[i])
29 if(to[i]!=fa)
30 {
31 f[to[i]][0]=x,dep[to[i]]=dep[x]+1,dis[to[i]]=dis[x]+val[i];
32 if(val[i]<0) g[to[i]][0]=val[i];
33 dfs(to[i],x);sz[x]+=sz[to[i]];
34 }
35 }
36 int lca(int u,int v)
37 {
38 if(dep[u]<dep[v]) swap(u,v);int t=dep[u]-dep[v];
39 for(int i=21;i>=0;i--) if((1<<i)&t) u=f[u][i];
40 if(u==v) return u;
41 for(int i=21;i>=0;i--)
42 if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
43 return f[u][0];
44 }
45 int work(int x,int anc)
46 {
47 int t=dep[x]-dep[anc],tmp=0,res=0;
48 for(int i=21;i>=0;i--)
49 if((1<<i)&t)
50 res=min(res,tmp+g[x][i]),
51 tmp+=dis[x]-dis[f[x][i]],x=f[x][i];
52 return res;
53 }
54 int main()
55 {
56 freopen("road.in","r",stdin);
57 freopen("road.out","w",stdout);
58 n=read(),q=read(),s=read();int a,b,c,l3,res,sum;
59 for(int i=1;i<n;i++) {a=read(),b=read(),c=read();add(a,b,c);add(b,a,c);}
60 dfs(s,0);
61 while(q--)
62 {
63 a=read(),b=read(),c=lca(a,b),res=sum=dis[a]+dis[b]-(dis[c]<<1);
64 printf("%d
",min(work(a,c)+dis[b]-dis[c],work(b,c)+dis[a]-dis[c]));
65 }
66 }
