E - Efficient Exchange
题意：
现在需要向银行支付\(X\)元钱，但是你和银行，但现在只有\(10\)的幂次方面值的硬币，问你给银行和银行找你的硬币数总和最少是多少？
思路：
定义\(f(i,0/1)\)为当前为是否多交1位，支付到当前位置的硬币的给和找回来的最小总和比赛期间一直没想到合适的贪心策略，也没想\(dp\)
View Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
char s[N];
int dp[N][2];
int main() {
cin >> s + 1;
int len = strlen(s + 1);
dp[0][0] = 0;
dp[0][1] = 1;
for (int i = 1; i <= len; i++) {
dp[i][0] = min({dp[i - 1][0] + s[i] - '0', dp[i - 1][1] + 10 - (s[i] - '0')});
dp[i][1] = min( {dp[i - 1][0] + s[i] - '0' + 1, dp[i - 1][1] + 9 - (s[i] - '0')});
}
cout << dp[len][0] << endl;
}
G - Gluttonous Goop
题意：
给定一张图，这些图上的病毒会每秒向八个方向扩散\(1\)格，问\(k\)秒有多少个格子被病毒占领了
思路：
扩散完后，占领的图形就是正方形，就是求\(n\)个正方形的面积并，注意方格和面积的转换
把方格与方格之间的间隔，看成整数的坐标线 ，这样求出来的面积也就是方格数了
正方形数量少，用不上线段树+扫描线
模板题 方形的面积并，扫描线比赛期间知道是模板题，但wa了后，不会改坐标，麻木中，菜！
View Code
#include <bits/stdc++.h>
using namespace std;
const int N = 50;
#define int long long
const int inf = 1e12;
struct node {
int x1, y1;
int x2, y2;
};
int n, m, s;
char g[N][N];
typedef pair<int, int> PII;
vector<PII> a;
vector<node> b;
int cal(int L, int R) {
vector<PII> c;
for (auto it : b) {
if (it.x1 <= L && it.x2 >= R) {
c.push_back({it.y1, it.y2});
}
}
sort(c.begin(), c.end());
vector<PII> ans;
int l = -inf, r = -inf;
for (auto i : c) {
if (r < i.first) {
if (l != -inf) {
ans.push_back({l, r});
}
l = i.first, r = i.second;
} else {
r = max(r, i.second);
}
}
if (l != -inf) ans.push_back({l, r});
int Y = 0;
for (auto i : ans) {
Y += (i.second - i.first);
}
return (R - L) * Y;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> s;
for (int i = 1; i <= n; i++) {
cin >> g[i] + 1;
for (int j = 1; j <= m; j++) {
if (g[i][j] == '#') {
a.push_back({i - s, j - s});
a.push_back({i + s + 1, j + s + 1});
b.push_back({i - s, j - s, i + s + 1, j + s + 1});
}
}
}
vector<int> q;
sort(a.begin(), a.end());
for (auto i : a) {
q.push_back(i.first);
}
sort(q.begin(), q.end());
q.erase(unique(q.begin(), q.end()), q.end());
int len = q.size();
int res = 0;
bool f = 0;
for (int i = 0; i + 1 < len; i++) {
if (q[i] != q[i + 1]) {
res += cal(q[i], q[i + 1]);
}
}
cout << res << endl;
}
A- Appeal to the Audience
题意：
给定一个\(n\)个结点的树，现在让你给\(k\)个叶子节点赋值，非叶子结点的值为儿子节点的最大值，问赋值后，除了根节点外的其他节点的总和最大是多少？
思路：
直接贪心，先把每个结点的高度搜出来，根据高度来分组，枚举高度，由于是取最大值，所以直接每个组取前\(num\)大的数的总和，最后累加即可
没做出来，无话可说，比赛期间卡题，没换题
View Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
#define int long long
typedef pair<int, int> PII;
int depth[N];
int n, k;
int a[N];
vector<int> e[N];
int pre[N];
int all[N];
int maxv;
bool cmp(PII a, PII b) { return a.first > b.first; }
void dfs(int u, int fa) {
if(e[u].size()==0) {
all[0]++;
depth[u]=0;
return ;
}
for(auto it : e[u]) {
dfs(it,u);
depth[u]=max(depth[it]+1,depth[u]);
}
maxv=max(maxv,depth[u]);
all[depth[u]]++;
}
signed main() {
cin >> n >> k;
for (int i = 1; i <= k; i++) {
cin >> a[i];
}
for (int i = 1; i <= n - 1; i++) {
int x;
cin >> x;
e[x].push_back(i);
}
dfs(0, -1);
sort(a+1,a+k+1,greater<int>());
for(int i=1;i<=k;i++) {
pre[i]=pre[i-1]+a[i];
}
int res=0;
for(int i=0;i<maxv;i++) {
res+=pre[all[i]];
}
cout<<res<<endl;
}
Inquiry II 暂时不会，找时间补