第十九届程协杯部分题解 A D F G I K
Preface
其实本来以为简单的题不少，会有很多人分数都很高，但是实际上来看也还好?（
貌似从完整过题率来看，区分度还是有的（虽然不是太明显)
有些题数据炸锅了，实在是抱歉，第一次负责出题，有些地方太弱智了实在抱歉。
以下是代码火车头，后续题解的std中就不会出现了：（这里有define int long long，所以后续的题解中都是int，没有long long)
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <random>
#define endl '\n'
#define int long long
#define rep(i,a,b) for (int aa = a, bb = b, i = aa; i <= bb; i++)
#define rep2(i,a,b) for (int aa = a, bb = b, i = aa; i >= bb; i--)
using namespace std;
template<typename T>
void cc(const vector<T> &tem) {
for (const auto &x: tem) cout << x << ' ';
cout << endl;
}
template<typename... Args>
void cc(const Args &... a) {
size_t idx = 0;
((std::cout << a << (++idx == sizeof...(Args) ? "\n" : " ")), ...);
}
void fileRead() {
#ifdef LOCALL
freopen("D:\\AADVISE\\Clioncode\\untitled2\\in.txt", "r", stdin);
freopen("D:\\AADVISE\\Clioncode\\untitled2\\out.txt", "w", stdout);
#endif
}
void kuaidu() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); }
inline int max(int a, int b) {
if (a < b) return b;
return a;
}
inline double max(double a, double b) {
if (a < b) return b;
return a;
}
inline int min(int a, int b) {
if (a < b) return a;
return b;
}
inline double min(double a, double b) {
if (a < b) return a;
return b;
}
void cmax(int &a, const int &b) { if (b > a) a = b; }
void cmin(int &a, const int &b) { if (b < a) a = b; }
void cmin(double &a, const double &b) { if (b < a) a = b; }
void cmax(double &a, const double &b) { if (b > a) a = b; }
int gcd(int a,int b) {
if (!b) return a;
return gcd(b, a % b);
}
template<const int T>
int Kuai(int a,int b) {
int l = 1;
while (b) {
if (b % 2) l = l * a % T;
a = a * a % T, b /= 2;
}
return l;
}
template<typename T>
using vec = vector<T>;
using PII = pair<int, int>;
using INT = __int128;
Problem A. 云端的数据结构
本来计算的是暴力可以拿到一半的分数，但是随机出来的，貌似整体偏小，再加上数据范围从5e5改成了1e5（怕很多人直接爆零)，结果导致了暴力直接拿到了70分阿巴阿巴。
先说一下最暴力的写法，就是模拟的做法。预期得分25分。
每一次更新下标x，然后for循环套for循环，第一层循环枚举第i个点，第二层循环去求出来前i个点的最大值和后n-i个点的最大值，然后计算答案。
//--------------------------------------------------------------------------------
const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
int A[N];
//--------------------------------------------------------------------------------
//struct or namespace:
//--------------------------------------------------------------------------------
signed main() {
fileRead();
kuaidu();
T = 1;
//cin >> T;
while (T--) {
cin >> n;
rep(i, 1, n) {
cin >> A[i];
}
int q;
cin >> q;
rep(i, 1, q) {
int x, k;
cin >> x >> k;
A[x] += k;
int sum = 0;
//枚举第j个点
rep(j, 1, n) {
int mmax1 = -INF, mmax2 = -INF;
//找出前缀的最大值
rep(p, 1, j) mmax1 = max(mmax1, A[p]);
//找出后缀的最大值
rep(p, j, n) mmax2 = max(mmax2, A[p]);
//计算答案
sum += min(mmax1, mmax2) - A[j];
}
cc(sum);
}
}
return 0;
}
稍微不那么暴力的做法，就是开一个pre，suf数组，代表前缀1到i的a_i最大值和后缀i到n的a_i最大值。预期得分70分。
然后每一次更新了一个点x之后，我们用两个for循环分别去重新更新一下pre和suf数组，然后再用一个for循环来去求出每一个点的贡献。
这样的时间复杂度是O(qn)级别的，有意思的是看到赛时有人写的线段树，还以为写出来了正解，结果是用线段树去更新最大值，时间复杂度多了一个log。
//--------------------------------------------------------------------------------
const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
int A[N], pre[N], suf[N];
//--------------------------------------------------------------------------------
//struct or namespace:
//--------------------------------------------------------------------------------
signed main() {
fileRead();
kuaidu();
T = 1;
//cin >> T;
while (T--) {
cin >> n;
rep(i, 1, n) {
cin >> A[i];
pre[i] = suf[i] = A[i];
}
rep(i, 1, n) pre[i] = max(pre[i], pre[i - 1]);
rep2(i, n, 1) suf[i] = max(suf[i], suf[i + 1]);
int q;
cin >> q;
rep(i, 1, q) {
int x, k;
cin >> x >> k;
A[x] += k; //更新x
//更新pre数组
pre[x] = max(pre[x], A[x]);
rep(j, x+1, n) pre[j] = max(pre[j], pre[j - 1]);
//更新suf数组
suf[x] = max(suf[x], A[x]);
rep2(j, x-1, 1) suf[j] = max(suf[j], suf[j + 1]);
//求出每一个点的贡献
int sum = 0;
rep(j, 1, n) {
sum += min(pre[j], suf[j]) - A[j];
}
cc(sum);
}
}
return 0;
}
正解的办法是：
首先想到，这个问题求的是：
对于这个式子，我们可以化成
然后会发现，这个其实就是全局的最大值，我们用一个变量去维护就好了，然后关于a_i的部分也很方便就能维护出来（数组的和)。
那么如何可以快速地，在logn的复杂度下维护出来pre_i的和呢?（因为suf和pre很像，所以这里光说pre)
线段树，对数组进行维护，这个数组是代表前缀
。如果修改了
，变成
那么就和当前线段树的这个位置比较，如果没有超过线段树维护这个点的
，就不做任何操作。否则就要向右找到最后一个小于等于
的位置（这一步我们可以用线段树上二分），这样我们就求出来了一个区间的左边界和右边界，然后把这段区间用区间赋值（懒标记）。
综上，线段树上的节点维护的信息有：（pre数组的求和），
（懒标记），
（代表区间最左端的pre，用来二分查找位置的），
（记录区间长度）
开两个线段树直接暴力开搞。
//--------------------------------------------------------------------------------
const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
//--------------------------------------------------------------------------------
//struct or namespace:
class SEG {
#define xl x+x
#define xr x+x+1
//TODO 节点维护信息、apply函数、up函数
struct info {
int sum = 0;
int siz = 1;
int lan = 0; //懒标记
int mmin = 0; //到达节点最左端的pre_mmax
//区间加操作，这个题没有用到
void apply1(int k) {
sum += siz * k;
lan += k;
mmin += k;
}
//区间赋值操作
void apply2(int k) {
mmin = k;
sum = siz * k;
lan = k;
}
//up函数
friend info operator+(const info &q1, const info &q2) {
info q;
q.siz = q1.siz + q2.siz;
q.sum = q1.sum + q2.sum;
q.mmin = min(q1.mmin, q2.mmin);
return q;
}
};
int L, R;
vector<info> F;
void init(int x, int l, int r) {
if (l == r) {
F[x] = info();
return;
}
int mid = l + r >> 1;
init(xl, l, mid), init(xr, mid + 1, r);
F[x] = F[xl] + F[xr];
}
void down(int x) {
if (!F[x].lan) return;
F[xl].apply2(F[x].lan), F[xr].apply2(F[x].lan);
}
void add(int x, int l, int r, int l1, int r1, int k) {
if (l1 > r1) return;
if (l != r) down(x);
F[x].lan = 0;
if (l1 <= l and r <= r1) {
F[x].apply1(k);
return;
}
int mid = l + r >> 1;
if (r1 <= mid) add(xl, l, mid, l1, r1, k);
else if (mid < l1) add(xr, mid + 1, r, l1, r1, k);
else add(xl, l, mid, l1, mid, k), add(xr, mid + 1, r, mid + 1, r1, k);
F[x] = F[xl] + F[xr];
}
void add2(int x, int l, int r, int l1, int r1, int k) {
if (l1 > r1) return;
if (l != r) down(x);
F[x].lan = 0;
if (l1 <= l and r <= r1) {
F[x].apply2(k);
return;
}
int mid = l + r >> 1;
if (r1 <= mid) add2(xl, l, mid, l1, r1, k);
else if (mid < l1) add2(xr, mid + 1, r, l1, r1, k);
else add2(xl, l, mid, l1, mid, k), add2(xr, mid + 1, r, mid + 1, r1, k);
F[x] = F[xl] + F[xr];
}
//二分，找到小于等于val的最后一个位置
int erfen(int x, int l, int r, int val) {
int mid = l + r >> 1;
if (l == r) return l;
if (l != r) down(x);
F[x].lan = 0;
//如果右儿子的最小的那个值都小于等于我们修改后的val，那么就遍历右儿子，否则遍历左儿子。
if (F[xr].mmin <= val) return erfen(xr, mid + 1, r, val);
else return erfen(xl, l, mid, val);
}
info qry(int x, int l, int r, int l1, int r1) {
if (l1 > r1) return info();
if (l != r) down(x);
F[x].lan = 0;
if (l1 <= l and r <= r1) return F[x];
int mid = l + r >> 1;
if (r1 <= mid) return qry(xl, l, mid, l1, r1);
else if (mid < l1) return qry(xr, mid + 1, r, l1, r1);
else { return qry(xl, l, mid, l1, mid) + qry(xr, mid + 1, r, mid + 1, r1); }
}
#undef xl
#undef xr
public:
//TODO 调整乘的系数
SEG(int l, int r) {
L = l, R = r;
F.resize(r * 2.7);
init(1, l, r);
}
void clear(int l, int r) {
L = l, R = r;
init(1, l, r);
}
void add(int l, int r, int k) { add(1, L, R, l, r, k); }
void add2(int l, int r, int k) { add2(1, L, R, l, r, k); }
info qry(int l, int r) { return qry(1, L, R, l, r); }
int erfen(int val) { return erfen(1, L, R, val); }
};
SEG seg(1, N);
//开了两个线段树， 下面线段树是用来维护suf数组的
SEG seg2(1, N);
int A[N], B[N], pre1[N], pre2[N]; //这里用的pre2数组，实际就是suf数组
//--------------------------------------------------------------------------------
signed main() {
fileRead();
kuaidu();
T = 1;
// cin >> T;
while (T--) {
cin >> n;
int mmax = 0, sum = 0;
rep(i, 1, n) {
cin >> A[i];
sum += A[i];
cmax(mmax, A[i]);
}
seg.clear(1, n);
seg2.clear(1, n);
rep(i, 1, n) {
B[i] = A[n - i + 1];
pre1[i] = max(pre1[i - 1], A[i]);
pre2[i] = max(A[n - i + 1], pre2[i - 1]);
seg.add(i, i, pre1[i]);
seg2.add(i, i, pre2[i]);
}
// cc(seg.qry(1, n).sum);
cin >> m;
rep(i, 1, m) {
int a, b;
cin >> a >> b;
A[a] += b;
cmax(mmax, A[a]);
sum += b;
int l, r;
int val = seg.qry(a, a).mmin;
if (A[a] > val) {
l = a, r = seg.erfen(A[a]);
if (l <= r)seg.add2(l, r, A[a]);
}
// cc(seg.qry(1, n).sum);
B[n - a + 1] += b;
// seg2.add(n - a + 1, n - a + 1, b);
val = seg2.qry(n - a + 1, n - a + 1).mmin;
if (B[n - a + 1] > val) {
l = n - a + 1, r = seg2.erfen(B[n - a + 1]);
if (l <= r) seg2.add2(l, r, B[n - a + 1]);
}
// cc(l, r);
// cc(seg2.qry(1, n).sum);
cc(seg.qry(1, n).sum + seg2.qry(1, n).sum - sum - n * mmax);
// rep(j, 1, n) {
// cc(seg2.qry(j, j).sum);
// }
}
// cc(mmax);
}
return 0;
}
Problem D. 量子隧道穿梭
其实这个题就是一个暴力bfs题...
感觉大家都觉得暴力不靠谱的样子没有写bfs，但实际上一个简单的bfs就够了。定位是基础搜索题。
用一个bfs，然后同时对走过的点进行标记，这样就可以了。
顺便一提，其实不难发现，直达直径另一端节点这个操作我们最多只会执行一次，因为再执行一次其实就是回到原来的位置了。哪怕是你先执行一次，然后走几步，然后再执行一次，其实也相当于就是不执行，然后还是走那么几步。
所以如果k有值，那么我们就把到达终点的步数和到达终点对端的那个点的步数+1比较，取一个min就好了。
//--------------------------------------------------------------------------------
const int N = 2e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
int dp[N];
bool vis[N];
int st, ed, shun, ni, k;
//--------------------------------------------------------------------------------
//struct or namespace:
//--------------------------------------------------------------------------------
signed main() {
fileRead();
kuaidu();
T = 1;
//cin >> T;
while (T--) {
cin >> n >> k >> st >> ed >> shun >> ni;
st -= 1, ed -= 1;
rep(i, 0, n - 1) dp[i] = INF; //dp数组用来记录到达第i个点的步数
queue<PII> F;
F.push({ st, 0 });
while (!F.empty()) {
auto [x, val] = F.front();
F.pop();
if (vis[x]) continue;
vis[x] = 1;//vis数组用来打标记，防止走重复。
dp[x] = val;
F.push({ (x + shun) % n, val + 1 });
F.push({ (x - ni + n) % n, val + 1 });
}
int ans = dp[ed];
if (k > 0) cmin(ans, dp[(ed + n / 2) % n] + 1);
if (ans >= INF / 2)ans = -1;
cc(ans);
}
return 0;
}
Problem F. 树上操作
这个题的定位和A题其实是有点接近防AK的程度，只不过这个不太好骗分。
由于感觉大家对于这个题全部都在想骗分而没有正解，我就少扯一点（bushi
首先二分，求所有点深度的最大值的最小值。
然后考虑怎么处理，首先可以想到要将深度以下的求一个
，挪动的时候直接挪动
这个点。
然后直接暴力枚举每个点和他交换之后满不满足就好了。
判断满不满足的时候我们求一个向下深度的最大值就好了。
//--------------------------------------------------------------------------------
const int N = 5e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
//--------------------------------------------------------------------------------
//struct or namespace:
namespace z {
vector<PII> A[N];
int son[N], dep[N], fa[N], dis[N];
//重儿子，顶根，时间戳，子树最右端时间戳，时间戳会对应节点x
int hea[N], up[N], dnf[N], dnff[N], seq[N];
int len[N];
int tot;
void dfs(int x, int pa) {
son[x] = 1, dep[x] = dep[pa] + 1, fa[x] = pa;
int t = 0;
for (auto [y, val]: A[x]) {
if (y == pa) continue;
dis[y] = dis[x] + val;
dfs(y, x);
cmax(len[x], len[y] + 1);
son[x] += son[y];
if (!t or son[t] < son[y]) t = y;
}
hea[x] = t;
}
void dfs2(int x, int pa, int ding) {
dnf[x] = ++tot, up[x] = ding, seq[dnf[x]] = x;
if (hea[x]) dfs2(hea[x], x, ding);
for (auto [y, val]: A[x]) {
if (y == pa || y == hea[x]) continue;
dfs2(y, x, y);
}
dnff[x] = tot;
}
void clear(int n) {
tot = 0;
rep(i, 1, n) {
A[i].clear();
dis[i] = hea[i] = up[i] = dnf[i] = seq[i] = 0;
}
}
void add(int x, int y, int c = 1) {
A[x].push_back({y, c});
A[y].push_back({x, c});
}
int lca(int x, int y) {
while (up[x] != up[y]) {
if (dep[up[x]] < dep[up[y]]) swap(x, y);
x = fa[up[x]];
}
if (dep[x] > dep[y]) swap(x, y);
return x;
}
//返回x向上k次的点
int upup(int x, int k) {
if (dep[x] <= k) return -1;
int to = dep[x] - k;
while (dep[up[x]] > to) x = fa[up[x]];
return seq[dnf[x] - (dep[x] - to)];
}
int dist(int x, int y) { return dis[x] + dis[y] - dis[lca(x, y)] * 2; }
void work(int rt = 1) { dfs(rt, 0), dfs2(rt, 0, rt); }
//x的子树里有y就返回1
bool isFa(int x, int y) { return (dnf[x] <= dnf[y] and dnff[x] > dnf[y]); }
};
//--------------------------------------------------------------------------------
bool check(int mid) {
using namespace z;
int t = 0;
rep(i, 1, n) {
if (dep[i] < mid) continue;
if (len[i] == 0) continue;
if (t == 0) t = i;
if (isFa(t, i)) continue;
t = lca(t, i);
}
if (t == 0) return 1;
if (len[1] + 1 <= mid) return 1;
rep(i, 1, n) {
if (isFa(t, i) or isFa(i, t)) continue;
if (dep[i] >= mid) continue;
if (dep[t] + len[i] <= mid and dep[i] + len[t] <= mid) return 1;
}
return 0;
}
signed main() {
fileRead();
kuaidu();
T = 1;
//cin >> T;
while (T--) {
cin >> n;
z::clear(n);
rep(i, 1, n-1) {
int a, b;
cin >> a >> b;
z::add(a, b);
}
z::work();
int l = 0, r = n + 1;
while (l + 1 != r) {
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid;
}
cc(r);
}
return 0;
}
/*
*/
Problem G. 最长序列
其实不难发现，由于我们可以随意的排序，所以可以直接全部从小到大的排序，然后去重就好了。
实际上我们也不需要做从小到大的排序，只需要对数组去重就好了，直接用一个set就好了。
不知道set的可以baidu一下。c++里一个可以去重的容器。
//--------------------------------------------------------------------------------
const int N = 2e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
//--------------------------------------------------------------------------------
//struct or namespace:
//--------------------------------------------------------------------------------
signed main() {
fileRead();
kuaidu();
T = 1;
//cin >> T;
while (T--) {
cin >> n;
set<int> S;
rep(i, 1, n) {
int a;
cin >> a;
S.insert(a);
}
cc(S.size());
}
return 0;
}
Problem I. 能源切割
貌似这个题的描述不是那么的清楚，赛时有被提问过题意的具体含义。
其实这个题就是一个背包，但是不想出一个比较裸的背包，所以就变了一点点的花样（没敢变太多，害怕没人过了)
我们可以使一个物品免费，但是这个物品左边的所有的物品我们的花费不能超过m，右边也一样。
回想一下正常的背包问题，01背包的式子是：
i是代表的前i个物品，j是容量。
我们让一个物品免费，就是直接加上他的v_i，然后左侧所有物品，花费不能超过m其实就是dp[i-1][m]，右侧的物品呢?
我们反着求一个背包，得到dp2数组，那么dp2[i+1][m]就是代表的i后面的物品，花费不超过m的最大价值。
把这三个加起来就是我们选择i免费的贡献，取所有i的一个max就好了。
//--------------------------------------------------------------------------------
const int N = 1e3 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
//--------------------------------------------------------------------------------
//struct or namespace:
//--------------------------------------------------------------------------------
int pre[N][N], suf[N][N];
int val[N], cost[N];
signed main() {
fileRead();
kuaidu();
T = 1;
//cin >> T;
while (T--) {
cin >> n >> m;
rep(i, 1, n) {
cin >> cost[i] >> val[i];
}
rep(i, 1, n) {
rep(j, 1, m) {
if (j >= cost[i]) {
pre[i][j] = max(pre[i][j], pre[i - 1][j - cost[i]] + val[i]);
}
pre[i][j] = max(pre[i][j], pre[i - 1][j]);
}
}
rep2(i, n, 1) {
rep(j, 1, m) {
if (j >= cost[i]) {
suf[i][j] = max(suf[i][j], suf[i + 1][j - cost[i]] + val[i]);
}
suf[i][j] = max(suf[i][j], suf[i + 1][j]);
}
}
int ans = 0;
rep(i, 1, n) {
ans = max(ans, val[i] + (pre[i - 1][m] + suf[i + 1][m]));
}
cc(ans);
}
return 0;
}
Problem K. 充能调节
这个题其实更多的是细节，有一些坑需要注意。经过大家反复的试错，其实最后过题率还是比较高的。
说几个点，首先是要记得开long long，还有就是m有可能是1，会导致一直乘下去而没有大于n的时候。
//--------------------------------------------------------------------------------
const int N = 5e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
int A[N];
//--------------------------------------------------------------------------------
//struct or namespace:
//--------------------------------------------------------------------------------
int dfs(int b, int a) {
if (b == 1) return 1;
int ans = 0, mmax = INF;
//l是次数 mmax是最小值 ans是记录的答案的次数
int l = 1, bas = b;
while (b <= a) {
if (abs(b - a) < mmax) mmax = abs(b - a), ans = l;
l++;
b = b * bas;
}
if (abs(b - a) < mmax) mmax = abs(b - a), ans = l;
return ans;
}
signed main() {
fileRead();
kuaidu();
T = 1;
//cin >> T;
while (T--) {
cin >> n;
rep(i, 1, n) {
int a, b;
cin >> a >> b;
cc(dfs(b, a));
}
}
return 0;
}
京公网安备 11010502036488号