【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
", 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
", 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
", 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
", dp[i]);
return 0;
}