NOIp2017水题报告

//已经学了这么多月了 去年的题多少也会了一点 (虽然考了大概还是不会 NOIp2018day0补一波题解当攒rp了
小凯的疑惑
没啥好讲的。。。我智商不够不学小学奥数有点亏

时间复杂度
模拟推荐把各种操作分开写 能好看一点( 以及负数注意不要太小 不然会爆成正数(

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 201;
const int INF = 147483645;
string s;
bool err, used[N];
int t, n, ce, fzd, Fzd, ans;
struct node {
    int fzd, var;
}p[N];
inline int readFzd() {
    cin >> s; if(s[2] == '1') return 0;
    int x = 0; for(int i = 4; s[i] != ')'; ++ i) 
        x = x * 10 + s[i] - '0'; return x; 
}
inline int readvar() {
    cin >> s; if(used[s[0]]) err = 1;
    used[s[0]] = 1; return s[0];
}
inline int readnum() {
    cin >> s; if(s[0] == 'n') return INF;
    //cout << INF << "-=-=-" << endl;
    int x = 0, len = s.size(); 
    for(int i = 0; i < s.size(); ++ i)
        x = x * 10 + s[i] - '0';
    return x;
}
inline int readfzd() {
    int a = readnum(), b = readnum();
    //printf("-=-=-=--=%d=====%d\n", a, b);
    if(a != INF && b == INF) return 1;
    if(a > b) return -INF; return 0;
}
inline void work() {
    cin >> s; if(s[0] == 'F') {
        p[++ ce].var = readvar();
        ans = max(ans, (fzd += (p[ce].fzd = readfzd())));
        //cout << "-=-=-=-" << p[ce].fzd << endl;;
    } else {
        if(! ce) {err = 1; return ;}
        used[p[ce].var] = 0; fzd -= p[ce --].fzd;
    }
}
int main() {
    cin >> t;
    while(t --) {
        memset(used, 0, sizeof used);
        ans = fzd = ce = err = 0; cin >> n;
        Fzd = readFzd();  for(int i = 1; i <= n; ++ i) work();
        //printf("-=-=-%d===%d\n", Fzd, ans);
        puts((ce || err) ? ("ERR") : ((Fzd == ans) ? ("Yes") : "No"));
    }
    return 0;
}
/*
1
2 O(n^1)
F x 1 n
E
*/


逛公园
先bfs可行点 预处理最短路 剩下的记忆画搜索即可 这题实测spfa比dijk加stl堆优化快点

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 120000;
const int M = 220000;
const int INF = 2147483645;
bool flag[N], vis[N][60], inq[N];
int n, m, k, p, t, dis[N], dp[N][60];
int head[N], to[M], nex[M], val[M];
int Head[N], To[M], Nex[M], Val[M], ce;
inline void add(int u, int v, int w) {
    to[++ ce] = v, nex[ce] = head[u], head[u] = ce, val[ce] = w;
    To[   ce] = u, Nex[ce] = Head[v], Head[v] = ce, Val[ce] = w;
}
queue <int > q;
inline void bfs() {
    q.push(n); flag[n] = 1;
    while(! q.empty()) {
        int x = q.front(); q.pop();
        for(int i = Head[x]; i != -1; i = Nex[i]) {
            int v = To[i]; if(! flag[v]) flag[v] = 1, q.push(v);
        }
    }
}
priority_queue <pair <int, int> > Q;
inline void dijkstra() {
    Q.push(make_pair(0, 1));
    while(! Q.empty()) {
        int x = Q.top().second; Q.pop();
        if(inq[x]) continue; inq[x] = 1;
        for(int i = head[x]; i != -1; i = nex[i]) {
            int v = to[i], w = val[i];
            if(dis[x] + w < dis[v]) dis[v] = dis[x] + w, Q.push(make_pair(-dis[v], v));
        }
    }
}
inline int dfs(int x, int k) {
    if(k < 0) return 0;
    if(vis[x][k] == 1) return -INF;
    if(dp[x][k] != -1) return dp[x][k];
    vis[x][k] = 1; int now = 0; if(x == n) ++ now;
    for(int i = head[x]; i != -1; i = nex[i]) {
        if(flag[to[i]] == 0) continue;
        int v = to[i], w = val[i], l = dis[v] - dis[x];
        int tmp = dfs(v, k + l - w);
        if(tmp == -INF) return -INF;
        (now += tmp) %= p;
    } vis[x][k] = 0; dp[x][k] = now % p; return now;
}
inline void init() { ce = 0;
    for(int i = 1; i <= n; ++ i) 
        head[i] = Head[i] = -1, inq[i] = 0;
    for(int i = 1; i <= n; ++ i) {
        flag[i] = 0;
        for(int j = 0; j <= k; ++ j) 
            dp[i][j] = -1, vis[i][j] = 0;
    }
}
inline int read() {
    int x = 0; bool w = 0; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') w = 1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return w ? - x : x;
}
int main() {
    memset(dp, -1, sizeof dp);
    memset(head, -1, sizeof head);
    memset(Head, -1, sizeof Head);
    t = read(); while(t --) {
        n = read(), m = read(), k = read(), p = read();
        for(int i = 1; i <= m; ++ i) {
            int u = read(), v = read(), w = read();
            add(u, v, w);
        }
        for(int i = 2; i <= n; ++ i) dis[i] = INF;
        bfs(); dijkstra(); int ans = dfs(1, k);
        printf("%d\n", ans == -INF ? -1 : ans); init();
    }
    return 0;
}

奶酪
这个也比较简单 可以先把与上 下链接的存起来 然后单独判断 当然也可以先新建两个节点 分别连上面和下面的点 剩下的 dfs bfs 并查集均可 注意维护联通性要双向边

#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int N = 1201;
struct node {
    int x, y, z;
}a[N];
bool vis[N]; int n, h, r, t, S, T;
int ce, head[N], to[N * N], nex[N * N];
inline void add(int u, int v) {
    to[++ ce] = v, nex[ce] = head[u], head[u] = ce;
    to[++ ce] = u, nex[ce] = head[v], head[v] = ce;
}
inline void dfs(int x) {
    vis[x] = 1;
    for(int i = head[x]; i != -1; i = nex[i])
        if(! vis[to[i]]) dfs(to[i]);
}
inline void build(int u, int v) {
    if((a[v].x - a[u].x) * (a[v].x - a[u].x) + (a[v].y - a[u].y) * (a[v].y - a[u].y) + (a[v].z - a[u].z) * (a[v].z - a[u].z) <= 4 * r * r) add(u, v);
}
inline int read() {
    int x = 0; bool w = 0; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') w = 1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return w ? - x : x;
}
signed main() {
    t = read(); while(t --) { ce = 0;
        memset(vis, 0, sizeof vis);
        memset(head, -1, sizeof head);
        n = read(), h = read(), r = read();
        S = n + 1, T = S + 1;
        for(int i = 1; i <= n; ++ i) {
            a[i].x = read(), a[i].y = read(), a[i].z = read();
            if(a[i].z <= r) add(S, i);
            if(a[i].z >= h - r) add(T, i);
        } 
        for(int i = 1; i <= n; ++ i) 
        for(int j = 1; j <= n; ++ j)
            build(i, j); dfs(S);
        puts(vis[T] ? "Yes" : "No");
    }
    return 0;
}

宝藏
n很小 可以状压 枚举不用花钱的起点记忆化搜索即可 挺暴力的

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 14;
const int inf = 1061109567;
const int INF = 2147483645;
int n, m, ans, E;
int mp[N][N], dp[1 << 13], dis[N];
inline void add(int u, int v, int w) {
    mp[u][v] = mp[v][u] = min(mp[u][v], w);
}
inline void dfs(int x) {
    for(int i = 1; i <= n; ++ i) {
        if(! (x & (1 << (i - 1)))) continue;
        for(int j = 1; j <= n; ++ j) {
            if(mp[i][j] < inf && ! (x & (1 << (j - 1)))) 
            if(dp[1 << (j - 1) | x] > dp[x] + dis[i] * mp[i][j]) {
                int now = dis[j]; dis[j] = dis[i] + 1;
                dp[1 << (j - 1) | x] = dp[x] + dis[i] * mp[i][j];
                dfs(1 << (j - 1) | x); dis[j] = now;
            } 
        }
    }
}
inline int read() {
    int x = 0; bool w = 0; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') w = 1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return w ? - x : x;
}
int main() {
    n = read(), m = read(), E = (1 << n) - 1;
    memset(mp, 63, sizeof mp); ans = INF;
    for(int i = 1; i <= m; ++ i) {
        int u = read(), v = read(), w = read();
        add(u, v, w);
    }
    for(int i = 1; i <= n; ++ i) {
        memset(dis, 63, sizeof dis);
        for(int j = 1; j <= E; ++ j) dp[j] = INF;
        dis[i] = 1; dp[1 << (i - 1)] = 0;
        dfs(1 << (i - 1)); ans = min(ans, dp[E]);
    } printf("%d", ans);
    return 0;
}

列队
用数据结构维护每行的前m-1个学生的编号 和最后一列的n个学生的编号 节点维护区间 学了一发fhq的这种操作 考场上估计还是会想写线段树的吧(

#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int N = 320000;
int n, m, ce, T, rt[N];
struct node {
    int l, r, sz, ls, rs, key;
}t[N * 20];
#define Ll t[rt].l
#define Rr t[rt].r
#define Ls t[rt].ls
#define Rs t[rt].rs
inline void pushup(int rt) {
    t[rt].sz = Rr - Ll + 1 + t[Ls].sz + t[Rs].sz;
}
inline int newnode(int l, int r) {
    t[++ ce].key = rand() % 2147483647;
    t[ce].l = l, t[ce].r = r, t[ce].sz = r - l + 1;
    t[ce].ls = t[ce].rs = 0; return ce;
}
inline void merge(int & rt, int a, int b) {
    if(! a || ! b) {rt = a + b; return;}
    (t[a].key < t[b].key) ? (rt = a, merge(Rs, Rs, b)) : (rt = b, merge(Ls, a, Ls)); 
    pushup(rt);
}
inline void Split(int rt, int k) {
    if(k >= Rr - Ll + 1) return ;
    int R = t[rt].l + k - 1, Rt = newnode(R + 1, t[rt].r);
    t[rt].r = R; merge(Rs, Rt, Rs); pushup(rt);
}
inline void split(int rt, int & a, int & b, int k) {
    if(! rt) {a = b = 0; return ;}
    if(t[Ls].sz >= k) b = rt, split(Ls, a, Ls, k);
    else Split(rt, k - t[Ls].sz), a = rt, split(Rs, Rs, b, k - t[Ls].sz - (Rr - Ll + 1));
    pushup(rt);
}
inline int read() {
    int x = 0; bool w = 0; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') w = 1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return w ? - x : x;
}
signed main() {
    srand(19260817); 
    n = read(), m = read(), T = read(); int nn = n + 1;
    for(int i = 1; i <= n; ++ i)
        rt[i] = newnode((i - 1) * m + 1, i * m - 1);
    for(int i = 1; i <= n; ++ i) 
        merge(rt[nn], rt[nn], newnode(i * m, i * m));
    while(T --) {
        int a = read(), b = read();
        if(b == m) {
            int x, y, z;
            split(rt[nn], x, y, a);
            split(x, x, z, a - 1);
            printf("%lld\n", t[z].l);
            merge(y, y, z); merge(rt[nn], x, y);
        } else {
            int x, y, z, X, Y, Z;
            split(rt[a], x, y, b);
            split(x, x, z, b - 1);
            printf("%lld\n", t[z].l);
            split(rt[nn], X, Y, a);
            split(X, X, Z, a - 1);
            merge(y, y, Z); merge(rt[a], x, y);
            merge(Y, Y, z); merge(rt[nn], X, Y);
        }
    }
    return 0;
}

如果。。。今年画风依旧清新就好了吧(

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注