Codeforces Round #671 (Div. 2)

A. Digit Game

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

如果字串長度為偶數，那麼就是 $B$ 最後拿偶數位的數，如果 $B$ 想贏，就把偶數位的偶數留到最後，換句話說，只要偶數位上有偶數，那麼 $B$ 必勝。
如果字串長度為奇數，那麼就是 $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$ 個樓梯時，資料已經到 $1 e 18$ 了。
那就先打表，把這些樓梯需要的塊的數量都打出來，然後記個字首和，二分查詢即可。

//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$ 次。
$1$ :
- 如果值的總和為 $0$ ,那麼 $1$ 次。
- 如果有 $1$ 個或多個為 $0$ 的數，那麼 $1$ 次。為什麼呢？因為這幾個數為 $0$ 的直接被感染了，然後它們可以隨意變化數值，變成其他分數，讓它們也感染。
$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$ 我按 $p y$ 做的，原本想繼續用 $p y$ 水過去得了，結果做到 $h a r d$ 的時候，發現 $R E$ 了，吃驚的我直接轉 $C$ 艹，就過了。。

$e a s y$

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$

//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$ 上綠了。。~~知道很垃圾了~~
完結