NOIP2016提高组复赛 解题报告

Day1

T1

按照题意模拟就行了，水。
代码：

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define N 100005

int n,m,d,num,now;
char s[N][20];
int len[N],dir[N],pre[N],nxt[N];

int main()
{
    freopen("toy.in","r",stdin);
    freopen("toy.out","w",stdout);
scanf("%d%d\n",&n,&m);
for (int i=1;i<=n;++i)
    {
        gets(s[i]);len[i]=strlen(s[i]);
        dir[i]=s[i][0]-'0';
for (int j=1;j<len[i]-1;++j) s[i][j]=s[i][j+1];
    }
/*
 for (int i=1;i<=n;++i)
 {
 for (int j=1;j<=len[i]-2;++j) putchar(s[i][j]);
 putchar('\n');
 }
 */
    now=1;
for (int i=1;i<=m;++i)
    {
scanf("%d%d",&d,&num);
if (!d)//left
        {
if (!dir[now])//in
            {
                now=((now-num-1)%n+n)%n+1;
            }
else//out
            {
                now=(now+num-1)%n+1;
            }
        }
else//right
        {
if (!dir[now])
            {
                now=(now+num-1)%n+1;
            }
else
            {
                now=((now-num-1)%n+n)%n+1;
            }
        }
    }
for (int i=1;i<=len[now]-2;++i)
putchar(s[now][i]);
putchar('\n');
}

T2

感觉这道题是今年最神的一道题，没想到放到day1T2来考。
考试的时候一个一个部分分打暴力，不过最后只搞出来了60pts。这题的暴力分很良心，不过每一个都不是很好打。。
正解是树上差分。题解的前半部分说得很明白：

也就是说，将每一个路径拆成4个，2条到根的和2条从根出发的。
假设一个观察员在 v ，其时间为 w 。
如果要统计有多少个从 u 到根的人可以被 v 观察到的话，那么首先， u 在 v 的子树里。其次，要保证 t+h(u)−h(v)=w ，即 t+h(u)=w+h(v) 。
如果要统计有多少个从根到 u 的人可以被 v 观察到的话，那么同样， u 在 v 的子树里，并且 t+h(v)−h(root)=w ，即 t=w−h(v)+h(root) 。
我们可以把等式前面的看做每一个人的权，把等式后面的看做是每一个观测员的权。
那么，设 ai 表示权为 i 的人的数量，然后在树上dfs一遍求出来每一个观测员子树中有多少个和它的权相等就可以了。
代码：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define N 1000005
#define base 300000
#define sz 19

int n,m,x,y,s,t,r,ct,ft;
struct hp{int pt,t,val;}tor[N*2],fromr[N*2];
int tot,point[N],nxt[N*2],v[N*2];
int father[N],a[N],w[N],dfs_clock,f[N][sz+5],h[N],in[N],ans[N];

void add(int x,int y)
{
    ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y;
}
void build(int x,int fa)
{
    father[x]=fa;h[x]=h[fa]+1;in[x]=++dfs_clock;
for (int i=1;i<sz;++i)
    {
if (h[x]-(1<<i)<1) break;
        f[x][i]=f[f[x][i-1]][i-1];
    }
for (int i=point[x];i;i=nxt[i])
if (v[i]!=fa)
        {
            f[v[i]][0]=x;
            build(v[i],x);
        }
}
int lca(int x,int y)
{
if (h[x]<h[y]) swap(x,y);
int k=h[x]-h[y];
for (int i=0;i<sz;++i)
if (k&(1<<i)) x=f[x][i];
if (x==y) return x;
for (int i=sz-1;i>=0;--i)
if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
int cmp(hp a,hp b)
{
return in[a.pt]<in[b.pt];
}
void dfs_to(int x,int fa)
{
int val=w[x]+h[x],minus=a[val];
while (ct<=2*m&&tor[ct].pt==x) a[tor[ct].t+h[tor[ct].pt]]+=tor[ct].val,ct++;
for (int i=point[x];i;i=nxt[i])
if (v[i]!=fa)
            dfs_to(v[i],x);
    ans[x]+=a[val]-minus;
}
void dfs_from(int x,int fa)
{
int val=w[x]-h[x]+1,minus=a[val+base];
while (ft<=2*m&&fromr[ft].pt==x)
        a[fromr[ft].t+base]+=fromr[ft].val,ft++;
for (int i=point[x];i;i=nxt[i])
if (v[i]!=fa)
            dfs_from(v[i],x);
    ans[x]+=a[val+base]-minus;
}
int main()
{
    freopen("running.in","r",stdin);
    freopen("running.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<n;++i)
    {
scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    build(1,0);
for (int i=1;i<=n;++i) scanf("%d",&w[i]);
for (int i=1;i<=m;++i)
    {
scanf("%d%d",&s,&t);
        r=lca(s,t);
        tor[++ct].pt=s,tor[ct].t=0,tor[ct].val=1;
if(r!=1)tor[++ct].pt=father[r],tor[ct].t=h[s]-h[r]+1,tor[ct].val=-1;
        fromr[++ft].pt=t,fromr[ft].t=h[s]-h[r]-(h[r]-1),fromr[ft].val=1;
        fromr[++ft].pt=r,fromr[ft].t=h[s]-h[r]-(h[r]-1),fromr[ft].val=-1;
    }
    sort(tor+1,tor+ct+1,cmp);ct=1;
    sort(fromr+1,fromr+ft+1,cmp);ft=1;
    dfs_to(1,0);
memset(a,0,sizeof(a));dfs_from(1,0);
for (int i=1;i<=n;++i)
    {
if (i!=1) putchar(' ');
printf("%d",ans[i]);
    }
}

T3

实际上这道题就是一道水水的dp。（Ta只用了5min就a掉了= =）
可是当时考试的时候没时间了，暴力都打得手忙脚乱。
首先用floyed求出来两两最短路。
f(i,j,0/1) 表示前 i 个课程，一共选了 j 个申请，第 i 个0不申请1申请的最小期望。
然后直接dp就可以了。。。
代码：

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define N 2005

int n,m,v,e,x,y;
int c[N],d[N];
double z,inf,kk[N],sdis[N],dis[N][N],f[N][N][2],ans;

void floyed()
{
for (int k=1;k<=v;++k)
for (int i=1;i<=v;++i)
for (int j=1;j<=v;++j)
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
int main()
{
    freopen("classroom.in","r",stdin);
    freopen("classroom.out","w",stdout);
    scanf("%d%d%d%d",&n,&m,&v,&e);
for (int i=1;i<=n;++i) scanf("%d",&c[i]);
for (int i=1;i<=n;++i) scanf("%d",&d[i]);
for (int i=1;i<=n;++i) scanf("%lf",&kk[i]);
    memset(dis,127,sizeof(dis));inf=dis[0][0];
for (int i=1;i<=v;++i) dis[i][i]=0.0;
for (int i=1;i<=e;++i)
    {
        scanf("%d%d%lf",&x,&y,&z);
        dis[x][y]=dis[y][x]=min(dis[x][y],z);
    }
    floyed();memset(f,127,sizeof(f));
/*
 for (int i=1;i<=v;++i)
 for (int j=i;j<=v;++j)
 printf("%d %d %.2lf\n",i,j,dis[i][j]);
 puts("");
 */
for (int i=2;i<=n;++i)
        ans+=dis[c[i-1]][c[i]];
    f[1][0][0]=f[1][1][1]=0.0;
for (int i=1;i<n;++i)
for (int j=0;j<=min(i,m);++j)
        {
if (f[i][j][0]!=inf)
            {
                f[i+1][j][0]=min(f[i+1][j][0],f[i][j][0]+dis[c[i]][c[i+1]]);
if (j<m) f[i+1][j+1][1]=min(f[i+1][j+1][1],f[i][j][0]+dis[c[i]][c[i+1]]*(1-kk[i+1])+dis[c[i]][d[i+1]]*kk[i+1]);
            }
if (f[i][j][1]!=inf)
            {
                f[i+1][j][0]=min(f[i+1][j][0],f[i][j][1]+dis[c[i]][c[i+1]]*(1-kk[i])+dis[d[i]][c[i+1]]*kk[i]);
if (j<m) f[i+1][j+1][1]=min(f[i+1][j+1][1],f[i][j][1]+(1-kk[i])*(1-kk[i+1])*dis[c[i]][c[i+1]]+(1-kk[i])*kk[i+1]*dis[c[i]][d[i+1]]+kk[i]*(1-kk[i+1])*dis[d[i]][c[i+1]]+kk[i]*kk[i+1]*dis[d[i]][d[i+1]]);
            }
        }
for (int i=0;i<=m;++i) ans=min(ans,min(f[n][i][0],f[n][i][1]));
printf("%0.2lf\n",ans);
}

Day2

T1

实际上就是统计 Cji%k==0 的数量，二维前缀和搞一下就行了。
考试的时候搞了一个非常傻逼的方法，就是将每一个 Cji 和 k 分解质因数，然后如果相减每一个质因子数都>=0就说明是可以整除的。
这样的话预处理用一个转移，就是 Cji 推到 Cj+1i ，也就是说 i！(i−j)！j！ 推到 i！(i−j−1)！(j+1)！ 只需要加上 i 的质因子再减去j的质因子就可以了。
由于 k<=21 ，所以只需要考虑前8个质数就可以了，时间复杂度为 O(n2∗8) 。
代码：

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define LL long long

int t,n,m,k,ANS;
int prime[9]={0,2,3,5,7,11,13,17,19};
int p[2005][20],s[2005][20],a[20],b[20],c[20],d[20],ans[2005][2005],Ans[2005][2005];

void calc(int x)
{
 int now=x;if (now==1) return;
 for (int i=1;i<=8;++i)
 if (now%prime[i]==0)
 {
 while (now%prime[i]==0)
 p[x][i]++,now/=prime[i];
 if (now==1) break;
 }
}
void sum(int x)
{
 for (int i=1;i<=8;++i)
 s[x][i]=s[x-1][i]+p[x][i];
}
int main()
{
 freopen("problem.in","r",stdin);
 freopen("problem.out","w",stdout);
 scanf("%d%d",&t,&k);
 for (int i=1;i<=2000;++i)
 calc(i);
 for (int i=1;i<=2000;++i) sum(i);
 for (n=0;n<=2000;++n)
 {
 bool flag=true;
 for (int i=1;i<=8;++i) a[i]=s[n][i],b[i]=s[n][i],c[i]=0,d[i]=a[i]-b[i]-c[i]-p[k][i];
 for (int i=1;i<=8;++i)
 {
 if (d[i]<0) {flag=false;break;}
 }
 if (flag) ans[n][0]++;
 for (m=1;m<=n;++m)
 {
 bool flag=true;
 for (int i=1;i<=8;++i) b[i]-=p[n-m+1][i],c[i]+=p[m][i],d[i]=a[i]-b[i]-c[i]-p[k][i];
 for (int i=1;i<=8;++i)
 {
 if (d[i]<0) {flag=false;break;}
 }
 if (flag) ans[n][m]++;
 }
 }
 for (int i=0;i<=2000;++i) Ans[i][0]=ans[i][0],Ans[0][i]=ans[0][i];
 for (int i=1;i<=2000;++i)
 for (int j=1;j<=2000;++j) Ans[i][j]=Ans[i-1][j]+Ans[i][j-1]-Ans[i-1][j-1]+ans[i][j];
 while (t--)
 {
 scanf("%d%d",&n,&m);
 printf("%d\n",Ans[n][m]);
 }
 return 0;
}

T2

搞三个数列。读进来初始值了之后排序，然后从大到小放到第一个队列里。每一次取3个队列中队首最大的那个值，然后计算出来 ⌊px⌋ 和 x−⌊px⌋ 之后分别将这两个数放到第2个和第3个队列里。
可以发现这样的话这三个队列都是分别单调的。
由于每一次要将其余的都+q，那么就将新得到的两个值-q之后再加入队列就可以了。
看起来非常科学非常简单的方法，但是考试的时候为什么想不到呢？
代码：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<cmath>
using namespace std;
#define inf 2100000000
#define N 100005

int n,m,t,x,qaq,add,a[N];
double u,v,p;
int q[4][N*100],l[4],r[4];

int cmp(int a,int b)
{
return a>b;
}
int Max()
{
int a=-inf,b=-inf,c=-inf,ans=1;
if (l[1]<r[1]) a=q[1][l[1]];
if (l[2]<r[2]) b=q[2][l[2]];
if (l[3]<r[3]) c=q[3][l[3]];
if (a<b) a=b,ans=2;
if (a<c) a=c,ans=3;
return ans;
}
int main()
{
    freopen("earthworm.in","r",stdin);
    freopen("earthworm.out","w",stdout);
    scanf("%d%d%d%lf%lf%d",&n,&m,&qaq,&u,&v,&t);p=u/v;
for (int i=1;i<=n;++i) scanf("%d",&a[i]);
sort(a+1,a+n+1,cmp);
for (int i=1;i<=n;++i) q[1][r[1]++]=a[i];
for (int i=1;i<=m;++i)
    {
int k=Max();
int now=q[k][l[k]++]+add;
if (i%t==0)
        {
if (i>t) putchar(' ');
printf("%d",now);
        }
int nxt1=floor(p*(double)now),nxt2=now-floor(p*(double)now);
        add+=qaq;
q[2][r[2]++]=nxt1-add,q[3][r[3]++]=nxt2-add;
    }
    putchar('\n');
for (int i=1;i<=n+m;++i)
    {
int k=Max();
int now=q[k][l[k]++]+add;
if (i%t==0)
        {
if (i>t) putchar(' ');
printf("%d",now);
        }
    }
}

T3

这道题实际上又是一道水水的dp。
预处理出来任意两点组成的抛物线，以及这条抛物线能打掉的点的状态。
设 f(i) 表示打掉的点状态为 i 的时候最少用的小鸟数。
因为小鸟的顺序是无所谓的，所以每次只需要枚举没有被打掉的第一个点和其余没有被打掉的点的抛物线就可以了。直接转移。。。
当时看到这道题的时候大脑竟然一片空白，一点办法也没有。真是不知道当时是怎么了。。。
代码：

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define N 18

const double eps=1e-9;
int T,n,m;
double a,b,x[N+1],y[N+1];
int birds[N+1][N+1],f[1<<N];

void clear()
{
    n=m=0;
    a=b=0.0;
memset(x,0,sizeof(x));memset(y,0,sizeof(y));
memset(birds,0,sizeof(birds));memset(f,0,sizeof(f));
}
int dcmp(double x)
{
if (x<=eps&&x>-eps) return 0;
if (x>eps) return 1;
return -1;
}
void calc(double &a,double &b,int id,int jd)
{
    a=b=0;
double A=x[id],B=y[id],C=x[jd],D=y[jd];
if (dcmp(A-C)==0) return;
    a=(B*C-A*D)/(A*A*C-A*C*C);
    b=(B*C*C-D*A*A)/(A*C*C-A*A*C);
}
bool on(int id,double a,double b)
{
double A=x[id],B=y[id];
if (dcmp(A*A*a+A*b-B)==0) return true;
else return false;
}
void init()
{
for (int i=1;i<=n;++i)
for (int j=i+1;j<=n;++j)
        {
            calc(a,b,i,j);
if (a>=0) continue;
for (int k=1;k<=n;++k)
if (on(k,a,b)) birds[i][j]|=1<<(k-1);
        }
}
int main()
{
    freopen("angrybirds.in","r",stdin);
    freopen("angrybirds.out","w",stdout);
scanf("%d",&T);
while (T--)
    {
        clear();
scanf("%d%d",&n,&m);
for (int i=1;i<=n;++i) scanf("%lf%lf",&x[i],&y[i]);
        init();
memset(f,127,sizeof(f));
        f[0]=0;
for (int i=0;i<1<<n;++i)
        {
for (int j=1;j<=n;++j)
if ((i&(1<<(j-1)))==0)
                {
for (int k=j+1;k<=n;++k)
if ((i&(1<<(k-1)))==0)
                            f[i|birds[j][k]]=min(f[i|birds[j][k]],f[i]+1);
                    f[i|(1<<(j-1))]=min(f[i|(1<<(j-1))],f[i]+1);
break;
                }
        }
printf("%d\n",f[(1<<n)-1]);
    }
}

今年的题目有这样的特点：题面比较吓人，难度乱序排列。我在对题目的把握和时间掌握上都出了问题，考的非常渣。。。
这提醒我：①一定要仔细读题，不要被题目所迷惑。②合理分配时间，不要每一道题都追求完美。③考试的时候要冷静，不要胡思乱想。④认真练码力吧。