【日常小测】最长路径

解题报告

1. 任意一个竞赛图一定存在哈密尔顿路径
2. 一个竞赛图存在哈密尔顿回路当且仅当这个竞赛图强连通

$ans_{x} = \sum\limits_{i = 1}^{x}{{{n – 1}\choose{i – 1}} g_i {{n – i}\choose{x – i}} f_{x – i} f_{n – x}}$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 2009;

int n, MOD, f[N], g[N], pw[N * N], C[N][N];

char c = getchar();
int ret = 0, f = 1;
while (c < '0' || c > '9') {
f = c == '-'? -1: 1;
c = getchar();
}
while ('0' <= c && c <= '9') {
ret = ret * 10 + c - '0';
c = getchar();
}
return ret * f;
}

int main() {
freopen("path.in", "r", stdin);
freopen("path.out", "w", stdout);
pw[0] = 1;
for (int i = 1; i < n * n; i++) {
pw[i] = (pw[i - 1] << 1) % MOD;
}
C[0][0] = 1;
for (int i = 1; i <= n; ++i) {
C[i][0] = 1;
for (int j = 1; j <= n; j++) {
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
}
}
f[0] = g[0] = 1;
for (int i = 1; i <= n; i++) {
f[i] = g[i] = pw[i * (i - 1) >> 1];
for (int j = 1; j < i; j++) {
g[i] = (g[i] - (LL)C[i][j] * g[j] % MOD * f[i - j]) % MOD;
}
}
for (int x = 1; x <= n; x++) {
int ans = 0;
for (int i = 1; i <= x; i++) {
ans = (ans + (LL)C[n - 1][i - 1] * g[i] % MOD * C[n - i][x - i] % MOD * f[x - i] % MOD * f[n - x]) % MOD;
}
printf("%d\n", ans > 0? ans: ans + MOD);
}
return 0;
}

【算法笔记】Kosaraju算法

前言

$T1$就是$Claris$用$bitset$配合这个算法把求$SCC$优化到了$\frac{n^2}{32}$

算法概述

$step \ 1.$ DFS一遍，记录下后序遍历的顺序
$step \ 2.$ 沿后续遍历的逆序、沿反向边再DFS一遍，每一个连通块即为一个SCC

代码实现

int scc_cnt, vis[N];
vector<int> scc_cnt[N], que;
void DFS0(int w) {
vis[w] = 0;
for (int i = head[w]; i; i = nxt[i]) {
if (!vis[to[i]]) {
DFS0(to[i]);
}
}
que[++tot] = w;
}
void DFS1(int w) {
scc[scc_cnt].push_back(w);
vis[w] = 1;
for (int i = rev_head[w]; i; i = nxt[i]) {
if (!vis[to[i]]) {
DFS1(to[i]);
}
}
}
void solve() {
que.clear();
memset(vis, 0, sizeof(vis));
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
DFS0(i);
}
}
scc_cnt = 0;
memset(vis, 0, sizeof(vis));
for (int i = (int)que.size() - 1; ~i; i--) {
if (!vis[que[i]]) {
scc_cnt++;
DFS1(que[i]);
}
}
}

【日常小测】友好城市

Code

#include<bits/stdc++.h>
#define LL long long
#define UI unsigned int
#define lowbit(x) ((x)&-(x))
using namespace std;

const int N = 159;
const int M = 300009;
const int QQ = 50009;
const int BlockSize = 1200;
const UI ALL = (1ll << 32) - 1;

int n, m, q, U[M], V[M], ans[QQ];
struct Query{
int l, r, blk, id;
inline bool operator < (const Query &Q) const {
return blk < Q.blk || (blk == Q.blk && r < Q.r);
}
}qy[QQ];
struct Bitset{
UI v[5];
inline void flip(int x) {
v[x >> 5] ^= 1 << (x & 31);
}
inline void set(int x) {
v[x >> 5] |= 1 << (x & 31);
}
inline void reset() {
memset(v, 0, sizeof(v));
}
inline bool operator [](int x) {
return v[x >> 5] & (1 << (x & 31));
}
}g[N], rg[N], PreG[M / BlockSize + 9][N], PreRG[M / BlockSize + 9][N];

char c = getchar();
int ret = 0, f = 1;
while (c < '0' || c > '9') {
f = c == '-'? -1: 1;
c = getchar();
}
while ('0' <= c && c <= '9') {
ret = ret * 10 + c - '0';
c = getchar();
}
return ret * f;
}

inline void AddEdge(int u, int v, Bitset *a1, Bitset *a2) {
a1[u].set(v);
a2[v].set(u);
}

class Kosaraju{
vector<int> que;
Bitset vis;
public:
inline int solve() {
vis.reset();
que.clear();
for (int i = 1; i <= n; ++i) {
if (!vis[i]) {
dfs0(i);
}
}
vis.reset();
int ret = 0;
for (int j = n - 1; ~j; j--) {
int i = que[j];
if (!vis[i]) {
int cnt = dfs1(i);
ret += cnt * (cnt - 1) / 2;
}
}
return ret;
}
private:
inline void dfs0(int w) {
vis.flip(w);
for (int i = 0; i < 5; i++) {
for (UI j = g[w].v[i] & (ALL ^ vis.v[i]); j; j ^= lowbit(j)) {
int t = (__builtin_ffs(j) - 1) | (i << 5);
if (!vis[t]) {
dfs0(t);
}
}
}
que.push_back(w);
}
inline int dfs1(int w) {
vis.flip(w);
int ret = 1;
for (int i = 0; i < 5; i++) {
for (UI j = rg[w].v[i] & (ALL ^ vis.v[i]); j; j ^= lowbit(j)) {
int t = (__builtin_ffs(j) - 1) | (i << 5);
if (!vis[t]) {
ret += dfs1(t);
}
}
}
return ret;
}
}scc;

int main() {
freopen("friend.in", "r", stdin);
freopen("friend.out", "w", stdout);
for (int i = 1; i <= m; i++) {
AddEdge(U[i], V[i], PreG[i / BlockSize], PreRG[i / BlockSize]);
}
for (int i = 1; i <= q; i++) {
qy[i].blk = qy[i].l / BlockSize;
qy[i].id = i;
}
sort(qy + 1, qy + 1 + q);
Bitset CurG[N], CurRG[N];
for (int i = 1, L = 1, R = 0; i <= q; i++) {
if (qy[i].blk != qy[i - 1].blk || i == 1) {
L = qy[i].blk + 1;
R = L - 1;
for (int j = 1; j <= n; j++) {
CurG[j].reset();
CurRG[j].reset();
}
}
if (qy[i].r / BlockSize - 1 > R) {
for (int j = R + 1, lim = qy[i].r / BlockSize - 1; j <= lim; j++) {
for (int k = 1; k <= n; k++) {
for (int h = 0; h < 5; h++) {
CurG[k].v[h] ^= PreG[j][k].v[h];
CurRG[k].v[h] ^= PreRG[j][k].v[h];
}
}
}
R = qy[i].r / BlockSize - 1;
}
if (L <= R) {
for (int i = 1; i <= n; i++) {
g[i] = CurG[i];
rg[i] = CurRG[i];
}
for (int l = qy[i].l; l < L * BlockSize; l++) {
}
for (int r = (R + 1) * BlockSize; r <= qy[i].r; r++) {
}
ans[qy[i].id] = scc.solve();
} else {
for (int i = 1; i <= n; i++) {
g[i].reset();
rg[i].reset();
}
for (int j = qy[i].l; j <= qy[i].r; ++j) {
}
ans[qy[i].id] = scc.solve();
}
}
for (int i = 1; i <= q; i++) {
printf("%d\n", ans[i]);
}
return 0;
}

【BZOJ 4886】[Lydsy2017年5月月赛] 叠塔游戏

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 500009;

int n,tot,u[N],v[N],fa[N],val[N],cir[N],sz[N];
LL ans;

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

int find(int x) {
return x == fa[x]? x: fa[x] = find(fa[x]);
}

int main() {
for (int i=1;i<=n;i++) {
ans += u[i];
ans += v[i];
}
sort(val+1, val+1+tot);
tot = unique(val+1, val+1+tot) - val - 1;
for (int i=1;i<=tot;i++) {
fa[i] = i;
sz[i] = 1;
}
for (int i=1;i<=n;i++) {
int x = lower_bound(val+1, val+1+tot, u[i]) - val;
int y = lower_bound(val+1, val+1+tot, v[i]) - val;
if (find(x) != find(y)) {
sz[fa[y]] += sz[fa[x]];
if (cir[fa[x]]) {
cir[fa[y]] = 1;
}
fa[fa[x]] = fa[y];
} else {
cir[fa[x]] = 1;
}
}
for (int i=1;i<=tot;i++) {
if (find(i) == i) {
sz[i] -= (cir[i] ^ 1);
}
}
for (int i=1,w=1;i<=n;i++,w++) {
while (sz[find(w)] == 0) ++w;
ans -= val[w];
sz[fa[w]]--;
}
printf("%lld\n",ans);
return 0;
}

【BZOJ 3033】太鼓达人

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 3000;

int n,k,arr[N];
set<int> S;

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline int get(int p) {
int ret = 0;
for (int i=0;i<k;i++) ret += (1 << i) * arr[p + i];
return ret;
}

int main() {
k = read(); n = 1 << k;
for (int i=1;i<=k;i++) arr[i] = 0; S.insert(0);
for (int i=n;i>n-k;i--) arr[i] = 1, S.insert(get(i));
for (int i=2;i<=n-k;i++) {
if (S.count(get(i))) arr[i+k-1] = 1;
S.insert(get(i));
}
printf("%d ",n);
for (int i=1;i<=n;i++) printf("%d",arr[i]);
return 0;
}

【日常小测】Mortal Kombat

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 3009;
const int M = N * N << 1;
const int INF = 1e9;

int n,m,S,T,E=1,mth[N],id[N][N],num[N],ins[N]; char pat[N];
stack<int> stk;

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline int AddEdge(int u, int v, int f=0) {
if (f) {
flow[E - 1] = f; return E - 1;
}

class Network_Flow{
int dis[N],cur[N]; queue<int> que;
public:
inline int MaxFlow() {
int ret = 0;
while (BFS()) {
ret += DFS(S, INF);
} return ret;
}
private:
int DFS(int w, int f) {
if (w == T) return f; int ret = 0;
for (int &i=cur[w],tmp;i;i=nxt[i]) {
if (flow[i] && dis[to[i]] == dis[w] + 1) {
tmp = DFS(to[i], min(f, flow[i]));
flow[i] -= tmp; flow[i^1] += tmp;
f -= tmp; ret += tmp;
if (!f) return ret;
}
} return ret;
}
inline bool BFS() {
memset(dis,60,sizeof(dis));
dis[S] = 0; que.push(S);
while (!que.empty()) {
int w = que.front(); que.pop();
if (flow[i] && dis[to[i]] > INF) {
dis[to[i]] = dis[w] + 1;
que.push(to[i]);
}
}
} return dis[T] < INF;
}
}Dinic;

void Tarjan(int w) {
static int dfs_cnt = 0, scc_cnt = 0;
dfs[w] = low[w] = ++dfs_cnt; stk.push(w); ins[w] = 1;
if (!dfs[to[i]]) Tarjan(to[i]), low[w] = min(low[w], low[to[i]]);
else if (ins[to[i]]) low[w] = min(low[w], dfs[to[i]]);
}
if (low[w] == dfs[w]) {
for (scc_cnt++;!stk.empty();stk.pop()) {
num[stk.top()] = scc_cnt; ins[stk.top()] = 0;
if (stk.top() == w) {stk.pop(); break;}
}
}
}

int main() {
n = read(); m = read(); S = 0; T = N - 1;
memset(id, -1, sizeof(id));
for (int i=1;i<=n;i++) {
scanf("%s",pat+1);
for (int j=1;j<=m;j++) {
if (pat[j] == '1') {
id[i][j] = AddEdge(i, m + j, 1);
}
}
}
for (int i=1;i<=n;i++) AddEdge(S, i, 1);
for (int i=1;i<=m;i++) AddEdge(m + i, T, 1);
if (Dinic.MaxFlow() != n) {
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) putchar('1');
puts("");
}
} else {
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++)
if (~id[i][j] && !flow[id[i][j]]) {mth[j] = i; break;}
for (int i=n+1,j=1;i<=m;i++,j++) {while(mth[j])j++;mth[j]=i;}
for (int i=1;i<=m;i++) for (int j=1;j<=m;j++) if (~id[i][j] || i > n) {
for (int i=1;i<=m*2;i++) if (!dfs[i]) Tarjan(i);
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
if ((~id[i][j]) && (mth[j] == i || num[i] == num[m+j])) putchar('0');
else putchar('1');
} putchar('\n');
}
}
return 0;
}

【BZOJ 1123】[POI2008] BLO

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100000+9;
const int M = 1000000+9;

LL vout[N];
vector<int> bcc_num[N];
stack<int> stk;

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

void Tarjan(int w, int f) {
stk.push(w); sz[w] = 1; int tmp = 0;
for (int i=head[w];i;i=nxt[i]) if (to[i] != f) {
if (!num[to[i]]) {
Tarjan(to[i], w);
sz[w] += sz[to[i]];
int cur; bcc_cnt++;
do {
cur = stk.top(); stk.pop();
bcc_num[cur].push_back(bcc_cnt);
} while (cur != to[i]);
vout[w] += 2LL * tmp * sz[to[i]];
tmp += sz[to[i]];
}
} else {
}
}
vout[w] += 2LL * tmp * (n - tmp - 1) + 2 * (n - 1);
}

inline void Add_Edge(int u, int v) {
static int T = 0;
}

int main(){
for (int i=1;i<=m;i++) {
}
Tarjan(1,1);
for (int i=1;i<=n;i++) {
printf("%lld\n",vout[i]);
}
return 0;
}

【Codeforces 700C】Break Up

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdio>
#include<cmath>
#include<queue>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 1000+9;
const int M = 60000+9;
const int INF = 0x7fffffff;

int n,m,s,t,vout=INF,vis[N],tag[M],tot,sign,upd;
queue<int> que,path,ans;

inline void AddEdge(int a, int b, int w){
static int T = 1;
to[++T] = b; nxt[T] = head[a]; head[a] = T; val[T] = w;
to[++T] = a; nxt[T] = head[b]; head[b] = T; val[T] = w;
}

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
return ret*f;
}

bool DFS(int w){
if (w == t) return 1; else vis[w] = 1;
if (DFS(to[i])) {path.push(i); return 1;}
return 0;
}

int Get_Cut(int w, int f){
if (!num[w]) link[w] = num[w] = ++tot; int ret = w==t?1:0;
for (int i=head[w];i;i=nxt[i]) if (!tag[i] && (i^1) != f) {
else {
int tmp = Get_Cut(to[i],i);
if (link[to[i]] > num[w]) {if (tmp && (upd==INF || val[upd] > val[i])) upd = i;}
ret |= tmp;
}
}
return ret;
}

inline bool BFS(){
memset(vis,0,sizeof(vis));
que.push(s); vis[s] = 1;

while (!que.empty()) {
int w = que.front(); que.pop();
if (!vis[to[i]]) vis[to[i]] = 1, que.push(to[i]);
}
return vis[t];
}

inline void update(int a, int b){
if (vout > val[a] + val[b]) {
vout = val[a] + val[b];
while (!ans.empty()) ans.pop();
ans.push(a); if (b) ans.push(b);
}
}

int main(){
if (DFS(s)) {
while (!path.empty()) {
int w = path.front();
tag[w] = tag[w^1] = 1;
if (BFS()) {
memset(num,0,sizeof(num)); upd = INF;
link[s] = num[s] = tot = 1; Get_Cut(s,-1);
if (upd != INF) update(upd,w);
} else update(w,0);
tag[w] = tag[w^1] = 0; path.pop();
}
if (vout == INF) cout<<-1;
else {
cout<<vout<<endl<<ans.size()<<endl;
while (!ans.empty()) cout<<ans.front()/2<<' ', ans.pop();
}
} else cout<<0<<endl<<0;
return 0;
}

【BZOJ 2438】[中山市选2011] 杀人游戏

PS:此题的随机数据不容易拍出错QAQ

#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
using namespace std;

const int MAXN = 300000+9;

int scc_num[MAXN],scc_sz[MAXN],scc_cnt;
stack<int> sta;

inline void AddEdge(int u, int v){
static int T = 0;
}

char c=getchar(); int buf=0,f=1;
while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();}
return buf*f;
}

void DFS(int w) {
static int tot = 0; sta.push(w);
}
scc_cnt += 1;
while (true) {
int nw = sta.top(); sta.pop();
scc_num[nw] = scc_cnt;
scc_sz[scc_cnt]++;
if (nw == w) break;
}
}
}

int main(){