本次比赛题目难度：
easy : I , D
medium-easy: H , L , E
medium :B , J
medium hard: A , G
hard: C ,
F题为算法板子题， 不计入难度表
A.阿拉德的冒险者
遍历的路线已经确定（1 ~ n），只需要从 1到n 遍历一遍 ， 将各自需要消耗的生命力排序后放入另一数组中，由于数据较小，每次重新排序并不会超时 ， 排序后在头尾设置指针 ， 需要消耗生命力最小的不释放能量 ， 大的释放能量即可
stl小根堆版本：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10 ;
ll n , m, k;
ll sum ;
ll s[N] ;
priority_queue<ll , vector<ll> , greater<ll> > q;//小根堆，确保队头为最小的元素值
int main()
{
cin >> n >> m >> k;
for(int i = 1 ; i <= n ; i ++) cin >> s[i] ;
for(int i = 1 ; i <= n ; i ++)
{
q.push(s[i]) ;//将该地区入队
if(q.size() > k )//如果队中元素大于k
{
sum += q.top() ;//第一个地区，即消耗生命力最小的地区不释放能量，选择消耗生命
q.pop() ;
}
if( sum >= m )
{
cout << i - 1 ;//在当前区域消耗完生命力意味着没有畅游该国家
return 0 ;
}
}
cout << n ;
return 0;
}
数组模拟版本：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10 ;
ll n , m, k;
ll sum ;
ll s[N] ;
ll q[N] ;
int main()
{
cin >> n >> m >> k;
for(int i = 1 ; i <= n ; i ++) cin >> s[i] ;
ll head = 1 , rear = 0 ;//头尾指针
for(int i = 1 ; i <= n ; i ++)
{
q[++ rear] = s[i] ;//入队
sort(q + 1 , q + 1 + rear) ;//确保队首元素最小
if( rear > k )
{
sum += q[head] ;
head ++ ;
}
if( sum >= m )
{
cout << i - 1 ;
return 0 ;
}
}
cout << n ;
return 0;
}
B. 大 大 大
只需要保证第一位数字最大即可使 式 S 最大
注意：如果将最大值右移到数组头部的次数大于 t ，从后往前遍历找 t 次内能一刀数组头部的最大值
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 +10 ;
int n , t , maxx = -1, idx = -1;
int a[N] ;
int main()
{
cin >> n >> t;
for(int i = 1; i <= n; i++)
{
cin >> a[i] ;
if(a[i] >= maxx )//存储最大值的位置与值
{
maxx = a[i] ;
idx = i ;
}
}
if(idx == 1)//如果最大值在第一位
{
cout << 0 ;
return 0;
}
else
{
if( n - idx + 1 <= t)
{
cout << n - idx + 1;
return 0;
}
else
{
maxx = a[n] ;//从后往前遍历 ，假设数组尾部的元素为最大值进行比较
idx = n;//位置为 n
for(int i = n ;i >= n - t + 1 ; i --)
{
if(a[i] > maxx)//如果有更大的值 ， 记录
{
maxx = a[i] ;
idx = i;
}
}
cout << n - idx + 1;//输出次数
return 0;
}
}
}
C. 玫瑰花的葬礼
由于元素组合个数最大为 495 * 495 ≈ 2.5 * 105 , 所以直接预处理出所有的组合
对于数组中的每个元素，如果两个元素大于495 ， 则对于该元素，对495取模的效果与用该元素直接寻找方案数效果相同，即取模后存入0 ~ 495的哈希表即可（桶排序）
再对hash表中已经存入的数字进行遍历，由于只能操作一次使得某个元素+1 ，则
对每个元素判断+1和不变两种情况时 ， 方案数最大值即可
还有一种方法是通过分解495的质因子为3 3 5 11 ， 因此若两个数含有3 3 5 11这四个质因子，则相乘后的数一定是495的倍数，这是官方正解
详情可以去b站搜索，这里不再赘述
原题链接：D-红魔馆的馆主（二）_牛客周赛 Round 68
#include<bits/stdc++.h>
using namespace std ;
#define int long long
const int res = 495 ;
int n ;
int hashs[res + 10] ;
int solve()//预处理
{
int ans = 0 ;
for(int i = 0 ; i < res ; i ++)
for(int j = 0 ; j < res ; j ++)
{
//如果是i * j是495的倍数 且哈希表中存在i与j的值（数组中出现过i , j）
if(i * j % res == 0 && hashs[i] > 0 && hashs[j] > 0)
{
//每个hashi[i]与其余个hashi[i]配对相乘
if(i == j) ans += hashs[i] * (hashs[i] - 1) ;
//值为i的元素个数与值为j的元素个数可以进行组合 ， 组合方案数为 i * j
else ans += (hashs[i] * hashs[j]) ;
}
}
return ans ;
}
signed main()
{
cin >> n ;
for(int i = 1 ; i <= n ; i ++)
{
int a ;
cin >> a ;
hashs[a % res] ++ ;//存入hash表中，表示出现次数;
}
int maxx = solve() ;//定义最开始时的记忆落痕最大值
for(int i = 0 ; i < res ; i ++)
{
if(hashs[i])//如果数组中存在该值或存在取模后为该值的元素
{
//选择+1后判断方案数
hashs[i] -- ;
hashs[(i + 1) % res] ++ ;
maxx = max(maxx , solve()) ;
//回溯 ， 复原该元素未+1前的hash表状态
hashs[i] ++ ;
hashs[(i + 1) % res] -- ;
}
}
//因为每个元素都进行了重复使用 ，对结果除以二后输出即可
cout << maxx / 2 ;
return 0 ;
}
D.离散数学
题目中说明：拥有无数次删除操作
则直接将图删除为n个点 ， 由基本不等式 a2 + b2 >= 2ab得
当a 与 b尽量接近时 ， 求得的复杂度最大
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long n , m , u , v;
long long val ;
cin >> n >> m;
for(int i = 1 ;i <= m; i++)
{
cin >> u >> v;
}
if(n == 1)//如果只有1个点时 ， 只能构成1个连通块， 复杂度为 0
{
cout << 0 ;
return 0 ;
}
else
{
//如果n为偶数 ， 复杂度最大值即为 （n / 2）2 ;
if( n % 2 == 0 ) val = (n/2) * (n/2);
//如果n为奇数 ， 复杂度最大值即为 n / 2 * (n + 1) / 2 ;
else val = n / 2 * (n + 1) / 2 ;
}
cout << val ;
return 0;
}
E.简单的运算
简单的字符串题目，输入后遍历字符串，找出不是数字的元素即可
#include<bits/stdc++.h>
using namespace std ;
int n ;
string s ;
int main()
{
cin >> n ;
cin >> s ;
vector<char> c ;
for(int i = 0 ; i < s.size() ; i ++)
{
if(s[i] < '0' || s[i] > '9')
c.push_back(s[i]) ;
}
for(int i = 0 ; i < c.size() ; i ++)
cout << c[i] ;
return 0 ;
}
F.哥德巴赫猜想
验证输入的n是否为质数
需要用到Miller_Rabin算法
注意数据范围
本题了解即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
int prime[10]={2,3,5,7,11,13,17,19,23,29};
int Quick_Multiply(int a,int b,int c) //快速积（和快速幂差不多）
{
long long ans = 0 , res = a;
while(b)
{
if(b & 1)
ans = ( ans + res ) % c;
res = (res + res) % c ;
b >>= 1;
}
return (int)ans;
}
int Quick_Power(int a , int b , int c) //快速幂，这里就不赘述了
{
int ans = 1 , res = a;
while(b)
{
if(b & 1)
ans = Quick_Multiply(ans , res , c);
res = Quick_Multiply(res , res , c);
b >>= 1;
}
return ans;
}
bool Miller_Rabin(int x) //判断素数
{
int i,j,k;
int s = 0 , t = x - 1;
if(x == 2) return true; //2是素数
if(x < 2 || !(x & 1)) return false; //如果x是偶数或者是0,1，那它不是素数
while(!(t & 1)) //将x分解成(2^s)*t的样子
{
s ++;
t >>= 1;
}
for(i = 0 ; i < 10 && prime[i] < x ; ++ i) //随便选一个素数进行测试
{
int a = prime[i];
int b = Quick_Power(a,t,x); //先算出a^t
for(j = 1 ; j <= s ; ++ j) //然后进行s次平方
{
k = Quick_Multiply(b , b , x); //求b的平方
if(k == 1 && b != 1 && b != x-1) //用二次探测判断
return false;
b = k;
}
if(b != 1) return false; //用费马小定律判断
}
return true; //如果进行多次测试都是对的，那么x就很有可能是素数
}
signed main()
{
int x;
cin >> x ;
if(Miller_Rabin(x)) cout << "YeS" ;
else cout << "NO" ;
return 0;
}
G.分解质因数
模拟操作即可
#include<bits/stdc++.h>
using namespace std ;
#define int long long
//判断是否为质数的函数
bool is_prime(int x)
{
if(x < 2) return false ;
for(int i = 2 ; i <= x / i ; i ++)
if(x % i == 0) return false ;
return true ;
}
//输出函数
void printPrime(int n)
{
//如果n本身就是质数 ， 输出n即可
if(is_prime(n))
{
cout << n ;
return ;
}
else
{
int x = n ;
for(int i = 2 ; i <= x / i ; i ++)
{
//直到x = 1 或者 x 为质数时结束循环
if(x == 1 || is_prime(x)) break ;//①
//如果i是x的因数
if(x % i == 0)
{
if(is_prime(i))//如果i是x的质因数
{
while(x % i == 0)//循环对x提取质因子i
{
x /= i ;
}
//输出i
cout << i << ' ' ;
}
//如果i不是x的质因数 ， 重新循环
else
{
continue ;
}
}
}
//如果x不为1 ， 输出x（上方 ① 处判断过x ， 必为质数或1 ， 不为1时x必为质数， 输出即可）
if(x != 1) cout << x ;
}
}
signed main()
{
int n ;
cin >> n ;
printPrime(n) ;
return 0 ;
}
H.倾 盆 的 雨 下 了 一 整 夜
二维数组在避免边界越界的情况下进行遍历即可
#include<bits/stdc++.h>
using namespace std ;
const int N = 1e3 + 10 ;
int n , m ;
char g[N][N] ;
int main()
{
cin >> n >> m ;
for(int i = 1 ; i <= n ; i ++)
for(int j = 1 ; j <= m ; j ++)
cin >> g[i][j] ;
//字符型或字符串型才可输入，否则若定义g[N]{N]为int型
//会出现只在一个g[i][j]中输入了一个大整数的情况
int res = 0 ;
//避免边界， i , j 从2开始 ， 每次与上一行/上一列进行判断
for(int i = 2 ; i <= n ; i ++)
for(int j = 2 ; j <= m ; j ++)
if(g[i][j] == '1' && g[i - 1][j] == '1' && g[i][j - 1] == '1' && g[i - 1][j - 1] == '1')
res ++ ;
cout << res ;
return 0 ;
}
I.神奇的数字
签到题
一共只有m个因子，从小到大排序后第m个因子一定是这个数本身。
而第(1 + m) / 2个因子是这个数的因子，这个数一定会被该因子整除
因此第m个因子一定能被第(1 + m) / 2个因子整除
只需要输出n即可（注意 ：题目要求输出1 ~ n中的”神奇的数字“个数）
#include<bits/stdc++.h>
using namespace std ;
int T ;
int main()
{
cin >> T ;
while(T --)
{
int n ;
cin >> n ;
cout << n << endl ;
}
return 0 ;
}
J.尖塔第四强的糕手
模拟即可，注意参数有可能是浮点型
#include<bits/stdc++.h>
using namespace std ;
int t ;
double n , m , k , q; //实数 -> double型
double s , d ;
//判断t个回合中是否会被boss打死
bool if_alive(int res)
{
//t个回合 ， 每个回合boss的攻击力上升q ， 则t个回合boss的总伤害可以用等差数列求和公式计算
if(n <= (k + (k + q * 1.0 * res)) * 1.0 * res / 2.0 ) return false ;
else return true ;
}
int main()
{
cin >> t ;
cin >> n >> m >> k >> q ;
cin >> s >> d ;
double res = 0.0 ;
//判断使用哪种攻击方式能在最少的回合内击败boss
if(2.0 * s >= d) res = 1.0 * m / s / 2.0 ;
else res = 1.0 * m / d ;
//如果res是小数 ， 向上取整才能使得boss生命值小于等于0
//由于是我们先手进攻，所以不用在boss伤害处进行修改
if(res - (int)res > 0)
{
res = (int)(res + 1) ;
}
//如果会被boss击杀或击杀boss的时间超出t回合
if(!if_alive(res) || res > t) res = -1 ;
cout << res << endl ;
return 0 ;
}
标签：周赛,cout,刘庭铄,res,cin,long,2024,int,hashs From： https://www.cnblogs.com/hautacm/p/18570728