本篇题解借鉴和参考了洛谷题解区的同学所写的题解以及部分博文，由于未能记录全面，并没能将这些参考内容全部列出，为此对这些内容的作者感到抱歉。

NOIP2017已经结束啦。在华中科大计科实验室度过的7个小时犯了挺多的错误，现在想想，其实自己能上300。初次考试，题型有少许变化加上自己没有经验，成功爆炸。还好最后D1T2救了一下场。
接下来是题解和感想。

NOIP2017 提高组 Day1

吐槽

T1实在是太太太太太太拉分了orz

个人成绩

30，90，0

题目列表（评测来自洛谷）

赛题 #A: P3951 小凯的疑惑 | 数论，找规律
赛题 #B: P3952 时间复杂度 | 大模拟，耐心
赛题 #C: P3953 逛公园 | 图论，记忆化搜索，k短路计数

小凯的疑惑

一句话题意

求使px+qy=n无自然数范围内的解的最大正整数n。其中，p, q互质。

解法

100% 1 \leq a, b \leq 10^9

只需输出pq - p - q即可。
证明：试使用反证法
假设存在正整数x, y使px + qy = pq - p - q
则有p(x+1)+q(y+1)=pq
易知p|q(y+1)
\because gcd(p, q)=1
\therefore p|y+1
同理q|x+1
令y+1=pj, x+1=qk
则有pqk+qpj=pq
也就是pq(j+k)=pq
\because j+k=x+y+2 \geq 2
上式并不成立，得证。
但是考场上推出这个方法应该打表找规律。
还有一种扩欧推出的方法，更多题解可以看洛谷题解 P3951 – 百科 – 洛谷。

代码

// Code by KSkun, 2017/11
#include <cstdio>

int main() {
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%lld", 1ll * a * b - a - b);
    return 0;
}

总结

千言万语汇成一句话：数论推个屁，打表找规律。铭记在心，终生受用。

时间复杂度

没有概括，自己看洛谷

解法

100% L \leq 100

维护一个管理循环的栈。由于循环从里到外结束，可用栈管理循环的嵌套关系。
细节比较多，如果该循环能够计入这一次的复杂度，则满足以下条件：

1. 之前不能有不能执行的循环
2. 循环的终点是n

不计入复杂度但能执行的循环满足以下条件中任意的一条：

1. 起点和终点都是常数，且起点小于等于终点
2. 起点和终点都是n

不能被执行的循环满足以下条件中任意的一条：

1. 起点是n
2. 起点和终点都是常数，且起点小于终点

语法错误有3类：

1. 变量名冲突（vis管理一下）
2. E语句结束了不存在的循环（判断栈是否为空）
3. 结束指令后仍有未关闭的循环（同2）

对于不能被执行的循环，打标记并使之后的循环对答案无贡献，直到它出栈。逐循环计算它对总复杂度的贡献。只要把以上细节写全了就能A。

代码

// Code by KSkun, 2017/11
#include <cstdio>
#include <cstring>
#include <stack>
#include <algorithm>

struct Loop {
    char var;
    int beg, end;
    Loop(char var, int beg, int end): var(var), beg(beg), end(end) {}
};

inline int getComp(char *str) {
    if(str[2] == 'n') {
        int res = 0, len = strlen(str);
        for(int i = 4; i < len; i++) {
            if(str[i] == ')') break;
            res = res * 10 + str[i] - '0';
        }
        return res;
    }
    return 0;
}

inline int getNum(char *str) {
    if(str[0] == 'n') return -1;
    int res = 0, len = strlen(str);
    for(int i = 0; i < len; i++) {
        res = res * 10 + str[i] - '0';
    }
    return res;
}

bool vis[50], iserr;
char op[5], var[5], beg[5], end[5], complexity[100], notValid;
int t, l, now, all, exp;
std::stack<Loop> sta;

int main() {
    //freopen("p3952.in", "r", stdin);
    scanf("%d", &t);
    while(t--) {
        memset(vis, 0, sizeof vis);
        while(!sta.empty()) sta.pop();
        iserr = false;
        notValid = '-';
        now = all = 0;
        scanf("%d%s", &l, complexity);
        exp = getComp(complexity);
        while(l--) {
            scanf("%s", op);
            if(op[0] == 'F') {
                scanf("%s%s%s", var, beg, end);
                // ERR proccess
                if(vis[var[0] - 'a']) {
                    iserr = true;
                    continue;
                } 

                // non-ERR process
                if(iserr) continue;
                vis[var[0] - 'a'] = true;
                Loop t = Loop(var[0], getNum(beg), getNum(end));
                sta.push(t);
                if(((t.beg == -1 && t.end != -1) || (t.beg != -1 && t.end != -1 && t.beg > t.end)) && notValid == '-') {
                    // if this is the first loop that any loop after it will not run. 
                    notValid = t.var;
                }
                if(notValid != '-') continue;
                if(t.end == -1 && t.beg != -1) {
                    now++;
                }
            } else if(op[0] == 'E') {
                // ERR proccess
                if(sta.empty()) {
                    // if stack is empty when trying to proccess an 'E' command
                    iserr = true;
                    continue;
                }

                // non-ERR proccess
                if(iserr) continue;
                Loop t = sta.top();
                sta.pop();
                vis[t.var - 'a'] = false;
                if(t.var == notValid) {
                    notValid = '-';
                }
                if(notValid != '-') continue;
                all = std::max(all, now); // always update all complexity value
                if(t.end == -1 && t.beg != -1) {
                    now--;
                }
            }
        }
        if(!sta.empty()) {
            // if stack is still not empty when all commands are inputed
            iserr = true;
        }
        if(iserr) {
            printf("ERR\n");
        } else if(all == exp) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    }
    return 0;
}

总结

考场上可能是没考虑周全，思路也比较乱，导致写出来代码很乱而且只有90，没能A掉。是一个遗憾。这种大模拟，重要的就是给自己偷懒，把能复用的代码写函数，能包的包起来，并且思路清晰分模块编写就好。本以为再也不会碰到这种大模拟题了，CCF在搞啥啊orz

逛公园

一句话题意

给一个有向图，求从1到N点长度不超过最短路径+K的路径数量。

解法

30% K = 0

最短路计数。（模板题：洛谷P1144、洛谷P1608）
在SPFA求最短路的时候加一个cnt数据记录到某点最短路的数量。如果一个点的最短路被更新，cnt重置为1，否则如果找到另外一条最短路，对cnt加一。

100% 1 \leq N \leq 100000, 1 \leq M \leq 200000, 0 \leq K \leq 50

很容易设计一个DP状态为dp[u][k]表示u点比最短路长k的路径数量，而初始dp[1][0]为1。规定dis数组为1到每个点的最短路距离，对于u点的所有入边（入边长度为len）的起点v，转移如下
dp[u][k] = \sum dp[v][dis[u]-dis[v]+k-len]
如果用SPFA转移，要考虑转移的状态是否已经计算过。我们规定转移的顺序是优先转移dis小的点，因此我们要保持转移队列的优先级有序。
但如果这个转移可以从N点开始，在反图上转移就不存在上面的问题。这种方案我们可以采用记忆化搜索。这道题时限有3s，能够满足需要。
那么0边如何处理？记忆化搜索不需要管0边，但是如果搜索的过程中遇到了一个0环，那么这个环任意跑多少圈都是一条可取的路径，这种情况是无解的，因此要在搜索过程中记录下搜索状态(u, k)是否已经在搜索栈中，可以用vis数组来处理一下。如果在栈中，就说明存在0环。
另外有一个很玄学的问题，搜索的最后要加一行dfs(N, K + 1);，否则就会有数据跑不过去，例如这一组数据

2 2 0 50
1 2 0
2 1 0

答案应该为-1，但是如果不加那一行答案就是1了。然而洛谷的数据好像不加那一行也能过，我不是很清楚原理是啥。

代码

// Code by KSkun, 2018/1
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>

struct io {
    char buf[1 << 26], *s;

    io() {
        fread(s = buf, 1, 1 << 26, stdin);
    }

    inline int read() {
        register int res = 0, neg = 1;
        while(*s < '0' || *s > '9') {
            if(*s == '-') neg = -1;
            s++; 
        } 
        while(*s >= '0' && *s <= '9') res = res * 10 + *s++ - '0';
        return res * neg;
    }
};

io ip;

#define read ip.read 

struct Edge {
    int to, w;
    Edge(int to, int w): to(to), w(w) {}
};

std::vector<Edge> vec[100005], rev[100005];

inline void addedge(int u, int v, int w) {
    vec[u].push_back(Edge(v, w));
    rev[v].push_back(Edge(u, w));
} 

int T, N, M, K, P, ut, vt, wt, dis[100005], dp[100005][55], ans;
bool vis[100005][55], zcircle;

std::queue<int> que;
bool inque[100005];

inline void spfa(int st) {
    memset(dis, 0x3f, sizeof dis);
    memset(inque, 0, sizeof inque);
    que.push(st);
    dis[st] = 0;
    inque[st] = true;
    while(!que.empty()) {
        int u = que.front();
        que.pop();
        inque[u] = false;
        for(int i = 0; i < vec[u].size(); i++) {
            int v = vec[u][i].to;
            if(dis[v] > dis[u] + vec[u][i].w) {
                dis[v] = dis[u] + vec[u][i].w;
                if(!inque[v]) {
                    inque[v] = true;
                    que.push(v);
                }
            } 
        } 
    }
}

inline int dfs(int u, int k) {
    //printf("u %d k %d\n", u, k);
    if(vis[u][k]) {
        zcircle = true;
        return -1;
    }
    if(dp[u][k] != -1) return dp[u][k];
    vis[u][k] = true;
    dp[u][k] = 0;
    for(int i = 0; i < rev[u].size(); i++) {
        int v = rev[u][i].to;
        int delta = dis[u] - dis[v] + k - rev[u][i].w;
        //printf("  v %d delta %d\n", v, delta);
        if(delta < 0) continue;
        dp[u][k] = (0ll + dp[u][k] + dfs(v, delta)) % P;
        if(zcircle) return -1;
    }
    vis[u][k] = false;
    return dp[u][k];
}

int main() {
    T = read();
    while(T--) {
        memset(dp, -1, sizeof dp);
        memset(vis, 0, sizeof vis);
        zcircle = false;
        ans = 0;
        N = read();
        M = read();
        K = read();
        P = read();
        for(int i = 1; i <= N; i++) {
            vec[i].clear();
            rev[i].clear();
        }
        for(int i = 0; i < M; i++) {
            ut = read();
            vt = read();
            wt = read();
            addedge(ut, vt, wt);
        }
        spfa(1);
        dp[1][0] = 1;
        for(int i = 0; i <= K; i++) {
            ans = (0ll + ans + dfs(N, i)) % P;
        }
        dfs(N, K + 1);
        if(zcircle) {
            printf("-1\n");
        } else {
            printf("%d\n", ans);
        }
    }
    return 0;
}

总结

图论+DP的写法是第一次碰到，最短路计数的骗分也不会写，NOIP之前的我果然是个鶸。

NOIP2017 提高组 Day2

吐槽

第一次碰到纯粹的数据结构题，第一次碰到这么难的DP。

个人成绩

100，20，30

题目列表（评测来自洛谷）

赛题 #A: P3958 奶酪 | BFS，并查集
赛题 #B: P3959 宝藏 | 状压DP，记忆化搜索
赛题 #C: P3960 列队 | 数据结构，线段树，平衡树

奶酪

一句话题意

给一堆球体，有两个平行于xOy坐标平面的平面作为底面（z=0）和顶面（z=h），两个相交或者相切的球体可以视作联通，求是否能找到一条路径从底面到顶面去。

解法

100% 1 \leq N \leq 1000

建图BFS或者并查集检查是否有底面-顶面球体对在同一集合内都可以解决这个问题。题目本身并不难，而且默认了z坐标为正也不会爆long long。

代码

// Code by KSkun, 2018/1
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>

struct Ball {
    int x, y, z;
    Ball(int x, int y, int z): x(x), y(y), z(z) {}
};

std::vector<Ball> balls;
std::vector<int> vec[1005];
std::queue<int> que;
bool top[1005], success, vis[1005];
int T, n, h, r, x, y, z;

inline long long dis(int a, int b) {
    long long x = 1ll * (balls[a].x - balls[b].x) * (balls[a].x - balls[b].x),
        y = 1ll * (balls[a].y - balls[b].y) * (balls[a].y - balls[b].y),
        z = 1ll * (balls[a].z - balls[b].z) * (balls[a].z - balls[b].z);
    return x + y + z;
}

inline bool can(int a, int b) {
    return dis(a, b) <= 1ll * r * r * 4;
}

int main() {
    scanf("%d", &T);
    while(T--) {
        success = false;
        while(!que.empty()) que.pop();
        memset(top, 0, sizeof top);
        memset(vis, 0, sizeof vis);
        balls.clear();
        scanf("%d%d%d", &n, &h, &r);
        for(int i = 1; i <= n; i++) {
            vec[i].clear();
        }
        for(int i = 1; i <= n; i++) {
            scanf("%d%d%d", &x, &y, &z);
            balls.push_back(Ball(x, y, z));
            if(std::abs(h - z) <= r) top[i] = true;
            if(std::abs(z) <= r) que.push(i);
            for(int j = 0; j < balls.size() - 1; j++) {
                if(can(i - 1, j)) {
                    vec[i].push_back(j + 1);
                    vec[j + 1].push_back(i);
                }
            }
        }
        // BFS
        while(!que.empty()) {
            int u = que.front();
            que.pop();
            if(top[u]) {
                success = true;
                break;
            }
            vis[u] = true;
            for(int i = 0; i < vec[u].size(); i++) {
                int v = vec[u][i];
                if(!vis[v]) {
                    que.push(v);
                }
            }
        } 
        if(success) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    }
    return 0;
} 

感想

当时写的时候还在纠结是不是要爆ll，然后开了ull。后来发现我多虑了。好多人都栽在这个题上。我当时写的大常数BFS是能在老爷机上A了的，所以并不清楚发生了什么。

宝藏

一句话题意

给一个无向图，让你找一个最小生成树，生成树的每条边产生Z \times W的代价，其中Z是该边起点到指定根的距离（每条边长度为1），W是边本来的权值。

解法

100% 1 \leq n \leq 12, 0 \leq m \leq 1000

考虑使用dis数组记录每个点到指定根的距离，然后设计状压DP，dp[S]表示已经加入生成树的点为S的时候的最佳方案。
转移直接使用搜索即可。对于集合S中的每一个点尝试转移到它们的下层点。如果发现下层点的状态方案不是最优，则更新最优并搜索下去，否则回溯。
然后枚举指定根，每一次都搜一遍。
代码相当短，题目本身也并不是很难，就是一个大暴力。

代码

// Code by KSkun, 2018/1
#include <cstdio>
#include <cstring>
#include <algorithm>

const int INF = 0x3f3f3f3f;

int n, m, gra[15][15], dis[15], dp[1 << 13], ans = INF, ut, vt, wt;

inline int dfs(int s) {
    for(int i = 1; i <= n; i++) {
        // if the point has been chosen
        if(s & (1 << (i - 1))) {
            for(int j = 1; j <= n; j++) {
                // if the goal is reachable and hasn't been chosen
                if(!(s & (1 << (j - 1))) && gra[i][j] != INF) {
                    // if there is a better solution
                    if(dp[s | 1 << (j - 1)] > dp[s] + dis[i] * gra[i][j]) {
                        int lst = dis[j];
                        dis[j] = dis[i] + 1;
                        dp[s | 1 << (j - 1)] = dp[s] + dis[i] * gra[i][j];
                        dfs(s | 1 << (j - 1));
                        dis[j] = lst;
                    }
                }
            }
        }
    }
}

int main() {
    memset(gra, 0x3f, sizeof gra);
    memset(dis, 0x3f, sizeof dis);
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; i++) {
        scanf("%d%d%d", &ut, &vt, &wt);
        gra[ut][vt] = gra[vt][ut] = std::min(gra[ut][vt], wt);
    }
    // choose who is the root
    for(int i = 1; i <= n; i++) {
        memset(dis, 0x3f, sizeof dis);
        memset(dp, 0x3f, sizeof dp);
        dis[i] = 1;
        dp[1 << (i - 1)] = 0;
        dfs(1 << (i - 1));
        ans = std::min(ans, dp[(1 << n) - 1]);
    }
    printf("%d", ans);
    return 0;
}

感想

考场上在想为什么今天还没出DP题以及这题怎么看怎么像生成树，然后疯狂想办法证贪心，然后GG。考完试一个华一大佬告诉我就是个贪心生成树，然后他也GG了，233。

列队

一句话题意

有一个n \times m的矩阵，每次从(x, y)拿出一个数并且删掉它，然后左对齐、上对齐，再把拿出的这个数插入(n, m)位置。给定很多(x, y)，每次求拿出的那个数是什么。

解法

30% n = 1

其实我们发现我们可以用一个长为m+q的线段树来维护这个序列。当每一次删点的时候记录哪些区间的子树里删了这个点，就可以统计出一个该区间内总共删掉的点数，然后每次查找第几个元素的时候以此为参考到它的左子树or右子树查找。至于多出来的那些个可能乱序的元素，就直接扔进vector然后如果要找就算一下下标。

100% 1 \leq n, m, q \leq 3 \times 10^5

对30%的做法进行延伸，我们可以发现，这个题需要n+1棵线段树，对应n行的前m-1个元素和最后一列，每一次在该行中删除一个元素，然后在最后一列中删一个元素加入该行，再往最后一列中加入一个元素。这样一来，思路就很明确了。

代码

// Code by KSkun, 2018/1
#include <cstdio>
#include <algorithm>
#include <vector>

struct io {
    char buf[1 << 26], *s;

    io() {
        //freopen("p3960-13.in", "r", stdin);
        //freopen("p3960-13.out", "w", stdout);
        fread(s = buf, 1, 1 << 26, stdin);
    }

    inline int read() {
        register int res = 0, neg = 1;
        while(*s < '0' || *s > '9') {
            if(*s == '-') neg = -1;
            s++; 
        } 
        while(*s >= '0' && *s <= '9') res = res * 10 + *s++ - '0';
        return res * neg;
    }
};

io ip;

#define read ip.read 

int n, m, q, x, y, N;
int lc[10000005], rc[10000005], del[10000005], root[300005], tot = 0;
std::vector<long long> vec[300005];

inline long long query(int o, int l, int r, int rnk) {
    if(l == r) return l;
    // res stands for how many points left subtree has
    int mid = (l + r) >> 1, res = mid - l + 1 - del[lc[o]];
    if(res >= rnk) return query(lc[o], l, mid, rnk);
    else return query(rc[o], mid + 1, r, rnk - res);
}

inline void update(int &o, int l, int r, int rnk) {
    if(!o) o = ++tot;
    del[o]++;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(mid >= rnk) update(lc[o], l, mid, rnk);
    else update(rc[o], mid + 1, r, rnk);
}

inline long long del_line(int x, int y) {
    long long res = query(root[x], 1, N, y);
    update(root[x], 1, N, res);
    return res < m ? 1ll * (x - 1) * m + res : vec[x][res - m];
}

inline long long del_row(int x) {
    long long res = query(root[n + 1], 1, N, x);
    update(root[n + 1], 1, N, res);
    return res <= n ? 1ll * res * m : vec[n + 1][res - n - 1];
}

int main() {
    n = read();
    m = read();
    q = read();
    N = std::max(n, m) + q;
    while(q--) {
        x = read();
        y = read();
        if(y != m) {
            long long res = del_line(x, y);
            vec[n + 1].push_back(res);
            printf("%lld\n", res);
            vec[x].push_back(del_row(x));
        } else {
            long long res = del_row(x);
            vec[n + 1].push_back(res);
            printf("%lld\n", res);
        }
    }
    return 0;
}

感想

从来没写过纯粹的数据结构题的我在考场上就是懵逼的qwq