06-08 20:35 已编辑河北工业大学产品经理发布于天津

关注

部分题题解

2025年夏第九届河北工业大学程序设计校赛题解

前言

K题的数据是我造的，没有考虑最极限的情况，因此让不少暴力都跑了过去，赛时紧急加了一组数据并进行重测，因此给大家造成的不便非常抱歉。（跪）

A.酒鬼地图前传

本题根据真实故事改编

C++代码

void solve()
{
	cout<<"He never showed up to confess";
}

Python代码

print("He never showed up to confess")

PHP代码

He never showed up to confess

B.酒鬼地图

中档题

这道题简单地来说就是给你一个长为 $n$ 的序列和一个值 $m$ ，你需要找到一个最小的 $x$ （或者不存在），使得按照规则去选若干个数，找不到方案使得和小于等于 $m$ ，这里找不到方案即选数的最优方案依旧大于 $m$ 。

规则就是选数必须从左到右选，即从 $a_1$ 到 $a_n$ 并且每连续选了大于等于 $x$ 个数之后，可以不选下一个数。最优的方案就是选出来的数的和最小的方案，假如 $x$ 越小最优的方案是不是就越小呢（ $x$ 越小相当于我不选的限制变宽了）。

由于 $x$ 对答案存在单调性，即假设最终答案是 $x_0$ 那么对于所有 $(x<x_0)$ 的 $x$ 的最优方案都小于等于 $m$ ，对于所有 $(x\geq x0)$ 的 $x$ 的最优方案都大于 $m$ ，所以我们考虑去二分求 $x_0$ 每次只比较当前的 $x$ 下的最优方案跟 $m$ 的大小。

所以当 $x$ 确定的时候，我们可以用动态规划去计算当前的最优方案的值，首先设置状态 $f[i]$ 表示强制不选第 $i$ 个数，前 $i$ 个数里面选的数的和的最大值，假设 $cost(l,r)$ 表示 $a$ 在区间 $[l,r]$ 的区间和动态转移方程就是：

f_i=\min_{j=1}^{i-x-1}(f_j+cost(j,i-1)), \quad (i>x)

对于 $(i \leq x)$ 那就是必选的情况， $f_i=a_1+a_2+......+a_i$

然后我们可以用线段树去动态处理 $\min_{j=1}^{i-x-1}(f_j+cost(j,i-1))$ 这个的值，每次遍历过一个点之后把第 $i$ 个点单点修为 $f[i]$ 并对 $1\sim i$ 上的点在线段树上都加上 $a[i]$ 即可，最后的答案就是

\min_{i=1}^{n}(f_i+cost(i+1,n))

这样做的时间复杂度是 $O(n\log^{2}_{2}n)$ 很明显过不了 $2e5$ 的数据。

我们用前缀和优化一下做法，用假设 $a$ 的前缀和是 $qzh_i$ ，那么动态转移方程可以变成:

\begin{align} \\f_i &=\min_{j=1}^{i-x-1}(f_j+qzh_{i-1}-qzh_{j-1}) \\ &=\min_{j=1}^{i-x-1}(f_j-qzh_{j-1})+qzh_{i-1}, \quad (i>x) \end{align}

那么我们只需要记录前 $(i-x-1)$ 个数的 $(f_j-qzh_{j-1})$ 的最小值即可，这个是可以线性计算的，最后时间复杂度就是 $O(n\log_2n)$ 的。

还有一种比较简单的思路，我们不妨使用以下正难则反的思路去看这道题，实际上相当于我们找出若干个不选的数，然后使它们的和尽量大，这样的话我们的最优方案的值就是总和减去这些不选的数，这样的话我们就可以换一个动态规划的状态设置：令 $f[i]$ 表示强制不选第 $i$ 个数，前 $i$ 个数里面不选的数的和的最大值，动态转移方程：

f_i=\min_{j=1}^{i-x-1}(f_j+a_i), \quad (i>x)

对于 $(i\leq x)$ 的情况就是没有所以 $f_i=0$ 最后求答案就是：

\min_{i=1}^{n}(cost(1,n)-f_i)

这样会比上一种情况好实现一点，其实也差不多时间复杂度 $O(n\log_2n)$ 是一样的，std 用的是这种写法。

#include <cstdio>
#include <algorithm>
#include <iostream>
#define int long long
using namespace std;

int t,n,m,s;
int a[2000006];
int f[2000006];
int qzh[2000006];

bool chk(int mid){
    int i,s,res;
    for(i=1;i<=mid;i++){
        f[i]=0;
    }
    s=0;
    res=qzh[n];
    for(i=mid+1;i<=n;i++){
        f[i]=s+a[i];
        res=min(res,qzh[n]-f[i]);
        s=max(s,f[i-mid]);
    }
    if(res<=m) return true;
    else return false;
}

void slv(){
    int l=1,r=n,mid,res=-1;
    while(l<=r){
        mid=l+r>>1;
        if(chk(mid)){
            l=mid+1;
        }else{
            res=mid;
            r=mid-1;
        }
    }
    cout << res << "\n";
}

signed main(){
    cin >> t;
    int i;
    while(t--){
        cin >> n >> m;
        s=0;
        qzh[0]=0;
        for(i=1;i<=n;i++){
            cin >> a[i];
            if(i&1) s+=a[i];
            qzh[i]=qzh[i-1]+a[i];
        }
        if(s>m) cout << "-1\n";
        else slv();
    }
    return 0;
}

E.等差数列（easy version）

签到题

~~（这题其实跟等差数列没什么关系）~~

因为要求 $k$ 个公差互不相同的等差数列，但是每个等差数列的元素个数至少两个，最简单的思路就是每次取当前剩下的第一个数和最后一个数形成一个等差数列，然后最后剩下一个等差数列就是公差为 $1$ 的等差数列。

假如 $n < 2k$ 那么一定凑不出 $k$ 个等差数列，这种情况无解，输出 $-1$ 就行。

当 $k$ 等于 $1$ 的时候，直接输出 $1\sim n$ 就行。

对于有解的 $n , k \quad (n \geq 2k,k \geq 2)$ 只需要按照如下分法，（一个括号表示一个等差数列）

$(1,n),(2,n-1) \cdots (k-1,n-k+1),(k,k+1,\cdots,n-k)$

这样可以保证每个等差数列的公差不同。

#include <cstdio>
#include <iostream>
using namespace std;
int t,n,k;
int main(){
    scanf("%d",&t);
    int i,j;
    while(t--){
        scanf("%d%d",&n,&k);
        if(n<k*2) printf("-1\n");
        else{
            for(i=1,j=n;i<k;i++,j--){
                printf("2 %d %d\n",i,j);
            }
            printf("%d ",j-i+1);
            while(i<=j){
                printf("%d ",i);
                i++;
            }
            printf("\n");
            
        }
    }
    return 0;
}

F.等差数列（hard version）

偏难题

~~（这题其实跟等差数列也没什么关系）~~

首先题目给出一棵树，树上每个节点都有权值，题意可以理解为，每次给出一个等差数列，只有等差数列上的点可以用，因为一条边只能走一次，所以相当于最后所有选中的点一定在以 $1$ 为端点的一条链上，那么我们不妨以 $1$ 为根去看这棵树。

那么题目就变成了每次求每条从根到叶子节点上的链的最大值，其中链的权值为链上可用的点的权值之和，这样的话，我们就可以每次把答案处理在每一个叶子节点上（无论这个叶子节点是否可用）。

首先我们先树上 dfs 遍历一遍所有叶子节点并且重新编号，根据dfs的顺序去编号叶子节点，使得对于每一个非叶子节点，以 $i$ 为子树的叶子节点的编号一定是连续的。

那么我们在接受询问之前预处理，预处理出每个点 $i$ 以其为根的子树的叶子节点所在区间 $L_i$ 和 $R_i$ ，对于每一个点，假如它可用，则它的作用区间就是 $[L_i,R_i]$ 。

这里我们介绍两种做法：

第一种是时间复杂度比较劣的做法，我们每次对于一次询问，枚举所有可用的点 $i$ ，用线段树做 $[L_i,R_i]$ 上的区间加上 $a_i$ 然后维护区间最大值（实际上只需要查询整个区间的最大值）。

然后我们考虑一下这么的时间复杂度：

对于同一数据点的两次询问，假如 $d$ 相同，那么答案一定是相同的，我们可以用一个数组去记录已经计算过的 $d$ 防止再次计算相同的询问，（或者干脆一次性把所有可能的 $d$ 的答案计算出来），假设这个数据点的树有 $m$ 个叶子节点，那么线段树线段树区间加的时间复杂度是 $O(\log_2m)$ 的。
对于每次数据点的计算前，我们需要对线段树做一个清零操作：如果细节写的不好的话，容易写成整个树进行一次建树，那么单次询问就会 $O(n)$ 的时间复杂度，所以对于两次询问之间的线段树清零不能重新建树，需要利用懒标记区间覆盖，这么做的单次询问清零的时间复杂度接近 $O(1)$ 。
清零之后枚举当前可用的点（点数为 $k=\lceil \frac{n}{d} \rceil$ ），然后每个点都进行一次区间加，最后查询最大值。这样处理的话单次询问的时间复杂度是 $O(k\log_2m)$ 的
对于每一种 $d$ 只会计算一次，当图最劣的情况下形成菊花图此时 $m=n-1$ ，所以总最大时间复杂度为（运用调和级数化简）
$O \left( \sum_{d=1}^{n-1} \lceil \frac{n}{d} \rceil\log_2m \right) < O(\log_2(n-1)\cdot (n\ln(n)+1))$
对于数据给出的 $n \leq 3e5$ 时间限制 $3000ms$ 来说，勉强能跑过，我写的线段树版本跑了 $2300ms$ 左右，我写的常数可能还是太大，可能赛场上会有更好的线段树处理方法，这里先提前期待一下。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#define int long long
using namespace std;

struct rd{
    int y;
    int nxt;
};
rd r[4000005];
struct qj{
    int l;
    int r;
    int s;
};
qj c[4000005];
int h[4000005];
int a[4000005];
int tb[4000005];
int tk[4000005];
int tg[4000005];
int t,n,q,cnt,res;
bool cmp(qj ax, qj ay){
    return ax.l < ay.l;
}
void build(int k,int l,int r){
    tk[k]=tg[k]=0;
    if(l==r) return;
    int mid=l+r>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
}
void addd(int k,int sc){
    if(sc==-1){
        tk[k]=0;
        tg[k]=-1;
    }else{
        if(tg[k]==-1){
            addd(k<<1,tg[k]);
            addd(k<<1|1,tg[k]);
            tg[k]=0;
        }
        tg[k]+=sc;
        tk[k]+=sc;
    }
}
void push_down(int k){
    if(tg[k]==0) return;
    addd(k<<1,tg[k]);
    addd(k<<1|1,tg[k]);
    tg[k]=0;
}
void update(int k){
    tk[k]=max(tk[k<<1],tk[k<<1|1]);
}
void modify(int k,int l,int r,int x,int y,int sc){
    if(tg[k]==-1) push_down(k);
    if(x<=l&&r<=y) return addd(k,sc);
    int mid=l+r>>1;
    push_down(k);
    if(x<=mid) modify(k<<1,l,mid,x,y,sc);
    if(y>mid) modify(k<<1|1,mid+1,r,x,y,sc);
    update(k);
}
void add(int ax,int ay){
    r[++cnt].y=ay;
    r[cnt].nxt=h[ax];
    h[ax]=cnt;
}
void dfs(int k,int fa){
    int i,j,flg=0;
    c[k].s=a[k];
    for(i=h[k];i!=0;i=r[i].nxt){
        j=r[i].y;
        if(j==fa) continue;
        flg=1;
        dfs(j,k);
        if(!c[k].l){
            c[k].l=c[j].l;
            c[k].r=c[j].r;
        }else{
            c[k].l=min(c[k].l,c[j].l);
            c[k].r=max(c[k].r,c[j].r);
        }
    }
    if(!flg) c[k].l=c[k].r=++res;
}
void slv(int d){
    if(tb[d]){
        cout << tb[d] << "\n";
        return;
    }
    int i;
    tk[1]=0;
    tg[1]=-1;
    for(i=1;i<=n;i+=d){
        modify(1,1,res,c[i].l,c[i].r,c[i].s);
    }
    tb[d]=tk[1];
    cout << tk[1] << "\n";
}
signed main(){
    ios::sync_with_stdio(false);
    cin >> t;
    int i,ax,ay,d;
    while(t--){
        cin >> n >> q;
        cnt=0;
        res=0;
        for(i=1;i<=n;i++){
            cin >> a[i];
            h[i]=0;
            tb[i]=0;
            c[i].l=c[i].r=c[i].s=0;
        }
        for(i=1;i<n;i++){
            cin >> ax >> ay;
            add(ax,ay);
            add(ay,ax);
        }
        dfs(1,0);
        build(1,1,res);
        for(i=1;i<=q;i++){
            cin >> d;
            slv(d);
        }
    }
    return 0;
}

第二种做法就比第一种好很多，线段树做法的不足之处在于，对于一次询问，时间复杂度里的 $m$ 是不可控因素，对于叶子节点数量特别多的图，可用点数特别少的询问，跑出来的效率就低。那么我们可以换一种方法去想这个问题，假如我们预处理出所有点的区间之后，对于每次询问，我们相当于有 $k$ 条可用线段（ $k=\lceil \frac{n}{d} \rceil$ ），我们需要寻找一个点，使得覆盖这个点的所有线段的权值总和最大：

首先我们先把可用的 $k$ 条线段拿出来，按照左端点排序，然后从左到右枚举所有线段，相当于一个从左到右的扫描线去扫描所有点，但是位于两个端点之间的所有点的值是一样的，所以我们只需要看端点的值就行了。
这里运用优先队列（小根堆）去存当前同时存在的线段。每次加入这个线段到时候要把右端点比这个线段小的已经加入的线段删除，然后小根堆按照线段的右端点为第一关键字排列，对每个端点的值取一个 $\max$ 。
这样子做的话对于单次询问，时间复杂度就只与 $k$ 有关，总的时间复杂度就是
$O \left( \sum_{d=1}^{n-1} \lceil \frac{n}{d} \rceil \cdot \log_2\lceil \frac{n}{d} \rceil \right)$
比线段树做法优，而且实现上也简单一点，（就是可能难想一点？），但是实际上最长的时间也跑了 $1100ms$ 左右。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#define int long long
using namespace std;

struct rd{
    int y;
    int nxt;
};
rd r[2000005];
struct qj{
    int l;
    int r;
    int s;
};
qj c[2000005];
qj f[2000005];
int h[2000005];
int a[2000005];
int tb[2000005];
int t,n,q,cnt,res;
bool cmp(qj ax, qj ay){
    return ax.l < ay.l;
}
void add(int ax,int ay){
    r[++cnt].y=ay;
    r[cnt].nxt=h[ax];
    h[ax]=cnt;
}
void dfs(int k,int fa){
    int i,j,flg=0;
    c[k].s=a[k];
    for(i=h[k];i!=0;i=r[i].nxt){
        j=r[i].y;
        if(j==fa) continue;
        flg=1;
        dfs(j,k);
        if(!c[k].l){
            c[k].l=c[j].l;
            c[k].r=c[j].r;
        }else{
            c[k].l=min(c[k].l,c[j].l);
            c[k].r=max(c[k].r,c[j].r);
        }
    }
    if(!flg) c[k].l=c[k].r=++res;
}
void slv(int d){
    if(tb[d]){
        cout << tb[d] << "\n";
        return;
    }
    int i,j,m=0,ans=0,ms=0;
    for(i=1;i<=n;i+=d){
        f[++m]=c[i];
    }
    sort(f+1,f+m+1,cmp);
    priority_queue < pair<int,int> > st;
    st.push(make_pair(-f[1].r,f[1].s));
    ms=f[1].s;
    ans=f[1].s;
    pair <int,int> k;
    for(i=2;i<=m;i++){
        while(!st.empty()){
            k=st.top();
            if(-k.first>=f[i].l) break;
            ms-=k.second;
            st.pop();
        }
        ms+=f[i].s;
        ans=max(ans,ms);
        st.push(make_pair(-f[i].r,f[i].s));
    }
    tb[d]=ans;
    cout << ans << "\n";
}
signed main(){
    ios::sync_with_stdio(false);
    cin >> t;
    int i,ax,ay,d;
    while(t--){
        cin >> n >> q;
        cnt=0;
        res=0;
        for(i=1;i<=n;i++){
            cin >> a[i];
            h[i]=0;
            tb[i]=0;
            c[i].l=c[i].r=c[i].s=0;
        }
        for(i=1;i<n;i++){
            cin >> ax >> ay;
            add(ax,ay);
            add(ay,ax);
        }
        dfs(1,0);
        for(i=1;i<=q;i++){
            cin >> d;
            slv(d);
        }
    }
    return 0;
}

J.昨天看见个题

首先，我们不考虑 $a$ 的计算，只考虑对于一个大整数 $x$ ， $\left \lfloor \dfrac{x}{b} \right \rfloor$ 对 $P$ 取模如何处理。有

\begin{align} \left \lfloor \frac{x}{b} \right \rfloor \bmod \ P &= \frac {(x - x \bmod b)}{b} \bmod P \\ \\ &= (x - x \bmod b) \times inv(b) \bmod P \end{align}

因此只需要得到 $a \bmod P$ 和 $a \bmod b$ 的值即可，再用快速幂得到 $a$ 的值和 $inv(b)$ 的值即可。

本题保证了 $\gcd(b , P) = 1$ 且 $P$ 为质数，求逆元时应用费马小定理即可。

#defint int long long
int p[N], k[N];
int quick_power(int a, int n, int mod)
{
	if (a == 0)
		return 0;
	int ans = 1;
	while (n)
	{
		if (n % 2)
			ans = ans * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return ans % mod;
}
void solve()
{
	int n, b, P;
	cin >> n >> b >> P;

	int res1 = 1, res2 = 1;
	int invb = quick_power(b, P - 2, P);
	for (int i = 1; i <= n; ++i)
	{
		cin >> p[i] >> k[i];
		res1 = res1 * quick_power(p[i], k[i], P) % P;
		res2 = res2 * quick_power(p[i], k[i], b) % b;
	}
	cout << ((res1 - res2) % P + P) % P * invb % P << endl;
}

K.昨天想了个题

根据题意知道，后一项为前两项差的绝对值，可以想到求 $\gcd$ 的辗转相减，所以该序列到最后一定会到 x x 0 x x 0 ... 结束，即不存在无解的情况。故 $a$ 序列本质上是一个利用辗转相减法求最大公约数的过程。考虑如何计算答案。假设两个数 $n < m$ ，那么通过若干次操作后使得 $n > m'$ ，这过程中 $m$ 一直减少，故在这过程中操作次数即为出现的不同的数的个数。

#define int long long
int ans = 0;
int gcd(int a, int b)
{
	if (b == 0)
		return a;
	ans += a / b;
	return gcd(b, a % b);
}

void solve()
{
	int a, b;
	ans = 0;
	cin >> a >> b;
	gcd(a, b);
	cout << ans + 1 << endl;
}

M.不玩舞萌

很简单的计算几何，算出直线和圆的交点，简单推导如下：

设直线由两点 $A$ 和 $B$ 确定，圆心为 $C$ ，半径为 $r$ 。做出点 $C$ 在直线 $AB$ 上的投影 $P$ ( $\vec{AB} \cdot \vec{PC} =0$ ) 。

投影 $P$ ：

P = A + \vec{AB} \cdot \frac{(C - A) \cdot \vec{AB}}{|\vec{AB}|^2}

算出垂足 $P$ 和圆心 $C$ 的距离 $d$ 、垂足 $P$ 和交点 $P_1$ 的距离 $x$ ：

d = |P - C|, \quad x = \sqrt{r^2 - d^2}

两个交点：

\vec{e} = \frac{\vec{AB}}{|\vec{AB}|}, \quad P_1 = P + \vec{e} \cdot x, \quad P_2 = P - \vec{e} \cdot x

由于此题保证 $vt<r$ ，因此圆和直线一定会有两个交点。

alt

const double PI = acos(-1.0);
struct point
{
	double x, y;
};

typedef point Vector;
struct circle
{
	point p;
	double r;
};
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}; }
point operator*(point a, double t) { return point{a.x * t, a.y * t}; }
point operator/(point a, double t) { return point{a.x / t, a.y / t}; }
point operator*(double t, point a) { return point{a.x * t, a.y * t}; }
double dot(point a, point b) { return a.x * b.x + a.y * b.y; }
point rotate(point a, double altha) { return point{a.x * cos(altha) - a.y * sin(altha), a.x * sin(altha) + a.y * cos(altha)}; }

pair<point, point> Intersection_line_circle(point A, point B, circle c)
{
	Vector AB = B;
	Vector pr = A + AB * (dot((c.p - A), AB) / dot(AB, AB));
	double base = sqrt(c.r * c.r - dot((pr - c.p), (pr - c.p)));
	Vector e = AB * (1.0 / sqrt(dot(AB, AB)));
	return make_pair(pr - e * base, pr + e * base);
}

void solve()
{
	double r, th, w, v, t;
	double d[5] = {0, 0.2, 0.4, 0.6, 0.8};
	cin >> r >> th >> w >> v >> t;
	th = th / 360 * 2 * PI, w = w / 360 * 2 * PI;
	double del = w * t, s = v * t; // 旋转的弧度和走过的距离
	point a = rotate({s, 0}, th);
	circle c = {{0, 0}, r};
	for (int i = 0; i <= 4; ++i)
	{
		Vector V = rotate({0, 1}, fmod(d[i] * 2 * PI + del, 2 * PI));
		point ans = Intersection_line_circle(a, V, c).se;
		cout << fixed << setprecision(12) << ans.x << " " << ans.y << endl;
	}
}