考试策略

T1不可做,T2不可做,T3不可做……

今天考试看到题目第一句话就是:“凸包是什么”,第二句话是:“Day3是什么”,后来经WY大佬指示才发现是“NOIp”模拟,注意,只有“p”是小写啊!

由于T1的暴力容易写一些,所以先写了T1,然后写了T2的暴力。

结果今天只考了60分就Rank1了……T3所有人都爆0……

T1

期望得分: 40 实际得分:40

题目描述

在不存在 (所以我们今天考了场假试?) 的 noip day3 里小w 见到了一堆堆的谜题。
比如这题为什么会叫共轭?
他并不知道答案。
有 n 堆谜题,每堆有 a i 个,小 w 每次从剩下的谜题中选择一个,然后把所在的那一堆谜题全部丢掉。
小 w 期望多少次后丢掉第一堆?

数据范围

对于20%的数据,$n \leq 10$
对于40%的数据,$n \leq 1000$
对于另外20%的数据,$a_i=1$
对于100%的数据$n \leq 10^5 ,1 \leq a_i \leq 10^9$

题目分析

首先对于$n \leq 10$,我们可以暴力搜出每一种丢掉方式和发生这种方式的概率,以此算期望。

对于$a_i=1$的情况,设f(x)表示还剩下x堆的时候丢掉第一堆的期望,显然$f(x)=\frac{1}{x}+\frac{x-1}{x}(f(x-1)+1)$

于是我们有了40分。

你会发现40分做法很优美 个鬼啊 ,然而100分算法也很容易……我们可以单独算除了1以外某一堆对期望的贡献,会发现任何一堆,如果它在第一堆被丢掉之前被丢掉,带来的丢掉次数是1,而它在第一堆被丢掉之前被丢掉的概率是$\frac{a_i}{a_i+a_1}$,所以……代码见下……

所以到底是为什么这道题没有人做出来啊喂,看来我们的期望都白学了……

代码

 #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+10;
double ans=1;int n,a[N];
int main()
{
    freopen("conjugate.in","r",stdin);
    freopen("conjugate.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    for(int i=2;i<=n;++i) ans+=a[i]*1.0/(a[1]+a[i]);
    printf("%.12lf\n",ans);
    return 0;
}

T2

期望得分:40 实际得分:20(然而是题目的锅)

题目描述

小w 有一个由 0、1、2 构成的序列。
他可以每次选一个序列中的数,把它移动到序列中任意一个位置。
要用最少多少次可以让 0 和 1 不相邻?
为了考验你的真实水平,小 w 决定使用多组数据。

数据范围

对于20%的数据,每个$n \leq 10$
对于40%的数据,每个$n \leq 100$
对于另外20%的数据,保证只有一个2
对于100%的数据,保证$\sum n \leq 5000$

暴力分析

对于20%保证只有一个2的数据,组成的序列里只要既有1又有0(当然要判断0或1只有一个的情况),那么一定是2放在某个位置,一边全是0一边全是1。所以枚举2放的位置,把某一边的1全部挪到另一边,把另一边的0全部挪过了即可。

对于20%的$n \leq 10$,我们可以使用迭代加深搜索。由于每一次移动最多只有三个数字的“前面数字”会发生改变(挪动的数,挪动的数后面的数,挪动的数到新位置后其后面的数),所以我们令h()表示“前面数字”不符合要求的情况,然后设maxd为当前最大层数,d为当前层数,当$h()+3d>maxd$时可以剪枝。不过这样还是扩展了很多无用状态,由于可能会有500组数据,这样还是拿不到20分。于是我们需要用哈希来判重。

于是我花了两个小时打好了一个价值20分的迭代A星加哈希剪枝优化的深搜,结果这个迭代A星加哈希剪枝优化的深搜没有给我带来20分,因为出题人并没有说无解输出-1但是有无解的情况并且要输出-1,于是我白打了这个迭代A星加哈希剪枝优化的深搜。

暴力代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int read() {
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q;
}
int n,T,ans,t1,t0,j2,j0,j1,kl;
int a[5005],vis[200000][6];
int h() {//(伪)估价函数
    int re=0;
    for(int i=2;i<=n;++i)
        if(a[i]==1&&a[i-1]==0) ++re;
        else if(a[i]==0&&a[i-1]==1) ++re;
    return re;
}
int has() {//哈希
    int t=1,i,re=0;
    for(i=1;i<=n;++i)
        re+=t*a[i],t*=3;
    return re;
}
int dfs(int d,int maxd) {//深搜的正文
    int i,j,k,t,kl=h(),b[12],kk;
    if(kl+3*d>maxd*3) return 0;
    if(!kl)return 1;
    kk=has();if(vis[kk][d]){return 0;}vis[kk][d]=1;
    for(i=1;i<=n;++i) b[i]=a[i];
    for(i=1;i<=n;++i) {
        t=0;
        for(j=1;j<=n;++j)if(j!=i) a[++t]=b[j];
        a[n]=b[i];
        for(j=n;j>=1;--j) {
            if(dfs(d+1,maxd)) {
                for(k=1;k<=n;++k) a[k]=b[k];
                return 1;
            }
            if(j==1) break;
            swap(a[j],a[j-1]);
        }
    }
    for(i=1;i<=n;++i) a[i]=b[i];
    return 0;
}
int main()
{
    freopen("conjunct.in","r",stdin);
    freopen("conjunct.out","w",stdout);
    int i,bj;T=read();
    while(T--) {
        n=read();
        for(i=1;i<=n;++i) a[i]=read();
        if(n<=10) {
            bj=0;
            for(i=0;i<=n/2;++i) {
                memset(vis,0,sizeof(vis));
                if(dfs(0,i)){printf("%d\n",i);bj=1;break;}
            }
            if(!bj)puts("-1");
        }
        else {//对于只有一个2的情况的暴力
            t1=t0=j0=j1=0;ans=1e7;
            for(i=1;i<=n;++i)
                if(a[i]==1) ++t1;
                else if(a[i]==0) ++t0;
                else j2=i;
            if(!t1||!t0){ puts("0");continue;}
            for(i=0;i<=n;++i) {
                if(j2==i) continue;
                if(a[i]==1&&i!=0) ++j1;
                else if(a[i]==0&&i!=0)++j0;
                kl=min(j1+t0-j0,j0+t1-j1);
                if(j2!=i+1) ++kl;
                ans=min(ans,kl);
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}

正解分析

好的那么问题来了:正解是什么?

正解是dp(我花了大约两个半小时来看懂正解QAQ)。

首先我们可以发现,我们移动数的过程可以看作是不动原序列与最终序列的lcs,然后把其他数都动一次。因此我们只要在原序列里选出一段最长的符合要求的子序列(注意此处的“子序列”并不一定是在原序列中截取的连续的一段)即可。

什么叫符合要求?显然最珍贵的资源是2,选出一个子序列后,对于2的需求量就求出来啦(子序列里的2的数量+子序列里相邻的0和1的数量),而对于2的需求量不超过原序列里2的数量的子序列就是符合要求的……所以我们需要记录子序列上一个选择的数是什么……

等等!还没完!假如对于一个既有0又有1并且只有一个2的序列,我选出了一个这样的序列:1 1 2 1 1 剩下的0往什么地方放啊???所以这样的子序列显然也是不符合要求的。因此我们还需要记录两个东西:d0和d1,分别表示当前选出的子序列中有没有可以放一段0的地方,有没有可以放一段1的地方。

好的,得到状态后我们继续分析实现代码。

1.如果整个序列没有1或者没有0,可以直接输出“1”

2.如果整个序列没有2,可以直接输出无解的“-1”

3.接下来,我们需要两个状态:f(i,d0,d1)和g(x,i,d0,d1),其中f是一个临时数组,g是永久的。g的含义:子序列的末尾是x,子序列已经带来了i的对2的需求量,子序列是否留给0和1位置(d0和d1),这样一个状态下选出的最长子序列长度。而f的含义中i,d0,d1同g中的i,d0,d1,不过f是临时的(具体含义等下讲)

4.现在我们看一看状态转移方程:

for(i=0;i<=2;++i) for(j=0;j<=n;++j)
    g[i][j][0][0]=g[i][j][1][0]=g[i][j][0][1]=g[i][j][1][1]=-inf;
g[2][0][0][0]=0;//可以假装子序列最开头有一个2(因为开头放什么都没问题)
//一些变量的意思:tot是原序列中2的数量,ans是最长序列的长度(要去求)
for(i=1;i<=n;++i) {
    for(j=0;j<=tot;++j) f[j][0][0]=f[j][0][1]=f[j][1][0]=f[j][1][1]=-inf;
    //f:一个临时的dp数组,表示的含义见上,并且f储存的那个子序列末尾一定是a[i]
    for(las=0;las<=2;++las)
        for(j=0;j<=tot&&j<=i-1;++j)
        for(d0=0;d0<=1;++d0) for(d1=0;d1<=1;++d1) {
        D0=d0||(a[i]==0),D1=d1||(a[i]==1);
        if(las==2&&a[i]==2) D0=D1=1;
          //如果子序列中出现了两个连续的2,那么下划线处可以放一个给0的区间和一个给1的区间:_2_2
        if((a[i]^las)==1||(a[i]==2)) //需要一个2
            f[j+1][D0][D1]=max(f[j+1][D0][D1],g[las][j][d0][d1]+1);
        else f[j][D0][D1]=max(f[j][D0][D1],g[las][j][d0][d1]+1);//不一定需要一个新的2
    }
    for(j=0;j<=i&&j<=tot;++j)//更新g数组
        for(d0=0;d0<=1;++d0) for(d1=0;d1<=1;++d1)
            g[a[i]][j][d0][d1]=max(g[a[i]][j][d0][d1],f[j][d0][d1]);
   //以下是答案统计部分
    for(j=0;j<=tot;++j) ans=max(ans,max(f[j][0][0],f[j][1][1]));
    for(j=0;j<=tot-1;++j) ans=max(ans,max(f[j][1][0],f[j][0][1]));
    if(a[i]==2) ans=max(ans,max(f[tot][0][1],f[tot][1][0]));
  //如果已经“用掉了”所有的2(所有的2被需求),并且给0或给1的区间有一个没有留出来,除非末尾是2(f表示的序列末尾是a[i]啊)的时候,可以在末尾新添一个区间放0或1,否则这个子序列就是不合要求的。
}

正解代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int read() {
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q;
}
const int N=5050,inf=1e6+5;
int T,n,t1,t0,tot,ans;
int a[N],g[3][N][2][2],f[N][2][2];
//g[x][i][d0][d1]:末尾是x,子序列需要i个2,有无放1和0的区间选出的最长子序列长度(不必须选择当前数)
//f[i][d0][d1]子序列需要i个2,有无放1和0的区间时选出的最长子序列长度(必须选择当前数)
void work() {
    int i,j,d0,d1,D0,D1,las;ans=0;
    for(i=0;i<=2;++i) for(j=0;j<=n;++j)
        g[i][j][0][0]=g[i][j][1][0]=g[i][j][0][1]=g[i][j][1][1]=-inf;
    g[2][0][0][0]=0;
    for(i=1;i<=n;++i) {
        for(j=0;j<=tot;++j) f[j][0][0]=f[j][0][1]=f[j][1][0]=f[j][1][1]=-inf;
        for(las=0;las<=2;++las)
            for(j=0;j<=tot&&j<=i-1;++j)
            for(d0=0;d0<=1;++d0) for(d1=0;d1<=1;++d1) {
            D0=d0||(a[i]==0),D1=d1||(a[i]==1);
            if(las==2&&a[i]==2) D0=D1=1;
            if((a[i]^las)==1||(a[i]==2)) 
                f[j+1][D0][D1]=max(f[j+1][D0][D1],g[las][j][d0][d1]+1);
            else f[j][D0][D1]=max(f[j][D0][D1],g[las][j][d0][d1]+1);
        }
        for(j=0;j<=i&&j<=tot;++j)
            for(d0=0;d0<=1;++d0) for(d1=0;d1<=1;++d1)
                g[a[i]][j][d0][d1]=max(g[a[i]][j][d0][d1],f[j][d0][d1]);
        for(j=0;j<=tot;++j) ans=max(ans,max(f[j][0][0],f[j][1][1]));
        for(j=0;j<=tot-1;++j) ans=max(ans,max(f[j][1][0],f[j][0][1]));
        if(a[i]==2) ans=max(ans,max(f[tot][0][1],f[tot][1][0]));
    }
    printf("%d\n",n-ans);
}
int main()
{
    freopen("conjunct.in","r",stdin);
    freopen("conjunct.out","w",stdout);
    T=read();
    while(T--) {
        n=read();t0=t1=tot=0;
        for(int i=1;i<=n;++i)
            a[i]=read(),t0+=(a[i]==0),t1+=(a[i]==1),tot+=(a[i]==2);
        if(!t0||!t1){puts("0");continue;}
        if(!tot){puts("-1");continue;}
        work();
    }
    return 0;
}

T3

期望得分: 0.4 实际得分:0

题目描述

听说 noip 不会考几何(那你还考?),所以当 Day3 出现了一道几何题的时候,小 w 的内心是崩溃的。
有 n 个三维空间里的点,每个点有 p i 的概率出现,求期望意义下凸包上有多少个点。
一个点不在凸包上,当且仅当存在一个四面体严格包含了这个点。

数据范围

对于20%的数据,保证$n \leq 15$
对于40%的数据,保证$n \leq 30$
对于另外20%的数据,保证$p_i=1$
对于100%的数据,保证$n \leq 50$,保证任意三点不共线,任意四点不共面

题目分析

我不会凸包……

更不会三维凸包……

我好弱啊……

另外所有人这题都爆0了……

吾不言,吾不言……

分类: 所有

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *