Codeforces Round #671 (Div. 2)A-E題解

Codeforces Round #671 (Div. 2)A-E題解
//寫於rating值1987/2184
//這場的A-D是真的水…

比賽連結:https://codeforces.ml/contest

A題
水題

題意為給定一個長度為n的數位，兩個人交替對這個數位上的某一位進行標記。先手的人只能標記奇數位上的數，後手的人只能標記偶數位上的數。當只剩下一個位置上的數沒被標記時，如果這個數位是奇數那麼先手勝利，如果這個數是偶數，那麼後手勝利。

注意到這道題裡面，先手後手兩個人能標記的數位部分是完全互不相關的。最後一個剩下的數位到底是奇數位置還是偶數位置上的數，只由n的奇偶性決定。如果最後剩下的是奇數位上的數位，先手的人肯定希望自己能勝利，因此如果奇數位上的數位如果有任意一個是奇數的話，他只要把這個數留到最後就能保證自己勝利了。
最後剩下的是偶數位上的數位的時候同理。

#include<bits/stdc++.h>
#define ll long long
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

int32_t main()
{
    IOS;
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        string s;
        cin>>s;
        bool flag;
        if(n&1)//如果總數量是奇數的話，奇數位上的數比偶數位上多1個，最後剩下的那個數一定是奇數位上的數
        {
            flag=0;
            for(int i=0;i<n;i+=2)//只要奇數位上的數存在任何一個是奇數，先手的人都可以使得它成為最後一個數，使得自己獲勝
                if(s[i]%2) flag=1;
        }
        else//對應總數量是偶數的情況，最後剩下的數一定是偶數位上的數
        {
            flag=1;
            for(int i=1;i<n;i+=2)//只要偶數位上的數存在任何一個是偶數，後手的人都可以使得它成為最後一個數，使得自己獲勝
                if(s[i]%2==0) flag=0;
        }
        if(flag) cout<<1<<endl;
        else cout<<2<<endl;
    }
}

B題
簡單規律總結

題意為給定x個正方形小方塊，要你儘可能構造多的不相同的完美臺階。n階完美臺階的定義為，從左到右各列的方塊數依次為1-n個，並且這個臺階恰好能分成n個正方形部分。

其實容易想到，這樣的一個完美臺階必然是一個軸對稱的圖形，通過畫圖可以輔助理解得到結論。
首先只有1層的臺階是完美的，而2層的臺階是不完美的。
3層的臺階左下和右上可用1層完美臺階去補，剩下的部分恰好是個正方形。
7層的臺階左下和右上可用3層完美臺階去補，剩下的部分恰好是個正方形。
…
可以推得結論，完美臺階的層數從小到大的遞推公式就是f(n+1)=f(n)$\times$f(n)+1

樣例的最後一個資料已經給了最大的x取值1e18時候答案也只有30，因此直接暴力迴圈即可。

#include<bits/stdc++.h>
#define ll long long
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

ll num[70];

int32_t main()
{
    IOS;
    int t;
    cin>>t;
    while(t--)
    {
        ll x;
        cin>>x;
        ll ans=0,cas=1;
        while(x>0)
        {
            x-=(1+cas)*cas/2;
            if(x>=0) ans++;
            cas=cas*2+1;
        }
        cout<<ans<<endl;
    }
}

C題
貪心，分類討論

題意為現在有一種病毒在codeforces網站上傳播，它會在rating值相等的人之間進行傳播。一開始的時候只有一個人被感染了，他的rating值為x，並且他無法參加比賽（無法改變自己的rating值）。現在有n個人各自有一個初始的rating值，每次參加比賽你可以任意改變他們的rating值，但是所有人的rating變化值的總和必須為0。現在詢問做少需要幾次比賽，可以讓所有人都感染上病毒。

首先我們按照初始rating值和x相等的人數的情況進行分類，設初始rating值和x相等的人為cas。
如果cas=n，那麼代表所有人一開始就都被感染了，直接輸出0。
如果cas<n但是cas>0，代表一開始有一部分人被感染了，還有一部分未被感染。我們可以通過1次比賽，讓為被感染的人的rating值全部變為x，總改變值為0，那麼對應的與之相反的該變數直接加到那些一開始就被感染的人身上即可。因此此時直接輸出1。
如果cas=0的話，代表一開始所有人都沒有被感染，那就不能採取上一種情況的策略了。
此時我們計數一下n個人的rating值總和sum，如果sum能夠整除n，並且sum/n=x的話，那麼我們可以用通過1次比賽就把所有人的rating值變為x。
而如果sum/n!=x或者sum無法整除n的時候，我們必然不可能在1次比賽內使得所有人感染，但是我們可以1次比賽制造出1個感染者，然後採取上面0<cas<n的策略，就可以總共在2次比賽就使得所有人感染。

#include<bits/stdc++.h>
#define ll long long
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

int32_t main()
{
    IOS;
    int t;
    cin>>t;
    while(t--)
    {
        int n,x;
        cin>>n>>x;
        int sum=0,cas=0;
        for(int i=0;i<n;i++)
        {
            int temp;
            cin>>temp;
            if(temp!=x) sum+=temp;
            else cas++;
        }
        if(cas==n) cout<<0<<endl;
        else if(cas) cout<<1<<endl;
        else
        {
            if(sum%n==0&&sum/n==x) cout<<1<<endl;
            else cout<<2<<endl;
        }
    }
}

D1+D2題
貪心，構造

題意為給你n個數位，你需要把他們進行重新打亂排列。使得其中滿足比自己左側和右側相鄰數都小的數位儘可能多（下標1和下標n的數位不算，也就是開頭和末尾的數位都不算），輸出最大的滿足的數位數量，並輸出任意一種滿足的構造方式。

這裡我們採取貪心的策略，對奇數下標構造小的數位（下標從0開始），偶數下標構造大的數位。
這是因為左右邊界的數位是不算的，也就是下標0是必然不算的，我們最多可以從下標1開始構造滿足的數。而如果x[1]<x[2]的話，那x[2]就必然不是滿足的數了。也就是我們最優也必須隔著一個數位構造滿足的數位。也就是奇數下標要構造相對小的數位，偶數下標要構造相對大的數位。
直接對原有數位排序後，按照從小到大，下標從左到右依次放到奇數下標，再下標從左到右依次放到偶數下標。這樣我們就保證了1.偶數下標的是最大的那些數，並且2.偶數下標中的最小值也不小於奇數下標中的最大值。我們這樣排列，也保證了3.偶數下標中相對小的數會和奇數下標中相對小的數相鄰。
根據上面三條可以推出這樣的貪心是最優的策略。

D1和D2的差別就在於D1的數位是各不相同的，所以滿足條件的數位個數就是（n-1）/2，而D2的數位是可能相同的，我們需要再for一遍去檢測一下具體有解滿足條件的數位而已。構造方法是完全相同的。

#include<bits/stdc++.h>
#define ll long long
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

vector<ll>num;
vector<ll>out;
ll n;

int32_t main()
{
    IOS;
    cin>>n;
    num.resize(n);
    out.resize(n);
    for(auto &x:num) cin>>x;
    sort(num.begin(),num.end());
    ll tar=0;
    for(ll i=1;i<n;i+=2) out[i]=num[tar++];
    for(ll i=0;i<n;i+=2) out[i]=num[tar++];
    ll ans=0;
    for(ll i=1;i<n;i+=2) if(i+1<n&&out[i-1]>out[i]&&out[i+1]>out[i]) ans++;
    cout<<ans<<endl;
    for(ll i=0;i<n;i++)
    {
        if(i) cout<<' ';
        cout<<out[i];
    }
    cout<<endl;
}

E題
數論，複雜度分析，構造

題意為給定一個數位n，要求你對n除1外的所有因數排列成一個環，要求相鄰兩個位置之間互質的對數最少。輸出一種構造方案，並輸出最少的互質對數。

這裡的話容易想到，n的所有因子，都可以由n的質因子的不同冪次組合來得到。然後我們注意到，對於兩個質因子a和b。如果我們在a和b中間放入了一個既能整除a又能整除b的數c的話，變成a,c,b。那麼在a和c之間就可以放所有能整除a的因子，c和b之間就可以放所有能整除b的因子。
由此我們可以先找出n的所有不同的質因子，然後在他們兩兩之間放入一個能整除相鄰兩個質因子的n的因子，接著其他所有的數能必定至少能被這些質因子的某一個整除，也就是能按照上段所述插入到間隔裡。

接著就是想這種方案是否永遠可行。
對於這些質因子來說，兩個質因子的積必定也是n的因子，並且不同的質因子之間得到的積必然是不相等的，因此我們可以在相鄰質因子之間插入他們的積的構造方案。但是這種方案，在n=a$\times$b的時候是不成立的，因為此時n只有三個因子，a,b和n，如果按照上述方案會構造成a,n,b,n。重複使用了兩次n。此時我們實際上只能構造a,n,b，這樣會存在1對相鄰互質的數，此時我們直接輸出a,n,b,endl,1,endl即可。因此我們特判一下n恰好等於a$\times$b的情況。
但是這樣會wa在第十個點。因為如果只有兩個質因子的話，雖然我們可以構造0對相鄰互質的數的情況，但是我們同樣會使用兩次a$\times$b。

這時候就要我們分析複雜度了，因為這裡題意說了所有n的因子數量是不超過2e5的，根據因子是由質因子不同的冪次組合而成的，容易得到質因子的個數是一個很小的值，不會超過1e3，因此我們可以採取比較暴力的方案。

排除掉n=a$\times$b這種必須構造1對相鄰互質數的情況，其他情況下，相鄰質因子之間的那個能整除他們的數的選擇，可以直接暴力去n的所有因子裡去找。

以上。

#include<bits/stdc++.h>
#define ll long long
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const ll maxn=31630;

vector<ll>prime;//線性篩篩出sqrt(1e9)內的所有素數
bool v[maxn];

void primes()
{
    for(ll i=2;i<maxn;i++)
    {
        if(!v[i])
        {
            v[i]=1;
            prime.push_back(i);
        }
        for(ll j=0;prime[j]<maxn/i;j++)
        {
            v[prime[j]*i]=1;
            if(i%prime[j]==0) break;
        }
    }
}


int32_t main()
{
    IOS;
    primes();
    int t;
    cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        vector<ll>primes_now;//儲存當前的n分解質因數後有幾個不同的質因子
        ll temp=n;
        for(ll i=0;i<prime.size()&&prime[i]<=temp/prime[i];i++)
        {
            if(temp%prime[i]==0)
            {
                primes_now.push_back(prime[i]);
                while(temp%prime[i]==0) temp/=prime[i];
            }
        }
        if(temp>1) primes_now.push_back(temp);

        unordered_map<ll,bool>M;//儲存n除了1外的因子有哪些，記錄它是否被使用過
        for(ll i=2;i<=n/i;i++)
        {
            if(n%i==0)
            {
                M[i]=0;
                M[n/i]=0;
            }
        }
        M[n]=0;


        if(primes_now.size()==2&&primes_now[0]*primes_now[1]==n) cout<<primes_now[0]<<' '<<primes_now[1]<<' '<<n<<endl<<1<<endl;
        //如果n剛好能拆分成兩個質因子相乘，就是唯一一種特殊的情況，我們無法構造出0對相鄰互質而只能構成1對相鄰互質的特殊情況，直接輸出三個數位和對數1。
        else
        {
            vector<ll>mid(primes_now.size());//mid[i]當前n分解的質因子，第i個和第i+1箇中間插入的數是哪一個
            for(ll i=0;i<primes_now.size();i++)//直接暴力for一遍，質因子數量是很少的
            {
                for(auto &x:M)//去n的所有因數裡面找既能整除第i個質因子又能整除第i+1個質因子的數
                {
                    if(!x.second&&x.first%primes_now[i]==0&&x.first&&x.first%primes_now[(i+1)%primes_now.size()]==0)
                    {
                        mid[i]=x.first;
                        x.second=1;
                        break;
                    }
                }
                M[primes_now[i]]=1;
            }

            for(ll i=0;i<primes_now.size();i++)//然後把剩下沒使用過的數位繼續暴力放到第i個質因子和mid[i]中間，只需要滿足整除第i個質因子即可
            {
                cout<<primes_now[i]<<' ';
                for(auto &x:M)
                {
                    if(!x.second&&x.first%primes_now[i]==0)
                    {
                        cout<<x.first<<' ';
                        x.second=1;
                    }
                }
                cout<<mid[i]<<' ';
            }
            cout<<endl<<0<<endl;
        }
    }
}