河南萌新联赛2024第（一）场：河南农业大学 A D F G H I K

A 造数

题目描述：

给定一个整数 ???? ，你可以进行以下三种操作
操作1： +1
操作2； +2
操作3： ×2
问最少需要多少次操作可以将 0 转为为 ???? 。

解题思路

操作1，2，3。操作 3 的使 n 变小的更快。

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 n;cin>>n;
    int ans=0;
    while(n)
    {
        if(n==1||n==2)//操作1，操作2 的 逆过程
        {
            ans++;
            break;
        }
        if(n%2==1) //操作 1 的逆过程
        {
            n--;
            ans++;
        }
        else // 操作 3 的逆过程
        {
            n/=2;
            ans++;
        }
    }
    cout<<ans;
}
signed main()
{
	int t;
	t=1;
	while(t--)solve();
	return 0;
}

D 小蓝的二进制询问

题目描述

小蓝有 ???? 组询问，每次给定两个数字 l,r 你需要计算出区间 [????,????] 中所有整数在二进制下1的个数之和。由于结果特别大，你只需要计算出结果模998244353之后的值即可。

解题思路

求出区间 [ 0 , x ] 之间的数的二进制下数的第 k 位是 1 时的所有情况

1.第 k 位前的数 为 k ^ 2 的倍数（周期 tl 的倍数），这时第 k 位后全为 0
2. 第 k 位以及第 k 位后的数（为第 1 种情况的余数就是认定为 0 的数，实际不一定为 0 ）如果大于周期，则加上大出的部分，否则不加

AC代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
int f(int x,int k)
{
    int y=1ll<<(k+1);// 2 的 k + 1 次幂，用于求出 x 的周期倍数
    int tl=y/2;// 周期（当第 k 位为 1 时，k 位之后为 0 1 的所有情况）
    x++;// 自增，用于后续判断 第 k 位 是否为 1 
    int res=(int)(x/y)*tl;// 计算出第一种情况
    int r=x%y; //求出第 k 位到 0 位的数
    r-=tl;
    if(r>0)res+=r;//计算第 2 种情况
    return res%mod;
}
void solve()
{
    int l,r;cin>>l>>r;
    int ans=0;
    for(int i=61;i>=0;i--)
    {
        int t=(f(r,i)-f(l-1,i))%mod;// 第 i 位为 1 时，[0 ,r] 与 [0,l-1] 的情况差
        ans=(ans+t)%mod;
    }
    cout<<ans<<'\n';
}
signed main()
{
    int t;cin>>t;
    while(t--)solve();
    return 0;
}

F 两难抉择新编

题目描述

现在有长度为 $n$ 的数组 $a$，你可以在两种操作中选择一种进行最多一次操作。

• 操作1:

选择一个数 $i$ $(1\le i\le n)$ 使得 $a_i:=a_i+x$，$x$ 可以是 $[1,\lfloor n/i\rfloor ]$ 范围内任意正整数（ $\lfloor \rfloor$ 表示向下取整 ）。

• 操作2:

选择一个数 $i$ $(1\le i\le n)$ 使得 $a_i:=a_i\times x$，$x$ 可以是 $[1,\lfloor n/i\rfloor ]$ 范围内任意正整数。

请问进行操作后，最大的数组异或和是多少？

数组异或和：数组 $a$ 中 $a_1\oplus a_2\oplus a_3...\oplus a_n$的值，$\oplus$ 表示异或。

解题思路

直接模拟所有情况，理解异或（ ^ ）的自逆

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 PII pair<int,int>
#define fi first
#define se second
const int N=2e5+10;
int a[N];
void solve()
{
	int n;cin>>n;
    int sum=0;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        if(i==0)
        {
            sum=a[i];
            continue;
        }
        sum=sum^a[i];
    }
    int ans=0;
    for(int i=0;i<n;i++)
    {
        int t=sum^a[i];
        for(int j=1;j<=n/(i+1);j++)
        {
            int x=t^(j+a[i]),y=t^(j*a[i]);
            ans=max(ans,max(x,y));
        }
    }
    cout<<ans;
}
signed main()
{
	int t;
//	cin>>t;
	t=1;
	while(t--)solve();
	return 0;
}

G 旅途的终点

题目描绘

在某大陆上面有 $n$ 个国家，作为旅行者兼冒险家的你想以一种既定的路线（即从1到 $n$ ）去畅游这 $n$ 个国家，但由于这 $n$ 个国家并不太平，因此每到一个国家你都需要消耗 $a_i$ 点的生命力来帮助这个国家重回往日的安宁然后再进行畅游。不过天生拥有神力的你却有 $k$ 次释放神力的机会来帮助这个国家恢复安宁，且释放神力时不消耗任何生命力。你在旅行前拥有 $m$ 点的生命力，若你在旅途中不幸用完全部的生命力，则便会回到你诞生的地方陷入沉睡。现在请问你最多可以畅游多少个国家。注意：若在当前国家消耗完生命力则意味着你并没有畅游该国家。

输入

输入包含 2 行。
第一行三个正整数 $n，m，k(1\le n\le 2\times 10^5,1\le m\le 10^{18},0\le k\le 2\times 10^5)$ ，分别代表国家的个数，你拥有的初始生命力，你可以释放神力的次数。
第二行包含 $n$ 个正整数，第 $i$ 个正整数 $a_i(1\le a_i\le 10^{18})$ 代表你不释放神力帮助第 $i$ 个国家需要消耗的生命力的大小。

输出

输出包含一行，共一个数，表示你能畅游的国家的个数。

解题思路

逆贪心，用优先队列 ，需要释放技能时，每次消化当前位置到首位的最大值。

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 PII pair<int,int>
#define fi first
#define se second
const int N=2e5+10;
void solve()
{
    priority_queue<int>q;
	int n,m,k;cin>>n>>m>>k;
    int ans=0;
    int i;
    for(i=0;i<n;i++)
    {
        int x;cin>>x;
        m-=x;
        q.push(x);
        if(m<=0&&k)
        {
            k--;
            m+=q.top();
            q.pop();
        }
        if(m<=0)break;
    }
    cout<<i;
}
signed main()
{
	int t;
//	cin>>t;
	t=1;
	while(t--)solve();
	return 0;
}

H 两难抉择

题目描述

现在有长度为 $n$ 的数组 $a$，你可以在两种操作中选择一种进行最多一次操作。

• 操作1:

选择一个数 $i$ $(1\le i\le n)$ 使得 $a_i:=a_i+x$，$x$ 可以是 $[1,n]$ 范围内任意正整数。

• 操作2:

选择一个数