最近咕咕了很多题目的题解，我来补锅了！！！
The Great Marathon
神仙题。。。
首先预处理两个点的最短路
然后枚举金牌最后一名和铜牌第一名，就可以确定每位选手能不能获得金银铜
然后考虑dp
(dp[i][j][k]) 表示选了 (i) 个人，当前有 (j) 个金，(k) 个银的方案数
具体实现见代码
ll f[N][N] ;
int g[N][N], Min[N], Max[N] ;
bool gold[N], silver[N], bronze[N] ;
int n, m, g1, g2, s1, s2 ;
ll ans ;
signed main() {
scanf("%d%d", &n, &m) ;
ass(g, 0x3f) ;
rep(i, 1, n) g[i][i] = 0 ;
rep(i, 1, m) {
int a, b, c ; scanf("%d%d%d", &a, &b, &c) ;
g[a][b] = g[b][a] = min(g[a][b], c) ;
}
rep(k, 1, n) rep(i, 1, n) rep(j, 1, n) chmin(g[i][j], g[i][k] + g[k][j]) ;
rep(i, 1, n) {
Min[i] = INF ; Max[i] = 0 ;
rep(j, 1, n)
if (i != j) {
g[i][j] = g[i][j] * 60 + i ;
chmax(Max[i], g[i][j]) ; chmin(Min[i], g[i][j]) ;
}
}
scanf("%d%d%d%d", &g1, &g2, &s1, &s2) ;
ans = 0 ;
rep(bst, 1, n) // gold last (ignore the vars' name)
rep(wst, 1, n) // bronze first
if (wst != bst && Min[bst] < Max[wst]) {
rep(i, 1, n) {
gold[i] = Min[i] <= Min[bst] ;
bronze[i] = Max[i] >= Max[wst] ;
silver[i] = false ;
rep(j, 1, n)
if (i != j && g[i][j] > Min[bst] && g[i][j] < Max[wst]) {
silver[i] = true ;
break ;
}
}
gold[bst] = true ; silver[bst] = bronze[bst] = false ;
gold[wst] = silver[wst] = false ; bronze[wst] = true ;
clr(f) ;
f[0][0] = 1 ;
rep(k, 1, n)
per(i, n, 0)
per(j, n, 0)
if (f[i][j]) {
if (gold[k]) add(f[i + 1][j], f[i][j]) ;
if (silver[k]) add(f[i][j + 1], f[i][j]) ;
if (!bronze[k]) f[i][j] = 0 ;
}
rep(i, g1, g2)
rep(j, s1, s2)
add(ans, f[i][j]) ;
}
printf("%lld
", ans) ;
return 0 ;
}
Destroying the bus station
写最小割的人的做法都是假的
vjudge 上已经有人给出了hack数据
但是贪心（网络流的实质是贪心）已经被否认，我们只能另寻它法
显然dp不太可靠，。。。（如果这能就神了）
虽然 (n<=50)，但是我们唯一的方法只有暴力！！！
上！！！搜索！！！
怎么搜就不用说了吧（自己看代码去）
套个迭代加深800ms通过
为什么搜索能通过？
- 当最短路还比较大的话，虽然可删的方案比较多，但我们搜索的层数不是很多
- 当最短路变小的时候，虽然层数加深，但是可删的边数会变少，我们距离成功也就越进
所以这是我们搜索的信心来源
int n, m, p, highest ;
int pre[N] ;
vi e[N] ;
int road[N][N] ;
bool del[N] ;
bool flg ;
void bfs() {
queue <int> q ;
clr(pre) ; pre[1] = -1 ;
q.push(1) ;
while (!q.empty()) {
int cur = q.front() ; q.pop() ;
rep(i, 0, siz(e[cur]) - 1) {
int to = e[cur][i] ;
if (!del[to] && !pre[to]) {
pre[to] = cur ;
q.push(to) ;
}
}
}
}
void dfs(int x) {
bfs() ;
if (!pre[n]) {
flg = 1 ;
return ;
}
int num = 0 ;
for (int i = n; i != -1; i = pre[i]) road[x][++num] = i ;
if (num - 1 > p) {
flg = 1 ;
return ;
}
if(x > highest) return ;
per(i, num - 1, 2) {
del[road[x][i]] = 1 ;
dfs(x + 1) ;
del[road[x][i]] = 0 ;
}
}
void init() {
flg = 0 ;
rep(i, 1, n) e[i].clear() ;
}
signed main() {
while (scanf("%d%d%d", &n, &m, &p) != EOF && n) {
init() ;
rep(i, 1, m) {
int u, v ; scanf("%d%d", &u, &v) ;
e[u].pb(v) ;
}
rep(i, 0, n - 2) {
highest = i ;
clr(del) ;
dfs(1) ;
if (flg) break ;
}
printf("%d
", highest) ;
}
return 0 ;
}
DrawingBlackCrosses
你大爷的又是状压dp
没怎么听懂qaq
大概就是枚举每个黑格子（?）的行和列是否被删然后转移
献上某神仙的代码（orz）
#define bitcnt(x) __builtin_popcount(x)
class DrawingBlackCrosses {
public:
int n, m, tot ;
int f[N][N], sumx[N], sumy[N] ;
bool validx[N], validy[N] ;
vii black ;
void reduce(int &x) { x += x >> 31 & mod ; }
bool check(int msk) {
rep(i, 0, n - 1) sumx[i] = 0 ;
rep(i, 0, m - 1) sumy[i] = 0 ;
rep(i, 0, tot - 1)
if (msk & (1 << i)) {
sumx[black[i].fi]++ ;
sumy[black[i].se]++ ;
}
int a = 0, b = 0 ;
rep(i, 0, n - 1)
if (!a) a = sumx[i] ;
else if (sumx[i] && a != sumx[i]) return 0 ;
rep(i, 0, m - 1)
if (!b) b = sumy[i] ;
else if (sumy[i] && b != sumy[i]) return 0 ;
return (a == 0 && b == 0 || b - a == n - m) && a * b == bitcnt(msk) ;
}
bool check(int S0, int S1) {
rep(i, 0, tot - 1)
if (S0 & (1 << i))
rep(j, 0, tot - 1)
if (S1 & (1 << j))
if (black[i].fi == black[j].fi || black[i].se == black[j].se)
return 0 ;
rep(i, 0, tot - 1)
if (S1 & (1 << i))
rep(j, i + 1, tot)
if (S1 & (1 << j))
if (black[i].fi == black[j].fi || black[i].se == black[j].se)
return 0 ;
return 1 ;
}
int count(vector <string> field) {
n = siz(field) ;
m = siz(field[0]) ;
rep(i, 0, n) f[i][0] = 1 ;
rep(i, 0, m) f[0][i] = 1 ;
rep(i, 1, n)
rep(j, 1, m)
f[i][j] = mulv(mulv(f[i - 1][j -1], i), j) ;
rep(i, 0, n - 1)
rep(j, 0, m - 1)
if (field[i][j] == 'B')
black.pb(mp(i, j)) ;
tot = siz(black) ;
int ans = 0 ;
rep(msk0, 0, (1 << tot) - 1)
if (check(msk0))
rep(msk1, 0, (1 << tot) - 1)
if (check(msk0, msk1)) {
clr(validx) ; clr(validy) ;
rep(i, 0, tot - 1)
if (msk0 & (1 << i))
validx[black[i].fi] = 1, validy[black[i].se] = 1 ;
rep(i, 0, tot - 1)
if (msk1 & (1 << i))
validx[black[i].fi] = 1, validy[black[i].se] = 1 ;
int a = n, b = m ;
rep(i, 0, n - 1) a -= validx[i] ;
rep(i, 0, m - 1) b -= validy[i] ;
int val = f[a][b], step = min(a, b) ;
rep(i, 1, bitcnt(msk1)) mul(val, step + i) ;
if (__builtin_parity(msk1)) sub(ans, val) ;
else add(ans, val) ;
}
return ans ;
}
} sol ;
Google Code Jam
还不错的好题
应该可以总结一种贪心的策略
只考虑那些 (0<P_i<1) 的大测试数据
考虑相邻两个题目优先完成的顺序的排序方式（什么鬼凑活理解一下吧）
假如是 (i,j)，如果 (i) 要在 (j) 前面，那么必须满足：
[(T_i+T_j)(1-P_j)+T_i(1-P_i)P_j<(T_i+T_j)(1-P_i)+T_j(1-P_j)P_i\
-P_j*T_j-T_i*P_j*P_i<-P_i*T_i-T_j*P_i*P_j\
T_i*P_i(1-P_j)<T_j*P_j(1-P_i)\
T_i*P_i/(1-P_i)<T_j*P_j(1-P_j)
]
我们就推出了 (i)在 (j) 之前需要满足的条件
这样就可以 (dp) 了
(dp[i][j][0/1]) 表示我们已经考虑了前 (i) 个题目，当前我们花费了 (j) 分钟所能够达到的最大期望分数/期望时间
此题卡精度，解决方案：乘大整数, 然后取整 (dp)
const int base = 1000000 ;
ll ss[N], sl[N], f[N], p[N], tl[N], ts[N] ;
int n, t, ord[N] ;
double pp[N], g[N] ;
double ans ;
bool cmp(int i, int j) {
return (tl[i] + tl[j]) * (base - p[j]) * base + tl[i] * p[j] * (base - p[i]) <
(tl[i] + tl[j]) * (base - p[i]) * base + tl[j] * p[i] * (base - p[j]) ;
}
void update(int x, ll v1, double v2) {
if (v1 > f[x] || v1 == f[x] && v2 < g[x]) f[x] = v1, g[x] = v2 ;
}
signed main() {
scanf("%d%d", &n, &t) ;
rep(i, 1, n) {
scanf("%lld%lld%lld%lld%lf", &ss[i], &sl[i], &ts[i], &tl[i], &pp[i]) ;
ord[i] = i ;
p[i] = (int) (pp[i] * base + 0.5) ;
}
sort(ord + 1, ord + n + 1, cmp) ;
rep(_, 1, n) {
int i = ord[_] ;
per(j, t, 0) {
if (j + ts[i] <= t) update(j + ts[i], f[j] + ss[i] * base, g[j] + ts[i]) ;
if (j + ts[i] + tl[i] <= t)
update(j + ts[i] + tl[i], f[j] + ss[i] * base + sl[i] * (base - p[i]),
ts[i] + g[j] * pp[i] + (j + tl[i]) * (1 - pp[i])) ;
}
}
ans = g[t] ;
rep(i, 0, t)
if (f[i] == f[t] && g[i] < ans)
ans = g[i];
printf("%.10lf %.10lf
", (double) f[t] / base, ans) ;
return 0 ;
}
Galaxy Union
树的部分直接换根dp
环two-pointers
口胡选手没写出来qaq
RoadsofKingdom
ntmd 怎么又是状压dp
树？合并？状压？还蛮好想到的吧（大雾）
对于一个状态msk，我们考虑子状态 (S_1,S_2=msk-S_1)，为了避免重复，可以固定 (u_1 in S_1, v_1 in S_2)
(S_1=u_1,u_2,...,u_n)
(S_2=v_1,v_2,...,v_m)
(f[msk]=f[S_1]*f[S_2]*sumlimits_{i=1}^m(p_{u_1,v_i}*sum_{x in S_2-v_i}(1-p_{u_1,x}))*prod_{i=2}^nprod_{x in S_2}(1-p_{u_i,x}))
自己理解一下吧。。。。公式是真的 (van♂)
class RoadsOfKingdom {
public:
int n ;
double dp[M], f1[M][N], f2[M][N], prob[N][N] ;
bool vis[M] ;
double dfs(int msk) {
if (vis[msk]) return dp[msk] ;
int p1 = -1, p2 = -1 ;
rep(i, 0, n - 1)
if (msk & (1 << i)) {
if (p1 == -1) p1 = i ;
else if (p2 == -1) { p2 = i ; break ; }
}
if (p2 == -1) return 1 ; // endings
int Msk = msk ^ (1 << p1) ^ (1 << p2) ;
double ans = 0 ;
for (int nmsk = Msk;; nmsk = (nmsk - 1) & Msk) {
int msk1 = nmsk | (1 << p1) ;
int msk2 = msk ^ msk1 ;
double tmp = 1 ;
rep(i, 0, n - 1)
if (p1 != i && (msk1 & (1 << i)))
tmp *= f1[msk2][i] ;
ans += dfs(msk1) * dfs(msk2) * f2[msk2][p1] * tmp ;
if (!nmsk) break ;
}
vis[msk] = 1 ;
return dp[msk] = ans ;
}
double getProbability(vector <string> roads) {
n = siz(roads) ;
rep(i, 0, n - 1)
rep(j, 0, n - 1)
prob[i][j] = (roads[i][j] - '0') / 8.0 ;
rep(i, 0, (1 << n) - 1)
rep(j, 0, n - 1) {
f1[i][j] = 1 ;
f2[i][j] = 0 ;
rep(k, 0, n - 1)
if (i & (1 << k)) {
f1[i][j] *= (1 - prob[k][j]) ;
f2[i][j] += f1[i ^ (1 << k)][j] * prob[j][k] ;
}
}
// cout << "???
" ;
return dfs((1 << n) - 1) ;
}
} sol ;
Levko and Sets
原根是什么qaq
这题先咕咕
Roadside Trees
线段树暴力维护前10小的数然后dp
#define ls(x) x << 1
#define rs(x) x << 1 | 1
struct tree {
int f[N] ;
void pushup(int p) { f[p] = max(f[ls(p)], f[rs(p)]) ; }
void update(int p, int l, int r, int x, int y) {
if (l == r) {
f[p] = y ;
return ;
}
int mid = l + r >> 1 ;
if (x <= mid) update(ls(p), l, mid, x, y) ;
else update(rs(p), mid + 1, r, x, y) ;
pushup(p) ;
}
int query(int p, int l, int r, int x, int y) {
if (x <= l && r <= y) return f[p] ;
int mid = l + r >> 1, ans = 0 ;
if (x <= mid) ans = max(ans, query(ls(p), l, mid, x, y)) ;
if (y > mid) ans = max(ans, query(rs(p), mid + 1, r, x, y)) ;
return ans ;
}
};
tree f, g ; // pos, height
int n, q ;
int pos[N], height[N], a[N] ;
set<int> s ;
int main() {
scanf("%d%d", &n, &q) ;
int m = delta + 10010 ;
while (q--) {
int op ; scanf("%d", &op) ;
if (op == 1) {
int p, h ;
scanf("%d%d", &p, &h) ; h += delta ;
s.insert(p) ;
pos[h] = p ;
height[p] = h ;
per(i,h, h - 9) {
if (!pos[i]) continue ;
int now = pos[i] ;
f.update(1, 1, n, now, 0) ;
g.update(1, 1, m, i, 0) ;
}
per(i, h, h - 9) {
if (!pos[i]) continue ;
int now = f.query(1, 1, n, pos[i] + 1, n) + 1 ;
f.update(1, 1, n, pos[i], now) ;
g.update(1, 1, m, i, now) ;
}
} else {
int k ; scanf("%d", &k) ;
auto it = s.begin() ;
int cnt = 0 ;
while (cnt < k) a[++cnt] = *it, ++it ;
--it ;
s.erase(it) ;
rep(i, 1, cnt) {
if (!height[a[i]]) continue ;
f.update(1, 1, n, a[i], 0) ;
g.update(1, 1, m, height[a[i]], 0) ;
}
per(i, cnt - 1, 1) {
if (!height[a[i]]) continue ;
int now = g.query(1, 1, m, height[a[i]] + 1, m) + 1 ;
f.update(1, 1, n, a[i], now) ;
g.update(1, 1, m, height[a[i]], now) ;
}
pos[height[a[cnt]]] = 0 ;
height[a[cnt]] = 0 ;
}
printf("%d
", f.f[1]) ;
delta-- ;
}
return 0 ;
}
Castles
太水了我tmd都不想写了
跟subway timing 做法类似
vi g[N] ;
int att[N], die[N], rem[N] ;
int n, ans ;
pii solve(int p, int fa) {
vii v ;
rep(i, 0, siz(g[p]) - 1) {
int to = g[p][i] ;
if (to == fa) continue ;
v.pb(solve(to, p)) ;
}
sort(all(v)) ;
pii res ;
res.se = max(att[p], rem[p] + die[p]) ;
res.fi = res.se - die[p] - rem[p] ;
per(i, siz(v) - 1, 0) {
pii cur = v[i] ;
int Rem = res.fi - cur.se ;
if (Rem >= 0) res.fi = Rem + cur.fi ;
else {
res.se -= Rem ;
res.fi = cur.fi ;
}
}
return res ;
}
signed main() {
int Case = 0 ;
while (scanf("%d", &n) != EOF && n) {
printf("Case %d: ", ++Case) ;
rep(i, 1, n) scanf("%d%d%d", &att[i], &die[i], &rem[i]) ;
rep(i, 1, n) g[i].clear() ;
rep(i, 1, n - 1) {
int x, y ; scanf("%d%d",&x, &y) ;
g[x].pb(y) ; g[y].pb(x) ;
}
ans = iinf ;
rep(i, 1, n) {
pii cur = solve(i, -1) ;
chmin(ans, cur.se) ;
}
printf("%d
", ans) ;
}
return 0 ;
}
Painting Graphs with AtcoDeer
群论。。。
首先tarjan处理出所有的点双联通分量
对于一个双联通分量，
- 如果边数<点数，可放任何颜色
- 边数=点数，有一个环，通过Burnside引理求
- 边数>点数，那么有多个环，用组合数求
int fac[N], inv[N] ;
int dfn[N], low[N], stk[N] ;
int n, m, k, tim, top, ans ;
vi e[N] ;
set <int> s ;
int C(int n, int k) {
return mulv(fac[n], mulv(inv[k], inv[n - k])) ;
}
int burnside(int n) {
int s = 0 ;
rep(i, 1, n) add(s, pw(k, __gcd(i, n))) ;
mul(s, pw(n, mod - 2)) ;
return s ;
}
void tarjan(int u) {
dfn[u] = low[u] = ++tim ;
stk[++top] = u ;
rep(i, 0, siz(e[u]) - 1) {
int to = e[u][i] ;
if (!dfn[to]) {
tarjan(to) ;
chmin(low[u], low[to]) ;
if (low[to] >= dfn[u]) {
s.clear() ; int t, nn, mm = 0 ;
do {
t = stk[top--] ;
s.insert(t) ;
} while (t != to) ;
s.insert(u) ;
nn = siz(s) ;
loop(it, s)
rep(i, 0, siz(e[*it]) - 1)
if (s.count(e[*it][i])) mm++ ;
mm /= 2 ;
if (mm < nn) mul(ans, k) ;
if (nn == mm) mul(ans, burnside(mm)) ;
if (nn < mm) mul(ans, C(mm + k - 1, k - 1)) ;
}
} else {
chmin(low[u], dfn[to]) ;
}
}
}
signed main() {
scanf("%d%d%d", &n, &m, &k) ;
rep(i, 1, m) {
int x, y ; scanf("%d%d", &x, &y) ;
e[x].pb(y) ; e[y].pb(x) ;
}
fac[0] = 1 ;
rep(i, 1, m + k) fac[i] = mulv(fac[i - 1], i) ;
inv[m + k] = pw(fac[m + k], mod - 2) ;
per(i, m + k, 1) inv[i - 1] = mulv(inv[i], i) ;
ans = 1 ;
rep(i, 1, n) if (!dfn[i]) tarjan(i) ;
printf("%d
", ans) ;
return 0 ;
}
TheContest
二分图匹配
神仙jt的假人做法，就是塞几个假人什么没怎么听懂qaq
typedef vector <string> vst ;
class TheContest {
public:
int vis[N], link[N] ;
int g[N][N] ;
int fix ;
int dfs(int u) {
if (u <= fix) return 0 ;
rep(v, 0, N - 10)
if (g[u][v] && !vis[v]) {
vis[v] = 1 ;
if (!~link[v] || dfs(link[v])) {
link[v] = u ;
link[u] = v ;
return 1 ;
}
}
return 0 ;
}
int ans[N][N], used[N][N], use[N][N] ;
int cnt[N] ;
vst getSchedule(int n, int m) {
int r = max(n, m) ;
rep(i, 1, n) {
clr(g) ;
rep(j, 1, m)
rep(k, 1, r) {
if (used[j][k]) continue ;
g[j][r + k] = 1 ;
}
rep(j, m + 1, r)
rep(k, 1, r)
if (m - cnt[k] < n - i + 1)
g[j][r + k] = 1 ;
vi anss ;
rep(j, 1, m) {
rep(k, 1, r)
if (g[j][k + r] && !use[i][k]) {
bool ok = 1 ;
ass(link, -1) ;
rep(l, 0, siz(anss) - 1) link[l + 1] = anss[l] + r,
link[anss[l] + r] = l + 1 ;
link[j] = k + r, link[k + r] = j ;
rep(l, j + 1, r) {
clr(vis) ;
fix = j ;
if (!dfs(l)) { ok = 0 ; break ; }
}
if (ok) {
use[i][k] = 1 ;
anss.pb(k) ;
cnt[k]++ ;
break ;
}
}
ans[i][j] = anss.back() ;
used[j][anss.back()] = 1 ;
}
}
vst res(n, string(m, '0')) ;
rep(i, 0, n - 1)
rep(j, 0, m - 1) {
if (ans[i + 1][j + 1] < 10) res[i][j] = '0' + ans[i + 1][j + 1] ;
else if (ans[i + 1][j + 1] < 36)
res[i][j] = 'A' + ans[i + 1][j + 1] - 10 ;
else res[i][j] = 'a' + ans[i + 1][j + 1] - 36 ;
}
return res ;
}
} sol ;
Subway Timing
二分+树形dp
题解咕咕
int f[N][M], tmp[M] ;
int n, mid ;
vii e[N] ;
int isok(int x) {
if (x >= -mid && x <= mid) return 1 ;
return 0 ;
}
void dfs(int x, int fa) {
rep(i, 0, mid) f[x][i] = -iinf ;
f[x][0] = 0 ;
rep(i, 0, siz(e[x]) - 1) {
int to = e[x][i].fi, w = e[x][i].se ;
if (to == fa) continue ;
dfs(to, x) ;
rep(j, 0, mid) {
tmp[j] = f[x][j] ;
f[x][j] = -iinf ;
}
rep(j, 0, mid)
if (tmp[j] != -iinf)
rep(k, 0, mid)
if (f[to][k] != iinf) {
if (isok(j + k - w) && isok(tmp[j] + f[to][k] - w))
chmax(f[x][max(j, k - w)], min(tmp[j], f[to][k] - w)) ;
w -= 60 ;
if (isok(j + k - w) && isok(tmp[j] + f[to][k] - w))
chmax(f[x][max(j, k - w)], min(tmp[j], f[to][k] - w)) ;
w += 60 ;
}
}
}
bool check(int mid) {
dfs(1, 0) ;
rep(i, 0, mid) if (f[1][i] > -iinf) return false ;
return true ;
}
signed main() {
int Case = 0 ;
while (scanf("%d", &n) && n) {
rep(i, 1, n) e[i].clear() ;
rep(i, 1, n - 1) {
int u, v, w ; scanf("%d%d%d", &u, &v, &w) ;
w %= 60 ;
e[u].pb(mp(v, w)) ;
e[v].pb(mp(u, w)) ;
}
int l = -1, r = 120 ;
while (l + 1 < r) { // 二分最小的代价
mid = (l + r) >> 1 ;
dfs(1, 0) ;
if (check(mid)) l = mid ;
else r = mid ;
}
printf("Case %d: %d
", ++Case, r) ;
}
return 0 ;
}
My bad
就是个模拟没什么好说的
大力枚举然后暴力check
古老代码
#include <iostream>
#include <string>
#include <string.h>
#include <stdlib.h>
using namespace std;
struct dat_edge {
int aim, last;
} edge[201];
int n, m, k, inde[101], coun[101], tmp_coun[101], pl[101], len_edge, num_key, key[300][101];
char kind[101];
void insert_edge(int x, int y) {
len_edge++;
edge[len_edge].aim = y;
edge[len_edge].last = pl[x];
pl[x] = len_edge;
}
void init(int o, string z) {
int p, i, num;
string t;
p = 1;
z += ' ';
for (i = 1; i < z.length(); i++)
if (z[i] == ' ') {
t = z.substr(p, i - p);
if (t[0] == 'i')
num = 0;
else
num = n;
if (t.length() == 2)
num += t[1] - '0';
else {
num += (t[1] - '0') * 10 + t[2] - '0';
}
coun[o]++;
insert_edge(num, o);
p = i + 1;
}
}
bool solve(int key[], int poi, int sta) {
int i, p, o, w, tmp, que[101], f[101];
for (i = 1; i <= n + m + k; i++) {
f[i] = 0;
}
for (i = 1; i <= n; i++) f[i] = key[i];
for (i = 1; i <= m; i++) {
if (kind[i] == 'a')
f[i + n] = 1;
else
f[i + n] = 0;
}
o = n;
w = 0;
for (i = 1; i <= n; i++) que[i] = i;
while (w < o) {
w++;
if (que[w] == poi) {
if (sta == 2)
f[que[w]] = !f[que[w]];
else
f[que[w]] = sta;
}
p = pl[que[w]];
while (p != -1) {
coun[edge[p].aim]--;
if (coun[edge[p].aim] == 0) {
que[++o] = edge[p].aim;
}
tmp = edge[p].aim;
if (kind[tmp - n] == 'a') {
if (f[que[w]] == 0)
f[tmp] = 0;
} else if (kind[tmp - n] == 'o') {
if (f[que[w]] == 1)
f[tmp] = 1;
} else if (kind[tmp - n] == 'x') {
f[tmp] = f[tmp] ^ f[que[w]];
} else {
f[tmp] = !f[que[w]];
}
p = edge[p].last;
}
}
for (i = 1; i <= n + m + k; i++) coun[i] = tmp_coun[i];
for (i = 1; i <= k; i++) {
if (f[inde[i] + n] != key[n + i])
return false;
}
return true;
}
void work(int t) {
int i, j, p, ans1, ans2, coun_ans;
bool ok = true;
for (i = 1; i <= num_key; i++) {
if (!solve(key[i], -1, -1)) {
ok = false;
break;
}
}
if (ok) {
cout << "Case " << t << ": No faults detected
";
return;
}
ans1 = ans2 = coun_ans = 0;
for (i = 1; i <= m; i++) {
for (j = 0; j <= 2; j++) {
ok = true;
for (p = 1; p <= num_key; p++) {
ok = solve(key[p], i + n, j);
if (!ok)
break;
}
if (ok) {
ans1 = i;
ans2 = j;
coun_ans++;
}
}
}
if (coun_ans != 1) {
cout << "Case " << t << ": Unable to totally classify the failure
";
return;
}
if (ans2 == 2) {
cout << "Case " << t << ": Gate " << ans1 << " is failing; output inverted
";
return;
}
if (ans2 == 0) {
cout << "Case " << t << ": Gate " << ans1 << " is failing; output stuck at 0
";
return;
}
if (ans2 == 1) {
cout << "Case " << t << ": Gate " << ans1 << " is failing; output stuck at 1
";
return;
}
}
int main() {
int t, i, j;
string z;
t = 0;
while (cin >> n >> m >> k && n + m + k != 0) {
t++;
memset(coun, 0, sizeof(coun));
len_edge = -1;
for (i = 1; i <= n + m + k; i++) pl[i] = -1;
for (i = 1; i <= m; i++) {
cin >> kind[i];
getline(cin, z);
init(i + n, z);
}
for (i = 1; i <= n + m + k; i++) tmp_coun[i] = coun[i];
for (i = 1; i <= k; i++) cin >> inde[i];
cin >> num_key;
for (i = 1; i <= num_key; i++)
for (j = 1; j <= n + k; j++) cin >> key[i][j];
work(t);
}
return 0;
}
The Great Wall Game
嘿嘿嘿我喜欢网络流
神仙 (ycs) 用状压 (dp)(f**k it) 秒了此题
我这个菜鸡只会费用流
暴力枚举最多32种最终状态
- 建立超级源和超级汇
- 将所有的目标节点和超级汇连边 ((0,1))
- 将超级源和初始节点连边 ((0,1))
- 将初始节点和所有目标节点连边 ((dis(i,j),inf))
- 跑最小费用最大流
int n, m, cur, ans, top, s = 31, t = 32 ;
int head[N], pre[N], x[N], y[N], vis[N], dis[N] ;
struct Edge {
int fr, to, nxt, val, len ;
} e[M] ;
void add(int a, int b, int c, int d) {
e[++top] = (Edge) {a, b, head[a], c, d} ; head[a] = top ;
e[++top] = (Edge) {b, a, head[b], -c, 0} ; head[b] = top ;
}
void init() {
clr(head) ; top = 1 ;
cur = 0 ;
}
int spfa() {
queue <int> q ; while (!q.empty()) q.pop() ;
ass(dis, 0x3f) ; clr(pre) ;
q.push(s) ; dis[s] = 0 ;
bool flg = 0 ;
while (!q.empty()) {
int u = q.front() ; q.pop() ;
if (u == t) flg = 1 ;
vis[u] = false ;
cont(i, u) {
int to = e[i].to ;
if (!e[i].len) continue ;
if (dis[u] + e[i].val < dis[to]) {
dis[to] = dis[u] + e[i].val ;
pre[to] = i ;
if (!vis[to]) {
vis[to] = 1 ;
q.push(to) ;
}
}
}
}
return flg ;
}
void EK() {
while (spfa()) {
for (int i = pre[t]; i; i = pre[e[i].fr]) {
e[i].len-- ; e[i ^ 1].len++ ;
cur += e[i].val ;
}
}
chmin(ans, cur) ;
}
void horizontal(int l) {
init() ;
rep(i, 1, n) add(i, t, 0, 1) ;
rep(i, 1, n) {
add(s, i + n, 0, 1) ;
rep(j, 1, n) add(i + n, j, abs(x[i] - l) + abs(y[i] - j), 100) ;
}
EK() ;
}
void vertical(int l) {
init() ;
rep(i, 1, n) add(i, t, 0, 1) ;
rep(i, 1, n) {
add(s, i + n, 0, 1) ;
rep(j, 1, n) add(i + n, j, abs(x[i] - j) + abs(y[i] - l), 100) ;
}
EK() ;
}
void diagonal() {
init() ;
rep(i, 1, n) add(i, t, 0, 1) ;
rep(i, 1, n) {
add(s, i + n, 0, 1) ;
rep(j, 1, n)
add(i + n, j, abs(x[i] - j) + abs(y[i] - (n - j + 1)), 100) ;
}
EK() ;
init() ;
rep(i, 1, n) add(i, t, 0, 1) ;
rep(i, 1, n) {
add(s, i + n, 0, 1) ;
rep(j, 1, n)
add(i + n, j, abs(x[i] - j) + abs(y[i] - j), 100) ;
}
EK() ;
}
signed main() {
int Case = 0 ;
while (scanf("%d", &n) != EOF && n) {
rep(i, 1, n) scanf("%d%d", &x[i], &y[i]) ;
ans = iinf ;
rep(i, 1, n) horizontal(i) ;
rep(i, 1, n) vertical(i) ;
diagonal() ;
printf("Board %d: %d moves required.
", ++Case, ans) ;
}
return 0 ;
}
Battle of the triangle
二分gg
Strings of Eternity
(KMP+dp) 裸题
(mathsf{Rolling~Hash}) 和 (mathsf{Z~Function}) 也都行
char s[N], t[N] ;
int n, m, k, ans ;
int fail[N], dp[N] ;
signed main() {
scanf("%s%s", s + 1, t + 1) ;
k = strlen(s + 1), n = k, m = strlen(t + 1) ;
while (n < m * 2) {
rep(i, 1, n) s[n + i] = s[i] ;
n *= 2 ;
}
rep(i, 1, n) s[n + i] = s[i] ; n *= 2 ;
fail[0] = -1 ;
rep(i, 1, m) {
int j = i - 1 ;
for (; j && t[fail[j] + 1] != t[i]; j = fail[j]) ;
fail[i] = fail[j] + 1 ;
}
int j = 0 ;
rep(i, 1, n) {
for (; ~j && s[i] != t[j + 1]; j = fail[j]) ;
j++ ;
if (j == m) dp[i] = dp[i - m] + 1, chmax(ans, dp[i]) ;
}
if (ans >= n / m - 1) ans = -1 ;
printf("%d
", ans) ;
return 0 ;
}