NOIp 2016 选讲

1. 初赛内容 在视频会体现

玩具谜题

#include<iostream>
using namespace std;
int n,m,num,ans;//num为一个指令的移动距离。 
string names[100010];//职业。 
bool drn,dr[100010];//drn为一个指令的方向，dr储存小人的朝向。 
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>dr[i]>>names[i];
    while(m--){
        cin>>drn>>num;
        ans+=num*(drn==dr[ans]?-1:1);//移动，相等减，相异加。原理很容易理解，
        ans+=(ans<0?n:(ans>=n?-n:0));//转圈。一般情况下恐怕是不能和上一行写在同一个ans+=里边的。 
    }
    cout<<names[ans]<<endl;
    return 0;
}

组合数问题

介绍组合数的部分详情请看ppt

#include<iostream>
#include<cstdio>

int t,k,n,m;
char C[3000][3000];
int sum[3000][3000];

int main(){
    scanf("%d%d",&t,&k);
    for (int i=0;i<=2000;i++) C[i][0]=1;
    for (int i=1;i<=2000;i++)
        for (int j=1;j<=i;j++)
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%k;
    for (int i=0;i<=2000;i++)
        for (int j=0;j<=2000;j++){
            sum[i][j]=((C[i][j]==0)&&(j<=i));
            if (i) sum[i][j]+=sum[i-1][j];
            if (j) sum[i][j]+=sum[i][j-1];
            if (i&&j) sum[i][j]-=sum[i-1][j-1];
        }
    for (int i=1;i<=t;i++){
        scanf("%d%d",&n,&m);
        printf("%d\n",sum[n][m]);
    }
}

1. 蚯蚓

   
   题目大意就不说了QWQ

首先65分裸优先队列，线段树，堆都可以。。。

100分：开三个队列，第一个存没被砍过的蚯蚓(要先sort)，第二个存被砍了长度p的蚯蚓，第三个存被砍了长度(1-p)的蚯蚓。每次都从三个队列的队头找一个最大的砍掉，然后分到第二个和第三个队列中。

怎么证明这样可以呢？其他博客有了详细的数学证明，但是我的思路很简单哇。。。假如某只蚯蚓x先被砍了，分成了两段，两段每秒都+q，等同于这只蚯蚓x每秒+2q，但是还没被砍的蚯蚓y每秒只+q，而x会比y先被砍肯定是原长度大于y，所以y砍掉之后的两条蚯蚓一定比所对应的x砍掉的两条蚯蚓要短，于是我们就能证明出三个队列都是单调的了。

然后就是坑爹的优化环节。。。可能是我比较蠢，处理+q这个操作我开了个数组表示某条蚯蚓被砍了几次，这样会被卡

优化：定义一个变量l，每次找出最长的蚯蚓长度ans+=l，砍完蚯蚓l+=q，然后砍成两段时两只蚯蚓入队要-=l，最后输出的时候所有蚯蚓长度要+=l。

于是优化掉了我的两个入队语句就过了。。。顺便一提队列用STL只有65分QAQ

代码如下：

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int inf=1<<31-1;
int n,m,q,u,v,t,l,tot,num,maxj,a[4][15000010],now[4],nowr[4],b[15000010];
double p;
bool cmp(int a,int b){return a>b;}
int main()
{
    scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);p=(double)u/v;
    for(int i=1;i<=n;i++)scanf("%d",&a[1][i]);
    sort(a[1]+1,a[1]+1+n,cmp);
    now[1]=now[2]=now[3]=1;nowr[1]=n;
    for(int i=1,ans=-inf;i<=m;i++,ans=-inf)
    {
        ++num;
        for(int j=1;j<=3;j++)
        if(now[j]<=nowr[j])
        if(ans<a[j][now[j]])ans=a[j][now[j]],maxj=j;
        ans+=l;l+=q;now[maxj]++;a[2][++nowr[2]]=(int)floor(ans*p)-l;a[3][++nowr[3]]=(ans-(int)floor(ans*p))-l;
           if(num==t)printf("%d ",ans),num=0;
    }
    printf("\n");
    num=0;
    for(int i=1,ans=-inf;i<=n+m;i++,ans=-inf)
    {
        ++num;
        for(int j=1;j<=3;j++)
        if(now[j]<=nowr[j])
        if(ans<a[j][now[j]])ans=a[j][now[j]],maxj=j;
        now[maxj]++;
        if(num==t)printf("%d ",ans+l),num=0;
    }
}