Kanon 40pts
签到题，但是不会，所以打了暴力；
正解时考虑相邻两个雪球，只有两种情况：它们的覆盖区间有交集或无交集，那么如果我们找出了无交集的最后一天，我们就很容易判断剩下的一堆雪该被谁拿走，于是我们二分找出这一天即可；赛时确实想不到二分
时间复杂度：$ \Theta(n \log n) $；
点击查看代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n, q;
long long a[500005];
long long w[500005];
long long sum[500005];
long long an[500005];
long long ma[500005], mi[500005];
namespace BIT{
long long tr[2][5000005];
inline int lowbit(int x) {
return x & (-x);
}
void add(int pos, long long d) {
for (int i = pos; i <= q; i += lowbit(i)) {
tr[0][i] = max(tr[0][i], d);
tr[1][i] = min(tr[1][i], d);
}
}
long long ask(int s, int pos) {
if (s == 0) {
long long ans = -0x3f3f3f3f3f3f3f3f;
for (int i = pos; i; i -= lowbit(i)) {
ans = max(ans, tr[0][i]);
}
return ans;
} else {
long long ans = 0x3f3f3f3f3f3f3f3f;
for (int i = pos; i; i -= lowbit(i)) {
ans = min(ans, tr[1][i]);
}
return ans;
}
}
}
using namespace BIT;
bool ck(int x, long long s) {
long long mma = ma[x];
long long mmi = mi[x];
if (mmi > 0) return mma <= s;
else return mma - mmi <= s;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= q; i++) {
cin >> w[i];
}
for (int i = 1; i <= n; i++) {
tr[0][i] = -0x3f3f3f3f3f3f3f3f;
tr[1][i] = 0x3f3f3f3f3f3f3f3f;
}
long long mma = 0;
long long mmi = 0;
for (int i = 1; i <= q; i++) {
sum[i] = sum[i - 1] + w[i];
mma = max(mma, sum[i]);
mmi = min(mmi, sum[i]);
add(i, sum[i]);
ma[i] = max(0ll, ask(0, i));
mi[i] = min(0ll, ask(1, i));
}
an[1] += (-mmi);
an[n] += mma;
for (int i = 1; i <= n - 1; i++) {
int l = 1;
int r = q;
int ans = 0;
while(l <= r) {
int mid = (l + r) >> 1;
if (ck(mid, a[i + 1] - a[i])) {
l = mid + 1;
ans = mid;
} else {
r = mid - 1;
}
}
mma = ma[ans];
mmi = mi[ans];
ans++;
an[i + 1] += (-mmi);
an[i] += mma;
if (ans > q) continue;
if (w[ans] < 0) {
an[i + 1] -= (-mmi);
an[i + 1] += (a[i + 1] - a[i] - mma);
} else {
an[i] -= mma;
an[i] += (a[i + 1] - a[i] + mmi);
}
}
for (int i = 1; i <= n; i++) {
cout << an[i] << '\n';
}
return 0;
}
黎明与萤火 0pts
签到题爆零。。。
赛时打的是正解，但没有判掉已经确定的答案导致错误；
考虑从下往上找（因为从上往下可能会使原来根节点和数个子节点都是偶数，结果删了根节点后数个子节点都是奇数导致不能再选，而从下往上可以反过来甚至避免这个问题，总的来说就是尽量选一个点，使其影响的点较少），那么我们可以采用类似拓扑排序的思路，开一个优先队列，重载运算符使其将深度大的且是偶数的点放在上面，每次取出队头是判断一下现在的奇偶以及被计算进答案的情况，然后将其符合条件且未被计算进答案的点放进去，完事以后判断一下即可；
时间复杂度：每个点至多会进队其度数次（这也是正确性的保证），但是总的遍历次数是度数次的，乘上优先队列的复杂度，那么总的时间复杂度为 $ \Theta(n \log n) $；
点击查看代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int n;
vector<int> v[500005];
vector<int> ans;
int d[500005], dep[500005], dd[500005];
bool vis[500005];
struct sss{
int x;
bool operator <(const sss &A) const {
return dep[x] < dep[A.x];
}
bool operator >(const sss &A) const {
return dep[x] < dep[A.x];
}
};
priority_queue<sss> q;
void dfs(int x, int fa) {
dep[x] = dep[fa] + 1;
for (int i = 0; i < v[x].size(); i++) {
int u = v[x][i];
if (u == fa) continue;
dfs(u, x);
}
}
bool solve() {
while(!q.empty()) {
while(!q.empty() && (d[q.top().x] % 2 != 0 || vis[q.top().x])) q.pop();
if (q.empty()) break;
sss tt = q.top();
q.pop();
int t = tt.x;
vis[t] = true;
d[t] = 0;
ans.push_back(t);
for (int i = 0; i < v[t].size(); i++) {
int u = v[t][i];
if (vis[u]) continue;
d[u]--;
if (d[u] % 2 == 0) {
q.push(sss{u});
}
}
}
for (int i = 1; i <= n; i++) {
if (!vis[i]) return false;
}
return true;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
int x;
for (int i = 1; i <= n; i++) {
cin >> x;
if (x == 0) continue;
v[i].push_back(x);
v[x].push_back(i);
d[x]++;
d[i]++;
}
dfs(1, 0);
for (int i = 1; i <= n; i++) {
if (d[i] % 2 == 0) {
q.push(sss{i});
}
}
if (solve()) {
cout << "YES" << '\n';
for (int i = 0; i < ans.size(); i++) {
cout << ans[i] << '\n';
}
} else {
cout << "NO";
}
return 0;
}
Darling Dance 10pts
赛时没看这道题，输出了个0就走了，拿了10pts
这个题把最短路DAG建出来就行，然后从1开始对其BFS（DFS也行），选k条边即可；
对于最短路DAG，只需在最短路成功更新时记录一下从哪里更新的即可（即其前驱节点）；
注意k=0的情况；
点击查看代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
int n, m, k;
struct sss{
int t, ne, w;
}e[2000005];
int h[2000005], cnt;
void add(int u, int v, int ww) {
e[++cnt].t = v;
e[cnt].ne = h[u];
h[u] = cnt;
e[cnt].w = ww;
}
int dis[500005];
bool vis[500005];
int fr[500005], id[500005];
vector<int> v[500005];
int w(int x, int y) {
if (x % y == 0) return x / y;
else return x / y + 1;
}
void dij(int x) {
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
dis[x] = 0;
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
q.push({0, x});
while(!q.empty()) {
int xu = q.top().second;
q.pop();
if (vis[xu]) continue;
vis[xu] = true;
for (int i = h[xu]; i; i = e[i].ne) {
int u = e[i].t;
if (dis[u] > dis[xu] + e[i].w) {
dis[u] = dis[xu] + e[i].w;
fr[u] = xu;
id[u] = w(i, 2);
q.push({dis[u], u});
}
}
}
}
queue<int> p;
int ans[500005], o;
void bfs() {
p.push(1);
while(!p.empty()) {
int t = p.front();
p.pop();
for (int i = 0; i < v[t].size(); i++) {
int u = v[t][i];
if (o == k) return;
p.push(u);
ans[++o] = id[u];
}
}
}
int main() {
cin >> n >> m >> k;
int x, y, w;
for (int i = 1; i <= m; i++) {
cin >> x >> y >> w;
add(x, y, w);
add(y, x, w);
}
dij(1);
for (int i = 1; i <= n; i++) {
v[fr[i]].push_back(i);
}
bfs();
cout << o << '\n';
for (int i = 1; i <= o; i++) {
cout << ans[i] << ' ';
}
return 0;
}
最近比赛打的真是越来越CD了。。。