目录
C. Illuminate Buildings
D. Santa Claus
E. Snowflake Tree
C. Illuminate Buildings
dp[ i ][ j ]：选择的 i 个建筑，间隔为 j。这样只需要两层循环就可以了，o（n^2）
其实本质只是个一维 dp，但我还需要再加一个判定条件，那就再加一个循环，dp 多一维
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e3 + 5, INF = 1e18;int T, n, cnt, ans, a[N], dp[N][N];
string s;signed main()
{cin >> n;ans = 1;for (int i = 1; i <= n; i ++)cin >> a[i];for (int i = 1; i <= n; i ++)for (int j = 0; j < i - 1; j ++){if (a[i - j - 1] == a[i])dp[i][j] = dp[i - j - 1][j] + 1;ans = max(ans, dp[i][j] + 1);}cout << ans;return 0;
}
D. Santa Claus
首先考虑一般性思路。对于每一次操作，假设是往上移动，那我就看 y 到 y + c 的路径上有多少个房子。
但是遍历所有房子复杂度太高，实际上我只需要看在横坐标为 x 的那一列上有多少房子在 y 到 y + c 的路径上，这将大大简化计数过程。由此想到优化方案：将所有房子按横纵坐标分类，每次操作在固定行或列上计数。
set 开不了那么大，用 map < int, set < int > >，一个是同一列（x 一致），一个是同一行（y 一致）
it = mpx [ x ].erase(it)：删除当前指针，指针会自动指向下一位
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5, INF = 1e18;int T, n, m, x, y, cnt, ans;
string s;
map<int, set<int> > mpx, mpy;signed main()
{cin >> n >> m >> x >> y;for (int i = 1; i <= n; i ++){int xx, yy;cin >> xx >> yy;mpx[xx].insert(yy), mpy[yy].insert(xx);}for (int i = 1; i <= m; i ++){char opt;int c;cin >> opt >> c;if (opt == 'U'){auto it = mpx[x].lower_bound(y);y += c;while (it != mpx[x].end() && *it <= y){ans ++, mpy[*it].erase(x);it = mpx[x].erase(it); }}if (opt == 'D'){int t = y;y -= c;auto it = mpx[x].lower_bound(y);while (it != mpx[x].end() && *it <= t){ans ++, mpy[*it].erase(x);it = mpx[x].erase(it);}}if (opt == 'R'){auto it = mpy[y].lower_bound(x);x += c;while (it != mpy[y].end() && *it <= x){ans ++, mpx[*it].erase(y);it = mpy[y].erase(it);}}if (opt == 'L'){int t = x;x -= c; auto it = mpy[y].lower_bound(x);while (it != mpy[y].end() && *it <= t){ans ++, mpx[*it].erase(y);it = mpy[y].erase(it);}}}cout << x << ' ' << y << ' ' << ans;return 0;
}
E. Snowflake Tree
删掉的最少就是留下的最多
(1) 枚举每个点作为中心点
(2) 找到与这个点直接相连的点作为蓝点
1.对这些点的 ( 度数 - 1 ) 进行排序（每个蓝点可拥有的叶子节点数量）
2.枚举选择 k 个蓝点
3.cnt = max(cnt, 1 + k + k * dk)
(3) ans = n - cnt
vector默认从小到大排序，若从大到小是用 greater。 sort(b.begin(), b.end(), greater<int>());
这点和优先队列正好相反。优先队列默认是从大到小排序。若从小到大也是用 greater。
priority_queue <int, vector<int>, greater<int> > pq;
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5 + 5, INF = 1e18;int T, n, cnt, ans;
string s;
vector<int> G[N];signed main()
{cin >>n;ans = INF;for (int i = 1; i < n; i ++){int u, v;cin >> u >> v;G[u].push_back(v), G[v].push_back(u);}for (int i = 1; i <= n; i ++){cnt = 0;int num = G[i].size();vector<int> b;for (int j = 0; j < num; j ++)b.push_back(G[G[i][j]].size() - 1);sort(b.begin(), b.end(), greater<int>());for (int k = 1; k <= num; k ++)cnt = max(cnt, 1 + k + k * b[k - 1]);ans = min(ans, n - cnt);}cout << ans;return 0;
}
