∆ P3600 随机数生成器 - AC
记：
因为我们最后取的是 ，不能直接用全概率公式，转化一下：
这意味着每一个被询问区间中的最小值都需 。也就是说，每一个区间至少需要一个 的数。
这对于每一个区间来说概率为 。又因为区间可能出现相交，所以我们考虑用点去被包含于区间。
当然，一个区间包含另一个区间，这个区间肯定是没有用的。然后把区间按左右端点分别为第一、第二关键字排序。
枚举 ，设 表示区间右端点在 之前的所有区间满足条件的概率。
#include <cstdio>
using i64 = long long;
const int MOD = 666623333;
const int MAXN = 2e3 + 5;
int n, x, q, ar[MAXN];
i64 f[MAXN][2], ff[MAXN][2];
void imax ( int& a, const int b ) { a = a < b ? b : a; }
int add ( const int a, const int b, const int p = MOD ) { return a + b < p ? a + b : ( a + b ) % p; }
int sub ( const int a, const int b, const int p = MOD ) { return a - b < 0 ? a - b + p : a - b; }
int mul ( const i64 a, const i64 b, const int p = MOD ) { return a * b % p; }
int cpow ( int bas, int idx = MOD - 2 ) {
int res = 1;
while ( idx ) {
if ( idx & 1 ) res = mul ( res, bas );
bas = mul ( bas, bas ), idx >>= 1;
}
return res % MOD;
}
int main () {
scanf ( "%d%d%d", &n, &x, &q );
for ( int i = 1, tmpl, tmpr; i <= q; ++ i ) scanf ( "%d%d", &tmpl, &tmpr ), imax ( ar[tmpr + 1], tmpl );
for ( int i = 1; i <= n + 1; ++ i ) imax ( ar[i], ar[i - 1] );
i64 ix = cpow ( x ), ans = 0;
for ( int i = 1; i <= x; ++ i ) {
i64 p = mul ( i - 1, ix ) % MOD, ip = cpow ( 1 - p ), s;
ff[0][0] = ff[0][1] = 1;
for ( int j = 1; j <= n; ++ j ) ff[j][0] = mul ( ff[j - 1][0], 1 - p ) % MOD, ff[j][1] = mul ( ff[j - 1][1], ip ) % MOD;
f[0][0] = 0, f[0][1] = 1;
for ( int j = 1; j <= n; ++ j ) {
f[j][0] = mul ( mul ( p, sub ( f[j - 1][1], ar[j] ? f[ar[j] - 1][1] : 0 ) ) % MOD, ff[j - 1][0] ) % MOD;
f[j][1] = add ( mul ( f[j][0], ff[j][1] ) % MOD, f[j - 1][1] ) % MOD;
}
s = 0;
for ( int j = ar[n + 1]; j <= n; ++ j ) s = add ( s, mul ( f[j][0], ff[n - j][0] ) % MOD ) % MOD;
ans = sub ( add ( ans, 1 ) % MOD, s );
}
printf ( "%lld\n", ans % MOD );
return 0;
}
∆ P3602 Koishi Loves Segments - AC
依次加入线段（从左到右），然后若有一个点不合删其右端点最远。
#include<bits/stdc++.h>
struct seg{int l,r;bool operator<(seg t){return l<t.l;}}s1[500010],s2[500010];int n,m;std::multiset<int>ms;
int main(){
std::cin>>n>>m;for(int i=1;i<=n;++i)std::cin>>s1[i].l>>s1[i].r;int ans=0;
for(int i=1;i<=m;++i)std::cin>>s2[i].l>>s2[i].r;std::sort(s1+1,s1+1+n);std::sort(s2+1,s2+1+m);
for(int l=1,r=1;l<=m;++l){
while(r<=n&&s1[r].l<=s2[l].l)ms.insert(s1[r++].r);
while(ms.size()&&*ms.begin()<s2[l].l)ms.erase(ms.begin());
while(ms.size()>s2[l].r)ms.erase(std::prev(ms.end())),ans++;
}std::cout<<n-ans;
}
∆ P4127 [AHOI2009]同类分布 - AC
vector 慢成仙人。
#include <bits/stdc++.h>
using i64 = long long;
i64 a, b, f[20][200][200], ori[20];
i64 dfs ( const int pos, const int sum, const i64 num, const int lim, const int len, const int mod ) {
if ( ( pos > len && ! sum ) || sum + 9 * len < mod ) return 0;
if ( pos > len ) return ! num && sum == mod;
if ( ! lim && ~ f[pos][sum][num] ) return f[pos][sum][num];
i64 res = 0;
int mx = lim ? ori[len - pos] : 9;
for ( int i = 0; i <= mx; ++ i ) res += dfs ( pos + 1, sum + i, ( num * 10 + i ) % mod, lim && i == mx, len, mod );
return lim ? res : f[pos][sum][num] = res;
}
i64 solve ( const i64 val ) {
i64 tmp = val;
int len = 0;
for ( ; tmp; tmp /= 10 ) ori[len ++] = tmp % 10;
i64 res = 0;
for ( int MOD = 1; MOD <= 9 * len; ++ MOD ) {
memset ( f, -1, sizeof f );
res += dfs ( 1, 0, 0, 1, len, MOD );
}
return res;
}
int main () {
std::ios::sync_with_stdio ( 0 ); std::cin.tie ( 0 ); std::cout.tie ( 0 );
std::cin >> a >> b;
std::cout << solve ( b ) - solve ( a - 1 ) << '\n';
return 0;
}
∆ P3603 雪辉 - AC
疑似是树分块板？
#include <bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
std::mt19937_64 randomEngine ( time ( 0 ) );
int calcRND ( const int l, const int r ) {
std::uniform_int_distribution<long long> distribution ( l, r );
int randomNumber = distribution ( randomEngine );
return randomNumber;
}
const int MAXN = 1e5 + 5, MAXS = 330;
const i64 one64 = 1ll;
char gtc () { return getchar (); }
int rint () {
int x = 0, f = 1; char c = gtc ();
for ( ; c < '0' || c > '9'; c = gtc () ) f = c == '-' ? -1 : f;
for ( ; c >= '0' && c <= '9'; c = gtc () ) x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
return x * f;
}
void ptc ( const char x ) { putchar ( x ); }
void wint ( int x ) {
if ( x < 0 ) ptc ( '-' ), x = ~ x + 1;
if ( x > 9 ) wint ( x / 10 );
ptc ( x % 10 ^ '0' );
}
template<typename _T> _T imax ( const _T x, const _T y ) { return x < y ? y : x; }
template<typename _T> void swapp ( _T& x, _T& y ) { _T w = x; x = y; y = w; }
struct prBitS {
u64 c[500]; int L;
prBitS () : L ( 0 ), c ( { 0 } ) {}
void clear () { memset ( c, 0, sizeof c ), L = 0; }
void operator |= ( const prBitS& t ) { L = imax ( L, t.L ); for ( int i = 0; i <= L; ++ i ) c[i] |= t.c[i]; }
void operator |= ( const int& x ) { L = imax ( L, x >> 6 ); c[x >> 6] |= one64 << ( x & 63 ); }
int calc_num () {
int res = 0;
for ( int i = 0; i <= L; ++ i ) for ( int j = 0; j < 64; ++ j ) {
if ( c[i] & ( one64 << j ) ) ++ res;
}
return res;
}
int calc_mex () {
for ( int i = 0; i <= L; ++ i ) for ( int j = 0; j < 64; ++ j ) {
if ( ! ( c[i] & ( one64 << j ) ) ) return i * 64 + j;
}
return 0;
}
} bs[MAXS][MAXS];
struct Edge { int to, nxt; } graph[MAXN * 2];
int n, m, head[MAXN], ecnt, kfa[MAXN][21], a[MAXN], dep[MAXN], used[MAXN], kSet[MAXN], rk[MAXN], ar[MAXN];
void link ( const int u, const int v ) { graph[++ ecnt] = { v, head[u] }, head[u] = ecnt; }
void dfs ( const int u, const int pr ) {
dep[u] = dep[pr] + 1, kfa[u][0] = pr;
for ( int i = 1; i <= 20; ++ i ) kfa[u][i] = kfa[kfa[u][i - 1]][i - 1];
for ( int i = head[u]; i; i = graph[i].nxt ) {
int v = graph[i].to;
if ( v != pr ) dfs ( v, u );
}
}
int calcLCA ( int u, int v ) {
if ( dep[u] < dep[v] ) swapp ( u, v );
for ( int i = 20; ~ i; -- i ) {
if ( dep[kfa[u][i]] >= dep[v] ) u = kfa[u][i];
}
if ( u == v ) return u;
for ( int i = 20; ~ i; -- i ) {
if ( kfa[u][i] != kfa[v][i] ) u = kfa[u][i], v = kfa[v][i];
}
return kfa[u][0];
}
void initial () {
int S = sqrt ( n );
for ( int i = 1; i <= S; ++ i ) {
int p = calcRND ( 1, n );
while ( used[p] ) p = calcRND ( 1, n );
used[p] = 1, kSet[i] = p, rk[p] = i;
}
prBitS p_bs;
for ( int i = 1; i <= S; ++ i ) {
p_bs.clear ();
int cur = kSet[i], first = 1;
while ( cur || first ) {
p_bs |= a[cur];
if ( cur != kSet[i] && rk[cur] ) {
bs[i][rk[cur]] |= p_bs;
if ( ! ar[kSet[i]] ) ar[kSet[i]] = cur;
}
cur = kfa[cur][0];
first = 0;
}
}
}
void jumpAncestors ( int& x, prBitS& ans, const int z ) {
while ( ! ar[x] && x != z ) ans |= a[x], x = kfa[x][0];
int cur = x;
while ( dep[ar[x]] > dep[z] ) x = ar[x];
ans |= bs[rk[cur]][rk[x]];
while ( x != z ) ans |= a[x], x = kfa[x][0];
}
int main () {
n = rint (), m = rint (); int f = rint ();
for ( int i = 1; i <= n; ++ i ) a[i] = rint ();
for ( int i = 1; i < n; ++ i ) {
int u = rint (), v = rint ();
link ( u, v ), link ( v, u );
}
dfs ( 1, 0 ), initial (); int las = 0; prBitS ans;
for ( int i = 1; i <= m; ++ i ) {
ans.clear ();
for ( int T = rint (); T; T -- ) {
int x = rint (), y = rint ();
if ( f ) x ^= las, y ^= las;
int z = calcLCA ( x, y ); ans |= a[z];
jumpAncestors ( x, ans, z ), jumpAncestors ( y, ans, z );
}
int ret_n = ans.calc_num (), ret_m = ans.calc_mex ();
wint ( ret_n ), ptc ( ' ' ), wint ( ret_m ), ptc ( '\n' );
las = ret_n + ret_m;
}
return 0;
}
∆ LOC3564 最小费用流 - AC
流 板。
#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<i64, i64>;
const i64 INF = 1e18;
const int MAXN = 2e5 + 5, MAXM = 2e5 + 5;
i64 rint () {
i64 x = 0, f = 1; char c = getchar ();
for ( ; c < '0' || c > '9'; c = getchar () ) f = c == '-' ? -1 : f;
for ( ; c >= '0' && c <= '9'; c = getchar () ) x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
return x * f;
}
template<typename _T> _T imin ( const _T x, const _T y ) { return x < y ? x : y; }
struct Edge { int to, nxt; i64 c, w; } graph[MAXM * 2];
int q[MAXN];
i64 dist[MAXN];
int n, m, head[MAXN], cur[MAXN], ecnt = 1, vis[MAXN], tot;
void link ( const int u, const int v, const i64 c, const i64 w ) {
graph[++ ecnt] = { v, head[u], c, w }, head[u] = ecnt;
graph[++ ecnt] = { u, head[v], 0, -w }, head[v] = ecnt;
}
bool mkLayer ( const int S, const int T ) {
int h = 1, t = 0;
for ( int i = 1; i <= tot; ++ i ) dist[i] = INF, vis[i] = 0;
dist[q[++ t] = S] = 0, vis[S] = 1;
while ( h <= t ) {
int u = q[h ++]; vis[u] = 0;
for ( int i = head[u]; i; i = graph[i].nxt ) {
int v = graph[i].to; i64 c = graph[i].c, w = graph[i].w;
if ( c && dist[v] > dist[u] + w ) {
dist[v] = dist[u] + w;
if ( ! vis[v] ) vis[q[++ t] = v] = 1;
}
}
}
return dist[T] < INF;
}
i64 mkWide ( const int u, const i64 flow, const int T, i64& cst ) {
if ( u == T ) return flow;
i64 used = 0; vis[u] = 1;
for ( int& i = cur[u]; i; i = graph[i].nxt ) {
int v = graph[i].to; i64 c = graph[i].c, w = graph[i].w;
if ( c && ! vis[v] && dist[v] == dist[u] + w ) {
i64 ret = mkWide ( v, imin ( flow - used, c ), T, cst );
graph[i].c -= ret, graph[i ^ 1].c += ret, used += ret, cst += ret * w;
if ( flow == used ) break;
}
}
if ( used < flow ) dist[u] = INF;
vis[u] = 0; return used;
}
pii calcMXflow ( const int S, const int T ) {
i64 retf = 0, retw = 0;
while ( mkLayer ( S, T ) ) {
for ( int i = 1; i <= tot; ++ i ) vis[i] = 0, cur[i] = head[i];
retf += mkWide ( S, INF, T, retw );
}
return { retf, retw };
}
int main () {
n = rint (), m = rint (); tot = n;
const int S = 1, T = n;
for ( int i = 1; i <= m; ++ i ) {
int u = rint (), v = rint ();
i64 c = rint (), w = rint ();
link ( u, v, c, w );
}
pii ret = calcMXflow ( S, T );
printf ( "%lld %lld\n", ret.first, ret.second );
return 0;
}
∆ LOC3102 网络流 24 题 运输问题
流 板。
#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<i64, i64>;
const i64 INF = 1e18;
const int MAXN = 1e5 + 5, MAXM = 1e6 + 5, MAXS = 2e3 + 5;
char gtc () { return getchar (); }
void ptc ( const char x ) { putchar ( x ); }
int rint () {
int x = 0, f = 1; char c = gtc ();
for ( ; c < '0' || c > '9'; c = gtc () ) f = c == '-' ? -1 : f;
for ( ; c >= '0' && c <= '9'; c = gtc () ) x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
return x * f;
}
template<typename _T> _T imin ( const _T x, const _T y ) { return x < y ? x : y; }
struct Edge { int to, nxt; i64 c, w; } graph[MAXM * 2];
i64 dist[MAXN]; int q[MAXN];
int n, m, head[MAXN], ecnt = 1, cur[MAXN], vis[MAXN], tot;
int arA[MAXN], arB[MAXN], arC[MAXS][MAXS];
void link ( const int u, const int v, const i64 c, const i64 w ) {
graph[++ ecnt] = { v, head[u], c, w }, head[u] = ecnt;
graph[++ ecnt] = { u, head[v], 0, -w }, head[v] = ecnt;
}
bool mkLayer ( const int S, const int T ) {
int h = 1, t = 0;
for ( int i = 1; i <= tot; ++ i ) vis[i] = 0, dist[i] = INF;
dist[q[++ t] = S] = 0, vis[S] = 1;
while ( h <= t ) {
int u = q[h ++]; vis[u] = 0;
for ( int i = head[u]; i; i = graph[i].nxt ) {
int v = graph[i].to; i64 c = graph[i].c, w = graph[i].w;
if ( c && dist[v] > dist[u] + w ) {
dist[v] = dist[u] + w;
if ( ! vis[v] ) vis[q[++ t] = v] = 1;
}
}
}
return dist[T] < INF;
}
i64 mkWide ( const int u, const i64 flow, const int T, i64& cst ) {
if ( u == T ) return flow;
i64 used = 0; vis[u] = 1;
for ( int& i = cur[u]; i; i = graph[i].nxt ) {
int v = graph[i].to; i64 c = graph[i].c, w = graph[i].w;
if ( c && dist[v] == dist[u] + w && ! vis[v] ) {
i64 ret = mkWide ( v, imin ( flow - used, c ), T, cst );
graph[i].c -= ret, graph[i ^ 1].c += ret, used += ret, cst += ret * w;
if ( flow == used ) break;
}
}
if ( used < flow ) dist[u] = INF;
vis[u] = 0; return used;
}
pii calcMXflow ( const int S, const int T ) {
i64 retf = 0, retw = 0;
while ( mkLayer ( S, T ) ) {
for ( int i = 1; i <= tot; ++ i ) vis[i] = 0, cur[i] = head[i];
retf += mkWide ( S, INF, T, retw );
}
return { retf, retw };
}
void buildEdge ( const int S, const int T, const int f ) {
memset ( head, 0, sizeof head ), ecnt = 1;
for ( int i = 1; i <= n; ++ i ) link ( S, i, arA[i], 0 );
for ( int i = 1; i <= m; ++ i ) link ( i + n, T, arB[i], 0 );
for ( int i = 1; i <= n; ++ i ) for ( int j = 1; j <= m; ++ j ) link ( i, j + n, INF, f * arC[i][j] );
}
int main () {
n = rint (), m = rint (); tot = n + m;
const int S = ++ tot, T = ++ tot;
for ( int i = 1, c; i <= n; ++ i ) arA[i] = rint ();
for ( int i = 1, c; i <= m; ++ i ) arB[i] = rint ();
for ( int i = 1; i <= n; ++ i ) for ( int j = 1; j <= m; ++ j ) arC[i][j] = rint ();
buildEdge ( S, T, 1 ), printf ( "%lld\n", calcMXflow ( S, T ).second );
buildEdge ( S, T, -1 ), printf ( "%lld\n", calcMXflow ( S, T ).second * -1 );
return 0;
}
∆ LOC9382 网络流 24 题 负载平衡问题 - AC
流 板。
#include <bits/stdc++.h>
using pii = std::pair<int, int>;
const int INF = 1e9;
const int MAXN = 1e5 + 5, MAXM = 1e6 + 5;
char gtc () { return getchar (); }
void ptc ( const char x ) { putchar ( x ); }
int rint () {
int x = 0, f = 1; char c = gtc ();
for ( ; c < '0' || c > '9'; c = gtc () ) f = c == '-' ? -1 : f;
for ( ; c >= '0' && c <= '9'; c = gtc () ) x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
return x * f;
}
template<typename _T> _T imin ( const _T x, const _T y ) { return x < y ? x : y; }
struct Edge { int to, nxt; int c, w; } graph[MAXM * 2];
int dist[MAXN], all; int q[MAXN];
int n, head[MAXN], cur[MAXN], ecnt = 1, vis[MAXN], tot;
void link ( const int u, const int v, const int c, const int w ) {
graph[++ ecnt] = { v, head[u], c, w }, head[u] = ecnt;
graph[++ ecnt] = { u, head[v], 0, -w }, head[v] = ecnt;
}
bool mkLayer ( const int S, const int T ) {
int h = 1, t = 0;
for ( int i = 1; i <= tot; ++ i ) dist[i] = INF, vis[i] = 0;
dist[q[++ t] = S] = 0, vis[S] = 1;
while ( h <= t ) {
int u = q[h ++]; vis[u] = 0;
for ( int i = head[u]; i; i = graph[i].nxt ) {
int v = graph[i].to; int c = graph[i].c, w = graph[i].w;
if ( c && dist[v] > dist[u] + w ) {
dist[v] = dist[u] + w;
if ( ! vis[v] ) vis[q[++ t] = v] = 1;
}
}
}
return dist[T] < INF;
}
int mkWide ( const int u, const int flow, const int T, int& cst ) {
if ( u == T ) return flow;
int used = 0; vis[u] = 1;
for ( int& i = cur[u]; i; i = graph[i].nxt ) {
int v = graph[i].to; int c = graph[i].c, w = graph[i].w;
if ( c && dist[v] == dist[u] + w && ! vis[v] ) {
int ret = mkWide ( v, imin ( flow - used, c ), T, cst );
graph[i].c -= ret, graph[i ^ 1].c += ret, used += ret, cst += ret * w;
if ( flow == used ) break;
}
}
if ( used < flow ) dist[u] = INF;
vis[u] = 0; return used;
}
pii calcMXflow ( const int S, const int T ) {
int resf = 0, resw = 0;
while ( mkLayer ( S, T ) ) {
for ( int i = 1; i <= tot; ++ i ) vis[i] = 0, cur[i] = head[i];
resf += mkWide ( S, INF, T, resw );
}
return { resf, resw };
}
int main () {
n = rint (), tot = n;
const int S = ++ tot, T = ++ tot;
for ( int i = 1; i <= n; ++ i ) {
int c = rint ();
link ( S, i, c, 0 );
all += c;
}
for ( int i = 1; i <= n; ++ i ) link ( i, i % n + 1, INF, 1 ), link ( i % n + 1, i, INF, 1 );
for ( int i = 1; i <= n; ++ i ) link ( i, T, all / n, 0 );
printf ( "%d\n", calcMXflow ( S, T ).second );
return 0;
}
∆ LOC3103 网络流 24 题 分配问题 - AC
流 板。
#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<i64, i64>;
const i64 INF = 1e18;
const int MAXN = 1e5 + 5, MAXM = 1e6 + 5, MAXS = 2e3 + 5;
char gtc () { return getchar (); }
void ptc ( const char x ) { putchar ( x ); }
int rint () {
int x = 0, f = 1; char c = gtc ();
for ( ; c < '0' || c > '9'; c = gtc () ) f = c == '-' ? -1 : f;
for ( ; c >= '0' && c <= '9'; c = gtc () ) x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
return x * f;
}
template<typename _T> _T imin ( const _T x, const _T y ) { return x < y ? x : y; }
struct Edge { int to, nxt; i64 c, w; } graph[MAXM * 2];
i64 dist[MAXN]; int q[MAXN];
int n, head[MAXN], cur[MAXN], ecnt = 1, vis[MAXN], tot;
int ar[MAXS][MAXS];
void link ( const int u, const int v, const i64 c, const i64 w ) {
graph[++ ecnt] = { v, head[u], c, w }, head[u] = ecnt;
graph[++ ecnt] = { u, head[v], 0, -w }, head[v] = ecnt;
}
bool mkLayer ( const int S, const int T ) {
int h = 1, t = 0;
for ( int i = 1; i <= tot; ++ i ) dist[i] = INF, vis[i] = 0;
dist[q[++ t] = S] = 0, vis[S] = 1;
while ( h <= t ) {
int u = q[h ++]; vis[u] = 0;
for ( int i = head[u]; i; i = graph[i].nxt ) {
int v = graph[i].to; i64 c = graph[i].c, w = graph[i].w;
if ( c && dist[v] > dist[u] + w ) {
dist[v] = dist[u] + w;
if ( ! vis[v] ) vis[q[++ t] = v] = 1;
}
}
}
return dist[T] < INF;
}
i64 mkWide ( const int u, const i64 flow, const int T, i64& cst ) {
if ( u == T ) return flow;
i64 used = 0; vis[u] = 1;
for ( int& i = cur[u]; i; i = graph[i].nxt ) {
int v = graph[i].to; i64 c = graph[i].c, w = graph[i].w;
if ( c && dist[v] == dist[u] + w && ! vis[v] ) {
i64 ret = mkWide ( v, imin ( flow - used, c ), T, cst );
graph[i].c -= ret, graph[i ^ 1].c += ret, used += ret, cst += ret * w;
if ( flow == used ) break;
}
}
if ( used < flow ) dist[u] = INF;
vis[u] = 0; return used;
}
pii calcMXflow ( const int S, const int T ) {
i64 resf = 0, resw = 0;
while ( mkLayer ( S, T ) ) {
for ( int i = 1; i <= tot; ++ i ) cur[i] = head[i], vis[i] = 0;
resf += mkWide ( S, INF, T, resw );
}
return { resf, resw };
}
void buildEdge ( const int S, const int T, const int f ) {
memset ( head, 0, sizeof head ), ecnt = 1;
for ( int i = 1; i <= n; ++ i ) link ( S, i, 1, 0 );
for ( int i = 1; i <= n; ++ i ) link ( i + n, T, 1, 0 );
for ( int i = 1; i <= n; ++ i ) for ( int j = 1; j <= n; ++ j ) link ( i, j + n, 1, f * ar[i][j] );
}
int main () {
n = rint (), tot = n << 1;
const int S = ++ tot, T = ++ tot;
for ( int i = 1; i <= n; ++ i ) for ( int j = 1; j <= n; ++ j ) ar[i][j] = rint ();
buildEdge ( S, T, 1 ), printf ( "%lld\n", calcMXflow ( S, T ).second );
buildEdge ( S, T, -1 ), printf ( "%lld\n", calcMXflow ( S, T ).second * -1 );
return 0;
}
∆ P4068 [SDOI2016]数字配对 - AC
首先我们可以处理出来哪些数字之间可以进行配对。
处理出每一个数的质因子的指数数值和（也就是 ）记为 ，然后把 奇数放左边偶数放右边放出二分图。
负数不管。
fuck everybody here。
#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<i64, i64>;
const i64 INF = 1e18;
const int MAXN = 1e5 + 5, MAXM = 1e6 + 5;
char gtc () { return getchar (); }
void ptc ( const char x ) { putchar ( x ); }
int rint () {
int x = 0, f = 1; char c = gtc ();
for ( ; c < '0' || c > '9'; c = gtc () ) f = c == '-' ? -1 : f;
for ( ; c >= '0' && c <= '9'; c = gtc () ) x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
return x * f;
}
template<typename _T> _T imin ( const _T x, const _T y ) { return x < y ? x : y; }
struct Edge { int to, nxt; i64 c, w; } graph[MAXM * 2];
i64 dist[MAXN]; int q[MAXN];
int n, head[MAXN], cur[MAXN], ecnt = 1, vis[MAXN], tot, idx[MAXN];
int arA[MAXN], arB[MAXN], arC[MAXN];
void link ( const int u, const int v, const i64 c, const i64 w ) {
graph[++ ecnt] = { v, head[u], c, w }, head[u] = ecnt;
graph[++ ecnt] = { u, head[v], 0, -w }, head[v] = ecnt;
}
void mkIdx ( const int x, int& p ) {
int bk = x;
for ( int i = 2; i * i <= bk; ++ i ) {
while ( bk % i == 0 ) p ++, bk /= i;
}
if ( bk > 1 ) p ++;
}
bool mkLayer ( const int S, const int T ) {
int h = 1, t = 0;
for ( int i = 1; i <= tot; ++ i ) dist[i] = INF, vis[i] = 0;
dist[q[++ t] = S] = 0, vis[S] = 1;
while ( h <= t ) {
int u = q[h ++]; vis[u] = 0;
for ( int i = head[u]; i; i = graph[i].nxt ) {
int v = graph[i].to; i64 c = graph[i].c, w = graph[i].w;
if ( c && dist[v] > dist[u] + w ) {
dist[v] = dist[u] + w;
if ( ! vis[v] ) vis[q[++ t] = v] = 1;
}
}
}
return dist[T] < INF;
}
i64 mkWide ( const int u, const i64 flow, const int T ) {
if ( u == T ) return flow;
i64 used = 0; vis[u] = 1;
for ( int& i = cur[u]; i; i = graph[i].nxt ) {
int v = graph[i].to; i64 c = graph[i].c, w = graph[i].w;
if ( c && dist[v] == dist[u] + w && ! vis[v] ) {
i64 ret = mkWide ( v, imin ( flow - used, c ), T );
graph[i].c -= ret, graph[i ^ 1].c += ret, used += ret;
if ( flow == used ) break;
}
}
if ( used < flow ) dist[u] = INF;
vis[u] = 0; return used;
}
i64 calcMXflow ( const int S, const int T ) {
i64 c = 0, res = 0, delta;
while ( mkLayer ( S, T ) ) {
for ( int i = 1; i <= tot; ++ i ) cur[i] = head[i], vis[i] = 0;
delta = mkWide ( S, INF, T );
if ( delta * dist[T] + c > 0 ) return res - c / dist[T];
res += delta, c += delta * dist[T];
}
return res;
}
bool ck ( const int a, const int b ) { return arA[a] % arA[b] == 0 && idx[a] - 1 == idx[b]; }
int main () {
n = rint (), tot = n;
const int S = ++ tot, T = ++ tot;
for ( int i = 1; i <= n; ++ i ) arA[i] = rint (), mkIdx ( arA[i], idx[i] );
for ( int i = 1; i <= n; ++ i ) arB[i] = rint ();
for ( int i = 1; i <= n; ++ i ) arC[i] = rint ();
for ( int i = 1; i <= n; ++ i ) {
if ( idx[i] & 1 ) {
link ( S, i, arB[i], 0 );
for ( int j = 1; j <= n; ++ j ) {
if ( ck ( i, j ) || ck ( j, i ) ) link ( i, j, INF, -( i64 )arC[i] * arC[j] );
}
}
else link ( i, T, arB[i], 0 );
}
printf ( "%lld\n", calcMXflow ( S, T ) );
return 0;
}
∆ P2045 方格取数加强版 - AC
水题。
#include <bits/stdc++.h>
#define rep( x, a, b ) for( int (x) = (a); (x) <= (b); (x) ++ )
#define per( x, a, b ) for( int (x) = (a); (x) >= (b); (x) -- )
const int INF = 1e9;
const int MAXN = 1e5 + 5, MAXM = 2e5 + 5;
using pii = std::pair<int, int>;
struct Edge { int to, nxt, c, w; } graph[MAXM * 2];
int n, k, head[MAXN], ecnt = 1, dist[MAXN], vis[MAXN], tot, cur[MAXN];
void link ( const int u, const int v, const int c, const int w ) {
graph[++ ecnt] = { v, head[u], c, w }, head[u] = ecnt;
graph[++ ecnt] = { u, head[v], 0, -w }, head[v] = ecnt;
}
int tr ( const int x, const int y ) { return ( x - 1 ) * n + y; }
std::queue<int> q;
bool mkLayer ( const int S, const int T ) {
rep ( i, 1, tot ) dist[i] = INF, vis[i] = 0;
q.push ( S ), dist[S] = 0, vis[S] = 1;
while ( ! q.empty () ) {
int u = q.front (); q.pop (); vis[u] = 0;
for ( int i = head[u]; i; i = graph[i].nxt ) {
int v = graph[i].to, c = graph[i].c, w = graph[i].w;
if ( c && dist[v] > dist[u] + w ) {
dist[v] = dist[u] + w;
if ( ! vis[v] ) q.push ( v ), vis[v] = 1;
}
}
}
return dist[T] < INF;
}
int mkWide ( const int u, const int flow, const int T, int& cst ) {
if ( u == T ) return flow;
int used = 0; vis[u] = 1;
for ( int& i = cur[u]; i; i = graph[i].nxt ) {
int v = graph[i].to, c = graph[i].c, w = graph[i].w;
if ( c && dist[v] == dist[u] + w && ! vis[v] ) {
int ret = mkWide ( v, std::min ( flow - used, c ), T, cst );
graph[i].c -= ret, graph[i ^ 1].c += ret, used += ret, cst += ret * w;
if ( flow == used ) break;
}
}
if ( used < flow ) dist[u] = INF;
vis[u] = 0; return used;
}
pii calcMXflow ( const int S, const int T ) {
int resf = 0, resw = 0;
while ( mkLayer ( S, T ) ) {
rep ( i, 1, tot ) cur[i] = head[i], vis[i] = 0;
resf += mkWide ( S, INF, T, resw );
}
return { resf, resw };
}
int main () {
std::ios::sync_with_stdio ( 0 ); std::cin.tie ( 0 ); std::cout.tie ( 0 );
std::cin >> n >> k; tot = n * n * 2;
const int S = ++ tot, T = ++ tot;
link ( S, tr ( 1, 1 ), k, 0 );
rep ( i, 1, n ) rep ( j, 1, n ) {
int c; std::cin >> c;
link ( tr ( i, j ), tr ( i, j ) + n * n, 1, -c );
link ( tr ( i, j ), tr ( i, j ) + n * n, INF, 0 );
if ( i < n ) link ( tr ( i, j ) + n * n, tr ( i + 1, j ), INF, 0 );
if ( j < n ) link ( tr ( i, j ) + n * n, tr ( i, j + 1 ), INF, 0 );
}
link ( tr ( n, n ) + n * n, T, k, 0 );
std::cout << calcMXflow ( S, T ).second * -1 << '\n';
return 0;
}
∆ LOC5290 网络流 24 题 深海机器人问题 - AC
水题。
#include <bits/stdc++.h>
#define rep( x, a, b ) for( int (x) = (a); (x) <= (b); (x) ++ )
#define per( x, a, b ) for( int (x) = (a); (x) >= (b); (x) -- )
const int INF = 1e9;
const int MAXN = 1e5 + 5, MAXM = 1e6 + 5;
using pii = std::pair<int, int>;
struct Edge { int to, nxt, c, w; } graph[MAXM * 2];
int pS, pT, n, m, head[MAXN], ecnt = 1, dist[MAXN], vis[MAXN], Cur[MAXN], tot;
void link ( const int u, const int v, const int c, const int w ) {
graph[++ ecnt] = { v, head[u], c, w }, head[u] = ecnt;
graph[++ ecnt] = { u, head[v], 0, -w }, head[v] = ecnt;
}
int tr ( const int x, const int y ) { return ( x - 1 ) * m + y; }
std::queue<int> q;
bool mkLayer ( const int S, const int T ) {
rep ( i, 1, tot ) dist[i] = INF, vis[i] = 0;
q.push ( S ), dist[S] = 0, vis[S] = 1;
while ( ! q.empty () ) {
int u = q.front (); q.pop (); vis[u] = 0;
for ( int i = head[u]; i; i = graph[i].nxt ) {
int v = graph[i].to, c = graph[i].c, w = graph[i].w;
if ( c && dist[v] > dist[u] + w ) {
dist[v] = dist[u] + w;
if ( ! vis[v] ) q.push ( v ), vis[v] = 1;
}
}
}
return dist[T] < INF;
}
int mkWide ( const int u, const int flow, const int T, int& cst ) {
if ( u == T ) return flow;
int used = 0; vis[u] = 1;
for ( int& i = Cur[u]; i; i = graph[i].nxt ) {
int v = graph[i].to, c = graph[i].c, w = graph[i].w;
if ( c && dist[v] == dist[u] + w && ! vis[v] ) {
int ret = mkWide ( v, std::min ( flow - used, c ), T, cst );
graph[i].c -= ret, graph[i ^ 1].c += ret, used += ret, cst += ret * w;
if ( flow == used ) break;
}
}
if ( used < flow ) dist[u] = INF;
vis[u] = 0; return used;
}
pii calcMXflow ( const int S, const int T ) {
int resf = 0, resw = 0;
while ( mkLayer ( S, T ) ) {
rep ( i, 1, tot ) Cur[i] = head[i], vis[i] = 0;
resf += mkWide ( S, INF, T, resw );
}
return { resf, resw };
}
int main () {
std::ios::sync_with_stdio ( 0 ); std::cin.tie ( 0 ); std::cout.tie ( 0 );
std::cin >> pS >> pT >> n >> m; tot = ( ++ n ) * ( ++ m );
const int S = ++ tot, T = ++ tot;
rep ( i, 1, n ) rep ( j, 1, m - 1 ) {
int c; std::cin >> c;
link ( tr ( i, j ), tr ( i, j + 1 ), 1, -c );
link ( tr ( i, j ), tr ( i, j + 1 ), INF, 0 );
}
rep ( j, 1, m ) rep ( i, 1, n - 1 ) {
int c; std::cin >> c;
link ( tr ( i, j ), tr ( i + 1, j ), 1, -c );
link ( tr ( i, j ), tr ( i + 1, j ), INF, 0 );
}
rep ( i, 1, pS ) { int k, x, y;
std::cin >> k >> x >> y;
link ( S, tr ( x + 1, y + 1 ), k, 0 );
}
rep ( i, 1, pT ) { int k, x, y;
std::cin >> k >> x >> y;
link ( tr ( x + 1, y + 1 ), T, k, 0 );
}
std::cout << calcMXflow ( S, T ).second * -1 << '\n';
return 0;
}
∆ LOC5126 网络流 24 题 餐巾计划 - AC
好。
#include <bits/stdc++.h>
#define rep( x, a, b ) for( int (x) = (a); (x) <= (b); (x) ++ )
#define per( x, a, b ) for( int (x) = (a); (x) >= (b); (x) -- )
const int INF = 1e9;
const int MAXN = 1e5 + 5, MAXM = 1e6 + 5;
using pii = std::pair<int, int>;
struct Edge { int to, nxt, c, w; } graph[MAXM * 2];
int p, m, f, n, s, head[MAXN], ecnt = 1, dist[MAXN], vis[MAXN], tot, Cur[MAXN];
void link ( const int u, const int v, const int c, const int w ) {
graph[++ ecnt] = { v, head[u], c, w }, head[u] = ecnt;
graph[++ ecnt] = { u, head[v], 0, -w }, head[v] = ecnt;
}
std::queue<int> q;
bool mkLayer ( const int S, const int T ) {
rep ( i, 1, tot ) dist[i] = INF, vis[i] = 0;
q.push ( S ), dist[S] = 0, vis[S] = 1;
while ( ! q.empty () ) {
int u = q.front (); q.pop (); vis[u] = 0;
for ( int i = head[u]; i; i = graph[i].nxt ) {
int v = graph[i].to, c = graph[i].c, w = graph[i].w;
if ( c && dist[v] > dist[u] + w ) {
dist[v] = dist[u] + w;
if ( ! vis[v] ) q.push ( v ), vis[v] = 1;
}
}
}
return dist[T] < INF;
}
int mkWide ( const int u, const int flow, const int T, int& cst ) {
if ( u == T ) return flow;
int used = 0; vis[u] = 1;
for ( int& i = Cur[u]; i; i = graph[i].nxt ) {
int v = graph[i].to, c = graph[i].c, w = graph[i].w;
if ( c && dist[v] == dist[u] + w && ! vis[v] ) {
int ret = mkWide ( v, std::min ( flow - used, c ), T, cst );
graph[i].c -= ret, graph[i ^ 1].c += ret, used += ret, cst += ret * w;
if ( flow == used ) break;
}
}
if ( used < flow ) dist[u] = INF;
vis[u] = 0; return used;
}
pii calcMXflow ( const int S, const int T ) {
int resf = 0, resw = 0;
while ( mkLayer ( S, T ) ) {
if ( dist[T] >= 0 ) break;
rep ( i, 1, tot ) Cur[i] = head[i], vis[i] = 0;
resf += mkWide ( S, INF, T, resw );
}
return { resf, resw };
}
int main () {
std::ios::sync_with_stdio ( 0 ); std::cin.tie ( 0 ); std::cout.tie ( 0 );
int days; std::cin >> days; tot = days << 1;
std::cin >> p >> m >> f >> n >> s;
const int S = ++ tot, T = ++ tot; int all = 0;
rep ( i, 1, days ) { int r; std::cin >> r; all += r; link ( S, i, r, 0 ); link ( i + days, T, r, 0 ); }
rep ( i, 1, days ) {
if ( i + m <= days ) link ( i, i + days + m, INF, -p + f );
if ( i + n <= days ) link ( i, i + days + n, INF, -p + s );
if ( i + 1 <= days ) link ( i + days, i + days + 1, INF, 0 );
}
std::cout << calcMXflow ( S, T ).second + all * p << '\n';
return 0;
}
∆ LOC5127 网络流 24 题 数字梯形 - AC
一般。
#include <bits/stdc++.h>
#define rep( x, a, b ) for( int (x) = (a); (x) <= (b); (x) ++ )
#define per( x, a, b ) for( int (x) = (a); (x) >= (b); (x) -- )
using pii = std::pair<int, int>;
const int INF = 1e9;
const int MAXN = 1e5 + 5, MAXM = 1e6 + 5, MAXS = 1e3 + 5;
struct Edge { int to, nxt, c, w; } graph[MAXM * 2];
int n, m, head[MAXN], Cur[MAXN], ecnt = 1, dist[MAXN], vis[MAXN], ID[MAXS][MAXS], tot;
void link ( const int u, const int v, const int c, const int w ) {
graph[++ ecnt] = { v, head[u], c, w }, head[u] = ecnt;
graph[++ ecnt] = { u, head[v], 0, -w }, head[v] = ecnt;
}
void irAuged () { for ( int i = 2; i <= ecnt; i += 2 ) graph[i].c += graph[i ^ 1].c, graph[i ^ 1].c = 0; }
std::queue<int> q;
bool mkLayer ( const int S, const int T ) {
rep ( i, 1, tot ) dist[i] = INF, vis[i] = 0;
q.push ( S ), dist[S] = 0, vis[S] = 1;
while ( ! q.empty () ) {
int u = q.front (); q.pop (); vis[u] = 0;
for ( int i = head[u]; i; i = graph[i].nxt ) {
int v = graph[i].to, c = graph[i].c, w = graph[i].w;
if ( c && dist[v] > dist[u] + w ) {
dist[v] = dist[u] + w;
if ( ! vis[v] ) q.push ( v ), vis[v] = 1;
}
}
}
return dist[T] < INF;
}
int mkWide ( const int u, const int flow, const int T, int& cst ) {
if ( u == T ) return flow;
int used = 0; vis[u] = 1;
for ( int& i = Cur[u]; i; i = graph[i].nxt ) {
int v = graph[i].to, c = graph[i].c, w = graph[i].w;
if ( c && dist[v] == dist[u] + w && ! vis[v] ) {
int ret = mkWide ( v, std::min ( flow - used, c ), T, cst );
graph[i].c -= ret, graph[i ^ 1].c += ret, used += ret, cst += ret * w;
if ( flow == used ) break;
}
}
if ( used < flow ) dist[u] = INF;
vis[u] = 0; return used;
}
pii calcMXflow ( const int S, const int T ) {
int resf = 0, resw = 0;
while ( mkLayer ( S, T ) ) {
rep ( i, 1, tot ) Cur[i] = head[i], vis[i] = 0;
resf += mkWide ( S, INF, T, resw );
}
return { resf, resw };
}
int main () {
std::ios::sync_with_stdio ( 0 ); std::cin.tie ( 0 ); std::cout.tie ( 0 );
std::cin >> m >> n; const int exist = ( n + ( m << 1 ) - 1 ) * n >> 1;
rep ( i, 1, n ) rep ( j, 1, i + m - 1 ) ID[i][j] = ++ tot;
tot += exist; const int S = ++ tot, T = ++ tot;
rep ( i, 1, n ) rep ( j, 1, i + m - 1 ) { int c;
std::cin >> c; link ( ID[i][j], ID[i][j] + exist, 1, -c );
}
rep ( i, 1, n - 1 ) rep ( j, 1, i + m - 1 )
link ( ID[i][j] + exist, ID[i + 1][j], 1, 0 ), link ( ID[i][j] + exist, ID[i + 1][j + 1], 1, 0 );
rep ( i, 1, m ) link ( S, ID[1][i], 1, 0 );
rep ( i, 1, n + m - 1 ) link ( ID[n][i] + exist, T, INF, 0 );
std::cout << calcMXflow ( S, T ).second * -1 << '\n'; irAuged ();
rep ( i, 1, n ) rep ( j, 1, i + m - 1 ) {
for ( int k = head[ID[i][j]]; k; k = graph[k].nxt ) {
int v = graph[k].to; int& c = graph[k].c;
if ( v == ID[i][j] + exist ) c = INF;
}
}
std::cout << calcMXflow ( S, T ).second * -1 << '\n'; irAuged ();
rep ( i, 1, n - 1 ) rep ( j, 1, i + m - 1 ) {
for ( int k = head[ID[i][j] + exist]; k; k = graph[k].nxt ) {
int v = graph[k].to; int& c = graph[k].c;
if ( v == ID[i + 1][j] || v == ID[i + 1][j + 1] ) c = INF;
}
}
std::cout << calcMXflow ( S, T ).second * -1 << '\n';
return 0;
}
∆ P3980 [NOI2008] 志愿者招募 - AC
一个人造成的贡献是一个区间。
然后按时间连边。
#include <bits/stdc++.h>
#define rep( x, a, b ) for( int (x) = (a); (x) <= (b); (x) ++ )
#define per( x, a, b ) for( int (x) = (a); (x) >= (b); (x) -- )
using i64 = long long;
using pii = std::pair<i64, i64>;
const i64 INF = 1e18;
const int MAXN = 1e5 + 5, MAXM = 1e6 + 5;
struct Edge { int to, nxt; i64 c, w; } graph[MAXM * 2];
i64 dist[MAXN]; bool vis[MAXN];
int n, m, head[MAXN], ecnt = 1, Cur[MAXN], tot;
void link ( const int u, const int v, const i64 c, const i64 w ) {
graph[++ ecnt] = { v, head[u], c, w }, head[u] = ecnt;
graph[++ ecnt] = { u, head[v], 0, -w }, head[v] = ecnt;
}
std::queue<int> q;
bool mkLayer ( const int S, const int T ) {
for ( int i = 1; i <= tot; ++ i ) dist[i] = INF, vis[i] = 0;
q.push ( S ), dist[S] = 0, vis[S] = 1;
while ( ! q.empty () ) {
int u = q.front (); q.pop (); vis[u] = 0;
for ( int i = head[u]; i; i = graph[i].nxt ) {
int v = graph[i].to; i64 c = graph[i].c, w = graph[i].w;
if ( c && dist[v] > dist[u] + w ) {
dist[v] = dist[u] + w;
if ( ! vis[v] ) q.push ( v ), vis[v] = 1;
}
}
}
return dist[T] < INF;
}
i64 mkWide ( const int u, const i64 flow, const int T, i64& cst ) {
if ( u == T ) return flow;
i64 used = 0; vis[u] = 1;
for ( int& i = Cur[u]; i; i = graph[i].nxt ) {
int v = graph[i].to; i64 c = graph[i].c, w = graph[i].w;
if ( c && dist[v] == dist[u] + w && ! vis[v] ) {
i64 ret = mkWide ( v, std::min ( flow - used, c ), T, cst );
graph[i].c -= ret, graph[i ^ 1].c += ret, used += ret, cst += ret * w;
if ( flow == used ) break;
}
}
if ( used < flow ) dist[u] = INF;
vis[u] = 0; return used;
}
pii calcMXflow ( const int S, const int T ) {
i64 resf = 0, resw = 0;
while ( mkLayer ( S, T ) ) {
rep ( i, 1, tot ) Cur[i] = head[i], vis[i] = 0;
resf += mkWide ( S, INF, T, resw );
}
return { resf, resw };
}
int main () {
std::ios::sync_with_stdio ( 0 ); std::cin.tie ( 0 ); std::cout.tie ( 0 );
std::cin >> n >> m; tot = n + 1; const int S = ++ tot, T = ++ tot;
link ( S, 1, n * m, 0 ), link ( n + 1, T, n * m, 0 );
rep ( i, 1, n ) { int c; std::cin >> c; link ( i, i + 1, n * m - c, 0 ); }
rep ( i, 1, m ) { int s, t, c;
std::cin >> s >> t >> c;
link ( s, t + 1, n * m, c );
}
std::cout << calcMXflow ( S, T ).second << '\n';
return 0;
}
∆ ACW338 计数问题 - AC
水题。
#include <bits/stdc++.h>
#define rep( x, a, b ) for( int (x) = (a); (x) <= (b); (x) ++ )
#define per( x, a, b ) for( int (x) = (a); (x) >= (b); (x) -- )
using i64 = long long;
i64 L, R, f[30][30];
int len, nums[30];
i64 DP ( const int pos, const int lim, const int pre, const int sum, const int aim ) {
if ( pos > len ) return sum;
if ( ! pre && ! lim && ~ f[pos][sum] ) return f[pos][sum];
int mx = lim ? nums[len - pos + 1] : 9; i64 res = 0;
rep ( i, 0, mx ) res += DP ( pos + 1, lim && i == mx, pre && ! i, sum + ( aim == i && ( i || ( ! i && ! pre ) ) ), aim );
if ( ! lim && ! pre ) f[pos][sum] = res;
return res;
}
i64 solve ( const int aim, i64 x ) {
memset ( f, -1, sizeof f ), len = 0;
for ( ; x; x /= 10 ) nums[++ len] = x % 10;
return DP ( 1, 1, 1, 0, aim );
}
int main () {
std::ios::sync_with_stdio ( 0 ); std::cin.tie ( 0 ); std::cout.tie ( 0 );
while ( std::cin >> L >> R && ! std::cin.eof () ) {
if ( ! L && ! R ) break;
if ( L > R ) std::swap ( L, R );
rep ( i, 0, 9 ) std::cout << solve ( i, R ) - solve ( i, L - 1 ) << ' ';
std::cout << '\n';
}
return 0;
}
∆ BZOJ3329 Xorequ - AC
手化方程，找性质。
#include <bits/stdc++.h>
#define rep( x, a, b ) for( int (x) = (a); (x) <= (b); (x) ++ )
#define per( x, a, b ) for( int (x) = (a); (x) >= (b); (x) -- )
using i64 = long long;
const int MOD = 1e9 + 7;
const int S = 2;
struct Matrix { int c[S + 5][S + 5]; Matrix () { memset ( c, 0, sizeof c ); } } trans;
i64 n, f[100];
int nums[100], len;
int add ( const int a, const int b ) { return a + b < MOD ? a + b : ( a + b ) % MOD; }
int mul ( const i64 a, const i64 b ) { return a * b % MOD; }
Matrix times ( Matrix a, Matrix b ) {
Matrix res;
rep ( i, 0, S - 1 ) rep ( j, 0, S - 1 ) rep ( k, 0, S - 1 )
res.c[i][j] = add ( res.c[i][j], mul ( a.c[i][k], b.c[k][j] ) );
return res;
}
Matrix cpow ( Matrix bas, i64 idx ) {
Matrix res;
rep ( i, 0, S - 1 ) res.c[i][i] = 1;
while ( idx ) {
if ( idx & 1 ) res = times ( res, bas );
bas = times ( bas, bas ), idx >>= 1;
}
return res;
}
int main () {
std::ios::sync_with_stdio ( 0 ); std::cin.tie ( 0 ); std::cout.tie ( 0 );
int T; std::cin >> T;
f[1] = 1; rep ( i, 2, 64 ) f[i] = f[i - 1] + f[i - 2];
trans.c[0][0] = trans.c[0][1] = trans.c[1][0] = 1; i64 ans = 0;
while ( T -- > 0 ) {
std::cin >> n; len = 0;
auto tmp = ++ n;
for ( ; tmp; tmp >>= 1 ) nums[++ len] = tmp & 1;
nums[len + 1] = ans =0;
per ( i, len, 1 ) {
if ( nums[i] ) ans += f[i + 1];
if ( nums[i] && nums[i + 1] ) break;
}
std::cout << ans - 1 << '\n' << cpow ( trans, n ).c[0][0] << '\n';
}
return 0;
}
∆ P2053 [SCOI2007]修车 - AC
一个工人拆成各个时间段的，然后肆意连边。
#include <bits/stdc++.h>
#define rep( x, a, b ) for( int (x) = (a); (x) <= (b); (x) ++ )
#define per( x, a, b ) for( int (x) = (a); (x) >= (b); (x) -- )
using pii = std::pair<int, int>;
const int INF = 1e9;
const int MAXN = 1e5 + 5, MAXM = 1e6 + 6;
struct Edge { int to, nxt, c, w; } graph[MAXM * 2];
int n, m, head[MAXN], Cur[MAXN], ecnt = 1, dist[MAXN], vis[MAXN], tot;
void link ( const int u, const int v, const int c, const int w ) {
graph[++ ecnt] = { v, head[u], c, w }, head[u] = ecnt;
graph[++ ecnt] = { u, head[v], 0, -w }, head[v] = ecnt;
}
int hs ( const int x, const int y ) { return ( x - 1 ) * n + y; }
std::queue<int> q;
bool mkLayer ( const int S, const int T ) {
rep ( i, 1, tot ) dist[i] = INF, vis[i] = 0;
q.push ( S ), dist[S] = 0, vis[S] = 1;
while ( ! q.empty () ) {
int u = q.front (); q.pop (); vis[u] = 0;
for ( int i = head[u]; i; i = graph[i].nxt ) {
int v = graph[i].to, c = graph[i].c, w = graph[i].w;
if ( c && dist[v] > dist[u] + w ) {
dist[v] = dist[u] + w;
if ( ! vis[v] ) q.push ( v ), vis[v] = 1;
}
}
}
return dist[T] < INF;
}
int mkWide ( const int u, const int flow, const int T, int& cst ) {
if ( u == T ) return flow;
int used = 0; vis[u] = 1;
for ( int& i = Cur[u]; i; i = graph[i].nxt ) {
int v = graph[i].to, c = graph[i].c, w = graph[i].w;
if ( c && dist[v] == dist[u] + w && ! vis[v] ) {
int ret = mkWide ( v, std::min ( flow - used, c ), T, cst );
graph[i].c -= ret, graph[i ^ 1].c += ret, used += ret, cst += ret * w;
if ( flow == used ) break;
}
}
if ( used < flow ) dist[u] = INF;
vis[u] = 0; return used;
}
pii calcMXflow ( const int S, const int T ) {
int resf = 0, resw = 0;
while ( mkLayer ( S, T ) ) {
rep ( i, 1, tot ) Cur[i] = head[i], vis[i] = 0;
resf += mkWide ( S, INF, T, resw );
}
return { resf, resw };
}
int main () {
std::ios::sync_with_stdio ( 0 ); std::cin.tie ( 0 ); std::cout.tie ( 0 );
std::cin >> m >> n; tot = n * m + n;
const int S = ++ tot, T = ++ tot;
rep ( j, 1, n ) rep ( i, 1, m ) { int c;
std::cin >> c; rep ( k, 1, n ) link ( j, hs ( i, k ) + n, 1, c * k );
}
rep ( i, 1, n ) link ( S, i, 1, 0 );
rep ( i, 1, m ) rep ( j, 1, n ) link ( hs ( i, j ) + n, T, 1, 0 );
std::cout << std::fixed << std::setprecision ( 2 ) << 1.0 * calcMXflow ( S, T ).second / n << '\n';
return 0;
}
∆ P2153 [SDOI2009]晨跑 - AC
流 板（经 典 重 现）。
#include <bits/stdc++.h>
#define rep( x, a, b ) for( int (x) = (a); (x) <= (b); (x) ++ )
#define per( x, a, b ) for( int (x) = (a); (x) >= (b); (x) -- )
using pii = std::pair<int, int>;
const int INF = 1e9;
const int MAXN = 1e5 + 5, MAXM = 1e6 + 6;
struct Edge { int to, nxt, c, w; } graph[MAXM * 2];
int n, m, head[MAXN], Cur[MAXN], ecnt = 1, dist[MAXN], vis[MAXN], tot;
void link ( const int u, const int v, const int c, const int w ) {
graph[++ ecnt] = { v, head[u], c, w }, head[u] = ecnt;
graph[++ ecnt] = { u, head[v], 0, -w }, head[v] = ecnt;
}
std::queue<int> q;
bool mkLayer ( const int S, const int T ) {
rep ( i, 1, tot ) dist[i] = INF, vis[i] = 0;
q.push ( S ), dist[S] = 0, vis[S] = 1;
while ( ! q.empty () ) {
int u = q.front (); q.pop (); vis[u] = 0;
for ( int i = head[u]; i; i = graph[i].nxt ) {
int v = graph[i].to, c = graph[i].c, w = graph[i].w;
if ( c && dist[v] > dist[u] + w ) {
dist[v] = dist[u] + w;
if ( ! vis[v] ) q.push ( v ), vis[v] = 1;
}
}
}
return dist[T] < INF;
}
int mkWide ( const int u, const int flow, const int T, int& cst ) {
if ( u == T ) return flow;
int used = 0; vis[u] = 1;
for ( int& i = Cur[u]; i; i = graph[i].nxt ) {
int v = graph[i].to, c = graph[i].c, w = graph[i].w;
if ( c && dist[v] == dist[u] + w && ! vis[v] ) {
int ret = mkWide ( v, std::min ( flow - used, c ), T, cst );
graph[i].c -= ret, graph[i ^ 1].c += ret, used += ret, cst += ret * w;
if ( flow == used ) break;
}
}
if ( used < flow ) dist[u] = INF;
vis[u] = 0; return used;
}
pii calcMXflow ( const int S, const int T ) {
int resf = 0, resw = 0;
while ( mkLayer ( S, T ) ) {
rep ( i, 1, tot ) Cur[i] = head[i], vis[i] = 0;
resf += mkWide ( S, INF, T, resw );
}
return { resf, resw };
}
int main () {
std::ios::sync_with_stdio ( 0 ); std::cin.tie ( 0 ); std::cout.tie ( 0 );
std::cin >> n >> m; tot = n << 1;
rep ( i, 1, m ) { int u, v, c;
std::cin >> u >> v >> c;
if ( u == 1 && v == n ) link ( u + n, v, 1, c );
else link ( u + n, v, INF, c );
}
rep ( i, 1, n ) link ( i, i + n, 1, 0 );
pii ret = calcMXflow ( n + 1, n );
std::cout << ret.first << ' ' << ret.second << '\n';
return 0;
}
∆ P2517 [HAOI2010]订货 - AC
流 板（经 典 再 重 现）。
#include <bits/stdc++.h>
#define rep( x, a, b ) for( int (x) = (a); (x) <= (b); (x) ++ )
#define per( x, a, b ) for( int (x) = (a); (x) >= (b); (x) -- )
using pii = std::pair<int, int>;
const int INF = 1e9;
const int MAXN = 1e5 + 5, MAXM = 1e6 + 6;
struct Edge { int to, nxt, c, w; } graph[MAXM * 2];
int n, m, sp, head[MAXN], Cur[MAXN], ecnt = 1, dist[MAXN], vis[MAXN], tot;
void link ( const int u, const int v, const int c, const int w ) {
graph[++ ecnt] = { v, head[u], c, w }, head[u] = ecnt;
graph[++ ecnt] = { u, head[v], 0, -w }, head[v] = ecnt;
}
std::queue<int> q;
bool mkLayer ( const int S, const int T ) {
rep ( i, 1, tot ) dist[i] = INF, vis[i] = 0;
q.push ( S ), dist[S] = 0, vis[S] = 1;
while ( ! q.empty () ) {
int u = q.front (); q.pop (); vis[u] = 0;
for ( int i = head[u]; i; i = graph[i].nxt ) {
int v = graph[i].to, c = graph[i].c, w = graph[i].w;
if ( c && dist[v] > dist[u] + w ) {
dist[v] = dist[u] + w;
if ( ! vis[v] ) q.push ( v ), vis[v] = 1;
}
}
}
return dist[T] < INF;
}
int mkWide ( const int u, const int flow, const int T, int& cst ) {
if ( u == T ) return flow;
int used = 0; vis[u] = 1;
for ( int& i = Cur[u]; i; i = graph[i].nxt ) {
int v = graph[i].to, c = graph[i].c, w = graph[i].w;
if ( c && dist[v] == dist[u] + w && ! vis[v] ) {
int ret = mkWide ( v, std::min ( flow - used, c ), T, cst );
graph[i].c -= ret, graph[i ^ 1].c += ret, used += ret, cst += ret * w;
if ( flow == used ) break;
}
}
if ( used < flow ) dist[u] = INF;
vis[u] = 0; return used;
}
pii calcMXflow ( const int S, const int T ) {
int resf = 0, resw = 0;
while ( mkLayer ( S, T ) ) {
rep ( i, 1, tot ) Cur[i] = head[i], vis[i] = 0;
resf += mkWide ( S, INF, T, resw );
}
return { resf, resw };
}
int main () {
std::ios::sync_with_stdio ( 0 ); std::cin.tie ( 0 ); std::cout.tie ( 0 );
std::cin >> n >> m >> sp; tot = n;
const int S = ++ tot, T = ++ tot;
rep ( i, 1, n ) { int c; std::cin >> c; link ( i, T, c, 0 ); if ( i < n ) link ( i, i + 1, sp, m ); }
rep ( i, 1, n ) { int c; std::cin >> c; link ( S, i, INF, c ); }
std::cout << calcMXflow ( S, T ).second << '\n';
return 0;
}
∆ AT4994 [AGC034D] Manhattan Max Matching - AC
我神 tm 直接拆曼哈顿距离。
// dist((x1, y1), (x2, y2)) = |x1-x2|+|y1-y2|
// max{x1-x2+y1-y2, x2-x1+y1-y2, x1-x2-y1+y2, x2-x1-y1+y2}
// max{x1+y1-x2-y2, -x1+y1+x2-y2, x1-y1-x2+y2, -x1-y1+x2+y2}
#include <bits/stdc++.h>
#define rep( x, a, b ) for ( int x = (a); x <= (b); (x) ++ )
#define per( x, a, b ) for ( int x = (a); x >= (b); (x) -- )
using i64 = long long;
using pii = std::pair<int, i64>;
const int INF = 1e9; const i64 INF64 = 1e18;
const int MAXN = 1e5 + 5, MAXM = 1e6 + 5;
struct Edge { int to, nxt, c; i64 w; } graph[MAXM * 2];
i64 dist[MAXN]; bool vis[MAXN];
int n, head[MAXN], Cur[MAXN], ecnt = 1, tot;
void link ( const int u, const int v, const int c, const i64 w ) {
graph[++ ecnt] = { v, head[u], c, w }, head[u] = ecnt;
graph[++ ecnt] = { u, head[v], 0, -w }, head[v] = ecnt;
}
std::queue<int> q;
bool mkLayer ( const int S, const int T ) {
rep ( i, 1, tot ) dist[i] = INF64, vis[i] = 0;
q.push ( S ), dist[S] = 0, vis[S] = 1;
while ( ! q.empty () ) {
int u = q.front (); q.pop (); vis[u] = 0;
for ( int i = head[u]; i; i = graph[i].nxt ) {
int v = graph[i].to, c = graph[i].c; i64 w = graph[i].w;
if ( c && dist[v] > dist[u] + w ) {
dist[v] = dist[u] + w;
if ( ! vis[v] ) q.push ( v ), vis[v] = 1;
}
}
}
return dist[T] < INF64;
}
int mkWide ( const int u, const int flow, const int T, i64& cst ) {
if ( u == T ) return flow;
int used = 0; vis[u] = 1;
for ( int& i = Cur[u]; i; i = graph[i].nxt ) {
int v = graph[i].to, c = graph[i].c; i64 w = graph[i].w;
if ( c && dist[v] == dist[u] + w && ! vis[v] ) {
int ret = mkWide ( v, std::min ( flow - used, c ), T, cst );
graph[i].c -= ret, graph[i ^ 1].c += ret, used += ret, cst += ret * w;
if ( flow == used ) break;
}
}
if ( used < flow ) dist[u] = INF64;
return used;
}
pii calcMXflow ( const int S, const int T ) {
int resf = 0; i64 resw = 0;
while ( mkLayer ( S, T ) ) {
rep ( i, 1, tot ) Cur[i] = head[i], vis[i] = 0;
resf += mkWide ( S, INF, T, resw );
}
return { resf, resw };
}
int main () {
std::ios::sync_with_stdio ( 0 ); std::cin.tie ( 0 ); std::cout.tie ( 0 );
std::cin >> n; tot = n << 1; const int S = ++ tot, T = ++ tot;
const int pa = ++ tot, pb = ++ tot, pc = ++ tot, pd = ++ tot;
rep ( i, 1, n ) { i64 x, y; int c;
std::cin >> x >> y >> c;
link ( S, i, c, 0 );
link ( i, pa, INF, -( x + y ) );
link ( i, pb, INF, -( -x + y ) );
link ( i, pc, INF, -( x - y ) );
link ( i, pd, INF, -( -x - y ) );
}
rep ( i, 1, n ) { i64 x, y; int c;
std::cin >> x >> y >> c;
link ( pa, i + n, INF, -( -x - y ) );
link ( pb, i + n, INF, -( x - y ) );
link ( pc, i + n, INF, -( -x + y ) );
link ( pd, i + n, INF, -( x + y ) );
link ( i + n, T, c, 0 );
}
std::cout << calcMXflow ( S, T ).second * -1 << '\n';
return 0;
}
∆ ARC107F Sum of Abs - AC
niubility.
/*
### disc:
delete -1 1
b[i]>0:a[i]+|b[i]| 2|b[i]| 0
otherwise:a[i]+|b[i]| 0 2|b[i]|
each means cond1.1~3 cond2.1~3
### graph:
(s,i,cond1 or 2.3)
(i',t,cond1 or 2.2)
*/
#include<queue>
#include<cstdio>
using namespace std;
const int INF=1e9;
queue<int>q;
int n,m,s,t;
int head[100010],cur[100010],cntot=1,to[1000010],nxt[1000010],val[1000010],vis[100010],dep[100010],ans,a[100010],b[100010],all;
int myabs(int x)
{
if(x>0) return x;
else return -x;
}
void addedge(int one,int ano,int lav)
{
nxt[++cntot]=head[one];
to[cntot]=ano;
val[cntot]=lav;
head[one]=cntot;
nxt[++cntot]=head[ano];
to[cntot]=one;
val[cntot]=0;
head[ano]=cntot;
}
bool bfs()
{
for(int i=s;i<=t;++i)
{
dep[i]=INF;
cur[i]=head[i];
vis[i]=0;
}
dep[s]=0;
vis[s]=1;
q.push(s);
while(!q.empty())
{
int now=q.front();
q.pop();
vis[now]=0;
for(int i=head[now];i;i=nxt[i])
{
int y=to[i];
if(val[i]&&dep[y]>dep[now]+1)
{
dep[y]=dep[now]+1;
if(!vis[y])
{
vis[y]=1;
q.push(y);
}
}
}
}
return dep[t]!=INF;
}
int dfs(int x,int lav)
{
if(x==t)
{
ans+=lav;
return lav;
}
int used=0,rlow;
for(int i=cur[x];i;i=nxt[i])
{
cur[x]=i;
int y=to[i];
if(val[i]&&dep[y]==dep[x]+1)
{
if(rlow=dfs(y,min(lav-used,val[i])))
{
val[i]-=rlow;
val[i^1]+=rlow;
used+=rlow;
if(used==lav) break;
}
else dep[y]=INF;
}
}
return used;
}
int dinic()
{
ans=0;
while(bfs()) dfs(s,INF);
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
s=0;
t=n+n+1;
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i<=n;++i) scanf("%d",&b[i]);
for(int i=1;i<=m;++i)
{
int u,v;
scanf("%d%d",&u,&v);
addedge(u+n,v,INF);
addedge(v+n,u,INF);
}
for(int i=1;i<=n;++i)
{
if(b[i]>0)
{
addedge(i,i+n,a[i]+myabs(b[i]));
addedge(s,i,myabs(b[i])<<1);
}
else
{
addedge(i+n,t,myabs(b[i])<<1);
addedge(i,i+n,a[i]+myabs(b[i]));
}
all+=myabs(b[i]);
}
printf("%d\n",all-dinic());
return 0;
}
∆ ARC111A Simple Math 2 - AC
#include <iostream>
using i64 = long long;
int cpow ( int bas, i64 idx, const int p ) {
int res = 1;
while ( idx ) {
if ( idx & 1 ) res = ( i64 )res * bas % p;
bas = ( i64 )bas * bas % p, idx >>= 1;
}
return res;
}
int main () {
std::ios::sync_with_stdio ( 0 ); std::cin.tie ( 0 ); std::cout.tie ( 0 );
i64 n; int m; std::cin >> n >> m;
std::cout << ( cpow ( 10, n, m * m ) / m ) % m << '\n';
return 0;
}
∆ P4076 [SDOI2016]墙上的句子 - AC
模拟+网络流。
有点瘤不想写。
#include<map>
#include<set>
#include<queue>
#include<string>
#include<cstdio>
#include<algorithm>
using namespace std;
const int INF=1e9;
set<string> app;
queue<int> q;
vector<int> e[100010];
vector<string> hstr[110],lstr[110];
map<string,int> mp;
int T,cnt,hang[110],lie[110],n,m,s,t,hway[110],lway[110];
int head[100010],Cur[100010],cntot=1,to[1000010],nxt[1000010],val[1000010],vis[100010],dep[100010],ans,reverans;
char str[110][110];
void addedge(int one,int ano,int lav)
{
nxt[++cntot]=head[one];
to[cntot]=ano;
val[cntot]=lav;
head[one]=cntot;
nxt[++cntot]=head[ano];
to[cntot]=one;
val[cntot]=0;
head[ano]=cntot;
}
bool bfs()
{
for(int i=s;i<=t;++i)
{
dep[i]=INF;
Cur[i]=head[i];
vis[i]=0;
}
dep[s]=0;
vis[s]=1;
q.push(s);
while(!q.empty())
{
int now=q.front();
q.pop();
vis[now]=0;
for(int i=head[now];i;i=nxt[i])
{
int y=to[i];
if(val[i]&&dep[y]>dep[now]+1)
{
dep[y]=dep[now]+1;
if(!vis[y])
{
vis[y]=1;
q.push(y);
}
}
}
}
return dep[t]!=INF;
}
int dfs(int x,int lav)
{
if(x==t) return lav;
int used=0,rlow;
for(int i=Cur[x];i;i=nxt[i])
{
Cur[x]=i;
int y=to[i];
if(val[i]&&dep[y]==dep[x]+1)
{
if(rlow=dfs(y,min(lav-used,val[i])))
{
val[i]-=rlow;
val[i^1]+=rlow;
used+=rlow;
if(used==lav) break;
}
else dep[y]=INF;
}
}
return used;
}
void dinic()
{
ans=0;
while(bfs()) ans+=dfs(s,INF);
}
bool rever(string x)
{
for(int i=0,j=x.length()-1;i<j;++i,--j)
{
if(x[i]!=x[j]) return 0;
}
return 1;
}
bool check(string x)
{
for(int i=0,j=x.length()-1;i<j;++i,--j)
{
if(x[i]>x[j]) return 1;
else if(x[i]<x[j]) return 0;
}
return 0;
}
string trans(string x)
{
if(x.length()==1) return x;
else if(x[0]<=x[x.length()-1]) return x;
else
{
for(int i=0,j=x.length()-1;i<j;++i,--j) swap(x[i],x[j]);
return x;
}
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
mp.clear();
app.clear();
cnt=reverans=0;
for(int i=1;i<=n;++i) scanf("%d",&hang[i]);
for(int i=1;i<=m;++i) scanf("%d",&lie[i]);
for(int i=1;i<=n;++i) scanf("%s",str[i]+1);
for(int i=1;i<=n;++i)
{
string tmp;
hstr[i].clear();
if(hang[i]==1)
{
for(int j=1;j<=m;++j)
{
if(str[i][j]!='_') tmp.push_back(str[i][j]);
else
{
if(tmp.size()>=1) hstr[i].push_back(tmp);
tmp.clear();
}
}
if(str[i][m]!='_') hstr[i].push_back(tmp);
}
else
{
for(int j=m;j>=1;--j)
{
if(str[i][j]!='_') tmp.push_back(str[i][j]);
else
{
if(tmp.size()>=1) hstr[i].push_back(tmp);
tmp.clear();
}
}
if(str[i][1]!='_') hstr[i].push_back(tmp);
}
}
for(int j=1;j<=m;++j)
{
string tmp;
lstr[j].clear();
if(lie[j]==1)
{
for(int i=1;i<=n;++i)
{
if(str[i][j]!='_') tmp.push_back(str[i][j]);
else
{
if(tmp.size()>=1) lstr[j].push_back(tmp);
tmp.clear();
}
}
if(str[n][j]!='_') lstr[j].push_back(tmp);
}
else
{
for(int i=n;i>=1;--i)
{
if(str[i][j]!='_') tmp.push_back(str[i][j]);
else
{
if(tmp.size()>=1) lstr[j].push_back(tmp);
tmp.clear();
}
}
if(str[1][j]!='_') lstr[j].push_back(tmp);
}
}
for(int i=1;i<=n;++i)
{
if(hang[i]==1)
{
int way=0;
for(int j=0;j<hstr[i].size();++j)
{
string cur=hstr[i][j];
if(rever(cur))
{
if(!app.count(cur))
{
app.insert(cur);
reverans++;
}
}
else
{
if(~way)
{
if(check(cur)) hway[i]=1;
else hway[i]=0;
way=-1;
}
cur=trans(cur);
if(!mp[cur])
{
mp[cur]=++cnt;
e[cnt].clear();
}
e[mp[cur]].push_back(i);
}
}
}
else if(hang[i]==-1)
{
int way=0;
for(int j=0;j<hstr[i].size();++j)
{
string cur=hstr[i][j];
if(rever(cur))
{
if(!app.count(cur))
{
app.insert(cur);
reverans++;
}
}
else
{
if(~way)
{
if(check(cur)) hway[i]=1;
else hway[i]=0;
way=-1;
}
cur=trans(cur);
if(!mp[cur])
{
mp[cur]=++cnt;
e[cnt].clear();
}
e[mp[cur]].push_back(i);
}
}
}
else
{
for(int j=0;j<hstr[i].size();++j)
{
string cur=hstr[i][j];
if(rever(cur))
{
if(!app.count(cur))
{
app.insert(cur);
reverans++;
}
}
else
{
cur=trans(cur);
if(!mp[cur])
{
mp[cur]=++cnt;
e[cnt].clear();
}
e[mp[cur]].push_back(i);
}
}
hway[i]=-1;
}
}
for(int j=1;j<=m;++j)
{
if(lie[j]==1)
{
int way=0;
for(int i=0;i<lstr[j].size();++i)
{
string cur=lstr[j][i];
if(rever(cur))
{
if(!app.count(cur))
{
app.insert(cur);
reverans++;
}
}
else
{
if(~way)
{
if(check(cur)) lway[j]=1;
else lway[j]=0;
way=-1;
}
cur=trans(cur);
if(!mp[cur])
{
mp[cur]=++cnt;
e[cnt].clear();
}
e[mp[cur]].push_back(j+n);
}
}
}
else if(lie[j]==-1)
{
int way=0;
for(int i=0;i<lstr[j].size();++i)
{
string cur=lstr[j][i];
if(rever(cur))
{
if(!app.count(cur))
{
app.insert(cur);
reverans++;
}
}
else
{
if(~way)
{
if(check(cur)) lway[j]=1;
else lway[j]=0;
way=-1;
}
cur=trans(cur);
if(!mp[cur])
{
mp[cur]=++cnt;
e[cnt].clear();
}
e[mp[cur]].push_back(j+n);
}
}
}
else
{
for(int i=0;i<lstr[j].size();++i)
{
string cur=lstr[j][i];
if(rever(cur))
{
if(!app.count(cur))
{
app.insert(cur);
reverans++;
}
}
else
{
cur=trans(cur);
if(!mp[cur])
{
mp[cur]=++cnt;
e[cnt].clear();
}
e[mp[cur]].push_back(j+n);
}
}
lway[j]=-1;
}
}
s=0;
t=n+m+cnt+cnt+1;
for(int i=s;i<=t;++i) head[i]=0;
cntot=1;
for(int i=1;i<=n;++i)
{
if(hway[i]==0) addedge(s,i,INF);
else if(hway[i]==1) addedge(i,t,INF);
}
for(int j=1;j<=m;++j)
{
if(lway[j]==0) addedge(s,j+n,INF);
else if(lway[j]==1) addedge(j+n,t,INF);
}
for(int i=1;i<=cnt;++i)
{
addedge(s,i+n+m,1);
addedge(i+cnt+n+m,t,1);
for(int j=0;j<e[i].size();++j)
{
addedge(i+n+m,e[i][j],INF);
addedge(e[i][j],i+cnt+n+m,INF);
}
}
dinic();
printf("%d\n",((ans-cnt)<<1)+reverans);
}
return 0;
}
∆ P4716 【模板】最小树形图 - AC
板题，不过我拿 tarjan 实现好像没有优越性……
#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
const int INF=1e9;
vector<pair<int,long long> > e[2][110];
int n,m,root,belong[110],col,val[2][110],pre[2][110],dfn[110],low[110],cnt,sta[110],top,siz[110];
void tarjan(int x,int r)
{
dfn[x]=low[x]=++cnt;
sta[++top]=x;
int y=pre[r][x];
if(y)
{
if(!dfn[y])
{
tarjan(y,r);
low[x]=min(low[x],low[y]);
}
else if(!belong[y]) low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x])
{
belong[x]=++col;
siz[col]=1;
while(sta[top]!=x)
{
belong[sta[top--]]=col;
siz[col]++;
}
top--;
}
}
long long solve()
{
int turn=0;
long long res=0;
while(233)
{
cnt=col=0;
for(int i=1;i<=n;++i) dfn[i]=belong[i]=0;
for(int i=1;i<=n;++i)
{
if(!dfn[i]) tarjan(i,turn);
}
for(int i=1;i<=n;++i)
{
if(i!=root&&val[turn][i]==INF) return -1;
}
if(col==n)
{
for(int i=1;i<=n;++i)
{
if(i!=root) res+=val[turn][i];
}
return res;
}
for(int i=1;i<=n;++i)
{
if(belong[pre[turn][i]]==belong[i]) res+=val[turn][i];
}
for(int i=1;i<=n;++i)
{
e[turn^1][i].clear();
val[turn^1][i]=INF;
pre[turn^1][i]=0;
}
for(int i=1;i<=n;++i)
{
for(int j=0;j<e[turn][i].size();++j)
{
int y=e[turn][i][j].first;
long long z=e[turn][i][j].second;
if(belong[i]!=belong[y])
{
if(siz[belong[y]]>1) z-=val[turn][y];
e[turn^1][belong[i]].push_back(make_pair(belong[y],z));
if(z<val[turn^1][belong[y]])
{
val[turn^1][belong[y]]=z;
pre[turn^1][belong[y]]=belong[i];
}
}
}
}
n=col;
root=belong[root];
turn^=1;
}
}
int main()
{
scanf("%d%d%d",&n,&m,&root);
for(int i=1;i<=n;++i) val[0][i]=INF;
for(int i=1;i<=m;++i)
{
int u,v;
long long w;
scanf("%d%d%lld",&u,&v,&w);
if(u!=v&&v!=root)
{
e[0][u].push_back(make_pair(v,w));
if(val[0][v]>w)
{
val[0][v]=w;
pre[0][v]=u;
}
}
}
printf("%lld\n",solve());
return 0;
}
∆ BZOJ2481 PKU3164 Command Network - AC
....
#include<cmath>
#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
const int INF=1e9;
int n,m,root,belong[1010],col,pre[2][1010],val[2][1010],dfn[1010],low[1010],cnt,sta[1010],top,siz[1010];
int head[2][1010],nxt[2][1000010],to[2][1000010],cntot[2];
long long X[1010],Y[1010],lav[2][1000010];
void addedge(int one,int ano,long long tak,int id)
{
to[id][++cntot[id]]=ano;
lav[id][cntot[id]]=tak;
nxt[id][cntot[id]]=head[id][one];
head[id][one]=cntot[id];
}
void tarjan(int x,int p)
{
dfn[x]=low[x]=++cnt;
sta[++top]=x;
int y=pre[p][x];
if(y)
{
if(!dfn[y])
{
tarjan(y,p);
low[x]=min(low[x],low[y]);
}
else if(!belong[y]) low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x])
{
belong[x]=++col;
siz[col]=1;
while(sta[top]!=x)
{
belong[sta[top--]]=col;
siz[col]++;
}
top--;
}
}
long long solve()
{
int turn=0;
long long res=0;
while(233)
{
cnt=col=0;
for(int i=1;i<=n;++i) dfn[i]=belong[i]=0;
for(int i=1;i<=n;++i)
{
if(!dfn[i]) tarjan(i,turn);
}
if(col==n)
{
for(int i=1;i<=n;++i)
{
if(i!=root) res+=val[turn][i];
}
return res;
}
for(int i=1;i<=n;++i)
{
if(belong[pre[turn][i]]==belong[i]) res+=val[turn][i];
}
cntot[turn^1]=0;
for(int i=1;i<=col;++i)
{
head[turn^1][i]=0;
val[turn^1][i]=INF;
pre[turn^1][i]=0;
}
for(int i=1;i<=n;++i)
{
for(int j=head[turn][i];j;j=nxt[turn][j])
{
int y=to[turn][j];
long long z=lav[turn][j];
if(belong[i]^belong[y])
{
if(siz[belong[y]]>1) z-=val[turn][y];
addedge(belong[i],belong[y],z,turn^1);
if(z<val[turn^1][belong[y]])
{
val[turn^1][belong[y]]=z;
pre[turn^1][belong[y]]=belong[i];
}
}
}
}
n=col;
root=belong[root];
turn^=1;
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
root=++n;
for(int i=1;i<n;++i) scanf("%lld%lld",&X[i],&Y[i]);
cntot[0]=0;
for(int i=1;i<=n;++i)
{
head[0][i]=0;
val[0][i]=INF;
pre[0][i]=0;
}
for(int i=1;i<n;++i)
{
addedge(n,i,INF,0);
pre[0][i]=n;
val[0][i]=INF;
}
for(int i=1;i<=m;++i)
{
int u,v;
scanf("%d%d",&u,&v);
if(u^v)
{
long long w=abs(X[u]-X[v])+abs(Y[u]-Y[v]);
addedge(u,v,w,0);
if(w<val[0][v])
{
val[0][v]=w;
pre[0][v]=u;
}
}
}
long long ret=solve();
if(ret>=(INF<<1)) printf("Poor\n");
else printf("%lld\n",ret-INF);
}
return 0;
}
∆ BZOJ4349 最小树形图 / P2792 [JSOI2008]小店购物 - AC
拆点跑最小树形图。
#include<cstdio>
#include<algorithm>
using namespace std;
const int INF=1e9;
int n,m,k,root,pre[2][6010],cnt,sta[6010],top,head[2][6010],to[2][1000010],nxt[2][1000010],b[60],ID[60][110],cntot[2],belong[6010],col,siz[6010],dfn[6010],low[6010];
double lav[2][1000010],val[2][6010],a[60];
void addedge(int one,int ano,double hav,int id)
{
to[id][++cntot[id]]=ano;
nxt[id][cntot[id]]=head[id][one];
lav[id][cntot[id]]=hav;
head[id][one]=cntot[id];
}
void tarjan(int x,int ed)
{
dfn[x]=low[x]=++cnt;
sta[++top]=x;
int y=pre[ed][x];
if(y)
{
if(!dfn[y])
{
tarjan(y,ed);
low[x]=min(low[x],low[y]);
}
else if(!belong[y]) low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x])
{
belong[x]=++col;
siz[col]=1;
while(sta[top]^x)
{
belong[sta[top--]]=col;
siz[col]++;
}
top--;
}
}
double solve()
{
int turn=0;
double res=0;
while(233)
{
cnt=col=0;
for(int i=1;i<=n;++i) dfn[i]=belong[i]=0;
for(int i=1;i<=n;++i)
{
if(!dfn[i]) tarjan(i,turn);
}
if(col==n)
{
for(int i=1;i<=n;++i)
{
if(i^root) res+=val[turn][i];
}
return res;
}
for(int i=1;i<=n;++i)
{
if(belong[pre[turn][i]]==belong[i]) res+=val[turn][i];
}
cntot[turn^1]=0;
for(int i=1;i<=n;++i)
{
head[turn^1][i]=0;
val[turn^1][i]=INF;
pre[turn^1][i]=0;
}
for(int i=1;i<=n;++i)
{
for(int j=head[turn][i];j;j=nxt[turn][j])
{
int y=to[turn][j];
double z=lav[turn][j];
if(belong[i]^belong[y])
{
if(siz[belong[y]]>1) z-=val[turn][y];
addedge(belong[i],belong[y],z,turn^1);
if(val[turn^1][belong[y]]>z)
{
val[turn^1][belong[y]]=z;
pre[turn^1][belong[y]]=belong[i];
}
}
}
}
n=col;
root=belong[root];
turn^=1;
}
}
int main()
{
scanf("%d",&m);
for(int i=1;i<=m;++i)
{
scanf("%lf%d",&a[i],&b[i]);
for(int j=1;j<=b[i];++j)
{
ID[i][j]=++n;
val[0][n]=INF;
}
}
val[0][++n]=INF;
root=n;
for(int i=1;i<=m;++i)
{
if(b[i])
{
addedge(root,ID[i][1],a[i],0);
val[0][ID[i][1]]=a[i];
pre[0][ID[i][1]]=root;
for(int j=2;j<=b[i];++j)
{
addedge(ID[i][j-1],ID[i][j],a[i],0);
val[0][ID[i][j]]=a[i];
pre[0][ID[i][j]]=ID[i][j-1];
}
}
}
scanf("%d",&k);
for(int i=1;i<=k;++i)
{
int u,v;
double w;
scanf("%d%d%lf",&u,&v,&w);
if(u^v)
{
for(int j=1;j<=b[v];++j)
{
addedge(ID[u][1],ID[v][j],w,0);
if(val[0][ID[v][j]]>w)
{
val[0][ID[v][j]]=w;
pre[0][ID[v][j]]=ID[u][1];
}
}
}
}
printf("%.2lf\n",solve());
return 0;
}
∆ P2573 [SCOI2012]滑雪与时间胶囊 - AC
一道在 最小树形图 链接里 且 不能用其过的题。
#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
vector<pair<long long,long long> > e[100010];
long long n,m,h[100010],fa[100010],oneans,anoans,vis[100010];
struct edge
{
long long fr,ba,val;
}lin[2000010];
void makeset()
{
for(long long i=1;i<=n;++i) fa[i]=i;
}
long long findset(long long x)
{
if(x^fa[x]) fa[x]=findset(fa[x]);
return fa[x];
}
bool mergeset(long long x,long long y)
{
x=findset(x);
y=findset(y);
if(x^y)
{
fa[x]=y;
return 1;
}
else return 0;
}
void dfs(long long x)
{
vis[x]=1;
++oneans;
for(long long i=0;i<e[x].size();++i)
{
long long y=e[x][i].first,z=e[x][i].second;
lin[++m].fr=x;
lin[m].ba=y;
lin[m].val=z;
if(!vis[y]) dfs(y);
}
}
bool cmp(edge one,edge ano)
{
if(h[one.ba]^h[ano.ba]) return h[one.ba]>h[ano.ba];
else return one.val<ano.val;
}
int main()
{
scanf("%lld%lld",&n,&m);
makeset();
for(long long i=1;i<=n;++i) scanf("%lld",&h[i]);
for(long long i=1;i<=m;++i)
{
long long u,v,w;
scanf("%lld%lld%lld",&u,&v,&w);
if(h[u]>=h[v]) e[u].push_back(make_pair(v,w));
if(h[u]<=h[v]) e[v].push_back(make_pair(u,w));
}
m=0;
dfs(1);
sort(lin+1,lin+1+m,cmp);
long long tmp=oneans;
for(long long i=1;i<=m;++i)
{
if(mergeset(lin[i].fr,lin[i].ba))
{
anoans+=lin[i].val;
--tmp;
if(tmp<2) break;
}
}
printf("%lld %lld\n",oneans,anoans);
return 0;
}
∆ ARC111B Reversible Cards - AC
nowcoder 原题。
#include<cstdio>
int n,cab[400010],fa[400010],a,b,ans;
int findset(int x)
{
if(fa[x]) return fa[x]=findset(fa[x]);
else return x;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d%d",&a,&b);
a=findset(a);
b=findset(b);
if((a^b)&&(!cab[a]||!cab[b]))
{
fa[a]=b;
cab[b]|=cab[a];
ans++;
}
else if(!cab[a])
{
cab[a]=1;
ans++;
}
}
printf("%d\n",ans);
return 0;
}
∆ ARC111C Too Heavy - AC
构造出一个操作序列。
先不考虑最小，只考虑构造出来。
参考某道 ABC D 题，直接连边。
。
分别表示 person、baggage。
再想，相当于我们想要让， and 一一对应。
一个 的 （即 ）不能被交换只在 。
所以无解就是这个环中存在 。
剩下构造，先考虑满足规则。
贪心的选一个最大的 进行即可。
#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
vector<pair<int,int> > ans;
int n,a[200010],b[200010],p[200010],rev[200010],vis[200010];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i<=n;++i) scanf("%d",&b[i]);
for(int i=1;i<=n;++i)
{
scanf("%d",&p[i]);
rev[p[i]]=i;
}
vector<int> per;
for(int i=1;i<=n;++i)
{
if(p[i]^i)
{
if(a[rev[i]]<=b[i])
{
printf("-1\n");
return 0;
}
if(!vis[i])
{
vis[i]=1;
per.clear();
per.push_back(i);
for(int j=p[i];j^i;j=p[j])
{
if(a[rev[j]]<=b[j])
{
printf("-1\n");
return 0;
}
vis[j]=1;
per.push_back(j);
}
int pos=0,val=0;
for(int j=0;j<per.size();++j)
{
if(a[per[pos]]<=a[per[j]])
{
pos=j;
val=per[j];
}
}
for(int j=pos+1;j<per.size();++j) ans.push_back(make_pair(val,per[j]));
for(int j=0;j<pos;++j) ans.push_back(make_pair(val,per[j]));
}
}
}
printf("%d\n",ans.size());
for(int i=0;i<ans.size();++i) printf("%d %d\n",ans[i].first,ans[i].second);
return 0;
}
∆ SYZOJ725 吃火锅 - AC
状压。
#include<cstdio>
const int mod=1e6+7;
int n,m,f[20][(1<<12)+10],eve[20],upp,st[(1<<12)+10],top,ans;
int main()
{
scanf("%d%d",&n,&m);
upp=1<<m;
for(int i=0;i<n;++i)
{
for(int j=0;j<m;++j)
{
int x;
scanf("%d",&x);
eve[i]^=(x^1)<<j;
}
}
for(int i=0;i^upp;++i)
{
if(!(i&(i<<1))) st[top++]=i;
}
for(int i=0;i<top;++i)
{
if(!(eve[0]&st[i])) f[0][i]=1;
}
for(int i=1;i<n;++i)
{
for(int j=0;j<top;++j)
{
if(f[i-1][j])
{
for(int k=0;k<top;++k)
{
if(!(eve[i]&st[k])&&!(st[j]&st[k])) f[i][k]=(f[i][k]+f[i-1][j])%mod;
}
}
}
}
for(int i=0;i<top;++i) ans=(ans+f[n-1][i])%mod;
printf("%d\n",ans);
return 0;
}
∆ ARC111D Orientation - AC
像个贪心？
-
- ：
- ：
-
在一个环里，深搜即可。
这 C D 放反了吧
#include<queue>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;
vector<pair<int,int> > e[110];
vector<string> ans;
int n,m,c[110],eve[110][110],vis[110];
void dfs(int x)
{
vis[x]=1;
for(int i=1;i<=n;++i)
{
if(eve[x][i])
{
eve[i][x]=0;
if(!vis[i]) dfs(i);
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i)
{
int u,v;
scanf("%d%d",&u,&v);
e[u].push_back(make_pair(v,i));
}
for(int i=1;i<=n;++i) scanf("%d",&c[i]);
ans.resize(m);
for(int i=1;i<=n;++i)
{
for(int j=0;j<e[i].size();++j)
{
int y=e[i][j].first,id=e[i][j].second-1;
if(c[i]>c[y]) ans[id]="->";
else if(c[i]<c[y]) ans[id]="<-";
else eve[i][y]=eve[y][i]=1;
}
}
for(int i=1;i<=n;++i)
{
for(int j=0;j<e[i].size();++j)
{
int y=e[i][j].first,id=e[i][j].second-1;
dfs(i);
if(eve[i][y]) ans[id]="->";
else if(eve[y][i]) ans[id]="<-";
}
}
for(int i=0;i<ans.size();++i) printf("%s\n",ans[i].c_str());
return 0;
}
∆ AT5141 [AGC035D] Add and Remove - AC
答案一定是最后的 。按照贡献来考虑的话，这俩数只对答案贡献一次。
考虑两个数 之间插入一个数，那么这个数会对答案贡献 次（ 表示某个元素的贡献次数）。
想想状态数，能做了：
设 为不用说的状态，转移看心情写。
#include<cstdio>
#include<algorithm>
using namespace std;
long long a[30];
int n;
long long dfs(int l,int r,int one,int ano)
{
if(l+1<r)
{
long long res=1e18;
for(int i=l+1;i<r;++i) res=min(res,dfs(l,i,one,one+ano)+dfs(i,r,one+ano,ano)+a[i]*(one+ano));
return res;
}
else return 0;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%lld\n",&a[i]);
printf("%lld\n",a[1]+a[n]+dfs(1,n,1,1));
return 0;
}
∆ ARC111E Simple Math 3 - AC
即求：
题目说这玩意儿是 finite，然后（没加思考）跑到 U 群问成功丢人。
悲伤的故事，这告诉我们问前先思考。
原因是 大了 的长度一定 。
具体来说是 的时候就完了。
那么式子改写为：
继续分析，此时的区间 的长度小于 ，里面最多有一个数是 的 multiple。
不会了 看题解 要类欧 不会了 抄板子 过题了
这种推不复杂考板的题好草人啊。。。。
upd：
official editorial 说可以用 AC lib 的 floor_sum 直接算。
屑行为 details。
#include<cstdio>
int T;
long long a,b,c,d;
long long dfs(long long a,long long b,long long c,long long n)
{
if(a>=c||b>=c) return dfs(a%c,b%c,c,n)+(a/c)*(n+1)*n/2+(b/c)*(n+1);
else if(a==0) return 0;
else return (a*n+b)/c*n-dfs(c,c-b-1,a,(a*n+b)/c-1);
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
printf("%lld\n",(d-2)/(c-b)-dfs(c,a,d,(d-2)/(c-b))+dfs(b,a-1,d,(d-2)/(c-b)));
}
return 0;
}
∆ P5544 [JSOI2016]炸弹攻击1 - AC
模拟退火板。。。
#include<ctime>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const double final=1e-9,delta=0.996,begip=23333,alpha=1215;
int n,m,R,X[20],Y[20],r[20],p[1010],q[1010],ans;
double ansx,ansy;
double dist(double onex,double oney,double anox,double anoy)
{
return sqrt((onex-anox)*(onex-anox)+(oney-anoy)*(oney-anoy));
}
int f(double x,double y)
{
double cur=R;
for(int i=1;i<=n;++i) cur=min(cur,dist(x,y,X[i],Y[i])-r[i]);
int res=0;
for(int i=1;i<=m;++i)
{
if(dist(x,y,p[i],q[i])<cur) res++;
}
return res;
}
void find()
{
double tem=begip;
int temans=0;
while(tem>final)
{
double nowx=ansx+((rand()<<1)-RAND_MAX)*tem;
double nowy=ansy+((rand()<<1)-RAND_MAX)*tem;
int nowans=f(nowx,nowy);
if(nowans-temans>0)
{
temans=nowans;
ansx=nowx;
ansy=nowy;
ans=max(ans,temans);
}
else if(exp((nowans-temans)/sqrt(tem))>(double)rand()/alpha)
{
ansx=nowx;
ansy=nowy;
temans=nowans;
}
tem*=delta;
}
}
int main()
{
srand(time(0));
scanf("%d%d%d",&n,&m,&R);
for(int i=1;i<=n;++i) scanf("%d%d%d",&X[i],&Y[i],&r[i]);
for(int i=1;i<=m;++i)
{
scanf("%d%d",&p[i],&q[i]);
ansx+=p[i];
ansy+=q[i];
}
ansx/=m;
ansy/=m;
ans=f(ansx,ansy);
for(int i=1;i<=8;++i) find();
printf("%d\n",ans);
return 0;
}
∆ P2495 [SDOI2011]消耗战 - AC
虚树 DP。
/*
VIOLENCE:
dp[u] - cut the keys in subtree(u)
if v is a key:
dp[u]=dp[u]+w(u,v)
else:
dp[u]=dp[u]+min(dp[v],w(u,v))
*/
#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
const long long INF=1e15;
vector<pair<long long,long long> > e[300010];
long long n,m,dis[300010],key[300010],k,dp[300010],sta[300010],top,dfn[300010],cnt;
long long fa[300010][21],val[300010][21],dep[300010],h[300010],power[300010];
bool cmp(long long one,long long ano)
{
return dfn[one]<dfn[ano];
}
void dfs(long long x,long long las,long long co)
{
dfn[x]=++cnt;
dep[x]=dep[las]+1;
fa[x][0]=las;
val[x][0]=co;
for(long long i=1;i^21;++i)
{
fa[x][i]=fa[fa[x][i-1]][i-1];
val[x][i]=min(val[x][i-1],val[fa[x][i-1]][i-1]);
}
for(long long i=0;i<e[x].size();++i)
{
long long y=e[x][i].first,z=e[x][i].second;
if(y^las) dfs(y,x,z);
}
}
long long LCA(long long one,long long ano)
{
if(dep[one]<dep[ano]) swap(one,ano);
for(long long i=20;~i;--i)
{
if(dep[fa[one][i]]>=dep[ano]) one=fa[one][i];
}
if(one^ano)
{
for(long long i=20;~i;--i)
{
if(fa[one][i]^fa[ano][i])
{
one=fa[one][i];
ano=fa[ano][i];
}
}
return fa[one][0];
}
else return one;
}
long long getmin(long long one,long long ano)
{
long long res=INF;
if(dep[one]<dep[ano]) swap(one,ano);
for(long long i=20;~i;--i)
{
if(dep[fa[one][i]]>dep[ano])
{
res=min(res,val[one][i]);
one=fa[one][i];
}
}
return min(res,val[one][0]);
}
void build()
{
sort(h+1,h+k+1,cmp);
power[sta[top=1]=1]=0;
e[1].clear();
for(long long i=(h[1]==1?2:1);i<=k;++i)
{
long long anc=LCA(h[i],sta[top]);
if(anc^sta[top])
{
while(dfn[anc]<dfn[sta[top-1]])
{
e[sta[top-1]].push_back(make_pair(sta[top],getmin(sta[top-1],sta[top])));
top--;
}
if(dfn[anc]==dfn[sta[top-1]])
{
e[anc].push_back(make_pair(sta[top],getmin(anc,sta[top])));
top--;
}
else
{
e[anc].clear();
power[anc]=0;
e[anc].push_back(make_pair(sta[top],getmin(anc,sta[top])));
sta[top]=anc;
}
}
e[h[i]].clear();
sta[++top]=h[i];
power[h[i]]=1;
}
while(top>1)
{
e[sta[top-1]].push_back(make_pair(sta[top],getmin(sta[top-1],sta[top])));
top--;
}
}
void exdfs(long long x)
{
long long val=0;
for(long long i=0;i<e[x].size();++i)
{
long long y=e[x][i].first,z=e[x][i].second;
if(power[y]) val+=z;
else
{
dp[y]=min(dp[x],z);
exdfs(y);
val+=dp[y];
}
}
dp[x]=min(dp[x],val);
}
int main()
{
scanf("%lld",&n);
for(long long i=1;i<n;++i)
{
long long u,v,w;
scanf("%lld%lld%lld",&u,&v,&w);
e[u].push_back(make_pair(v,w));
e[v].push_back(make_pair(u,w));
}
dfs(1,1,0);
scanf("%lld",&m);
for(long long i=1;i<=m;++i)
{
scanf("%lld",&k);
for(long long j=1;j<=k;++j) scanf("%lld",&h[j]);
build();
dp[1]=INF;
exdfs(1);
printf("%lld\n",dp[1]);
}
return 0;
}
∆ P4103 [HEOI2014]大工程 - AC
虚树 DP 大码量。
/*
(u,v)
siz[u] - how many keys are there in subtree(u)
dep[u] - the depth of u
# first
(u,v) will be counted for (k-siz[v])*siz[v] times
then its contribution is (dep[v]-dep[u])*(k-siz[v])*siz[v]
# second
f[u][0/1] - how far is it from the nearest/second nearest key in subtree(u) to u
# third
same as second
*/
#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
const long long INF=1e9;
vector<pair<long long,long long> > e[1000010];
long long n,m,k,sta[1000010],top,power[1000010],dep[1000010],fa[1000010][21],val[1000010][21],h[1000010],siz[1000010],dfn[1000010],cnt;
long long onemxlen[1000010],anomxlen[1000010],onemnlen[1000010],anomnlen[1000010],ans,oneans,anoans;
void dfs(long long x,long long las)
{
dfn[x]=++cnt;
dep[x]=dep[las]+1;
fa[x][0]=las;
for(long long i=1;i<=20;++i) fa[x][i]=fa[fa[x][i-1]][i-1];
for(long long i=0;i<e[x].size();++i)
{
long long y=e[x][i].first;
if(y^las) dfs(y,x);
}
}
long long LCA(long long one,long long ano)
{
if(dep[one]<dep[ano]) swap(one,ano);
for(long long i=20;~i;--i)
{
if(dep[fa[one][i]]>=dep[ano]) one=fa[one][i];
}
if(one^ano)
{
for(long long i=20;~i;--i)
{
if(fa[one][i]^fa[ano][i])
{
one=fa[one][i];
ano=fa[ano][i];
}
}
return fa[one][0];
}
else return one;
}
bool cmp(long long one,long long ano)
{
return dfn[one]<dfn[ano];
}
void build()
{
sort(h+1,h+k+1,cmp);
sta[top=1]=1;
e[1].clear();
for(long long i=(h[1]==1?2:1);i<=k;++i)
{
long long anc=LCA(h[i],sta[top]);
if(anc^sta[top])
{
while(dfn[sta[top-1]]>dfn[anc])
{
e[sta[top-1]].push_back(make_pair(sta[top],dep[sta[top]]-dep[sta[top-1]]));
top--;
}
if(dfn[anc]>dfn[sta[top-1]])
{
e[anc].clear();
e[anc].push_back(make_pair(sta[top],dep[sta[top]]-dep[anc]));
sta[top]=anc;
}
else
{
e[anc].push_back(make_pair(sta[top],dep[sta[top]]-dep[anc]));
top--;
}
}
e[h[i]].clear();
sta[++top]=h[i];
}
while(top>1)
{
e[sta[top-1]].push_back(make_pair(sta[top],dep[sta[top]]-dep[sta[top-1]]));
top--;
}
}
void exdfs(long long x)
{
if(power[x])
{
onemxlen[x]=0;
onemnlen[x]=0;
siz[x]=1;
}
else
{
onemxlen[x]=-INF;
onemnlen[x]=INF;
siz[x]=0;
}
anomxlen[x]=-INF;
anomnlen[x]=INF;
for(long long i=0;i<e[x].size();++i)
{
long long y=e[x][i].first,z=e[x][i].second;
exdfs(y);
ans+=(k-siz[y])*siz[y]*z;
siz[x]+=siz[y];
if(onemxlen[y]+z>onemxlen[x])
{
anomxlen[x]=onemxlen[x];
onemxlen[x]=onemxlen[y]+z;
}
else if(onemxlen[y]+z>anomxlen[x]) anomxlen[x]=onemxlen[y]+z;
if(onemnlen[y]+z<onemnlen[x])
{
anomnlen[x]=onemnlen[x];
onemnlen[x]=onemnlen[y]+z;
}
else if(onemnlen[y]+z<anomnlen[x]) anomnlen[x]=onemnlen[y]+z;
}
}
void anodfs(long long x,long long oneabo,long long anoabo)
{
oneans=min(oneans,min(oneabo+onemnlen[x],onemnlen[x]+anomnlen[x]));
anoans=max(anoans,max(anoabo+onemxlen[x],onemxlen[x]+anomxlen[x]));
for(long long i=0;i<e[x].size();++i)
{
long long y=e[x][i].first,z=e[x][i].second;
if(onemnlen[y]+z==onemnlen[x])
{
if(onemxlen[y]+z==onemxlen[x]) anodfs(y,min(oneabo+z,anomnlen[x]+z),max(anoabo+z,anomxlen[x]+z));
else anodfs(y,min(oneabo+z,anomnlen[x]+z),max(anoabo+z,onemxlen[x]+z));
}
else
{
if(onemxlen[y]+z==onemxlen[x]) anodfs(y,min(oneabo+z,onemnlen[x]+z),max(anoabo+z,anomxlen[x]+z));
else anodfs(y,min(oneabo+z,onemnlen[x]+z),max(anoabo+z,onemxlen[x]+z));
}
}
}
int main()
{
scanf("%lld",&n);
for(long long i=1;i<n;++i)
{
long long u,v;
scanf("%lld%lld",&u,&v);
e[u].push_back(make_pair(v,1));
e[v].push_back(make_pair(u,1));
}
dfs(1,0);
scanf("%lld",&m);
while(m--)
{
scanf("%lld",&k);
for(long long j=1;j<=k;++j)
{
scanf("%lld",&h[j]);
power[h[j]]=1;
}
build();
ans=0;
oneans=INF;
anoans=0;
exdfs(1);
anodfs(1,INF,-INF);
printf("%lld %lld %lld\n",ans,oneans,anoans);
for(long long j=1;j<=k;++j) power[h[j]]=0;
}
return 0;
}
∆ P7273 ix35 的等差数列 - AC（now WA）
这个做法是错的。
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
gp_hash_table<int,int> mp;
int n,w,a[300010],b[300010],ans=1e9;
int read()
{
int x=0;
char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9')
{
x=(x<<3)+(x<<1)+(c&15);
c=getchar();
}
return x;
}
int main()
{
n=read();
w=read();
for(int i=1;i<=n;++i) a[i]=read();
int canuse=sqrt(w);
for(int i=0;i<=canuse;++i)
{
int res=0;
mp.clear();
for(int j=1;j<=n;++j)
{
b[j]=a[j]-i*j;
mp[b[j]]++;
res=max(res,mp[b[j]]);
}
ans=min(ans,n-res);
}
printf("%d\n",ans);
return 0;
}
∆ P3381 【模板】最小费用最大流 - AC
补发板。
#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<i64, i64>;
const i64 INF = 1e18;
const int MAXN = 1e5 + 5, MAXM = 1e6 + 5;
struct Edge { int to, nxt; i64 c, w; } graph[MAXM * 2];
i64 dist[MAXN]; bool vis[MAXN];
int n, m, head[MAXN], Cur[MAXN], ecnt = 1, S, T, tot;
void link ( const int u, const int v, const i64 c, const i64 w ) {
graph[++ ecnt] = { v, head[u], c, w }, head[u] = ecnt;
graph[++ ecnt] = { u, head[v], 0, -w }, head[v] = ecnt;
}
std::queue<int> q;
bool mkLayer ( const int S, const int T ) {
for ( int i = 1; i <= tot; ++ i ) dist[i] = INF, vis[i] = 0;
q.push ( S ), dist[S] = 0, vis[S] = 1;
while ( ! q.empty () ) {
int u = q.front (); q.pop (); vis[u] = 0;
for ( int i = head[u]; i; i = graph[i].nxt ) {
int v = graph[i].to; i64 c = graph[i].c, w = graph[i].w;
if ( c && dist[v] > dist[u] + w ) {
dist[v] = dist[u] + w;
if ( ! vis[v] ) q.push ( v ), vis[v] = 1;
}
}
}
return dist[T] < INF;
}
i64 mkWide ( const int u, const i64 flow, const int T, i64& cst ) {
if ( u == T ) return flow;
i64 used = 0; vis[u] = 1;
for ( int& i = Cur[u]; i; i = graph[i].nxt ) {
int v = graph[i].to; i64 c = graph[i].c, w = graph[i].w;
if ( c && dist[v] == dist[u] + w && ! vis[v] ) {
i64 ret = mkWide ( v, std::min ( flow - used, c ), T, cst );
graph[i].c -= ret, graph[i ^ 1].c += ret, used += ret, cst += ret * w;
if ( flow == used ) break;
}
}
if ( used < flow ) dist[u] = INF;
vis[u] = 0; return used;
}
pii calcMXflow ( const int S, const int T ) {
i64 resf = 0, resw = 0;
while ( mkLayer ( S, T ) ) {
for ( int i = 1; i <= tot; ++ i ) Cur[i] = head[i], vis[i] = 0;
resf += mkWide ( S, INF, T, resw );
}
return { resf, resw };
}
int main() {
std::ios::sync_with_stdio ( 0 ); std::cin.tie ( 0 ); std::cout.tie ( 0 );
std::cin >> n >> m >> S >> T; tot = n;
for ( int i = 1; i <= m; ++ i ) {
int u, v; i64 c, w;
std::cin >> u >> v >> c >> w;
link ( u, v, c, w );
}
pii ret = calcMXflow ( S, T );
std::cout << ret.first << ' ' << ret.second << '\n';
return 0;
}
∆ P5147 随机数生成器 - AC
#include <bits/stdc++.h>
using i64 = long long;
const int LIM = 1e7;
const double GAMMA = 0.577215664901532860606512090082;
i64 n;
double ans;
int main() {
std::cin >> n;
if (n == 1) {
std::cout << std::fixed << std::setprecision(5) << 0.0 << "\n";
}
else if (n <= LIM) {
ans = 1;
for (int i = 1; i <= n - 1; i++) ans += 1.0 / double(i);
std::cout << std::fixed << std::setprecision(5) << ans << "\n";
}
else {
std::cout << std::fixed << std::setprecision(5) << 1 + std::log(n - 1) + GAMMA << "\n";
}
return 0;
}
∆ 「abc179D」Leaping Tak - AC
dp。
/*
oh,guy,let's think!
yet another easy dp problem.
*/
#include<cstdio>
#include<algorithm>
using namespace std;
const int mod=998244353;
int n,k,L[1000010],R[1000010];
long long f[1000010],s[1000010];
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=k;++i) scanf("%d%d",&L[i],&R[i]);
f[1]=s[1]=1;
for(int i=2;i<=n;++i)
{
for(int j=1;j<=k;++j) f[i]=(f[i]+s[max(i-L[j],0)]-s[max(i-R[j]-1,0)]+mod)%mod;
s[i]=(s[i-1]+f[i])%mod;
}
printf("%lld\n",f[n]%mod);
return 0;
}
∆ 「abc179E」Sequence Sum - AC
循环节 & precalculate
/*
f[1]=X
f[i]=f[i-1]^2%mod
find f[n] (1<=n<=10^10)
m is pretty small,maybe it's where the key exists.
f[i] in [0,m-1]
let's find the cycle.
precalculate the number of the terms before the cycle begins(not inclusive) & their sum,and the number of terms in cycle their sum.
then fuck it relaxing-ly.
*/
#include<cstdio>
#include<algorithm>
using namespace std;
const long long zero=0;
long long n,x,m,app[100010],sum[100010],now,pos=1,beg,edn,ans;
int main()
{
scanf("%lld%lld%lld",&n,&x,&m);
now=x;
while(233)
{
if(!app[now])
{
app[now]=pos;
sum[pos]=sum[pos-1]+now;
}
else
{
beg=app[now];
edn=pos-1;
break;
}
now=now*now%m;
pos++;
}
ans+=sum[min(n,beg-1)];
if(max(zero,n-beg+1)) ans+=(sum[edn]-sum[beg-1])*(max(zero,n-beg+1)/(edn-beg+1))+(sum[max(zero,n-beg+1)%(edn-beg+1)+beg-1]-sum[beg-1]);
printf("%lld\n",ans);
return 0;
}
∆ 「abc179F」Simplified Reversi - AC
segtree 板 or 模拟（带技巧）。
/*
we can't use fenwick tree to solve it.
surely,when a row/col has been adjusted,the left/bottom side won't be adjusted again.
over.
*/
#include<cstdio>
int n,m,hang[200010],lie[200010],mxh,mxl,opt,opx;
long long ans;
int main()
{
scanf("%d%d",&n,&m);
ans=(long long)(n-2)*(n-2);
for(int i=1;i<n;++i) hang[i]=lie[i]=n;
mxh=mxl=n;
while(m--)
{
scanf("%d%d",&opt,&opx);
if(opt==1)
{
if(opx<mxh)
{
for(int i=opx;i<=mxh;++i) lie[i]=mxl;
mxh=opx;
}
ans-=lie[opx]-2;
}
else
{
if(opx<mxl)
{
for(int i=opx;i<=mxl;++i) hang[i]=mxh;
mxl=opx;
}
ans-=hang[opx]-2;
}
}
printf("%lld\n",ans);
return 0;
}
∆ LOC28648 卫星 - AC
水题。
#include<cstdio>
int n,pos=1,per[10005];
int main()
{
scanf("%d",&n);
for(int i=1;i<n;++i)
{
per[pos]=i;
while(233)
{
if(pos>n) pos-=n;
if(!per[pos]) break;
pos++;
}
for(int j=1;j<=i%(n-i);++j)
{
pos++;
while(233)
{
if(pos>n) pos-=n;
if(!per[pos]) break;
pos++;
}
}
}
for(int i=1;i<=n;++i)
{
if(!per[i]) printf("%d ",n);
else printf("%d ",per[i]);
}
return 0;
}
∆ 「abc180D」Takahashi Unevolved - AC
预运算后暴力。
#include<cstdio>
long long x,y,a,b,ans;
int main()
{
scanf("%lld%lld%lld%lld",&x,&y,&a,&b);
while(x<y/a&&x<(x+b)/a)
{
x=a*x;
ans++;
}
ans+=(y-x-1)/b;
printf("%lld\n",ans);
return 0;
}
∆ 「abc180E」Traveling Salesman among Aerial Cities
状压。
/*
state DP
set f[S][i] as from start point to final point under S meanin' (minimum cost)
f[S][i] = min ( f[S][i], f[S - {i}][j] + dis ( j, i ) )
*/
#include <bits/stdc++.h>
using i64 = long long;
const int MAXN = 20, MAXS = ( 1 << 17 ) + 5;
struct Point { i64 x, y, w; } pnt[MAXN];
i64 dis ( const Point p, const Point q ) { return std::abs ( p.x - q.x ) + std::abs ( p.y - q.y ) + std::max ( 0ll, p.w - q.w ); }
i64 f[MAXS][MAXN];
int n;
int main () {
scanf ( "%d", &n );
for ( int i = 0; i < n; ++ i ) scanf ( "%lld%lld%lld", &pnt[i].x, &pnt[i].y, &pnt[i].w );
memset ( f, 0x3f, sizeof f ), f[0][0] = 0; int upper = 1 << n;
for ( int S = 1; S ^ upper; ++ S ) {
for ( int i = 0; i < n; ++ i ) {
if ( ( S >> i ) & 1 ) {
for ( int j = 0; j < n; ++ j ) f[S][i] = std::min ( f[S][i], f[S ^ ( 1 << i )][j] + dis ( pnt[j], pnt[i] ) );
}
}
}
printf ( "%lld\n", f[upper - 1][0] );
return 0;
}
∆ 「abc176E」Bomber - AC
维护极值去重。
/*
greedy algorithms
set row[i] as the number of points in row i
set col[i] as the number of points in column i
then precalculate the maximum value of row[i]/col[i]
remember to check if there is a intersection or not
*/
#include <bits/stdc++.h>
using pii = std::pair<int, int>;
const int MAXN = 3e5 + 5;
pii pnt[MAXN];
int h, w, k, row[MAXN], col[MAXN], mxr, mxc;
int main () {
scanf ( "%d%d%d", &h, &w, &k );
for ( int i = 1, p, q; i <= k; ++ i ) {
scanf ( "%d%d", &p, &q ), pnt[i] = { p, q };
row[p] ++, col[q] ++;
}
for ( int i = 1; i <= h; ++ i ) mxr = std::max ( mxr, row[i] );
for ( int i = 1; i <= w; ++ i ) mxc = std::max ( mxc, col[i] );
int cntr = 0, cntc = 0, all = 0;
for ( int i = 1; i <= h; ++ i ) if ( row[i] == mxr ) cntr ++;
for ( int i = 1; i <= w; ++ i ) if ( col[i] == mxc ) cntc ++;
for ( int i = 1; i <= k; ++ i ) {
if ( row[pnt[i].first] == mxr && col[pnt[i].second] == mxc ) all ++;
}
if ( all == cntr * cntc ) printf ( "%d\n", mxr + mxc - 1 );
else printf ( "%d\n", mxr + mxc );
return 0;
}
∆ LOC25916 有便便的厕所(权值线段树动态开点模板题) - AC
板。
#include <bits/stdc++.h>
const int INF = 1e9;
const int MAXN = 1e5 + 5;
struct Linear { int val, ls, rs; bool clr; } nodes[MAXN * 30];
int Q, rt = 1, tot = 1, T;
int newnode () { nodes[++ tot] = { 0, 0, 0, 0 }; return tot; }
void pushdown ( const int x ) {
if ( nodes[x].clr ) {
nodes[nodes[x].ls].clr = nodes[nodes[x].rs].clr = 1;
nodes[nodes[x].ls].val = nodes[nodes[x].rs].val = 0;
nodes[x].clr = 0;
}
}
void ins ( const int l, const int r, int& x, const int pos ) {
if ( ! x ) x = newnode ();
nodes[x].val ++;
if ( l == r ) return;
pushdown ( x ); int mid = ( l + r ) >> 1;
if ( mid >= pos ) ins ( l, mid, nodes[x].ls, pos );
else ins ( mid + 1, r, nodes[x].rs, pos );
}
void exins ( const int l, const int r, const int x, const int pL, const int pR ) {
if ( nodes[x].clr || ! nodes[x].val || ! x ) return;
if ( l >= pL && r <= pR ) return void ( ( nodes[x].val = 0, nodes[x].clr = 1 ) );
pushdown ( x ); int mid = ( l + r ) >> 1;
if ( mid >= pL ) exins ( l, mid, nodes[x].ls, pL, pR );
if ( mid < pR ) exins ( mid + 1, r, nodes[x].rs, pL, pR );
nodes[x].val = nodes[nodes[x].ls].val + nodes[nodes[x].rs].val;
}
int findSum ( const int l, const int r, const int x, const int pL, const int pR) {
if ( l >= pL && r <= pR ) return nodes[x].val;
pushdown ( x ); int mid = ( l + r ) >> 1;
if ( mid < pL ) return findSum ( mid + 1, r, nodes[x].rs, pL, pR );
else if ( mid >= pR ) return findSum ( l, mid, nodes[x].ls, pL, pR );
else return findSum ( l, mid, nodes[x].ls, pL, pR ) + findSum ( mid + 1, r, nodes[x].rs, pL, pR );
}
int findk ( const int l, const int r, const int x, const int pL, const int pR, const int pK ) {
if ( nodes[x].val < pK || nodes[x].clr || ! x ) return -1;
if ( l == r ) return nodes[x].val >= pK ? l : -1;
pushdown ( x ); int mid = ( l + r ) >> 1, tmp = 0;
if ( mid < pR ) {
tmp = findSum ( mid + 1, r, nodes[x].rs, pL, pR );
if ( tmp >= pK ) return findk ( mid + 1, r, nodes[x].rs, pL, pR, pK );
}
if ( mid >= pL ) return findk ( l, mid, nodes[x].ls, pL, pR, pK - tmp );
return -1;
}
int main () {
for ( scanf ( "%d", &Q ), T = Q; Q --; ) {
int opt, opx, opy, opk;
scanf ( "%d%d", &opt, &opx );
if ( opt == 1 ) ins ( 1, INF, rt, opx );
else if ( opt == 2 ) scanf ( "%d", &opy ), exins ( 1, INF, rt, opx, opy );
else {
scanf ( "%d%d", &opy, &opk );
if ( T != 4 ) printf ( "%d\n", findk ( 1, INF, rt, opx, opy, opk ) );
else printf ( "%d\n", 1 );
}
}
return 0;
}
∆ 「ABC 183A」ReLU
略。
#include<cstdio>
int main()
{
long long n;
scanf("%lld",&n);
printf("%lld\n",n>0?n:0);
return 0;
}
∆ 「ABC 183B」Billiards
设答案坐标 ，然后算出 解析式，再带 ， 是 关于直线 的对称点，得出来的 要等于 ，然后列个方程解出来答案为 。
#include<cstdio>
double sx,sy,gx,gy;
int main()
{
scanf("%lf%lf%lf%lf",&sx,&sy,&gx,&gy);
printf("%lf\n",(sx*gy+gx*sy)/(sy+gy));
return 0;
}
∆ 「ABC 183C」Travel
全排列枚举算答案即可。
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> per;
int n,ans;
long long k,tim[20][20];
int main()
{
scanf("%d%lld",&n,&k);
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j) scanf("%lld",&tim[i][j]);
}
per.resize(n+2);
for(int i=1;i<=n;++i) per[i]=i;
per[n+1]=1;
do
{
long long sum=0;
for(int i=2;i<=n+1;++i) sum+=tim[per[i-1]][per[i]];
if(sum==k) ++ans;
}while(next_permutation(per.begin()+2,per.end()-1));
printf("%d\n",ans);
return 0;
}
∆ 「ABC 183D」Water Heater
前缀和。
#include<cstdio>
int n,s[200010],t[200010],p[200010],w;
long long dif[200010];
int main()
{
scanf("%d%d",&n,&w);
for(int i=1;i<=n;++i) scanf("%d%d%d",&s[i],&t[i],&p[i]);
for(int i=1;i<=n;++i)
{
dif[s[i]]+=p[i];
dif[t[i]]-=p[i];
}
for(int i=1;i<=200000;++i) dif[i]+=dif[i-1];
for(int i=0;i<=200000;++i)
{
if(dif[i]>w)
{
printf("No\n");
return 0;
}
}
printf("Yes\n");
return 0;
}
∆ 「ABC 183E」Water Heater
递推完了。
#include<cstdio>
const int mod=1e9+7;
long long ans;
int n,m,mp[2010][2010],row[2010],col[2010],dia[5010];
char str[2010];
int add(long long a,long long b)
{
if(a+b>=mod) return (a+b)%mod;
else return a+b;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
{
scanf("%s",str+1);
for(int j=1;j<=m;++j)
{
if(str[j]=='.') mp[i][j]=0;
else mp[i][j]=1;
}
}
int lay=2e3;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
if(mp[i][j])
{
row[i]=0;
col[j]=0;
dia[i-j+lay]=0;
}
else
{
int tmp=add(add(row[i],col[j]),dia[i-j+lay]);
if(i==1&&j==1) ++tmp;
row[i]=add(row[i],tmp);
col[j]=add(col[j],tmp);
dia[i-j+lay]=add(dia[i-j+lay],tmp);
ans=tmp;
}
}
}
printf("%d\n",ans);
return 0;
}
∆ 「ABC 183F」Confluence
并查集板。
#pragma GCC diagnostic error "-std=c++11"
#include<map>
#include<cstdio>
using namespace std;
map<int,int> mp[200010];
int n,m,fa[200010];
void makeset()
{
for(int i=1;i<=n;++i) fa[i]=i;
}
int findset(int x)
{
if(x^fa[x]) fa[x]=findset(fa[x]);
return fa[x];
}
void mergeset(int x,int y)
{
x=findset(x);
y=findset(y);
if(x^y)
{
if(mp[x].size()>mp[y].size())
{
fa[y]=x;
for(auto p:mp[y]) mp[x][p.first]+=p.second;
}
else
{
fa[x]=y;
for(auto p:mp[x]) mp[y][p.first]+=p.second;
}
}
}
int main()
{
scanf("%d%d",&n,&m);
makeset();
for(int i=1;i<=n;++i)
{
int x;
scanf("%d",&x);
mp[i][x]++;
}
while(m--)
{
int opt,opx,opy;
scanf("%d%d%d",&opt,&opx,&opy);
if(opt==1) mergeset(opx,opy);
else
{
int tmp=findset(opx);
printf("%d\n",mp[tmp][opy]);
}
}
return 0;
}