河南萌新联赛2024第（一）场：河南农业大学

A.造数

题意

就是有3个操作,然后构成最少需要几步
操作1：+1
操作2：+2
操作3：*2

思路

可以从n往前倒推，当n是偶数是除2，当n是奇数时-1再除2，如果最后n等于2时特判直接操作+1结束

代码

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
int n, sum = 0;signed main() {IOScin >> n;if (n == 2) {cout << 1 << endl;return 0;}while (n >= 1) {if (n == 2) {sum++;break;}if (n % 2 == 0) {n /= 2;sum++;} else {n -= 1;sum++;}}cout << sum << endl;return 0;
}

D.小蓝的二进制询问

题意

就是给你l和r，求区间二进制1的个数

思路

考虑每一位二进制位的贡献。算出1到R的贡献减去1到L-1的贡献，就是L到R的贡献
从低位往高位枚举x的二进制位，简单枚举一下1到15的二进制可以发现，第0位是每2次出现一个1，第1位是每4次出现2个1，第2位是每8次出现4个1，可以看出，对于每一位，画红框的地方是每一位的循环节，第 k 位的循环节长度为2k+1,其中有2k个1，所以我们可以按位枚举，计算每一位上总共有多少个循环节和剩下非循环节中 1 的个数，因为这里是从 0 开始计算每一行的长度，所以实际计算时 x 需要加 1

代码

int mod=998244353;
int f(int x){int ans=0,a=2;x++;while(x>=a/2){ans=(ans+(x/a)*(a/2))%mod;//循环节里面1的个数if(x%a!=0) ans=(ans+max(0ll,x%a-(a/2)))%mod;//非循环节1的个数a*=2;}return ans;
}
void solve(){int l,r;cin >> l >> r;cout << (f(r)-f(l-1)+mod)%mod << endl;return ;
}

H.两难抉择

题意

选择一个操作然后使数组和最大
操作1：选1~ n中的数让a_i=a_i+n
操作2：选1~ n中的数让a_i=a_i*n

思路

先把数组最大值找出来如果最大值是1就选操作1，反之让最大的数乘n

代码

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
int n, m[200010], sum = 0;bool cmp(int a, int b) {return a > b;
}signed main() {IOScin >> n;for (int i = 0; i < n; i++) {cin >> m[i];}sort(m, m + n, cmp);if (m[0] == 1) {for (int i = 0; i < n; i++) {sum += m[i];}cout << sum + n << endl;} else {for (int i = 1; i < n; i++) {sum += m[i];}cout << sum + m[0]*n << endl;}return 0;
}

F.两难抉择新编

题意

就是有两种操作，使数组的异域和最大，操作只能用一次
操作1：选1~ n/i中的数让a_i=a_i+n（n/i向下取整）
操作2：选1~ n/i中的数让a_i=a_i*n

思路

一开始比赛时我用贪心写的但一直不对，然后结束后看了别人代码暴力直接过了，就是先把数组异域和求出然后再循环数组2重循环1到n/i，就可以过了，暴力出奇迹

代码

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
int sum = 0, n, m[200010], ma = 0;signed main() {IOScin >> n;for (int i = 1; i <= n; i++) {cin >> m[i];sum ^= m[i];}for (int i = 1; i <= n; i++) {for (int j = 1; j <= n / i; j++) {int x = sum ^ m[i] ^ (m[i] * j);if (x > ma)ma = sum ^ m[i] ^ (m[i] * j);int y = sum ^ m[i] ^ (m[i] + j);if (y > ma)ma = sum ^ m[i] ^ (m[i] + j);}}cout << ma << endl;return 0;
}

G.旅途的终点

题意

有一个冒险家要去旅游，但每去一个国家都要消耗一些血量，如果血量小于等于0，旅游就终止，但冒险家有k次魔法，用一次就可以在当前国家不消耗血量，求最多可以畅游多少个国家

思路

其实这个题用的是反悔贪心，就是先让消耗血量然后用最大堆维护一下，当血量小于等于0时消耗一次魔法，把最大堆中之前消耗最多的血量再加回来就行了

代码

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
int n,m,k,a[200100],t=0;
priority_queue<int> q;
signed main()
{IOSint T=1;//cin>>T;while(T--){cin>>n>>m>>k;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){t=i;q.push(a[i]);if(m-a[i]<=0){if(k==0){t=t-1;break;}else {m-=a[i];while(m<=0){m=m+q.top();q.pop();k--;if(k==0)break;}}}else{m-=a[i];}}cout<<t<<endl;}return 0;
}

I.除法移位

题意

有一个数组，有t次操作可以把数组中的数往后移一位a_n变成a₁求用尽可能少的操作让
a₁/a₂/a₃/a₄…/a_n尽可能小

思路

我们知道除以一个数等于乘以它的倒数，所以就是用有限的t步让他变小，就是尽可能的让a₁更大

代码

#include <bits/stdc++.h>
//#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;int main() {//IOSint n, t, l = 0, x =1;cin >> n >> t;double sum = 1, ma;int m[200010];for (int i = 1; i <= n; i++)cin >> m[i];for (int i = 1; i <= n; i++) {sum = sum / m[i];}ma = sum * m[1];for (int i = 2; i <= n; i++) {if (sum * m[i] > ma && n - x <= t) {ma = sum * m[i];l = n - x;}x++;}cout << l << endl;return 0;
}

K.图上计数(Easy)

题意

给你n个点和m个边让联通块合成一个图的代价尽可能的大，最后剩下两个联通块大小的乘积为此图的代价，若只有一个则代价为0

思路

这个题其实我们不用管边数，因为可以无数次删除边，我们先把所有的边都删除，然后连接成两个联通块，我们要使两个联通块的值尽可能相近，这样才能让两个联通块的乘积尽可能大

代码

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;signed main() {IOSint m, n, a, b;cin >> m >> n;for (int i = 1; i <= n; i++) {cin >> a >> b;}if (m == 1)cout << 0 << endl;else {cout << m / 2 * (m - m / 2) << endl;}return 0;
}

题目链接