造数
\(25-24-12-6-3-2-0\)
\(11-10-5-4-2-0\)
1.观察上面的例子可以发现，每个数如果是偶数直接除二，如果是奇数就减一，这样得到的次数最少
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin(),v.end()
int dx[]={0,1,-1,0};
int dy[]={-1,0,0,1};
int a[35];
void solve()
{
int n;cin>>n;
int res=0;
while(n>2)
{
if(n%2!=0)
{
res++;
n--;
continue;//这个continue别忘了 不然res会多加一次
}
n/=2;
res++;
}
if(n==2||n==1) res++;
cout<<res;
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0);
int t=1;
//cin>>t;
while(t--) solve();
return 0;
}
两难抉择
1.判断一下从大到小排序后的第一个元素，在操作1下大，还是操作2下大即可
2.但是别把操作中的x当成ve【0】了，x的范围是【1，n】，而不是【a1，an】
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
int dx[]={0,1,-1,0};
int dy[]={-1,0,0,1};
int a[35];
void solve()
{
int n;cin>>n;
int sum=0;
vector<int>ve(n);
int fla=0;
for(int i=0;i<n;i++) {
cin>>ve[i];
}
sort(allr(ve));
if(ve[0]*n>(ve[0]+n)){
ve[0]=ve[0]*n;
}
else ve[0]=ve[0]+n;
for(int i=0;i<n;i++) sum+=ve[i];
cout<<sum;
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0);
int t=1;
//cin>>t;
while(t--) solve();
return 0;
}
图上计数(Easy)
1.直接算有几个顶点，然后这些顶点分为两部分乘积要最大，偶数则为（n/2）✖️（n/2），奇数则为（n/2）✖️（n/2+1）
void solve()
{
int n,m;
cin>>n>>m;
int ans=0;
while(m--)
{
int xx,yy;cin>>xx>>yy;
}
if(n&1) ans=(n/2)*(n/2+1);
else ans=(n/2)*(n/2);
cout<<ans;
}
除法移位
1.其实本质上也是个贪心，找能够移动的依次最大数即可，就是按从大到小找，尽量把大的往第一位挪即可
2.但是注意重复数这种情况，比如1 2 9 9 8，应该移动后面这个次数更少，当然这题是因为我的排序方式需要考虑这个
3.我是以点对的方式，x存值，y存位置，然后按照从大到小派，值相同按照序号从大到小排，然后按顺序遍历找满足条件的即可
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin(),v.end()
int dx[]={0,1,-1,0};
int dy[]={-1,0,0,1};
int a[35];
bool cmp(pii a,pii b)
{
if(a.x!=b.x)return a.x>b.x;
return a.y>b.y;
}
void solve()
{
int n,m; cin>>n>>m;
vector<pii>ve(n);
for(int i=0;i<n;i++)
{
cin>>ve[i].x;
ve[i].y=i;
}
sort(all(ve),cmp);
int ans=0;
if(ve[0].y==0){
cout<<0;
return;
}
for(int i=0;i<n;i++)
{
if(ve[i].y!=0&&n-ve[i].y<=m){
ans=n-ve[i].y;
break;
}
}
//for(auto t:ve) cout<<t.x<<" "<<t.y<<endl;
cout<<ans;
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0);
int t=1;
//cin>>t;
while(t--) solve();
return 0;
}
两难抉择新编
1.当n最大为2e5时，总的次数也才2472133，所以肯定满足暴力的条件
2.其次就是异或的一些小知识要知道，两个相同的数异或，相当于消除这个数
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin()+1,v.end()
int dx[]={0,1,-1,0};
int dy[]={-1,0,0,1};
void solve()
{
int n; cin>>n;
int sum=0;
vector<int>ve(n+1);
for(int i=0;i<n;i++)
{
cin>>ve[i];
sum^=ve[i];
}
int ans=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n/i;j++)
{
ans=max(ans,sum^ve[i-1]^(ve[i-1]+j));//两个相同的数异或为0相当于把a【i-1】转化为a【i-1】+j
ans=max(ans,sum^ve[i-1]^(ve[i-1]*j));
}
}
cout<<ans;
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0);
int t=1;
//cin>>t;
while(t--) solve();
return 0;
}
旅途的终点
1.贪心的思想，用k次把耗费体力多的遍历掉，然后再检查遍历到多少个国家时sum>=m即可
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
int dx[]={0,1,-1,0};
int dy[]={-1,0,0,1};
void solve()
{
int n,m,k; cin>>n>>m>>k;
vector<int>ve(n);
priority_queue<int,vector<int>,greater<int> >q;
for(int i=0;i<n;i++){
cin>>ve[i];
}
int sum=0;
for(int i=0;i<n;i++)
{
q.push(ve[i]);
if(q.size()>k)//因为队列是从小到大，当放的个数大于k个相当于这k个放到底部了
{//所以当国家数少于k个时，直接遍历完输出n了
sum+=q.top();
q.pop();
}
if(sum>=m)
{
cout<<i;
return;
}
}
cout<<n;
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0);
int t=1;
//cin>>t;
while(t--) solve();
return 0;
}