T1
传送门
肯定是准备用传送门的时候才会开。于是打出一个传送门之后肯定是找最近的能走到的墙然后在这面墙上打一个传送门穿过去。因此每一步的决策就是四向移动或者以 当前格到最近的墙的距离 的代价走到四个方向上最近的墙之一。直接最短路即可。
代码
#include <iostream>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
vector<pair<int, int> > G[1000005];
void add(int u, int v, int ww) { G[u].emplace_back(v, ww); }
int n, m;
string str[1005];
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };
queue<pair<int, int> > q;
int vis[1005][1005], nr[1005][1005];
int to[1005][1005][4];
int id[1005][1005], idcnt;
struct node {
int x, dis;
};
bool dvis[1000005];
int dist[1000005];
bool operator<(node a, node b) { return a.dis > b.dis; }
priority_queue<node> qq;
int sx, sy, tx, ty;
void dijkstra() {
memset(dist, 63, sizeof dist);
qq.push((node) { id[sx][sy], dist[id[sx][sy]] = 0 });
while (!qq.empty()) {
node tmp = qq.top();
qq.pop();
int x = tmp.x;
if (dvis[x])
continue;
dvis[x] = 1;
for (auto i : G[x]) {
int v = i.first, w = i.second;
if (dist[v] > dist[x] + w)
qq.push((node) { v, dist[v] = dist[x] + w });
}
}
}
int main() {
freopen("portals.in", "r", stdin);
freopen("portals.out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> str[i], str[i] = ' ' + str[i];
for (int i = 1; i <= n; i++) q.push(make_pair(i, 0)), q.push(make_pair(i, m + 1)), vis[i][0] = vis[i][m + 1] = 1;
for (int i = 1; i <= m; i++) q.push(make_pair(0, i)), q.push(make_pair(n + 1, i)), vis[0][i] = vis[n + 1][i] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
id[i][j] = ++idcnt;
if (str[i][j] == '#')
q.push(make_pair(i, j)), vis[i][j] = 1;
if (str[i][j] == 'S')
sx = i, sy = j;
if (str[i][j] == 'C')
tx = i, ty = j;
}
}
while (!q.empty()) {
pair<int, int> p = q.front();
q.pop();
int x = p.first, y = p.second;
for (int i = 0; i < 4; i++) {
if (x + dx[i] > 0 && y + dy[i] > 0 && x + dx[i] <= n && y + dy[i] <= m && !vis[x + dx[i]][y + dy[i]]) {
nr[x + dx[i]][y + dy[i]] = nr[x][y] + 1;
q.push(make_pair(x + dx[i], y + dy[i])), vis[x + dx[i]][y + dy[i]] = 1;
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
str[i][j] == '#' ? (to[i][j][0] = 0) : (to[i][j][0] = to[i - 1][j][0] + 1);
str[i][j] == '#' ? (to[i][j][3] = 0) : (to[i][j][3] = to[i][j - 1][3] + 1);
}
}
for (int i = n; i; i--) {
for (int j = m; j; j--) {
str[i][j] == '#' ? (to[i][j][1] = 0) : (to[i][j][1] = to[i][j + 1][1] + 1);
str[i][j] == '#' ? (to[i][j][2] = 0) : (to[i][j][2] = to[i + 1][j][2] + 1);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (str[i][j] == '#')
continue;
if (i != 1 && str[i - 1][j] != '#') {
add(id[i][j], id[i - 1][j], 1);
add(id[i][j], id[i - to[i][j][0] + 1][j], nr[i][j]);
}
if (j != 1 && str[i][j - 1] != '#') {
add(id[i][j], id[i][j - 1], 1);
add(id[i][j], id[i][j - to[i][j][3] + 1], nr[i][j]);
}
if (i != n && str[i + 1][j] != '#') {
add(id[i][j], id[i + 1][j], 1);
add(id[i][j], id[i + to[i][j][2] - 1][j], nr[i][j]);
}
if (j != m && str[i][j + 1] != '#') {
add(id[i][j], id[i][j + 1], 1);
add(id[i][j], id[i][j + to[i][j][1] - 1], nr[i][j]);
}
}
}
dijkstra();
if (dist[id[tx][ty]] >= 100000000)
cout << "-1\n";
else
cout << dist[id[tx][ty]] << "\n";
return 0;
}
T2
硬币游戏
题目给的限制非常奇怪。考察一堆棋子能凑出的价值：\(a_i, a_i + b_i, 2a_i + b_i\)。容易发现这三个东西恰好可以用 \(a_i, a_i + b_i\) 两个东西凑出来，因此就把一堆棋子拆成两种，而且两种是独立的。因此再枚举一共选几个棋子的时候，决策就只有 新选一个 \(a_i\) 和 踢掉已选的最小的 \(a_i\)，换上未选的最大的 \(a_i + b_i\) 两种。容易发现踢掉 \(a_i + b_i\) 再换上别的什么东西的决策是很蠢的，因此不必考虑。这样就可以通过开三个 set 分别维护已选和未选的 \(a_i\) 和未选的 \(a_i + b_i\) 然后模拟。但是带 \(\log\) 要 TLE，于是发现未选的 \(a_i + b_i\) 的最大值单减，可以开桶维护；而对剩下两个东西的操作总是形如 把 \(A\) 的最大值移到 \(B\) 或者 把 \(B\) 的最小值移到 \(A\)。因此这两个东西都可以开栈维护。这样就是线性了。
代码
#include <iostream>
#define int long long
using namespace std;
const int inf = 0x7fffffffffffffff;
int threshold=10000000, n, k;
int a[5000005], b[5000005];
unsigned long long k1,k2;
unsigned long long xorShift128Plus() {
unsigned long long k3=k1,k4=k2;
k1=k4;
k3^=k3<<23;
k2=k3^k4^(k3>>17)^(k4>>26);
return k2+k4;
}
void gen() {
scanf("%lld%lld%llu%llu",&n,&k,&k1,&k2);
for(int i=1;i<=n;i++) {
a[i]=xorShift128Plus()%threshold+1;
b[i]=xorShift128Plus()%threshold+1;
}
}
int buc[20000005], b1[10000005];
int stk1[5000005];
int stk2[5000005];
int sz1, sz2;
int ans, cur;
int p = 20000000;
signed main() {
freopen("coin.in", "r", stdin);
freopen("coin.out", "w", stdout);
gen();
for (int i = 1; i <= n; i++) ++buc[b[i] += a[i]], ++b1[a[i]];
for (int i = 1; i <= 10000000; i++) while (b1[i]--) stk1[++sz1] = i;
while (p && !buc[p]) --p;
for (int i = 1; i <= k; i++) {
int v1 = (!sz1 ? -inf : stk1[sz1]);
int v2 = (!p || !sz2 ? -inf : (p - stk2[sz2]));
if (v1 > v2)
cur += v1, stk2[++sz2] = stk1[sz1--];
else {
cur += v2, stk1[++sz1] = stk2[sz2--];
--buc[p]; while (p && !buc[p]) --p;
}
ans ^= cur;
}
cout << ans << "\n";
return 0;
}
T3
序列计数
注意到本质不同子序列计数的其中一种 dp：\(f_{i, j}\) 表示只考虑前 \(i\) 个字符，以字符 \(j\) 结尾的本质不同子序列数量。这个 dp 非常容易用矩阵刻画，只需要一个 \(\Sigma \times \Sigma\) 的矩阵。而这个矩阵的逆也是好求的。然后直接前缀和可以做到 \(n \times \Sigma^3\)。注意到转移矩阵及其逆都是稀疏的，因此预处理前缀和就只用 \(n \times \Sigma^2\)。查询时向量乘矩阵，总复杂度 \(\mathcal{O}((n + q)\Sigma^2)\)。
代码
#include <iostream>
#include <string.h>
#include <time.h>
#include <vector>
// #define int long long
using namespace std;
const long long P = 1000000007;
static char buf[1000005], *p1 = buf, *p2 = buf;
inline char nnc() { return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000005, stdin), p1 == p2) ? EOF : *p1++; }
// #define nnc getchar
inline int read() {
int ret = 0, neg = 0;
char c = 0;
while (c < '0' || c > '9') c = nnc(), c == '-' ? (neg = 1) : 0;
while ('0' <= c && c <= '9') ret = ret * 10 + c - 48, c = nnc();
return ret * (neg ? -1 : 1);
}
string str;
int n, q;
struct Matrix {
int a[11][11];
Matrix() { memset(a, 0, sizeof a); }
void ini(int x = 1) { for (int i = 0; i <= 10; i++) a[i][i] = x; }
int* operator[](int x) { return a[x]; }
} Pr, IP;
struct Vector {
int a[11];
Vector() { memset(a, 0, sizeof a); }
int& operator[](int x) { return a[x]; }
} F[500005];
Vector operator*(Vector a, Matrix b) {
Vector c;
long long tmp;
for (int j = 0; j <= 10; j++) {
for (int k = tmp = 0; k <= 10; k++)
tmp += 1ll * a[k] * b[k][j] % P;
c[j] = tmp % P;
}
return c;
}
vector<int> ql[500005], qr[500005];
long long s[11];
signed main() {
int ttt = clock();
freopen("count.in", "r", stdin);
freopen("count.out", "w", stdout);
cin >> str;
q = read();
n = str.size();
str = ' ' + str;
for (int i = 1, l, r; i <= q; i++) {
l = read(), r = read();
ql[l - 1].emplace_back(i);
qr[r].emplace_back(i);
for (int x = 0; x < 10; x++) F[i][x] = 1;
}
Pr.ini(), IP.ini();
for (int _ = 1; _ <= n; _++) {
int x = str[_] - 'a';
for (int i = 0; i <= 10; i++) {
for (int j = 0; j <= 10; j++) {
if (j != x)
Pr[i][j] = (Pr[i][j] + Pr[i][x]) % P;
}
}
memset(s, 0, sizeof s);
for (int i = 0; i <= 10; i++) {
for (int j = 0; j <= 10; j++)
s[j] -= IP[i][j];
}
for (int i = 0; i <= 10; i++) s[i] = (s[i] % P + P) % P;
for (int i = 0; i <= 10; i++) {
for (int j = 0; j <= 10; j++) {
if (x == i)
IP[i][j] = (s[j] + IP[i][j] * 2) % P;
}
}
for (auto v : ql[_]) F[v] = F[v] * IP;
for (auto v : qr[_]) F[v] = F[v] * Pr;
}
for (int i = 1; i <= q; i++) cout << F[i][10] << "\n";
cerr << (1.0 * clock() - ttt) / CLOCKS_PER_SEC << "\n";
return 0;
}
T4
优惠购物
神秘贪心题。首先转化为要用掉尽可能多的优惠券。大体思路是将对于每个物品使用的优惠券分成三类。第一类是前 \(a_i \bmod c\) 张，这些优惠券的使用不会影响总共能使用的优惠券的数量，因此一定先把这些用掉。接下来是每 \(c\) 张捆绑起来一块用，每用一组会让后面的优惠券数量减少 \(1\)。由于用的位置越靠后影响的位置越少，我们考虑从后往前使用这一类。使用时，前面剩余的优惠券 和 当前位置的优惠券的限量 和 后面任意时刻剩余的优惠券不能为负 这三个要求分别对当前位置使用的组数提出限制。每次使用就顶满这三个中最小的限制即可。接下来是剩下的不到 \(c\) 张优惠券，这些优惠券不管用多少，只要用了就会给后面的优惠券数量减少 \(1\)。根据贪心的原则，我们每次操作能用的优惠券最多的位置。然后就是一些观察性质和数据结构优化了。
代码
#include <iostream>
#include <algorithm>
#include <queue>
#define int long long
using namespace std;
const int inf = 0x7fffffffffffff;
int n, m, c, ans;
int a[1000005], b[1000005], x[1000005];
int s[1000005];
struct Segment_Tree {
int mn[4000005], tg[4000005];
inline void tag(int o, int v) { mn[o] += v, tg[o] += v; }
inline void pushdown(int o) {
if (!tg[o])
return;
tag(o << 1, tg[o]);
tag(o << 1 | 1, tg[o]);
tg[o] = 0;
}
void Build(int o, int l, int r) {
tg[o] = mn[o] = 0;
if (l == r) {
mn[o] = s[l - 1] - x[r];
return;
}
int mid = (l + r) >> 1;
Build(o << 1, l, mid);
Build(o << 1 | 1, mid + 1, r);
mn[o] = min(mn[o << 1], mn[o << 1 | 1]);
}
void Minus(int o, int l, int r, int L, int R, int v) {
if (L <= l && r <= R)
return tag(o, -v);
pushdown(o);
int mid = (l + r) >> 1;
if (L <= mid)
Minus(o << 1, l, mid, L, R, v);
if (R > mid)
Minus(o << 1 | 1, mid + 1, r, L, R, v);
mn[o] = min(mn[o << 1], mn[o << 1 | 1]);
}
int Query(int o, int l, int r, int L, int R) {
if (L <= l && r <= R)
return mn[o];
pushdown(o);
int mid = (l + r) >> 1;
if (R <= mid)
return Query(o << 1, l, mid, L, R);
if (L > mid)
return Query(o << 1 | 1, mid + 1, r, L, R);
return min(Query(o << 1, l, mid, L, R), Query(o << 1 | 1, mid + 1, r, L, R));
}
} seg;
pair<int, int> p[1000005];
priority_queue<int> q;
signed main() {
int tc;
cin >> tc;
while (tc--) {
ans = 0;
cin >> n >> m >> c;
for (int i = 1; i <= n + 1; i++) a[i] = b[i] = x[i] = 0;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> b[i];
s[0] = m;
for (int i = 1; i <= n; i++) {
x[i] = min(b[i], min(s[i - 1], a[i] % c));
s[i] = s[i - 1] + (a[i] - x[i]) / c - x[i];
}
for (int i = n + 1, mn = inf; i; i--) {
int t = min((b[i] - x[i]) / c, min((s[i - 1] - x[i]) / c, mn));
x[i] += t * c;
mn = min(mn - t, (s[i - 1] - x[i]) / (c + 1));
}
for (int i = 1; i <= n + 1; i++) s[i] = s[i - 1] + (a[i] - x[i]) / c - x[i];
seg.Build(1, 1, n + 1);
for (int i = 1; i <= n; i++) p[i] = make_pair(min(c - 1, b[i] - x[i]), i);
sort(p + 1, p + n + 1, greater<pair<int, int> >());
while (q.size()) q.pop();
for (int i = 1; i <= n;) {
int j = i;
while (j <= n && p[i].first == p[j].first) q.push(p[j++].second);
while (q.size()) {
int t = q.top();
int v = min(min(c - 1, b[t] - x[t]), min(seg.Query(1, 1, n + 1, t, t), seg.Query(1, 1, n + 1, t + 1, n + 1) - 1));
if (v > p[j].first) {
q.pop();
x[t] += v;
seg.Minus(1, 1, n + 1, t, t, v);
seg.Minus(1, 1, n + 1, t + 1, n + 1, v + 1);
} else
break;
}
i = j;
}
for (int i = 1; i <= n; i++) ans += a[i] - x[i];
cout << ans << "\n";
}
return 0;
}
稀疏矩阵乘法：枚举稀疏矩阵的每个有值位置，枚举另一个矩阵的对应行 / 列，向目标位置贡献。复杂度 \(\mathcal{O}( n\times 稀疏矩阵元素个数)\)。
标签：优惠券,int,1000005,long,20241112,1005,include From： https://www.cnblogs.com/forgotmyhandle/p/18550315