1608C - Game Master

Title Description:

Now there are n n n players are competing, of which No i i The ability values of i players in the two maps are a i , b i a_i,b_i ai​,bi​. Now we're going to do it n − 1 n-1 In n − 1 game, a winner is expelled from the corner. In each game, any two of the current non eliminated players can be arranged to compete in any map. Among them, the one with high ability value in the map wins (the title ensures that everyone's ability in each map is different). Ask all n n Do n people have a chance to be the final winner

1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5 1≤n≤105

solution:

This problem is actually an implicit graph problem i i i players abstract into i i i points if and only if i i The capability value of i is greater than on any map j j j, from i i i connecting direction j j j.

Practice 1:

It can be found that the desired number of edges can be achieved O ( n 2 ) O(n^2) O(n2), if hard construction is required, consider the optimization of line segment tree to build the map, open two line segment trees with the ability value as the subscript, and connect the edge from this person's point to the interval with greater ability each time, and maintain the connected block where the point with the largest ability value is located, and the person in the connected block may become the winner.

Practice 2:

Because the essence of an edge is a partial order relationship, it is transitive. Suppose we build an edge like this A − > B , B − > C A->B,B->C A − > b, B − > C, then obviously A − > C A->C A − > C is redundant. So we followed a i , b i a_i,b_i ai, bi} sort, then O ( n ) O(n) O(n) just build edges for all adjacent two points.

Obviously, only when a point can reach the point with the highest ability value, that point can become the winner. Therefore, we consider that the whole graph is a strongly connected component and consider the Tarjan contraction point. After obtaining DAG, it is obvious that the final penetration is 0 0 There is only one strong connected component of 0. The meaning of this strong connected component is that it can go to the point with the highest capability value, then there are and only all points in it may become the winner.

Practice 3:

The above two methods are essentially to find the point that can reach the highest ability value. If we don't use the above skills, we can only try at each point of violent dfs. If u u If u can reach the point with the highest capability value, there must be a one-way path. So we consider building a reverse graph, so we just need to start from the point with the highest capability value and see if we can reach each point.

Practice 4:

Considering the sequence approach, we take a a a is the descending sort of keywords. Obviously, the sorted keywords are i i i points, all [ i + 1 , n ] [i+1,n] [i+1,n] points can pass directly a i a_i ai ， rolling wins, which also means for the third party i i i points, the largest point we can control at present b i b_i bi# exists in [ i , n ] [i,n] [i,n], that's what we beat [ 1 , n − 1 ] [1,n-1] [1,n − 1] unique weight.

We need to be [ 1 , n − 1 ] [1,n-1] [1,n − 1] find one who can be the final winner, and b i b_i Points where the bi ＾ value is less than the above maximum value. We maintain them separately p r e i pre_i prei ， and s u f i suf_i sufi represents the former i i The smallest of i points that can become the winner b i b_i bi ， and back [ i , n ] [i,n] Maximum of [i,n] points b i b_i bi ， value, obviously as long as p r e i − 1 < s u f i pre_{i-1}<suf_i prei − 1 < Sufi, current point i i i can be the winner. And for p r e 1 pre_1 pre1 ， obviously due to its a 1 a_1 a1 ， value is rolling, so it must win.

Practice 5:

Consider those who will lose, either can't beat anyone, or those who can beat can't beat anyone, or those who can beat can't beat anyone, and so on. Consider optimization

We were right a i a_i ai and b i b_i bi ＾ sort in descending order, if there is a position (and it is the position where this occurs for the first time) i i i make it in front of both sides i i i strong is this i i i individual, then everyone inside can become a winner, and no one outside the collection can defeat them

code (tarjan shrink point):

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=3e5+10;

int n;

struct node{
    int a,b,id;
}a[maxn];

bool cmp1(node x,node y){
    return x.a<y.a;
}

bool cmp2(node x,node y){
    return x.b<y.b;
}

vector<int> g[maxn];

int dfn[maxn],low[maxn],cnt,cl,col[maxn];
bool vis[maxn],qs[maxn];
int in[maxn];

stack <int> st;

void tarjan(int x) {
    dfn[x]=low[x]=++cnt; 
    vis[x]=1;
    st.push(x);
    for(int i=0;i<g[x].size();i++) {
        int v=g[x][i];
        if(!dfn[v]) tarjan(v),low[x]=min(low[x],low[v]);
        if(vis[v]) low[x]=min(low[x],dfn[v]);
    }
    if(dfn[x]==low[x]) {
        ++cl;
        int tt;
        do{
            tt=st.top();
            vis[tt]=0;
            col[tt]=cl;
            st.pop();
        }while(tt^x); 
    }
} 

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++) g[i].clear(),vis[i]=qs[i]=dfn[i]=low[i]=col[i]=0;
        for(int i=1;i<=n;i++) cin>>a[i].a;
        for(int i=1;i<=n;i++) cin>>a[i].b,a[i].id=i;
        sort(a+1,a+n+1,cmp1);
        for(int i=1;i<n;i++) g[a[i+1].id].push_back(a[i].id);
        sort(a+1,a+n+1,cmp2);
        for(int i=1;i<n;i++) g[a[i+1].id].push_back(a[i].id);
        
        for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
        for(int i=1;i<=n;i++){
            for(int j=0;j<g[i].size();j++){
                int v=g[i][j];
                if(col[v]!=col[i]) ++in[col[v]];
            }
        }


        for(int i=1;i<=cl;i++){
            if(!in[i]) qs[i]=1;
        }

        for(int i=1;i<=n;i++) cout<<qs[col[i]];
        cout<<endl;
    }

    return 0;
}

1608D - Dominoes

Title Description:

have n n For n dominoes divided into left and right squares, black and white dyeing is required. The left or right squares of some dominoes have been dyed, and the rest need to be dyed. Q: there are several coloring schemes to make the rearrangement of colored dominoes meet any second order i i The right half and the second half of i dominoes ( i   m o d      n ) + 1 (i \mod n)+1 (i   mod   n) + the color of the left half of a domino is different.

solution:

Due to the above constraints, black and white appear in pairs, that is, they must exist in the legal scheme n n n black and n n n white, and if a domino is pure black / pure white, there must be a corresponding pure white / pure black domino, that is, the number of "WW" and "BB" in the legal scheme is equal.

The same type of "WB" and "BW" dominoes can coexist, and the next card can always be the same card

When there are only two types of "WB" and "BW" dominoes, there is no scheme to connect the two different types of dominoes, that is, the two types of dominoes need the transition of solid color dominoes to be arranged, and due to the ring structure, they need to transition back after one transition. Due to the above findings, "WW" and "BB" "Equal quantity" means that if "WB" and "BW" exist at the same time, there must be solid color cards (sufficient and necessary conditions) to make the scheme legal.

In other words, if there is a solid color plate in the original painting, we only need to ensure that the number of black and white is equal, then the scheme must be legal, and set the number of black as b b b. White quantity is w w w. The plan is obviously C 2 n − w − b n − w C_{2n-w-b}^{n-w} C2n−w−bn−w​

If not, we need to consider subtracting illegal schemes, that is, those with and only these two types of "WB" and "BW" dominoes, and it is not easy to calculate. Then the difficulty is the opposite. The essence of the situation is that there is no solid color dominoes minus all "WB" and all "BW".

The number of dominoes without coloring is easy to calculate. If a dominoes has only one grid without coloring or both, there is obviously only one scheme. If both grids are not colored, there are two, which meet the multiplication principle. If the original dominoes do not have any color subsequence in the case of opposite types of "WB" and "BW", it may be the case that they are all dominoes of these two types of "WB" and "BW".

code:

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=3e5+10;
const int p=998244353;

#define endl '\n'

int n;
string s[maxn];
ll fac[maxn],ifac[maxn];

ll qpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1) res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}

ll cal(int n,int m){
    return fac[n]*ifac[m]%p*ifac[n-m]%p;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    fac[0]=1;
    for(int i=1;i<=2*n;i++) fac[i]=fac[i-1]*i%p;
    ifac[2*n]=qpow(fac[2*n],p-2);
    for(int i=2*n-1;i>=0;i--){
        ifac[i]=ifac[i+1]*(i+1)%p;
    }

    bool f=0;
    int w=0,b=0,cnt=0;
    int c1=0,c2=0;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        if(s[i]=="BB"||s[i]=="WW") f=1;
        if(s[i][0]=='W') w++;
        if(s[i][1]=='W') w++;
        if(s[i][0]=='B') b++;
        if(s[i][1]=='B') b++;
        if(s[i]=="??") cnt++;
        if(s[i][0]=='W'||s[i][1]=='B') c1++;
        if(s[i][0]=='B'||s[i][1]=='W') c2++; 
    }
    if(w>n||b>n){
        cout<<0<<endl;
        return 0;
    }
    if(f){
        cout<<cal(2*n-w-b,n-w)<<endl;
        return 0;
    }

    ll ans=cal(2*n-w-b,n-w);
    ans=(ans-qpow(2,cnt)+p)%p;
    if(!c1) ans++;
    if(!c2) ans++;

    cout<<ans<<endl;
    return 0;
}