昨天去西湖玩了一天，所以BLOG咕咕咕了……这两天考了一场NOIP模拟赛，题目和思路还是很棒的，下面让我们一起来分享一下这些题目和思路吧！

T1 钢铁侠的诞生(a.c/cpp)

托尼是斯塔克工业公司的继承人，在一次交易中不幸被恐怖分子抓捕并关押
在山洞里。为了逃离恐怖分子的魔爪，托尼假装为恐怖分子研究武器，实际上是
在秘密研究一套全新的钢铁战衣。
几个月之后，钢铁战衣基本成型了，但需要使用强力的能源装置进行充能。
所幸恐怖分子的仓库里存放了 n 个能源提供装置。每个装置上都写了一个整数
代表它的类别（同一个类别的装置可能有多个）。
托尼一共需要 m 个能源提供装置，并且他幸运地发现这个需求是可以满足
的（既托尼需求的m个装置都可以从仓库里获得）。
现在托尼希望你帮他整理出剩下的装置种类，以便制作一些别的武器掩人耳
目（毕竟托尼假装在帮恐怖分子制造武器）。

输入格式：
第一行输入两个整数n, m分别代表仓库中的装置总数以及托尼需要的装置
总数
接下来一行n个整数，第i个整数a[i]代表仓库中第i个装置的类别
接下来一行m个整数，第i个整数b[i]代表托尼需要的第i个装置的类别
输出格式：
输出仅一行，按从小到大的顺序输出 n – m 个整数，代表剩下的每个装置
的类别

样例输入：
5 2
4 3 2 1 1
2 1

样例输出：
1 3 4

样例说明：
类别 1 的装置一共有 2 个，托尼用掉一个之后还剩下 1 个。类别 2 的装置只有
一个，托尼用掉之后就没有了。

数据范围：
对于30%的数据：
1<=N<=1000
另外有20%的数据：
1 <= a[i], b[i]（装置的类别编号） <= 100000
对于100%的数据：
1 <= N <= 300000
1 <= a[i], b[i] <= 1000000000

这道题算是签到题了，思路多种多样，考察知识点主要是：排序, stl的应用，下面我们来看一下具体解法：

方法一：用map<int, int> 可以记录每个类别的资源一共有多少个，然后减去托尼需要的资源后按顺序输出即可

方法二：可以将所有资源、托尼需要的资源分别排序，排序完之后用两个指针i, j分别指向两个数组的首位。如果对应位置的资源类别相等，那么指针同时后移，否则说明当前资源托尼不需要，输出后把指针i后移即可

方法三：这种解法就比较厉害了，当我第一眼看到这道题的数据范围，O(n log n)是稳过的，我们要维护数据的添加和删除，那就打个平衡树吧！于是考试我就敲了一个FHQ平衡树……虽然可以过而且跑的挺快，但是代码长度对比上面两种解法就……下面附上代码：

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
FILE *fin,*fout;
struct node
{
    int d,c,key,son[2];
}tr[3300000];int len;

int root=1,seed=233;

int Random()
{
    return seed=int(seed*482711ll%2147483647);
}

void update(int x)
{
    tr[x].c=tr[tr[x].son[0]].c+tr[tr[x].son[1]].c+1;
    return ;
}

int add(int d)
{
    tr[++len].d=d;
    tr[len].c=1;
    tr[len].key=Random();
    tr[len].son[0]=tr[len].son[1]=0;
    return(len);
} 

int find(int now,int rank)
{
    while(tr[tr[now].son[0]].c+1!=rank)
    {
        if(rank<=tr[tr[now].son[0]].c)now=tr[now].son[0];
        else 
          rank-=tr[tr[now].son[0]].c+1,now=tr[now].son[1];
    }
    return(tr[now].d);
}

void merge(int &now,int a,int b)
{
    if(a==0 || b==0)
    {
        now=a+b;
        return ;
    }

    if(tr[a].key<tr[b].key)
      now=a,merge(tr[now].son[1],tr[a].son[1],b);

    else
      now=b,merge(tr[now].son[0],a,tr[b].son[0]);

    update(now);
    return ;
}

void splid(int now,int &a,int &b,int d)
{
    if(now==0)
    {
        a=b=0;
        return ;
    }

    if(tr[now].d<=d)
      a=now,splid(tr[now].son[1],tr[a].son[1],b,d);
    else
      b=now,splid(tr[now].son[0],a,tr[b].son[0],d);

    update(now);
    return ;
}

void ins(int d)
{
    int z=add(d),x=0,y=0;
    splid(root,x,y,d);
    merge(x,x,z);
    merge(root,x,y);
    return ;
}

void del(int d)
{
    int z=0,x=0,y=0;
    splid(root,x,y,d);
    splid(x,x,z,d-1);
    merge(z,tr[z].son[0],tr[z].son[1]);
    merge(x,x,z);
    merge(root,x,y);
     return ;
} 
int find(int x)
{
    if(tr[x].son[0]!=0)find(tr[x].son[0]);
    if(tr[x].d!=2147483627)fprintf(fout,"%d ",tr[x].d);
    if(tr[x].son[1]!=0)find(tr[x].son[1]);
}
int main()
{
    fin=fopen("a.in","rb");
    fout=fopen("a.out","wb");
    int i,j,k,n,m,x,y;root=1;
    add(2147483627); tr[1].c=0;

    fscanf(fin,"%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        fscanf(fin,"%d",&x);
        ins(x);
    }
    for(int i=1;i<=m;i++)
    {
        fscanf(fin,"%d",&x);
        del(x);
    }
    find(root);
    fclose(fin);
    fclose(fout);
    return 0;
} 

T2 钢铁侠的逃离(b.c/cpp)

终于，托尼在你的帮助下造出了钢铁战衣。为了逃离山洞，托尼必须先将恐
怖分子沿路建设的防御塔摧毁。
通过钢铁战衣上的透视装置，托尼观察到恐怖分子在一条直线上建设了 N
座防御塔，且两两之间的距离都为 A。最近的防御塔到托尼的距离为 A+B，因
此这N座防御塔到托尼的距离呈一个等差数列:
B + A, B + 2A, B + 3A, ..., B + NA
托尼准备了 N 个炸药，每个炸药都可以直接炸毁一座防御塔。炸药需要使
用推进器进行推进，每个推进器可以将炸药向前推进一段距离。一个炸药上可以
使用多个推进器。但因为推进器的构造特殊，每个推进器推进的距离必须是2的
非负整数次幂（既1， 2， 4， 8， 16…）。
因为推进器的材料十分宝贵，托尼希望你帮他计算出至少要使用多少个推进
器才可以炸毁所有防御塔。
输入格式：
第一行输入一个整数T代表数据组数
接下来T行每行输入三个整数A,B,N
输出格式：
输出T行，每行一个整数代表答案
样例输入：
3
1 1 2
4 7 1
5 8 2
样例输出：
3
3
5

样例说明：
对于第一组样例，有一个距离为 2 的防御塔和一个距离为 3 的防御塔，第一个
防御塔只需要一个推进器就可以炸毁，第二个防御塔需要使用两个距离分别为1,
2的推进器才可以炸毁
对于第二组样例，只有一个距离为 11 的防御塔，需要使用三个距离分别为 1、
2、8的推进器才可以炸毁

数据范围：
对于30%的数据：
1<=T<=20 , 1<=A<=10000 , 1<=B<=10^16 , 1<=N<=10^3
对于60%的数据：
1<=T<=20 , 1<=A<=10000 , 1<=B<=10^16 , 1<=N<=10^9
对于100%的数据：
1<=T<=20 , 1<=A<=10000 , 1<=B<=10^16 , 1<=N<=10^12

这道题考察知识点有：枚举法，二进制的理解与应用
观察可知，摧毁一个防御塔需要的推进器数量，等于这个防御塔距离的二进制表示中有多少个1。因此原问题相当于求一个等差数列每一位有多少1。
对于30%的数据，我们直接对每一个防御塔进行计算即可：

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
unsigned long long a,b,n,cc;
long long i,j,k,m,o,p,js,jl,ans,t;  
int main()
{
    FILE *fin,*fout;
    fin=fopen("b.in","rb");
    fout=fopen("b.out","wb");
    fscanf(fin,"%d",&t);
    for(int i=1;i<=t;i++)
    {
        ans=0;
        fscanf(fin,"%lld%lld%lld",&a,&b,&n);
        for(int j=1;j<=n;j++)
        {
            b+=a;cc=b;
            while(cc>0)
            {
                ans+=cc%2;
                cc=cc/2;
            }
        }
        fprintf(fout,"%lld\n",ans);
    }
    fclose(fin);
    fclose(fout);
    return 0;
} 

对于100%的数据，我们考虑依次统计二进制的每一位上有多少个1。对于二进制的第K位，B+A与B+(2 ^ K + 1)A显然是相同的，因此我们只需要统计一个循环节内（既B+A到B + （2 ^ K）A）里面有多少个1即可。
对于一个循环节内，可以将连续的一段0或者连续的一段1一起处理，循环节长度为2^K, 而连续的一段0或1有(2^(K - 1) / A)个，因此枚举的复杂度为O(2^K/((2^(K - 1))/A)) = O(2A)。因为外层还要枚举二进制的每一位，因此总复杂度为O(A * (log(B + NA))

程序比较简单就不附上来了。

T3 钢铁侠的复仇(c.c/cpp/pas)

在你的帮助下，托尼终于逃回了公司。
为了防止恐怖分子再次行动，托尼决定改进钢铁战衣，对恐怖分子的基地进
行打击。
通过观察，托尼发现恐怖分子的基地中一共有N*M个碉堡并排布成一个N
行M列的矩形。为了便于描述，我们假定第X行，第Y列的碉堡坐标为(x, y) (1
<= x <= N, 1 <= y <= M)。对于坐标为(x, y)的碉堡，它的攻克难度为A[x][y],
攻克需要的时间为 B[x][y]。从一个碉堡(x1, y1)飞到另一个碉堡(x2, y2)需要的
时间为它们之间的曼哈顿距离：|x1 - x2| + |y1 - y2|。
由于钢铁战衣有精确的定位装置，托尼可以随意选择一个碉堡降落，然后按
任意顺序攻克若干个碉堡（不要求攻克所有的碉堡）。由于托尼是一个喜欢挑战
的人，因此他要求他攻克碉堡的难度必须是严格上升的。同时，托尼想多活动一
下身体，因此他希望这次行动的总时间尽可能的长。
因为钢铁战衣上配置了智能的控制系统，托尼在攻克一个碉堡之后必须直接
飞行到下一个要攻克的碉堡，且不允许绕远路（既飞行时间为两点之间的曼哈顿
距离）。托尼希望你帮他计算出这次行动可能的最长总时间。

输入格式：
第一行输入两个整数N, M
接下来N行每行M个整数，第x行第y个整数代表A[x][y]
接下来N行每行M个整数，第x行第y个整数代表B[x][y]
注意，有一些A[x][y]=B[x][y]=0，说明这个碉堡已经毁坏，不能攻克
输出格式：
输出一行代表最长的总时间
样例输入：
4 5
1 2 6 0 2
1 3 4 0 4
0 0 4 0 3
2 2 0 0 4
1 3 5 0 2
2 8 1 0 2
0 0 3 0 4
0 5 0 0 3
样例输出：
39
样例说明：攻克顺序为(2,1)->(1,5)->(2,2)->(4,5)->(1,3)
数据范围：
对于30%的数据：
1<=N<=50 , 1<=M<=50
对于60%的数据：
1<=N<=300 , 1<=M<=300
对于100%的数据：
1<=N<=1000 , 1<=M<=1000
0<=A[x][y]<=1000000
0<=B[x][y]<=10^9
注意：本题输入数据较大，请注意输入消耗的时间

这道题是这套题目里面最有趣的题目，首先我们会发现，每一层必走，也就是难度假如有3，4，5三个点，路线一定是3-4-5，而不是3-5；所以我们就可以由此打出一个明显分成若干层的有向图，明显可以SPFA跑最短路，然后就拿到了30分：

#include<cmath>
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
struct node
{
    int x,y,z,next;
}f[1100000];
struct nodee
{
    int x,y,z,next;
}g[11000000];
int a[1100][1100],b[1100][1100],last[1100000],lastt[1100000],h[1100000],vis[1100000],ys[1100000],fys[1100000];
int i,j,k,m,n,o,p,js,jl,jk,len=0,lenn=0,mi,ma,x,y,s,t;

int my_min(int x,int y)
{
    if(x<y)return(x);
    else return(y);
}

int my_max(int x,int y)
{
    if(x>y)return(x);
    else return(y);
}

int add(int x,int y,int z)
{
    len++;
    f[len].x=x;f[len].y=y;f[len].z=z;
    f[len].next=last[z];
    last[z]=len;
}

int ins(int x,int y,int z)
{
    lenn++;
    g[lenn].x=x;g[lenn].y=y;g[lenn].z=z;
    g[lenn].next=lastt[x];
    lastt[x]=lenn;

}

deque <int> q;

int spfa(int s,int t)
{
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=t;i++)h[i]=-2147483620;
    h[0]=0;
    q.push_back(s);vis[s]=1;

    while(!q.empty())
    {
        x=q.front();q.pop_front();
        for(int k=lastt[x];k;k=g[k].next)
        {
            y=g[k].y;
            if(g[k].z+h[x]>h[y])
            {
                h[y]=(g[k].z+h[x]);
                if(vis[y]==0)
                {
                    vis[y]=1;
                     if(!q.empty() && h[y]>q[q.front()])q.push_front(y);
                     else q.push_back(y);
                }
             } 
        }
        vis[x]=0;
    }
    return(0);
} 

int main()
{
    FILE *fin,*fout;
    fin=fopen("c.in","rb");
    fout=fopen("c.out","wb");
    fscanf(fin,"%d%d",&n,&m);
    ma=0;mi=2147483627;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        fscanf(fin,"%d",&a[i][j]);
        if(a[i][j]>0)add(i,j,a[i][j]);
        ma=my_max(ma,a[i][j]);
        if(a[i][j]>0)mi=my_min(mi,a[i][j]);
    }
    js=0;
    for(int i=1;i<=ma;i++)if(last[i]>0)
    {
        js++;
        ys[i]=js;
        fys[js]=i;
    }

    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    fscanf(fin,"%d",&b[i][j]);
    s=0;t=n*m+1;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    if(a[i][j]>0)
    {
        x=fys[ys[a[i][j]]+1];
        if(a[i][j]==mi)ins(s,(i-1)*m+j,0);
        if(a[i][j]==ma)ins((i-1)*m+j,t,b[i][j]);
        for(int k=last[x];k;k=f[k].next)
        {
            y=abs(i-f[k].x)+abs(j-f[k].y)+b[i][j];
            ins((i-1)*m+j,(f[k].x-1)*m+f[k].y,y);
        }
    }

    spfa(s,t);
    fprintf(fout,"%d",h[t]);
    fclose(fin);
    fclose(fout);
    return 0;
}

然后我们仔细想一想，分层的最短路？这不就是动态规划吗？

直接的转移方程很容易想到: f[x][y] = max(f[i][j] + abs(i - x) + abs(j - y)), i in [1, N], j in [1, M]
直接转移的复杂度为O(N^2 * M^2)，但是还是只能通过30%的数据：

接下来我们考虑如何加速转移
对于转移方程中的式子，可以根据绝对值函数内的正负形拆成四种形式。例如i >= x, j >= y时，原式变为
f[i][j] + i - x + j - y

(f[i][j] + i + j) - x - y
在求f[x][y]时， 我们只需要找到这个满足条件的最大的(f[i][j] + i + j)即可，类似的还有三种形式，可以使用二维线段树分别维护最大值。这种做法的复杂度为O(N M log(N) * log(M)，可以通过60%的数据

接下来继续考虑i, j到x, y的转移，有四种可能的形式:
f[i][j] + (i - x) + (j - y), f[i][j] + (i - x) + (y - j), f[i][j] + (x - i) + (j - y), f[i][j] + (x - i) + (y - j)
因为有绝对值运算，正确的转移应该要根据i, x的大小关系与j, y的大小关系选择四种形式中的一种。但考虑到绝对值的性质有：abs(i - x) >= i - x，因此有
f[i][j] + abs(i - x) + abs(j - y) =
max(f[i][j] + (i - x) + (j - y), f[i][j] + (i - x) + (y - j), f[i][j] + (x - i) + (j - y), f[i][j] + (x - i) + (y - j))
所以我们其实可以不管i, x和j, y的大小关系，四种情况的转移都一起考虑，最终的答案也是一样的
既
f[x][y] = max(
-x - y + max(f[i, j] + i + j),
-x + y + max(f[i, j] + i - j),
x - y + max(f[i, j] - i + j),
x + y + max(f[i, j] - i - j)
)， i in [1, N], j in [1, M]
这四项中的max均为全局最大值，在每次转移结束后更新即可，复杂度为O(N * M)，但是貌似二维树状数组无法维护区域最值，所以要手打非常非常复杂的二维线段树。

结语

这次模拟赛看到了自己还是有很多欠缺的，希望自己能慢慢成长，在NOIP2018中，考出真正的水平吧！