文章目录
- A.造数
- 题意:
- 思路
- H.两难抉择
- 题意:
- 思路
- K.图上计数(Easy)
- 题意:
- 思路
- I.除法移位
- 题意:
- 思路
- L.两难抉择新编
- 题意:
- 思路
- G.旅途的终点
- 题意:
- 思路
- D.小蓝的二进制询问
- 题意:
- 思路
A.造数
一个签到题,比较简单,但是我30min才A了,还WA了一发,不太行,有点影响后面的题了
题意:
给定一个整数 𝑛,你可以进行以下三种操作:
操作1:+1 操作2:+2 操作3:×2 至少需要几步可以把0变成n
思路
通过观察几个样例发现17由16变最快,16由8变最快,8由4变最快,4由2变最快。2到0一步就可以。所以当n为17时,结果是5;因此我们就可以用循环来不断的靠近2或者1来解决
#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define fi first
#define se second
#define PII pair <int,int>
#define ALL(x) x.begin(),x.end()
#define lowbit(x) (x&(-x))
using namespace std;
const int N = 1e6+5;
int a[N],b[N];void solve () {int n;cin>>n;if (n==1) {cout<<1<<'\n';return;}if (n==2) {cout<<1<<'\n';return ;}if (n==0) {cout<<0<<'\n';return;}//这前面都是一些特判,当然这题1,2,不用特判,因为我循环里面判过了int ans=0; if (n&1) {ans++;n--;}while (1) {ans++;if (n==1||n==2) break;if (n&1) n--;else n/=2;}cout<<ans;
}signed main () {IOS;int T =1;
// cin>>T;while(T--) solve ();return 0;
}
H.两难抉择
题意:
有两次操作:
- 从 i ∈ ( 1 , n ) i\in(1,n) i∈(1,n)里面选一个 a i = a i ∗ x , x ∈ [ 1 , n ] a_i=a_i*x,x\in[1,n] ai=ai∗x,x∈[1,n]
- 从 i ∈ ( 1 , n ) i\in(1,n) i∈(1,n)里面选一个 a i = a i + x , x ∈ [ 1 , n ] a_i=a_i+x,x\in[1,n] ai=ai+x,x∈[1,n]
操作一次后,序列的总和最大是多少?
思路
将数组先降序排序,看最大的是否为1,如果为1的话就进行2操作,否则进行1操作,最后再遍历一遍输出总和。
#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define fi first
#define se second
#define PII pair <int,int>
#define ALL(x) x.begin(),x.end()
#define lowbit(x) (x&(-x))
using namespace std;
const int N = 1e6+5;
int a[N],b[N];void solve () {int n;cin>>n;for (int i=1;i<=n;i++) {cin>>a[i];}if (n==1) {cout<<a[1]+1;return ;}sort (a+1,a+1+n,greater<int>());if (a[1]==1) {a[1]+=n;}else a[1]*=n;int sum=0;for (int i=1;i<=n;i++) sum+=a[i];cout<<sum;
}signed main () {IOS;int T =1;
// cin>>T;while(T--) solve ();return 0;
}
K.图上计数(Easy)
题意:
思路
这一题说实话,没咋看懂,图的部分还没咋学,但是凭借我闯荡牛客那么久就知道这题不难,所以我直接就对半砍,然后再相乘
#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define fi first
#define se second
#define PII pair <int,int>
#define ALL(x) x.begin(),x.end()
#define lowbit(x) (x&(-x))
using namespace std;
const int N = 1e6+5;
int a[N],b[N];void solve () {int n,m;cin>>n>>m;for (int i=1;i<=m;i++) {int x,y;cin>>x>>y;}if (n%2==0) {int ans=(n/2)*(n/2);cout<<ans;}else {int ans=(n/2+1)*(n/2);cout<<ans;}
}signed main () {IOS;int T =1;
// cin>>T;while(T--) solve ();return 0;
}
I.除法移位
题意:
式子S被定义如下
现在可以将序列往右移动t次,问怎么移动使式子S的值最大
思路
由数学知识我们可以知道当被除数越大,除数越小的时候值最大,所以我们尽可能让第一个数最大,但是由于t次移动的限制,我们可能做不到将第一个数变成最大的,因此我们用一个数组来存放每个数字移动到最左边的步数,再将数组排个序,在t允许的情况下,我们首先考虑最大的移动。
#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define fi first
#define se second
#define PII pair <int,int>
#define ALL(x) x.begin(),x.end()
#define lowbit(x) (x&(-x))
using namespace std;
const int N = 1e6+5;
//int a[N],b[N];
struct qwe
{int x,y;
}a[N];bool cmp (qwe A,qwe B) {if (A.x==B.x) return A.y<B.y;else return A.x>B.x;
}void solve () {int n,t;cin>>n>>t;for (int i=1;i<=n;i++) {cin>>a[i].x;if (i==1) a[i].y=0;else a[i].y=n-i+1;}sort (a+1,a+1+n,cmp);for (int i=1;i<=n;i++) {if (a[i].y<=t) {cout<<a[i].y;break;}}
}signed main () {IOS;int T =1;
// cin>>T;while(T--) solve ();return 0;
}
L.两难抉择新编
和H题差不多,但是这一题考到了一个异或就是^这个符号,异或的详细知识去书上看看。
题意:
同样是有两次操作,只能进行一次操作:
- 从 i ∈ ( 1 , n ) i\in(1,n) i∈(1,n)里面选一个 a i = a i ∗ x , x ∈ [ 1 , n / i ] a_i=a_i*x,x\in[1,n/i] ai=ai∗x,x∈[1,n/i]
- 从 i ∈ ( 1 , n ) i\in(1,n) i∈(1,n)里面选一个 a i = a i + x , x ∈ [ 1 , n / i ] a_i=a_i+x,x\in[1,n/i] ai=ai+x,x∈[1,n/i]
操作一次后,序列的总和最大是多少?
和H题不一样的是x的值在发生变化从 [ 1 , n ] [1,n] [1,n]变到 [ 1 , n / i ] [1,n/i] [1,n/i]
思路
我们可以直接通过异或的特殊性质直接遍历,暴力求解,将第一个 a 1 a_1 a1特殊求解一下,因为 a 1 a_1 a1的情况下x的范围是 [ 1 , n ] [1,n] [1,n],如果不单独考虑的话就会超时
#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define fi first
#define se second
#define PII pair <int,int>
#define ALL(x) x.begin(),x.end()
#define lowbit(x) (x&(-x))
using namespace std;
const int N = 1e6+5;
int a[N],b[N];void solve () {int n;cin>>n;int pos=0;int mm=0,j;for (int i=1;i<=n;i++) {cin>>a[i];pos=a[i]^pos;}int qwe;int ma=0;int asd=pos^a[1];int mmm=0;for (int i=1;i<=n;i++) {int zxc1=a[1]*i;int zxc2=a[1]+i;int zxc3=zxc1^asd;int zxc4=zxc2^asd;mmm=max({zxc3,zxc4,mmm});}for (int i=2;i<=n;i++) {int asd=pos^a[i];for (int j=1;j<=n/i;j++) {int zxc1=a[i]*j;int zxc2=a[i]+j;int zxc3=zxc1^asd;int zxc4=zxc2^asd;mmm=max({zxc3,zxc4,mmm});}}cout<<mmm;
}signed main () {IOS;int T =1;
// cin>>T;while(T--) solve ();return 0;
}
G.旅途的终点
赛时没有看的一道题,但也不难,考的就是一个反悔贪心。
题意:
给定3个整数 n , m , k n,m,k n,m,k,分别代表国家的个数,你拥有的初始生命力,你可以释放神力的次数。下方有 a i a_i ai,每经过一个国家都要付出相应的体力,只有通过这个国家时体力大于0才能通过。但是有k次释放神力的机会,释放神力不需要消耗体力,问最多能通过几个国家
思路
前面一直不释放神力,每通过一个国家,体力就相应减少多少,当体力小于等于0的时候,开始对前面释放神力,对前面消耗体力最大的地方释放神力。用一个优先队列存放前面消耗的体力,当体力不支的时候,释放神力,体力加上队列的首项。
#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define fi first
#define se second
#define PII pair <int,int>
#define ALL(x) x.begin(),x.end()
#define lowbit(x) (x&(-x))
using namespace std;
const int N = 1e6+5;
int a[N],b[N];void solve () {int n,m,k;cin>>n>>m>>k;for (int i=1;i<=n;i++) {cin>>a[i];}priority_queue<int>q;int ans=0;for (int i=1;i<=n;i++) {m-=a[i];q.push(a[i]);if (m<=0) {if (k==0) break;k--;m+=q.top();q.pop();}ans++;}cout<<ans;
}signed main () {IOS;int T =1;
// cin>>T;while(T--) solve ();return 0;
}
D.小蓝的二进制询问
一道规律题,比较难看出来啥规律,要打表才能好看出来
题意:
给出l,r,求这个区间里面二进制中1的总和
思路
通过打表我们可以发现1的出现是有规律的,直接用规律代入求解即可。
虽然但是,这个规律是比较难看出来的,
#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define fi first
#define se second
#define PII pair <int,int>
#define ALL(x) x.begin(),x.end()
#define lowbit(x) (x&(-x))
using namespace std;
const int N = 1e6+5;
const int mod =998244353;
int a[N],b[N];int asd (int x) {int t=0;while (x) {x/=2;t++;}return t;
}int qwe (int x) {int cnt= asd (x);x++;int ans=0;for (int i=1;i<=cnt;i++) {int pos=pow(2,i);ans+=(x/pos)*(pos/2);ans%=mod;ans+=max(0ll,x%pos-pos/2);ans%=mod;}return ans;
}void solve () {int l,r;cin>>l>>r;cout<<(qwe(r)-qwe(l-1)+mod)%mod<<'\n';return ;
}signed main () {IOS;int T =1;cin>>T;while(T--) solve ();return 0;
}