noip刷题记录 20170818

天天爱跑步

lca + 树上差分

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;

const int N = 3e5 + 5, M = 3e5 + 5;
int n, m, ans[N], offset;
int ecnt, adj[N], go[M << 1], nxt[M << 1];
int w[N], dep[N], cnt[N << 2], fa[N][25];
struct node{
    int val, delta;
    node(){}
    node(int a, int b):val(a), delta(b){}
}; 
vector<node> tag[N];

inline void addEdge(int u, int v){
    nxt[++ecnt] = adj[u], adj[u] = ecnt, go[ecnt] = v;
    nxt[++ecnt] = adj[v], adj[v] = ecnt, go[ecnt] = u;
}

inline int getLca(int u, int v){
    if(dep[u] < dep[v]) swap(u, v);
    int delta = dep[u] - dep[v];
    for(int i = 20; i >= 0; i--)
        if((1 << i) & delta) u = fa[u][i];
    if(u == v) return u;
    for(int i = 20; i >= 0; i--)
        if(fa[u][i] != fa[v][i]) 
            u = fa[u][i], v = fa[v][i];
    return fa[u][0];
}

inline void dfs(int u, int f){
    fa[u][0] = f;
    for(int i = 1; i <= 20; i++)
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for(int e = adj[u], v; e; e = nxt[e]){
        v = go[e];
        if(v != f){
            dep[v] = dep[u] + 1;
            dfs(v, u);
        }
    }
}

inline void solve(int u){
    int cur = cnt[dep[u] + w[u]] + cnt[w[u] - dep[u] + offset];
    for(int i = 0; i < tag[u].size(); i++)
        cnt[tag[u][i].val] += tag[u][i].delta;
    for(int e = adj[u], v; e; e = nxt[e]){
        if((v = go[e]) == fa[u][0]) continue;
        solve(v);
    }
    ans[u] = cnt[dep[u] + w[u]] + cnt[w[u] - dep[u] + offset] - cur;
}

inline int read(){
    int i = 0, f = 1; char ch = getchar();
    for(; (ch < '0' || ch > '9') && ch != '-'; ch = getchar());
    if(ch == '-') f = -1, ch = getchar();
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        i = (i << 3) + (i << 1) + (ch - '0');
    return i * f;
}

inline void wr(int x){
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) wr(x / 10);
    putchar(x % 10 + '0');
}

int main(){
    n = read(), m = read(), offset = 3 * n + 1; 
    for(int i = 1; i < n; i++){
        int x = read(), y = read();
        addEdge(x, y);
    }
    dfs(1, 0);
    for(int i = 1; i <= n; i++) w[i] = read();
    for(int i = 1; i <= m; i++){
        int s = read(), t = read(), lca = getLca(s, t);
        tag[s].push_back(node(dep[s], 1));
        tag[t].push_back(node(dep[s] - 2 * dep[lca] + offset, 1));
        tag[fa[lca][0]].push_back(node(dep[s], -1));
        tag[lca].push_back(node(dep[s] - 2 * dep[lca] + offset, -1));
    }
    solve(1);
    for(int i = 1; i <= n; i++) wr(ans[i]), putchar(' ');
    return 0;
}

借教室

二分法

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;

const int N = 1e6 + 5;
int n, m, a[N], f[N], s[N], t[N], d[N], ans;

inline int read(){
    int i = 0, f = 1; char ch = getchar();
    for(; (ch < '0' || ch > '9') && ch != '-'; ch = getchar());
    if(ch == '-') f = -1, ch = getchar();
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        i = (i << 3) + (i << 1) + (ch - '0');
    return i * f;
}

inline void wr(int x){
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) wr(x / 10);
    putchar(x % 10 + '0');
}

inline bool check(int mid){
    int sum = 0;
    memset(f, 0, sizeof f);
    for(int i = 1; i <= mid; i++)
        f[s[i]] += d[i], f[t[i] + 1] -= d[i];
    for(int i = 1; i <= n; i++){
        sum += f[i];
        if(sum > a[i]) return false;
    }
    return true;
}

int main(){
    n = read(), m = read();
    for(int i = 1; i <= n; i++) a[i] = read();
    for(int i = 1; i <= m; i++) d[i] = read(), s[i] = read(), t[i] = read();
    int l = 1, r = m; 
    while(l <= r){
        int mid = l + r >> 1;
        if(check(mid)) l = mid + 1;
        else ans = mid, r = mid - 1;
    }
    if(ans == 0) putchar('0');
    else{
        wr(-1), putchar('
');
        wr(ans);
    }
    return 0;
}

线段树

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;

const int N = 1e6 + 5, oo = 0x3f3f3f3f;
int n, m, minn[N * 4], a[N], tag[N * 4];

inline int read(){
    int i = 0, f = 1; char ch = getchar();
    for(; (ch < '0' || ch > '9') && ch != '-'; ch = getchar());
    if(ch == '-') f = -1, ch = getchar();
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        i = (i << 3) + (i << 1) + (ch - '0');
    return i * f;
}

inline void wr(int x){
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) wr(x / 10);
    putchar(x % 10 + '0');
}

inline void build(int k, int l, int r){
    if(l == r){
        minn[k] = a[l];
        return;
    }
    int mid = l + r >> 1, lc = k << 1, rc = k << 1 | 1;
    build(lc, l, mid);
    build(rc, mid + 1, r);
    minn[k] = min(minn[lc], minn[rc]);
}

inline void minuss(int k, int v){
    minn[k] -= v;
    tag[k] += v;
}

inline void pushDown(int k){
    if(tag[k]){
        if(minn[k << 1] != -1) minuss(k << 1, tag[k]);
        if(minn[k << 1 | 1] != -1) minuss(k << 1 | 1, tag[k]);
        tag[k] = 0;
    }
}


inline void modify(int k, int l, int r, int x, int y, int v){
    if(x <= l && r <= y){
        minuss(k, v);
        return;
    }
    pushDown(k);
    int mid = l + r >> 1, lc = k << 1, rc = k << 1 | 1, ret = oo;
    if(x <= mid) modify(lc, l, mid, x, y, v);
    if(y > mid) modify(rc, mid + 1, r, x, y, v);
    minn[k] = min(minn[lc], minn[rc]);
}

inline int query(int k, int l, int r, int x, int y){
    if(x <= l && r <= y) return minn[k];
    pushDown(k);
    int mid = l + r >> 1, lc = k << 1, rc = k << 1 | 1, ret = oo;
    if(x <= mid) ret = min(ret, query(lc, l, mid, x, y));
    if(y > mid) ret = min(ret, query(rc, mid + 1, r, x, y));
    return ret;
}

int main(){
    n = read(), m = read();
    for(int i = 1; i <= n; i++) a[i] = read();
    memset(minn, -1, sizeof tag);
    build(1, 1, n); 
    for(int i = 1; i <= m; i++){
        int d = read(), s = read(), t = read();
        if(s > t) swap(s, t);
//        cout<<s<<" "<<t<<" "<<query(1, 1, n, s, t)<<"!!!"<<endl;
        if(query(1, 1, n, s, t) < d){
            wr(-1), putchar('
'), wr(i);
            return 0;
        }
        modify(1, 1, n, s, t, d);
    }
    wr(0);
    return 0;
}

积木大赛

简单分析

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;

const int N = 1e5 + 5;
int n, ans, last;

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        int tmp; cin >> tmp;
        if(tmp - last > 0) ans += tmp - last;
        last = tmp;
    }
    cout << ans;
    return 0;
}

Vigenère密码

简单分析 + 模拟

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;

int klen, slen, key[1005];
char k[1005], s[1005], t[1005];

int main(){
    cin >> k >> s;
    klen = strlen(k), slen = strlen(s);
    for(int i = 0; i < klen; i++){
        if('a' <= k[i] && k[i] <= 'z')
            key[i] = k[i] - 'a';
        else key[i] = k[i] - 'A'; 
    }
    for(int i = 0; i < slen; i++){
        if('a' <= s[i] && s[i] <= 'z'){
            t[i] = s[i] - key[i % (klen)];
            while(t[i] < 'a') t[i] += 26;
        }
        else if('A' <= s[i] && s[i] <= 'Z'){
            t[i] = s[i] - key[i % (klen)];
            while(t[i] < 'A') t[i] += 26;
        }
        else continue;
        putchar(t[i]);
    }
    return 0;
}

花匠

动态规划 + 树状数组优化

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;

const int N = 1e5 + 5, H = 1e6 + 5;
int n, h[N], f[N], g[N], maxh, maxxF[H], maxxG[H], ans;

inline int read(){
    int i = 0, f = 1; char ch = getchar();
    for(; (ch < '0' || ch > '9') && ch != '-'; ch = getchar());
    if(ch == '-') f = -1, ch = getchar();
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        i = (i << 3) + (i << 1) + (ch - '0');
    return i * f;
}

inline void wr(int x){
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) wr(x / 10);
    putchar(x % 10 + '0');
}

inline void uptF(int x, int v){
    for(int i = x; i <= maxh; i += (i&(-i)))
        maxxF[i] = max(maxxF[i], v);
}

inline void uptG(int x, int v){
    for(int i = x; i <= maxh; i += (i&(-i)))
        maxxG[i] = max(maxxG[i], v);
}

inline int queryF(int x){
    int ret = 0;
    for(int i = x; i > 0; i-=(i&-i))
        ret = max(maxxF[i], ret);
    return ret;
}

inline int queryG(int x){
    int ret = 0;
    for(int i = x; i > 0; i-=(i&-i))
        ret = max(ret, maxxG[i]);
    return ret;
}

int main(){
    n = read();
    for(int i = 1; i <= n; i++) h[i] = read() + 1, maxh = max(maxh, h[i]);
    maxh += 5;
    for(int i = 1; i <= n; i++){
        f[i] = max(queryG(h[i] - 1) + 1, f[i]);
        g[i] = max(queryF(maxh - h[i] - 1) + 1, g[i]);
        uptF(maxh - h[i], f[i]);
        uptG(h[i], g[i]);
        ans = max(ans, max(f[i], g[i]));
    }
    wr(ans);
    return 0;
}