2018冬令营模拟测试赛（九）
[Problem A]王子
试题描述
不是所有王子都会遇见自己的中关村，主公，公主。
从前有个王子姓王，王王子遇到了一位美丽的公主，她的名字当然是公公主啦。
王王子对公公主一见钟情，他想方设法地去讨好公公主， 他准备了 (N) 个节目依次表演给公主看，每个节目他可以倒立表演，或者正常表演。王王子非常聪明，所以他总是能预估出每个节目的每种表演形式能刷多少好感度，我们记第i个节目倒立表演能增加 (A_i) 的好感度，正常表演能增加 (B_i) 的好感度。
这个公公主也不是一个省油的灯，他（没打错）看节目的时候既不喜欢太循规蹈矩，也不喜欢太标新立异。准确的说，他看的王子表演的任意连续 (K) 个节目里面，至少有 (P) 个倒立表演的节目，(Q) 个正常表演的节目。
王王子想知道，在满足公公主的特殊癖好的前提下，他最多能刷多少的好感度。
输入
第一行四个整数 (N,K,P,Q)。
接下来N行每行两个整数表示 (A_i) 和 (B_i)。
输出
一行一个正整数表示答案。
输入示例
2 2 1 1
2 3
3 5
输出示例
7
数据规模及约定
对于 (20\%) 的数据，(N < 16)。
对于另外 (30\%) 的数据， (K < 10)。
对于另外 (30\%) 的数据， (A_i, B_i < 4)
对于 (100\%) 的数据， (0 < N < 200, 0 < A_i, B_i < 10000000, 0 ≤ P + Q ≤ K ≤ N)。
题解
这题还是可以不用线性规划做，直接上上下界费用流。
一开始先假设所有节目都是正常表演（即所有节目收益都为 (B_i)），然后将一些节目调整成倒立表演。那么这时一个区间的限制就是“可以调整的数量在区间 ([P, K - Q]) 中”。于是我们就可以把所有的区间串起来，每个区间所对应的边的流量限制为 ([P, K - Q])，节目 (i) 就将它影响到的区间圈在内加一条容量限制为 (1) 的费用为 (A_i - B_i) 的边。然后跑一下上下界最大费用流即可。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define rep(i, s, t) for(int i = (s); i <= (t); i++)
#define dwn(i, s, t) for(int i = (s); i >= (t); i--)
int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
#define maxn 220
#define maxm 1320
#define oo 2147483647
#define LL long long
struct Edge {
int from, to, flow, cost;
Edge() {}
Edge(int _1, int _2, int _3, int _4): from(_1), to(_2), flow(_3), cost(_4) {}
};
struct ZKW {
int n, m, s, t, cost, ans, head[maxn], nxt[maxm];
Edge es[maxm];
bool inq[maxn];
int d[maxn], Q[maxn], hd, tl;
bool vis[maxn];
void init() {
ans = m = 0; memset(head, -1, sizeof(head));
return ;
}
void setn(int _) {
n = _;
return ;
}
void AddEdge(int a, int b, int c, int d) {
es[m] = Edge(a, b, c, d); nxt[m] = head[a]; head[a] = m++;
es[m] = Edge(b, a, 0, -d); nxt[m] = head[b]; head[b] = m++;
return ;
}
int Nxt(int u) { return (u + 1) % maxn; }
bool BFS() {
rep(i, 1, n) d[i] = oo;
d[t] = 0;
hd = tl = 0; Q[tl = Nxt(tl)] = t; inq[t] = 1;
while(hd != tl) {
int u = Q[hd = Nxt(hd)]; inq[u] = 0;
for(int i = head[u]; i != -1; i = nxt[i]) {
Edge& e = es[i^1];
if(e.flow && d[e.from] > d[u] + e.cost) {
d[e.from] = d[u] + e.cost;
if(!inq[e.from]) inq[e.from] = 1, Q[tl = Nxt(tl)] = e.from;
}
}
}
if(d[s] == oo) return 0;
cost = d[s];
return 1;
}
int DFS(int u, int a) {
if(u == t || !a) return ans += cost * a, a;
if(vis[u]) return 0;
vis[u] = 1;
int flow = 0, f;
for(int i = head[u]; i != -1; i = nxt[i]) {
Edge& e = es[i];
if(d[e.to] == d[u] - e.cost && (f = DFS(e.to, min(a, e.flow)))) {
flow += f; a -= f;
e.flow -= f; es[i^1].flow += f;
if(!a) return flow;
}
}
return flow;
}
int MaxFlow(int _s, int _t) {
s = _s; t = _t;
int flow = 0, f;
while(BFS())
do {
memset(vis, 0, sizeof(vis));
f = DFS(s, oo);
flow += f;
} while(f);
return flow;
}
} sol;
int ind[maxn];
int main() {
int n = read(), len = read(), P = read(), Q = read(), S = n - len + 3, T = S + 1, sum = 0, cost = 0;
sol.init(); sol.setn(T);
rep(i, 1, n) {
int A = read(), B = read(), l = max(i - len + 1, 1), r = min(i + 1, n - len + 2);
if(B > A) sol.AddEdge(r, l, 1, B - A);
else sol.AddEdge(l, r, 1, A - B), ind[l]++, ind[r]--, cost += B - A;
sum += B;
}
rep(i, 1, n - len + 1) sol.AddEdge(i, i + 1, len - P - Q, 0), ind[i+1] += P, ind[i] -= P;
rep(i, 1, n - len + 2) {
if(ind[i] > 0) sol.AddEdge(S, i, ind[i], 0);
if(ind[i] < 0) sol.AddEdge(i, T, -ind[i], 0);
}
sol.MaxFlow(S, T);
printf("%d
", sum - (sol.ans + cost));
return 0;
}
[Problem B]遇见
试题描述
啊写背景好累.
有一个长度为 (N) 的序列，求这个序列有多少个区间，满足所有在这个区间里出现过的数，他们的出现次数都是奇数次（没出现过的数不考虑在内）。
由于答案不会太大，我们就不取模了。
输入
第一行一个整数 (N)
接下来一行 (N) 个整数表示这个序列，第 (i) 个数是序列的第 (i) 个元素 (A_i)。
输出
一行一个整数表示答案
输入示例
4
2 2 2 3
输出示例
7
数据规模及约定
对于 (20\%) 的数据，(N le 500)。
对于 (40\%) 的数据，(N le 2000)。
对于另外 (30\%) 的数据，(A_i le 200)。
对于 (100\%) 的数据，(1 le N le 30000)，(1 le A_i le 1000000)。
题解
此题暴力水过。
正解是个 (O(n sqrt{n} mathrm{log}n)) 的非确定性算法：给每个不同的权值随机安排一个小于 (2^{64}) 的权值，然后除第一次出现外每出现一次就异或一次它对应的权值，当权值为 (0) 的时候计数；那么就从前往后枚举右端点，每次区间异或、查询多少个全 (0) 数，于是分块 + trie 可以实现。
直接贴暴力了。。。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define rep(i, s, t) for(int i = (s); i <= (t); i++)
#define dwn(i, s, t) for(int i = (s); i >= (t); i--)
int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
#define maxn 30010
int n, A[maxn], num[maxn], tot[maxn], tag[maxn];
bool has[maxn], lst[maxn];
int main() {
n = read();
rep(i, 1, n) num[i] = A[i] = read();
sort(num + 1, num + n + 1);
int cn = unique(num + 1, num + n + 1) - num - 1;
rep(i, 1, n) A[i] = lower_bound(num + 1, num + cn + 1, A[i]) - num;
dwn(i, n, 1) if(!has[A[i]]) lst[i] = 1, has[A[i]] = 1;
int cnt = 0, cant;
rep(l, 1, n) {
cant = 0;
rep(r, l, n) {
int &Tot = tot[A[r]], &Tag = tag[A[r]];
if(Tag != l) Tag = l, Tot = 1;
else Tot++;
if(!(Tot & 1)) {
cant++;
if(lst[r]) break;
}
else if(Tot > 1) cant--;
cnt += !cant;
}
}
printf("%d
", cnt);
return 0;
}
[Problem C]中关村
试题描述
在一个 (K) 维空间中，每个整点被黑白染色。对于一个坐标为 ((x_1,x_2,……,x_k)) 的点，他的颜色我们通过如下方式计算：
1) 如果存在一维坐标是 $0$，则颜色是黑色。
2) 如果这个点是 $(1,1,cdots,1)$（每一维都是 $1$），这个点的颜色是白色
3) 如果这个点的 $K$ 个前驱(任取一维坐标减一)中的白点有奇数个，那么这个点的颜色就是白色，否则就是黑色。
给出一个 (K) 维超矩形，求这个矩形内的白点个数。
输入
第一行一个整数 (K)
接下来 (K) 行每行两个整数 (L_i)，(R_i) 表示矩形的第 (i) 维的坐标范围。
输出
一行一个整数表示答案对 (998244353) 取模的结果
输入示例
2
1 3
2 4
输出示例
5
数据规模及约定
对于 (10\%) 的数据，矩形内整点个数不超过 (1000000) 个。
对于另外 (15\%) 的数据，(K = 2)。
对于另外 (15\%) 的数据，(K = 3)。
对于另外 (20\%) 的数据，(K = 4)。
对于 (100\%) 的数据，(1 le K le 9)， (1 le L_i le R_i le 10^{15}).
题解
如果我们形象地表示一下题目描述，可以发现是一个 dp，如果我们将白点看成 (1)，黑点看成 (0)，那么点 ((x_1, x_2, cdots , x_K)) 的值就是从 ((1, 1, cdots , 1)) 到 ((x_1, x_2, cdots , x_K)) 的不同最短路径数模 (2) 的结果。
这个东西可以用组合数算，不难发现如果将所有坐标减 (1)，那么点 ((x_1, x_2, cdots , x_K)) 上的值就是 (prod_{i = 1}^K { C_{ sum_{j = 1}^i {x_j} }^{ x_i } })，如果这个东西等于 (1)，当且仅当所有组合数的值都为 (1)，用 lucas 定理我们可以得到对于 (K = 2) 的情况当且仅当 (x_1) 与 (x_2) 的二进制表示无交集时，((x_1, x_2)) 上的值为 (1)；然后用归纳法可以推导 (K > 2) 的情况就是 (x_1, x_2, cdots , x_K) 两两没有交集时该点上的值为 (1)。
然后就是数位 dp 了，令 (f(i, S)) 表示从高往低前 (i) 位，状态为 (S) 的方案数，(S) 是一个三进制数，第 (i) 为 (0)、(1)、(2) 分别表示贴着下界、在上下界之间和贴着上界；转移时枚举一下那个 (1) 放在哪一维，或者不放 (1)，讨论一下特殊情况（如由于下界的限制必须要放 (1) 等）。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define rep(i, s, t) for(int i = (s); i <= (t); i++)
#define dwn(i, s, t) for(int i = (s); i >= (t); i--)
#define LL long long
LL read() {
LL x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
#define maxn 10
#define maxb 51
#define maxs 262144
#define MOD 998244353
int n, f[maxb][maxs], diff[maxn];
LL L[maxn], R[maxn];
void print(int x) {
rep(i, 0, n - 1) printf("%d", x >> (i << 1) & 3);
return ;
}
int main() {
n = read();
rep(i, 0, n - 1) L[i] = read() - 1, R[i] = read() - 1;
int all = (1 << n) - 1, mxs = (1 << (n << 1)) - 1;
f[maxb-1][0] = 1;
rep(i, 0, n - 1) dwn(b, maxb - 1, 0) if((L[i] ^ R[i]) >> b & 1){ diff[i] = b; break; }
dwn(b, maxb - 1, 1) rep(s, 0, mxs) if(f[b][s]) {
// printf("f[%d][", b); print(s); printf("] = %d [%lld, %lld][%lld, %lld]
", f[b][s], L[0] >> b & 1, R[0] >> b & 1, L[1] >> b & 1, R[1] >> b & 1);
int must = -1; bool ok = 1;
rep(i, 0, n - 1) if((s >> (i << 1) & 3) == 0 && (L[i] >> b - 1 & 1)) {
if(must < 0) must = i;
else{ ok = 0; break; }
}
if(!ok) continue;
int chgu = 0;
rep(i, 0, n - 1) if((s >> (i << 1) & 3) == 2 && (R[i] >> b - 1 & 1)) chgu |= 3 << (i << 1);
if(must >= 0) {
(f[b-1][s^chgu] += f[b][s]) %= MOD;
continue;
}
rep(i, 0, n - 1) // set bit[i] = 1
switch(s >> (i << 1) & 3) {
case 0:
if(b > diff[i] && !(R[i] >> b - 1 & 1)) break;
if(b > diff[i]){ (f[b-1][s^chgu^(2<<(i<<1))] += f[b][s]) %= MOD; break; }
(f[b-1][s^chgu^(1<<(i<<1))] += f[b][s]) %= MOD; break;
case 1: (f[b-1][s^chgu] += f[b][s]) %= MOD; break;
case 2:
if(!(chgu >> (i << 1) & 3)) break;
(f[b-1][s^chgu^(3<<(i<<1))] += f[b][s]) %= MOD;
}
(f[b-1][s^chgu] += f[b][s]) %= MOD; // everybody 0
}
// rep(s, 0, mxs) if(f[0][s]) printf("f[%d][", 0), print(s), printf("] = %d [%lld, %lld][%lld, %lld]
", f[0][s], L[0] >> 0 & 1, R[0] >> 0 & 1, L[1] >> 0 & 1, R[1] >> 0 & 1);
int ans = 0;
rep(s, 0, mxs) (ans += f[0][s]) %= MOD;
printf("%d
", ans);
return 0;
}