版權屬于yhzq，想要引用此題（包括題面）的朋友請聯系部落客
T2.Van
分析：
這樣把博弈黑出翔真的好嗎。。。
首先我們要明确怎麼計算一個序列的最長Van序列
這就和花匠那道題有異曲同工之妙了
我們隻需要找到序列的所有折點即可
k=1
這種情況下我們隻能把序列中的每一個數變成一樣的
顯然都變成中位數最優
“中位數定理”的玄學證明
k=2
這種情況下我們需要使整個序列單調不升或者不降
于是我就想到了這道題
mmp，完全是原題好伐。。。不講
k=3
枚舉中間折點，轉化成k=2的情況
k<=10
注意到這個資料的n很小，那麼我們可以預處理使每個區間上升或下降的最小代價
然後就可以dp了
f[i][j][k] f [ i ] [ j ] [ k ] 表示第 i i 位，已經有了jj段，最後一段是上升還是下降
#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 20010
#define M 1010
using namespace std;
int tot, a[N], n, k;
struct heap {
int ch[N][], dis[N], val[N];
int merge(int x, int y) {
if (x * y == ) return x + y;
if (val[x] < val[y]) swap(x, y);
ch[x][] = merge(ch[x][], y);
if (dis[ch[x][]] < dis[ch[x][]])
swap(ch[x][], ch[x][]);
dis[x] = dis[ch[x][]] + ;
return x;
}
int pop(int x) {
return merge(ch[x][], ch[x][]);
}
void init(int x, int v) {
ch[x][] = ch[x][] = dis[x] = ;
val[x] = v;
}
} h;
struct seqs {
int l, r, root, insum, innum, sum;
int cost() {
int v = h.val[root];
return (v * innum - insum) + (sum - insum - v * (r - l + - innum));
}
void merge(seqs now) { //now must behind this
r = now.r, root = h.merge(root, now.root);
innum += now.innum, insum += now.insum, sum += now.sum;
while (innum * > r - l + )
innum--, insum -= h.val[root],
root = h.pop(root);
}
} seq[N];
void add(int pos, int v, int &cost) {
seq[++tot].root = seq[tot].l = seq[tot].r = pos;
seq[tot].innum = , seq[tot].insum = seq[tot].sum = v;
h.init(pos, v), cost += seq[tot].cost();
while(tot > && h.val[seq[tot].root] < h.val[seq[tot - 1].root]) {
cost -= seq[tot].cost() + seq[tot - 1].cost();
seq[tot - 1].merge(seq[tot]), tot--;
cost += seq[tot].cost();
}
}
void solve_1() {
sort(a + , a + + n);
int ans = , mid = a[n / ];
for (int i = ; i <= n; i++) ans += abs(a[i] - mid);
printf("%d\n", ans);
}
void solve_2() {
int ans = , cost;
cost = , tot = ;
for (int i = ; i <= n; i++) add(i, a[i], cost);
ans = min(ans, cost);
cost = , tot = ;
for (int i = ; i <= n; i++) add(i, -a[i], cost);
ans = min(ans, cost);
printf("%d\n", ans);
}
void solve_3() {
static int fwd1[N], fwd2[N], bac1[N], bac2[N];
int ans = , cost;
cost = tot = ;
for (int i = ; i <= n; i++) add(i, a[i], cost), fwd1[i] = cost;
cost = tot = ;
for (int i = ; i <= n; i++) add(i, -a[i], cost), fwd2[i] = cost;
cost = tot = ;
for (int i = n; i >= ; i--) add(n - i + , a[i], cost), bac1[i] = cost;
cost = tot = ;
for (int i = n; i >= ; i--) add(n - i + , -a[i], cost), bac2[i] = cost;
for (int i = ; i <= n + ; i++)
ans = min(ans, fwd1[i - ] + bac1[i]),
ans = min(ans, fwd2[i - ] + bac2[i]);
printf("%d\n", ans);
}
void solve_4() {
k--;
static int fwd[M][M], bac[M][M], f[M][], g[M][];
for (int i = ; i <= n; i++) {
int cost = ; tot = ;
for (int j = i; j <= n; j++) add(j, a[j], cost), fwd[i][j] = cost;
cost = , tot = ;
for (int j = i; j <= n; j++) add(j, -a[j], cost), bac[i][j] = cost;
}
memset(f, , sizeof f), memset(g, , sizeof g);
f[][] = g[][] = ;
for (int i = ; i <= n; i++)
for (int j = ; j <= k; j++)
for (int l = ; l < i; l++)
f[i][j] = min(f[i][j], g[l][j - ] + fwd[l + ][i]),
g[i][j] = min(g[i][j], f[l][j - ] + bac[l + ][i]);
int ans = ;
for (int i = ; i <= k; i++) ans = min(ans, f[n][i]);
for (int i = ; i <= k; i++) ans = min(ans, g[n][i]);
printf("%d\n", ans);
}
main() {
freopen("van.in", "r", stdin);
freopen("van.out", "w", stdout);
scanf("%d%d", &n, &k);
for (int i = ; i <= n; i++)
scanf("%d", &a[i]);
if (k == ) solve_1();
else if (k == ) solve_2();
else if (k == ) solve_3();
else solve_4();
}
T3.Gay
分析：
題目來源：33IQ
曲神表示：啊~原題是狗，我改成了博弈，沒什麼太大差別嘛
。。。博弈被黑的最慘的一次。。。
算法一
最簡單的還是完全圖的20分
如果第一天，有人走出去看到其他所有人的博弈都正常，那麼就可以确定ta的博弈病變了，于是ta就會懷着沉重的心情用炒栗子超離子垃圾處理器把ta的博弈融掉
如果第一天，有人走出去看見一家的博弈病變了，但是到了這一天沒有人去融掉博弈，說明這個住宅區中一定還存在一個病變的博弈，就是自己的那隻？那個？那位？那坨？
反正第二天兩個人會同時懷着沉重的心情用炒栗子超離子垃圾處理器把博弈融掉（嘶~~）
以此類推
是以有 x x 個病變博弈的社群需要xx天才能确定下來，進行融化
是以兩問答案都是 ∑ni=1C(n,i)∗i ∑ i = 1 n C ( n , i ) ∗ i
算法二
上一個算法也還是挺有啟發性的，我們發現我們在分析自己的博弈有沒有病變的時候的方法是：假設沒有病變，然後看前一天是否應該有熔化。而這個方法對任意圖都适用的。
考慮狀壓dp，令 dpU d p U 表示 U U 集合中的博弈病變時的熔化時間
然後我們接着分析：如果我的博弈沒病，那麼什麼時候應該熔化呢？
于是要枚舉了所有可能的病變情況VV，那麼如果他的博弈沒有病變，最遲應該在
max dpV m a x d p V 的時間有人熔化自己的博弈
是以他會在第 max dpV+1 m a x d p V + 1 天熔化
是以我們就知道怎麼DP了！
對于一個狀态，我們枚舉這個狀态中每個病變的博弈的主人，那麼這個狀态的熔化時間應該是這些病變的博弈主人中熔化時間的最小值，從中我們也可以知道有多少人同時熔化
那麼一個人會枚舉哪些可能的病變情況呢：首先對于他看到的博弈，他枚舉的病變情況一定是和目前情況相同的，其次他自己一定是沒有病變的，而至于那些他看不到的博弈，他就隻好枚舉這些博弈的所有病變狀況了
最後，如果有限時間内不會熔化怎麼辦？事實上是存在這種情況的，但是沒關系，如果我們發現轉移出現了環，是以這個環中的所有狀态都是在有限時間内不會熔化的
時間複雜度似乎是 O(4nn) O ( 4 n n ) ？
可以通過前兩個測試點
算法三
有了算法二，我們可以把表打出來看看，然後就可以發現一個小小的規律：
對于病變狀态U和V，如果U∈V，那麼必然有 dpU≤dpV d p U ≤ d p V
至于這一個規律的證明放在後面
是以就可以隻枚舉一種病變情況：首先對于所有他看到的博弈，他枚舉的病變情況一定是和目前情況相同的，其次他自己一定是沒有病變的，而至于那些他看不到的博弈，由剛才的規律，可以全部當成病變的
是以時間複雜度就可以降到 O(2nn) O ( 2 n n ) ，可以通過前四個測試點
算法四
為了取得更多的分，我們需要一個多項式算法
我們重新來考慮有限時間内熔化的條件：轉移無環
實際上這是一個很強的條件
根據轉移建一個新圖，如果 i i 不能看到jj，那麼就在 i i 到jj連條有向邊
這個新圖中可能有若幹個強連通分量，如果一個病變狀态中有病變的博弈的主人是在一個多于一個點的強連通分量中，那麼這一個狀态一定無法在有限時間内熔化（轉移有環），否則一定能在有限時間内熔化（轉移無環）
那麼我們先把所有可以到達大小大于1的強連通分量的點連同和他們相關的邊一起删掉，于是我們得到了一個DAG！
接着我們繼續站在這張圖的立場上來想怎麼求一個狀态的熔化時間：
首先這張圖上有一些點被染黑了，黑點表示這個博弈有病，白點表示這個博弈沒病
接着每一時刻，我們可以把一個黑點染白，然後把這個點連向的點的集合的一個子集染黑
若幹輪之後，所有點都變白了
假設 k k 個點一度被染黑，那麼熔化時間就是所有操作方案中最大的kk
看起來這個轉化比較意識流，但是如果我們考慮怎麼DP所有操作方案中最大的 k k ，我們會發現這個DP方法和算法二是等價的
如果再要解釋的話，首先枚舉博弈主人相當于枚舉反轉的黑點，算博弈主人熔化時間中的max展現在求最大的一度被染黑的點數，算狀态的熔化時間中對博弈主人熔化時間取min展現在多次被染黑的點隻被計算一次
而在這個模型下，算法三的小規律就很顯然了
增加黑點對答案的貢獻一定非負，是以問題又變成了：
一個DAG上有一些點被染黑了，接着每一時刻，我們可以把一個黑點染白，然後把這個點連向的點全部染黑。若幹輪之後，所有點都變白了
假設有k個點一度被染黑，求所有操作方案中最大的kk
這不就是求DAG上一個點集能直接或者間接到達的點數嗎？
是以我們把判斷一個病變狀态在第幾天熔化轉化為了求DAG上一個集合能直接或間接到達的點數。這樣第一問已經非常簡單了。考慮算每一個點的貢獻，如果一個點能被 i i 個點到達（包括自己），而DAG上一共有NN個點，那麼顯然這個點的貢獻就是 (2i−1)×2N−i ( 2 i − 1 ) × 2 N − i
接下來考慮第二問，一個人要在DAG上滿足什麼樣的條件才會在第一天熔化呢？
在原來的DP中，我們是在取min的過程中得到同時熔化的人數的，而我們知道，在現在的模型中，算狀态的熔化時間中對博弈主人熔化時間取min展現在多次被染黑的點隻被計算一次。
是以我們腦補一下可以得到：如果一個點第一個反轉，且之後得到的狀态無論怎麼操作都無法再把這個點染黑，那麼這個點對應着一個最早熔化的博弈主人。
是以第二問也可以很簡單的解決了，還是考慮算每一個點的貢獻，如果一個點能被 i i 個點到達（包括自己），而DAG上一共有NN個點，那麼顯然這個點的貢獻就是 2N−i 2 N − i
因為計算DAG中每一個點可以被多少點到達是 O(nm) O ( n m ) 的，而在這個DAG中 m m 是O(n2)O(n2)的，是以時間複雜度是 O(n3) O ( n 3 ) ，可以通過前六個點。
算法五
最後的技術含量就很低了，這個問題顯然是可以壓位的嘛，是以可以把時間複雜度搞到 O(n332) O ( n 3 32 ) ，可以通過所有測試點
#include <cstdio>
#include <bitset>
using namespace std;
typedef long long ll;
const int N = ;
const int mod = ;
bitset <N> b[N];
int d[N], que[N], g[N][N], n, m, t;
int pw2[N], ans1, ans2;
char s[N];
main() {
freopen("gay.in", "r", stdin);
freopen("gay.out", "w", stdout);
scanf("%d", &n);
for (int i = ; i <= n; ++i) {
scanf("%s", s + ), s[i] = '1';
for (int j = ; j <= n; ++j)
if (s[j] == '0')
d[i]++, g[i][j] = ;
}
pw2[] = ;
for (int i = ; i <= n; ++i) pw2[i] = (pw2[i - ] << ) % mod;
for (int i = ; i <= n; ++i) if (!d[i]) que[++t] = i;
for (int i = ; i <= t; ++i)
for (int j = , now = que[i]; j <= n; ++j)
if (g[j][now] && !--d[j]) que[++t] = j;
for (int i = t; i; --i) {
int now = que[i];
b[now][now] = ;
int cnt = b[now].count();
ans1 = (ans1 + l * (pw2[cnt] - ) * pw2[t - cnt]) % mod;
ans2 = (ans2 + pw2[t - cnt]) % mod;
for (int j = ; j <= n; ++j)
if (g[now][j]) b[j] |= b[now];
}
printf("%d %d\n", ans1, ans2);
}