写在前面
补题地址：https://acm.hdu.edu.cn/listproblem.php?vol=64，题号 7336~7346。
哈哈，单刷 5 题，我是只会做套路题的飞舞。
Boc'z 那个单曲太牛逼了，最喜欢的一首，但是 live 上唱的这首是真难绷。
以下按个人向难度排序。
7336
显然若 \(n\le 2\times k\) 则前后两段任意并相同，中间一段任意，答案即 \(m^{k}\times m^{n - 2\times k} = m^{n - k}\)；若 \(n = k\) 答案即 \(m^n\)，否则序列由长度为 \(n-k\) 的循环节构成，答案仍为 \(m^{n - k}\)。
注意快速幂中要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模。
//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define LL long long
const LL p = 998244353;
//=============================================================
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
LL Qpow(LL x_, LL y_) {
LL ret = 1;
x_ %= p;
for (; y_; y_ >>= 1ll) {
if (y_ & 1) ret = ret * x_ % p;
x_ = x_ * x_ % p;
}
return ret % p;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
LL n, m, k;
scanf("%lld%lld%lld", &n, &m, &k);
LL ans = 0;
if (n - 2 * k >= 0) ans = Qpow(m, k) * Qpow(m, n - 2 * k) % p;
else if (k < n) ans = Qpow(m, n - k);
else ans = Qpow(m, n);
printf("%lld\n", ans);
}
return 0;
}
/*
1
5 2 4
*/
7341
暴力即可。枚举要修改的位置再枚举包含这个位置的所有区间，考虑使这些区间变为平方数时该位置要被修改为什么值，取贡献最大的目标值即可。
写的好看就 \(O(n^3)\)。
//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
const int kN = 310;
//=============================================================
bool square[kN * kN];
int n, allcnt, a[kN], sum[kN], cnt[kN];
int ans;
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void Init() {
allcnt = 0;
}
void Solve() {
for (int i = 1; i <= n; ++ i) {
for (int j = i; j <= n; ++ j) {
if (square[sum[j] - sum[i - 1]]) ++ allcnt;
}
}
ans = allcnt;
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= 300; ++ j) cnt[j] = 0;
for (int l = 1; l <= i; ++ l) {
for (int r = i; r <= n; ++ r) {
int s = sum[r] - sum[l - 1];
int mins = s - a[i] + 1, maxs = s - a[i] + 300;
for (int j = sqrt(mins - 1) + 1; j <= sqrt(maxs); ++ j) {
cnt[j * j - (s - a[i])] ++;
}
}
}
for (int j = 1; j <= 300; ++ j) {
ans = std::max(ans, allcnt - cnt[a[i]] + cnt[j]);
}
}
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
for (int i = 1; i <= 300; ++ i) square[i * i] = true;
int T = read();
while (T --) {
Init();
n = read();
for (int i = 1; i <= n; ++ i) {
a[i] = read();
sum[i] = sum[i - 1] + a[i];
}
Solve();
printf("%d\n", ans);
}
return 0;
}
7345
每个节点出度均为 1，构成了一棵基环内向树，显然一段路径的贡献可以表示成 \(k\times x + b\) 的形式，两段路径也可以直接合并。直接无脑倍增预处理从某个节点走 \(2^k\) 步对答案的贡献即可。总时间复杂度 \(O((n + q)\log v)\) 级别。
注意询问中的 \(l\le 10^9\)，\(\log v\) 要取到 30 左右。
//
/*
By:Luckyblock
*/
#include <queue>
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define LL long long
const int kN = 1e5 + 10;
const LL p = 1e9 + 7;
//=============================================================
int n, q, k[kN], b[kN], fa0[kN];
int fa[kN][32];
LL kk[kN][32], bb[kN][32];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void Init() {
n = read(), q = read();
for (int i = 1; i <= n; ++ i) k[i] = read();
for (int i = 1; i <= n; ++ i) b[i] = read();
for (int i = 1; i <= n; ++ i) fa0[i] = read();
for (int i = 1; i <= n; ++ i) {
fa[i][0] = fa0[i];
kk[i][0] = k[fa0[i]];
bb[i][0] = b[fa0[i]];
}
for (int i = 1; i <= 32; ++ i) {
for (int u_ = 1; u_ <= n; ++ u_) {
int fa1 = fa[u_][i - 1];
fa[u_][i] = fa[fa1][i - 1];
kk[u_][i] = kk[u_][i - 1] * kk[fa1][i - 1] % p;
bb[u_][i] = (kk[fa1][i - 1] * bb[u_][i - 1] % p + bb[fa1][i - 1]) % p;
}
}
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
Init();
while (q --) {
int x = read(), l = read(), y = read();
LL ans = y, nowl = l;
for (int i = 32; i >= 0; -- i) {
LL len = (1ll << i);
if (len <= nowl) {
nowl -= len;
ans = (kk[x][i] * ans % p + bb[x][i]) % p;
x = fa[x][i];
}
}
printf("%lld\n", ans);
}
}
return 0;
}
7337
扫描线套路，比较有印象的例子是 HH 的项链。
\(p\) 是 \(1\sim n\) 的排列，那么 \(p_i + p_j \le 2\times n - 1\)，可以组成的平方数的种类仅有 \(\sqrt n\) 级别；并且保证了对于每个数，当组成某种平方数时它的另一半的位置是唯一的。
一个直观的想法是对于某个询问区间 \([l, r]\) 中的元素 \(p_i\)，考虑枚举它可以组成的平方数 \(s^2\)，如果 \(s^2 - p_i\) 位于区间 \([i + 1, r]\) 中则贡献加 1。于是考虑上面的扫描线套路，考虑降序枚举询问的左端点 \(L\)，枚举元素 \(p_L\) 可以组成的平方数的另一半 \(s^2 - p_L\) 存在的位置 \(q\)，如果存在则令位置 \(q\) 的贡献加 1；在此过程中同时按照左端点降序枚举询问，枚举到对应询问的左端点时直接查询区间和即可。
上述过程需要支持单点修改，查询区间和，用树状数组简单维护即可，总复杂度 \(O(n\sqrt n\log n + q\log n)\) 级别。因为常数太小辣，跑得相当快。
给结构体起名好麻烦呃呃呃呃，现在遇到结构体就写脑子第一个想到的单词。
//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define LL long long
const int kN = 1e5 + 10;
//=============================================================
int n, q, p[kN], pos[kN];
struct AdmireVega {
int l, r, id;
} ayabe[kN];
LL ans[kN];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
bool cmp(AdmireVega fir_, AdmireVega sec_) {
return fir_.l > sec_.l;
}
namespace BIT {
#define lowbit(x) ((x)&(-x))
const int kL = kN;
int lim;
LL f[kN];
void Init(int n_) {
lim = n_;
for (int i = 1; i <= lim; ++ i) f[i] = 0ll;
}
void Insert(int pos_, int val_) {
for (int i = pos_; i <= lim; i += lowbit(i)) {
f[i] += val_;
}
}
LL Sum(int pos_) {
LL ret = 0;
for (int i = pos_; i; i -= lowbit(i)) {
ret += f[i];
}
return ret;
}
LL Query(int l_, int r_) {
return Sum(r_) - Sum(l_ - 1);
}
#undef lowbit
}
void Solve() {
int sqrtlim = sqrt(2 * n - 1);
for (int nowl = n, nowq = 1; nowl && nowq <= q; -- nowl) {
int i = p[nowl];
for (int j = sqrt(i) + 1; j <= sqrtlim; ++ j) {
if (j * j - i < 0) continue;
if (j * j - i > n) break;
if (pos[j * j - i] > nowl) BIT::Insert(pos[j * j - i], 1);
}
while (nowq <= q && ayabe[nowq].l == nowl) {
ans[ayabe[nowq].id] = BIT::Query(nowl, ayabe[nowq].r);
++ nowq;
}
}
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
n = read();
BIT::Init(n);
for (int i = 1; i <= n; ++ i) {
p[i] = read();
pos[p[i]] = i;
}
q = read();
for (int i = 1; i <= q; ++ i) {
int l_ = read(), r_ = read();
ayabe[i] = (AdmireVega) {l_, r_, i};
}
std::sort(ayabe + 1, ayabe + q + 1, cmp);
Solve();
for (int i = 1; i <= q; ++ i) printf("%lld\n" ,ans[i]);
}
return 0;
}
7339
点分治板题，赛时去博客里贺了份板子改了改 1A 了。
在点分治统计过根节点路径时，当两条路径上的颜色数量可以互补时，可以拼接成一条有贡献的路径。设某条路径三种颜色数量分别为 \((a, b, c)\)，我们设该路径的颜色差为一个三元组 \((b - a, c - b, a - c)\)，显然颜色差与该路径完全相反的路径可以与该路径互补拼接成一条有贡献的路径。
于是开个桶记录每种颜色差的路径的数量即可，完全是板题呃呃呃呃。
算上 map 总时间复杂度为 \(O(n\log^2 n)\) 级别。
//知识点：点分治
/*
By:Luckyblock
*/
#include <map>
#include <queue>
#include <cctype>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define LL long long
#define pr std::pair
#define mp std::make_pair
#define AdmireVega pr <int, pr <int, int> >
const int kN = 1e5 + 10;
//=============================================================
int n, edgenum, head[kN], v[kN << 1], ne[kN << 1];
int root, sumsz, sz[kN], maxsz[kN];
char s[kN];
bool vis[kN];
LL ans;
AdmireVega dis[kN];
std::map <AdmireVega, int> exist;
std::vector <AdmireVega> tmp;
std::queue <AdmireVega> tag;
//=============================================================
inline int read() {
int f = 1, w = 0;
char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void Chkmax(int &fir, int sec) {
if (sec > fir) fir = sec;
}
void Chkmin(int &fir, int sec) {
if (sec < fir) fir = sec;
}
void Add(int u_, int v_) {
v[++ edgenum] = v_;
ne[edgenum] = head[u_];
head[u_] = edgenum;
}
void CalcSize(int u_, int fa_) { //求重心
sz[u_] = 1, maxsz[u_] = 0;
for (int i = head[u_]; i; i = ne[i]) {
int v_ = v[i];
if (v_ == fa_ || vis[v_]) continue;
CalcSize(v_, u_);
Chkmax(maxsz[u_], sz[v_]);
sz[u_] += sz[v_];
}
Chkmax(maxsz[u_], sumsz - sz[u_]);
if (maxsz[u_] < maxsz[root]) root = u_;
}
AdmireVega F(AdmireVega x_) {
int a_ = x_.first, b_ = x_.second.first, c_ = x_.second.second;
return mp(b_ - a_, mp(c_ - b_, a_ - c_));
}
void CalcDis(int u_, int fa_) { //求得各点到当前根的距离
tmp.push_back(dis[u_]);
int ua = dis[u_].first;
int ub = dis[u_].second.first;
int uc = dis[u_].second.second;
for (int i = head[u_]; i; i = ne[i]) {
int v_ = v[i];
if (v_ == fa_ || vis[v_]) continue;
if (s[v_] == 'a') dis[v_] = mp(ua + 1, mp(ub, uc));
if (s[v_] == 'b') dis[v_] = mp(ua, mp(ub + 1, uc));
if (s[v_] == 'c') dis[v_] = mp(ua, mp(ub, uc + 1));
CalcDis(v_, u_);
}
}
void Dfs(int u_, int fa_) {
int ua = (s[u_] == 'a');
int ub = (s[u_] == 'b');
int uc = (s[u_] == 'c');
exist[mp(0, mp(0, 0))] = 1;
tag.push(mp(0, mp(0, 0)));
vis[u_] = true; //标记已处理
for (int i = head[u_]; i; i = ne[i]) { //处理链信息
int v_ = v[i];
if (v_ == fa_ || vis[v_]) continue;
if (s[v_] == 'a') dis[v_] = mp(1, mp(0, 0));
if (s[v_] == 'b') dis[v_] = mp(0, mp(1, 0));
if (s[v_] == 'c') dis[v_] = mp(0, mp(0, 1));
CalcDis(v_, u_);
for (int j = 0, lim = tmp.size(); j < lim; ++ j) {
int a_ = tmp[j].first;
int b_ = tmp[j].second.first;
int c_ = tmp[j].second.second;
AdmireVega ayabe = F(mp(a_ + ua, mp(b_ + ub, c_ + uc)));
a_ = ayabe.first;
b_ = ayabe.second.first;
c_ = ayabe.second.second;
ans += exist[mp(-a_, mp(-b_, -c_))];
}
for (int j = 0, lim = tmp.size(); j < lim; ++ j) {
AdmireVega ayabe = F(tmp[j]);
tag.push(ayabe);
if (!exist.count(ayabe)) exist[ayabe] = 1;
else exist[ayabe] ++;
}
tmp.clear();
}
while (!tag.empty()) {
exist[tag.front()] = 0;
tag.pop();
}
for (int i = head[u_]; i; i = ne[i]) { //分治求解
int v_ = v[i];
if (v_ == fa_ || vis[v_]) continue;
sumsz = sz[v_];
root = 0, maxsz[root] = kN;
CalcSize(v_, u_), CalcSize(root, 0), Dfs(root, 0);
}
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
n = read();
scanf("%s", s + 1);
for (int i = 1; i < n; ++ i) {
int u_ = read(), v_ = read();
Add(u_, v_), Add(v_, u_);
}
sumsz = n;
root = 0, maxsz[root] = kN;
CalcSize(1, 0), CalcSize(root, 0), Dfs(root, 0);
printf("%lld\n", ans);
return 0;
}
7338
判断四个三维向量是否线性相关。
纯现代题，绷不住了我草，手写了分数运算类模拟初等行变换怎么就是过不去啊我草，我疯了，咕咕。
我先在这里放一拖四。
//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define LL long long
//=============================================================
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
struct AdmireVega {
LL up, down;
} a[5][5], ans[5];
LL gcd(LL x_, LL y_) {
return y_ ? gcd(y_, x_ % y_) : x_;
}
LL lcm(LL x_, LL y_) {
return x_ / gcd(x_, y_) * y_;
}
bool Equal1(AdmireVega fir_) {
return fir_.up == 1 && fir_.down == 1;
}
bool Zero(AdmireVega fir_) {
return fir_.up == 0;
}
bool Negative(AdmireVega fir_) {
return fir_.up < 0;
}
AdmireVega Abs(AdmireVega fir_) {
return (AdmireVega) {abs(fir_.up), fir_.down};
}
bool Cmp(AdmireVega fir_, AdmireVega sec_) {
LL down = lcm(fir_.down, sec_.down);
LL up1 = down / fir_.down * fir_.up, up2 = down / sec_.down * sec_.up;
return up1 > up2;
}
AdmireVega Plus(AdmireVega fir_, AdmireVega sec_) {
LL down = lcm(fir_.down, sec_.down);
LL up1 = down / fir_.down * fir_.up, up2 = down / sec_.down * sec_.up;
LL up = up1 + up2;
if (up == 0) down = 1ll;
LL d = gcd(abs(up), abs(down));
if (down < 0 && up > 0) up = -up, down = -down;
if (down < 0 && up < 0) up = -up, down = -down;
return (AdmireVega) {up / d, down / d};
}
AdmireVega Minus(AdmireVega fir_, AdmireVega sec_) {
LL down = lcm(fir_.down, sec_.down);
LL up1 = down / fir_.down * fir_.up, up2 = down / sec_.down * sec_.up;
LL up = up1 - up2;
if (up == 0) down = 1ll;
LL d = gcd(abs(up), abs(down));
if (down < 0 && up > 0) up = -up, down = -down;
if (down < 0 && up < 0) up = -up, down = -down;
return (AdmireVega) {up / d, down / d};
}
AdmireVega Prod(AdmireVega fir_, AdmireVega sec_) {
LL up = fir_.up * sec_.up;
LL down = fir_.down * sec_.down;
if (up == 0) down = 1ll;
LL d = gcd(abs(up), abs(down));
if (down < 0 && up > 0) up = -up, down = -down;
if (down < 0 && up < 0) up = -up, down = -down;
return (AdmireVega) {up / d, down / d};
}
AdmireVega Div(AdmireVega fir_, AdmireVega sec_) {
LL up = fir_.up * sec_.down;
LL down = fir_.down * sec_.up;
if (up == 0) down = 1ll;
LL d = gcd(abs(up), abs(down));
if (down < 0 && up > 0) up = -up, down = -down;
if (down < 0 && up < 0) up = -up, down = -down;
return (AdmireVega) {up / d, down / d};
}
bool Solve() {
int r1 = 0, r2 = 0;
int pos1[5] = {0};
for (int i = 1, k = 1; i <= 3 && k <= 3; ++ i, ++ k) { //每次将第 i 行第 k 个元素消为 1。
int pos = i; //每次找到最大系数消除，减小误差
for (int j = i + 1; j <= 3; ++ j) {
if (Cmp(Abs(a[j][k]), Abs(a[pos][k]))) {
pos = j;
}
}
if (Zero(a[pos][k])) { //系数为 0，跳
-- i;
continue;
}
pos1[++ r1] = k;
for (int j = 1; j <= 4; ++ j) { //交换到第 i 行
std::swap(a[pos][j], a[i][j]);
}
AdmireVega tmp = a[i][k]; //将第 i 行第 k 个消成 1，同时处理该行其他系数
for (int j = k; j <= 4; ++ j) {
a[i][j] = Div(a[i][j], tmp);
}
for (int j = i + 1; j <= 3; ++ j) { //枚举其他行
tmp = a[j][k]; //该行对应系数
for (int l = k; l <= 4; ++ l) {
a[j][l] = Minus(a[j][l], Prod(a[i][l], tmp));
// a[j][k] -= a[i][k] * tmp; //注意第 i 行的系数均已被处理过
}
}
}
r2 = r1;
for (int i = r1 + 1; i <= 3; ++ i) {
if (!Zero(a[i][4])) ++ r2;
}
if (r2 > r1) return 0;
ans[r1] = a[r1][4];
for (int i = r1 - 1; i >= 1; -- i) {
ans[i] = a[i][4];
for (int j = i + 1; j <= r1; ++ j) { //回带
ans[i] = Minus(ans[i], Prod(a[i][pos1[j]], ans[j]));
// ans[i] -= a[i][j] * ans[j];
}
}
for (int i = 1; i <= r1; ++ i) {
if (Negative(ans[i])) return 0;
}
return 1;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
for (int i = 1; i <= 4; ++ i) {
for (int j = 1; j <= 3; ++ j) {
LL x = read();
a[j][i] = (AdmireVega) {x, 1ll};
}
}
printf("%s\n", Solve() ? "YES" : "NO");
}
return 0;
}
/*
1
1 0 0 1 0 0 1 0 0 3 0 0
1
0 0 0 0 0 0 0 1 0 0 2 1
1
1 0 0 2 0 0 0 1 0 1 1 0
1
1 0 1 1 0 1 1 0 1 1 0 2
1
1 0 0 1 0 0 1 1 0 0 1 0
1
1 0 0 0 0 0 0 0 1 1 0 2
1
1 0 0 1 0 1 1 1 0 2 1 1
*/
写在最后
学到了什么：
- 快速幂中要对底数取模。
- 看数据范围确定倍增的上限。