Codeforces Round #640 (Div. 4)

前言

有幸参加了Codeforces史上第一场div4，总的来看，div4的题就是暴力+构造+模拟+思维，应该不会用到数据结构或者其他更深知识，多做点div3和div4，以后div2前三题尽量都迅速搞定

constructive algorithm——一生之敌

A. Sum of Round Numbers（签到）

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;

vector<int> ans;
string s;

int Pow(int k){
    int ans=1;
    for(int i=1;i<=k;i++)
        ans*=10;
    return ans;
}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t,n;
    cin>>t;
    while(t--){
        cin>>s;
        ans.clear();
        for(int i=s.size()-1,j=0;i>=0;i--,j++){
            if(s[i]=='0') continue;
            else ans.push_back((s[i]-'0')*Pow(j));
        }
        cout<<ans.size()<<"\n";
        for(int i=0;i<ans.size();i++)
            cout<<ans[i]<<" ";
        cout<<"\n";
    }
    return 0;
}

B. Same Parity Summands（规律）

为什么我感觉这个

B

$B$

题比后面的三道都难，有点难受，wa+3才过了

首先对通过最后一组样例，求出

n/k

$n / k$

不难发现就是

111111110

$111111110$

，然后就明白还需要求出

n\%k

$n % k$

，然后分

x

$x$

和

y

$y$

的奇偶情况考虑

一开始没注意

k

$k$

的奇偶性，然后发现在

y

$y$

是奇数的情况下可能出现特例，因此特判

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t,n,k;
    cin>>t;
    while(t--){
        cin>>n>>k;
        int x=n/k,y=n%k;
        //cout<<x<<" "<<y<<endl;
        if(x==0){
            cout<<"NO\n";
            continue;
        }
        if(y==0){
            cout<<"YES\n";
            cout<<x;
            for(int i=1;i<k;i++)
                cout<<" "<<x;
            cout<<"\n";
            continue;
        }
        if(x&1){
            if(y&1){
                if(x==1 || k%2==0){
                    cout<<"NO\n";
                }else{
                    cout<<"YES\n";
                    cout<<x+y+k-1;
                    for(int i=1;i<k;i++)
                        cout<<" "<<x-1;
                    cout<<"\n";
                }
            }else{
                cout<<"YES\n";
                cout<<x+y;
                for(int i=1;i<k;i++)
                    cout<<" "<<x;
                cout<<"\n";
            }
        }else{
            if(y&1){
                if(k&1){
                    cout<<"YES\n";
                    cout<<x+y+k-1;
                    for(int i=1;i<k;i++)
                        cout<<" "<<x-1;
                    cout<<"\n";
                }else cout<<"NO\n";
            }else{
                cout<<"YES\n";
                cout<<x+y;
                for(int i=1;i<k;i++)
                    cout<<" "<<x;
                cout<<"\n";
            }
        }
    }
    return 0;
}

C. K-th Not Divisible by n（思维）

反向思考，考虑找第

i

$i$

个

n

$n$

的倍数，不难发现在它前面有

∗

−

n*i-i

$n * i - i$

个非

n

$n$

的倍数，因此就变成了找第

k

$k$

个非

n

$n$

的倍数左边最近的

n

$n$

的倍数即可

样例搞过题目就过了

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t,n,k;
    cin>>t;
    while(t--){
        cin>>n>>k;
        int p=n-1;
        int x=k%p,y=k/p;
        if(x) cout<<y*n+x<<endl;
        else cout<<y*n+x-1<<endl;
    }
    return 0;
}

D. Alice, Bob and Candies（模拟）

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;

int a[maxn];

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t,n;
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        int ans=1,l=2,r=n,pre=a[1],flag=1,res1=a[1],res2=0;
        while(l<=r){
            if(flag){
                int sum=0;
                while(sum<=pre && r>=l){
                    sum+=a[r--];
                }
                ans++;
                pre=sum;
                flag=0;
                res2+=sum;
                //cout<<sum<<endl;
            }else{
                int sum=0;
                while(sum<=pre && l<=r){
                    sum+=a[l++];
                }
                ans++;
                pre=sum;
                flag=1;
                res1+=sum;
                //cout<<sum<<endl;
            }
        }
        cout<<ans<<" "<<res1<<" "<<res2<<"\n";
    }
    return 0;
}

E. Special Elements（暴力+前缀和处理）

求出前缀和后考虑序列长度

−

2-n

$2 - n$

的连续子序列，然后分别判断某个

[

]

a[i]

$a [i]$

是否出现即可，注意本题卡内存，需要一个小优化

比赛时因为

B

$B$

耽误了太长时间，最后交了两发都是

MLE

$M L E$

，因为每个

[

]

≤

a[i] \leq n

$a [i] \leq n$

，因此我们求出了连续子序列的和，判断一下是否小于

n

$n$

因为使用哈希

map

$m a p$

而没有判断是否小于

n

$n$

造成内存不够，下次一定注意

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=1e4+10;

int a[maxn],sum[maxn];
bool vis[maxn];

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t,n;
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            sum[i]=sum[i-1]+a[i];
            vis[a[i]]=0;
        }
        for(int k=2;k<=n;k++){
            for(int i=1;i<=n-k+1;i++){
                int res=sum[i+k-1]-sum[i-1];
                if(res<=n) vis[res]=1;
            }
        }
        ll ans=0;
        for(int i=1;i<=n;i++)
            if(vis[a[i]]) ans++;
        cout<<ans<<endl;
    }
    return 0;
}

F. Binary String Reconstruction（构造）

不难发现如果是010101这样的，既不会使”00″变多，也不会使”11″变多，那么我们统一采用以下方式构造：

000…00111…11010101…

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t,a,b,c;
    cin>>t;
    while(t--){
        cin>>a>>b>>c;
        if(!b){
            if(a) for(int i=0;i<a+1;i++) cout<<0;
            if(c) for(int i=0;i<c+1;i++) cout<<1;
        }else{
            for(int i=0;i<a+1;i++) cout<<0;
            for(int i=0;i<c+1;i++) cout<<1;
            for(int i=0;i<b-1;i++) cout<<(i&1);
        }
        cout<<endl;
    }
    return 0;
}

G. Special Permutation（构造）

不难发现

≤

n \leq 3

$n \leq 3$

一定无解

首先容易想到这样的序列：

…9 7 5 3 1 + 2 4 6 8 10…

但是中间的1和2相差为1怎么办？实际上样例告诉我们了，交换一下2和4即可

另外我在写题的时候将

(

)

puts()

$p u t s ()$

和

cout<<endl

$c o u t < < e n d l$

混用，本地没事但是

cf

$c f$

的评测机不知道为什么将特判的

(

puts(

$p u t s ($

”

-1

$- 1$

”

)

$)$

都最后输出导致了输出混乱，以后一定注意！

#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;

list<int> ans;

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t,n;
    cin>>t;
    while(t--){
        cin>>n;
        if(n<=3){
            cout<<"-1"<<endl;
            continue;
        }
        ans.clear();
        ans.push_back(3);
        ans.push_back(1);
        ans.push_back(4);
        ans.push_back(2);
        for(int i=5;i<=n;i++)
            if(i&1) ans.push_front(i);
            else ans.push_back(i);
        int flag=1;
        for(auto i: ans){
            if(flag){
                cout<<i;
                flag=0;
            }else cout<<" "<<i;
        }
        cout<<endl;
    }
    return 0;
}

原文链接：https://blog.csdn.net/qq_44691917/article/details/106044268

前言