[NOI 2014]做题记录

【NOI2014】起床困难综合症

按位贪心

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#define maxn 100010

using namespace std;

int n, m;

int tp[maxn], v[maxn];

int getans(int final, int p){

	for(int i = 1; i <= n; i ++){

		if(tp[i] == 0)final &= v[i];

		if(tp[i] == 1)final |= v[i];

		if(tp[i] == 2)final ^= v[i];

	}return final >> p & 1;

}

bool check(int x){

	if(getans(0, x) >= getans(1 << x, x))

		return 0;

	return 1;

}

int solve(int final){

    for(int i = 1; i <= n; i ++){

		if(tp[i] == 0)final &= v[i];

		if(tp[i] == 1)final |= v[i];

		if(tp[i] == 2)final ^= v[i];

	}return final;

}

int main(){

	scanf("%d%d", &n, &m);

	char cmd[5]; int x;

	for(int i = 1; i <= n; i ++){

		scanf("%s%d", cmd, &x);

		if(cmd[0] == 'A')tp[i] = 0;

		if(cmd[0] == 'O')tp[i] = 1;

		if(cmd[0] == 'X')tp[i] = 2;

		v[i] = x;

	}

	int log = 1;

	for(; 1ll << log <= m; log ++);log --;

	int ans = 0;

	for(int i = log; i >= 0; i --)

		if((ans | (1 << i)) <= m && check(i))

			ans = ans | (1 << i);

	printf("%d\n", solve(ans));

	return 0;

}

【NOI2014】魔法森林

最小增量生成树

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#define maxn 200010

using namespace std;

int n, m;

struct Edge_{

    int u, v, a, b;

    void read(){scanf("%d%d%d%d", &u, &v, &a, &b);}

    bool operator<(const Edge_& k)const{

        return a < k.a;

    }

}G[maxn];

int L[maxn], R[maxn];

int val[maxn], c[maxn][2], fa[maxn], pos[maxn];

bool rev[maxn];

namespace Splay{

    #define l c[x][0]

    #define r c[x][1]

    int st[maxn], top;

    void init(){

        memset(val, 0x80, sizeof val);

        for(int i = 1; i <= 2 * n; i ++)

            pos[i] = i;

    }

    void pushup(int x){

        pos[x] = x;

        if(val[pos[x]] < val[pos[l]])

            pos[x] = pos[l];

        if(val[pos[x]] < val[pos[r]])

            pos[x] = pos[r];

    }

    void pushdown(int x){

        if(rev[x]){

            rev[x] = 0;

            rev[l] ^= 1;

            rev[r] ^= 1;

            swap(l, r);

        }

    }

    void rotate(int p, int x){

        int mark = p == c[x][1], y = c[p][mark ^ 1];

        int z = fa[x];

        if(x == c[z][0])c[z][0] = p;

        if(x == c[z][1])c[z][1] = p;

        if(y)fa[y] = x;

        fa[p] = z; c[p][mark ^ 1] = x;

        fa[x] = p; c[x][mark] = y;

        pushup(x);

    }

    bool isroot(int p){

        return c[fa[p]][0] != p && c[fa[p]][1] != p;

    }

    void splay(int p){

        st[top = 1] = p;

        for(int i = p; !isroot(i); i = fa[i])

            st[++ top] = fa[i];

        for(;top; top --)

            pushdown(st[top]);

        while(!isroot(p)){

            int x = fa[p], y = fa[x];

            if(isroot(x))rotate(p, x);

            else if(p == c[x][0] ^ x == c[y][0])

                rotate(p, x), rotate(p, y);

            else rotate(x, y), rotate(p, x);

        }

        pushup(p);

    }

    #undef l

    #undef r

}

namespace LCT{

    void Access(int u){

        int t = 0;

        while(u){

            Splay::splay(u);

            c[u][1] = t;

            t = u;

            u = fa[u];

        }

    }

    void Evert(int u){

        Access(u);

        Splay::splay(u);

        rev[u] ^= 1;

    }

    void link(int u, int v, int t){

        Evert(v);

        fa[v] = t;

        Evert(t);

        fa[t] = u;

    }

    void cut(int u, int v, int t){

        Evert(t);

        Access(u);

        Splay::splay(u);

        c[u][0] = fa[t] = 0;

        Evert(t);

        Access(v);

        Splay::splay(v);

        c[v][0] = fa[t] = 0;

    }

    int find(int u){

        Access(u);

        Splay::splay(u);

        while(c[u][0])u = c[u][0];

        return u;

    }

    int ask(int u, int v){

        if(find(u) != find(v))

            return -1;

        Evert(u);

        Access(v);

        Splay::splay(v);

        return pos[v];

    }

}

int main(){

    scanf("%d%d", &n, &m);

    for(int i = 1; i <= m; i ++)

        G[i].read();

    sort(G + 1, G + 1 + m);

    Splay::init();

    int ans = 0x7fffffff;

    int cnt = n;

    for(int i = 1; i <= m; i ++){

        int t = LCT::ask(G[i].u, G[i].v);

        if(t == -1){

            t = ++ cnt;

            L[t] = G[i].u;

            R[t] = G[i].v;

            val[t] = G[i].b;

            fa[t] = c[t][0] = c[t][1] = 0;

            pos[t] = t;

            LCT::link(L[t], R[t], t);

        }

        else if(val[t] > G[i].b){

            LCT::cut(L[t], R[t], t);

            L[t] = G[i].u;

            R[t] = G[i].v;

            val[t] = G[i].b;

            fa[t] = c[t][0] = c[t][1] = 0;

            pos[t] = t;

            LCT::link(L[t], R[t], t);

        }

        t = LCT::ask(1, n);

        if(t != -1)

            ans = min(ans, val[t] + G[i].a);

        //cout << ans << ' ' << val[t] << ' ' << G[i].a << ' ' << G[i].b << endl;

    }

    if(ans > 1000000)

        ans = -1;

    printf("%d\n", ans);

    return 0;

}

【NOI2014】动物园

KMP

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define maxn 1000010

#define mod 1000000007ll

using namespace std;

int nxt[maxn], n;

char c[maxn];

int p[maxn];

long long ans;

void solve(){

	p[1] = 1;

	nxt[0] = nxt[1] = 0;

	for(int i = 2; i <= n; i ++){

		int j = nxt[i - 1];

		while(j && c[i] != c[j + 1])j = nxt[j];

		if(c[i] == c[j + 1])j ++;

		nxt[i] = j;

		p[i] = p[j] + 1;

	}

	int j = 0;

	ans = 1;

	for(int i = 2; i <= n; i ++){

		while(j && c[i] != c[j + 1])j = nxt[j];

		if(c[i] == c[j + 1])j ++;

		while(j * 2 > i)j = nxt[j];

		ans = 1ll * (p[j] + 1) * ans % mod;

	}

	printf("%lld\n", ans);

}

int main(){

	int test;

	scanf("%d", &test);

	while(test --){

		scanf("%s", c + 1);

		n = strlen(c + 1);

		solve();

	}

	return 0;

}

【NOI2014】随机数生成器

把序列搞出来每次取最小值看是否可以添加进去

每一行可取的范围是连续的，维护Li和Ri就可以判定

#include <algorithm>

#include <stdio.h>

typedef long long ll;

int x0, a, b, c, d;

int n, m, q;

int T[25000001], mp[5001][5001];

int l[5001], r[5001];

int Rand(){

	x0 = ((ll)a * x0 * x0 % d + (ll)b * x0 + c) % d;

	return x0;

}

int main(){

	scanf("%d%d%d%d%d", &x0, &a, &b, &c, &d);

	scanf("%d%d%d", &n, &m, &q);

	int k = n * m;

	for(int i = 1; i <= k; i ++)

	    T[i] = i;

	for(int i = 1; i <= k; i ++)

	    std::swap(T[i], T[Rand() % i + 1]);

	int x, y;

	for(int i = 1; i <= q; i ++)

	    scanf("%d%d", &x, &y), std::swap(T[x], T[y]);

	int nw = 0;

	for(int i = 1; i <= n; i ++)

	    for(int j = 1; j <= m; j ++)

	        mp[i][j] = T[++ nw];

	for(int i = 1; i <= n; i ++)

	    for(int j = 1; j <= m; j ++)

	        T[mp[i][j]] = i << 16 | j;

	for(int i = 1; i <= n; i ++)

	    l[i] = 1, r[i] = m;

	bool flag = false;

	for(int i = 1; i <= k; i ++){

		x = T[i] >> 16;

		y = T[i] & 65535;

		if(l[x] <= y && y <= r[x]){

			if(flag)putchar(' ');

			flag = true;

			printf("%d", i);

			for(int j = 1; j < x; j ++)r[j] = std::min(r[j], y);

			for(int j = x + 1; j <= n; j ++)l[j] = std::max(l[j], y);

		}

	}

	return 0;

}

【NOI2014】购票

树剖+三分

long long 乘 long long乘爆了。。

改成double才过

凸包不要建错

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <vector>

#define maxn 200010

using namespace std;

typedef long long ll;

int n;

struct Edge{

	int to, nxt;

	ll dis;

}edge[maxn];

int h[maxn], cnt;

void add(int u, int v, ll d){

	edge[++ cnt] = (Edge){v, h[u], d};

	h[u] = cnt;

}

const ll inf = 1ll << 60;

const int root = 1;

ll p[maxn], q[maxn], L[maxn], dis[maxn], dp[maxn];

int fa[maxn], anc[maxn][20];

int top[maxn], son[maxn], pos[maxn], size[maxn], dfs_clock;

void dfs1(int u){

	size[u] = 1;

	for(int i = h[u]; i; i = edge[i].nxt){

		int v = edge[i].to;

		if(v == fa[u])continue;

		anc[v][0] = fa[v] = u;

		dis[v] = dis[u] + edge[i].dis;

		dfs1(v);

		size[u] += size[v];

		if(size[v] > size[son[u]])

		    son[u] = v;

	}

}

void dfs2(int u, int tp){

	pos[u] = ++ dfs_clock;

	top[u] = tp;

	if(son[u])dfs2(son[u], tp);

	for(int i = h[u]; i; i = edge[i].nxt){

		int v = edge[i].to;

		if(v == fa[u] || v == son[u])continue;

		dfs2(v, v);

	}

}

int Find(int u, ll d){

	for(int i = 18; i >= 0; i --)

	    if(dis[anc[u][i]] >= d)

	        u = anc[u][i];

	return u;

}

#define lc id << 1

#define rc id << 1 | 1

vector<int> t[maxn << 2];

void update(int id, int l, int r, int u){

	int top = t[id].size() - 1;

	while(top > 0){

		int t1 = t[id][top], t2 = t[id][top - 1];

		if((double)(dp[u] - dp[t1]) / (dis[u] - dis[t1]) < (double)(dp[u] - dp[t2]) / (dis[u] - dis[t2]))

	    	top --, t[id].pop_back();

		else break;

	}

	t[id].push_back(u);

	if(l == r)return;

	int mid = l + r >> 1;

	if(pos[u] <= mid)update(lc, l, mid, u);

	else update(rc, mid+1, r, u);

}

ll pd(int i, int u){return dp[i] + (dis[u] - dis[i]) * p[u] + q[u];}

ll check(int id, int u){

	int l = 0, r = t[id].size() - 1;

	ll ret = inf;

	while(r - l >= 3){

		int m1 = (l + l + r) / 3, m2 = (l + r + r) / 3;

		if(pd(t[id][m1], u) > pd(t[id][m2], u))

		    l = m1;

		else r = m2;

	}

	for(int i = l; i <= r; i ++)

	    ret = min(ret, pd(t[id][i], u));

	return ret;

}

ll ask(int id, int l, int r, int L, int R, int u){

	if(l == L && r == R)return check(id, u);

	int mid = l + r >> 1;

	if(R <= mid)return ask(lc, l, mid, L, R, u);

	if(L > mid) return ask(rc, mid+1, r, L, R, u);

	return min(ask(lc, l, mid, L, mid, u), ask(rc, mid+1, r, mid+1, R, u));

}

ll query(int u){

	ll d = dis[u] - L[u], ret = inf;

	int nw = u; u = fa[u];

	while(u){

		if(dis[u] < d)break;

		int l = pos[top[u]], r = pos[u];

		if(dis[top[u]] < d)l = pos[Find(u, d)];

		ret = min(ret, ask(1, 1, n, l, r, nw));

		u = fa[top[u]];

	}return ret;

}

void solve(int u){

	if(u != 1)dp[u] = query(u);

	update(1, 1, n, u);

	for(int i = h[u]; i; i = edge[i].nxt){

		int v = edge[i].to;

		if(v == fa[u])continue;

		solve(v);

	}

}

int main(){

	int test;

	scanf("%d%d", &n, &test);

	int f; ll s;

	for(int i = 2; i <= n; i ++){

		scanf("%d%lld%lld%lld%lld", &f, &s, &p[i], &q[i], &L[i]);

		add(f, i, s);

	}

	dfs1(root);

	dfs2(root, root);

	for(int j = 1; 1 << j <= n; j ++)

		for(int i = 1; i <= n; i ++)

		    anc[i][j] = anc[anc[i][j-1]][j-1];

	solve(root);

	for(int i = 2; i <= n; i ++)

	    printf("%lld\n", dp[i]);

	return 0;

}