A.造数
题目：
链接：https://ac.nowcoder.com/acm/contest/86639/A
思路：
签到题，特判如果n=0，输出0，如果n=1或2，输出1；while循环，首先如果n%2!=0，那么s++，然后n/2,s++，知道n<=2时，停止，输出s。
AC代码：
#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,s=0;
cin>>n;
if(n==0)
cout<<"0"<<'\n';
else if(n==1||n==2)
cout<<"1"<<'\n';
else
{
while(n>=2)
{
if(n%2!=0)
s++;
n=n/2;
s++;
//cout<<n<<'\n';
}
cout<<s<<'\n';
}
return 0;
}
F.两难抉择新编
题目:
有一个数组，可以进行两种操作：
操作一：选择一个数i(1<=i<=n)，使得a[i]:=a[i]+x，x是[1,n/i]范围内的正整数。
操作二：选择一个数i(1<=i<=n)，使得a[i]:=a[i]*x，x是[1,n/i]范围内的正整数。
进行操作后数组相加最大为多少，只能执行一次操作。
思路：
用了一个^，意思是异或后再转化为二进制后的值，用循环分别求出两个操作后与原数组最大的异或值，跟H题差不多。
AC代码：
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int N=2e5+20;
int a[N];
signed main()
{
IOS
int n,s=0;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
s=s^a[i];
}
int dd=0;
for(int i=0;i<n;i++)
{
for(int j=1;j<=n/(i+1);j++)
{
dd=max(dd,s^a[i]^(a[i]+j));
dd=max(dd,s^a[i]^(a[i]*j));
}
}
cout<<dd<<'\n';
return 0;
}
G.旅途的终点
题目：
链接：https://ac.nowcoder.com/acm/contest/86639/G
来源：牛客网
思路：
用队列，弹出最小，依次推入，当数量大于k时，s加上此时的最小，删除头项，如果s>=m，输出此时的i，如果全推完了也没有大于等于，则输出n。
AC代码：
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int N=2e5+20;
vector<int> a(N);
priority_queue<int,vector<int>,greater<int> > q;
signed main()
{
IOS
int n,m,k,s=0;
cin>>n>>m>>k;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
for(int i=0;i<n;i++)
{
q.push(a[i]);
if(q.size()>k)
{
s+=q.top();
q.pop();
}
if(s>=m)
{
cout<<i<<'\n';
return 0;
}
}
cout<<n<<'\n';
return 0;
}
H.两难抉择
题目：
有一个数组，可以进行两种操作：
操作一：选择一个数i(1<=i<=n)，使得a[i]:=a[i]+x，x是[1,n]范围内的正整数。
操作二：选择一个数i(1<=i<=n)，使得a[i]:=a[i]*x，x是[1,n]范围内的正整数。
进行操作后数组异或和最大为多少，只能执行一次操作。
思路：
定义三个数组，一个是题目输入数组a，其中一个数组b用来储存a数组中分别进行操作一再减去对应a中的数，同理，c数组操作二，这样是求操作后在原来和基础上增加了多少，把b,c数组sort排序，求出最大的一个数，然后用a数组的和再加上这个数就可以了。一开始没有认真读题，导致错了两发。
AC代码：
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int N=2e5+10;
int a[N],b[N],c[N];
signed main()
{
IOS
int n,s=0;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
for(int i=0;i<n;i++)
{
//cout<<a[i]<<" "<<'\n';
b[i]=(a[i]*n)-a[i];
c[i]=(a[i]+n)-a[i];
}
sort(b,b+n);
sort(c,c+n);
int dd=max(b[n-1],c[n-1]);
for(int i=0;i<n;i++)
{
s+=a[i];
}
cout<<s+dd<<'\n';
// int t1=a[n-1]*a[n-1];
// int t2=a[n-1]+a[n-1];
// int c=max(t1,t2);
// for(int i=0;i<n-1;i++)
// {
// s+=a[i];
// }
// cout<<s+c<<'\n';
return 0;
}
I.除法移位
题目：
一个数组，每次可以往右移一位，例a1,a2,a3移完后是a3,a1,a2，求a1/a2/a3/……/an的最大值，注意是正常除法，不降位。移动次数有限制。
思路：
如果数组长度小于可移动次数，秩序从后往前遍历，找出数组中最大的数，然后用n减就可以，如果大于，那么如果最大的数n减之后大于可移动次数的话，就找第二大的，依次类推，小于可移动次数是结束，输出。
AC代码：
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int N=2e5+20;
int a[N],b[N];
signed main()
{
IOS
int n,t,ss=0;
cin>>n>>t;
for(int i=0;i<n;i++)
{
cin>>a[i];
b[i]=a[i];
}
sort(b,b+n);
//cout<<b[n-1]<<'\n';
if(a[0]==b[n-1])
cout<<"0"<<'\n';
else
{
if(n<=t)
{
for(int i=n-1;i>=0;i--)
{
if(a[i]==b[n-1])
{
ss=i;
break;
}
}
cout<<n-ss<<'\n';
}
else
{
int qq=n,dd,f=1;;
//cout<<b[qq-2]<<'\n';
for(int i=n-1;i>=0;i--)
{
if(a[i]==b[qq-1])
{
ss=i;
f=0;
//cout<<i<<'\n';
}
if(f==0)
{
dd=n-ss;
if(dd<=t)
{
// cout<<i<<'\n';
// cout<<a[n-1]<<'\n';
//cout<<b[qq-1]<<'\n';
//cout<<ss<<'\n';
cout<<dd<<'\n';
break;
}
else
{
//cout<<"1"<<'\n';
i=n;
qq=qq-1;
}
f=1;
}
}
//cout<<ss<<'\n';
}
}
}
K. 图上计数(Easy)
题目：
思路：
一开始没看懂题目，就跳过去了，后来又理解错了，费了挺长时间的，其实特别简单，因为是无限次，至于要让两个数相加等于n，相乘最大就可以了。
AC代码：
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int N=2e6;
int a[N];
signed main()
{
IOS
int n,m,u,v;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>u>>v;
//a[i]=abs(v-u)+1;
}
// if(m==0||m==1)
// cout<<"0"<<'\n';
// else
// {
int dd=n/2;
int ddd=n-dd;
cout<<dd*ddd<<'\n';
// sort(a,a+m);
// cout<<a[m]*a[m-1]<<'\n';
// }
// for(int i=0;i<m;i++)
// cout<<a[i]<<" ";
// int s=0;
// for(int i=1;i<=m;i++)
// s+=i;
// //cout<<s<<'\n';
// if(s%2!=0)
// cout<<"0"<<'\n';
// else
// cout<<a[1]*a[2]<<'\n';
return 0;
}
