當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

2018冬令营模拟测试赛（九）

發布時間：2025/4/16 编程问答 27 豆豆

生活随笔收集整理的這篇文章主要介紹了 2018冬令营模拟测试赛（九）小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

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

輸出示例

數據規模及約定

對于 $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 longstruct 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\n", sum - (sol.ans + cost));return 0; }

[Problem B]遇見

試題描述

啊寫背景好累.

有一個長度為 $N$ 的序列，求這個序列有多少個區間，滿足所有在這個區間里出現過的數，他們的出現次數都是奇數次（沒出現過的數不考慮在內）。

由于答案不會太大，我們就不取模了。

輸入

第一行一個整數 $N$

接下來一行 $N$ 個整數表示這個序列，第 $i$ 個數是序列的第 $i$ 個元素 $A_i$。

輸出

一行一個整數表示答案

輸入示例

4 2 2 2 3

輸出示例

數據規模及約定

對于 $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 可以實現。

直接貼暴力了。。。

[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

輸出示例

數據規模及約定

對于 $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 longLL 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 998244353int 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]\n", 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] = 1switch(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]\n", 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\n", ans);return 0; }

轉載于:https://www.cnblogs.com/xiao-ju-ruo-xjr/p/8203662.html

總結

以上是生活随笔為你收集整理的2018冬令营模拟测试赛（九）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇：进程在与Windows Process
下一篇：著名站点的爬虫 —— 豆瓣