A. Find Array

题意：

给一个数字 n n n要求寻找出一个长为 n n n的数组 a a a，保证：

• 1 ≤ a i ≤ 1 0 9 1\le a_i \le 10^9 1≤ai​≤109
• a 1 < a 2 < ⋯ < a n a_1<a_2<\dots<a_n a1​<a2​<⋯<an​
• 对于 i ≥ 2 i\ge 2 i≥2， a i a_i ai​不可以被 a i − 1 a_{i-1} ai−1​整除

分析：

直接返回 2 2 2到 n + 1 n+1 n+1即可

代码：

#include<bits/stdc++.h>
using namespace  std;

int main()
{
    ios::sync_with_stdio(0);
    int T;cin>>T;
    while (T--)
    {
        int n;cin>>n;
        for (int i=1;i<=n;++i)cout<<i+1<<" ";
        cout<<endl;
    }
}

B. Build the Permutation

题意：

构造一个 1 1 1到 n n n的排列，要求有 a a a个山顶， b b b个山谷

对 n − 1 ≥ i ≥ 2 n-1\ge i\ge 2 n−1≥i≥2 如果

• a i a_i ai​> a i − 1 a_{i-1} ai−1​且 a i a_i ai​> a i + 1 a_{i+1} ai+1​ 则 a i a_i ai​是一个山顶
• a i < a i − 1 a_i<a_{i-1} ai​<ai−1​且 a i < a i + 1 a_i<a_{i+1} ai​<ai+1​ 则 a i a_i ai​是一个山谷

分析：

只有 n − 1 ≥ i ≥ 2 n-1\ge i\ge 2 n−1≥i≥2，才有可能出现山顶或者山谷

因此， a + b ≤ n − 2 a+b\le n-2 a+b≤n−2

然后， a a a与 b b b之间最多差值为 1 1 1

因为，在两个极大值之间，必然存在一个极小值；

同理在两个极小值之间也必然存在一个极大值。

• a = b a=b a=b： 我们将$2,4,6,\dots 2*a $ 依次取 n , n − 1 , n − 2 , … , n − a + 1 n,n-1,n-2,\dots,n-a+1 n,n−1,n−2,…,n−a+1

  这样，这些点一定是山顶。而 3 , 5 , 7 , … , 2 ∗ a − 1 3,5,7,\dots,2*a-1 3,5,7,…,2∗a−1一定是山谷我们要保证 2 ∗ a + 1 2*a+1 2∗a+1也是山谷因此要使得 2 ∗ A + 1 2*A+1 2∗A+1也是山谷，我们要让 2 ∗ a + 2 2*a+2 2∗a+2处的值大于 2 ∗ a + 1 2*a+1 2∗a+1处的值，从后往前填充 n − a , n − a − 1 , n − a − 2 … , 1 n-a,n-a-1,n-a-2\dots,1 n−a,n−a−1,n−a−2…,1

• a = b + 1 a=b+1 a=b+1时：我们同样将$2,4,6,\dots 2*a 依 次 取 依次取 依次取n,n-1,n-2,\dots,n-a+1$

  然后从前往后填充 n − a , n − a − 1 , n − a − 2 , … , 1 n-a,n-a-1,n-a-2,\dots,1 n−a,n−a−1,n−a−2,…,1即可

• b = a + 1 b=a+1 b=a+1：我们将 2 , 4 , 6 , … , 2 ∗ a 2,4,6,\dots,2*a 2,4,6,…,2∗a依次填充 1 , 2 , … , a 1,2,\dots,a 1,2,…,a，然后再从前到后

  填充 a + 1 , a + 2 , … , n a+1,a+2,\dots,n a+1,a+2,…,n即可

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+100;
int res[maxn];
int n,a,b;

int main()
{
    ios::sync_with_stdio(0);
    int T;cin>>T;
    while (T--)
    {
        cin>>n>>a>>b;
        if (a+b>n-2||abs(a-b)>1)
        {
            cout<<"-1\n";
            continue;
        }
        for (int i=1;i<=n;++i)res[i]=0;
        if (a==b)
        {
            int cur = n;
            for (int i=2;a>0;i+=2,--a)res[i]=cur--;
            for (int i=n;i>=1;--i)if (res[i]==0)res[i]=cur--;
        }
        else if (a>b)
        {
            int cur = n;
            for (int i=2;a>0&&i<n;i+=2,--a)res[i]=cur--;
            if (a>0)
            {
                cout<<"-1\n";
                continue;
            }
            for (int i=1;i<=n;++i)if (res[i]==0)res[i]=cur--;
        }
        else if (a<b)
        {
            int cur = 1;
            for (int i=2;b>0;i+=2,--b)res[i]=cur++;
            if (b>0)
            {
                cout<<"-1\n";
                continue;
            }
            for (int i=1;i<=n;++i)if (res[i]==0)res[i]=cur++;
        }for (int i=1;i<=n;++i)
        {
            cout<<res[i]<<" ";
            res[i]=0;
        }cout<<endl;
    }
}

C. Game Master

题意：

给 n n n个人，每个人有两个属性 a , b a,b a,b

举办 n − 1 n-1 n−1轮游戏，每轮选择两个人进行游戏，一个人 i i i可以消灭另一个人 j j j当且仅当， a i > a j a_i>a_j ai​>aj​或者 b i > b j b_i>b_j bi​>bj​

我们制定一个人被消灭

问每一个人是否有可能留到最后

分析：

我们可以想象，对于 a a a最大的那个人，一定可以战胜所有的人

对于 b b b最大的那个人也一定可以战胜所有人

因此，能战胜 a a a最大的人一定是可能的。同样能战胜 b b b最大的人也一定是可能的

我们首先尝试去统计能战胜最大 a a a的人 u u u

可以这样统计

维护两个值， m i n ( a ) min(a) min(a)和 m i n ( b ) min(b) min(b)刚开始， m i n ( a ) = u a min(a)=u_a min(a)=ua​， m i n ( b ) = u b min(b)=u_b min(b)=ub​

然后大于 m i n ( b ) min(b) min(b)的人加入，更新 m i n ( a ) min(a) min(a)，之后大于 m i n ( a ) min(a) min(a)的人加入，更新 m i n ( b ) min(b) min(b)

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+100;
const int inf = 1e9;
int a[maxn],b[maxn];
int c[maxn],d[maxn];
int res[maxn];
int n;
int main()
{
    ios::sync_with_stdio(0);
    int T;cin>>T;
    while (T--)
    {
        cin>>n;
        for (int i=1;i<=n;++i)cin>>a[i];
        for (int i=1;i<=n;++i)cin>>b[i];
        for (int i=1;i<=n;++i)c[i]=d[i]=i;
        sort(c+1,c+1+n,[](int na,int nb)
        {
            return a[na]>a[nb];
        });
        sort(d+1,d+1+n,[](int na,int nb)
        {
            return b[na]>b[nb];
        });
        for (int i=1;i<=n;++i)res[i]=0;
        int mna = a[c[1]], mnb = b[c[1]];
        int p1 = 1,p2 = 1;
        while (true)
        {
            bool f = false;
            while (p1<=n&&a[c[p1]]>=mna)
            {
                mnb = min(mnb, b[c[p1]]);
                res[c[p1]]=1;
                ++p1;
                f = true;
            }
            while (p2<=n&&b[d[p2]]>=mnb)
            {
                mna = min(mna, a[d[p2]]);
                res[d[p2]]=1;
                ++p2;
                f = true;
            }
            if (!f)break;
        }
        mna = a[d[1]], mnb = b[d[1]];
        p1=1,p2=1;
        while (true)
        {
            bool f = false;
            while (p1<=n&&a[c[p1]]>=mna)
            {
                mnb = min(mnb, b[c[p1]]);
                res[c[p1]]=1;
                ++p1;
                f = true;
            }
            while (p2<=n&&b[d[p2]]>=mnb)
            {
                mna = min(mna, a[d[p2]]);
                res[d[p2]]=1;
                ++p2;
                f = true;
            }
            if (!f)break;
        }
        for (int i=1;i<=n;++i)cout<<res[i];cout<<endl;

    }
}

D. Dominoes

题意：

一张骨牌，分为左右两部分，骨牌不可以旋转。

对n张骨牌，如果他是合法的。那么则存在一个排列，是的每张骨牌左边的颜色与左边邻近骨牌的右边颜色不同。右边的颜色与右边邻近骨牌的左边颜色不同

第n张骨牌和第1张骨牌相邻

n ≥ 2 n\ge 2 n≥2

分析：

是有点偏向于找规律的题目

首先一个小结论， B B B的数量一定要和 W W W的数量相等

我们想想反例： B W BW BW和 W B WB WB

如果只存在这两种骨牌的话，我们是无论如何也无法成功找到合法排列的

因为 B W BW BW是一定要和 W B WB WB衔接的！

但是， B W , W B , B B / W W BW,WB,BB/WW BW,WB,BB/WW就可以，因为我们可以借助 B B BB BB或者 W W WW WW为中介

成功衔接！

其次，全是 B W / W B BW/WB BW/WB也是可以的

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+100;
const ll mod = 998244353;
ll POW(ll base,ll p)
{
    ll ans = 1;
    while (p)
    {
        if (p&1)ans = ans*base%mod;
        base = base*base%mod;
        p>>=1;
    }return ans;
}
ll inv(ll num)
{
    return POW(num,mod-2);
}
ll J[maxn];
ll C(int n,int m)
{
    return J[n]*inv(J[m]*J[n-m]%mod)%mod;
}
int D[maxn][2];
int n;
int main()
{
    cin>>n;
    J[0]=1;
    for (int i=1;i<=2*n;++i)
        J[i]=J[i-1]*i%mod;
    int sum = 0;
    int haa = 0;
    int B=0,W=0;
    int aa = 0;
    int bw=0,wb=0;
    for (int i=1;i<=n;++i)
    {
        for (int j=0;j<2;++j)
        {
            char ch;cin>>ch;
            if (ch=='?')
            {
                D[i][j]=-1;
                ++sum;
            }
            else if (ch=='B')
            {
                D[i][j]=0;
                ++B;
            }
            else
            {
                D[i][j]=1;
                ++W;
            }
        }
        if (D[i][0]==D[i][1]&&D[i][0]!=-1)haa=1;
        if (D[i][0]==-1&&D[i][1]==-1)++aa;
        if (D[i][0]!=-1&&D[i][1]==-1)D[i][1]=1^D[i][0];
        else if (D[i][1]!=-1&&D[i][0]==-1)D[i][0]=1^D[i][1];
        if (D[i][0]==0&&D[i][1]==1)bw = 1;
        if (D[i][0]==1&&D[i][1]==0)wb = 1;
    }
    if (sum==0)
    {
        if (B==W&&(haa||(bw^wb)))cout<<"1\n";
        else cout<<"0\n";
        return 0;
    }
    else if (B>n||W>n)
    {
        cout<<"0\n";
        return 0;
    }
    sum = C(sum, n-B);
    if (haa)
    {
        cout<<sum<<endl;
        return 0;
    }
    if (aa) sum = (sum - POW(2, aa) + (wb^1) + (bw^1) + mod)%mod;
    cout<<sum<<endl;
}