河南萌新联赛2024第（五）场：信息工程大学

A 日历游戏

题目描述

Alice 和 Bob 在玩一个游戏，他们先从 2000.1.1 到 2024.8.1 这个日期之间（不包括2024.8.1）随意抽取一个日期出来。然后他们轮流对这个日期进行操作：

把日期的天数加 1，例如：2000.1.1 变到 2000.1.2
把月份加 1，例如：2000.1.1 变到 2000.2.1

其中如果天数超过应有天数则日期变更到下个月的第 1 天。月份超过 12 则变到下一年的1月。而且进行操作2的时候，如果有这样的日期：2000.1.31，则变成了 2000.2.31，这样的操作是非法的，我们不允许这样做。

所有的操作均要考虑历法和闰年的规定。

谁先将日期变到 2024.8.1 谁就赢了。如果超越了指定日期不算获胜。

每次游戏都是 Alice 先操作，问他有没有必胜策略?

解题思路

谁先出现能让下一日期的月数和日数的和为奇数的情况，谁就必胜

AC代码

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
void solve()
{int x,y,z;cin>>x>>y>>z;if((y==9&&z==30)||(y==11&&z==30)||(y+z)%2==0)    puts("YES");else    puts("NO");
}
signed main()
{IOSint t;cin>>t;
//     t=1;while(t--)solve();return 0;
}

B 学生分组

题目描述

有一个含有 n 个元素的随机序列，如果一个序列中所有元素均在 [L,R] 区间内，则称其为一个好的序列，现在每次你可以在使其中一个数+1，另一个数-1，问最少要多少次才可以使随机序列成为一个好的序列。

解题思路

实质就是让数组的所有数，变成 [L,R] 之间的数，操作是让数组的一个数 +1 ，同时另一个数必须 -1 。求最少的操作操作步数，如果不能完成变化输出" -1 "。
分别求出，需要减的次数，需要加的次数，最后多出的次数，数组内符合条件的数在区间内移动，消除多出的次数

AC代码

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define fi first
#define se second
#define PII pair<int,int>
#define ALL(x) x.begin(),x.end()
const int N=1e6+10;
int a[N];
void solve()
{int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}int l,r;cin>>l>>r;int x=0,y=0;for(int i=1;i<=n;i++){if(a[i]<l){x+=l-a[i];a[i]=l;}if(a[i]>r){y+=a[i]-r;a[i]=r;}}sort(a+1,a+n+1);if(x==y){cout<<x<<'\n';}else if(x>y){int tt=x-y;for(int i=n;i>=1;i--){if((a[i]-l)>0){tt-=a[i]-l;}if(tt<=0)break;}if(tt<=0)    cout<<x<<'\n';else    cout<<"-1"<<'\n';}else{int tt=y-x;for(int i=1;i<=n;i++){if((r-a[i])>0){tt-=r-a[i];}if(tt<=0)    break;}if(tt<=0)    cout<<y<<'\n';else    cout<<"-1"<<'\n';}
}signed main()
{IOSint t;
//     cin>>t;t=1;while(t--)solve();return 0;
}

C 小美想收集

题目描述

小美想：整个暑假不能全部用来锻炼，也应该收集一些回忆。

整个暑假的回忆将被小美分为两部分：好回忆和坏回忆。

但是并不是所有回忆都可以相安无事的，所以小美也不会随意划分这些回忆的种类。

一个回忆可能会跟其它的一些回忆产生“冲突”，这个“冲突”有一个值 c ，而小美会用波动值来描述整个暑假的美好程度。

只要会产生冲突的两个回忆同时被划分到好回忆或者坏回忆中，小美的波动值就可能发生变化。

具体来说，小美的波动值取决于在最后的划分结果中，同一回忆（好回忆或者坏回忆）种类下最大的那个冲突值。

小美想要自己的暑假尽可能的美好，所以她想请你帮她来划分回忆，使得最后的波动值最小。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
int p[N];
struct op{int a,b,c;
}q[N];
bool cmp(op x,op y)
{return x.c>y.c;
}
int find(int x)
{return p[x]==x ? x : (p[x]=find(p[x]));
}
signed main()
{int n,m;cin>>n>>m;for(int i=1;i<=2*n;i++)	p[i]=i;for(int i=1;i<=m;i++)cin>>q[i].a>>q[i].b>>q[i].c;sort(q+1,q+m+1,cmp);for(int i=1;i<=m;i++){int x=find(q[i].a);int y=find(q[i].b);if(x==y){cout<<q[i].c;break;}p[find(q[i].a+n)]=y;p[find(q[i].b+n)]=x;}return 0;
}

D 区间问题1

题目描述

Alice 有 n 个数，她可以对这 n 个数执行以下两种操作：

1. 将区间 [L,R] 上的所有数加上 d

2. 查询第 x 个数的值

解题思路

直接暴力加上数 d

AC代码

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define fi first
#define se second
#define PII pair<int,int>
#define ALL(x) x.begin(),x.end()
const int N=1e5+10;
int a[N],p[N],tt[N];
void solve()
{memset(p,0,sizeof p);int n;cin>>n;for(int i=1;i<=n;i++)    cin>>a[i];int q;cin>>q;while(q--){int l,r,d;int x;int op;cin>>op;if(op==1){cin>>l>>r>>d;for(int i=l;i<=r;i++)    a[i]+=d;}else{cin>>x;cout<<a[x]<<'\n';}}
}signed main()
{IOSint t;// cin>>t;t=1;while(t--)solve();return 0;
}

E 哥德巴赫猜想

题目描述

1742 年 6 月 7 日，哥德巴赫写信给当时的大数学家欧拉，提出了以下的猜想：任何一个大于 9 的奇数都可以表示成 3 个质数之和。欧拉在回信中说，他相信这个猜想是正确的，但他不能证明。从此，这道数学难题引起了几乎所有数学家的注意。哥德巴赫猜想由此成为数学皇冠上一颗可望不可及的“明珠”。

现在请你编一个程序验证哥德巴赫猜想。

解题思路

先算出[1, 50000] 的素数，打表找到规律，答案数组中，第一个数一定为 2 或 3 ，前两数只能是 2和2 或者 3和其他素数，模拟即可

AC代码

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define fi first
#define se second
#define PII pair<int,int>
#define ALL(x) x.begin(),x.end()
const int N=1e5+10;
int a[N],p[N],tt[N];
int primes[N], cnt=0;
bool st[N];
void get_primes(int n)
{for (int i = 2; i <= n; i ++ ){if (!st[i]) primes[cnt ++ ] = i;for (int j = 0; primes[j] <= n / i; j ++ ){st[primes[j] * i] = true;if (i % primes[j] == 0) break;}}
}
void solve()
{int n;cin>>n;if(n<7)    cout<<"-1\n";else if(n==9)    cout<<"3 3 3\n";else{int fa=0;int tt=n-4;if(!st[tt])    cout<<"2 2 "<<tt<<'\n';else{for(int i=1;i<=cnt;i++){int y=primes[i];if(!st[n-3-y]){cout<<'3'<<' '<<y<<' '<<n-3-y<<'\n';break;}}}}
}signed main()
{IOSget_primes(50100);int t;cin>>t;
//     t=1;while(t--)solve();return 0;
}

F 小美想跑步

题目描述

暑假来了，对于小美来说，想要锻炼身体，游泳还不够，小美想：她还必须要跑步。

为此，小美在家的周围设置了 n-1 个打卡点，小美每次跑步都需要把这 n-1 个打卡点全部打卡。

但是小美喜欢轻装上阵，所以小美出去跑步时从来不带水杯。

可是小美又容易口渴，所以每次小美打卡完一个打卡点后，都要返回到家中去喝水。

小美第一次出去打卡是从家出发的，小美最后一次打完卡还要回到家中喝水。

况且小美很自律，所以她一定会出去打 n-1 次不同的卡，即便在打卡路上遇到了另一个打卡点，她也不会打卡。

不过小美想：既然已经在假期坚持游泳了，那么跑步上可不可以偷偷懒呢。

所以小美想请聪明的你来帮她想想办法，让她跑步的总路程最短。

输入格式：
第一行包含两个整数 n 和 m，其中 1 ≤ n, m ≤ 1e6。n 表示打卡点的总数（包括小美家），m 表示路的数量。	
接下来 m 行，每行包含三个整数 x, y, z，其中 1 ≤ x, y ≤ n 且 1 ≤ z ≤ 1e6。这三个整数表示一条从 x 出发到 y 的单行路，路的长度为 z。

具体说明：

小美家的编号为 1。
打卡点的编号为 2 到 n。
所有的路都是单行路，即小美只能沿着一个方向跑，不能反向行驶。

解题思路

多源汇最短路，Floyd 算法的模版题，当时看到题时想到的是Floyd 但时间复杂度是 nnn，又因为1 ≤ n ≤ 1e6，所有畏惧时间超限没敢写，实际开个1000* 1000 的二位数组就能过

AC代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
int dist[1010][1010];
int ans=0;
int main(){cin>>n>>m;memset(dist,0x3f3f,sizeof(dist));for(int i=1;i<=n;i++) dist[i][i]=0;for(int i=1;i<=m;i++){int x,y,z;cin>>x>>y>>z;dist[x][y]=min(dist[x][y],z);}// Floydfor(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);}}}for(int i=2;i<=n;i++)    ans+=dist[i][1]+dist[1][i];cout<<ans;return 0;
}

G 爬楼梯

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1-3 个台阶。你有多少种不同的方法可以爬到楼顶呢？

仅一行，输出到达楼顶的方案数，由于其结果较大，请对结果与 1000000007 取模。

解题思路

动态规划，f[i]=(f[i-1]%mod+f[i-2]%mod+f[i-3]%mod)%mod

AC代码

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define fi first
#define se second
#define PII pair<int,int>
#define ALL(x) x.begin(),x.end()
const int N=1e6+10,mod=1000000007;
int f[N];
void solve()
{f[0]=1;f[1]=1;f[2]=2;for(int i=3;i<=N-10;i++){f[i]=(f[i-1]%mod+f[i-2]%mod+f[i-3]%mod)%mod;}int n;cin>>n;cout<<f[n]%mod<<'\n';
}signed main()
{IOSint t;// cin>>t;t=1;while(t--)solve();return 0;
}

H 区间问题2

题目描述

Bob 有 n 个数，他想知道任意一个区间内的最大值是多少。

输入
第一行一个整数 n，表示数的个数，其中 n<=10^6；

第二行为 n 个整数。

第三行一个整数 q，表示询问的次数，其中 q<=10^6；

接下来 q 行，每行有一对 L,R，即询问区间 [L,R] 的最大值。

输出
q 行，每一次询问的结果。

提示：注意此题输入量极大，需要使用输入优化。

解题思路

st表与快读快出的模版题

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi(a,b) for(int i = a; i <= b; ++i)
#define fr(a,b) for(int i = a; i >= b; --i)
using pii = pair<int,int>;
int Matrix[1000005];
int dp[1000005][30];
inline int read(){int x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-'){f = -1;}ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + (ch - '0');ch = getchar();}return x * f;
}
inline void write(int x){if(x < 0){putchar('-');x = -x;}if(x > 9){write(x / 10);}putchar(x % 10 + '0');
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);int n,m;n=read();fi(1,n)    Matrix[i]=read();m=read();for(int i = 1; i <= n; ++i)    dp[i][0] = Matrix[i];for(int j = 1; 1 << j <= n;++j)for(int i = 1;i + (1 << j) - 1 <= n;++i)dp[i][j] = max(dp[i][j-1],dp[i + (1 << (j -1))][j - 1]);while(m--){int a,b;a=read();b=read();int k = log2(b - a + 1);int ans= max(dp[a][k],dp[b - (1 << k) + 1][k]);write(ans);printf("\n");}return 0;
}

I 小美想打音游

题目描述

小美在暑假期间，为了锻炼手指肌肉，选择了打音游这一挑战。她是个音游高手，但最近在冲击歌曲分数时屡遭失败。为了突破瓶颈，小美决定使用魔法来辅助。

在她的音游中，共有n首歌曲，每首歌都有一个当前的分数ci，但均未达到满分。小美的魔法可以将所有歌曲的分数统一调整至某个特定分数a，但这一过程会消耗她的魔力，消耗量等于每首歌当前分数与目标分数a之差的绝对值之和，即∑| $c_i$ - a|。

小美希望，在将所有歌曲分数调整至同一水平后，再一次性将所有分数提升至满分，这样她只需再消耗一次魔力。现在，她想知道，为了最小化整个过程中消耗的魔力总值，应该如何选择这个中间分数a。

简而言之，小美需要找到一个最优的a值，使得从当前分数到a，再从a到满分的两次调整过程中，她所消耗的魔力总和最小。

解题思路

转化同一数的最小次数为转化成中位数

AC代码

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define fi first
#define se second
#define PII pair<int,int>
#define ALL(x) x.begin(),x.end()
const int N=1e6+10;
int a[N],sum=0;
void solve()
{int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1);int mid;int ans=0;if(n%2==1){mid=a[(n/2)+1];for(int i=1;i<=n;i++){ans+=(int)abs(a[i]-mid);}}else{mid=a[(n/2)];for(int i=1;i<=n;i++){ans+=(int)abs(a[i]-mid);}int ans2=0;mid=a[(n/2)+1];for(int i=1;i<=n;i++){ans2+=(int)abs(a[i]-mid);}ans=max(ans,ans2);}cout<<ans+1;
}
signed main()
{IOSint t;
//     cin>>t;t=1;while(t--)solve();return 0;
}

J 平方根

题目描述

求一个数 n 的算术平方根

解题思路

利用函数pow(n, 0.5）

AC代码

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define fi first
#define se second
#define PII pair<int,int>
#define ALL(x) x.begin(),x.end()
const int N=2e5+10;
int a[N];
void solve()
{int n;cin>>n;cout<<(int)pow(n,0.5)<<'\n';
}signed main()
{IOSint t;cin>>t;
//     t=1;while(t--)solve();return 0;
}

K 小美想游泳

题目描述

暑假来了，又到了小美游泳的时候了。

小美的家在海边，但是小美并不想去海里游泳，所以她选择去河里游泳。

小美家的旁边共有 m 条河和 n 个岛屿，这 m 条河将这 n 个岛屿相连。

小美想选择一条路线，能够从 s 岛游到 t 岛。

但是小美家旁边的河可不是普通的河，因为受到了大海的影响，所以每条河都会有波浪，波浪很厉害。

而一条河当中的波浪的厉害程度 a 是固定的，小美作为一个初学者，希望不要遇到太厉害的波浪。

所以小美想请你帮她找到一条路线，使这条路线上最厉害的波浪的厉害程度值 a 最小。

但是对于初学者小美来说，她并不关心别的事情，所以你只需要告诉她这个最厉害的波浪的厉害程度值是多少就可以了。

解题思路

利用并查集的归属操作，先按照厉害程度值的升序排序，当点s 和点t 属于同一根时，即点s 能到点t 此时，该点的波浪的厉害程度值最大。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,s,t;
int p[10005];
vector<tuple<int, int, int > >g;
int find(int x)
{return p[x]==x ? x : (p[x]=find(p[x]));
}
signed main()
{cin>>n>>m;for(int i=1;i<=n;i++)p[i]=i;for(int i=1;i<=m;i++){int a,b,c;cin>>a>>b>>c;g.push_back({c,a,b});}cin>>s>>t;sort(g.begin(),g.end());for(auto a : g){auto [w,x,y]=a;x=find(x);y=find(y);if(x==y)	continue;p[y]=x;if(find(s)==find(t)){cout<<w;break;}}return 0;
}