这里写目录标题
A 造数
题意:
给一个整数n,求出最少的操作数使0转化为n
有三种操作方式:
- +1
- +2
- *2
解题思路:
我们可以将基础的1,2,3分别需要1,1,2次操作,
当n大于3时,若n为偶数,则将n=n/2,如果n为奇数,则将操作数加一,n=(n-1)/2
,循环进行直到n小于等于3时,加上相应的基础操作数,即可得到操作次数
解题代码:
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
int a[10000];
signed main()
{
IOS
// int t;
// cin>>t;
// while(t--)
// {
int n,t=0,p=0;
cin>>n;
a[1]=1;
a[2]=1;
a[3]=2;
if(n==0)
cout<<"0"<<endl;
else if(n<=3)
cout<<a[n]<<endl;
else
{
while(n>3)
{
if(n%2==1)
p++;
n=n/2;
t++;
}
cout<<t+a[n]+p<<endl;
}
// }
return 0;
}
D 小蓝的二进制询问
题意:
有 t 组询问,每次给定两个数字l,r 计算出区间 [l,r] 中所有整数在二进制下1的个数之和。
结果对998244353取模
解题思路:
由于二进制下的0,1出现是有规律的,倒着看,第一位是0,1,0,1…交互出现,第二位则是0,0,1,1,0,0,1,1,第三位是0,0,0,0,1,1,1,1…
由此我们可以发现规律,第k位是2k-1个0与2k-1个1为一次循环,交替出现
我们可以用前缀和找到每个数及以前所有数的出现过1的和,最终区间l,r则为a[r]-a[l]
解题代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
int js(int l)
{
int sum=0,t=2;
l+=1;
while(t<2*l)//当t<2*l,即在下半周期才会出现1
{
sum+=l/t*t/2;
if(l%t-t/2>0)//当不满一周期的出现在下半周期才会有1出现
sum+=l%t-t/2;
sum%=mod;
t*=2;
}
if(l==1) return 0;
return sum%mod;
}
void solve()
{
int l,r;
cin>>l>>r;
l=js(l-1);
r=js(r);
cout<<(r-l+mod)%mod<<endl;
}
signed main()
{
int p;
cin>>p;
while(p--)
solve();
}
F 两难抉择新编
题意:
给出长度为n的数组a,你可以在下列两项操作中选择一种进行最多一次操作:
操作1:
选择一个数i,使得a[i]=a[i]+x,x为[1,⌊n/i⌋] 范围内任意正整数( ⌊⌋ 表示向下取整 )
操作2:
选择一个数i,使得a[i]=a[i]*x,x为[1,⌊n/i⌋] 范围内任意正整数( ⌊⌋ 表示向下取整 )
求出操作后最大的数组异或和.
解题思路:
异或有自反性:A ^B ^B=A
在这个数组中。我们可以先将数组全部异或
然后遍历,在遍历到一个元素时,应用其自反性,先对其异或,然后将该元素中每一个可以出现的数分别异或,取最大值
解题代码:
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
int a[200010];
signed main()
{
IOS
int n,sum=0;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum=sum^a[i];
}
int t=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n/i;j++)
{
t=max(t,sum^a[i]^(a[i]+j));
t=max(t,sum^a[i]^(a[i]*j));
}
}
cout<<t<<endl;
return 0;
}
G 旅途的终点
题意:
地面上有n个国家,去每个国家都需要消耗a[i]点生命力使其恢复太平,以便畅游,但你具有k次释放神力的机会,在旅行中你有m点生命力,用完则不可继续畅游国家,
注:在当前国家消耗完生命力则意味着你并没有畅游该国家。
解题思路:
这是一道返回贪心的题,我们先将前k个国家用神力畅游,放入优先队列
当畅游第i个国家,i>k时,我们将队列中需要消耗最小生命力的改为消耗生命力,使sum++,将其弹出队列,第i个国家来使用神力,并且将其推进队列
当sum>=m时,我们则不可用生命力畅游队列中的国家,只能用神力,因此我们不能继续用神力畅游第i个国家,最后i-1即为可畅游的国家
如果sum一直小于m。则证明可以畅游n个国家,输出n即可
解题代码:
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
ll a[200010];
priority_queue<ll,vector<ll>,greater<ll> >q;
int main()
{
IOS
ll n,m,k,r=0;
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
ll sum=0;
for(int i=1;i<=n;i++)
{
q.push(a[i]);
if(q.size()>k)
{
sum+=q.top();
q.pop();
}
if(sum>=m)
{
cout<<i-1<<endl;
r=1;
break;
}
}
if(r==0)
cout<<n<<endl;
return 0;
}
H 两难抉择
题意:
给出长度为n的数组a,你可以在下列两项操作中选择一种进行最多一次操作:
操作1:
选择一个数i,使得a[i]=a[i]+x,x为[1,n]范围内任意正整数
操作2:
选择一个数i,使得a[i]=a[i]*x,x为[1,n]范围内任意正整数
求出操作后最大的数组总和.
解题思路:
想要得到最大的数组总和,应该让数组中最大的值max进行操作
无论哪个操作,x的值取得越大,操作后数组总和越大,所以x应取n,
然后将max分别进行操作1,2,取操作后较大值,最后计算出数组总和即可。
解题代码:
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
int a[200010];
signed main()
{
IOS
int n;
cin>>n;
int max=-1,sum=0;
for(int i=0;i<n;i++)
{
cin>>a[i];
if(a[i]>max)
max=a[i];
sum=sum+a[i];
}
int sum2=sum+n;
sum=sum-max+max*n;
if(sum<sum2)
sum=sum2;
cout<<sum<<endl;
return 0;
}
I 除法移位
题意:
有长度为n的数组a,我们可以对数组进行循环右移操作:
一次循环操作会使数组a[1],a[2],a[3]…a[n]变为a[n],a[1],a[2]…a[n-1]
式子s=a[1]/a[2]/a[3]…/a[n],求出在t次操作的范围内,使s值最大的最小操作数。
解题思路:
s的值为a[1]/(a[2]* a[3] *…*a[n]),要使s值最大,应让分子即数组第一个数尽量大
由于有最大操作数限制,所以只有操作t>=n-1时,我们可以取整个数组的最大值
当t<n-1时,我们应该取下标为n-t+1到n的最大值,由于这个操作是从最后移动,所以当有多个最大值时,应该取数组中靠后的那一个
如果最初的数组的首元素也为最大值,则无需进行操作,即操作数为0
解题代码:
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
int a[200010];
signed main()
{
IOS
int n,m,r;
cin>>n>>m;
if(m>=n)
r=1;
else
r=n-m+1;
int ma=0;
int t;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(i>=r)
{
if(a[i]>=ma)
{
ma=a[i];
t=i;
}
}
}
if(a[1]>=ma)
t=1;
if(t==1)
cout<<0<<endl;
else
cout<<n-t+1<<endl;
return 0;
}
K 图上计数(Easy)
题意:
图中有n个顶点,m条边,可以进行无数次删除操作来删除任意条边以获得若干个联通块。
定义联通块的大小为其所包含点个数。
定义这个图的代价是:你有任意次操作,每次操作合并两个联通块,合并后联通块大小为二者之和,最后剩下两个联通块大小的乘积为此图的代价,若只有一个则代价为0。你需要最大化此图代价。
解题思路:
代价为两个两个连通块大小的乘积,连通块的大小即为顶点数
因此,我们只需将顶点分为两部分,然后使得两部分乘积最大
要使一个数n分为两部分使得乘积最大,则两个值分别为n/2, n-(n/2)
解题代码:
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
signed main()
{
IOS
int n,m;
cin>>n>>m;
int p=n/2;
int q=n-p;
cout<<p*q<<endl;
return 0;
}