E - Escape
https://codeforces.com/gym/102361/problem/E
题意
若干个机器人从矩阵第一行上方要走到矩阵最后一行下方，一个机器人对应一个出口，机器人只能直走，现在可以设置转换器让机器人转向，一个格子只能设置一个转向器，可以被多个机器人访问。
问每个机器人是否都能到达出口。\(1<=n,m<=100\)
(存在方格不能走)
题意
思考用网络流
建立两个矩阵图。
1.s->图1入口建流量为 1边
2.第一张图只建纵向边 第二张图之间流量为 1横向边
3.然后两张图对应可以转向的建一条流量为 1的边 （代表转向）
4.第一张图的出口和t建一条流量为1 的边。
(建的都是双向边)
最后跑dinic就好了。
#include<bits/stdc++.h>
#include<array>
#define ll long long
#define all(a) a.begin(),a.end()
using namespace std;
const int N = 5e5 + 5;
const int M = 1e6 + 1;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const ll mod = 998244353;
int n, m, numst, numed;
char ch[105][105];
int s, t, vtot;
int head[N], cur[N];
int dis[N], etot;
struct edge {
int v, nxt;
int f;
}e[M * 2];
//复杂度 O(n^2*m)
//存图用前向星比较方便 有边的信息
void addedge(int u, int v, int f) {
//边序号从零开始
e[etot] = { v, head[u], f }; head[u] = etot++;
e[etot] = { u, head[v], 0 }; head[v] = etot++;
}
//s到t是否还有路径
bool bfs() {
for (int i = 1; i <= vtot; i++) {
dis[i] = 0;
cur[i] = head[i];
}
queue<int>q;
q.push(s); dis[s] = 1;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = head[u]; ~i; i = e[i].nxt) {
//有剩余流量且未被访问过
if (e[i].f && !dis[e[i].v]) {
int v = e[i].v;
dis[v] = dis[u] + 1;
if (v == t) return true;
q.push(v);
}
}
}
return false;
}
//找最优路径
int dfs(int u, int m) {
if (u == t) return m;
int flow = 0;
//cur[]当前弧优化 保证增广过了不再增广
for (int i = cur[u]; ~i; cur[u] = i = e[i].nxt) {
//如果流量还有剩余 且该边方向是对的
if (e[i].f && dis[e[i].v] == dis[u] + 1) {
int f = dfs(e[i].v, min(m, e[i].f));
e[i].f -= f;
e[i ^ 1].f += f;
m -= f;
flow += f;
if (!m) break;//保证复杂度
}
}
if (!flow) dis[u] = -1;
return flow;
}
int dinic() {
int flow = 0;
while (bfs()) flow += dfs(s, INF);
return flow;
}
void init(int s_, int t_, int vtot_) {
s = s_;
t = t_;
vtot = vtot_;
for (int i = 1; i <= vtot; i++) head[i] = -1;
}
void solve() {
cin >> n >> m >> numst >> numed;
s = n * m * 2 + 1, t = n * m * 2 + 2;
init(s, t, t);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> ch[i][j];
int x;
for (int i = 1; i <= numst; i++) cin >> x, addedge(s, x, 1);
for (int i = 1; i <= numed; i++) {
cin >> x;
if(ch[n][x] != '1') addedge((n - 1) * m + x, t, 1);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (ch[i][j] == '1') continue;
int num = (i - 1) * m + j;
if (num + m <= n * m ) {
addedge(num, num + m, 1);
addedge(num + m, num, 1);
}
if (num % m) {
addedge(num + n * m, num + n * m + 1, 1);
addedge(num + n * m + 1, num + n * m, 1);
}
addedge(num, num + n * m, 1);
addedge(num + n * m, num, 1);
}
}
int ans = dinic();
ans == numst ? cout << "Yes\n" : cout << "No\n";
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int _t = 1;
cin >> _t;
while (_t--) {
solve();
}
return 0;
}
F - Forest Program
https://codeforces.com/gym/102361/problem/F
题意
给你一张图， 保证没有重环，现在要删几条边，使得整个图边变成森林，问有几种删边方案。
思路
我们可以先按点双缩点，对于一个连通块真可能有一个环，对于有环的连通块我们至少删一条边，最多就是删掉所有边,方案数为\(2^(num)\)，而没有环的连通块可以不删边少一种方案， 即\(2^(num - 1)\)。
#include<bits/stdc++.h>
#include<array>
#define ll long long
#define all(a) a.begin(),a.end()
using namespace std;
const int N = 5e5 + 5;
const int M = 1e6 + 1;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const ll mod = 998244353;
#define int ll
ll n, m, p, tot, dfn[N], low[N], nn, vc, cut[N], root, c[N];
vector<ll>edge[N], vcc[N];
stack<ll>st;
void tarjan(ll x, ll fa) {
low[x] = dfn[x] = ++tot;
st.push(x);
ll cnt = 0;
for (auto to : edge[x]) {
if (!dfn[to]) {
tarjan(to, x);
cnt++;
low[x] = min(low[x], low[to]);
if (low[to] >= dfn[x]) {
cut[x] = 1;
vc++;
//有可能x点已经被切掉了 因为一个缩点可以属于多个连通块
vcc[vc].push_back(x);
while (1) {
ll now = st.top();
st.pop();
vcc[vc].push_back(now);
if (now == to) break;
}
}
}
else if (to != fa) low[x] = min(low[x], dfn[to]);
}
if (x == root && cnt <= 1) cut[x] = 0;
//这里的割点缩点实际上是可以对多个连通块进行考虑 如果需要对孤点进行考虑我们可以加上这一个部分
if (!edge[x].size())
vcc[++vc].push_back(x);
}
ll qpow(ll base, ll pow)
{
ll res = 1;
while (pow)
{
if (pow & 1)
res = res * base % mod;
base = base * base % mod;
pow >>= 1;
}
return res;
}
void solve() {
cin >> n >> m;
for (int i = 1, u, v; i <= m; i++) {
cin >> u >> v;
edge[u].push_back(v);
edge[v].push_back(u);
}
for (int i = 1; i <= n; i++) {
if (!dfn[i]) tarjan(i, -1);
}
ll ans = 1;
for (int i = 1; i <= vc; i++) {
ll num = vcc[i].size(), cnt = 0;
for (auto x : vcc[i]) c[x] = i;
for (auto x : vcc[i]) {
for (auto to : edge[x]) {
if (c[to] == c[x]) cnt++;
}
}
cnt /= 2;
if (cnt == num)
ans = (qpow(2, num) % mod - 1 + mod) * ans % mod;
else ans = ans * (qpow(2, num - 1)) % mod;
}
cout << ans << "\n";
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int _t = 1;
//cin >> _t;
while (_t--) {
solve();
}
return 0;
}
K - MUV LUV UNLIMITED
https://codeforces.com/gym/102361/problem/K
题意
给你一棵树
两个人博弈，每个人每次至少拿一个叶子节点，谁最后不能拿了就为输。
思路
先可以考虑一条链，如果为偶链先者就输了，但如果这条链在任何一个地方多出一个点, 那么先手可以通过这个点转变局势。
如果多出长度为2 的链那么先手不会拿这条链上的点
这就相当于奇数链就可以是转变局势的点，而偶数链是不能选的，选了你就给了对手转变局势的机会。
所以我们只要判断是否有一个叶子到一个子节点的链长为奇数即可。（有则先手获胜）
#include<bits/stdc++.h>
#include<array>
#define ll long long
#define all(a) a.begin(),a.end()
using namespace std;
const int N = 1e6 + 5;
const int M = 1e6 + 1;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const ll mod = 998244353;
#define int ll
ll n, m, val[N];
vector<int>g[N];
vector<int>leave;
void dfs(int x) {
if (g[x].size() > 1) val[x] = 0;
if (!g[x].size()) leave.push_back(x);
for (auto to : g[x]) {
if (val[x] >= 0) val[to] = val[x] + 1;
dfs(to);
}
}
void solve() {
cin >> n;
for (int i = 1; i <= n; i++) {
val[i] = -1;
g[i].clear();
}
leave.clear();
for (int i = 1, x; i < n; i++) {
cin >> x;
g[x].push_back(i + 1);
}
dfs(1);
if (leave.size() == 1) {
n % 2 ? cout << "Takeru\n" : cout << "Meiya\n";
return;
}
for (auto x : leave)
if (val[x] % 2) {
cout << "Takeru\n";
return;
}
cout << "Meiya\n";
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int _t = 1;
cin >> _t;
while (_t--) {
solve();
}
return 0;
}
J - MUV LUV EXTRA
https://codeforces.com/gym/102361/problem/J
题意
给出一个循环小数（后部分布置），求可能的最大价值\(a * p - b * l\) a ,b是题目给定的，p是循环长度，l是循环节的长度。
思路
可以将小数点后面的字符串倒转，求nxt数组（第i个位置前的最大匹配前后缀）
然后枚举p，对应的p的循环节长度就是nxt[p]，max取大就好, 即\(max(a*i - b * nxt[i])\)
#include<bits/stdc++.h>
#include<array>
#define ll long long
#define all(a) a.begin(),a.end()
using namespace std;
const int N = 1e7 + 5;
const int M = 2e6 + 1;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const ll mod = 998244353;
#define int ll
ll a, b, nxt[N];
string s;
void get_nxt(string s) {
int j = 0, k = -1;
nxt[0] = -1;
while (j < s.size()) {
if (k == -1 || s[j] == s[k]) {
j++, k++;
nxt[j] = k;
}
else k = nxt[k];
}
}
void solve() {
cin >> a >> b;
cin >> s;
string ss = "";
int f = 0;
for (int i = 0; i < s.size(); i++) {
if (f) ss += s[i];
if (s[i] == '.') f = 1;
}
reverse(ss.begin(), ss.end());
get_nxt(ss);
int n = ss.size();
int ans = max(a - b, n * (a - b));
for (int i = 1; i <= ss.size(); i++) {
int p = i;
int len = p - nxt[i];
ans = max(ans, a * p - b * len);
}
cout << ans << '\n';
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int _t = 1;
//cin >> _t;
while (_t--) {
solve();
}
return 0;
}