[SDOI2014]数表 题解
题目地址:洛谷:【P3312】[SDOI2014]数表 – 洛谷、BZOJ:P …
May all the beauty be blessed.
题目地址:洛谷:【P3313】[SDOI2014]旅行 – 洛谷、BZOJ:Problem 3531. — [Sdoi2014]旅行
S国有N个城市,编号从1到N。城市间用N-1条双向道路连接,满足从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教,如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。
为了方便,我们用不同的正整数代表各种宗教, S国的居民常常旅行。旅行时他们总会走最短路,并且为了避免麻烦,只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S国政府为每个城市标定了不同的旅行评级,旅行者们常会记下途中(包括起点和终点)留宿过的城市的评级总和或最大值。
在S国的历史上常会发生以下几种事件:
“CC x c“:城市x的居民全体改信了c教;
“CW x w“:城市x的评级调整为w;
“QS x y“:一位旅行者从城市x出发,到城市y,并记下了途中留宿过的城市的评级总和;
“QM x y“:一位旅行者从城市x出发,到城市y,并记下了途中留宿过的城市的评级最大值。
由于年代久远,旅行者记下的数字已经遗失了,但记录开始之前每座城市的信仰与评级,还有事件记录本身是完好的。请根据这些信息,还原旅行者记下的数字。 为了方便,我们认为事件之间的间隔足够长,以致在任意一次旅行中,所有城市的评级和信仰保持不变。
一棵树上每个点有颜色和权值,四种操作:
保证询问的起终点同色
输入格式:
输入的第一行包含整数N,Q依次表示城市数和事件数。
接下来N行,第i+l行两个整数Wi,Ci依次表示记录开始之前,城市i的评级和信仰。 接下来N-1行每行两个整数x,y表示一条双向道路。
接下来Q行,每行一个操作,格式如上所述。
输出格式:
对每个QS和QM事件,输出一行,表示旅行者记下的数字。
输入样例#1:
5 6 3 1 2 3 1 2 3 3 5 1 1 2 1 3 3 4 3 5 QS 1 5 CC 3 1 QS 1 5 CW 3 3 QS 1 5 QM 2 4
输出样例#1:
8 9 11 3
N,Q < =10^5 , C < =10^5
数据保证对所有QS和QM事件,起点和终点城市的信仰相同;在任意时刻,城市的评级总是不大于10^4的正整数,且宗教值不大于C。
可以每个颜色开一棵线段树做树剖,但是空间开不下。于是我们想到了动态开点。
复杂度O(n \log^2 n)。动态开点遇到null点可以直接return减小常数。
// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <vector>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1;
register char c = fgc();
while(!isdigit(c)) {
if(c == '-') neg = -1;
c = fgc();
}
while(isdigit(c)) {
res = (res << 1) + (res << 3) + c - '0';
c = fgc();
}
return res * neg;
}
inline bool isop(char c) {
return c == 'C' || c == 'Q';
}
inline int readop() {
char c;
while(!isop(c = fgc())) {}
if(c == 'C') {
if(fgc() == 'C') return 1;
else return 2;
} else {
if(fgc() == 'S') return 3;
else return 4;
}
}
const int MAXN = 100005;
int n, q;
std::vector<int> gra[MAXN];
struct Node {
int lch, rch, sum, mx;
} tr[MAXN << 8];
int rt[MAXN], tot;
inline void modify(int &o, int l, int r, int x, int v) {
if(!o) o = ++tot;
if(l == r) {
tr[o].sum = tr[o].mx = v; return;
}
int mid = (l + r) >> 1;
if(x <= mid) modify(tr[o].lch, l, mid, x, v);
else modify(tr[o].rch, mid + 1, r, x, v);
tr[o].sum = tr[tr[o].lch].sum + tr[tr[o].rch].sum;
tr[o].mx = std::max(tr[tr[o].lch].mx, tr[tr[o].rch].mx);
}
inline int querymx(int o, int l, int r, int ll, int rr) {
if(!o) return 0;
if(l >= ll && r <= rr) return tr[o].mx;
int mid = (l + r) >> 1, res = 0;
if(ll <= mid) res = std::max(res, querymx(tr[o].lch, l, mid, ll, rr));
if(rr > mid) res = std::max(res, querymx(tr[o].rch, mid + 1, r, ll, rr));
return res;
}
inline int querysum(int o, int l, int r, int ll, int rr) {
if(!o) return 0;
if(l >= ll && r <= rr) return tr[o].sum;
int mid = (l + r) >> 1, res = 0;
if(ll <= mid) res += querysum(tr[o].lch, l, mid, ll, rr);
if(rr > mid) res += querysum(tr[o].rch, mid + 1, r, ll, rr);
return res;
}
int fa[MAXN], siz[MAXN], son[MAXN], top[MAXN], dep[MAXN], dfn[MAXN], clk;
inline void dfs1(int u) {
siz[u] = 1;
for(int i = 0; i < gra[u].size(); i++) {
int v = gra[u][i];
if(v == fa[u]) continue;
fa[v] = u;
dep[v] = dep[u] + 1;
dfs1(v);
siz[u] += siz[v];
if(siz[v] > siz[son[u]]) son[u] = v;
}
}
inline void dfs2(int u, int tp) {
top[u] = tp; dfn[u] = ++clk;
if(son[u]) dfs2(son[u], tp);
for(int i = 0; i < gra[u].size(); i++) {
int v = gra[u][i];
if(v == fa[u] || v == son[u]) continue;
dfs2(v, v);
}
}
inline int querymx(int x, int y, int c) {
int res = 0, tx = top[x], ty = top[y];
while(tx != ty) {
if(dep[tx] > dep[ty]) {
std::swap(x, y); std::swap(tx, ty);
}
res = std::max(res, querymx(rt[c], 1, n, dfn[ty], dfn[y]));
y = fa[ty]; ty = top[y];
}
if(dep[x] > dep[y]) std::swap(x, y);
res = std::max(res, querymx(rt[c], 1, n, dfn[x], dfn[y]));
return res;
}
inline int querysum(int x, int y, int c) {
int res = 0, tx = top[x], ty = top[y];
while(tx != ty) {
if(dep[tx] > dep[ty]) {
std::swap(x, y); std::swap(tx, ty);
}
res += querysum(rt[c], 1, n, dfn[ty], dfn[y]);
y = fa[ty]; ty = top[y];
}
if(dep[x] > dep[y]) std::swap(x, y);
res += querysum(rt[c], 1, n, dfn[x], dfn[y]);
return res;
}
int w[MAXN], c[MAXN], op, x, y;
int main() {
n = readint(); q = readint();
for(int i = 1; i <= n; i++) {
w[i] = readint(); c[i] = readint();
}
for(int i = 1; i < n; i++) {
x = readint(); y = readint();
gra[x].push_back(y); gra[y].push_back(x);
}
dfs1(1);
dfs2(1, 1);
for(int i = 1; i <= n; i++) {
modify(rt[c[i]], 1, n, dfn[i], w[i]);
}
while(q--) {
op = readop(); x = readint(); y = readint();
if(op == 1) {
modify(rt[c[x]], 1, n, dfn[x], 0);
c[x] = y;
modify(rt[c[x]], 1, n, dfn[x], w[x]);
} else if(op == 2) {
w[x] = y;
modify(rt[c[x]], 1, n, dfn[x], w[x]);
} else if(op == 3) {
printf("%d\n", querysum(x, y, c[x]));
} else {
printf("%d\n", querymx(x, y, c[x]));
}
}
return 0;
}
题目地址:洛谷:【P4280】[AHOI2008]逆序对 – 洛谷、BZOJ:Problem 1831. — [AHOI2008]逆序对
暑假到了,小可可和伙伴们来到海边度假,距离海滩不远的地方有个小岛,叫做欢乐岛,整个岛是一个大游乐园,里面有很多很好玩的益智游戏。碰巧岛上正在举行“解谜题赢取免费门票”的活动,只要猜出来迷题,那么小可可和他的朋友就能在欢乐岛上免费游玩两天。
迷题是这样的:给出一串全部是正整数的数字,这些正整数都在一个范围内选取,谁能最快求出这串数字中“逆序对”的个数,那么大奖就是他的啦!
当然、主办方不可能就这么简单的让迷题被解开,数字串都是被处理过的,一部分数字被故意隐藏起来,这些数字均用-1来代替,想要获得大奖就必须求出被处理的数字串中最少能有多少个逆序对。小可可很想获得免费游玩游乐园的机会,你能帮助他吗?
注:“逆序对”就是如果有两个数A和B,A在B左边且A大于B,我们就称这两个数为一个“逆序对”,例如:4 2 1 3 3里面包含了5个逆序对:(4, 2)、(4, 1)、(4, 3)、(4, 3)、(2, 1)。
假设这串数字由5个正整数组成,其中任一数字N均在1~4之间,数字串中一部分数字被“-1”替代后,如:4 2 -1 -1 3 ,那么这串数字,可能是4 2 1 3 3,也可能是4 2 4 4 3,也可能是别的样子。你要做的就是根据已知的数字,推断出这串数字里最少能有多少个逆序对。
一个序列中有一些空位,求所有填空方案中序列逆序对数最小为多少。
输入格式:
第一行两个正整数N和K;
第二行N个整数,每个都是-1或是一个在1~K之间的数(N<=10000,K<=100)。
输出格式:
一个正整数,即这些数字里最少的逆序对个数。
输入样例#1:
5 4 4 2 -1 -1 3
输出样例#1:
4
100%的数据中,N<=10000,K<=100。
60%的数据中,N<=100。
40%的数据中,-1出现不超过两次。
有一个贪心的结论是,在空位上填上单调不降的数字会更好。我们可以假设i < j且a[i] < a[j],如果交换a[i]和a[j],对a[1]~a[i-1]以及a[j+1]~a[n]产生的逆序对无影响,对于a[i+1]~a[j-1]之间且不在(a[i], a[j])区间内的数字也无影响,只会影响在该区间内的数字,可以发现,对于这些数字,逆序对数显然增加了。因此我们证明了,单调不降答案不会变差。
于是我们发现填单调不降序列无后效性,可以开始愉快地DP了。设计状态dp[i][j]表示填到第i个空且该位置填j的逆序对数,显然有以下转移
dp[i][j] = \min_{1 \leq k \leq j} \{ dp[i-1][j] \} + 该位置填j的逆序对数
中间用到的min,我们可以在转移的时候顺便处理出来,因此整个DP可以实现O(nk)的复杂度。
最后的答案是 \min_{1 \leq i \leq k} \{ dp[n'][i] \} + 原有逆序对数 。
// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1;
register char c = fgc();
while(!isdigit(c)) {
if(c == '-') neg = -1;
c = fgc();
}
while(isdigit(c)) {
res = (res << 1) + (res << 3) + c - '0';
c = fgc();
}
return res * neg;
}
const int MAXN = 10005;
int n, k, a[MAXN], pre[MAXN][105], nxt[MAXN][105], mn[MAXN][105], dp[MAXN][105], pos[MAXN], tot;
int main() {
n = readint(); k = readint();
for(int i = 1; i <= n; i++) {
a[i] = readint();
if(a[i] == -1) pos[++tot] = i;
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= k; j++) {
pre[i][j] = pre[i - 1][j] + (j < a[i]);
}
}
for(int i = n; i; i--) {
for(int j = 1; j <= k; j++) {
nxt[i][j] = nxt[i + 1][j] + (j > a[i] && a[i] != -1);
}
}
for(int i = 1; i <= tot; i++) {
mn[i][1] = dp[i][1] = mn[i - 1][1] + pre[pos[i]][1] + nxt[pos[i]][1];
for(int j = 2; j <= k; j++) {
dp[i][j] = mn[i - 1][j] + pre[pos[i]][j] + nxt[pos[i]][j];
mn[i][j] = std::min(mn[i][j - 1], dp[i][j]);
}
}
int ans = 1e9;
for(int i = 1; i <= k; i++) {
ans = std::min(ans, dp[tot][i]);
}
for(int i = 1; i <= n; i++) {
if(a[i] != -1) ans += pre[i][a[i]];
}
printf("%d", ans);
return 0;
}
题目地址:洛谷:【P3425】[POI2005]KOS-Dicing – 洛谷、BZOJ:Problem 1532. — [POI2005]Kos-Dicing
掷骰子是一种双人游戏,它的结果是完全随机的。最近它在整个Byteotia变得非常流行。在Byteotia的首都甚至有一个特别的掷骰子业余爱好者俱乐部。俱乐部的老主顾们花时间互相聊天并每隔一阵子就和一个随机选择的对手玩这他们最喜欢的游戏。一天中赢得最多游戏的人会得到“幸运者”头衔。有时晚上俱乐部很安静,只有很少的比赛。这是哪怕赢一场也能获得“幸运者”头衔的时间。
很久很久以前有一个很不走运的人,叫Byteasar,赢得了这个光荣的头衔。他被深深地震惊了以至于完全忘了他已经赢了多少场。现在他想知道他有多幸运,以及幸运之神是否最终会向他微笑——也许他的运气会变好?他确切地知道在那个幸运的晚上有多少场游戏以及是谁玩的。然而,他不知道结果。Byteasar希望查明至少要赢几场才能获得“幸运者”头衔。做个好人,帮他满足他的好奇心吧!
任务:写一个程序:
对于每场游戏从stdin读入这场游戏的一对玩家 找到最小的数k,使得存在一个游戏结果的集合,其中赢最多的玩家赢了k场。向stdout输出数k和找到的集合中游戏的结果
Dicing 是一个两人玩的游戏,现在有一个非常不走运的家伙,他想成为那个玩的最好的人,他现在知道了所有比赛的安排,他想知道,在最好的情况下,他最少只需要赢几场就可以赢得冠军,即他想知道比赛以后赢的最多的那个家伙最少会赢多少场.
输入格式:
stdin的第一行有一个一对由一个空格分开整数n和m (1 <= n, m <= 10000) 。n表示玩家数,m表示游戏数。玩家从1到n编号。在接下来的m行中有每场游戏的一对玩家的编号,由一个空格分开,描述了游戏的序列。一对玩家可能会在这个序列中多次出现。
输出格式:
stdout的第一行应该包含一个确定的数k。对于在输入的第i行指定的一对玩家a, b,如果在找到的结果集合中a胜过b,则在输出的第i行输出1, 否则输出0.
输入样例#1:
4 4 1 2 1 3 1 4 1 2
输出样例#1:
1 0 0 0 1
考虑二分答案然后判定。判定可以采用网络流,建立源→每场游戏→游戏玩家→汇的网络,源→游戏及游戏→玩家的边容量为1,玩家→汇的边容量为二分的答案。如果答案是x,说明游戏中每个人胜出的次数都不大于x,因此只需在该网络上判定是否满流,满流说明该答案可行。
复杂度玄学。
// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <queue>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1;
register char c = fgc();
while(!isdigit(c)) {
if(c == '-') neg = -1;
c = fgc();
}
while(isdigit(c)) {
res = (res << 1) + (res << 3) + c - '0';
c = fgc();
}
return res * neg;
}
const int MAXN = 20005, INF = 1e9;
struct Edge {
int to, cap, nxt;
} gra[MAXN << 4];
int head[MAXN], tot;
inline void addedge(int u, int v, int cap) {
gra[tot] = Edge {v, cap, head[u]}; head[u] = tot++;
gra[tot] = Edge {u, 0, head[v]}; head[v] = tot++;
}
int level[MAXN];
inline bool bfs(int s, int t) {
memset(level, -1, sizeof(level));
std::queue<int> que;
que.push(s); level[s] = 0;
while(!que.empty()) {
int u = que.front(); que.pop();
for(int i = head[u]; ~i; i = gra[i].nxt) {
int v = gra[i].to;
if(gra[i].cap && level[v] == -1) {
level[v] = level[u] + 1;
if(v == t) return true;
que.push(v);
}
}
}
return level[t] != -1;
}
int cur[MAXN];
inline int dfs(int u, int t, int left) {
if(u == t || !left) return left;
int flow = 0;
for(int &i = cur[u]; ~i; i = gra[i].nxt) {
int v = gra[i].to;
if(level[v] == level[u] + 1 && gra[i].cap) {
int f = dfs(v, t, std::min(left, gra[i].cap));
if(f) {
flow += f; left -= f;
gra[i].cap -= f; gra[i ^ 1].cap += f;
if(!left) break;
}
}
}
return flow;
}
inline int dinic(int s, int t) {
int flow = 0;
while(bfs(s, t)) {
memcpy(cur, head, sizeof(head));
int f;
while(f = dfs(s, t, INF)) flow += f;
}
return flow;
}
int n, m, a[MAXN], b[MAXN], S, T;
inline bool check(int x) {
tot = 0; memset(head, -1, sizeof(head));
for(int i = 1; i <= n; i++) {
addedge(i, T, x);
}
for(int i = 1; i <= m; i++) {
addedge(S, i + n, 1);
addedge(i + n, a[i], 1);
addedge(i + n, b[i], 1);
}
return dinic(S, T) >= m;
}
int main() {
n = readint(); m = readint(); S = n + m + 1; T = S + 1;
for(int i = 1; i <= m; i++) {
a[i] = readint(); b[i] = readint();
}
int l = 0, r = m, mid;
while(r - l > 1) {
mid = (l + r) >> 1;
if(check(mid)) r = mid; else l = mid;
}
printf("%d\n", r);
check(r);
for(int i = 1; i <= m; i++) {
for(int j = head[i + n]; ~j; j = gra[j].nxt) {
int v = gra[j].to;
if(!gra[j].cap) {
printf("%d\n", v == a[i]); break;
}
}
}
return 0;
}