【普及组】

【P1372】又是毕业季I

这k个数就是x,x*2,...,x*k，所以符合条件的x即为答案，x*k<=n,x<=n/k，因此答案即n/k。

#include<bits/stdc++.h>
using namespace std;
int n,k;
int main(){
    scanf("%d%d",&n,&k);
    printf("%d
",n/k);
    return 0;
} 

【P1338】末日的传说

题意是求1~n的排列中字典序最小的满足m个逆序对的排列。

n个数字最多存在n*(n-1)/2对逆序对，那么考虑每个数i的位置，剩下的n-i个数最多存在逆序对对数为(n-i)(n-i-1)/2，若此对数大于等于m，则直接输出当前排序；否则把i放在排列末尾使得字典序最小，这样会产生n-i对逆序对，将m更新为m-(n-i)即可。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,q[50005],tmp,cnt,num;
int main(){
    cin>>n>>m;num=n;
    for(int i=1;i<=n;i++){
        tmp=(n-i)*(n-i-1)/2;
        if(tmp>=m) q[++cnt]=i;
        else q[num--]=i,m-=(n-i);
    }
    for(int i=1;i<=n;i++) cout<<q[i]<<' ';
    return 0;
}

【P1582】倒水

用二进制表示，因为所有的水都是由两份相同的水合并成的，因此每瓶水的体积一定是2的x次方升。最后保留的k个瓶子，那么最后总的二进制数中1的个数不超过k，用lowbit解决。__builtin_popcount(x)返回一个二进制数中有多少1。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,k,ans;
int main(){
    cin>>n>>k;
    while(__builtin_popcount(n)>k) ans+=n&-n,n+=n&-n;
    cout<<ans<<endl;
    return 0;
}