A Birthday
思路：设置一个源点，一个汇点，每次对$源点对a_i, b_i , a_i 对 b_i 连一条流为1，费用为0的边$
每个点都再连一条 1, 3, 5, 7, ....的边到汇点之间，因为每多加一个流的费用，然后就是最小费用最大流
#include<bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f; const int maxn = ;
const int maxm = ; struct Edge{
int to, nxt, cap, flow, cost;
}edge[maxm]; int head[maxn], tot;
int pre[maxn], dis[maxn];
bool vis[maxn];
int N; void Init(int n)
{
N = n;
tot = ;
memset(head, -, sizeof head);
} void addedge(int u, int v, int cap, int cost)
{
edge[tot].to = v;
edge[tot].cap = cap;
edge[tot].cost = cost;
edge[tot].flow = ;
edge[tot].nxt = head[u];
head[u] = tot++; edge[tot].to = u;
edge[tot].cap = ;
edge[tot].cost = -cost;
edge[tot].flow = ;
edge[tot].nxt = head[v];
head[v] = tot++;
} bool SPFA(int s, int t)
{
queue<int>q;
for(int i = ; i < N; ++i)
{
dis[i] = INF;
vis[i] = false;
pre[i] = -;
}
dis[s] = ;
vis[s] = true;
q.push(s);
while(!q.empty())
{
int u = q.front();
q.pop();
vis[u] = false;
for(int i = head[u]; ~i; i = edge[i].nxt)
{
int v = edge[i].to;
if(edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost)
{
dis[v] = dis[u] + edge[i].cost;
pre[v] = i;
if(!vis[v])
{
vis[v] = true;
q.push(v);
}
}
}
}
if(pre[t] == -) return false;
else return true;
} int solve(int s,int t)
{
int flow = ;
int cost = ;
while(SPFA(s, t))
{
int Min = INF;
for(int i = pre[t]; ~i; i = pre[edge[i ^ ].to])
{
Min = min(Min, edge[i].cap - edge[i].flow);
}
for(int i = pre[t]; ~i; i = pre[edge[i ^ ].to])
{
edge[i].flow += Min;
edge[i ^ ].flow -= Min;
cost += edge[i].cost * Min;
}
flow += Min;
}
return cost;
} int n, m; int main()
{
while(~scanf("%d %d", &n, &m))
{
Init(n + m + );
int s = , t = n + m + ;
for(int i = ; i <= n; ++i)
{
int u, v;
scanf("%d %d", &u, &v);
addedge(, i, , );
addedge(i, u + n, , );
addedge(i, v + n, , );
}
for(int i = n + ; i <= n + m; ++i)
{
for(int j = ; j < ; j += )
{
addedge(i, t, , j);
}
}
int cost = solve(, n + m + );
printf("%d\n", cost);
}
return ;
}
B Board
思路一：考虑 $a[x], b[x]$ 分别表示第x行加了多少， 第x列加了多少 那么 $arr[x][y]$ 就可以表示成 $a[x] + b[y]$ 那么 就可以通过找一个点来解，比如说找一个点$x_1, y_1$ 那么 $a[x] + b[y] = a[x] + b[y_1] + a[x_1] + b[y] - a[x_1] - b[x_1] = arr[x][y_1] + arr[x_1][y] - arr[x_1][y_1]$
#include <bits/stdc++.h>
using namespace std; #define N 1010 int n;
int arr[N][N]; int Move[][] =
{
-, -,
, ,
-, ,
, -,
}; bool ok(int x, int y)
{
if (x < || x > n || y < || y > n) return false;
return true;
} int main()
{
while (scanf("%d", &n) != EOF)
{
int x, y;
for (int i = ; i <= n; ++i)
for (int j = ; j <= n; ++j)
{
scanf("%d", &arr[i][j]);
if (arr[i][j] == -)
x = i, y = j;
}
if (n == )
printf("%d\n", arr[][] == - ? : arr[][]);
else
{
for (int i = ; i < ; ++i)
{
int nx = x + Move[i][];
int ny = y + Move[i][];
if (ok(nx, ny))
{
printf("%d\n", arr[x][ny] + arr[nx][y] - arr[nx][ny]);
break;
}
}
}
}
return ;
}
思路二：考虑分成n块，包含n行n列，那么每次对每一列加上一个数或者对每一行加上一个数，相当于对n块都加上了，也就是说，这n个块最后相加的数是相同的，然后就可以求解
#include<bits/stdc++.h> using namespace std; #define N 1010 int n;
int arr[N][N];
int sum[N];
int x, y; int main()
{
while(~scanf("%d", &n))
{
memset(sum, , sizeof sum);
for(int i = ; i <= n; ++i)
{
for(int j = ; j <= n; ++j)
{
scanf("%d", &arr[i][j]);
if(arr[i][j] != -) sum[(i + j) % n] += arr[i][j];
else x = i, y = j;
}
}
int tmp = (x + y) % n;
int ans = ;
if(tmp != )
{
ans = sum[] - sum[tmp];
}
else
{
ans = sum[] - sum[tmp];
}
printf("%d\n", ans);
}
return ;
}
C Circle
水。
#include <bits/stdc++.h>
using namespace std; int n; int main()
{
while (scanf("%d", &n) != EOF)
printf("%d\n", n);
return ;
}
D 土龙弟弟
留坑。
E Growth
思路：考虑将$x, y 分别离散 dp[x][y]$ 表示 $a_i, b_i 到达 x, y $的状态 的时候可以拿到多少奖励了
$value[x][y] 表示的是 到达x并且到达y 的奖励一共有多少$
$dp[i][j] = max(dp[i][j - 1] + value[i][j - 1] *(yy[j] - yy[j - 1]), dp[i - 1][j] + value[i - 1][j] * (xx[i] - xx[i - 1]));$
#include <bits/stdc++.h>
using namespace std; #define N 1010
#define ll long long int n, mx, my;
ll m;
int xx[N], yy[N], zz[N];
ll dp[N][N], value[N][N]; struct node
{
int x, y, z;
void scan(int i)
{
scanf("%d%d%d", &x, &y, &z);
xx[i] = x; yy[i] = y;
}
}arr[N]; void Init()
{
sort(xx + , xx + + n);
sort(yy + , yy + + n);
mx = unique(xx + , xx + + n) - xx - ;
my = unique(yy + , yy + + n) - yy - ;
memset(dp, , sizeof dp);
memset(value, , sizeof value);
for (int i = ; i <= n; ++i)
{
arr[i].x = lower_bound(xx + , xx + + mx, arr[i].x) - xx;
arr[i].y = lower_bound(yy + , yy + + my, arr[i].y) - yy;
value[arr[i].x][arr[i].y] += arr[i].z;
}
} int main()
{
while (scanf("%d%lld", &n, &m) != EOF)
{
for (int i = ; i <= n; ++i) arr[i].scan(i); Init();
for (int i = ; i <= mx; ++i)
{
for (int j = ; j <= my; ++j)
{
value[i][j] += value[i - ][j] + value[i][j - ] - value[i - ][j - ];
}
}
for (int i = ; i <= mx; ++i)
{
for (int j = ; j <= my; ++j)
{
dp[i][j] = max(dp[i][j], dp[i - ][j] + value[i - ][j] * (xx[i] - xx[i - ]));
dp[i][j] = max(dp[i][j], dp[i][j - ] + value[i][j - ] * (yy[j] - yy[j - ]));
}
}
ll ans = ;
for (int i = ; i <= mx; ++i)
{
for (int j = ; j <= my; ++j)
{
if(xx[i] + yy[j] <= m) ans = max(ans, dp[i][j] + value[i][j] * (m - xx[i] - yy[j] + ));
}
}
printf("%lld\n", ans);
}
return ;
}
F kingdom
留坑。
G Matrix
留坑。
H Mountain
水。
#include <bits/stdc++.h> using namespace std; #define N 1010 int n;
int arr[N]; int main()
{
while(~scanf("%d", &n))
{
for(int i = ; i <= n; ++i) scanf("%d", arr + i);
int ans = ;
for(int i = ; i <= n; ++i)
{
ans = max(ans, arr[i]);
}
ans = ans * ;
printf("%d\n", ans);
}
return ;
}
I 清明梦超能力者黄YY
思路：树链剖分维护u->v 路径上染色次数，倒着操作，每次找有没有第k次染色的点，有的话拿出来更新的答案，并且把那个点的然后次数置位-INF, 每个点最多拿出来一次
#include <bits/stdc++.h>
using namespace std; #define N 100010
#define INF 0x3f3f3f3f int n, m, k;
vector <int> G[N];
int ans[N]; struct QUE
{
int u, v, c;
void scan()
{
scanf("%d%d%d", &u, &v, &c);
}
}que[N]; int top[N], fa[N], deep[N], num[N], p[N], fp[N],son[N], pos; void Init()
{
memset(son, -, sizeof son);
pos = ;
fa[] = , deep[] = ;
} void DFS(int u)
{
num[u] = ;
for (auto v : G[u]) if (v != fa[u])
{
fa[v] = u; deep[v] = deep[u] + ;
DFS(v); num[u] += num[v];
if (son[u] == - || num[v] > num[son[u]])
son[u] = v;
}
} void getpos(int u, int sp)
{
top[u] = sp;
p[u] = ++pos;
fp[pos] = u;
if (son[u] == -) return;
getpos(son[u], sp);
for (auto v : G[u]) if (v != son[u] && v != fa[u])
getpos(v, v);
} struct SEG
{
struct node
{
int l, r;
int lazy, Max, pos;
node () {}
node (int _l, int _r)
{
l = _l, r = _r;
Max = ;
pos = _l;
lazy = ;
}
}a[N << ]; void pushup(int id)
{
if (a[id << ].Max > a[id << | ].Max)
{
a[id].Max = a[id << ].Max;
a[id].pos = a[id << ].pos;
}
else
{
a[id].Max = a[id << | ].Max;
a[id].pos = a[id << | ].pos;
}
} void pushdown(int id)
{
if (a[id].l >= a[id].r) return;
if (a[id].lazy)
{
int lazy = a[id].lazy; a[id].lazy = ;
a[id << ].lazy += lazy;
a[id << | ].lazy += lazy;
a[id << ].Max += lazy;
a[id << | ].Max += lazy;
}
} void build(int id, int l, int r)
{
a[id] = node(l, r);
if (l == r) return;
int mid = (l + r) >> ;
build(id << , l, mid);
build(id << | , mid + , r);
pushup(id);
} void update(int id, int l, int r, int val)
{
if (a[id].l >= l && a[id].r <= r)
{
a[id].Max += val;
a[id].lazy += val;
return;
}
pushdown(id);
int mid = (a[id].l + a[id].r) >> ;
if (l <= mid) update(id << , l, r, val);
if (r > mid) update(id << | , l, r, val);
pushup(id);
}
}segtree; void change(int u, int v, int val)
{
int fu = top[u], fv = top[v];
while (fu != fv)
{
if (deep[fu] < deep[fv])
{
swap(fu, fv);
swap(u, v);
}
int l = p[fu], r = p[u];
segtree.update(, l, r, );
while ()
{
// puts("bug");
if (segtree.a[].Max < k) break;
int pos = segtree.a[].pos;
// cout << pos << " " << segtree.a[1].Max << endl;
ans[fp[pos]] = val;
segtree.update(, pos, pos, -INF);
// cout << pos << " " << segtree.a[1].Max << endl;
}
u = fa[fu], fu = top[u];
}
if (deep[u] > deep[v]) swap(u, v);
int l = p[u], r = p[v];
// printf("%d %d\n", l, r);
segtree.update(, l, r, );
while ()
{
if (segtree.a[].Max < k) break;
int pos = segtree.a[].pos;
// cout << pos << endl;
ans[fp[pos]] = val;
// cout << segtree.a[1].pos << " " << segtree.a[1].Max << endl;
segtree.update(, pos, pos, -INF);
// cout << segtree.a[1].pos << " " << segtree.a[1].Max << endl;
// puts("...................");
}
} int main()
{
while (scanf("%d%d%d", &n, &m, &k) != EOF)
{
Init();
for (int i = , u, v; i < n; ++i)
{
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
} DFS(), getpos(, );
// for (int i = 1; i <= n; ++i) printf("%d %d %d\n", i, p[i], fp[i]);
for (int i = ; i <= m; ++i) que[i].scan();
memset(ans, , sizeof ans);
segtree.build(, , n);
for (int i = m; i >= ; --i) change(que[i].u, que[i].v, que[i].c);
for (int i = ; i <= n; ++i) printf("%d%c", ans[i], " \n"[i == n]);
}
return ;
}
J 最短路
思路一（应该不是正解）：对于环内的点，拿出来，分别跑Dijkstra, 这样的点数应该在100左右，然后每次询问的时候更新答案。但是有一点奇怪的是，用并查集找出环内的点，就不会T，标记访问直接DFS找就会T。
#include <bits/stdc++.h>
using namespace std;
using pii = pair <int, int>; #define N 101010 const int INF = 0x3f3f3f3f; template <class T>
inline bool scan_d(T &ret)
{
char c; int sgn;
if (c = getchar(), c == EOF) return ;
while (c != '-' && (c < '' || c > '')) c = getchar();
sgn = (c == '-') ? - : ;
ret = (c == '-') ? : (c - '');
while (c = getchar(), c >= '' && c <= '') ret = ret * + (c - '');
ret *= sgn;
return ;
} inline void out(int x)
{
if (x / ) out(x / );
putchar(x % + '');
} vector <int> G[N];
int vis[N], deep[N], stk[N], top; struct ST
{
int mm[N << ];
int dp[N << ][];
int rmq[N << ];
int F[N << ], P[N], cnt; void Init(int n)
{
mm[] = -;
for (int i = ; i <= n; ++i)
{
mm[i] = ((i & (i - )) == ) ? mm[i - ] + : mm[i - ];
dp[i][] = i;
}
for (int j = ; j <= mm[n]; ++j)
for (int i = ; i + ( << j) - <= n; ++i)
dp[i][j] = rmq[dp[i][j - ]] < rmq[dp[i + ( << (j - ))][j - ]] ? dp[i][j - ] : dp[i + ( << (j - ))][j - ];
} int query(int a, int b)
{
if (a > b) swap(a, b);
int k = mm[b - a + ];
return rmq[dp[a][k]] <= rmq[dp[b - ( << k) + ][k]] ? dp[a][k] : dp[b - ( << k) + ][k];
} void DFS(int u, int fa)
{
F[++cnt] = u;
rmq[cnt] = deep[u];
P[u] = cnt;
vis[u] = ;
for (auto v : G[u]) if (v != fa)
{
if (vis[v])
{
stk[++top] = v;
continue;
}
deep[v] = deep[u] + ;
DFS(v, u);
F[++cnt] = u;
rmq[cnt] = deep[u];
}
} void init(int root, int node_num)
{
cnt = ;
deep[] = ;
DFS(root, root);
Init( * node_num - );
} int query_lca(int u, int v)
{
return F[query(P[u], P[v])];
}
}st; int n, m;
int dis[][N];
queue <int> q; void Dijkstra(int it, int st)
{
for (int i = ; i <= n; ++i)
{
vis[i] = ;
dis[it][i] = INF;
}
dis[it][st] = ;
q.push(st);
while (!q.empty())
{
int u = q.front(); q.pop();
if (vis[u]) continue;
vis[u] = ;
for (auto v : G[u])
{
if (dis[it][v] > dis[it][u] + )
{
dis[it][v] = dis[it][u] + ;
q.push(v);
}
}
}
} vector <pii> tmp; int pre[N]; int find(int x)
{
if (x != pre[x])
pre[x] = find(pre[x]);
return pre[x];
} void Run()
{
while (scan_d(n), scan_d(m))
{
for (int i = ; i <= n; ++i) pre[i] = i; top = ;
for (int i = , u, v; i <= m; ++i)
{
scan_d(u), scan_d(v);
int fu = find(u), fv = find(v);
if (fu == fv)
{
tmp.emplace_back(u, v);
stk[++top] = u;
}
else
{
G[u].push_back(v);
G[v].push_back(u);
pre[fu] = fv;
}
}
st.init(, n);
sort(stk + , stk + + top);
int nn = unique(stk + , stk + + top) - stk - ;
for (auto it : tmp)
{
G[it.first].push_back(it.second);
G[it.second].push_back(it.first);
}
for (int i = ; i <= nn; ++i) Dijkstra(i, stk[i]);
int q;
scan_d(q);
while (q--)
{
int u, v;
scan_d(u), scan_d(v);
int root = st.query_lca(u, v);
int ans = deep[u] + deep[v] - * deep[root];
for (int i = ; i <= nn; ++i)
ans = min(ans, dis[i][u] + dis[i][v]);
out(ans), putchar('\n');
}
}
}
int main()
{
#ifdef LOCAL
freopen("Test.in", "r", stdin);
#endif Run();
return ;
}
K 排序
留坑。