Codeforces Round #671 (Div. 2)

Powered by:AB_IN 局外人

A. Digit Game

給定一串數字， A A A和 B B B輪流選數， A A A只能選奇數位的, B B B只能選偶數位的，最后一個數是奇數則 A A A勝，否則 B B B勝，

• 如果字串長度為偶數，那么就是 B B B最后拿偶數位的數，如果 B B B想贏，就把偶數位的偶數留到最后，換句話說，只要偶數位上有偶數，那么 B B B必勝，
• 如果字串長度為奇數，那么就是 A A A最后拿奇數位的數，如果 A A A想贏，就把奇數位的奇數留到最后，換句話說，只要奇數位上有奇數，那么 A A A必勝，

for _ in range(int(input())):
    n=int(input())
    s=input()
    f=0
    if n%2==0:#剩偶數位置的數
        for i in range(1,n,2):
            if int(s[i])%2==0:
                print(2)
                f=1
                break
        if f==0:
            print(1)
    else:
        for i in range(0,n,2):
            if int(s[i])%2!=0:
                print(1)
                f=1
                break
        if f==0:
            print(2)

B. Stairs

就是個找規律的題，
觀察發現建 30 30 30個樓梯時，資料已經到 1 e 18 1e18 1e18了，
那就先打表，把這些樓梯需要的塊的數量都打出來，然后記個前綴和，二分查詢即可，

//C++17
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")

using namespace std;

#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define ull unsigned long long
#define rint register int
#define ld long double
#define db double
#define rep(i, l, r) for (rint i = l; i <= r; i++)
#define rep1(i,a,n) for (rint i=a;i<n;i++)
#define per(i, l, r) for (rint i = l; i >= r; i--)
#define per1(i,a,n) for (rint i=a;i>n;i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define sd(x) scanf("%d",&(x))
#define slld(x) scanf("%lld",&(x))
#define sdd(x,y) scanf("%d%d",&(x),&(y))
#define sc(s) scanf("%s",(s))
#define pd(x) printf("%d\n",(x))
#define plld(x) printf("%lld\n",(x))
#define pdk(x) printf("%d ",(x))
const int inf=0x3f3f3f3f;

namespace IO{
    char ibuf[1<<21],*ip=ibuf,*ip_=ibuf;
    char obuf[1<<21],*op=obuf,*op_=obuf+(1<<21);
    inline char gc(){
        if(ip!=ip_)return *ip++;
        ip=ibuf;ip_=ip+fread(ibuf,1,1<<21,stdin);
        return ip==ip_?EOF:*ip++;
    }
    inline void pc(char c){
        if(op==op_)fwrite(obuf,1,1<<21,stdout),op=obuf;
        *op++=c;
    }
    inline ll read(){
        register ll x=0,ch=gc(),w=1;
        for(;ch<'0'||ch>'9';ch=gc())if(ch=='-')w=-1;
        for(;ch>='0'&&ch<='9';ch=gc())x=x*10+ch-48;
        return w*x;
    }
    template<class I>
    inline void write(I x){
        if(x<0)pc('-'),x=-x;
        if(x>9)write(x/10);pc(x%10+'0');
    }
    class flusher_{
    public:
        ~flusher_(){if(op!=obuf)fwrite(obuf,1,op-obuf,stdout);}
    }IO_flusher;
}
using namespace IO;
const int N=1e5+10;
ull a[N],b[N],x;
int t;
ll q (ll a, ll b){
    ll ret=1;
    while(b){
        if(b&1)
            ret=ret*a;
        a=a*a;
        b=b>>1;
    }
    return ret;
}
int main()
{
	t=read();
    a[1]=1;
    rep(i, 2, 30) a[i]=a[i-1]*2+q(2,2*(i-1));
    rep(i, 2, 30) b[i]=b[i-1]+a[i];
    while(t--){
        x=read();
        ll c=lower_bound(b+1, b+31 ,x)-b-1;
        write(c);
        pc('\n');
    }
	return 0;
}

C. Killjoy

先預處理，每個數都減感染，

• 0 0 0:如果值全為 0 0 0，那么 0 0 0次，
• 1 1 1:
  • 如果值的總和為 0 0 0,那么 1 1 1次，
  • 如果有 1 1 1個或多個為 0 0 0的數，那么 1 1 1次，為什么呢？因為這幾個數為 0 0 0的直接被感染了，然后它們可以隨意變化數值，變成其他分數，讓它們也感染，
• 2 2 2:其余情況，

//C++17
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")

using namespace std;

#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define ull unsigned long long
#define rint register int
#define ld long double
#define db double
#define rep(i, l, r) for (rint i = l; i <= r; i++)
#define rep1(i,a,n) for (rint i=a;i<n;i++)
#define per(i, l, r) for (rint i = l; i >= r; i--)
#define per1(i,a,n) for (rint i=a;i>n;i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define sd(x) scanf("%d",&(x))
#define slld(x) scanf("%lld",&(x))
#define sdd(x,y) scanf("%d%d",&(x),&(y))
#define sc(s) scanf("%s",(s))
#define pd(x) printf("%d\n",(x))
#define plld(x) printf("%lld\n",(x))
#define pdk(x) printf("%d ",(x))
const int inf=0x3f3f3f3f;

namespace IO{
    char ibuf[1<<21],*ip=ibuf,*ip_=ibuf;
    char obuf[1<<21],*op=obuf,*op_=obuf+(1<<21);
    inline char gc(){
        if(ip!=ip_)return *ip++;
        ip=ibuf;ip_=ip+fread(ibuf,1,1<<21,stdin);
        return ip==ip_?EOF:*ip++;
    }
    inline void pc(char c){
        if(op==op_)fwrite(obuf,1,1<<21,stdout),op=obuf;
        *op++=c;
    }
    inline ll read(){
        register ll x=0,ch=gc(),w=1;
        for(;ch<'0'||ch>'9';ch=gc())if(ch=='-')w=-1;
        for(;ch>='0'&&ch<='9';ch=gc())x=x*10+ch-48;
        return w*x;
    }
    template<class I>
    inline void write(I x){
        if(x<0)pc('-'),x=-x;
        if(x>9)write(x/10);pc(x%10+'0');
    }
    class flusher_{
    public:
        ~flusher_(){if(op!=obuf)fwrite(obuf,1,op-obuf,stdout);}
    }IO_flusher;
}
using namespace IO;
const int N=1e5+10;
ll t,a[N],b,n,x,ans1,ans2,sum,flag;
int main()
{
	t=read();
    while(t--){
        n=read();x=read();
        ans1=0,sum=0,flag=0;
        mset(a, 0);
        rep(i, 1, n){
            a[i]=read();
            a[i]-=x;
            if(!a[i]){
                ans1++;
                flag=1;
            }
            sum+=a[i];
        }
        if(ans1==n) write(0);
        else if (sum==0 || flag) write(1);
        else write(2);
        pc('\n');
    }
	return 0;
}

D1. Sage’s Birthday (easy version) && D2. Sage’s Birthday (hard version)

一開始 e a s y easy easy我按 p y py py做的，原本想繼續用 p y py py水過去得了，結果做到 h a r d hard hard的時候，發現 R E RE RE了，吃驚的我直接轉 C C C艸，就過了，，

e a s y easy easy

n=int(input())
lst=list(map(int,input().split()))
lst.sort()
tmp=[i for i in range(1,n+1)]
cnt=0
for i in range(1,n,2):
    tmp[i]=lst[cnt]
    cnt+=1
if n%2==0:
    print(cnt-1)
else:
    print(cnt)
for i in range(0,n,2):
    tmp[i]=lst[cnt]
    cnt+=1
print(*tmp)  

h a r d hard hard

//C++17
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")

using namespace std;

#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define ull unsigned long long
#define rint register int
#define ld long double
#define db double
#define rep(i, l, r) for (rint i = l; i <= r; i++)
#define rep1(i,a,n) for (rint i=a;i<n;i++)
#define per(i, l, r) for (rint i = l; i >= r; i--)
#define per1(i,a,n) for (rint i=a;i>n;i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define sd(x) scanf("%d",&(x))
#define slld(x) scanf("%lld",&(x))
#define sdd(x,y) scanf("%d%d",&(x),&(y))
#define sc(s) scanf("%s",(s))
#define pd(x) printf("%d\n",(x))
#define plld(x) printf("%lld\n",(x))
#define pdk(x) printf("%d ",(x))
const int inf=0x3f3f3f3f;

namespace IO{
    char ibuf[1<<21],*ip=ibuf,*ip_=ibuf;
    char obuf[1<<21],*op=obuf,*op_=obuf+(1<<21);
    inline char gc(){
        if(ip!=ip_)return *ip++;
        ip=ibuf;ip_=ip+fread(ibuf,1,1<<21,stdin);
        return ip==ip_?EOF:*ip++;
    }
    inline void pc(char c){
        if(op==op_)fwrite(obuf,1,1<<21,stdout),op=obuf;
        *op++=c;
    }
    inline ll read(){
        register ll x=0,ch=gc(),w=1;
        for(;ch<'0'||ch>'9';ch=gc())if(ch=='-')w=-1;
        for(;ch>='0'&&ch<='9';ch=gc())x=x*10+ch-48;
        return w*x;
    }
    template<class I>
    inline void write(I x){
        if(x<0)pc('-'),x=-x;
        if(x>9)write(x/10);pc(x%10+'0');
    }
    class flusher_{
    public:
        ~flusher_(){if(op!=obuf)fwrite(obuf,1,op-obuf,stdout);}
    }IO_flusher;
}
using namespace IO;
const int N=1e5+10;
ll a[N],b[N],n,cnt,ans;
int main()
{
	n=read();
    rep(i, 1, n){
        a[i]=read();
    }
    sort(a+1,a+1+n);
    for(int i=2;i<=n;i+=2){
        b[i]=a[++cnt];
    }
    for(int i=1;i<=n;i+=2){
        b[i]=a[++cnt];
    }
    for(int i=2;i<=n;i+=2){
        if(b[i-1]>b[i]&&b[i]<b[i+1])
            ans++;
    }
    printf("%lld\n",ans);
    rep(i, 1, n) printf("%lld ",b[i]);
	return 0;
}

C F CF CF上綠了，，知道很垃圾了
完結