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