题面
给定一个包含N个节点N-1条边的有向图，对该图做q次询问：
- “1 u v” 表示从u到v添加一条边
- “2 x” 打印从x可达的最小节点编号
($n \le 2e5, q \le 2e5$)
题解
不是，我不会啊
题意
给定长为N的数组$A=(A_1, A_2, …, A_N)$，数组中的每个元素均为[0:M]的整数，进行如下操作：
- 1. 将所有$A_i==0$的元素随机替换为某个均匀分布X~U(1, M)中的整数元素
- 2. 将数组A按升序排序
求$A_k$对998244353取模的期望。
($1\le K \le N \le 2e3, 1 \le M \le 2e3, 0 \le A_i \le M$)
题解
不会
G - Distance Queries on a Tree
涉及知识点
树链剖分，最近公共祖先
题意
给定N个点的无根带权树，给定N-1条边的信息为$u_i \leftrightarrow v_i$，权值为w_i，现在做Q次询问：
1 i w: 表示把第i条边的权重改为w2 u v: 询问从节点u到v的距离
($n \le 2e5, w_i, w \le 1e9, q \le 2e5$)
题解
我不会啊，我只会不修改的，麻了，等着看题解 [已更新]
应该时刻牢记，
$$dist(u, v) = dist(u, root) + dist(v, root) - 2dist(lca(u, v), root)$$
这里$lca(u, v)$表示u和v的最近公共祖先
其次这是一道树链剖分接近模板的题，首先处理一下所有边u->v，把权值记在深度更大的那个节点上。然后对这颗原始的无根带权树做树链剖分，可以在$O(log^2n)$的时间内询问任意两点之间的距离（把所有节点到树根的距离都变成了O(logn)段时间戳连续的区间，而求区间和又是O(logn)的时间复杂度，通过树状数组或者线段树这种可以维护区间和性质的数据结构）。
再看给定的两个操作，第一个操作就是单点修改（树链剖分路径修改的特殊情况），第二个操作利用上面给的公式即可。所以本题就是一个彻头彻尾的树剖板子题，然而我好久没写完全忘了这件事。总时间复杂度$O(nlog^2n+qlog^2n)$，代码如下。
/**
* @file template.cpp
* @author Emanual20(Emanual20@foxmail.com)
* @brief For Codeforces, Atcoder or some other OJs else
* @version 0.1
* @date 2023-3-22
*
* @copyright Copyright (c) 2022
*
*/
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int maxn = 2e5 + 10;
const int inf = 0x3f3f3f3f;
const ll MOD = 1e9 + 7;
int n, root, q;
vector<int> edges[maxn];
struct item{
int nto, nw, nidx;
};
vector<item> ne[maxn];
int idx2dnode[maxn];
#define lson(x) ((x) << 1)
#define rson(x) ((x) << 1 | 1)
#define father(x) ((x) >> 1)
struct seg_node{
int left, right;
ll sum, lazy;
};
struct HeavyLightNode{
int fath, heavyson, top;
int sz, depth;
int w, seq;
} a[maxn];
struct HeavyLightDecomposition{
public:
int Timestamp, ts2orindex[maxn];
seg_node tree[4 * maxn];
public:
void init(){
Timestamp = 0, memset(ts2orindex, 0, sizeof(ts2orindex));
}
void dfs1(int now, int fm, int depth){
a[now].fath = fm, a[now].depth = depth, a[now].sz = 1;
for(auto &it : edges[now]){
if(it != fm){
dfs1(it, now, depth + 1);
a[now].sz += a[it].sz;
if(a[it].sz > a[a[now].heavyson].sz)
a[now].heavyson = it;
}
}
}
void dfs2(int now, int fm, int tp){
Timestamp += 1, a[now].seq = Timestamp, ts2orindex[Timestamp] = now, a[now].top = tp;
// if node now haven't any heavy sons, return
if(!a[now].heavyson) return;
dfs2(a[now].heavyson, now, tp);
for(auto &it : edges[now]){
if(it != fm && it != a[now].heavyson){
// light node is the first node of any chain
dfs2(it, now, it);
}
}
}
void Pushup(int k){
tree[k].sum = tree[lson(k)].sum + tree[rson(k)].sum;
}
void build_seg(int left, int right, int k = 1){
tree[k].left = left, tree[k].right = right;
if (left == right){
tree[k].sum = a[ts2orindex[left]].w;
return;
}
int mid = (left + right) >> 1;
build_seg(left, mid, lson(k));
build_seg(mid + 1, right, rson(k));
Pushup(k);
}
void Pushdown(int k){
if (tree[k].lazy == 0) return;
tree[lson(k)].lazy += tree[k].lazy, tree[rson(k)].lazy += tree[k].lazy;
tree[lson(k)].lazy %= MOD, tree[rson(k)].lazy %= MOD;
tree[lson(k)].sum += tree[k].lazy * (tree[lson(k)].right - tree[lson(k)].left + 1);
tree[lson(k)].sum %= MOD;
tree[rson(k)].sum += tree[k].lazy * (tree[rson(k)].right - tree[rson(k)].left + 1);
tree[rson(k)].sum %= MOD;
tree[k].lazy = 0;
}
void Update_seg(int l, int r, int x, int y, ll C, int k = 1){
if (x <= l && r <= y){
tree[k].sum = C, tree[k].sum %= MOD;
return;
}
Pushdown(k);
int mid = (l + r) >> 1;
if(x <= mid) Update_seg(l, mid, x, y, C, lson(k));
if(y > mid) Update_seg(mid + 1, r, x, y, C, rson(k));
Pushup(k);
}
ll Query_seg(int l, int r, int x, int y, int k = 1){
ll ret = 0;
if (x <= l && r <= y){
ret = tree[k].sum;
return ret;
}
Pushdown(k);
int mid = (l + r) >> 1;
if (mid >= x) ret += Query_seg(l, mid, x, y, lson(k));
if (mid < y) ret += Query_seg(mid + 1, r, x, y, rson(k));
return ret;
}
void UpdateSubtree(int u, ll k){
Update_seg(1, n, a[u].seq, a[u].seq + a[u].sz - 1, k);
}
ll QuerySubtree(int u){
return Query_seg(1, n, a[u].seq, a[u].seq + a[u].sz - 1);
}
void UpdatePath(int u, int v, ll k){
while(a[u].top != a[v].top){
if(a[a[u].top].depth < a[a[v].top].depth)
swap(u, v);
Update_seg(1, n, a[a[u].top].seq, a[u].seq, k);
u = a[u].top;
u = a[u].fath;
}
if(a[u].depth < a[v].depth)
swap(u, v);
Update_seg(1, n, a[v].seq, a[u].seq, k);
}
ll QueryPath(int u, int v){
ll ret = 0;
while(a[u].top != a[v].top){
if(a[a[u].top].depth < a[a[v].top].depth)
swap(u, v);
ret += Query_seg(1, n, a[a[u].top].seq, a[u].seq);
u = a[u].top;
u = a[u].fath;
}
if(a[u].depth < a[v].depth)
swap(u, v);
ret += Query_seg(1, n, a[v].seq, a[u].seq);
return ret;
}
ll QueryLCA(int u, int v){
while(a[u].top != a[v].top){
if(a[a[u].top].depth < a[a[v].top].depth)
swap(u, v);
u = a[a[u].top].fath;
}
return a[u].depth < a[v].depth ? u : v;
}
};
void dfs_init(int now, int fm){
for(auto &it : ne[now]){
auto nto = it.nto, nw = it.nw, nidx = it.nidx;
if(nto != fm){
a[nto].w = nw, idx2dnode[nidx] = nto;
dfs_init(nto, now);
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i < n; i++){
int nfm, nto, nw;
cin >> nfm >> nto >> nw;
edges[nfm].push_back(nto), edges[nto].push_back(nfm);
ne[nfm].push_back({nto, nw, i}), ne[nto].push_back({nfm, nw, i});
}
root = 1;
dfs_init(1, -1);
HeavyLightDecomposition hld;
hld.init();
hld.dfs1(root, -1, 1);
hld.dfs2(root, -1, root);
hld.build_seg(1, n);
cin >> q;
while(q--){
int op;
cin >> op;
if(op == 1){
int nidx, nw;
cin >> nidx >> nw;
hld.UpdatePath(idx2dnode[nidx], idx2dnode[nidx], nw);
}
else if(op == 2){
int nu, nv;
cin >> nu >> nv;
auto res = hld.QueryPath(root, nu) + hld.QueryPath(root, nv) - 2 * hld.QueryPath(root, hld.QueryLCA(nu, nv));
cout << res << "\n";
}
}
return 0;
}
Sugar Water 2
涉及知识点
二分答案
题意
给定两组糖水，A组糖水有N瓶，B组糖水有M瓶。A组的每瓶糖水有$A_i$克糖，$B_i$克水；同理B组的每瓶有$C_i$克糖，$D_i$克水。从两组中各挑选出一瓶糖水混合出一瓶新的糖水的组合方式共有MN种，且组合后的糖水浓度为$\frac{a_i + c_j}{a_i + b_i + c_j + d_j}$，问这MN种方式中第k浓的糖水浓度是多少(误差不小于1e-9)？
($n, m \le 5e4, 1 \le K \le N*M, 1 \le a_i, b_i, c_i, d_i \le 1e5$)
题解
不会啊，看上去是个分治，咋做捏，等着补题了
实际上是二分答案，对于每次二分的check(mid)，就是要检验能配成这种浓度的组合方式是不是大于k种。这个子问题看上去必须要遍历所有组合方式，但实际上它和leetcode第一题的两数之和思想是完全一样的，可以优化到$O(nlogn)$，即我们固定某一维a[i]，看a[i]这杯糖水距离配成mid浓度还需要额外添加（多余）的糖的数目，用这个去二分搜索另一维。因此总时间复杂度是$O(nlognlogp)$，p表示精度要求所需要搜索的数据范围。代码如下：
/**
* @file template.cpp
* @author Emanual20(Emanual20@foxmail.com)
* @brief For Codeforces, Atcoder or some other OJs else
* @version 0.1
* @date 2023-3-19
*
* @copyright Copyright (c) 2022
*
*/
#pragma GCC optimize(2)
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int maxn = 2e5 + 10;
const int inf = 0x3f3f3f3f;
const long double eps = 1e-12;
int n, m;
ll k;
struct item{
int s, w;
};
vector<item> va, vb;
bool check(long double ck){
long double portion = ck / (1 - ck);
ll tot = 0;
vector<long double> v;
for (int i = 0; i < m; i++){
long double res = vb[i].s - vb[i].w * portion;
v.push_back(res);
}
sort(v.begin(), v.end());
for (int i = 0; i < n; i++){
long double res = va[i].s - va[i].w * portion;
tot += v.end() - lower_bound(v.begin(), v.end(), -res);
}
// cout << ck << " " << tot << endl;
return tot >= k;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m >> k;
va = vector<item>(n, {0, 0}), vb = vector<item>(m, {0, 0});
for (int i = 0; i < n; i++){
cin >> va[i].s >> va[i].w;
}
for (int i = 0; i < m; i++){
cin >> vb[i].s >> vb[i].w;
}
long double l = 0, r = 1;
while(abs(l - r) > eps){
long double mid = (l + r) / 2;
if(check(mid)){
l = mid;
}
else
r = mid;
}
cout << fixed << setprecision(10) << l * 100 << endl;
return 0;
}
这次没有难题，难度大概是1个平时的t1和3个t3，但是我居然wa了7次，整不会了真。Profile Here。
Question D Minimum Time to Repair Cars
题意
给定一个长为n的数组ranks，表示n个修理工的能力，一个能力为r的修理工可以在$k^2*r$的时间内修理k辆汽车。所有修理工同时开始修理共p辆汽车，问最短多长时间可以完成？
($n\le 1e5, ranks[i]\le 100, p \le 1e6$)
题解
这个是典型的二分答案题目，只要当我们很难直接求解答案，但是我们的数据范围能够付出logp(p为答案的解空间大小)的时间代价将其转换为多项式时间内检验某个答案是否满足条件的问题(P问题)的时候，我们可以考虑用这种方式检验问题。转换后，我们每次检验二分的答案能否满足即可。
代码如下
typedef long long ll;
class Solution {
public:
vector<int> rk;
int goal;
bool check(ll rt){
ll tot = 0;
for(int i = 0; i < rk.size(); i++){
tot += floor(sqrt(rt * 1.0 / rk[i]));
}
return tot >= goal;
}
long long repairCars(vector<int>& ranks, int cars) {
rk = ranks, goal = cars;
ll l = 1, r = 1e14;
while(l < r){
ll mid = (l + r) >> 1;
if(check(mid)){
r = mid;
}
else{
l = mid + 1;
}
}
return l;
}
};
Question C Find Score of an Array After Marking All Elements
题意
给定一个含有n个正整数的数组nums。
从 score = 0 开始, 模拟下列过程:
- 在nums数组中选择一个最小的未被标记的元素nums[i]，如果有相同的元素，选择最小的那个下标。
- score += nums[i]
- 标记选中的元素和其相邻的元素nums[i-1]和nums[i+1]
- 重复上述操作直至所有元素被标记
求上述过程结束之后score的值。
($n \le 1e5, a[i] \le 1e6$)
题解
我们肯定需要一种比较高效的维护方式来找到未被标记的最小元素，且相同元素还能找到最小的那个下标。如果纯暴力的话，即每次通过遍历一次数组的方式找到这个元素，实际上复杂度要$O(n^2)$，肯定是不能接受的。
考虑对每个key维护一个set，这个set即包括所有未被标记的元素大小为key的下标集合。这个map[HTML_REMOVED]> mp的数据结构就维护了所有没有被标记的元素下标，且这个数据结构可以帮助找到最小的未标记元素。每次标记元素的时候，只需要将这个需要标记的元素从mp中移除出去即可。
思路很简单，但是我tle了一次的原因是什么呢set<int>& itv = it->second;这里忘记加引用号了，如果没有引用号就相当于会重新进行一次值拷贝，导致复杂度就爆炸了！正确代码如下：
typedef long long ll;
class Solution {
public:
long long findScore(vector<int>& nums) {
ll ret = 0;
int n = nums.size();
vector<int> flag(n, 1);
map<int, set<int>> mp;
for(int i = 0; i < n; i++){
mp[nums[i]].insert(i);
}
while(mp.size() > 0){
auto it = mp.begin();
int itk = it->first;
set<int>& itv = it->second;
auto itvf = itv.begin();
ret += itk;
int lidx = (*itvf) - 1, idx = (*itvf), ridx = (*itvf) + 1;
if(lidx >= 0 && lidx < n && flag[lidx]){
flag[lidx] = 0, mp[nums[lidx]].erase(lidx);
if(mp[nums[lidx]].size() == 0) mp.erase(nums[lidx]);
}
if(ridx >= 0 && ridx < n && flag[ridx]){
flag[ridx] = 0, mp[nums[ridx]].erase(ridx);
if(mp[nums[ridx]].size() == 0) mp.erase(nums[ridx]);
}
flag[idx] = 0, mp[nums[idx]].erase(idx);
if(mp[nums[idx]].size() == 0) mp.erase(nums[idx]);
}
return ret;
}
};
Question B Maximize Greatness of an Array
题意
给定一个长为n的数组a[1:n]，可以对这个数组a进行任意重排为一个新的等长数组perm，求最多能有多少个位置满足perm[i]>a[i]？
($n\le 1e5, a[i] \le 1e9$)
题解
贪心，首先对a从小到大排序。
然后从小到大看一下数组a中，有哪个最小且还没有被放入perm中的元素比a[i]大。
class Solution {
public:
int maximizeGreatness(vector<int>& a) {
int n = a.size();
sort(a.begin(), a.end());
int ret = 0, idy = 0;
for(int i = 0; i < n && idy < n; i++){
while(idy < n){
if(a[idy] <= a[i])
idy++;
else{
ret++, idy++;
break;
}
}
}
return ret;
}
};
Question A Distribute Money to Maximum Children
题意
不想翻译了，直接贴过来了…
You are given an integer money denoting the amount of money (in dollars) that you have and another integer children denoting the number of children that you must distribute the money to.
You have to distribute the money according to the following rules:
All money must be distributed.
Everyone must receive at least 1 dollar.
Nobody receives 4 dollars.
Return the maximum number of children who may receive exactly 8 dollars if you distribute the money according to the aforementioned rules. If there is no way to distribute the money, return -1.
题解
理解题意就可以。不知道为什么要设计这么多规则约束，是为了避免gpt4自动代码生成过题吗，wa了很多次。
class Solution {
public:
int distMoney(int money, int children) {
if(money < children || (money == 4 && children == 1)) return -1;
if(money == children * 8) return children;
if(money > children * 8) return children - 1;
money -= children;
return (money / 7) - (money % 7 == 3 && children - money / 7 == 1 ? 1 : 0);
}
};
题面
给定A, X, M, 求$S=\sum_{i=0}^{X-1}A^i (mod M)$
($1\le A, M \le 1e9, 1\le X \le 1e12$)
题解
很容易用浅薄的小学二年级知识想到，这是个等比数列，所以我们推个公式！$$S=\frac{A^x-1}{A-1}$$，矩阵快速幂，求个逆元！这不就完事了！这也能算是个E题？
坏了！A-1和M不一定互质，逆元不一定存在（费马小定理$a^{p-1} \equiv 1(\bmod p)$要求(a, p) = 1，即a和p互质；即使用拓展欧几里得也必须要求逆元存在），这可咋办！
实际上，我们设$a_n = \sum_{i=0}^{n-1}A^i $, 那么$a_n = A a_{n - 1} + 1$！这是一个典型的矩阵快速幂，就可以避免求不一定存在的逆元了！代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<ll>> mat_mul(vector<vector<ll>> a, vector<vector<ll>> b, ll mod) {
int n = a.size();
vector<vector<ll>> res(n, vector<ll>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
res[i][j] += a[i][k] * b[k][j];
res[i][j] %= mod;
}
}
}
return res;
}
vector<vector<ll>> mat_pow(vector<vector<ll>> a, ll b, ll mod) {
int n = a.size();
vector<vector<ll>> res(n, vector<ll>(n));
for (int i = 0; i < n; i++) res[i][i] = 1;
while (b) {
if (b & 1) res = mat_mul(res, a, mod);
a = mat_mul(a, a, mod);
b >>= 1;
}
return res;
}
int main() {
ll a, x, m;
cin >> a >> x >> m;
vector<vector<ll>> f = { {a,1},{0,1} };
vector<vector<ll>> g = mat_pow(f, x, m);
cout << g[0][1] << endl;
return 0;
}
倒着讲。Profile Here。
Question D Count Number of Possible Root Nodes
题意
给定一个n个节点的无根树，Bob同学对这个无根树的父子关系进行m次猜测，每次猜测u为v的父亲(注意不是祖先)，由于这个树是没有根的，并不能确定每个节点之间的父子关系。求这n个节点分别当无根树的根的这些情况中，Bob同学猜测正确次数超过k次的情况有多少？
($n\le 1e5, m\le 1e5, k \le m$)
题解
首先我们需要会判断以一个固定节点为根时候，在$O(n+m)$的时间复杂度内完成对Bob所有猜测对当前固定根是否满足的求解过程。这个过程如果你想到了一些LCA的事情（倍增、Tarjan），这说明你和我一样没认真读题，导致把题目想的非常复杂！题意里也强调了，只是猜测是不是父亲，不是祖先关系！父子关系就简单多了！你可以在一次dfs遍历的过程中完成这个过程，因为有父子关系的两个点一定是相邻的，正好就是我们dfs遍历的过程。
但是如果这样枚举n次，时间复杂度是$O(nm+n^2)$，这个时间范围是不对的。由于父子关系是节点的邻居关系，我们应该比较自然能想到换根dp：即，我们考虑如果存在u<->v的一条边，我们已知刚才以u为根节点时候猜测正确的条数，现在想求以v为根节点时正确的条数，这两个之间一定存在很紧密的关系，思考这两者之间的差异。发现u转移到v的时候，只会改变u和v两个节点之间的父子关系，其他的完全不影响！
所以我们只需要看看猜测列表里如果：
- 存在(u, v)，就-1，因为即将变成错的；
- 存在(v, u)，就+1，因为即将变成对的。
代码如下
const int maxn = 1e5 + 10;
class Solution {
public:
int n;
vector<int> edges[maxn];
set<pair<int, int>> st;
int res = 0;
map<int, int> mp_ans;
void dfs1(int now, int fm){
res += st.count({fm, now}) > 0;
for(auto &nto : edges[now]){
if(nto != fm){
dfs1(nto, now);
}
}
}
void dfs2(int now, int fm){
if(mp_ans.find(now) == mp_ans.end())
mp_ans[now] = res;
for(auto &nto : edges[now]){
if(nto != fm){
res += st.count({nto, now}) > 0, res -= st.count({now, nto}) > 0;
dfs2(nto, now);
res -= st.count({nto, now}) > 0, res += st.count({now, nto}) > 0;
}
}
}
int rootCount(vector<vector<int>>& e, vector<vector<int>>& g, int k) {
n = e.size() + 1;
for(auto &it : e)
edges[it[0]].push_back(it[1]), edges[it[1]].push_back(it[0]);
for(auto &it : g)
st.insert({it[0], it[1]});
int root = 0; res = 0;
dfs1(root, -1);
dfs2(root, -1);
int ret = 0;
for(int i = 0; i < n; i++){
// cout << i << " :" << mp_ans[i] << endl;
ret += mp_ans[i] >= k;
}
return ret;
}
};
Question C Count Ways to Group Overlapping Ranges
题意
给定一个长为n(n<1e5)的数组ranges，每个元素(start_i, end_i)表示一个区间的开始和结束，你需要将这个ranges数组分成两部分，保证：
- 每个range元素属于唯一的部分
- 任意两个重叠的区间属于相同的部分
注意两个区间只要有一个整数同时属于这两个区间就称为重叠。问有多少种分割ranges数组的方式，方案数模(1e9+7)。
题解
可以不难感觉到是把区间先分成组内不冲突的组，再把组随意放到两个部分中的过程。具体一点，就是区间组内部元素有相交关系，而区间组之间两两互不相交（两个区间组不相交就定义为这个区间组内的所有小区间都不相交）。而有了这样的区间组，每个区间组就可以没有任何限制的放到两个部分中，因此假定区间组总量为tot，方案数就是$2^tot$。
下面就是求解区间组的过程。先把所有区间按照左端点排序，然后从左到右线性扫一次所有区间就行了。
typedef long long ll;
const ll MOD = 1e9 + 7;
struct line{
int x, y;
};
bool comp(line l1, line l2){
if(l1.x != l2.x) return l1.x < l2.x;
else return l1.y > l2.y;
}
class Solution {
public:
int countWays(vector<vector<int>>& ranges) {
int n = ranges.size();
ll ret = 1;
vector<line> v;
for(auto &it : ranges) v.push_back({it[0], it[1]});
sort(v.begin(), v.end(), comp);
ll tot = 0, res = -1;
for(int i = 0; i < n; i++){
ll nx = v[i].x, ny = v[i].y;
if(nx > res){
tot += 1, res = max(res, ny);
}
else{
res = max(res, ny);
}
}
for(int i = 0; i < tot; i++){
ret *= 2, ret %= MOD;
}
return ret;
}
};
Question B Count Total Number of Colored Cells
题解
找规律
typedef long long ll;
class Solution {
public:
long long coloredCells(int n) {
ll ret = 2ll * n * (n - 1) + 1;
return ret;
}
};
Question A Split With Minimum Sum
题解
贪心，大的数位尽量放在低位。
class Solution {
public:
int splitNum(int num) {
int nums1 = 0, nums2 = 0;
string s = to_string(num);
sort(s.begin(), s.end());
int n = s.length(), res[2] = {0, 0}, flag = 0;
for(int i = 0; i < n; i++){
res[flag] *= 10, res[flag] += (s[i] - '0'), flag = !flag;
}
return res[0] + res[1];
}
};
这次周赛做的很差很差，主要原因可能是因为我的双指针水平太差了，这个t3真的看了很久没有看出来怎么做，甚至连贪心都想了，自然也没时间做完t4了，Profile Here。另外，之后如果A/B题太简单就不发题解了，只提一下用到了什么知识点，可以节约一些时间。
Question D Minimum Time to Visit a Cell In a Grid
题意
给定一个n*m的方格，左上的格子为起点，坐标记作(0, 0)，右下的格子为终点，坐标记作(n-1, m-1)。只能移动到相邻（上下左右）的格子，均需要花费1s时间，而不能停留在某个格子保持位置不变。给定每个格子的最早到达时间，求从起点到达终点的最短时间。
题解
是一个经典的单源最短路问题，如果差分约束问题做得够多的话，应该会一开始想到用差分约束的方法建边，之后从起点跑一个dijkstra。但是这个思路稍微有一点问题，是因为每个格点有一个要求的最早到达时间，而每个时刻都要求在移动，不能停留，这就要求如果可以从起点出发的话，就一定存在一个阶段可以满足在两个格点之间来回走的方式使满足所有格点的最早到达时间，因此这个最短到达时间和格点的最短到达时间之差的奇偶性与每个格点距离起点的hamilton距离的奇偶性应该是相同的（因为来回走并不会改变hamilton距离的奇偶性）。
在满足奇偶性的前提下，这个问题就是一个完完全全的魔改版dijkstra了。考虑从u走到v，从起点到u和v的最早时间是$t_u$和$t_v$，应该满足：
- $t_v \ge t_u + 1$
- $t_v \ge grid[v.x][v.y]$
接下来实现魔改dijkstra就可以了。代码见下：
代码
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
class Solution {
public:
int minimumTime(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
if (grid[0][1] > 1 && grid[1][0] > 1) return -1;
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
priority_queue<piii> q;
int dis[n][m];
memset(dis, -1, sizeof(dis));
q.push(piii(0, pii(0, 0)));
while (!q.empty()) {
auto p = q.top(); q.pop();
int i = p.second.first, j = p.second.second;
if (dis[i][j] >= 0) continue;
dis[i][j] = -p.first;
for (int k = 0; k < 4; k++) {
int nx = i + dir[k][0], ny = j + dir[k][1];
if (nx < 0 || ny < 0 || nx >= n || ny >= m || dis[nx][ny] >= 0) continue;
int v = (dis[i][j] + 1 >= grid[nx][ny] ? dis[i][j] + 1 : grid[nx][ny] + (grid[nx][ny] % 2 != (nx + ny) % 2));
q.push(piii(-v, pii(nx, ny)));
}
}
return dis[n - 1][m - 1];
}
};
Question C Find the Maximum Number of Marked Indices
题意
给定一个长为n的数组nums，在每个下标只能使用一次的前提下，找同时满足条件的(i, j)对($i \le j$)使得$2 * nums[i] \le nums[j]$的最多对数。
题解
首先暴力搜索是不行的，其次要注意每个下标只能使用一次，如果不是的话（即统计所有的i, j pair，且每个下标可以用无限次）可以遍历第一维，然后对第二维做二分，就可以在O(nlogn)的时间内实现。
但比赛时候我的思路就stuck在这里了，然后同时还想了个假的双指针做法，直接以为这题的正解不是双指针，但实际上就是个只需要五行就能写完的双指针…首先应该注意到答案最多不能超过n/2，因为每个数只能用一次。所以很自然的想法是把所有数按从小到大排序后，分成前半部和后半部两部分。nums[i]只在前半部分取，nums[j]只在后半部分取，而nums[i]我们希望从小到大选，因为这样可以让更多的后半部数可选，按照这种贪心方式可以用双指针来实现。
class Solution {
public:
int maxNumOfMarkedIndices(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
int l = 0, r = (n + 1) / 2;
while(r < n){
if(nums[l] * 2 <= nums[r]) l += 1;
r += 1;
}
return l * 2;
}
};
但我一开始想双指针均左向右扫描，对于每个左指针指到的nums[i]，都让右指针每次找到一个最小的nums[j]使满足nums[i] * 2 <= nums[j]，但这个如果不分成前后两部是错的，因为这样选到的一部分nums[j]可能本身可以用于充当nums[i]。
Question B Find the Divisibility Array of a String
涉及知识点
模拟，简单数论（记得取模）
typedef long long ll;
class Solution {
public:
vector<int> divisibilityArray(string word, int m) {
int n = word.length();
vector<int> ret(n, 0);
ll res = 0;
for(int i = 0; i < n; i++){
res *= 10;
res += (word[i] - '0');
ret[i] = (res % m == 0);
res %= m;
}
return ret;
}
};
Question A Left and Right Sum Differences
涉及知识点
前缀和，模拟
class Solution {
public:
vector<int> leftRigthDifference(vector<int>& nums) {
int n = nums.size();
vector<int> lsum(n + 1, 0), rsum(n + 1, 0);
for(int i = 1; i <= n; i++){
lsum[i] = lsum[i - 1] + nums[i - 1];
}
for(int i = n - 1; i >= 0; i--){
rsum[i] = rsum[i + 1] + nums[i];
}
vector<int> ret(n, 0);
for(int i = 0; i < n; i++){
ret[i] = abs(lsum[i] - rsum[i + 1]);
}
return ret;
}
};
这次周赛质量也是不错的，但是周末我当然是摸了，所以只能周一上午没课的时候把题补了，Profile Here。
Question D Find the String with LCP
题意
对于一个长为n的字符串word，定义它的lcp(longest common prefix)矩阵中的每个元素lcp[i][j]表示为word[i:n-1]和word[j:n-1]的最长公共前缀长度。现在给定一个lcp矩阵，问满足这个lcp矩阵的最小字典序的字符串是什么。
题解
好吧看了讨论区里的题解发现这个构造题我有点想不到，所以我摸了。。
贴一下题解链接
Question C Count the Number of Square-Free Subsets
题意
给定一个长为n的数组nums，定义若一个nums的子集中所有元素的和不能被任何平方数整除则说它是square-free的。求nums的所有square-free的非空子集的数目。
($n\le1000, nums[i]\le30$)
题解
这个问题受到数据范围影响特别大，我们可以首先关注到nums[i]最大只有30，小于30的质数只有2, 3, 5, 7, 11, 13, 17, 19, 23, 29这10个，所以实际上需要枚举的内容很少。题目的要求实际上就是说这个子集中所有元素的乘积分解质因子之后，每个因子最多只能出现一次（当然也可以是0次）。如果这是一个数据范围比较大的题，会需要先用唯一分解定理把所有数做分解质因子，然后dfs对于1-30中所有的合数（注意一下，需要枚举的合数实际上只有8个，有很多合数本身自己就包含了超过2个的相同质因子，这样我们可以减少很多枚举次数）进行选或者不选的枚举就可以了。
还需要注意一下，1比较特殊，选多少个都可以。最后计算完2-30取或不取的方法数res要再乘以pow(2, 1出现的次数)再减1（去掉什么都不选的空集，题目要求的是非空子集）
“复杂度”应该是需要最多计算(10*2^8)次
// 枚举合数的选取情况，对于每种枚举方式看还有哪些质数可以用
typedef long long ll;
const ll MOD = 1e9 + 7;
struct item{
ll prime, tot;
};
class Solution {
public:
int flag[31];
ll res = 0;
map<int, int> mp;
map<int, vector<item>> facmp;
set<map<int, int>> smp;
vector<item> Prime_Factorization(int x){
vector<item> ret;
for (int i = 2; i <= x / i; i++){
if(x % i == 0){
int tot = 0;
while(x % i == 0){
x /= i, tot++;
}
ret.push_back({i, tot});
}
}
if(x > 1) ret.push_back({x, 1});
return ret;
}
bool check(map<int, int> nusage, map<int, int> now){
bool ret = true;
for(auto &it : nusage)
ret = ret && (it.second <= min(1, mp[it.first]));
for(auto &it : now)
ret = ret && (it.second <= 1);
return ret;
}
void dfs(map<int, int> usage, map<int, int> st){
if(!check(usage, st) || smp.find(usage) != smp.end()){
return;
}
else{
ll tmp = 1;
for(auto &it : st){
if(it.second == 0 && mp[it.first] >= 1)
tmp *= (1 + mp[it.first]);
}
for(auto &it : usage){
if(it.second >= 1)
tmp *= mp[it.first];
}
res = (res + tmp) % MOD;
smp.insert(usage);
}
for(auto &it : usage){
if(mp[it.first] > 0 && it.second == 0){
usage[it.first] = 1;
auto nfac = facmp[it.first];
for(auto &it : nfac)
st[it.prime] += it.tot;
dfs(usage, st);
for(auto &it : nfac)
st[it.prime] -= it.tot;
usage[it.first] = 0;
}
}
}
int squareFreeSubsets(vector<int>& nums) {
for(auto &it : nums) mp[it] += 1;
for(auto &it : mp) facmp[it.first] = Prime_Factorization(it.first);
memset(flag, 0, sizeof(flag));
flag[2] = flag[3] = flag[5] = flag[7] = flag[11] = flag[13] = flag[17] = flag[19] = flag[23] = flag[29] = 1;
map<int, int> nusage;
nusage[6] = nusage[10] = nusage[14] = nusage[15] = nusage[21] = nusage[22] = nusage[26] = nusage[30] = 0;
map<int, int> nst;
for(int i = 1; i <= 30; i++) if(flag[i]) nst[i] = 0;
dfs(nusage, nst);
for(int i = 0; i < mp[1]; i++)
res *= 2, res %= MOD;
return (res - 1 + MOD) % MOD;
}
};
Question B Minimum Operations to Reduce an Integer to 0
题意
给定一个数n，可以对这个数做若干次操作：每次操作对当前这个数加上或减去一个任意的2的幂。求使n变为0的最少次数。
($n\le1e5$)
题解
由于n的范围很小，不想动脑子的方法就可以直接从0开始反向bfs递推，即先扩散到所有2的幂即需要1次操作的数，再扩散到需要2次操作的数等等。
const int maxn = 1e5 + 10;
class Solution {
public:
int dp[maxn * 2];
int minOperations(int n) {
memset(dp, 0x3f, sizeof(dp));
queue<pair<int, int>> q;
dp[0] = 0, q.push({0, 0});
while(!q.empty()){
auto now = q.front();
for(int i = 0; i < 17; i++){
auto nvalue = now.first + (1 << i);
if(nvalue <= 2e5 && dp[nvalue] > now.second + 1){
dp[nvalue] = now.second + 1, q.push({nvalue, now.second + 1});
}
nvalue = now.first - (1 << i);
if(nvalue >= 0 && nvalue <= 2e5 && dp[nvalue] > now.second + 1){
dp[nvalue] = now.second + 1, q.push({nvalue, now.second + 1});
}
}
q.pop();
}
return dp[n];
}
};
Question A Merge Two 2D Arrays by Summing Values
题意
合并两个表示key-value的key按照升序排列的列表(很像是倒排索引的合并)。
代码
可以双指针，这样是线性复杂度。因为数据范围很小，也可以直接用map偷懒。我比赛当然会选择偷懒好写的方法啦。
class Solution {
public:
vector<vector<int>> mergeArrays(vector<vector<int>>& nums1, vector<vector<int>>& nums2) {
map<int, int> mp;
for(auto &it : nums1){
mp[it[0]] += it[1];
}
for(auto &it : nums2){
mp[it[0]] += it[1];
}
vector<vector<int>> ret;
for(auto &it : mp){
ret.push_back(vector<int>{it.first, it.second});
}
return ret;
}
};
倒着讲，但这套题目没上场周赛质量高，A是个常规的枚举，B/C都是猜结论题，D是经典的线段树应用。前三题搞完23分钟，最后一题不想写线段树了就找了个板子改了改过了，D改板子有一个地方写错了错了一次，1:19AK的，Rank 516 / 22683。Profile Here。
Question D Handling Sum Queries After Update
题意
有两个长度均为n的数组nums1和nums2，nums1是一个01数组，针对这两个数组做q次询问，规则如下：
- “1 l r”，表示对nums1[l:r]上的0变为1，1变为0；
- “2 p 0”，表示对nums2[1:n]上的所有nums2[i] += p * nums1[i]
- “3 0 0”, 表示求$\sum_{i=1}^{n} nums2[i]$
($n \le 1e5, q \le 1e5, p \le 1e6$)
题解
我个人认为这是一道被改简单过的题，操作2和操作3完全是脱裤子放屁。操作1是一个区间01翻转，操作3实际上并不会询问特定区间的和，而只是询问nums2数组完整的和，这就要求我们的操作2并不需要单点更新，只需要维护这个数组完整的和就可以了，要想维护这个数组完整的和，我们在操作2实际上就相当于询问nums1数组[1:n]区间上到底有多少1，这个问题可以扩展到询问任意的[l:r]区间上到底有多少1。
因此我们明确了要做的事情，维护一个01序列的区间翻转，询问01序列的特定区间上到底要有多少1。这个是线段树的经典问题，更复杂的操作也可以完成，这实际上是SCOI2010(四川2010年省队)选拔的题目，我相信洛谷的评论区会比我讲的更加详细。代码如下：
typedef long long ll;
#define ls(k) ((k)<<1)
#define rs(k) (ls(k)^1)
#define mid ((l+r)>>1)
const int maxn = 1e5 + 10;
struct Node {
int len,sum;
int l[2],r[2],res[2];
int same,flip;
Node():same(-1),flip(0) {}
void turn(int k) {
l[k]=r[k]=res[k]=len,
l[k^1]=r[k^1]=res[k^1]=0;
sum=!k?0:len;
same=k, flip=0;
}
void rev() {
swap(l[0],l[1]), swap(r[0],r[1]), swap(res[0],res[1]);
sum=len-sum;
flip^=1;
}
};
class Solution {
public:
int n;
int a[maxn];
Node node[maxn*4];
void pushdown(int k) {
Node &ls=node[ls(k)], &rs=node[rs(k)];
int &same=node[k].same, &flip=node[k].flip;
if(same!=-1) {
ls.turn(same), rs.turn(same);
same=-1;
}
if(flip==1) {
ls.rev(), rs.rev();
flip=0;
}
}
Node maintain(const Node &ls,const Node &rs) {
Node R;
R.len=ls.len+rs.len, R.sum=ls.sum+rs.sum;
for(int i=0;i<2;i++) {
R.l[i]=ls.l[i], R.r[i]=rs.r[i];
if(ls.l[i]==ls.len) R.l[i]=ls.len+rs.l[i];
if(rs.r[i]==rs.len) R.r[i]=rs.len+ls.r[i];
R.res[i]=max(max(R.l[i],R.r[i]),ls.r[i]+rs.l[i]);
R.res[i]=max(R.res[i],max(ls.res[i],rs.res[i]));
}
R.same=-1, R.flip=0;
return R;
}
void build(int k,int l,int r) {
node[k].len=r-l+1;
if(l==r) {
int x=a[l];
node[k].l[x]=node[k].r[x]=node[k].res[x]=1;
node[k].sum=x;
return;
}
build(ls(k),l,mid);
build(rs(k),mid+1,r);
node[k]=maintain(node[ls(k)],node[rs(k)]);
return;
}
void flip(int k,int l,int r,int ql,int qr) {
if(l!=r) pushdown(k);
if(ql<=l && r<=qr) {
node[k].rev();
return;
}
if(ql<=mid) flip(ls(k),l,mid,ql,qr);
if(qr> mid) flip(rs(k),mid+1,r,ql,qr);
node[k]=maintain(node[ls(k)],node[rs(k)]);
return;
}
void flip(int l,int r) {
flip(1,1,n,l,r);
}
Node query(int k,int l,int r,int ql,int qr) {
if(l!=r) pushdown(k);
if(ql<=l && r<=qr) return node[k];
if(qr<=mid) return query(ls(k),l,mid,ql,qr);
else if(ql>mid) return query(rs(k),mid+1,r,ql,qr);
else return maintain(query(ls(k),l,mid,ql,qr),query(rs(k),mid+1,r,ql,qr));
}
int query_sum(int l,int r) {
Node ans=query(1,1,n,l,r);
return ans.sum;
}
public:
vector<long long> handleQuery(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {
vector<ll> ret;
ll res = 0;
n = nums1.size();
for(int i = 0; i < n; i++){
a[i + 1] = nums1[i];
}
build(1, 1, n);
for(auto &it : nums2){
res += it;
}
for(auto &q : queries) {
int op = q[0], x = q[1], y = q[2];
if(op == 1)
x += 1, y += 1, flip(x, y);
else if(op == 2){
res += query_sum(1, n) * 1ll * x;
}
else if(op == 3){
ret.push_back(res);
}
}
return ret;
}
};
Question C Minimum Impossible OR
题意
给定一个长为n的数组nums，问最小不能被任意个nums中的数按位或(即 $|_{i = 1}^{k} nums[index_i]$ ）表示的数。$(n \le 1e5, a[i] \le 1e9)$
题解
这也是一个观察的题目，有点数学归纳法的想法。
先从k=1开始想，如果nums不包括1，那么1一定是无法被表示的最小的那个数。
接着k=2，如果k=1已经被包括了，接下来需要考虑的不能被表示的最小数应该是k=2。而如果1和2都存在的话，下一个不能被表示的数就应该是k=4，到这里我们已经可以看出一些潜在的规律了，实际上我们只需要看看最小的不存在于给定的nums数组中的数就可以了，这些数都应该是2的幂次，就可以得到如下代码：
class Solution {
public:
int minImpossibleOR(vector<int>& nums) {
int tt = 1;
set<int> st;
for(auto &it : nums) st.insert(it);
for(int i = 1; i <= 31; i++){
if(st.count(tt) == 0){
return tt;
}
tt *= 2;
}
return tt;
}
};
Question B Minimum Score by Changing Two Elements
题意
给定一个长为n的数组nums，定义low score为|nums[i] - nums[j]| (0 <= i < j < nums.length)中最小的,high score是 |nums[i] - nums[j]| (0 <= i < j < nums.length)中最大的，可以任意修改最多两个下标的nums[i] = a, nums[j] = b($a, b \in Z$)，问修改后low score + high score 的最小可能值是多少？
题解
因为要求high + low的最小可能值，low score的最小可能值只能是0，即只要nums数组中存在两个相同的数就能达到这个最小可能值。
我们希望在取到high score的最小可能值的时候也尽量让low=0，而high相当于是求nums数组中最大值和最小值的差，想要让这个值尽可能地小，我们可以考虑把nums数组中的所有数从小到大排列在一个数轴上，数对应的点之间构成一条线段，如果想让这条线段变短，就只能砍掉一部分端点(即如让nums的最大值变为num s的次大值，就相当于砍掉次大值和最大值之间的这条线段)，因为只能砍两刀，因此让这条线段尽可能短的方法，只可能在int cand1 = abs(nums[n - 1] - nums[2]), cand2 = abs(nums[n - 2] - nums[1]), cand3 = abs(nums[n - 3] - nums[0]);这三个值中取最小的，而这个过程自然可以保证产生两个相同的值。
因此我们就有了如下代码：
class Solution {
public:
int minimizeSum(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
int cand1 = abs(nums[n - 1] - nums[2]), cand2 = abs(nums[n - 2] - nums[1]), cand3 = abs(nums[n - 3] - nums[0]);
return min(cand1, min(cand2, cand3));
}
};
Question A Maximum Difference by Remapping a Digit
题意
给定一个值num，可以做一次映射操作使0-9中的一个数码变为另一个数码（也可以相同，相当于不变化），从而使num变为一个新数。问这样得到的新数的最大值和最小值之间的差？
代码
暴力枚举每种映射就可以了。不需要想什么取巧的方法。
class Solution {
public:
int minMaxDifference(int num) {
string res = to_string(num);
int mini = num, maxi = num;
for(int dfm = '0'; dfm <= '9'; dfm++){
for(int dto = '0'; dto <= '9'; dto++){
string temp = res;
int x = 0;
for(auto &it : temp){
if(it == dfm)
it = dto;
}
for(int i = 0; i < temp.length(); i++){
x *= 10, x += (temp[i] - '0');
}
mini = min(mini, x), maxi = max(maxi, x);
}
}
return maxi - mini;
}
};
