AtCoder Regular Contest 144【VP记录】

A - Digit Sum of 2x

        其实通过样例就很容易发现M=2*N，f(x)=N,f(2*x)=M,x要尽可能小，故x就需要满足每个位上的数字至多为4，然后贪心放4就好了，4尽可能放在后面的位。

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
//#define rep(i,a,b) for(int i=a;i<=b;i++)
//#define rep2(i,a,b) for(int i=a;i>=b;i--)
///* run this program using the console pauser or add your own getch, system("pause") or input loop */
#define sc(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ll long long
#define pb push_back
typedef pair<int,int>PII;
const int Max=2e5+200;
const ll INF=1e15+5;
vector<int>v;
int main(){
    int n;sc(n);
    cout<<2*n<<endl;
    while(n!=0){
        if(n>=4) v.pb(4),n-=4;
        else v.pb(n),n=0;
    }
    for(int i=v.size()-1;i>=0;i--) printf("%d",v[i]);
}

B - Gift Tax

        一看到求最小值最大的情况，可立马往二分上想！！！这题二分最小值即可！！咳，思路很简单，自己码了好久，还要加强码力！！！

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
//#define rep(i,a,b) for(int i=a;i<=b;i++)
//#define rep2(i,a,b) for(int i=a;i>=b;i--)
///* run this program using the console pauser or add your own getch, system("pause") or input loop */
#define sc(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ll long long
#define pb push_back
typedef pair<int,int>PII;
const int Max=2e5+200;
const ll INF=1e15+5;
int vis[Max];
int n,a,b;
int Min=1e9+5;
int tmp[Max];
bool check(int x){
    for(int i=1;i<=n;i++) tmp[i]=vis[i];
    int len=n;
    for(int i=1;i<=n;i++){
        if(tmp[i]<x){
            int num=x-tmp[i];
            if(num%a==0) num=num/a;
            else num=num/a+1;
            // cout<<num<<"----\n";
            while(num!=0&&len>i){
                int ans=tmp[len]-x;
                // cout<<num<<' '<<ans<<"++\n";
                if(num>=ans/b){
                    num-=ans/b;tmp[i]+=(ans/b*a);
                    tmp[len]-=ans/b*b;len--;
                }
                else{
                    tmp[i]+=num*a;
                    tmp[len]-=b*num;num=0;
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        // cout<<tmp[i]<<' ';
        if(tmp[i]<x) return false;
    }
    return true;
}
int main(){
    sc(n);sc(a);sc(b);
    for(int i=1;i<=n;i++){
        sc(vis[i]);
    }
    sort(vis+1,vis+1+n);
    // cout<<check(2)<<endl;
    int l=0,r=1e9;
    while(l<=r){
        int mid=(l+r)/2;
        if(check(mid)) l=mid+1;
        else r=mid-1;
    }
    cout<<r<<endl;
}

C - K Derangement

好细节的构造题，一看这题，立马就想到了构造方法，但是还是有小瑕疵。

例如：9 2

我们先可以按2*k分组，依次分成【1，4】，【5，8】，【9，9】

如果有多余的组别，可与最后一组2*k合并【1，4】，【5，9】

此时我们只要每个组别的数字前k个数+k，后k个数-k即可，此时数列即为

3，4，1，2，7，8，9，5，6 这就是最后构造结果；

但是还要一种特殊情况（我当时就是没注意到，呜呜呜呜.....）

例如 ：15 4

按上面方法构造出的即是：5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 

但是你可以发现最后一个组别1，2...有的数还可以在这个组别内继续往前调整位置，使得字典序更小，变成 5 6 7 8 1 2 3 12 13 14 15 4 9 10 11 

做题技巧：在构造题完全没思路的时候，可以尝试打表看看规律

例如官方题解：

 

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
//#define rep(i,a,b) for(int i=a;i<=b;i++)
//#define rep2(i,a,b) for(int i=a;i>=b;i--)
///* run this program using the console pauser or add your own getch, system("pause") or input loop */
#define sc(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ll long long
#define pb push_back
typedef pair<int,int>PII;
const int Max=1e6+5;
const ll INF=1e15+5;
int a[Max],n;
int main(){
    sc(n);int k;
    sc(k);
    if(n<k*2){
        printf("-1\n");
        return 0;
    }
    int num=n/(2*k);
    int ans=1,i=1;
    if(n%(2*k)==0){
        while(num>0){
            for(int j=0;j<k;j++){
                a[i+j+k]=ans;
                ans++;
            }
            for(int j=0;j<k;j++){
                a[i+j]=ans;
                ans++;
            }
            i+=2*k;
            num--;
        }
        for(int i=1;i<=n;i++){
            printf("%d ",a[i]);
        }
        return 0;
    }
    while(num>=2){
        for(int j=0;j<k;j++){
            a[i+j+k]=ans;
            ans++;
        }
        for(int j=0;j<k;j++){
            a[i+j]=ans;
            ans++;
        }
        i+=2*k;
        num--;
    }
    int pre=abs(n-k);int len=n;
    int j;int tmp,temp,cnt;
    for(j=pre;j>=i;j--){
        a[j]=len;
        if(len==pre){
            tmp=j;
            cnt=len;
        }
        len--;
    }
    temp=a[i+k-1];
    // cout<<tmp<<' '<<cnt<<"----\n";
    for(int m=i+k;m<=tmp;m++){
        a[m]=ans;ans++;
    }
    for(int j=pre+1;j<=n;j++) a[j]=ans,ans++;
    for(int j=n;j>=1;j--){
        if(cnt<=temp) break;
        a[j]=cnt;
        cnt--;
    }
    // if(!flag) printf("-1\n");
    // else{
        // for(int j=i;)
        for(int i=1;i<=n;i++){
            printf("%d ",a[i]);
        }
    // }
}