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

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

A题

签到题，题意为初始时乐观之神的勇气值为0，喝一杯鸡尾酒会增加1点勇气值，至少勇气值为10时，乐观之神才会去向女孩表白，乐观之神现在一共喝了7杯鸡尾酒，如果乐观之神表白了，输出“He showed up to confess”，否则输出“He never showed up to confess”，由于$7<10$，因此直接输出“He never showed up to confess”即可。

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

---

B题

知识点：二分，DP

题意总结就是给定$n$个酒馆，每个酒馆有一杯酒精度为$a_i$的的酒，乐观之神必须按照1到$n$的顺序去喝酒，对于第$k$家酒馆，乐观之神可以选择喝，也可以选择不喝，如果不喝那么就必须喝从$k-x$到$k-1$这$x$家酒馆的酒。乐观之神的酒量为$m$，问乐观之神从酒馆1到酒馆$n$，能够使乐观之神喝醉的最小$x$。如果对于任意正整数$x$，乐观之神一定不会醉或者一定会醉，输出-1.

解法：先考虑在给定一个$x$的情况下，假设为$k$，如何求得最小的酒精度之和。可以使用动态规划来求解。定义$dp[i][0/1]$表示酒馆$i$喝酒或者不喝酒能够得到的最小酒精度和，$dp[i][0]$表示不喝第$i$家酒馆能够获得的最小酒精和，$dp[i][1]$表示和第$i$家酒馆的最小酒精和，那么有如下状态转移方程:
$$dp[i][0]=\{\begin{array}{ll}min(dp[i-1-k][1],dp[i-1-k][0])+pre[i-1]-pre[i-1-k]& i-k-1>=0,\\ inf& i-k-1<0.\end{array}$$

$$dp[i][1]=min(dp[i-1][0],dp[i-1][1])+a[i]$$

表达式中的$pre$为前缀和，$O(1)$求得连续$x$家酒馆的酒精和。

初始化：$dp[0][0]=0,dp[0][1]=0$，从$i\ge 1$开始。

这样就求得了给定$x$下走完$n$家酒馆的最小酒精和了。

之后考虑输出-1的情况，显然如果$x=1$时，最小酒精和大于了$m$，或者$x=n$时，最小酒精和小于等于$m$，输出-1.

再看怎样求最小$x$，可以分析出一个性质，$x$越小，那么喝的酒就越少，那么就越不容易醉，那么$x$是单调的，考虑二分$x$，求出最小能够使得乐观之神喝醉的$x$。每次check可以使用DP检查可行性。时间复杂度为$O(n\times \log n)$，因为$x$的上限为$n$。

int DP(int k){vector<vector<int>> dp(n+1,vector<int>(2,inf));//求在k下的最小值dp[0][0]=0,dp[0][1]=0;for(int i=1;i<=n;i++){if(i-1-k<0) dp[i][0]=inf;else dp[i][0]=min(dp[i-1-k][0],dp[i-1-k][1])+pre[i-1]-pre[i-1-k];dp[i][1]=min(dp[i-1][0],dp[i-1][1])+a[i];}return min(dp[n][0],dp[n][1]);
}void solve(){cin >> n >> m;for(int i=1;i<=n;i++){cin >> a[i];pre[i]=pre[i-1]+a[i];}int p=DP(1);if(p>m||pre[n]<=m){cout << -1 << endl;return;}//二分xint l=1,r=n,mid,x;while(l<=r){mid=(l+r)/2;if(DP(mid)<=m){l=mid+1;}else{x=mid;r=mid-1;}}cout << x << endl;
}

---

D题

知识点：分类讨论

看示例很容易明白这道题的做法，就是用$s$表示到了第几个帧，每次分类讨论即可。记得不要开一个数组存前缀和，这样会MLE。时间复杂度为$O(n)$。

void solve(){int n;cin >> n;vector<int> a(n+1);for(int i=1;i<=n;i++){cin >> a[i];}vector<int> ans;int s=1;for(int i=1;i<=n;i++){int e=s+a[i]-1;int t=0;if(s&1){if((e-s+1)%2==0){t=(e-s+2)/2*12+(e-s+1)/2*13;}else{t=(e-s+2)/2*12+(e-s+1)/2*13;}}else{if((e-s+1)%2==0){t=(e-s+2)/2*13+(e-s+1)/2*12;}else{t=(e-s+2)/2*13+(e-s+1)/2*12;}}ans.push_back(t);s+=a[i];}for(int i:ans) cout << i << " ";cout << endl;
}

---

E题

知识点：构造，双指针

先看无解的情况：因为每组至少两个人，所以如果$k\times 2>n$，那么肯定是无解的，输出-1。

构造方法：每次选择最左边和最右边的两个元素组成一组，那么公差为$n-1,n-3,n-5\dots$，用 $l$ 和 $r$ 来表示最左边和最右边的人，我们先考虑组成$k-1$个组，这样需要$2\times (k-1)$个人，剩下$n-2\times (k-1)$构成一个分组，这个分组的公差为1。这样就是一个可行的构造方法。时间复杂度为$O(n)$。

void solve(){int n,k;cin >> n >> k;if(k*2>n){cout << -1 << endl;return;}if(k==1){cout << n << " ";for(int i=1;i<=n;i++) cout << i << " ";cout << endl;return;}int l=1,r=n;for(int i=1;i<k;i++){cout << 2 << " " << l << " " << r << endl;l++,r--;}cout << r-l+1 << " ";for(int i=l;i<=r;i++) cout << i << " ";cout << endl;
}

---

H题

知识点：状压，枚举

题意为给了$n$行$3$列的图，每个字符要么是.或者是#。

上面有颜色的地方就是#，可以看出每种图形要么是3行，要么是2行，那么用一个整数的二进制来表示一个图形。比如：

#..
##.
#..
我们编号为
0 1 2
3 4 5
6 7 8

那么这个图形对应的整数为$2^0+2^3+2^4+2^6=1+8+16+64=89$，这样就可以用一个整数来表示一个图形。我们手动算出每个图形的值，用一个map<int,string>来存储，比如mp[89]="up"。

题目还给出了输入保证只会得到唯一的解码序列，所以我们从上到下依次枚举即可，每次先看2行是否有对应的图形，再看3行，这样保证不会错误。最后提交通过率只有$30.51\%$。不知道为什么。时间复杂度为$O(n)$。

const int maxn=1e5+9;
char g[maxn][3];
int two(int s){int res=0;for(int i=0;i<=1;i++){for(int j=0;j<3;j++){if(g[s+i][j]=='#'){res+=1<<(i*3+j);}}}return res;
}
int three(int s){int res=0;for(int i=0;i<=2;i++){for(int j=0;j<3;j++){if(g[s+i][j]=='#'){res+=1<<(i*3+j);}}}return res;
}
void solve(){int n;cin >> n;for(int i=1;i<=n;i++){for(int j=0;j<3;j++){cin >> g[i][j];}}map<int,string> mp;mp[89]="up";mp[178]="up";mp[90]="LT";mp[180]="LT";mp[154]="down";mp[308]="down";mp[153]="RT";mp[306]="RT";mp[58]="left";mp[54]="A";mp[23]="right";set<int> se;se.insert(89);se.insert(178);se.insert(90);se.insert(180);se.insert(154);se.insert(308);se.insert(153);se.insert(306);se.insert(58);se.insert(54);se.insert(23);int s=1;//表示从这一行去寻找图形vector<string> ans;while(s+1<=n){//每次先看两行int res=two(s);if(se.count(res)){ans.push_back(mp[res]);s+=2;}else{res=three(s);if(se.count(res)){ans.push_back(mp[res]);s+=3;}else{s++;}}}for(string i:ans) cout << i << endl;
}

---

I题

知识点：DP，二分查找

定义$pre[i]$为前$i$种折扣方式中$d_i$的最大值，即$pre[i]=ma{x}_{j=1}^i{d}_j$；定义$suf[i]$为从$i$到$n$这$n-i+1$种中$l_i-d_i$的最小值，即$suf[i]=mi{n}_{j=i}^n(l_i-d_i)$。对$n$种折扣按$l_i$进行升序排序，之后对于每一个$k_j$，先找到第一个大于$k_j$的位置$idx$，那么就有三种购买方式了，不适用折扣方式，使用前面的折扣和使用后面的折扣，我们取最小值即可：
$$ans=min(k_j-pre[idx],k_j,suf[idx+1])$$
当然注意边界情况。时间复杂度为$O((n+q)\times \log n)$，因为有排序和二分查找。

const int maxn=2e5+9;
bool cmp(int val, const pii& p) {return val < p.first;
}
void solve(){int n;cin >> n;vector<pair<int,int>> a(n+1);for(int i=1;i<=n;i++){int l,d;cin >> l >> d;a[i]={l,d};}sort(a.begin()+1,a.end());//维护前缀最大livector<int> pre(n+1,0),suf(n+2,inf);for(int i=1;i<=n;i++){pre[i]=max(pre[i-1],a[i].second);}for(int i=n;i>=1;i--){suf[i]=min(suf[i+1],a[i].first-a[i].second);}int q;cin >> q;while(q--){int k;cin >> k;int idx=upper_bound(a.begin()+1,a.end(),k,cmp)-a.begin()-1;//如果所有元素都小于等于k，那么idx==n，即n是最大的一个元素//如果所有元素都大于k，那么idx==0,即没有比k小的元素if(idx<1){//那么查后缀最小值cout << min(k,suf[idx+1]) << endl;}else if(idx==n){cout << k-pre[idx] << endl;}else{int ans=k;ans=min(ans,k-pre[idx]);ans=min(ans,suf[idx+1]);cout << ans << endl;}}}

---

J题

知识点：数论，快速幂

这道题主要是怎么转化求的表达式。

$$\begin{gathered} a\equiv b\times \lfloor \frac{a}{b}\rfloor +a(\mathrm{mod}b)(\mathrm{mod}P) \\ a-a(\mathrm{mod}b)\equiv b\times \lfloor \frac{a}{b}\rfloor (\mathrm{mod}P) \end{gathered}$$

因为$b$与$P$互质，那么在模$p$的情况下，$b$有乘法逆元$b^{-1}(\mathrm{mod}P)$，那么式子变为：

$\lfloor \frac{a}{b}\rfloor \equiv (a-a(\mathrm{mod}b))\times b^{-1}(\mathrm{mod}P)$，令$a_b\equiv a(\mathrm{mod}b),a_p\equiv a(\mathrm{mod}P)$，我们只需要用快速幂求得每个值即可。时间复杂度为$O({\sum }_{i=1}^n{\log }_2{k}_i)$

int ksm(int base,int p,int mod){int res=1;while(p){if(p&1) res=res*base%mod;base=base*base%mod;p>>=1;}return res;
}void solve(){int n,b,P;cin >> n >> b >> P;//需要求a模p和a模bint a_p=1,a_b=1;for(int i=1;i<=n;i++){int k,p;cin >> p >> k;a_p=a_p*ksm(p,k,P)%P;a_b=a_b*ksm(p,k,b)%b;}int ans=((a_p-a_b)%P+P)*ksm(b,P-2,P)%P;cout << ans << endl;
}

---

K题

知识点：欧几里得算法

给定两个数$a$和$b$，第三个数是为前两个数之差的绝对值，我们发现生成的数和欧几里得算法相似，生成序列的每一个数都是$gcd(a,b)$的倍数，所以让$a=a/gcd(a,b),b=b/gcd(a,b)$，现在$a$和$b$互质，最终序列不同元素个数即为现在的$a$和$b$能够生成的不同数的个数。考虑例子：46 4

23 2 21 19 2 17 15 2 13 11 2 9 7 2 5 3 2 1 1 0 1 1 0

一共产生了14个不同的数，也就是当$a$大于等于$b$时，23可以通过不断减2，可以获得$23/2=11$个数，当$a<b$时，swap(a,b)，这时$a=2,b=1$，可以产生$2/1=2个数$，$b=a\%b=0$，后面都是重复，所以就可以看出如何统计答案了。时间复杂度为$O(log(max(a,b)))$。

int Euclid(int a,int b){int res=1;//最后那一个0while(b!=0){res+=a/b;int t=b;b=a%b;a=t;}return res;
}void solve(){int a,b;cin >> a >> b;if(a==b&&a==0){cout << 1 << endl;return;}int g=__gcd(a,b);a/=g,b/=g;int ans=Euclid(a,b);cout << ans << endl;
}