【2018.11.8】小迟的比赛 / Yuno like cake / 格子填数
分类:
IT文章
•
2023-10-31 11:10:23
题目
$noip$ 欢乐赛真是欢乐,除了不欢乐的方面以外我都很欢乐。
T1
鸡汤题目,故意输对后面的胜率又没有影响,为什么要故意输呢?
所以第二个决策是凑字用的,这题就是朴素递推概率,最后乘结果权值计算期望。
1 #include<cctype>
2 #include<cstdio>
3 #include<cstdlib>
4 #include<cstring>
5 #include<iostream>
6 #include<algorithm>
7 using namespace std;
8 inline int read(){
9 int x=0; bool f=1; char c=getchar();
10 for(;!isdigit(c);c=getchar()) if(c=='-') f=0;
11 for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^'0');
12 if(f) return x;
13 return 0-x;
14 }
15 #define N 1001
16 int n;
17 double p[N][N],f[N][N];
18 int main(){
19 freopen("game.in","r",stdin);
20 freopen("game.out","w",stdout);
21 n=read();
22 int i,j;
23 f[0][0]=1;
24 for(i=1;i<=n;++i){
25 cin>>p[i][j]; f[i][0]=f[i-1][0]*(1-p[i][j]);
26 for(j=1;j<i;++j){
27 cin>>p[i][j];
28 f[i][j]=f[i-1][j-1]*p[i][j-1]+f[i-1][j]*(1-p[i][j]);
29 }
30 f[i][j]=f[i-1][j-1]*p[i][j-1];
31 }
32 double ans=0;
33 for(i=1;i<=n;++i) ans+=f[n][i]*i;
34 printf("%.2f",ans);
35 return 0;
36 }
View Code
T2
原题……在日本竞赛书上看到过……
把 $40$ 个数平分成两半,枚举其中一半的选取情况,然后在另一半中二分出能取的最大的剩下部分。时间复杂度 $O(2^{20}*log(2^{20}))$。
1 #include<cctype>
2 #include<cstdio>
3 #include<cstdlib>
4 #include<cstring>
5 #include<iostream>
6 #include<algorithm>
7 #define ll long long
8 using namespace std;
9 inline int read(){
10 int x=0; bool f=1; char c=getchar();
11 for(;!isdigit(c);c=getchar()) if(c=='-') f=0;
12 for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^'0');
13 if(f) return x;
14 return 0-x;
15 }
16
17 int n,x;
18 ll v[1<<21],l[1<<21],r[1<<21];
19 int main(){
20 freopen("cake.in","r",stdin);
21 freopen("cake.out","w",stdout);
22 n=read(),x=read();
23 int i,to=n>>1;
24 for(i=1;i<=to;++i) v[1<<(i-1)]=read();
25 int l_len=1<<to, r_len=1<<(n-to), tmp;
26 for(i=1;i^l_len;++i) tmp=i&(i-1), l[i]=v[i^(i&tmp)]+l[i&tmp];
27 for(i=1;i<=n-to;++i) v[1<<(i-1)]=read();
28 for(i=1;i^r_len;++i) tmp=i&(i-1), r[i]=v[i^(i&tmp)]+r[i&tmp];
29 sort(l+1,l+l_len);
30 sort(r+1,r+r_len);
31 int wz; ll ans=0;
32 for(i=0;i^l_len;++i){
33 if(l[i]>x) continue;
34 wz=upper_bound(r+1,r+r_len,x-l[i])-r-1;
35 ans=max(ans,l[i]+r[wz]);
36 //printf("go:%d %d %d %d
",i,wz,l[i],r[wz]);
37 }
38 printf("%lld",x-ans);
39 return 0;
40 }
View Code
1 #include<bits/stdc++.h>
2 #define rep(i,x,y) for(register int i=(x);i<=(y);i++)
3 #define dwn(i,x,y) for(register int i=(x);i>=(y);i--)
4 #define maxn 51
5 #define maxk 10010
6 #define maxs ((1<<10)+5)
7 #define LL long long
8 using namespace std;
9 int read()
10 {
11 int x=0,f=1;char ch=getchar();
12 while(!isdigit(ch)&&ch!='-')ch=getchar();
13 if(ch=='-')f=-1,ch=getchar();
14 while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
15 return x*f;
16 }
17 void write(int x)
18 {
19 int f=0;char ch[20];
20 if(!x){putchar('0'),putchar('
');return;}
21 if(x<0)x=-x,putchar('-');
22 while(x)ch[++f]=x%10+'0',x/=10;
23 while(f)putchar(ch[f--]);
24 putchar('
');
25 }
26 typedef struct quest{int l,r,u,d,k;}que;
27 que q[maxn];
28 const int mod=1e9+7;
29 int f[maxs][maxs],sum;//,sum;
30 int full,fulls,r,c,n,m,g[maxn][maxn],siz[maxs],tox[maxk],toy[maxk],num[maxn][maxn],bacx[maxn],bacy[maxn],extx[maxn],exty[maxn],cntx,cnty,nowx=2,nowy=2;
31 int mul(int x,int y)
32 {
33 int ans=1;
34 while(y)
35 {
36 if(y&1)ans=(int)(((LL)ans*(LL)x)%((LL)mod));
37 x=(int)(((LL)x*(LL)x)%((LL)mod)),y>>=1;
38 }
39 return ans;
40 }
41 void print(int x)
42 {
43 rep(i,1,n)cout<<((x&(1<<(i-1)))?1:0);return;
44 }
45 int main()
46 {
47 freopen("grid.in","r",stdin);
48 freopen("grid.out","w",stdout);
49 memset(bacx,-1,sizeof(bacx));
50 memset(bacy,-1,sizeof(bacy));
51 r=read(),c=read(),m=read(),n=read();
52 bacx[1]=bacy[1]=1;tox[1]=toy[1]=1;
53 fulls=(1<<n)-1;
54 rep(i,1,n)
55 q[i].l=read(),q[i].u=read(),q[i].r=read(),q[i].d=read(),q[i].k=read(),
56 extx[++cntx]=q[i].l,extx[++cntx]=q[i].r,exty[++cnty]=q[i].u,exty[++cnty]=q[i].d;
57 sort(extx+1,extx+cntx+1),sort(exty+1,exty+cnty+1);
58 extx[0]=1;
59 rep(i,1,cntx)
60 {
61 if(extx[i]!=extx[i-1]){if(extx[i]-extx[i-1]>1)nowx++;bacx[nowx]=extx[i],tox[extx[i]]=nowx,nowx++;}
62 }
63 if(bacx[nowx-1]!=r){if(r-extx[cntx]>1)nowx++;bacx[nowx]=r,tox[r]=nowx;}
64 else nowx--;
65 exty[0]=1;
66 rep(i,1,cnty)
67 {
68 // cout<<exty[i]<<endl;
69 if(exty[i]!=exty[i-1]){if(exty[i]-exty[i-1]>1)nowy++;bacy[nowy]=exty[i],toy[exty[i]]=nowy,nowy++;}
70 }
71 if(bacy[nowy-1]!=c){if(c-exty[cnty]>1)nowy++;bacy[nowy]=c,toy[c]=nowy;}
72 else nowy--;
73 rep(i,1,nowx)
74 rep(j,1,nowy)
75 {
76 int numx,numy;
77 if(bacx[i]!=-1)numx=1;
78 else numx=bacx[i+1]-bacx[i-1]-1;
79 if(bacy[j]!=-1)numy=1;
80 else numy=bacy[j+1]-bacy[j-1]-1;
81 num[i][j]=numx*numy;
82 }
83 rep(i,1,n)
84 {
85 rep(j,tox[q[i].l],tox[q[i].r])
86 rep(k,toy[q[i].u],toy[q[i].d])
87 g[j][k]+=(1<<(i-1));
88 }
89 rep(i,1,nowx)
90 {
91 rep(j,1,nowy)
92 {
93 siz[g[i][j]]+=num[i][j];
94 full=max(full,g[i][j]);
95 }
96 }
97 f[0][0]=mul(m,siz[0]);
98 rep(i,0,full-1)
99 {
100 rep(j,0,fulls)
101 {
102 int limit=m,num=0;
103 rep(k,1,n)if((i+1)&(1<<(k-1)))limit=min(limit,q[k].k);
104 rep(k,1,n)if(((i+1)&(1<<(k-1)))&&q[k].k==limit)num|=(1<<(k-1));
105 f[i+1][j]=(int)(((LL)f[i+1][j]+(LL)f[i][j]*(LL)mul(limit-1,siz[i+1]))%((LL)mod));
106 f[i+1][j|num]=(int)(((LL)f[i+1][j|num]+(LL)f[i][j]*(((LL)mul(limit,siz[i+1])-(LL)mul(limit-1,siz[i+1])+(LL)mod)%((LL)mod)))%((LL)mod));
107 }
108 }
109 write(f[full][fulls]);
110 return 0;
111 }
112 /*
113 2 3 2 1
114 1 2 2 3 2
115 */
116 /*
117 3 6 3 2
118 1 2 2 3 2
119 1 3 3 6 1
120 */
121 /*
122 7 11 5 4
123 2 2 4 4 3
124 3 3 5 5 2
125 4 4 5 9 3
126 1 7 6 8 1
127 */