2025年冬第十届河北工业大学程序设计校赛题解
前言
由于负责出题的几个人近期都在准备区域赛，这次校赛准备的时间比较仓促，校赛当中出现的许多锅向大家道歉。这次校赛的所有数据都是我造的，B题造数据的时候没有考虑到最极限的情况，导致很多暴力解法通过，J题则是 std 写错了，赛时紧急修复数据并重测了。
A.欢迎
输出一个字符串即可
C++代码
void solve()
{
cout<<"I have read and agreed to the testing protocol.";
}
PHP代码
I have read and agreed to the testing protocol.
B.递归缩写
先从原字符串当中提取出缩写词，问题就是从原字符串中是否找到一个字串，使得这个字串能和缩写词相等。这是一个经典的 KMP 模板题。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
int t,n;
string s;
int p[2000005];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> t;
int i,j,flg;
while(t--){
cin >> n >> s;
string ch="";
for(i=0;i<n;i++){
if(s[i]>='a'&&s[i]<='z') s[i]-='a'-'A';
}
ch+=s[0];
for(i=1;i<n;i++){
if(s[i]=='_'&&i+1<n) ch+=s[i+1];
}
for(i=0;i<n;i++) p[i]=-1;
p[0]=-1;
for(i=0,j=-1;i<ch.size()-1;i++){
while(j!=-1&&s[j+1]!=s[i+1]) j=p[j];
if(s[i+1]==s[j+1]) j++;
p[i+1]=j;
}
flg=0;
for(i=-1,j=-1;i<n-1;i++){
while(j!=-1&&s[i+1]!=ch[j+1]) j=p[j];
if(s[i+1]==ch[j+1]) j++;
if(j==ch.size()-1){
flg=1;
break;
}
}
if(flg) cout << "Yes\n" << ch << "\n";
else cout << "No\n";
}
return 0;
}
C.对合和逆转
fun fact：一开始这个题的输出是一个可行的排列就可以，后来改成了输出字典序最小的排列。
首先题目给出了对合排列的定义，我们需要先对对合排列的性质进行分析。
我们令 因为对合排列具有可逆性，即
对于每一个 都有
，
再根据
得出对于所有的
都有
即 同理有
我们令
代换得
也就是说两个位置的值是两两对应的。
根据这样的性质我们会发现，整个序列是由一个从小到大的为 到
的排列，进行了若干次，无重复元素的二元组
的交换操作，每次交换
并且每个位置至多只会被交换一次。
接下来我们需要对第二个限制，逆序对进行分析。根据刚才的分析，题目被我们简化为，进行若干次交换的操作，使得每个位置至多被交换一次并且最后的序列逆序对个数为 并且使得字典序最小。
我们考虑上界跟下界问题，合法的 的最小值应该为
（不进行交换），最大值为
（把整个序列倒过来）
然后再来考虑 在这个范围内的值是否都能取到。
我们考虑一个状态： 表示当前有一个长度为
的原排列并且需要进行若干次操作使得逆序对的个数为
。
先考虑第一个位置的数是否进行交换，与谁交换，会产生什么价值：
-
假如不进行交换，那么状态会转移到
。
-
假如与
进行交换，产生的逆序对个数为：
然后剩下
个数的相对大小不变，相当于把
和
右边的数都整体减一。状态就转移到
为什么可以相当于把这两个数删去呢？
因为交换完之后 右边的数无论怎么改变都不会影响
产生的逆序对个数，并且，对于
之间的数都大于
所以
的数无论怎么交换也不会影响
产生的逆序对个数。
那么我们的逆序对个数将会由若干次交换产生，假设当前第 次与当前的
交换的是
那么将产生
个逆序对，也就是需要
次操作使得：
需要注意的是对某次状态为 来说
是一个范围在
之间的奇数。
考虑一个状态 是否有解：假如
为奇数并且小于等于
那么一定有解，否则进入到状态
中，临界状态为
或
的情况。
-
时只有两种情况
或
-
时有
四种情况，
均有解，特殊情况是
这种情况是无解的。
因此我们在向后推状态的时候不能使得最后变成 的场面，实际上需要考虑的情况是，当前状态
选跟哪个点交换的时候，如果
即如果不选最后一个就进入无解状态的时候，这种状态我们称为非自由状态（因为不能自由选择跟谁交换了），如果一个状态经历若干个非自由状态进入到
那么这个状态也会无解。因此我们在每个自由态去选择跟谁交换的时候需要额外判断下一个状态是否为无解状态。那么初始为无解的状态即为当
为奇数并且
时无解，否则一定有解。
接下来考虑怎么做到使字典序最小，在每次自由态的时候，在满足不进入无解状态的前提下，能不换就不换，否则就换最近的点即可。具体实现可以用线段树上二分维护某些被选的点删除了之后，当前的第 个点是原序列的第几个点。
时间复杂度
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#define int long long
using namespace std;
int t,n,k;
int a[2000005];
struct trs{
int s[5000005];
void update(int k){
s[k]=s[k<<1]+s[k<<1|1];
}
void build(int k,int l,int r){
if(l==r){
s[k]=1;
return;
}
int mid=l+r>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
update(k);
}
void chg(int k,int l,int r,int x,int y){
if(l==r){
s[k]+=y;
return;
}
int mid=l+r>>1;
if(x<=mid) chg(k<<1,l,mid,x,y);
else chg(k<<1|1,mid+1,r,x,y);
update(k);
}
int qry(int k,int l,int r,int x){
if(l==r) return l;
int mid=l+r>>1;
if(s[k<<1]>=x) return qry(k<<1,l,mid,x);
return qry(k<<1|1,mid+1,r,x-s[k<<1]);
}
};
trs tk;
void init(){
cin >> n >> k;
int i;
for(i=1;i<=n;i++) a[i]=i;
}
int chk(int x,int mid){
if(x==mid) return 0;
int c=mid-x+1;
return (c-1)*2-1;
}
void clc(){
int x=1,res=k;
while(x<=n){
int fc=tk.qry(1,1,n,1);
if(x>=n){
tk.chg(1,1,n,fc,-1);
break;
}
int c=n-x+1;
if((c-1)*(c-2)/2>=res){
if(c%2==0&&res==(c-1)*(c-2)/2-1){
;
}else{
tk.chg(1,1,n,fc,-1);
x++;
continue;
}
}
int l=2,r=c,mid,f=c;
while(l<=r){
mid=l+r>>1;
if(res-chk(1,mid)<=max(0ll,(c-2)*(c-3)/2)){
f=mid;
r=mid-1;
}else l=mid+1;
}
if(c%2==1&&res-chk(1,f)==(c-2)*(c-3)/2-1) f++;
int f2=tk.qry(1,1,n,f);
swap(a[fc],a[f2]);
tk.chg(1,1,n,fc,-1);
tk.chg(1,1,n,f2,-1);
x+=2;
res-=chk(1,f);
}
}
void slv(){
if(k>(n-1)*n/2||(n%2==1&&k==(n-1)*n/2-1)){
cout << "-1\n";
return;
}
tk.build(1,1,n);
clc();
int i;
for(i=1;i<=n;i++) cout << a[i] << " ";
cout << "\n";
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> t;
while(t--){
init();
slv();
}
return 0;
}
D.连线
fun fact：在写 std 之前还以为这是道简单的签到题。
讲一种思路：
注意到 的取值范围只能是
不能更大或者更小。
的情况很好想到，当三个点的横坐标都相等或者三个点的纵坐标都相等的时候，直接用一条线段链接。 在这里我假设横坐标都相等，该线段的两个纵坐标则分别是
和
。
的时候情况比较特殊，有且仅有两个点横坐标或者纵坐标相等，第三个点不在这两个点“中间”的时候。拿出其中一种情况，当
且
的时候，当且仅当
的时候，最少可以有
个线段可以覆盖所有点。
且
的时候同理。
的时候有两种情况，一种是上面没提到的有且仅有两个点横坐标或者纵坐标相等，第三个点在这两个点中间的时候。一种是三个点的横纵坐标都不相同。先说第一种情况，题目中并没有说折线段不能够重叠，一种可行的构造方案是构造出一个 “T” 字型折线段（如下图所示）。第二种情况可以把三个点按照横坐标排序，从左到右链接三个点即可。
这个题还有爆搜等其他做法，这里就不细讲了。
void solve()
{
int ax, ay, bx, by, cx, cy;
cin >> ax >> ay >> bx >> by >> cx >> cy;
if (ax == bx && ax == cx)
{
cout << 1 << endl;
cout << ax << " " << min({ay, by, cy}) << endl;
cout << ax << " " << max({ay, by, cy}) << endl;
return;
}
else if (ay == by && ay == cy)
{
cout << 1 << endl;
cout << min({ax, bx, cx}) << " " << ay << endl;
cout << max({ax, bx, cx}) << " " << ay << endl;
return;
}
int f = false;
if (ax == cx)
f = 1, swap(bx, cx), swap(by, cy);
if (bx == cx)
f = 1, swap(ax, cx), swap(ay, cy);
if (ax == bx)
f = 1;
if (ax == bx && f)
{
if (cy <= min(ay, by))
{
cout << 2 << endl;
cout << cx << " " << cy << endl;
cout << ax << " " << cy << endl;
cout << ax << " " << max(ay, by) << endl;
}
else if (cy >= max(ay, by))
{
cout << 2 << endl;
cout << cx << " " << cy << endl;
cout << ax << " " << cy << endl;
cout << ax << " " << min(ay, by) << endl;
}
else
{
cout << 3 << endl;
cout << cx << " " << cy << endl;
cout << ax << " " << cy << endl;
cout << ax << " " << ay << endl;
cout << ax << " " << by << endl;
}
return;
}
f = false;
if (ay == cy)
f = 1, swap(bx, cx), swap(by, cy);
if (by == cy)
f = 1, swap(ax, cx), swap(ay, cy);
if (ay == by)
f = 1;
if (ay == by && f)
{
if (cx <= min(ax, bx))
{
cout << 2 << endl;
cout << cx << " " << cy << endl;
cout << cx << " " << ay << endl;
cout << max(ax, bx) << " " << ay << endl;
}
else if (cx >= max(ax, bx))
{
cout << 2 << endl;
cout << cx << " " << cy << endl;
cout << cx << " " << ay << endl;
cout << min(ax, bx) << " " << ay << endl;
}
else
{
cout << 3 << endl;
cout << cx << " " << cy << endl;
cout << cx << " " << ay << endl;
cout << ax << " " << ay << endl;
cout << bx << " " << by << endl;
}
return;
}
vector<pair<int, int>> v;
v.push_back({ax, ay}), v.push_back({bx, by}), v.push_back({cx, cy});
sort(v.begin(), v.end());
cout << 3 << endl;
cout << v[0].first << " " << v[0].second << endl;
cout << v[0].first << " " << v[1].second << endl;
cout << v[2].first << " " << v[1].second << endl;
cout << v[2].first << " " << v[2].second << endl;
}
E.未读事项
这个题可以二分 + 线段树，也可以在线段树上二分，两种时间复杂度都能接受。讲一种二分 + 线段树的做法，把设置已读看做区间覆盖 ，把设置未读看做区间覆盖
，查询则是在区间
中用区间查询求出
的个数记作
，然后找到一个最大的
使得
，这个东西具有单调性，直接二分求出
。
整体时间复杂度是
。
#include <bits/stdc++.h>
#define endl '\n'
#define lc p << 1
#define rc p << 1 | 1
const int N = 2e5;
using namespace std;
struct node
{
int l, r, lazy, sum;
} tr[N * 4];
void pushup(int p)
{
tr[p].sum = tr[lc].sum + tr[rc].sum;
}
void pushdown(int p)
{
if (tr[p].lazy == 1)
{
tr[lc].sum = tr[lc].r - tr[lc].l + 1;
tr[rc].sum = tr[rc].r - tr[rc].l + 1;
tr[lc].lazy = tr[rc].lazy = 1;
}
else if (tr[p].lazy == 0)
{
tr[lc].sum = 0;
tr[rc].sum = 0;
tr[lc].lazy = tr[rc].lazy = 0;
}
tr[p].lazy = -1;
}
void build(int p, int l, int r)
{
tr[p] = {l, r, -1, 0};
if (l == r)
return;
int mid = (l + r) >> 1;
build(lc, l, mid);
build(rc, mid + 1, r);
}
int query(int p, int x, int y)
{
if (x <= tr[p].l && tr[p].r <= y)
return tr[p].sum;
int m = tr[p].l + tr[p].r >> 1;
pushdown(p);
int sum = 0;
if (x <= m)
sum += query(lc, x, y);
if (y > m)
sum += query(rc, x, y);
return sum;
}
void update(int p, int x, int y, int op)
{
if (x <= tr[p].l && tr[p].r <= y)
{
tr[p].sum = (tr[p].r - tr[p].l + 1) * op;
tr[p].lazy = op;
return;
}
pushdown(p);
int m = tr[p].l + tr[p].r >> 1;
if (x <= m)
update(lc, x, y, op);
if (y > m)
update(rc, x, y, op);
pushup(p);
}
void solve()
{
int n, q;
cin >> n >> q;
build(1, 1, n);
while (q--)
{
string op;
cin >> op;
if (op[4] == 'R') // SET_READ
{
int l, r;
cin >> l >> r;
update(1, l, r, 1);
}
else if (op[4] == 'U') // SET_UNREAD
{
int l, r;
cin >> l >> r;
update(1, l, r, 0);
}
else if (op[4] == 'T') // FIRST_UNREAD_SINCE
{
int x;
cin >> x;
int tot = (n - x + 1) - query(1, x, n); // number of 0
if (tot == 0)
{
cout << "None" << endl;
continue;
}
int l = x - 1, r = n + 1;
while (l + 1 < r)
{
int mid = (l + r) >> 1;
int res = (n - mid + 1) - query(1, mid, n);
if (res == tot)
l = mid;
else
r = mid;
}
cout << l << endl;
}
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while (T--)
solve();
return 0;
}
F.极速冷却
一个细节比较多的多源 bfs ，具体实现的时候不能实时更新图格的状态，必须要确定水和熔岩都会“待流入”哪些图格，再去更新每个图格的状态。具体实现请看代码，代码时间复杂度 。
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef pair<int, int> pii;
const int N = 1e3 + 50;
char c[N][N];
int vis[N][N];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
struct node
{
int x, y, life;
};
void solve()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
vis[i][j] = 0;
queue<node> w, l;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
cin >> c[i][j];
if (c[i][j] == 'W')
w.push({i, j, 7}), vis[i][j] = 1;
else if (c[i][j] == 'L')
l.push({i, j, 7}), vis[i][j] = 1;
}
}
while (!w.empty() || !l.empty())
{
set<pii> st;
vector<node> vw, vl;
while (!w.empty())
{
auto [x, y, life] = w.front();
w.pop();
for (int i = 0; i < 4; ++i)
{
int xx = x + dx[i];
int yy = y + dy[i];
if (xx < 1 || xx > n || yy < 1 || yy > m || vis[xx][yy])
continue;
vw.push_back({xx, yy, life - 1}), st.insert({xx, yy});
}
}
while (!l.empty())
{
auto [x, y, life] = l.front();
l.pop();
for (int i = 0; i < 4; ++i)
{
int xx = x + dx[i];
int yy = y + dy[i];
if (xx < 1 || xx > n || yy < 1 || yy > m || vis[xx][yy])
continue;
vl.push_back({xx, yy, life - 1});
if (st.count({xx, yy}))
c[xx][yy] = 'S', vis[xx][yy] = 1;
}
}
for (auto [x, y, life] : vw)
{
vis[x][y] = 1;
if (c[x][y] == '.')
{
c[x][y] = 'W';
if (life)
w.push({x, y, life});
}
}
for (auto [x, y, life] : vl)
{
vis[x][y] = 1;
if (c[x][y] == '.')
{
c[x][y] = 'L';
if (life)
l.push({x, y, life});
}
}
}
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
cout << c[i][j];
cout << endl;
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T = 1;
cin >> T;
while (T--)
solve();
return 0;
}
G.别样的纸牌 (?) 游戏 II
记初始数组的最大值为 ，所有数的最大公约数为
。把白板上目前的数当作集合
（去重后计数为
）。考虑集合在“任取两数相减并加入正差”下的闭包：
-
任取两数相减并反复进行，能得到的最小正整数等于初始数的 gcd，因此闭包中最小正元为
；所有新产生的数必是
-
当
都在集合中时，可以用
、再用
……反复相减得到所有不超过
元素个数为
。
因此游戏中一共可以写出的不同正整数总数为 ，当前已经有的不同数为
，还可以写的合法新数数目为
双方轮流写新数，不能写时输，所以胜负由剩余可写步数的奇偶决定：
- 若
为奇数，先手（Sente）最后拿到最后一步，先手必胜；
- 若
void solve()
{
int n, d, mx = 0;
set<int> st;
cin >> n;
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
if (i == 1)
d = a[1];
else
d = gcd(d, a[i]);
st.insert(a[i]);
mx = max(mx, a[i]);
}
if ((mx / d - st.size()) % 2 == 1)
cout << "Sente" << endl;
else
cout << "Gote" << endl;
}
H. 多次元宇宙融合论与测试扩充计划
能够走到编号为 的房间的前提是控制编号
房间的按钮全部被按下，考虑建有向图跑拓扑排序。只不过这个拓扑排序只把编号为
的房间压入队列。最后，房间编号
的入度为
的时候即为有解，否则无解。
vector<int> e[N];
int p[N], d[N], in[N], out[N], vis[N];
void solve()
{
int n, m;
cin >> n >> m;
for (int i = 0; i <= n + 1; ++i)
in[i] = out[i] = vis[i] = 0, e[i].clear();
for (int i = 1; i <= m; ++i)
cin >> p[i];
for (int i = 1; i <= m; ++i)
cin >> d[i];
for (int i = 1; i <= m; ++i)
{
e[p[i]].push_back(d[i]);
out[p[i]]++, in[d[i]]++;
cerr << p[i] << " " << d[i] << endl;
}
queue<int> q;
q.push(0), vis[0] = 0;
while (!q.empty())
{
int u = q.front();
if (u == n + 1)
return (void)(cout << "YES" << endl);
vis[u] = 1, q.pop();
for (int v : e[u])
{
if (vis[v])
continue;
in[v]--;
if (!in[v])
q.push(v);
}
}
cout << "NO" << endl;
}
I.多次元宇宙融合论与测试扩充计划（续）
题面有点没说清楚，这个题的简化题意就是：输入是 lca(i,j) ，输出则是输出每个点的父亲。这个题做法很多，可以跑拓扑排序，可以直接观察矩阵得出一个性质。这个性质就是：一个深度是 的结点
（这里假设根节点的深度是
），这个结点
一定有
个祖先。我们就可以求出每个结点的深度以及它的所有祖先。把结点
的所有祖先按照深度排序，深度等于
的结点就是结点
的父亲。下面代码的时间复杂度是
。
vector<int> v[N];
int dep[N], ans[N];
void solve()
{
int n;
cin >> n;
for (int i = 1; i <= n; ++i)
v[i].clear(), dep[i] = ans[i] = 0;
for (int i = 1; i <= n; ++i)
{
set<int> st;
for (int j = 1; j <= n; ++j)
{
int a;
cin >> a;
st.insert(a);
}
dep[i] = st.size();
for (int j : st)
v[i].push_back(j);
}
for (int i = 1; i <= n; ++i)
{
sort(v[i].begin(), v[i].end(), [&](int x, int y)
{ return dep[x] < dep[y]; });
if (v[i].size() >= 2)
ans[i] = v[i][v[i].size() - 2];
}
for (int i = 1; i <= n; ++i)
cout << ans[i] << " ";
cout << endl;
}
J. 超乎寻常的重力
体块为顶底面相同的直棱柱且质量均匀，整体质心就是底面凸多边形的面积重心。绕固定点自由转动，重力作用下静止时质心必须正好处在固定点的竖直下方（即质心的向量相对于固定点指向“向下”方向）。因此问题归结为：把多边形绕给定固定点旋转一个角度，使得多边形的面积重心在旋转后位于固定点的正下方（ 坐标与固定点相同，且在其下方）。
这里给出多边形（质量分布均匀）的重心公式，（ 代表多边形的面积 ）：
以及向量旋转的公式： ，
表示逆时针旋转的弧度。
#include <bits/stdc++.h>
#define double long double
#define endl '\n'
using namespace std;
const int N = 2e5 + 50;
const double eps = 1e-9;
struct point
{
double x, y;
};
typedef point Vector;
int n;
point p[N];
bool operator==(point a, point b) { return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0; }
point operator+(point a, point b) { return point{a.x + b.x, a.y + b.y}; }
point operator-(point a, point b) { return point{a.x - b.x, a.y - b.y}; }
double cross(point a, point b) { return a.x * b.y - a.y * b.x; }
double dot(point a, point b) { return a.x * b.x + a.y * b.y; }
double len(Vector a) { return sqrt(dot(a, a)); }
point rotate(point a, double altha) { return point{a.x * cos(altha) - a.y * sin(altha), a.x * sin(altha) + a.y * cos(altha)}; }
double angle(Vector a, Vector b) { return acos(dot(a, b) / len(a) / len(b)); }
int nxt(int x) { return x == n ? 1 : x + 1; };
int pre(int x) { return x == 1 ? n : x - 1; };
void solve()
{
point P, Q;
cin >> n;
cin >> P.x >> P.y;
Q = P, Q.y -= 1;
for (int i = 1; i <= n; ++i)
{
int x, y;
cin >> x >> y;
p[i] = {(double)x, (double)y};
}
double A = 0;
for (int i = 1; i <= n; ++i)
A += cross(p[i], p[nxt(i)]);
A = fabs(A);
double ansx = 0, ansy = 0;
point C;
for (int i = 1; i <= n; ++i)
ansx += (p[i].x + p[nxt(i)].x) * cross(p[i], p[nxt(i)]);
for (int i = 1; i <= n; ++i)
ansy += (p[i].y + p[nxt(i)].y) * cross(p[i], p[nxt(i)]);
C = {ansx / 3 / A, ansy / 3 / A};
double ang = angle(Q - P, C - P);
if (cross(Q - P, C - P) > 0)
ang = -ang;
cout << fixed << setprecision(12);
for (int i = 1; i <= n; ++i)
{
point res = P + rotate(p[i] - P, ang);
cout << res.x << " " << res.y << endl;
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while (T--)
solve();
return 0;
}
K.一次性密码本
把字母映射为数字 。设输入的两条长度为
的大写字符串为
和
。题目说明二者中一条是密文
，另一条是密钥（长度为
的密钥按周期重复得到的长为
的序列）——但不知道哪一条是哪一种。由维吉尼亚（模
加法）定义，若已知密文
与密钥
，明文
的每一位为
因此只需对两种可能做一次模 相减，得到两个候选明文：
- 假设
是密文、
是密钥：
；
- 假设
。
题目允许输出任意一个满足条件的明文，所以任选上面两个中的任意一个输出。
void solve()
{
int n;
cin >> n;
string a, b;
cin >> a >> b;
for (int i = 0; i < n; ++i)
cout << (char)('A' + ((b[i] - a[i] + 26) % 26));
cout << endl;
}
结语
感谢来参加我们的校赛！
投递百度等公司7个岗位