vp 赛时过了 A B D，C E 没做出来，唐完了 eee
感觉自己真的可以退役了
A - Primary Task
B - Seating in a Bus
C - Numeric String Template
这题很简单，开两个 map 扫一遍就可以了，但是赛时我只开了一个，然后居然没调出来 qwq，降智
D - Right Left Wrong
很显然的贪心，最左边配对最右边，尽量每对 L，R 有重合是更优的
那么双指针，前缀和，完了。（赛时不知道为什么敲了个线段树板子，思维僵化了
code
#include <bits/stdc++.h>
#define re register int
#define lp p << 1
#define rp p << 1 | 1
#define int long long
using namespace std;
const int N = 2e5 + 10;
struct Tree
{
int l, r, sum;
}t[N << 2];
int T, n, a[N];
char c[N];
inline void build(int p, int l, int r)
{
t[p].l = l, t[p].r = r;
if (l == r)
{
t[p].sum = a[l];
return;
}
int mid = (l + r) >> 1;
build(lp, l, mid);
build(rp, mid + 1, r);
t[p].sum = t[lp].sum + t[rp].sum;
}
inline int query(int p, int l, int r)
{
if (l <= t[p].l && t[p].r <= r) return t[p].sum;
int res = 0;
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid) res += query(lp, l, r);
if (r > mid) res += query(rp, l, r);
return res;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> T;
while (T --)
{
cin >> n;
for (re i = 1; i <= n; i ++) cin >> a[i];
build(1, 1, n);
string s; cin >> s;
for (re i = 0; i < s.size(); i ++) c[i + 1] = s[i];
int i = 1, j = n, ans = 0;
while (i <= j)
{
if (c[i] != 'L') i ++;
if (c[j] != 'R') j --;
if (c[i] == 'L' && c[j] == 'R')
{
ans += query(1, i, j);
i ++, j --;
}
}
cout << ans << '\n';
}
return 0;
}
E - Photoshoot for Gorillas
首先发现，对一个有限平面用一个矩形扫一遍，越往中间重复覆盖次数越大
所以，个头高的对应放在重复次数高的位置贡献更大
那么就要在 \(O(nm)\) 的时间里，记录每个格子的覆盖次数，考虑二维差分，
然后前缀和还原，得到的覆盖数据 sort 一下就行了。
code
#include <bits/stdc++.h>
#define re register int
#define int long long
using namespace std;
const int N = 2e5 + 10;
int T, n, m, k, w, h[N];
bool cmp(int i, int j) { return i > j; }
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> T;
while (T --)
{
cin >> n >> m >> k;
cin >> w;
for (re i = 1; i <= w; i ++) cin >> h[i];
int cf[n + 10][m + 10], sum[n + 10][m + 10];
memset(cf, 0, sizeof(cf));
memset(sum, 0, sizeof(sum));
for (re i = 1; i <= n - k + 1; i ++)
for (re j = 1; j <= m - k + 1; j ++)
{
int a = i, b = j, c = min(n, i + k - 1), d = min(m, j + k - 1);
cf[a][b] ++;
cf[c + 1][d + 1] ++;
cf[a][d + 1] --;
cf[c + 1][b] --;
}
for (re i = 1; i <= n; i ++)
for (re j = 1; j <= m; j ++)
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + cf[i][j];
int val[N], cnt = 0, ans = 0;
for (re i = 1; i <= n; i ++)
for (re j = 1; j <= m; j ++) val[++ cnt] = sum[i][j];
sort(val + 1, val + cnt + 1, cmp);
sort(h + 1, h + w + 1, cmp);
for (re i = 1; i <= w; i ++) ans += h[i] * val[i];
cout << ans << '\n';
}
return 0;
}
F - Color Rows and Columns
对单个矩形，使操作数尽量少，得分尽量大，
很容易发现的贪心是，每次总是选较短的边涂满，然后得 1 分，这样操作 n + m - 1 次
但是注意，最后一次对 1 * 1 的格子操作，会导致所在行和列都被涂满，贡献为 2（因为这个没注意到，导致我手摸 case #5 一直云里雾里，然后跳了
每个矩形都可以预处理出它的所有贡献，
然后跑个 01 背包就可以了 eee，
不过是分成了多组，但是每组可以多选，还有就是因为贡献有为 2 的存在，可能数据刚好无法得到 k 得分，而是 k + 1，从 至少 k 分 也能注意到
code
#include <bits/stdc++.h>
#define re register int
using namespace std;
const int N = 1e3 + 10, K = 110, M = 210, inf = 0x3f3f3f3f;
int T, n, k;
int v[N][M], w[N][M], s[N], f[K];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> T;
while (T --)
{
cin >> n >> k;
for (re i = 1; i <= n; i ++) s[i] = 0;
for (re i = 1; i <= n; i ++)
{
int a, b; cin >> a >> b;
while (a > 1 || b > 1)
{
s[i] ++;
v[i][s[i]] = v[i][s[i] - 1] + min(a, b);
w[i][s[i]] = w[i][s[i] - 1] + 1;
if (a > b) a --;
else b --;
}
s[i] ++;
v[i][s[i]] = v[i][s[i] - 1] + 1;
w[i][s[i]] = w[i][s[i] - 1] + 2;
}
memset(f, 0x3f, sizeof(f));
f[0] = 0;
for (re i = 1; i <= n; i ++)
for (re j = k + 1; j >= 0; j --)
for (re l = 1; l <= s[i]; l ++)
if (j - w[i][l] >= 0)
f[j] = min(f[j], f[j - w[i][l]] + v[i][l]);
int ans = min(f[k], f[k + 1]);
cout << (ans == inf ? -1 : ans) << '\n';
}
return 0;
}
G - Call During the Journey
最短路，
求最迟时间，发现时间越早，越可能到达（不会更劣），时间越晚，越不可能到达（不会更优），
时间具有单调性，考虑二分这个最迟时间。
对于每个二分出来的起始时间 \(t\)，跑最短路
考虑经过当前边 u -> v（u, v, w1, w2），用 \(dist_u\) 表示走到 \(u\) 已经花的时间，\(w1,w2\) 表示当前走路和坐车的耗时，
显然，在约束下，至少到达 v 的时间有走路 \(dist_u + w1\)
而要坐车，必须保证坐车时间与打电话时间不冲突
易得，冲突条件就是 \(\max(dist_u, t_1) < min(dist_u + w2, t_2)\)，若不冲突，则坐车最优 \(dist_u + w2\)
否则，此时就有第三种方式，在 u 点打完电话再坐车走 \(t_2 + w2\)
三个值在符合约束下取 \(\min\) 即可
时间复杂度 \(O(m\log n \log t_0)\)，4s 时限可过
code
#include <bits/stdc++.h>
#define re register int
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
const int inf = 1e18;
struct Edge
{
int to, w1, w2, next;
}e[N << 1];
int idx, h[N];
int T, n, m, t0, t1, t2;
int dist[N];
bool st[N];
inline void add(int x, int y, int w1, int w2)
{
e[++ idx] = (Edge){y, w1, w2, h[x]};
h[x] = idx;
}
inline int dijkstra(int s, int t)
{
priority_queue<PII, vector<PII>, greater<PII> > q;
for (re i = 1; i <= n; i ++) dist[i] = inf, st[i] = false;
dist[s] = t;
q.push({dist[s], s});
while (!q.empty())
{
int x = q.top().second; q.pop();
if (st[x]) continue;
st[x] = true;
for (re i = h[x]; i; i = e[i].next)
{
int y = e[i].to, w1 = e[i].w1, w2 = e[i].w2;
int tmp = dist[x] + w2;
if (max(dist[x], t1) < min(dist[x] + w1, t2)) tmp = min(tmp, t2 + w1);
else tmp = min(tmp, dist[x] + w1);
if (dist[y] > tmp)
{
dist[y] = tmp;
q.push({dist[y], y});
}
}
}
return dist[n];
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> T;
while (T --)
{
cin >> n >> m >> t0 >> t1 >> t2;
for (re i = 1; i <= n; i ++) h[i] = 0;
idx = 0;
while (m --)
{
int x, y, a, b; cin >> x >> y >> a >> b;
add(x, y, a, b), add(y, x, a, b);
}
int l = -1, r = t0;
while (l < r)
{
int mid = (l + r + 1) >> 1;
if (dijkstra(1, mid) <= t0) l = mid;
else r = mid - 1;
}
cout << l << '\n';
}
return 0;
}
H - Ksyusha and the Loaded Set
一道值域线段树的板子，以后补吧
标签：966,dist,int,--,cin,Codeforces,re,tie,Div From： https://www.cnblogs.com/wenzieee/p/18496044