# 2022杭电多校（九）

2022杭电多校（九）

• 2022杭电多校（九）
• 一、比赛小结
• 二、题目分析及解法（基础题）
• 1001、Arithmetic Subsequence
• 1003、Fast Bubble Sort
• 1007、Matryoshka Doll
• 1008、Shortest Path in GCD Graph
• 1010、Sum Plus Product
• 三、题目分析及解法（进阶题）

• 1 ≤ 𝑖 < 𝑗 < 𝑘 ≤ 𝑁;

• (𝐵𝑖 , 𝐵𝑗 , 𝐵𝑘 )不构成等差序列。

``````// #pragma comment(linker, "/STACK:102400000,102400000")
#pragma GCC optimize("O3")
#pragma GCC optimize("O2")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
// #pragma GCC optimize("trapv")
#include
// #include
#define int long long
#define double long double
// #define i128 long long
// #define double long double
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define F first
#define S second

typedef long long ll;
typedef unsigned long long ull;
// typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
const int mod = 998244353;
const double EPS = 1e-9;
const double pi = acos(-1);
const int INF = 1e18;
const int N = 5007;
mt19937 rng(1235);
int n;
vi ans;
void solve(vi &x) {
vector<pair<int, int>> y;
int n = sz(x);
for (int i = 0; i < n; ++i) {
y.push_back({0, x[i]});
for (int j = 0; j < 30; ++j) {
if (x[i] >> j & 1) y[i].first |= (1ll << (29 - j));
}
}
sort(range(y));
for (int i = 0; i < n; ++i) ans.push_back(y[i].second);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout.precision(15);
int _;
cin >> _;
while (_--) {
cin >> n;
vi a(n, 0);
rep(i, n) cin >> a[i];
map<int, int> cnt;
ans.clear();
rep(i, n) {
cnt[a[i]]++;
if (cnt[a[i]] > 2) {
cout << "NO\n";
goto cont;
}
}
cout << "YES\n";
solve(a);
for (auto c : ans) cout << c << " ";
cout << "\n";
cont:;
}
return 0;
}
/*

*/
``````
1003、Fast Bubble Sort

``````// #pragma comment(linker, "/STACK:102400000,102400000")
#pragma GCC optimize("O3")
#pragma GCC optimize("O2")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
// #pragma GCC optimize("trapv")
#include
// #include
#define int long long
#define double long double
// #define i128 long long
// #define double long double
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define F first
#define S second

typedef long long ll;
typedef unsigned long long ull;
// typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

namespace internal {

// @param n `0 <= n`
// @return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
// constexpr int bsf_constexpr(unsigned int n) {
//     int x = 0;
//     while (!(n & (1 << x))) x++;
//     return x;
// }

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsf(unsigned int n) {
#ifdef _MSC_VER
unsigned long index;
_BitScanForward(&index, n);
return index;
#else
return __builtin_ctz(n);
#endif
}

}  // namespace internal

template <class S, S (*op)(S, S), S (*e)()>
struct segtree {
public:
segtree() : segtree(0) {}
segtree(int n) : segtree(std::vector<S>(n, e())) {}
segtree(const std::vector<S>& v) : _n((int)(v.size())) {
log = internal::ceil_pow2(_n);
size = 1 << log;
d = std::vector<S>(2 * size, e());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}

void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}

S get(int p) {
assert(0 <= p && p < _n);
return d[p + size];
}

S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
S sml = e(), smr = e();
l += size;
r += size;

while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}

S all_prod() { return d[1]; }

template <bool (*f)(S)>
int max_right(int l) {
return max_right(l, [](S x) { return f(x); });
}
template <class F>
int max_right(int l, F f) {
assert(0 <= l && l <= _n);
assert(f(e()));
if (l == _n) return _n;
l += size;
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!f(op(sm, d[l]))) {
while (l < size) {
l = (2 * l);
if (f(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}

template <bool (*f)(S)>
int min_left(int r) {
return min_left(r, [](S x) { return f(x); });
}
template <class F>
int min_left(int r, F f) {
assert(0 <= r && r <= _n);
assert(f(e()));
if (r == 0) return 0;
r += size;
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!f(op(d[r], sm))) {
while (r < size) {
r = (2 * r + 1);
if (f(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}

private:
int _n, size, log;
std::vector<S> d;

void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};

using S = int;
S op(S l, S r) { return l + r; }
S e() { return 0; }

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
const int mod = 998244353;
const int base[] = {12321, 32123};
const double EPS = 1e-9;
const double pi = acos(-1);
const int INF = 1e18;
const int N = 100017;
mt19937 rng(1235);

int n, q;
int p[N];
int ans[N], C[N], now[N];
vector<pii> info[N];
int st[N];

int lowbit(int u) { return u & (-u); }
void update(int u, int w) {
for (int i = u; i <= n + 7; i += lowbit(i)) C[i] += w;
}
int query(int u) {
int ans = 0;
for (int i = u; i; i -= lowbit(i)) ans += C[i];
return ans;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int _;
cin >> _;
//_=1;
while (_--) {
cin >> n >> q;
rep(i, n) cin >> p[i];
for (int i = 1; i <= n + 5; ++i) C[i] = 0, now[i] = 0;
rep(i, N) info[i].clear();
p[n] = n + 1;
rep(i, q) {
int u, v;
cin >> u >> v;
u--, v--;
info[u].pb({i, v});
}
int cnt = 0;
st[cnt++] = n;
auto upd = [&](int u) {
update(u + 1, (now[u + 1] ? -1 : 1)), now[u + 1] ^= 1;
update(u + 2, (now[u + 2] ? -1 : 1)), now[u + 2] ^= 1;
};
for (int i = n - 1; i > -1; --i) {
while (cnt && p[i] > p[st[cnt - 1]]) {
cnt--;
upd(st[cnt]);
}
st[cnt++] = i, upd(i);
for (auto c : info[i]) {
int id = c.F, r = c.S;
if (i == r)
ans[id] = 0;
else
ans[id] = (query(r + 1) - query(i)) / 2;
}
}
rep(i, q) cout << ans[i] << "\n";
}
return 0;
}
``````
1007、Matryoshka Doll

``````#include
using namespace std;
typedef long long ll;
const int M = 998244353;
int n, k, r, a[5005], dp[5005][5005];
void solve() {
memset(dp, 0, sizeof(dp));
cin >> n >> k >> r;
for (int i = 1; i <= n; i++) cin >> a[i];
int p = 0;
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
while (p + 1 < i && a[p + 1] + r <= a[i]) ++p;
int s = i - p - 1;
for (int j = s + 1; j <= i; j++)
dp[i][j] = (1ll * (j - s) * dp[i - 1][j] + dp[i - 1][j - 1]) % M;
}
cout << dp[n][k] << endl;
}
int main() {
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
int T;
cin >> T;
while (T--) solve();
}
``````
1008、Shortest Path in GCD Graph

``````#include
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn = 1e7 + 5;
typedef vector<int> vi;
int prime[maxn / 10], f[maxn], n, Q;
bool p[maxn];
void sieve(int n) {
int cnt = 0;
for (int i = 2; i <= n; i++) {
if (!p[i]) prime[++cnt] = i, f[i] = i;
for (int j = 1; j <= cnt && prime[j] * i <= n; j++) {
p[prime[j] * i] = 1;
f[prime[j] * i] = prime[j];
if (i % prime[j] == 0) break;
}
}
}
int m, ret;
set<int> S;
vi a;
void pv(int x) {
while (x > 1) {
int y = f[x];
if (S.find(y) == S.end()) S.insert(y);
while (x % y == 0) x /= y;
}
}
void dfs(int x, int s, int o) {
if (x == m) {
ret += o * (n / s);
return;
}
dfs(x + 1, s, o);
if (s <= n / a[x]) dfs(x + 1, s * a[x], -o);
}
int calc(int x, int y) {
S.clear();
pv(x);
pv(y);
a.clear();
for (auto x : S) a.pb(x);
m = a.size();
ret = 0;
dfs(0, 1, 1);
return ret;
}
int main() {
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
ios::sync_with_stdio(false);
cin >> n >> Q;
sieve(n);
while (Q--) {
int x, y;
cin >> x >> y;
assert(x != y);
if (__gcd(x, y) == 1) {
cout << 1 << ' ' << 1 << endl;
continue;
}
int ans = calc(x, y);
if (__gcd(x, y) == 2) ans++;
cout << 2 << ' ' << ans << endl;
}
return 0;
}
``````
1010、Sum Plus Product

``````#include
#define int long long
using namespace std;
const int mod = 998244353;
const int maxn = 600;
int n;
int a[maxn];
signed main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int _;
cin >> _;
while (_--) {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
int ans = 1ll;
for (int i = 1; i <= n; i++) {
ans = ans * (a[i] + 1ll) % mod;
}
ans = (ans - 1ll + mod) % mod;
cout << ans << endl;
}
return 0;
}
``````

(0)

• ## 潮汕话心焦是什么意思

心焦，就是"心里焦急,非常着急"的意思。与"心急,着急"比起来,显然"心焦"的程度要严重一些。来源：三国魏．阮籍〈咏怀诗〉八二首之三三：「终身履薄冰，谁知我心焦？」《三国演义．第六

2022-12-06
000
• ## b站的昏睡红茶是什么梗

昏睡红茶，B站这个国内知名视频弹幕网站里网友们玩的梗，野兽先辈有一部作品，是一个日本电视剧里的一个被称为野兽先辈的角色，喝了红茶之后就昏睡了，所以网友们就把昏睡红茶当做一个梗来调侃。恶臭梗之一，野兽先

2022-12-06
000
• ## 网络用语ioi是什么意思

ioi，饭圈里指I.O.I，（全称Ideal Of Idol）是由韩国YMC Entertainment于2016年5月推出的女子演唱组合，由林娜荣、金请夏、金世正、郑采妍、周洁琼、金素慧、俞琏静、磪

2022-12-06
000
• ## 网络语被某人圈粉、被圈粉是什么意思

被圈粉，表示被动方被某个人吸引了并且成为了他的粉丝。“被圈粉”出处在哪：该词最早出自于2013年的时候，最早的释义也是仅仅跟营销手段挂钩，而后慢慢在粉丝圈子中流行起来了，衍生出其新的含义。 圈粉，就是

2022-12-06
000
• ## 故宫冷宫为何不开放

故宫冷宫不开放主要有两方面的原因，一是因为常年失修，有些宫殿已经破败不堪，没有观赏价值，也不够安全，二是因为地处偏僻，空间狭小，大部分宫殿不像三大殿那样能够容纳很多的游客。其实冷宫不对外开放跟闹鬼没有

2022-12-06
000
• ## 袁世凯当了多长时间皇帝

袁世凯只当了八十三天的皇帝就被赶下了台。当初辛亥革命成功之后，袁世凯窃取了革命成功的果实，想要复辟帝制。1915年12月袁世凯登基称帝，结果次年三月份就被迫下台，前前后后当皇帝的时间只有短短的八十三

• ## 刘邦怎么死的

刘邦死因是在沙场上被流矢射中后病重而死，刘邦是汉朝的开国皇帝，他出身布衣却拥有领兵打仗之才，有勇有谋，但人终归是要经历生老病死的，所以刘邦也难逃死亡的命运安排，他在讨伐乱党时被流矢射中，然后一病不起

2022-12-06
000
• ## 北周和隋朝的关系

北周和隋朝有亲戚关系。虽然有亲属关系，不过并没有血缘关系。周明帝宇文毓的妻子与隋文帝杨坚的妻子是姐妹关系，也就是说周明帝与隋文帝是连襟关系。除了北周和隋朝是亲戚关系，两朝和唐朝也一样是亲属关系。唐高祖

2022-12-06
000
• ## 城濮之战是以少胜多吗

城濮之战是以少胜多。城濮之战中晋国以战车七百乘、五万多兵力击败楚国以及其他国家的联盟军队十余万人，是一场以少胜多的战役。此次战争在春秋历史上具有重要的意义，它遏制了楚国北进的势头，稳定了中原形势，奠定

2022-12-06
000