A - Divide a Cuboid
如果一边是偶数，肯定一刀切一半最优，否则看一下切出来的差就是另外两边的乘积。
//waz
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)((x).size()))
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;
#define gi(x) ((x) = F())
#define gii(x, y) (gi(x), gi(y))
#define giii(x, y, z) (gii(x, y), gi(z))
int F()
{
char ch;
int x, a;
while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');
if (ch == '-') ch = getchar(), a = -1;
else a = 1;
x = ch - '0';
while (ch = getchar(), ch >= '0' && ch <= '9')
x = (x << 1) + (x << 3) + ch - '0';
return a * x;
}
int A, B, C;
int main()
{
giii(A, B, C);
if (A % 2 == 0 || B % 2 == 0 || C % 2 == 0) puts("0");
else printf("%lld
", min(1LL * A * B, min(1LL * B * C, 1LL * A * C)));
return 0;
}
B - Colorful Slimes
枚举转了y次，那么一个点被造出来的花费就是min(a[i-y]...a[i])，最后加上x*y对所有情况取min就好了。
//waz
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)((x).size()))
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;
#define gi(x) ((x) = F())
#define gii(x, y) (gi(x), gi(y))
#define giii(x, y, z) (gii(x, y), gi(z))
int F()
{
char ch;
int x, a;
while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');
if (ch == '-') ch = getchar(), a = -1;
else a = 1;
x = ch - '0';
while (ch = getchar(), ch >= '0' && ch <= '9')
x = (x << 1) + (x << 3) + ch - '0';
return a * x;
}
int n, a[2010], x, mn[2010][2010];
long long ans;
int main()
{
gii(n, x);
for (int i = 1; i <= n; ++i) gi(a[i]), ans += a[i];
for (int i = 1; i <= n; ++i)
{
mn[i][i] = a[i];
for (int j = i + 1; j <= n; ++j)
mn[i][j] = min(mn[i][j - 1], a[j]);
}
for (int i = 0; i <= n; ++i)
{
long long ret = 1LL * x * i;
for (int j = 1; j <= n; ++j)
{
int k = j - i;
if (k < 1) k += n, ret += min(mn[k][n], mn[1][j]);
else ret += mn[k][j];
}
ans = min(ans, ret);
}
printf("%lld
", ans);
return 0;
}
C - AND Grid
两边摆成类似正反E字交错放，重复地方两个都放就好了。
//waz
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)((x).size()))
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;
#define gi(x) ((x) = F())
#define gii(x, y) (gi(x), gi(y))
#define giii(x, y, z) (gii(x, y), gi(z))
int F()
{
char ch;
int x, a;
while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');
if (ch == '-') ch = getchar(), a = -1;
else a = 1;
x = ch - '0';
while (ch = getchar(), ch >= '0' && ch <= '9')
x = (x << 1) + (x << 3) + ch - '0';
return a * x;
}
int n, m;
char str[510][510];
int main()
{
gii(n, m);
for (int i = 1; i <= n; ++i) scanf("%s", str[i] + 1);
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
if (((j == 1 || (i & 1)) && j != m) || str[i][j] == '#')
putchar('#');
else
putchar('.');
}
putchar('
');
}
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
if (((j == m || !(i & 1)) && j != 1) || str[i][j] == '#')
putchar('#');
else
putchar('.');
}
putchar('
');
}
}
D - Teleporter
首先，1号必须连自己，因为如果1有在一个环上，环上每个点走k次结果都不一样，其它也只能改为1号最优。
那么，省下就是一棵树了，bfs一遍即可。
//waz
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)((x).size()))
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;
#define gi(x) ((x) = F())
#define gii(x, y) (gi(x), gi(y))
#define giii(x, y, z) (gii(x, y), gi(z))
int F()
{
char ch;
int x, a;
while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');
if (ch == '-') ch = getchar(), a = -1;
else a = 1;
x = ch - '0';
while (ch = getchar(), ch >= '0' && ch <= '9')
x = (x << 1) + (x << 3) + ch - '0';
return a * x;
}
const int N = 1e5 + 10;
int n, k, a[N];
int ans = 0;
int deg[N], dep[N];
int main()
{
gii(n, k); --k;
for (int i = 1; i <= n; ++i) gi(a[i]);
if (a[1] != 1) ++ans, a[1] = 1;
for (int i = 1; i <= n; ++i)
++deg[a[i]];
static int q[N]; int l = 0, r = 0;
for (int i = 1; i <= n; ++i)
{
if (!deg[i]) q[r++] = i;
}
while (l < r)
{
int u = q[l++];
--deg[a[u]];
if (!deg[a[u]]) q[r++] = a[u];
if (dep[u] == k && a[u] != 1) a[u] = 1, ++ans;
else dep[a[u]] = max(dep[a[u]], dep[u] + 1);
}
printf("%d
", ans);
return 0;
}
E - Salvage Robots
能走的区域是一个矩形，但是能取到的就长得奇形怪状了，所以我们就写一个四位dp，算算边界就好了。
//waz
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)((x).size()))
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;
#define gi(x) ((x) = F())
#define gii(x, y) (gi(x), gi(y))
#define giii(x, y, z) (gii(x, y), gi(z))
int F()
{
char ch;
int x, a;
while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');
if (ch == '-') ch = getchar(), a = -1;
else a = 1;
x = ch - '0';
while (ch = getchar(), ch >= '0' && ch <= '9')
x = (x << 1) + (x << 3) + ch - '0';
return a * x;
}
int H, W;
char str[110][110];
int cnt[110][110];
int sum(int x1, int y1, int x2, int y2)
{
x1 = max(x1, 1), x1 = min(x1, H);
x2 = max(x2, 1), x2 = min(x2, H);
y1 = max(y1, 1), y1 = min(y1, W);
y2 = max(y2, 1), y2 = min(y2, W);
if (x1 > x2) return 0;
if (y1 > y2) return 0;
//cerr << x1 << ", " << y1 << " and " << x2 << ", " << y2 << endl;
return cnt[x2][y2] + cnt[x1 - 1][y1 - 1] - cnt[x1 - 1][y2] - cnt[x2][y1 - 1];
}
int f[2][110][110][110];
int main()
{
gii(H, W);
for (int i = 1; i <= H; ++i)
scanf("%s", str[i] + 1);
int x = 0, y = 0;
for (int i = 1; i <= H; ++i)
for (int j = 1; j <= W; ++j)
if (cnt[i][j] = (str[i][j] == 'o'), str[i][j] == 'E')
x = i, y = j;
for (int i = 1; i <= H; ++i)
for (int j = 1; j <= W; ++j)
cnt[i][j] += cnt[i - 1][j] + cnt[i][j - 1] - cnt[i - 1][j - 1];
int ans = 0;
for (int l = 0; x + l <= H; ++l)
for (int r = 0; x - r > 0; ++r)
for (int u = 0; y + u <= W; ++u)
for (int d = 0; y - d > 0; ++d)
{
int L = l & 1;
f[L][r][u][d] = 0;
int left = x - r, right = x + l;
int up = y - d, down = y + u;
left = max(1 + l, left);
right = min(H - r, right);
up = max(up, 1 + u);
down = min(down, W - d);
if (l && l + r + x <= H) f[L][r][u][d] = max(f[L][r][u][d], f[L ^ 1][r][u][d] + sum(x + l, up, x + l, down));
if (r && l + r <= x - 1) f[L][r][u][d] = max(f[L][r][u][d], f[L][r - 1][u][d] + sum(x - r, up, x - r, down));
if (u && u + d + y <= W) f[L][r][u][d] = max(f[L][r][u][d], f[L][r][u - 1][d] + sum(left, y + u, right, y + u));
if (d && u + d <= y - 1) f[L][r][u][d] = max(f[L][r][u][d], f[L][r][u][d - 1] + sum(left, y - d, right, y - d));
//cerr << l << ", " << r << ", " << u << ", " << d << " : " << f[l][r][u][d] << endl;
ans = max(ans, f[L][r][u][d]);
}
printf("%d
", ans);
return 0;
}
F - Namori
我们首先可以发现一个性质，黑色只能成对出现而且，这两个点距离为奇数，次数是距离。
那么树就很好写了，只要一个启发式合并，求深度的奇偶性。
环套树我们把它缩成环，然后每个附上权值d[i]，偶环就是一个负载平衡问题，奇环我们可以断开一条边，因为那条边的作用是改变奇偶用的，所以我们扫一遍就能知道会改变多少次。
//waz
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)((x).size()))
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;
#define gi(x) ((x) = F())
#define gii(x, y) (gi(x), gi(y))
#define giii(x, y, z) (gii(x, y), gi(z))
int F()
{
char ch;
int x, a;
while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');
if (ch == '-') ch = getchar(), a = -1;
else a = 1;
x = ch - '0';
while (ch = getchar(), ch >= '0' && ch <= '9')
x = (x << 1) + (x << 3) + ch - '0';
return a * x;
}
const int N = 1e5 + 10;
VI edge[N];
int n, m;
namespace task1
{
set<int> e[N][2];
int fa[N], dep[N], check_cnt;
void dfs1(int u)
{
dep[u] = dep[fa[u]] + 1;
e[u][dep[u] & 1].insert(u);
if (dep[u] & 1) ++check_cnt;
else --check_cnt;
for (auto v : edge[u])
{
if (v == fa[u]) continue;
fa[v] = u;
dfs1(v);
}
}
long long ans;
void dfs2(int u)
{
for (auto v : edge[u])
{
if (v == fa[u]) continue;
dfs2(v);
if (e[u][1].size() < e[v][1].size())
e[u][1].swap(e[v][1]);
for (auto x : e[v][1])
e[u][1].insert(x);
if (e[u][0].size() < e[v][0].size())
e[u][0].swap(e[v][0]);
for (auto x : e[v][0])
e[u][0].insert(x);
}
if (e[u][1].size() && e[u][0].size())
{
int s = min(e[u][1].size(), e[u][0].size());
set<int>::iterator it1 = e[u][1].begin(), it2 = e[u][0].begin();
static PII stk[N]; int tp = 0;
for (int i = 1; i <= s; ++i)
{
int v1 = *it1;
int v2 = *it2;
stk[++tp] = mp(v1, v2);
ans += dep[v1] + dep[v2] - (dep[u] << 1);
//cerr << v1 << ", " << v2 << ", " << u << endl;
++it1, ++it2;
}
for (int i = 1; i <= tp; ++i)
e[u][1].erase(stk[i].fi), e[u][0].erase(stk[i].se);
}
}
void solve()
{
dfs1(1);
if (check_cnt)
{
puts("-1");
return;
}
dfs2(1);
printf("%lld
", ans);
}
}
namespace task2
{
bool vis[N], cir[N];
int use_fa[N];
vector<int> circle;
bool exit_flag;
void dfs1(int u)
{
vis[u] = 1;
for (auto v : edge[u])
{
if (exit_flag) return;
if (use_fa[u] == v) continue;
if (vis[v])
{
while (u != v) circle.pb(u), cir[u] = 1, u = use_fa[u];
circle.pb(v), cir[v] = 1;
exit_flag = 1;
return;
}
use_fa[v] = u;
dfs1(v);
}
}
int dep[N], fa[N];
set<int> e[N][2];
void dfs2(int u)
{
dep[u] = dep[fa[u]] + 1;
e[u][dep[u] & 1].insert(u);
for (auto v : edge[u])
{
if (v == fa[u]) continue;
if (cir[v]) continue;
fa[v] = u;
dfs2(v);
}
}
long long ans;
void dfs3(int u)
{
for (auto v : edge[u])
{
if (v == fa[u]) continue;
if (cir[v]) continue;
dfs3(v);
if (e[u][1].size() < e[v][1].size())
e[u][1].swap(e[v][1]);
for (auto x : e[v][1])
e[u][1].insert(x);
if (e[u][0].size() < e[v][0].size())
e[u][0].swap(e[v][0]);
for (auto x : e[v][0])
e[u][0].insert(x);
}
if (e[u][1].size() && e[u][0].size())
{
int s = min(e[u][1].size(), e[u][0].size());
set<int>::iterator it1 = e[u][1].begin(), it2 = e[u][0].begin();
static PII stk[N]; int tp = 0;
for (int i = 1; i <= s; ++i)
{
int v1 = *it1;
int v2 = *it2;
stk[++tp] = mp(v1, v2);
ans += dep[v1] + dep[v2] - (dep[u] << 1);
//cerr << v1 << ", " << v2 << ", " << u << endl;
++it1, ++it2;
}
for (int i = 1; i <= tp; ++i)
e[u][1].erase(stk[i].fi), e[u][0].erase(stk[i].se);
}
}
int d[N];
void solve()
{
dfs1(1);
for (auto root : circle)
{
//cerr << root << endl;
dfs2(root), dfs3(root);
if (e[root][1].size())
{
for (auto v : e[root][1])
++d[root], ans += dep[v] - 1;
}
else if (e[root][0].size())
{
for (auto v : e[root][0])
--d[root], ans += dep[v] - 1;
}
}
int vtx = SZ(circle);
//cerr << "ok!" << endl;
if (vtx % 2 == 0)
{
int sum = 0;
for (int i = 0; i < vtx; ++i)
{
if (i & 1) d[circle[i]] = -d[circle[i]];
sum += d[circle[i]];
}
if (sum)
{
puts("-1");
return;
}
static vector<int> t;
t.pb(-d[circle[0]]);
for (int i = 1; i < vtx; ++i)
{
d[circle[i]] += d[circle[i - 1]];
t.pb(-d[circle[i]]);
}
sort(t.begin(), t.end());
int v = t[SZ(t) >> 1];
for (auto x : t)
ans += abs(x - v);
printf("%lld
", ans);
}
else
{
int sum = 0;
for (int i = 0; i < vtx; ++i)
{
if (i & 1) d[circle[i]] = -d[circle[i]];
sum += d[circle[i]];
}
if (sum % 2 != 0)
{
puts("-1");
return;
}
ans += abs(sum / 2);
d[circle[0]] -= sum / 2;
d[circle[vtx - 1]] += sum / 2;
for (int i = 0; i < vtx - 1; ++i)
{
ans += abs(d[circle[i]]);
d[circle[i + 1]] += d[circle[i]];
}
printf("%lld
", ans);
}
}
}
int main()
{
gii(n, m);
for (int i = 1; i <= m; ++i)
{
int u, v;
gii(u, v);
edge[u].push_back(v);
edge[v].push_back(u);
}
if (m == n - 1)
{
task1::solve();
return 0;
}
task2::solve();
return 0;
}
- //waz
- #include<bits/stdc++.h>
- usingnamespace std;
- #define mp make_pair
- #define pb push_back
- #definefi first
- #define se second
- #define ALL(x)(x).begin(),(x).end()
- #define SZ(x)((int)((x).size()))
- typedef pair<int,int> PII;
- typedef vector<int> VI;
- typedeflonglong int64;
- typedefunsignedintuint;
- typedefunsignedlonglong uint64;
- #define gi(x)((x)= F())
- #define gii(x, y)(gi(x), gi(y))
- #define giii(x, y, z)(gii(x, y), gi(z))
- int F()
- {
- char ch;
- int x, a;
- while(ch = getchar(),(ch <'0'|| ch >'9')&& ch !='-');
- if(ch =='-') ch = getchar(), a =-1;
- else a =1;
- x = ch -'0';
- while(ch = getchar(), ch >='0'&& ch <='9')
- x =(x <<1)+(x <<3)+ ch -'0';
- return a * x;
- }
- constint N =1e5+10;
- int n, k, a[N];
- int ans =0;
- int deg[N], dep[N];
- int main()
- {
- gii(n, k);--k;
- for(int i =1; i <= n;++i) gi(a[i]);
- if(a[1]!=1)++ans, a[1]=1;
- for(int i =1; i <= n;++i)
- ++deg[a[i]];
- staticint q[N];int l =0, r =0;
- for(int i =1; i <= n;++i)
- {
- if(!deg[i]) q[r++]= i;
- }
- while(l < r)
- {
- int u = q[l++];
- --deg[a[u]];
- if(!deg[a[u]]) q[r++]= a[u];
- if(dep[u]== k && a[u]!=1) a[u]=1,++ans;
- else dep[a[u]]= max(dep[a[u]], dep[u]+1);
- }
- printf("%d ", ans);
- return0;
- }