Noip2011题解报告

NOIP2011解题报告

标签（空格分隔）： 考试
题目总结：
Day1-T1 模拟
Day1-T2 记录前驱+观察性质
Day1-T3 搜索+剪枝
Day2-T1 组合数学+快速幂
Day2-T2 二分+前缀和优化
Day2-T3 贪心

备注：观察性质是一种思考方式，不是做题方法和技巧！是态度！

---

Day-1

T1:铺地毯

数据范围:
对于30% 的数据，有 n ≤2 ；
对于50% 的数据，0 ≤a, b, g, k≤100；
对于100%的数据，有 0 ≤n ≤10,000 ，0≤a, b, g, k ≤100,000。

部分分

除了O(n)的算法我想不到任何方法了,自古T1模拟题(Noip2017被打脸)

一个值得注意的优化

从上面的地毯往下面的地毯扫(也就是从后往前扫)，扫到的第一个则是满足条件的最上面的地毯，break即可

代码

for(int i=n;i>=1;i--)
{
    if(pd(i)) {printf("%d\n",i);return 0;}
}

T2:选择客栈

数据范围:
对于30% 的数据，有 n ≤100；
对于50% 的数据，有 n ≤1,000；
对于100%的数据，有 2 ≤n ≤200,000，0< k ≤50，0≤p ≤100 ，0 ≤最低消费≤100。

部分分

30%:O(n^3)枚举左端点，右端点，再是O(n)的check
50%:O(n^2*logn)或O(n^2)，就是优化掉O(n)的check，提前预处理好区间最大最小值(线段树，st表都可以)
100%:O(n*k)，注意到若两个相同颜色的客栈之间存在一个满足题意的咖啡馆，则之后所有与这客栈颜色相同的都可计入答案。所以不难想到用一个桶来统计每种颜色的次数和每种颜色的合法数即可

值得注意的是

要先更新合法桶再更新颜色桶
其实这个题目数据不强，O(n^2)可以过，只需注意到一个优良性质”若两个相同颜色的客栈之间存在一个满足题意的咖啡馆，则之后所有与这客栈颜色相同的都可计入答案”，所以考虑优化，记录所有的颜色相同的位置及下一个同色出现的位置，然后如果找到一个满足题意的咖啡馆，则直接加上后面客栈的个数然后break

代码

for(int i=1;i<=n;i++)
{
    scanf("%d%d",&se,&mon);
    for(int j=0;j<k;j++)
    {
        if(mon<=p&&color[j])
        {
            tongji[j]=color[j];
        }
    }
    ans+=tongji[se];
    color[se]++;
    if(mon<=p)tongji[se]++;
}

来自某位大佬的题解报告

因为只有相同颜色才会产生贡献
记录一下上一个相同颜色的位置，以及当前是否有满足条件的咖啡店
用前缀和处理即可

for(int i=1;i<=N;++i)
{
    int c=read(),v=read();
    if(v<=P)lt=i;
    if(pos[c]<=lt)last[c]=sum[c];
    ans+=last[c];sum[c]++;pos[c]=i;
}

O(n2∗k)$O(n^2\ast k)$也能AC$AC$

for(rg int i=1;i<=K;i++)
{
    b[0]=0;
    for(rg int j=head[i];j;j=a[j].next)
    {
        rg int v=a[j].to;
        b[++b[0]]=v;
    }
    for(rg int j=1;j<=b[0];j++)
    {
        for(rg int z=j+1;z<=b[0];z++)
        {
            rg int u=b[z],v=b[j],k=log[v-u+1];
            if(min(f[k][u],f[k][v-(1<<k)+1])<=P)
            {ans+=b[0]-z+1;break;}
        }
    }
}    

T3:Mayan游戏

数据范围
对于30% 的数据，初始棋盘上的方块都在棋盘的最下面一行；
对于100%的数据，0 < n≤5 。

部分分

对于30%:顶多只有5颗棋子，暴力模拟就好了，我还有什么话可说
对于100%:
先讲剪枝吧
总而言之，四条剪枝原则：
（1）交换两个颜色相同的块没有意义
（2）一个块的左边是非空块时不需要考虑左移,因为会和之前的块右移重复，即只有当左块为空时才左移
（3）根据题目优先度的排序，可以知道，右移优先于左移，所以在dfs时先考虑右移
（4）如果有一种颜色当前的块数目x满足1<=x<=2，则此情况不合法
至于消的话，则可以做另外一个棋盘来进行标记，先暂时不消(以防消少了的情况)，再所有能消的棋子标记完后再一起消。

温馨提示

此题细节巨多，易打挂，请耐心调试

Day-2

T1:计算系数

数据范围
对于30% 的数据，有 0 ≤k ≤10 ；
对于50% 的数据，有 a = 1，b = 1；
对于100%的数据，有 0 ≤k ≤1,000，0≤n, m ≤k ，且n + m = k ，0 ≤a ，b ≤1,000,000。

部分分

50%:不会，其实a=1,b=1就是裸的杨辉三角了
100%:由a=1,b=1可以发现，唯一区别就是再杨辉三角的系数上再乘以a^n*b^m

值得注意的是

组合数是要求逆元的！！！
组合数是要求逆元的！！！
组合数是要求逆元的！！！
（重要的事情说三遍）
不求逆元会炸成30分！

T2:聪明的质监员

数据范围
对于10% 的数据，有 1 ≤n ，m≤10；
对于30% 的数据，有 1 ≤n ，m≤500 ；
对于50% 的数据，有 1 ≤n ，m≤5,000；
对于70% 的数据，有 1 ≤n ，m≤10,000 ；
对于100%的数据，有 1 ≤n ，m≤200,000，0 < wi, vi≤10^6，0 < S≤10^12，1 ≤Li ≤Ri ≤n 。

部分分

50%:不用前缀和优化的加一些卡常就大概有60分吧
至于其余的部分分我不会辣
100%:二分+前缀和优化，对于每一次二分出来的标准值W计算一遍前缀和，如果当前Y > S，则说明W分小了,l=mid+1，若Y < S,则说明W分大了,r=mid-1,若Y = S，则刚好

值得注意的是

开long long，然后更坑的是输入值S是long long，读入优化别打成int了！

T3:观光公交

数据范围
对于10% 的数据，k=0 ；
对于20% 的数据，k=1 ；
对于40% 的数据，2 ≤ n ≤ 50，1 ≤ m ≤ 1,000，0 ≤ k ≤ 20，0 ≤ Di ≤ 10，0 ≤ T i ≤ 500；
对于60% 的数据，1 ≤ n ≤ 100，1 ≤ m ≤ 1,000，0 ≤ k ≤ 100 ，0 ≤ Di ≤ 100，0 ≤ T i ≤ 10,000 ；
对于100%的数据，1 ≤ n ≤ 1,000，1 ≤ m ≤ 10,000 ，0 ≤ k ≤ 100,000，0 ≤ Di ≤ 100 ，0 ≤ T i ≤ 100,000。

部分分

不会部分分，所以直接来正解(部分分应该是给细节或者贪心打挂的人的分吧)
正解:
边加速边计算答案很麻烦所以我们把不用加速器的答案算出来再减去加速的时间。关键就是在哪里用加速器…我们要让一个加速器尽可能多的贡献出它的价值，就要让他造福更多的人。如果这条边上经过的人很多的话，使用加速器会更划算。
每次找一个能够影响最多人的路径。每个点出发时间一定在最后一个人到达的时间之后因此每次找的时候，计算一下每一条边最多能够向后影响多少人，取最大值，然后重复计算O(nk)的复杂度可以接受

代码

for(int i=1;i<n;++i)d[i]=read();
for(int i=1;i<=m;++i)
{
    T[i]=read();fr[i]=read();to[i]=read();
    lst[fr[i]]=max(lst[fr[i]],T[i]);//某一个景点最后一个人出现的时间
    down[to[i]]++;//统计下车人数
}
for(int i=2;i<=n;++i)tt[i]=max(tt[i-1],lst[i-1])+d[i-1];
for(int i=1;i<=n;++i)ss[i]=ss[i-1]+down[i];
for(int i=1;i<=m;++i)ans+=tt[to[i]]-T[i];
us[n]=us[n-1]=n;//用一个加速器可以影响的最后一条边
tt[1]=lst[1];
while(k--)
{
   for(int i=2;i<=n;++i)
   tt[i]=max(tt[i-1],lst[i-1])+d[i-1];//计算每一个站到达的时间
   for(int i=n-2;i;--i)
   us[i]=tt[i+1]<=lst[i+1]?i+1:us[i+1];
   nn=mm=0;
   for(int i=1;i<n;++i)
   {
        if(ss[us[i]]-ss[i]>nn&&d[i])
        {
            nn=ss[us[i]]-ss[i];
            mm=i;
        }
   }
   ans-=nn;d[mm]--;
}

Thanks for your attention.