NOIp2018集训test-9-18

2023-11-06 06:50

文章标签 test 18 集训 noip2018

本文主要是介绍NOIp2018集训test-9-18，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

T1.Conjugate

只能选没选过的点，看成如果选了选过的堆的点就不管它继续选。如果第一次选到某一堆的点在第一次选到第一堆的点之前，这一堆对答案就会有1的贡献。那么a[i]有贡献的概率是a[i]和a[1]的相对顺序序列中，第一个是a[i]中的点的概率（转换后的游戏和原游戏等价），即ai/(a1+ai)，答案就是这个东西求和再+1。

 1 //Achen
 2 #include<bits/stdc++.h>
 3 #define Formylove return 0
 4 #define For(i,a,b) for(int i=(a);i<=(b);i++)
 5 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)
 6 const int N=100007;
 7 typedef long long LL;
 8 typedef double db;
 9 using namespace std;
10 int n,a[N];
11 db ans;
12 
13 template<typename T>void read(T &x)  {
14     char ch=getchar(); x=0; T f=1;
15     while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
16     if(ch=='-') f=-1,ch=getchar();
17     for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
18 }
19 
20 #define ANS
21 int main() {
22 #ifdef ANS
23     freopen("conjugate.in","r",stdin);
24     freopen("conjugate.out","w",stdout);
25 #endif
26     read(n);
27     For(i,1,n) read(a[i]); 
28     ans=1;
29     For(i,2,n) ans=ans+(db)a[i]/(1.0*(a[i]+a[1]));
30     printf("%lf\n",ans);
31     Formylove;
32 }

View Code

T2.Conjunct

我不是很懂题解说的dp lcs是什么意思，但是我自己yy了一个dp。

最后的序列肯定是一坨0和一坨1交替，相交的位置中间有一个2（0和1的坨里面可能也有2，就看成是0或者1就好了）

f[i][j][k]表示前i个位置的移动确定好了，最后一个坨是k（0/1）的坨，第i个位置后面放一个分割的2的答案，因为是0.1相间的，一定存在一种合法的方案是把前i个中最后一个部分的和这一部分不同的数移到下一个坨里和把下一个坨里一部分数移到这一坨里，所以转移的时候只需要放心大胆地把不合法的代价算出来，它一定是有地方可去的，而这个代价预处理0.1的前缀和就可以求出。这样复杂度是n^3的，发现f[i][j]k]仅由f[i'][j-1][k^1]转移来，对于每个j和k求前缀最小值即可n^2解决。

 1 //Achen
 2 #include<bits/stdc++.h>
 3 #define Formylove return 0
 4 #define For(i,a,b) for(int i=(a);i<=(b);i++)
 5 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)
 6 const int N=5007;
 7 const int inf=1e8;
 8 typedef long long LL;
 9 typedef double db;
10 using namespace std;
11 int T,n,tot,a[N],f[N][N][2],mi[2][N],ans,sum1[N],sum0[N],tot1,tot0;
12 
13 template<typename T>void read(T &x)  {
14     char ch=getchar(); x=0; T f=1;
15     while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
16     if(ch=='-') f=-1,ch=getchar();
17     for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
18 }
19 
20 void get_min(int &x,int y) {
21     if(y<x) x=y; return ;
22 }
23 
24 #define ANS
25 int main() {
26 #ifdef ANS
27     freopen("conjunct.in","r",stdin);
28     freopen("conjunct.out","w",stdout);
29 #endif
30     read(T);
31     while(T--) {
32         read(n); 
33         tot=tot0=tot1=0;
34         For(i,1,n) {
35             read(a[i]);
36             sum0[i]=sum0[i-1];
37             sum1[i]=sum1[i-1];
38             if(a[i]==1) tot1++,sum1[i]++;
39             else if(a[i]==0) tot0++,sum0[i]++;
40             else tot++;
41         }
42         if(!tot0||!tot1) {
43             puts("0"); 
44             continue; 
45         }
46         For(i,0,n) For(j,0,tot) f[i][j][0]=f[i][j][1]=inf;
47         For(i,0,tot) mi[0][i]=mi[1][i]=inf;
48         ans=inf;
49         mi[0][0]=mi[1][0]=0;
50         if(a[1]==2) get_min(ans,min(tot1,tot0));
51         For(i,1,n) Rep(j,min(tot,i),1) {
52             get_min(f[i][j][0],sum1[i]+(a[i+1]!=2)+mi[1][j-1]);
53             get_min(f[i][j][1],sum0[i]+(a[i+1]!=2)+mi[0][j-1]);
54             get_min(mi[0][j],f[i][j][0]-sum0[i]);
55             get_min(mi[1][j],f[i][j][1]-sum1[i]);    
56             get_min(ans,f[i][j][0]+sum0[n]-sum0[i]);
57             get_min(ans,f[i][j][1]+sum1[n]-sum1[i]);
58         }
59         if(ans==inf) ans=-1;
60         printf("%d\n",ans);
61     }
62     Formylove;
63 }