【题解】abc216

C

考虑从后往前推,即若此数为 14,发现能被而除尽,则 /2。7 不能除尽,则 -1。同时将这些步骤存在 stack 中,输出即可。

#include<bits/stdc++.h>
using namespace std;
long long n;
stack<char>st;
int main(){
    cin>>n;
    while(n){
        if(n%2==0){
            st.push('B');
            n/=2;
        }else{
            st.push('A');
            n-=1;
        }
    }
    while(!st.empty()){
        cout<<st.top();
        st.pop();
    } 
    return 0;
}

D

类似 BFS 的思想是最容易实现的算法。即将 cnt[num]== 2 的行都存在队列中,每次取出一组,并将这两行后面的数字提前,继续判断 cnt[num] 是否等于 2。可以认为是用 BFS 实现的模拟

#include<bits/stdc++.h>
using namespace std;
int pos[200005][2];
int n,m;
queue<int> q[200005];
int cnt[200005];
int fir[200005];
int tot=0;
int main(){
    cin>>n>>m;
    int k,tmp;
    for(int i=1;i<=m;i++){
        cin>>k;
        for(int j=1;j<=k;j++){
            cin>>tmp;
            q[i].push(tmp);
        }
    }
    queue<int> qq;
    for(int i=1;i<=m;i++){
        fir[i]=q[i].front();
        q[i].pop();
        pos[fir[i]][cnt[fir[i]]]=i;
        cnt[fir[i]]++;
        if(cnt[fir[i]]==2){
            qq.push(fir[i]);
        }
    }
    int p0,p1;
    while(!qq.empty()){
        tot+=2;
        int now=qq.front();
        qq.pop();
        cnt[now]=0;
        p0=pos[now][0],p1=pos[now][1];
        if(!q[p0].empty()){
            fir[p0]=q[p0].front();
            q[p0].pop();
            pos[fir[p0]][cnt[fir[p0]]]=p0;
            cnt[fir[p0]]++;
            if(cnt[fir[p0]]==2)qq.push(fir[p0]);
        }
        if(!q[p1].empty()){
            fir[p1]=q[p1].front();
            q[p1].pop();
            pos[fir[p1]][cnt[fir[p1]]]=p1;
            cnt[fir[p1]]++;
            if(cnt[fir[p1]]==2)qq.push(fir[p1]);
        }
    }
    if(tot==2*n){
        cout<<"Yes";
    }else{
        cout<<"No"; 
    }
    return 0;
}

E

我们很容易发现,最大的数到第二大的数中间,每个数字取一次;第二大到第三大中间每个数字取两次。

所以我们可以先把数列排序,判断 k 次之后再哪两个数字中间,设两个数字为 i,j。然后用等差数列求和公式把最大的数字到 i 之间的和算出来。剩下的 k -cnt 次取数则先判断取到哪个数,接着用同样的方法求出。最后还剩下一些次数,取的时同一个数字,则直接相乘即可。

#include<bits/stdc++.h>
using namespace std;
int n,k;
long long a[100005];
long long times[100005];
long long cnt=1;
bool cmp(long long x,long long y){
    return x>y;
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++){
        times[i]=times[i-1]+1;
    }
    for(int i=n-1;i>=1;i--){
        if(a[i]==a[i+1]){
            times[i]=times[i+1];
        }
    }
    a[n+1]=0;
    long long cnt=0;
    int pos=-1;
    for(int i=2;i<=n+1;i++){//判断位置 
        cnt+=(a[i-1]-a[i])*times[i-1];
        if(cnt>k){
            pos=i;
            break;
        }
    }
    long long ans=0;
    if(pos==-1){
        for(int i=2;i<=n+1;i++){
            ans+=(a[i-1]+a[i]+1)*(a[i-1]-a[i])/2*times[i-1];
        }
        cout<<ans;
        return 0;
    }else{
        long long cntt=0;
        for(int i=2;i<pos;i++){//将pos之前的全部求和 
            ans+=(a[i-1]+a[i]+1)*(a[i-1]-a[i])/2*times[i-1];
            cntt+=(a[i-1]-a[i])*times[i-1]; 
        }
        long long res=k-cntt;
        long long more=res/times[pos-1];
        ans+=(a[pos-1]+a[pos-1]-more+1)*more/2*times[pos-1];//求出整组的数字之和 
        long long moremore=res-more*times[pos-1];
        ans+=(a[pos-1]-more)*moremore;//求出剩下的数字之和 
        cout<<ans<<endl;
    }
    return 0;
}

或者可以考虑二分最后一个数是多少,最后处理剩下的小数量数字。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
ll a[100010],k,ans=0;
ll cal,maxi=0;
bool ok(ll x) {
    cal=0;
    for(int i=1;i<=n;++i) {
        if(a[i]<x) continue;
        cal+=a[i]-x+1;
    } 
    if(cal>=k) return true;
    else return false;
}
int main() {
    cin>>n>>k;
    for(int i=1;i<=n;++i) {
        scanf("%lld",&a[i]);
        maxi=max(maxi,a[i]);
    } 
    ll l=0,r=maxi,cnt=0,d=0;
    while(l<=r) {
        ll mid=(l+r)>>1;
        if(ok(mid)) l=mid+1,cnt=mid,d=cal;
        else r=mid-1;
    }
    for(int i=1;i<=n;++i) {
        if(a[i]<cnt) continue;
        ans+=(cnt+a[i])*(a[i]-cnt+1)/2;
    }
    printf("%lld",ans-(d-k)*cnt);
    return 0;
}

F

此题为 DP,dp[j]+=dp[j-b[i]](j 取 [b[i],5000])。并非所有都可以取,但是我们为了推 dp 需要全部取,所以边 dp,边算 ans。
ans+=dp[j-b[i]](j 取 [b[i],a[i]])。

#include<bits/stdc++.h>
using namespace std;
const int Mod=998244353;
int n;
struct kk{
    int a,b;
}k[5005];
long long dp[5005];
bool cmp(kk aa,kk bb){
    return aa.a<bb.a;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>k[i].a;
    }
    for(int i=1;i<=n;i++){
        cin>>k[i].b;
    }
    sort(k+1,k+1+n,cmp);
    dp[0]=1;
    long long ans=0;
    for(int i=1;i<=n;i++){
        for(int j=k[i].a;j>=k[i].b;j--){
            ans+=dp[j-k[i].b];
            ans%=Mod; 
        }
        for(int j=5000;j>=k[i].b;j--){
            dp[j]+=dp[j-k[i].b];
            dp[j]%=Mod;
        }
    }
    cout<<ans<<endl;
    return 0;
}