HDU 2025“钉耙编程”中国大学生算法设计春季联赛（5）（补题）， 含（6）、（7） 题解链接
1001小凯逛超市
题意：选择n种商品，每种商品可无限选择，第 i 种商品价值为gi，体积都是1，你需要输出在总价格不超过v的前提下填满m背包的方案数，答案 % 1e9+7。
输入：有 T 组数据，1≤T≤5 , 1≤n,m,V,gi≤400 。
输出：对于每组数据，输出一个数 ans， 表示方案数取模之后的值。
思路：完全背包问题，定义f[ j ][ k ] : 达到总价格为j ，体积为k的总方案数
初始化：memset( f,0,sizeof(f) ) , f[0][0]=1
转移方程：f[ j ][ k ] = f[ j ][ k ]+f[ j - x ][k – 1] (x:当前商品的价值)
计算答案Ans : for(int i=1;i<=v;i++) ans=(ans+f[ v ][ m ])%M。
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=500,M=1e9+7;
int f[N][N];
signed main(){
int T;
cin >> T;
int n,m,v,x;
while(T--){
cin >> n >> m >> v;
memset( f,0,sizeof(f) ); //初始化动态数组
f[0][0]=1; // 初始化不选任何物品且价值为 0 的方案数为 1
for(int i=1;i<=n;i++){
cin >> x;
for(int j=x;j<=v;j++){ //选取物品的总价值
for(int k=1;k<=m;k++){ //选取物品的总体积
f[j][k] = (f[j][k]+f[j-x][k-1])%M;
}
}
}
int ans=0;
for(int i=1;i<=v;i++) { //遍历体积为m的方案数
ans = (ans + f[i][m])%M;
}
cout << ans <<'\n';
}
return 0;
}
1006小凯在长跑
题意：一个常规跑道，由两个半圆、两条直道连接组成，圆的半径为r，直道长度为2d。现在给出一个坐标（x，y），求这个点走到跑道的最近距离。
输入：有 T组数据，1≤T≤1e5，1≤d,r≤1e4, −1e4≤x,y≤1e4。
输出：T行，每行一个整数，四舍五入后可到固定路径的最短距离长度。
思路：将x，y都取abs，将范围缩小到第一区间，因为四个区间都是对称等区域的，所以不会影响答案，然后再讨论坐标在直跑道内/外，还是在圆跑道内外即可。
1、当 y 小于等于 d 时，说明点在某个特定的水平范围内。此时比较 x 和 r 的大小，计算它们的差值，差值的绝对值就是所求的距离。
2、当 y 大于 d 时，点不在上述水平范围内。此时需要计算点 (x, y) 到圆心（这里圆心可以理解为 (0, d)）的距离 len，使用勾股定理 sqrt(x * x + (y - d) * (y - d)) 来计算。然后比较 len 和 r 的大小，计算它们的差值并四舍五入得到最终结果。
代码：
#include <bits/stdc++.h>
using namespace std;
int main(){
int T;
cin >> T;
int d,r,x,y;
while(T--){
cin >> d >> r >> x >> y;
x=abs(x),y=abs(y);
if(y<=d){
if(x>r) cout << x-r;
else cout << r-x;
}
else{
// 计算点 (x, y) 到圆心 (0, d) 的距离
double len=sqrt((x*x)+(y-d)*(y-d));
if(len>r) cout << round(len-r);
else cout << round(r-len);
}
cout <<'\n';
}
return 0;
}
1010小凯做梦
题意：存在一棵树，无向边，n个节点，有n-1条边，一条边从点u到点v的边权为w，dis（i，j）表示 i 号节点跟 j 号节点之间的距离对 2 取模之后的结果，问有多少对 ( i,j,k ) 满足, dis(i,j) = dis(j,k) = dis(i,k) , (1 <= i , j , k <= n) ，注意 i,j,k 可以相等。
输入：有 T组数据，1≤T≤5, 1≤n≤5∗1e5, 1≤u,v≤n,1 ≤w≤1e9 。
输出：共T行，对于每组数据，输出一个数 ans 表示有多少对( i,j,k )满足条件。
思路：因为%2后dis要么0（偶），要么1（奇），可以建立无向树：v[u]={v,w}（u->v且边权w）, v[v]={u,w}，以任意根节点dfs（x，fa，u）搜索：x:当前节点，fa:父节点，u:当前步奇/偶，return{奇数总个数，偶数总个数}，分奇偶两组，每组中任意一个数都可以填入（i，j，k）三个位置，答案ans= pow(奇数总个数,3)+pow(偶数总个数,3)。
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
typedef pair<int,int>PII;
const int N=5e5+10;
vector<PII>v[N];
PII dfs(int x,int fa,int u){ //x:当前节点，fa:父节点，u:当前步奇/偶
PII res;
if(u==0) res={0,1}; // 如果当前步为偶数，初始化奇数个数为 0，偶数个数为 1
else res={1,0}; // 如果当前步为奇数，初始化奇数个数为 1，偶数个数为 0
for(auto p:v[x]){
int l=p.fi,w=p.se;
if(l==fa) continue;
// 递归调用 dfs 函数，计算从邻接节点开始的路径长度的奇偶性数量
PII val=dfs(l,x,(u+w)%2);
res.fi+=val.fi;
res.se+=val.se;
}
return res;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
int n,l,r,w;
while(T--){
cin >> n;
for(int i=1;i<=n;i++) v[i].clear();
n--;
while(n--){// 读取边的两个端点 l 和 r 以及边的权重 w
cin >> l >> r >> w;
v[l].push_back({r,w});
v[r].push_back({l,w});
}
PII d=dfs(1,0,0);
int ans= pow(d.fi,3)+pow(d.se,3);
cout << ans<<'\n';
}
return 0;
}
1008小凯想要MVP!
题意：在一个长度为n数组中每元素Ci满足1≤Ci≤m , 是否存在两个数组：
1、长度相同，2、元素和相同，3、两个子序列不能相交。（即不能取相同位置上的数），存在“YES”，否则“NO”。
输入：有T组数组， 1≤T≤20, 1≤n,m≤2∗1e5 。
输出：共T行，对于每组数据，如果能找到满足条件的子序列，输出 YES ，否则输出 NO 。
思路：因为两个子序列的长度相同，总和一样，如果存在满足条件的情况必定有两个数的差值同时存在两序列中，否则无法构造出两个等长等和的子序列，输出“NO”即可。
数组sort排序后，每两个相邻的差值存在map中，当map的值==2且差值不相邻（i，j，k，j-i==k-j为两个差值相邻）或者map的值>2 , 则“YES”，否则“NO”。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
map<int,int>mp,vp;
int t[N];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
int n,m;
while(T--){
cin >> n >> m;
int p=0;
vp.clear(),mp.clear();
for(int i=0;i<n;i++) {
cin >> t[i];
vp[t[i]]++;
if(vp[t[i]]==2) p=1;
}
if(p) {
cout << "YES"<<'\n';
continue;
}
sort(t,t+n);
for(int i=0;i<n;i++){
int u=t[i+1]-t[i];
mp[u]++;
if(i-1>=0&&mp[u]==2&&u!=t[i]-t[i-1]) p=1;
else if(mp[u]>2) p=1;
}
if(p) cout << "YES";
else cout << "NO";
cout << '\n';
}
return 0;
}
1009小凯取石子
题意：现有 n 个石子，小凯和 Kc0 轮流从中取出 1 或 4 颗石子，Kc0 先手，取走最后一颗石子的人即为胜者。
由于 Kc0 太笨了，所以他每次只会等概率随机地想要取走 1 颗或者 4 颗石子。如果 Kc0 想要取走 4 颗石子但是剩下的石子不足 4 颗，那么他会掀桌走人并被判负。
小凯非常聪明，并且他知道 Kc0 的策略。那么小凯最终获胜的概率是多少？
输入：表示有 T组数据，T<=100, 1<=n<=1e9。
输出：对于每组数据输出一行一个整数，表示小凯获胜的概率对 998244353998244353 取模后的结果。
推导打表找规律：
打表代码：
#include <bits/stdc++.h>
using namespace std;
typedef array<int,2> ar2;
typedef pair<int,int>PII;
map<int,ar2>m;
ar2 sg(int x){
if(m.count(x)) return m[x];
ar2 u=sg(x-2);
ar2 v=sg(x-5);
ar2 w=sg(x-8);
ar2 d1,d2;
double du=1.0*u[0]/u[1], dv=1.0*v[0]/v[1], dw=1.0*w[0]/w[1];
if(du>dv) d1=u;
else d1=v;
d1[1]*=2;
if(dv>dw) d2=v;
else d2=w;
d2[1]*=2;
ar2 res={d1[0]*d2[1]+d1[1]*d2[0],d1[1]*d2[1]};
int g=__gcd(res[0],res[1]);
res[0]/=g,res[1]/=g;
return m[x]=res;
}
int main(){ //《打表代码》
m[1]={1,2};
m[2]={1,1};
m[3]={3,4};
m[4]={1,2};
m[5]={1,1};
m[6]={1,2};
m[7]={1,1};
m[8]={7,8};
int n;
cin >> n;
for(int i=1;i<=n;i++){
auto x=sg(i);
cout << i <<" "<< m[i][0]<<" "<< m[i][1]<<endl;
}
return 0;
}
AC代码：
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n=0,m=0,k=0;
const int mod =998244353;
int qc(int a,int b)
{
int ans=1;
while (b)
{
if(b&1)ans*=a;
a*=a;
b>>=1;
ans%=mod;
a%=mod;
}
return ans%mod;
}
signed main ()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
while (T--)
{
cin>>n;
if(n==1){
cout<<499122177<<"\n";
continue;
}
int x=n%5,y=n/5;
if(x==3) y+=2;
if(x==4) y+=1;
if(x==2||x==0){
cout<<1<<"\n";
continue;
}
int fm=qc(2,y)%mod;
int fz=(fm-1+mod)%mod;
cout<<(fz%mod*qc(fm,mod-2)%mod)%mod<<"\n";
}
return 0;
}2025“钉耙编程”中国大学生算法设计春季联赛（6）题解链接：
HDU 2025“钉耙编程”中国大学生算法设计春季联赛（6）（补题）-CSDN博客
2025“钉耙编程”中国大学生算法设计春季联赛（7）题解链接：
更多推荐
39
0- 0
已为社区贡献4条内容
所有评论(0)