题目链接：
河南萌新联赛2024第（五）场：信息工程大学_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ
目录
1.日历游戏
//解题思路：这个题看起来是一个日期的计算的题，其实把情况都计算一遍就会看出来这是一个找规律的博弈题。
//即2001.10.4和2001.11.3必胜（此时m+d=偶数）再推上去是11.2，10.3，9.3，都是必败（此时m+d=奇数），以此类推……
//从9月30和11月30开始推算的话也是必胜的（这是一个例外），其他情况就是偶数必胜，奇数必败
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int x,y,z,n;
cin>>n;
while(n--)
{
cin>>x>>y>>z;
if(((y==9||y==11)&&z==30)||(y+z)%2==0)
{
cout<<"YES"<<endl;
}
else
{
cout<<"NO"<<endl;
}
}
return 0;
}2.学生分组
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n;
cin >> n;
vector<long long> a(n);
long long total = 0;
for(int i = 0; i < n; i++)
{
cin >> a[i];
total += a[i];
}
long long L, R;
cin >> L >> R;
if (total < L * n || total > R * n)
{
cout << -1 << endl;
return 0;
}
long long max1 = 0; // 超出 R 的总和
long long min1 = 0; // 低于 L 的总和
for(int i = 0; i < n; i++)
{
if (a[i] > R)
{
max1 += (a[i] - R);
}
else if (a[i] < L)
{
min1 += (L - a[i]);
}
}
cout << max(max1, min1) << endl;
return 0;
}3.区间问题1
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,q;
ll a[100010];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
cin>>q;
while(q--)
{
ll sign,l,r,d,x;
cin>>sign;
if(sign==1)
{
cin>>l>>r>>d;
for(int i=l;i<=r;i++)
{
a[i]+=d;
}
}
else
{
cin>>x;
cout<<a[x]<<endl;
}
}
return 0;
}4. 哥德巴赫猜想
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 50010; // 质数生成范围
int t;
int primes[N], cnt; // primes[]存储所有的质数
bool st[N]; // st[x]表示 x 是否被标记（存储的是非质数）
// 线性筛法生成质数(直接用模板)
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;
}
}
}
// 检查一个数是否是质数
bool is_prime(int x)
{
if (x < 2) return false;
if (x < N) return !st[x];
return false;
}
int main()
{
get_primes(50000);
cin >> t;
while (t--)
{
int n;
cin >> n;
bool found = false;
for (int i = 0; i < cnt; i++)
{
for (int j = i; j < cnt; j++)
{
int temp = n - primes[i] - primes[j];
if (temp > 0 && is_prime(temp) && temp >= primes[j])
{
cout << primes[i] << " " << primes[j] << " " << temp << endl;
found = true;
break;
}
}
if (found)
{
break;
}
}
if (!found)
{
cout << -1 << endl;
}
}
return 0;
}5.小美想跑步
//解题思路：两点之间，直线最短，图论Floyd-Warshall算法
//dp[i][j][k]:点i到点j只经过0到k个点最短路径,降维说明：
//发现dp[i][j][k]依赖于前面的k的值，例如dp[i][j][k-1],也就是说
//如果我们已经计算了k-1个中介点，那么加上第k个中介点只能改善路径，或者保持不变，而不会更差。
//最后通过逐步引入中介点k来计算最优路径
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int dp[1010][1010];//i到j的最短总路程
void fun(int n)
{
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
}
}
}
}
int main()
{
int n,m;
memset(dp,0x3f3f3f,sizeof(dp));
cin>>n>>m;
while(m--)
{
int x,y,z;
cin>>x>>y>>z;
dp[x][y]=z;
}
fun(n);
ll sum=0;
for(int i=2;i<=n;i++)
{
sum+=dp[1][i]+dp[i][1];
}
cout<<sum<<endl;
return 0;
}6.爬楼梯
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000000007;
ll dp[1000010];//爬到楼顶方式
int n;
int main()
{
memset(dp,0,sizeof(dp));
cin>>n;
dp[1]=1;
dp[2]=2;
dp[3]=4;
dp[4]=7;
for(int i=5;i<=n;i++)
{
dp[i]=(dp[i-1]+dp[i-2]+dp[i-3])%N;
}
cout<<dp[n]<<endl;
return 0;
}7. 区间问题2
//st算法(用st表) 状态区间 st[i][j]:按需查找数组从i开始到2^(j-1)最值
//状态转移方程：st[i][j]=max{st[i][j-1],st[i+(1<<(j-1))][j-1]}对于数组S,划分为两部分(A和B),那么S的最大值取max(A,B)
//当j=0时，2^0=1，st[i][0] = S[i]
#include<bits/stdc++.h>
#define MAX_N 1000007
#define MAX_M 30 // 2^30 > 1000007
using namespace std;
int S[MAX_N],Log[MAX_N];
int st[MAX_N][MAX_M];
int n,m;
//区间最值
void init()
{
for(int i=1; i<=n; i++)
st[i][0] = S[i]; //存取输入的数组
for(int j=1; (1<<j)<=n; j++) //遍历所有可能的区间长度 2^j，从 j = 1 开始。
for(int i=1; i+(1<<(j-1))<=n; i++) //计算长度为 2^j 的区间的最大值。i 是区间的起始位置。
st[i][j] = max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
//进行log值计算
void getLog()
{
Log[1] = 0;
for(int i=2; i<=n+1; i++)
Log[i] = Log[i/2]+1;
}
//区间最值查询长度：只需要找到对应的st表的区间, 因为L一般来说不会刚好为 2的某个次方，或者说由于logL是向下取整的，2k一般会小于L
//k=向下取整(log2(r-l+1))所以要确保取到正确的区间最值，可以在(l,r)的两头取，取 (l,l+2k) 与 (r-2k+1,r) 区间的最值，这样虽然包含了重复部分，但不会影响结果
int Query(int l,int r)
{
int k = Log[r-l+1];
return max(st[l][k],st[r-(1<<k)+1][k]);
}
//这里是快读，处理大量输入数据耗时多的问题
inline int read()
{
int x=0,f=1;
char ch=getchar();
while (!isdigit(ch))
{
if (ch=='-') f=-1;
ch=getchar();
}
while (isdigit(ch))
{
x=x*10+ch-48;
ch=getchar();
}
return x*f;
}
int main()
{
int l,r;
n = read();
for(int i=1; i<=n; i++)
S[i] = read();
m = read();
getLog();
init();
for(int i=1; i<=m; i++)
{
l = read();
r = read();
printf("%d\n",Query(l,r));
}
return 0;
}
8.小美想打音游
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int c[1000010];
ll sum=0;
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>c[i];
}
sort(c,c+n);
for(int i=0;i<n;i++)
{
sum+=abs(c[i]-c[n/2]);
}
cout<<sum+1<<endl;
return 0;
}9.平方根
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n;
int main()
{
cin>>t;
while(t--)
{
cin>>n;
cout<<(ll)sqrt(n)<<endl;
}
return 0;
}