考试策略
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 了……
吾不言，吾不言……
0 条评论