2022SDNU-ACM结训赛题解

首先感谢一下各位出题人的精心准备、验题人的辛勤付出、以及选手的积极参加

题解

Problem A 柳予欣的归来【数学】

出题人： bhq

没想到一血是被打完山大的牛客比赛后来结训赛玩的wyx拿走的！

题目描述：

计算$({\sum }_{0<d<p}{d}^{-1}{)}^m$，其中 $d^{-1}$ 是 $d$ 在模 $p$ ( $p$ 是一个素数) 意义下的乘法逆元，由于结果可能很大，请对 $998244353$ 取模。

思路：

本题是一个小思维题，对于一个素数 $p$ 来说，$p$ 的剩余系的每个元素的逆仍然构成它的剩余系。我们记 $p$ 的剩余系是 $P$ ，对于 $a\in P$ 来说， $a$ 的逆一共有两种情况，第一种情况是 $a^{-1}=a$，第二种情况是 $a^{-1}=b,b\in P$，此时$b^{-1}=a$，所以总体来说取逆并不会有什么变化，括号里面本质上就是一个等差数列求和。注意数据范围，$p$ 会很大，所以 $p\ast (p-1)$ 时会爆 $longlong$，所以要先取模 $998244353$，除以 $2$ 转化成乘 $2$ 的逆元，之后做一遍快速幂就可以了。

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define ll long long
const ll N = 1e5+5;
const ll mod = 998244353;ll qpow(ll a, ll b)
{a %= mod;ll ans = 1;while(b){if(b & 1)ans = (ans * a) % mod;a = (a * a) % mod;b >>= 1;}return ans;
}int main()
{std::ios::sync_with_stdio(false);ll p, m;cin >> p >> m;p %= mod;ll ans = (p * (p-1) % mod) * qpow(2, mod-2) % mod;cout << qpow(ans, m) << '\n';return 0;
}

Problem B 收收心找个电子厂上班了【区间贪心/差分约束】

出题人： LYJ

很可惜，赛时并没有人过这个题

题目描述：

给你m种条件(l[i],r[i],c[i])，要求构造一个01串，使得l[i]到r[i]中至少有c[i]个1，问满足所有条件下1的数量最少的串是什么

思路1

经典的区间贪心问题，我们将m种条件按照r从大到小排序

对于一个区间[l,r]，我们先计算一下区间中已经存在了多少个1，剩下的1就选最靠近r的那几个不是1的位置。

所以我们需要一个数据结构维护一下区间查询/更新 1的数量，还需要一个数据结构可以知道当前这个位置往前的一个不是1的位置，来进行更新

我们可以用树状数组或者线段树进行区间的维护

利用并查集进行维护i往前的第一个不为1的位置

#include <bits/stdc++.h>
using namespace std;#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define No cout<<"No\n"
#define Yes cout<<"Yes\n"
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define lowbit(x) (x&(-x))
#define io ios::sync_with_stdio(false)
typedef long long ll;
typedef pair <int,int> pii;#define MAX 300000 + 50
int n, m, k, x, y, p;
struct ran{int l, r, x;int id;bool operator < (const ran &a)const{return r < a.r;}
}tr[MAX];int ans[MAX];
int fa[MAX];
int getfa(int x){return x == fa[x] ? x : fa[x] = getfa(fa[x]);
}int ar[MAX];
void add(int id){while(id <= n){++ar[id];id += lowbit(id);}
}
int getans(int id){int ans = 0;while(id){ans += ar[id];id -= lowbit(id);}return ans;
}void work(){cin >> n >> m;for(int i = 1; i <= m; ++i){cin >> tr[i].l >> tr[i].r >> tr[i].x;tr[i].id = i;}sort(tr+1, tr+1+m);for(int i = 1; i <= n; ++i)fa[i] = i;for(int i = 1; i <= m; ++i){tr[i].x -= (getans(tr[i].r) - getans(tr[i].l - 1));if(tr[i].x <= 0)continue;for(int id = getfa(tr[i].r); tr[i].x;id = getfa(id)){add(id);--tr[i].x;fa[id] = getfa(id-1);ans[id] = 1;}}for(int i = 1; i <= n; ++i)cout << ans[i] << " \n"[i==n];
}int main(){io;work();return 0;
}

思路2:

差分约束板子题

假设所求数组叫做ar[i]

则我们令sum[i]表示ar数组的前缀和数组，对于l, r, c我们可以转换成sum[r]-sum[l-1] >= c，因为求的是最小值，所以跑最长路，用>号，也就是sum[r] >= sum[l-1] + c,建一条l-1到r的权值为c的边，但是为了避免使用0，我们改成l到r+1建一条边

因为是前缀和，且一个位置最多一个1，所以建立一个0≤sum[i]-sum[i-1]≤1的条件，拆开来看就是sum[i]≥sum[i-1]+0,建一条从i-1到i的权值为0的边，sum[i-1]≥sum[i]-1,建立一条从i到i-1的权值为-1的边，因为存在负权边，所以跑SPFA

得到的前缀和数组再做一次差分就可以得到原数组

#include <bits/stdc++.h>
using namespace std;#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define No cout<<"No\n"
#define Yes cout<<"Yes\n"
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false)
typedef long long ll;
typedef pair <int,int> pii;#define MAX 1000000 + 50
int n, m, k, l, r, c, p;int tot;
int head[MAX];
struct ran{int to, nex, val;
}tr[MAX];
inline void add(int u, int v, int c){tr[++tot].to = v;tr[tot].val = c;tr[tot].nex = head[u];head[u] = tot;
}int dis[MAX];
bool vis[MAX];
void spfa(){deque<int>q;for(int i = 1; i <= n; ++i){q.push_back(i);dis[i] = 0;vis[i] = 1;}while (!q.empty()) {int u = q.front();q.pop_front();vis[u] = 0;for(int i = head[u]; i; i = tr[i].nex){int v = tr[i].to;if(dis[v] < dis[u] + tr[i].val){dis[v] = dis[u] + tr[i].val;if(!vis[v]){vis[v] = 1;if(!q.empty() && dis[q.front()] > dis[v])q.push_front(v);else q.push_back(v);}}}}for(int i = 2; i <= n + 1; ++i){cout << dis[i] - dis[i - 1] << " \n"[i==n+1];}
}void work(){cin >> n >> m;for(int i = 1; i <= n; ++i){add(i, i+1, 0);add(i+1, i, -1);}for(int i = 1; i <= m; ++i){cin >> l >> r >> c;add(l, r+1, c);}spfa();
}int main(){io;work();return 0;
}

Problem C 我没有脑子【打表/矩阵快速幂】

出题人: JBQ

很遗憾这么签到的一道题没有人做

题目描述：

生兔子，兔子的数量是斐波那契数列

问第l亿年到第r亿年出生了多少兔子，且出生的兔子并不包括第l年出生的兔子，第0年是没有兔子出生的

思路：

观察一下数据范围，会发现0<=l,r<=300,显然是个简单的打表题，我们可以暴力跑斐波那契求出0亿到300亿的斐波那契数，跑的时候可以用三个变量来回倒换即可避免数组开不下的问题，大概本地跑个几分钟就能打出表，然后用数组记录下来第i亿年的斐波那契数，这就是一个前缀和，查询哪个区间就利用前缀和的性质计算一下就行

因为涉及到减法，所以会出现负数的情况，记得+mod后再对mod取模

当然，这是一个矩阵快速幂的板子题，套了就能过

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double pi = acos(-1);
const ll mod = 998244353;ll qz[] = {0,174079809,350529837,540135893,248983311,188662298,163535581,26424980,29356346,377822061,990450892,302998835,770343747,552350183,15396855,424926956,88941576,763450547,898383525,17528340,412076452,206977951,379701090,699742036,380345178,630855901,215773428,670848941,708850059,759042535,370671059,914173509,546356307,5232597,694566734,700347768,106284179,48542533,336670082,271726108,760855650,177724054,224473711,884667489,399724153,120220241,856574745,909795978,378135714,190545578,146687109,355925757,346733017,121393103,736658703,436961107,259288615,749208626,766089397,194102954,638000257,519167820,655288960,872163139,532492585,496860676,774844232,39275773,498133671,371136296,389528837,693448612,466324418,925981560,611164646,232564044,13688323,711293940,965100438,399071469,90757559,803023736,326830157,805286509,254912924,102214332,274197678,524443975,289792461,926311141,67790802,467964271,333938384,258436673,71452804,683937426,404752872,198446430,838706053,501212411,167522484,427792454,240181277,502955299,959889585,956146057,947694331,472908698,164907180,295903902,789545095,819397095,885110015,187068234,859373205,461949265,833268322,188830126,620580489,81476315,799979868,872780884,639335743,214604713,725457919,602768712,404752628,261042264,452466864,264650298,83342962,525806466,242898501,648090615,211023083,216855464,271913720,956861944,389777898,246477234,277948122,261757157,583255005,168253729,301612668,617239094,32212131,382009316,914610194,865430047,367903763,582568911,237402789,907511216,795851825,535685886,184939689,215710754,830040275,404086346,178845145,133296369,768509020,34346825,579080786,789976801,291262952,445117166,638901953,466760442,524216211,990440339,351571978,434005891,41322877,67726455,857058332,886192362,908954613,601948714,350088780,970979040,656331119,804659347,151691585,686880448,555777756,212851886,562313640,685580955,792479573,305192341,212979909,755367688,422525487,279142234,908459752,116009277,138047368,74170783,908569483,278453199,832057846,480474473,744340566,524823005,490844667,491530577,908970624,578875419,778732446,981441931,930496121,455524732,336924607,337585594,22617186,337729446,273285818,118523424,123031060,470173959,2335851,265337201,239746786,649284192,963473000,267280391,367303681,768114245,941758551,454661791,605958520,201446298,646412496,455731820,428662317,558589444,262367234,641423282,726013475,897721843,206526423,904882765,25830392,995523912,304380590,881069167,922277936,949431046,116187873,599781594,404612175,340924556,688094980,354391975,701905403,220003631,506648913,905201506,848118900,691020931,611886852,46282188,735419146,223099686,554098962,124828843,283063450,176654870,404630446,796542941,770962213,676150050,456492707,909163219,971214787,400826726,254478508,463527309,686895321,688734626,781497186,460395419,411403102,778541634,894602464,915995672,604742042,160537389,89030071,956235246,605154828,169835294,549232325,789998297,189968249,55896911,957522027,790730960,238229067};int main()
{ll T,p,q;cin>>T;while(T--){cin>>p>>q;cout<<(qz[q] - qz[p] + mod)%mod<<endl;}return 0;
}

#include <bits/stdc++.h>
using namespace std;#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 998244353
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;#define MAX 300000 + 50
int n, m, k, x, y;
int tr[MAX];struct Matrix{ll tr[2][2];Matrix(){mem(tr, 0);}Matrix operator * (const Matrix y){Matrix ans;for(int i = 0; i < 2; ++i){for(int j = 0; j < 2; ++j){for(int k = 0; k < 2; ++k){(ans.tr[i][j] += tr[i][k] * y.tr[k][j]) %= mod7;}}}return ans;}void operator = (const Matrix b){for(int i = 0; i < 2; ++i){for(int j = 0; j < 2; ++j){tr[i][j] = b.tr[i][j];}}}
};
ll getans(ll n){Matrix ans, cnt;ans.tr[0][0] = ans.tr[1][1] = 1;cnt.tr[0][0] = cnt.tr[0][1] = cnt.tr[1][0] = 1;while(n){if(n & 1)ans = ans * cnt;cnt = cnt * cnt;n /= 2;}return ans.tr[0][0];
}ll fuck[MAX];void work(){for(ll i = 1; i <= 300; ++i){fuck[i] = getans(i * 100000000ll - 1);}int t;cin>>t;while(t--){cin >> x >> y;cout << (fuck[y] - fuck[x] + mod7) % mod7 << endl;}
}int main(){io;work();return 0;
}

Problem D 我是杀猪饲料，祝你天天开心【签到】

出题人: LYJ

本来没想出hello world的题，但是突然接到通知大二不打了，这套题只给大一打，我就连夜加了一道

如果没有这个题，大家很可能五个小时都在牢底坐穿

还是要祝一下蛇姐生日快乐耶！

题目描述：

输出”蛇姐生日快乐!!!”即可

#include <bits/stdc++.h>
using namespace std;#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;#define MAX 300000 + 50
int n, m, k, x;
int tr[MAX];void work(){cout << "蛇姐生日快乐!!!";
}int main(){io;work();return 0;
}

Problem E 没什么特殊意义，就是想混一个最长的题目名字，然后让大家点进来做这道题

出题人: NXY

关于xygg出了个权值线段树却被两个人用别的思路随便卡过去这件事

思路：

第一种做法：离散化 + 权值线段树
我们发现每个数本身没有什么用，我们需要的仅仅是他们之间的大小关系，而 $N$ 又不是很大，所以考虑离散化。
然后把离散化之后的序列用权值线段树维护起来。

第二种做法：平衡树
动态查询第 $k$ 大数，容易想到平衡树直接维护

第三种做法：对顶堆
$\text{szz}$ 的考场做法。

第四种做法: 主席树
$\text{gts}$ 的考场做法

大家如果要补题的话建议学习第一种做法和第三种做法，第一种做法很典型很常见，是一种必不可少的技能点。第三种做法思维上很巧妙很有意思，并且代码简短容易理解，也同样建议大家学习

#include<bits/stdc++.h>using namespace std;
const int N = 1e5 + 10;int n,w;
int a[N],b[N],c[N];bool cmp(int x , int y)
{return x > y;}struct NO
{int l;int r;int w;
};struct SigmentT
{NO t[N * 4];void Build(int p , int l , int r){t[p].l = l; t[p].r = r;if(l == r) return;int mid = (l + r) >> 1;Build(p << 1 , l , mid);Build(p << 1 | 1 , mid + 1 , r);}void Updata(int p , int w){if(t[p].l == t[p].r) {t[p].w++; return;}int mid = (t[p].l + t[p].r) >> 1;if(w <= mid) Updata(p << 1 , w);else Updata(p << 1 | 1 , w);t[p].w = t[p << 1].w + t[p << 1 | 1].w;}int Query(int p , int k){if(t[p].l == t[p].r) return t[p].l;if(t[p << 1].w < k) return Query(p << 1 | 1, k - t[p << 1].w);else return Query(p << 1 , k);}
}tr;int main()
{//freopen("aa.in","r",stdin);scanf("%d%d",&n,&w); for(int i = 1; i <= n; i++)scanf("%d",&a[i]) , b[i] = a[i];std::sort(b + 1 , b + 1 + n);int LEN = std::unique(b + 1 , b + 1 + n) - b - 1;for(int i = 1, tmp; i <= n; i++)tmp = a[i] , a[i] = std::lower_bound(b + 1 , b + 1 + LEN , a[i]) - b , c[a[i]] = tmp;tr.Build(1 , 0 , LEN);for(int i = 1; i <= n; i++){int m = max(1 , i * w / 100);tr.Updata(1 , a[i]);printf("%d ",c[tr.Query(1 , i - m + 1)]);}}

#include<bits/stdc++.h>const int N = 3e5 + 10;int n,w;
int a[N];struct No {int p,siz,val,sel,son[2];
};struct SBT{int rt,idx;No t[N];void Pushup(int u) {t[u].siz = t[t[u].son[0]].siz + t[t[u].son[1]].siz + t[u].sel;}void rotate(int u) {int y = t[u].p , z = t[y].p;int k = t[y].son[1] == u;t[z].son[t[z].son[1] == y] = u , t[u].p = z;t[y].son[k] = t[u].son[k ^ 1] , t[t[u].son[k ^ 1]].p = y;t[u].son[k ^ 1] = y , t[y].p = u;Pushup(y) , Pushup(u);}void Splay(int u , int p) {while(t[u].p != p) {int y = t[u].p , z = t[y].p;if(z != p)if((t[z].son[1] == y) ^ (t[y].son[1] == u))rotate(u);else rotate(y);rotate(u);}if(!p) rt = u;}void insert(int val) {int u = rt , p = 0;while(u) {if(val == t[u].val) break;p = u , u = t[u].son[val > t[u].val];}if(!u) u = ++idx;t[u].sel++;t[u].p = p;t[u].val = val;if(p) t[p].son[val > t[p].val] = u;Splay(u , 0);}int getk(int k) {int u = rt;while(1) {if(k <= t[t[u].son[0]].siz) u = t[u].son[0];else if(k <= t[t[u].son[0]].siz + t[u].sel) {Splay(u , 0); return t[u].val;}else k -= t[t[u].son[0]].siz + t[u].sel , u = t[u].son[1];}}
}tr;const int inf = 1e9;int main() {//freopen("aa.in","r",stdin);scanf("%d%d",&n,&w); tr.insert(-1) , tr.insert(inf);for(int i = 1 , x; i <= n; i++) {scanf("%d",&x); tr.insert(x);int end = std::max(1 , i * w / 100);printf("%d ",tr.getk(i - end + 1 + 1));}
}

Problem F 泷1千0（hard version）【构造】

出题人: DJK

看hard版之前先看看easy版的

题目描述：

跟简单版相比，不同点在于字符串长度，和操作总次数发生了变化。

思路：

给出其中一种构造方式。

由于是对前缀进行操作，容易想到从后向前匹配两个01串，当$s串与t串$在位置$i$不同时，执行操作$i$,但当执行完操作$i$后，$s串和t串$在位置$i$依旧可能不匹配，所以我们需要预处理$s$串，让它全变成$0$或$1$，这样的话就可以保证执行操作$i$后，一定匹配。

容易发现，至多操作$2\ast n$次（预处理至多$n$次，从后向前匹配过程至多$n$次）。

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
//#define int ll
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define endl '\n'
#define pii pair<int,int>const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const double eps = 1e-4;
int n, sum;
string s1, s2;
char ch;
int ans[maxn];int main()
{io;//freopen("20.in", "r", stdin);//freopen("20.out", "w", stdout);cin >> s1 >> s2;n = s1.size();s1 = '$' + s1;s2 = '$' + s2;sum = 0;for(int i = 2; i <= n; ++i){if(s1[i] != s1[i - 1])ans[++sum] = i - 1;}ch = s1[n] - '0';for(int i = n; i > 0; --i){if(ch != (s2[i] - '0')){ans[++sum] = i;ch = 1 - ch;}}cout << sum;for(int i = 1; i <= sum; ++i) cout << ' ' << ans[i];cout << '\n';return 0;
}

Problem G A+B Problem【ull自然溢出】

出题人：NXY

a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊

这个题最开始的时候是NXY想考ull自然溢出等于对2⁶⁴取模，所以题目名称本来叫做**“自然溢出啥事没有!”**，但是有狗提议改把a和b的数字的长度改到1e5，使得NXY卡了一下py（

思路：

需要用到的知识点有两个：

• unsigned long long自然溢出等价于对 $2^{64}$ 取模，也就是说自然溢出啥事没有!
• $(a\times b+c)\%p=((a\times b)\%p+c\%p)\%p$

因此我们只需要把输入的数 $a$ 分解为 $a=x\ast 10+c$即可

NXY 特意卡了 python

#include <bits/stdc++.h>
using namespace std;#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int,int> pii;#define MAX 300000 + 50
string s;
ull a, b;void work(){cin >> s;a = b = 0;for(auto x : s){a = a * 10 + (ull)(x - '0');}cin >> s;for(auto x : s){b = b * 10 + (ull)(x - '0');}cout << (ull)(a+b) <<endl;
}int main(){io;work();return 0;
}

Problem H 柳予欣的色图【Pólya 计数】

出题人: BHQ

防AK题

题目描述：

一个手链上有 $n$ 个珠子，有 $n$ 种颜色，给每个珠子都染上颜色。有多少种不同的染色方法。由于方案数很多，请对 $998244353$ 取模。

题解

Pólya 计数的裸题，很难，想了解可以自己了解。

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define ll long long
const int N = 1e4+5;
const ll mod = 998244353;ll qpow(ll a, ll b, ll c){a %= c;ll ans = 1;while(b){if(b & 1)ans = (ans * a) % c;a = (a * a) % c;b >>= 1;}return ans;
}ll phi(ll n){ll ans = n;for(int i = 2; i*i <= n; ++i){if(n % i == 0){ans = ans / i * (i-1);while(n % i == 0)n /= i;}}if(n != 1)ans = ans / n * (n-1);return ans;
}void solve(ll n){if(n == 1)cout << 1 << '\n';else{ll ans = 0;for(int i = 1; i * i <= n; ++i){if(n % i == 0){if(i * i == n)ans = (ans + (phi(n/i) * qpow(n, i, mod) % mod)) % mod;else{ans = (ans + (phi(i) * qpow(n, n/i, mod) % mod)) % mod;ans = (ans + (phi(n/i) * qpow(n, i, mod) % mod)) % mod;}}}cout << (ans * qpow(n, mod-2, mod)) % mod << '\n';}
}int main()
{std::ios::sync_with_stdio(false);ll n;cin >> n;solve(n);return 0;
}

Problem I WWW的杂货铺【模拟】

出题人: WYY

题目描述：

M条出售记录，每条出售记录由物品名称、收货地、出售数目组成。

请按如下规则进行统计并输出：物品按收货地分类，并合并出售数目,收货地按字典序排列，同一收货地的物品按字典序排列。

思路：

很简单的模拟题，没什么意思

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;#define MAX 300000 + 50
int n, m, k, op;
int x, y, z;
string s, t;struct ran{string s;map<string, int>mp;
}tr[105];void work(){cin >> n;for(int i = 1; i <= 100;++i)tr[i].mp.clear();map<string, int>mp;int tot = 0;for(int i = 1; i <= n; ++i){cin >> s >> t >> x;if(!mp.count(t))mp[t] = ++tot;tr[mp[t]].s = t;tr[mp[t]].mp[s]+=x;}for(auto [x,y] : mp){cout << tr[y].s << endl;cout << "--------------------\n";for(auto [u, v] : tr[y].mp){cout << "    ";cout << u << "(" <<v <<")\n";}cout << "--------------------\n";}}int main(){io;int tt;cin>>tt;for(int _t = 1; _t <= tt; ++_t){work();if(_t != tt)cout << endl;}return 0;
}

Problem J 去玩宝可梦喽~ 【dp+线段树】

出题人: DJK

题目描述：

脱离题干背景，单纯考虑区间操作，发现题意如下：

给你一个长度为$n(1\le n\le 5\ast 10^5)$的数组。你需要将其分成几段连续的子区间，每一段区间的权值如下：

• 若区间和大于0，则为区间长度
• 如区间和等于0，则为0
• 如区间和小于0，则为区间长度的相反数

用一个式子表示即：$val[l,r]=sign(sum[l,r])\ast (r-l+1)$ $(val[l,r]表示区间[l,r]的权值,sign函数同原题中的f函数，sum[l,r]亦相同)$

问你分出来的子区间的权值和最大为多少，并且是否大于等于$H$。

思路

数据结构优化DP

我们首先考虑暴力解法。

定义$dp[i]$为$[1,i]$中的最大权值和，容易发现可以$O(n)$转移，总体复杂度需要$O(n^2)$。

转移方程：$dp[i]=max(dp[i],dp[j]+sign(sum[j+1,i])\ast (i-(j+1)+1))其中(0\le j<i)$

复杂度过高，我们考虑优化。

根据$sign$函数的值分类讨论，化简转移方程：

$dp[i]=max(dp[i],dp[j]+sign(sum[i]-sum[j])\ast (i-j))$

若$sum[i]==sum[j]$, $dp[i]=max(dp[j])$

若$sum[i]>sum[j]$,$dp[i]=max(dp[j]-j+i)$

若$sum[i]<sum[j]$,$dp[i]=max(dp[j]+j-i)$

我们只需要求出上述三种情况下对应的$max$，之后这三个值取$max$即可。

容易发现，需要一个支持单点修改+区间查询且复杂度过得去的数据结构来维护。

做法是预处理前缀和，之后离散化，然后按照前缀和建线段树（其他满足条件的数据结构均可）。

即线段树的下标表示$sum[j]$,上述的三个最大值分别通$query(sum[i],sum[i])$,$query(1,sum[i]-1)$,$query(sum[i]+1,n)$获得。

复杂度$O(nlogn)$。

另外，提示中试试暴力是希望先写出暴力转移方程，方便之后的观察优化。

$5e5$的数据量暴力是不可能过的。

下面给出利用线段树优化的代码。

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
#define int ll
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define endl '\n'
#define itt set<node>::iterator
#define pii pair<int,int>const int inf = 0x3f3f3f3f;
const int maxn = 5e5 + 5;
int t, n, x, h;
int sum[maxn];
int dp[maxn];
vector<int> vt;
struct node
{int l, r;int dp, dp1, dp2;//维护上述的三个最大值int mid(){return (l + r) >> 1;}void print(){cout << l << ' ' << r << ' ' << dp << ' ' << dp1 << ' ' << dp2 << '\n';}
} tree[maxn<<2];void pushup(node &p, node &le, node &ri)
{p.l = le.l;p.r = ri.r;p.dp = max(le.dp, ri.dp);p.dp1 = max(le.dp1, ri.dp1);p.dp2 = max(le.dp2, ri.dp2);
}void pushup(int p)
{pushup(tree[p], tree[p<<1], tree[p<<1|1]);
}void build(int p, int l, int r)
{tree[p].l = l;tree[p].r = r;if(l == r){tree[p].dp = tree[p].dp1 = tree[p].dp2 = -inf;return ;}int mid = tree[p].mid();build(p<<1, l, mid);build(p<<1|1, mid + 1, r);pushup(p);
}void updata(int p, int pos, int dp, int id)
{if(tree[p].l == tree[p].r){tree[p].dp = max(tree[p].dp, dp);tree[p].dp1 = max(tree[p].dp1, dp - id);tree[p].dp2 = max(tree[p].dp2, dp + id);return ;}int mid = tree[p].mid();if(pos <= mid) updata(p<<1, pos, dp, id);else updata(p<<1|1, pos, dp, id);pushup(p);
}node query(int p, int l, int r)
{if(l > r) return {-inf, -inf, -inf, -inf};if(l <= tree[p].l && tree[p].r <= r) return tree[p];int mid = tree[p].mid();if(mid >= r) return query(p<<1, l, r);else if(mid < l) return query(p<<1|1, l, r);else{node le = query(p<<1, l, r);node ri = query(p<<1|1, l, r);node res;pushup(res, le, ri);return res;}
}void work()
{vt.clear();cin >> n >> h;for(int i = 1; i <= n; ++i){cin >> x;sum[i] = sum[i - 1] + x;vt.push_back(sum[i]);dp[i] = 0;}vt.push_back(0);sort(vt.begin(), vt.end());vt.erase(unique(vt.begin(), vt.end()), vt.end());build(1, 1, vt.size());node pp;int mx1, mx2, mx3, pos;pos = lower_bound(vt.begin(), vt.end(), 0) - vt.begin() + 1;updata(1, pos, 0, 0);for(int i = 1; i <= n; ++i){pos = lower_bound(vt.begin(), vt.end(), sum[i]) - vt.begin() + 1;mx1 = query(1, 1, pos - 1).dp1;mx2 = query(1, pos, pos).dp;mx3 = query(1, pos + 1, vt.size()).dp2;dp[i] = max(mx1 + i, max(mx2, mx3 - i));updata(1, pos, dp[i], i);}cout << dp[n] << ' ' << (dp[n] >= h) << '\n';
}signed main()
{io;cin >> t;while(t--) work();return 0;
}

Problem K 逃出虚圈！【bfs】

出题人: LYJ

出了一个bfs的模版题，没人做，好伤心，写了半天的题目背景，没人看，好伤心，甚至在赛时加了一个小彩蛋，也没人看，好伤心

虽然

题目描述：

n个点，m条边，无向图

给你p个起点，q个终点，问你从任意一个起点出发，到达任意一个终点需要的最短距离是多少

思路：

bfs就行，把起点都塞进队列里面，然后记录q个终点，跑的时候遇到第一个出现的终点的时候就是最短的

#include <bits/stdc++.h>
using namespace std;#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;#define MAX 1000000 + 50
int n, m, k, x, y, a, b;
vector<int>G[MAX];queue<int>q;
set<int>se;
int dis[MAX];void bfs(){while(!q.empty()){int u = q.front();q.pop();if(se.count(u)){cout << dis[u] << endl;return;}for(auto v : G[u]){if(dis[v] != inf)continue;dis[v] = dis[u] + 1;q.push(v);}}cout << "N0" << endl;
}void work(){cin >> n >> m;for(int i = 1; i <= m; ++i){cin >> x >> y;G[x].push_back(y);G[y].push_back(x);}mem(dis, inf);cin >> a >> b;for(int i = 1; i <= a; ++i){cin >> x;q.push(x);dis[x] = 0;}for(int i = 1; i <= b; ++i){cin >> x;se.insert(x);}bfs();}int main(){work();return 0;
}

Problem L 为爱发电的Oier【简单期望】

出题人: WWY

签到题，没人写，6

题目描述：

我们可以把题目理解成抛硬币，问期望抛多少次可以使得正面朝上的次数是n

思路：

显然，期望抛2次，可以使得正面朝上的次数是1

拿n次正面朝上的期望就是2*n次

所以输出2*n就行

这里有一个很有意思的事情：

十六分钟的时候就有人看到了这个题，并写出了正解，但是因为他没写输入，所以挂了，（笑死

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;#define MAX 300000 + 50
int n, m, k, x;
int tr[MAX];void work(){cin >> n;cout << 2 * n << endl;
}int main(){io;work();return 0;
}

Problem M完全不管大一死活【分类讨论】

出题人: LYJ

出题的时候，在这个题前面出了五六个题，没有一个签到题，所以我就放了一个小讨论题

题目描述：

你在0的位置，目标是x的位置，y的位置有一个门，z的位置有一个钥匙，问你最少需要走几步能到x，如果不能到输出-1

思路：

签到题，简单分类一下就行，没什么意思

#include <bits/stdc++.h>
using namespace std;#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;#define MAX 300000 + 50
int x, y, z;void work(){cin >> x >> y >> z;if(x == 0){cout << 0 << endl;}else if(x > 0){if(y < 0 || y > x)cout << x << endl;else {if(z > y)cout << "BLEACH yyds" << endl;else{if(z > 0)cout << x << endl;else cout << -z*2 + x << endl;}}}else{if(y < x || y > 0)cout << -x << endl;else{if(z < y)cout << "BLEACH yyds" << endl;else {if(z > 0)cout << 2*z - x << endl;else cout << -x << endl;}}}
}int main(){io;work();return 0;
}

Problem N 泷1千0（easy version）【构造】

出题人: DJK

题目描述：

给你两个字符串$s,t$,按照给定的操作方式，是$s$串变成$t$串，要求在$3\ast n$次内完成（$n$是字符串的长度）。

思路：

给出其中一种构造方式。

我们希望当$s串与t串$在位置$i$不同时，我们希望取反第$i$个元素且不影响其他元素，这样就可以$O(n)$遍历一遍。

容易发现，取反和反转都拥有一个特征。即对一个01串取反或反转偶数次，字符串不变。

由此，我们即可实现取反第$i$个位置,而不影响其他元素。

当$s串与t串$在位置$i$不同时，进行如下操作：

• 执行操作$i$
• 执行操作$1$
• 执行操作$i$

可以发现，至多需要$3\ast n$次，满足题意。

代码：

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
#define int ll
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define endl '\n'
#define itt set<node>::iterator
#define pii pair<int,int>const int inf = 0x3f3f3f3f;
const int maxn = 5e5 + 5;
int n;
string s, t;
int ans[3005];
int sum;signed main()
{io;cin >> s >> t;n = s.size();sum = 0;for(int i = 0; i < n; ++i){if(s[i] != t[i]){ans[++sum] = i + 1;ans[++sum] = 1;ans[++sum] = i + 1;}}cout << sum << ' ';for(int i = 1; i <= sum; ++i) cout << ans[i] << ' ';return 0;
}

总结

从出题情况来说，很多签到题没人看，没人做，线上比赛比线下比赛的相比，差距很大，有些同学线上比赛没人监督，就随便写两三个题就跑去玩了，这样很不好…