您的位置:首页 > 娱乐 > 明星 > 河南萌新联赛2024第(一)场:河南农业大学

河南萌新联赛2024第(一)场:河南农业大学

2024/10/14 11:19:11 来源:https://blog.csdn.net/2302_81590667/article/details/140503272  浏览:    关键词:河南萌新联赛2024第(一)场:河南农业大学

文章目录

  • A.造数
    • 题意
    • 思路
    • 代码
  • D.小蓝的二进制询问
    • 题意
    • 思路
    • 代码
  • H.两难抉择
    • 题意
    • 思路
    • 代码
  • F.两难抉择新编
    • 题意
    • 思路
    • 代码
  • G.旅途的终点
    • 题意
    • 思路
    • 代码
  • I.除法移位
    • 题意
    • 思路
    • 代码
  • K.图上计数(Easy)
    • 题意
    • 思路
    • 代码
  • 题目链接

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中的数让ai=ai+n
操作2:选1~ n中的数让ai=ai*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中的数让ai=ai+n(n/i向下取整)
操作2:选1~ n/i中的数让ai=ai*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次操作可以把数组中的数往后移一位an变成a1求用尽可能少的操作让
a1/a2/a3/a4…/an尽可能小

思路

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

代码

#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;
}

题目链接