这两天的模拟赛着实让人找到了当年敲键盘的感觉(学了两个月习，手感消失殆尽QwQ)。今天，就让我们一同走进国庆的第二套NOIP模拟赛试题吧！

A Lot-A Journey to Mars

问题描述：
Byteazar 决定去火星参加一个空间站旅行. 火星的所有空间站都位于一个圆上. Byteazar 在其中一个登陆然后变开始饶圈旅行.
旅行需要耗费油料,一升油料只能跑1米,每个空间站可以补给的油料都有所不同.
Byteazar 每到一个空间站便可以把该空间站的油料全部拿走.(他的油箱是没有容量限制的) 但是如果走到某个时候突然没油了那么旅行便失败了.
Byteazar 需要决定要在哪个地方登陆使得他能顺利访问完所有的空间站后回到他当初登陆的地方. 一个细节是他登陆后可以选择两个方向中的任意一个进行旅行.
输入格式
第一行是一个数N (3≤N≤1 000 000). 表示空间站的总数. 空间站从1 到 N标号.
接下来N 行每行两个数pi 和 di (p≤0, di＞0). 表示第i个空间站所储存的油料以及第i个到第i + 1个空间站之间的距离( dN 表示第N个空间站到第1个空间站的距离).
所有的油料以及所有的距离的和保证不超过2 000 000 000.
输出格式
输出n行,如果从第i个空间站登陆可以走遍所有的空间站那么打印TAK (YES is Polish), 否则打印NIE (NO in Polish).
样例输入
5
3 1
1 2
5 2
0 1
5 4
样例输出
TAK
NIE
TAK
NIE
TAK

这道题看起来十分复杂，但其实只要get到思路，就是一道简单的裸题了。

在此之前，你有么有考虑过一个问题：跑一圈都是跑的相同的一圈，经过的点也都相同，为什么有的点开始就能跑完一整圈，有的点开始就跑不完呢？

如果一个点跑不完一整圈，那它一定是在半路上某两个点中间死掉了，即油量小于零了。如果我们给每个点设一个“濒死值”，表示刚到某个点，还没有拿这个点的油时，油的剩余量。死掉了就是中间有某个点的“濒死值”小于0了。

而在我们一圈的计算中，某个点为什么可以往后走？那是因为它之前节点省吃俭用省下来的油量加上它这个节点本来的油量，再减去这个节点走到下一个节点的距离大于等于0，那他能顺利走到下一个节点，并把多余的油交给下个节点，以此重复……

因此，问题转化为了，每个点在初始没有结余（即初始油量为0【就是拿不到之前节点省吃俭用省下来的油量】）的情况下，能否熬过以它开始的一圈中汽油最少的一段（濒死值最小的一个点）。

所以可以预处理——从1开始暴力模拟一遍，求出以1为起点的每个点的“濒死值”。因为是环，所以可以在n后面再补一段1~n。把这段长为 2*n 的路走一遍。 看一下每个点走到自己对应的点的路上最小的濒死值的最小值是否大于这个点的剩余（也就是这个点的濒死值），就可以判断是否能从这个点开始走完一圈了。

现在，唯一的问题变为了，如何在一个长为 2n 的序列中，求出一些长为 n 的段的最小值。

这不就是一个裸的优先队列吗？所以总的思路就是预处理加优先队列

至此，这道题就被完美解决了，详见代码：

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int v[2200000];//油量 
int d[2200000];//路程 
int a[2200000];//濒死值 
int b[2200000];//b[i]表示i到i+n-1中濒死值最小的值为多少 
int q[2200000];//队列
bool ans[2200000]={0}; 

int i,j,k,m,n,o,p,js,jl,jk,s,h,t;

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&v[i],&d[i]);
        v[i+n]=v[i];d[i+n]=d[i];
    }

    js=0;
    for(int i=1;i<=2*n;i++)
    {
        a[i]=js;
        js=js+v[i]-d[i];
    }

    h=0;t=0;

    for(int i=1;i<=2*n;i++)
    {
        while(h<t && a[i]<=a[q[t-1]])t--;
        q[t++]=i;

        while(h<t && q[t-1]-q[h]>=n)h++;

        if(i>n)b[i-n]=a[q[h]];
    }

    for(int i=1;i<=n;i++)if(b[i]-a[i]>=0)ans[i]=1;
    //正向

    js=0;d[0]=d[2*n];
    for(int i=2*n;i>=1;i--)
    {
        a[i]=js;
        js=js+v[i]-d[i-1];
    }

    h=0;t=0;

    for(int i=2*n;i>=1;i--)
    {
        while(h<t && a[i]<=a[q[t-1]])t--;
        q[t++]=i;

        while(h<t && q[h]-q[t-1]>=n)h++;

        if(i<=n)b[i]=a[q[h]];
    }

    for(int i=1;i<=n;i++)if(b[i]-a[i+n]>=0)ans[i]=1;
    //反向
    for(int i=1;i<=n;i++)
    if(ans[i])printf("TAK\n");
    else printf("NIE\n");
    return 0;
}

B 中国象棋

问题描述：
这次小可可想解决的难题和中国象棋有关，在一个N行M列的棋盘上，让你放若干个炮（可以是0个），使得没有一个炮可以攻击到另一个炮，请问有多少种放置方法。
大家肯定很清楚，在中国象棋中炮的行走方式是：一个炮攻击到另一个炮，当且仅当它们在同一行或同一列中，且它们之间恰好 有一个棋子。你也来和小可可一起锻炼一下思维吧！
输入格式
一行包含两个整数N，M，之间由一个空格隔开。
【数据规模】
除了在3个格子中都放满炮的的情况外，其它的都可以.
100%的数据中N,M不超过100
50%的数据中，N,M至少有一个数不超过8
30%的数据中，N,M均不超过6
输出格式
总共的方案数，由于该值可能很大，只需给出方案数模9999973的结果。
样例输入
1 3
样例输出
7

这是一道很经典的DP题，一上来看100%的数据肯定是很蒙的，所以我们可以根据数据一步一步慢慢猜测出最终的解法。

首先，30%的算法，没什么好说的，就是单纯的暴力，将每种情况搞出来，判断可行性，时间复杂度O(2^(n*n))。

然后我们重点来思考一下50%的解法，N,M至少有一个数不超过8，这很明显是在暗示我们使用状压DP，我们考虑可以用一个三进制数 k 表示前 i 列的状态，比如当k=01201时，就代表此时第一列还没有放炮，第二列已经放了一个炮，第三列已经放了一个炮了，第四列还没有放炮，第五列已经放了一个炮了。所以我们可以设a[i][k]为第i行状态为k的方案总数，然后正常的状压DP转移就可以了，还是挺简单的，50分到手。

现在我们考虑100%的解法，显然，我们DP的方向但应该是对的，但是为什么刚刚50%的做法过不了100%呢？那是因为表示状态的 k 这一维实在太大了。所以我们就考虑，能不能把k给简化或者替代掉？当然可以，其实在DP转移的过程中，哪一列是有一个炮，哪一列有两个炮其实是不重要的，主要是要知道有几列有一个炮，有几列有两个炮。

所以我们就设 a[i][j][k] 为前i行，有j列有一个炮，k列有两个炮【当然就有（m-j-k）列没有炮】的方案总数，接着我们分情况讨论转移就解决了(详见代码)，100分到手。

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
long long a[110][110][110];
long long i,j,k,m,n,o,p,js,jl,jk;
int main()
{
    scanf("%lld%lld",&n,&m);
    a[0][0][0]=1;

    for(int i=0;i<n;i++)
    for(int j=0;j<=m;j++)
    for(int k=0;k<=m-j;k++)
    {
        a[i+1][j][k]=(a[i+1][j][k]+a[i][j][k])%9999973;//直接转移

        //这一行不放炮

        if(j+k<m)a[i+1][j+1][k]=(a[i+1][j+1][k]+(m-j-k)*a[i][j][k])%9999973;//把一个没有炮的列变成有一个炮的列
        if(j>0)a[i+1][j-1][k+1]=(a[i+1][j-1][k+1]+j*a[i][j][k])%9999973;//把一个有一个炮的列变成一个有两个炮的列

        //这一行放一个炮

        if(j+k<m-1)a[i+1][j+2][k]=(a[i+1][j+2][k]+(m-j-k)*(m-j-k-1)/2*a[i][j][k])%9999973;//把两个没有炮的列变成两个只有一个炮的列
        if(j>1)a[i+1][j-2][k+2]=(a[i+1][j-2][k+2]+j*(j-1)/2*a[i][j][k])%9999973;//把两个只有一个炮的列变成两个有两个炮的列
        if(j+k<m)if(j>0)a[i+1][j][k+1]=(a[i+1][j][k+1]+(m-j-k)*j*a[i][j][k])%9999973;//把一个没有炮的列变成有一个炮的列，同时把之前一个只有一个炮的列变成有两个炮的列

        //这一行放两个炮

    }
    js=0;
    for(int i=0;i<=m;i++)
    for(int j=0;j<=m-i;j++)
    js=(js+a[n][i][j])%9999973;
    //统计结果总数
    printf("%lld",js);
    return 0; 
} 

C 飞行棋

问题描述：
在经过地“小小宇航员夏令营”的学习以及模拟飞行实验后，小可可明白宇航员并不是那么容易当的，
除了需要强健的身体，丰富的经验以及灵活的应变能力以外，缜密的思维也是不可少的，为了早日实现自己的宇航员的梦想，
小可可决定在平时就开始锻炼——利用棋类游戏来锻炼自己的思维。
小可可发明一种飞行棋，棋盘是一个圆周形，在圆周形上有若干个点，已知这些点与点之间的弧长，弧长均为正整数，并且依圆弧顺序排列，
飞行棋的规则是找出这些点中有没有可以围成矩形的，在最短时间内找出所有不重复矩形的玩家胜出。
输入格式
第一行为正整数N，表示点的个数，接下来N行分别为这N个点所分割的各个圆弧长度
【数据规模】
N≤20
输出格式
所构成不重复矩形的个数
样例输入
8
1
2
2
3
1
1
3
3
样例输出
3

这应该是这套题目中最水的一题了，考虑什么时候四个点围成的四边形才是矩形？对！就是对角线恰好为直径的时候，所以我们只要找出任意两点的连线中，为直径的个数n，答案ans就为n*(n-1)。

那么问题就变成了，如何确定圆上的两个点的连线是否为直径。这就很简单了，我们知道，直径的两个点肯定平分一个圆，所以我们设全部弧长为m，如果这两点的差值的绝对值恰好为m/2，那么这两个点就恰好跨过了半个园，也就恰好是直径了。代码如下：

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int a[22],s[22];
int i,j,k,m,n,o,p,js,jl,jk;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        s[i]=s[i-1]+a[i];
    }

    if(s[n]%2==1)
    {
        printf("0");
        exit(0);
    }

    jl=0;
    for(int i=1;i<=n;i++)
    {
        if(s[i]>s[n]/2)break;
        for(int j=1;j<=n;j++)if(s[j]-s[i]==s[n]/2)jl++;

    }

    printf("%d",jl*(jl-1)/2);

    return 0;
}

D 物流运输

问题描述：
物流公司要把一批货物从码头A运到码头B。由于货物量比较大，需要n天才能运完。货物运输过程中一般要转停好几个码头。
物流公司通常会设计一条固定的运输路线，以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在，有的时候某个码头会无法装卸货物。
这时候就必须修改运输路线，让货物能够按时到达目的地。
但是修改路线是一件十分麻烦的事情，会带来额外的成本。因此物流公司希望能够订一个n天的运输计划，使得总成本尽可能地小。
输入格式
第一行是四个整数n（1<=n<=100）、m（1<=m<=20）、K和e。
n表示货物运输所需天数，m表示码头总数，K表示每次修改运输路线所需成本。
接下来e行每行是一条航线描述，包括了三个整数，依次表示航线连接的两个码头编号以及航线长度（>0）。其中码头A编号为1，码头B编号为m。单位长度的运输费用为1。航线是双向的。
再接下来一行是一个整数d，后面的d行每行是三个整数P（ 1 < P < m）、a、b（1 < = a < = b < = n）。表示编号为P的码头从第a天到第b天无法装卸货物（含头尾）。
同一个码头有可能在多个时间段内不可用。但任何时间都存在至少一条从码头A到码头B的运输路线。
输出格式
包括了一个整数表示最小的总成本。总成本=n天运输路线长度之和+K改变运输路线的次数。
【样例解释】
前三天走1-4-5，后两天走1-3-5，这样总成本为(2+2)3+(3+2)*2+10=32
样例输入
5 5 10 8
1 2 1
1 3 3
1 4 2
2 3 2
2 4 4
3 4 1
3 5 2
4 5 2
4
2 2 3
3 1 1
3 3 3
4 4 5
样例输出
32

不得不说，这确实是一道很有意思的题目。很明显是要求解最短路，但是怎么操作呢？别急，等我慢慢分析给你听。

我们构想一下，由于我们不知道哪一天要走那一条路，但我知道，在某一段路线不变的时间内，我们走过的要不就是这段时间能走的最短路径，要不就是这段时间之前就一直在走的路径，所以这就有一些dp的味道了。

我们试想一下，当我们到第i天的时候，只有两种选择，一是继续i-1天走过的路，二是换一条新的路，当然，如果在这一天原先的路不能走了就必须要换一条路，然而换成什么路当然是用最短路求啦。

我们再考虑一下，如果第n-1天的路在第n天就不能走了，我们换了一条最短的路，然而第n+1天这条最短路就又不能走了，又要换一条新的，可能就会导致最后的答案不是最优。所以我们可以考虑这样做，先设dp[i]为前i天的最小花费。我们很明显可以枚举一个j，表示从j到i的线路是一样的，也就是说，在第j天变更了线路，接着我们求出从第i天到第j天都可以走的最短路成本乘上（j-i+1），加上第i-1天及以前的总成本，再加上换方案的费用k，就是这种方案下到第i天的最小花费数，j继续向前枚举，让每种方案得到的花费数与dp[i]一一比较，得到的最小值dp[i]就是我们最后要的结果。

程序如下：

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int i,j,k,m,n,o,p,js,jl,e,x,y,z,d,ll;
int map[22][22],dp[110],now[22];
int a[22][110]={0};
int list[22000],f[22],vis[22];
int head,tail;

inline char gc(){
    static char buff[0xFFFF],*p1=buff,*p2=buff;
    return (p1==p2)&&(p2=(p1=buff)+fread(buff,1,0xFFFF,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    int t=0;
    char ch=gc();
    while((ch<'0')||(ch>'9'))
        ch=gc();
    while((ch>='0')&&(ch<='9'))
        t=t*10+ch-'0',
        ch=gc();
    return t;
}

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

int spfa()
{
    memset(list,0,sizeof(list));
    memset(f,63,sizeof(f));
    memset(vis,0,sizeof(vis));
    head=1;tail=2;list[1]=1;f[1]=0;vis[1]=1;

    while(head<tail)
    {
        int x=list[head];
        for(int i=1;i<=m;i++)
        {
            if(now[i]==0 && map[x][i]!=1061109567)
            {
                if(f[i]>f[x]+map[x][i])
                {
                    f[i]=f[x]+map[x][i];
                    if(vis[i]==0)
                    {
                        list[tail]=i;
                        tail++;
                        vis[i]=1;
                    }
                }
            }
        } 
        vis[x]=0;
        head++;
    }
    return(f[m]);
}
int main()
{
    n=read(),m=read(),k=read(),e=read();
    memset(map,63,sizeof(map));
    memset(dp,63,sizeof(dp));
    for(int i=1;i<=e;i++)
    {
        x=read(),y=read(),z=read();
        map[x][y]=z;
        map[y][x]=z;
    }   

    d=read();
    for(int i=1;i<=d;i++)
    {
        p=read(),x=read(),y=read();
        for(int j=x;j<=y;j++)a[p][j]=1;
    }

    dp[0]=-k;

    for(int i=1;i<=n;i++)
    {
        memset(now,0,sizeof(now));
        for(int j=i;j>=1;j--)
        {
            for(int l=1;l<=m;l++)now[l]|=a[l][j];
            ll=spfa(); 
            if(ll>=1061109567)break;
            dp[i]=my_min(dp[i],dp[j-1]+ll*(i-j+1)+k);
        }
    }

    printf("%d",dp[n]);
    return 0;
}

结语

呀突然发现明天又要开始上课了呢（毕竟高三QWQ），然后下周六就初赛了……突然感到岁月的沧桑，人世的迷茫(划掉)，那就希望各位小伙伴能顺利通过初赛，在复赛上运用蒟蒻的知识一展身手。哈哈，最后还是希望你能喜欢这篇BLOG！

【ps最后的最后一起来看猫片QwQ(激励我学oi的猫)】