2020夏休み杭電第三場1005+1009そして調査集+数学

1005 Little W and Contest
タイトル
http://acm.hdu.edu.cn/showproblem.php?pid=6795
に言及
n個の点が与えられ、2つの点があり、重み値はそれぞれ1と2であり、
最初はn個の点が互いにつながっていなかった.最初はn個の点が互いにつながっていなかった.最初はn個の点が互いにつながっていなかった.
次にn−1辺を加え,毎回加わる辺の2つの端点が事前に連通していないことを保証する.
3つのポイントを選択するには、3つのポイントの重み値の和が5以上で、3つのポイントが互いに接続されていない場合に、異なる選択スキームの数を計算します.
エッジを追加するたびに、現在の連通状態で異なる選択スキームの数が出力されます.
問題解
初期状態の計算:重み値が1の点の数がcnt 1、重み値が2の点の数がcnt 2であると仮定し、
このときの異なるスキームの総数:ans=C 2 cnt 2 x C 1 cnt 1+C 3 cnt 2
エッジを追加するたびに、どの部分のシナリオが非合法なシナリオになるかを考えています.
エッジマージのたびに2つの連通ブロックが動作するため、uとvの間にエッジが追加されると仮定する.
そこで、n個の点を、uが存在する連通ブロックGu、vが存在する連通ブロックGv、その他の残点Grの3つの部分に分けた.
非合法な案は以下の4種類ある.
(1)Guは重み値が1の点を選択し,Gvは重み値が2の点を選択し,Grは重み値が2の点を選択する.
(2)Guは重み値2の点を選択し,Gvは重み値1の点を選択し,Grは重み値2の点を選択する.
(3)Guは重み値2の点を選択し,Gvは重み値2の点を選択し,Grは重み値2の点を選択する.
(4)Guは重み値2の点を選択し,Gvは重み値2の点を選択し,Grは重み値1の点を選択する.
参考ブログ:https://blog.csdn.net/njuptACMcxk/article/details/107641773
ACコード

#include
#include
#include
#include
#include

#define ll long long

using namespace std;

const int N=1e5+10, mod=1e9+7;

int T,n;
int w[N];
int cnt[3];
int p[N];
int p1[N],p2[N];

int Find(int x)
{
    if(p[x]!=x) p[x]=Find(p[x]);
    return p[x];
}

int C_2(int n)
{
    if(n<2) return 0;
    return (ll)(n-1)*n/2%mod;
}

int C_3(int n)
{
    if(n<3) return 0;
    return (ll)(n)*(n-1)*(n-2)/6%mod;
}

int main()
{  
    cin>>T;
    while(T--)
    {
        scanf("%d",&n);
        memset(cnt,0,sizeof cnt);
        for(int i=1;i<=n;i++) 
        {
            scanf("%d",&w[i]);p[i]=i;
            if(w[i]==1) {p1[i]=1, p2[i]=0;cnt[1]++;}
            else {p2[i]=1, p1[i]=0;cnt[2]++;}
        }
        int ans=(C_3(cnt[2])+(ll)C_2(cnt[2])*cnt[1]%mod)%mod;
        printf("%d
",ans);
        
        int u,v;
        for(int i=0;i<n-1;i++)
        {
            int k=0;
            scanf("%d%d",&u,&v);
            int pu=Find(u), pv=Find(v);

            k=(k+(ll)p1[pu]*p2[pv]*(cnt[2]-p2[pu]-p2[pv]))%mod;
    
            k=(k+(ll)p2[pu]*p1[pv]*(cnt[2]-p2[pu]-p2[pv]))%mod;
            
            k=(k+(ll)p2[pu]*p2[pv]*(cnt[2]-p2[pu]-p2[pv]))%mod;
            
            k=(k+(ll)p2[pu]*p2[pv]*(cnt[1]-p1[pu]-p1[pv]))%mod;
            
            ans=(ans-k+mod)%mod;
            printf("%d
",ans);
            p[pv]=pu;
            p1[pu]+=p1[pv], p2[pu]+=p2[pv];
            p1[pv]=0, p2[pv]=0;
        }
    }
    
    return 0;
}

1009 Parentheses Matching
タイトル:
http://acm.hdu.edu.cn/showproblem.php?pid=6799
に言及
文字列sには、()*の3つの文字が含まれます.*を左右のカッコに変換するか、変換しないことができます.sカッコマッチングに適合する場合、最小の辞書順を求めて出力する.答えが出ない「No solution!」
問題解
優先的に左から星を左かっこに変更し、右かっこのマッチングを完了します.右から星を右かっこに変更し、左かっこのマッチングを完了します.これで辞書順が最小になります.
コード#コード#

#include
#include
#include
#include
#include
#include
#define inf 2147483647
using namespace std;
typedef long long ll;
const int maxn = 100005;
char s[maxn];
int l[maxn],r[maxn],local[maxn];
int main()
{
//    freopen("1009.txt", "r", stdin);   // ¶áèë¸ÕD′μÄÎļt
//    freopen("1009zhz.out", "w", stdout);  // êä3ö½«òaêä3öμÄêy¾Y
    int T;
    int cnt=1;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",s);
        int len = strlen(s);
//        if(cnt==8708)
//            puts(s);
        int lena=0,lenb=0,star=0;
        for(int i=0; i<len; i++)
        {
            if(s[i]=='(')
                l[lena++]=i+1;
            else if(s[i]==')')
                r[lenb++]=i+1;
            else
                local[star++]=i+1;
        }
        l[lena]=0;
        r[lenb]=0;
        local[star]=0;
        bool falg = true;
        int beg=0;
        bool next = true;
        for(int i=0,j=0; i<lenb; i++)
        {
            if(l[j]<r[i]&&l[j]!=0)
                j++;
            else
            {
                if(star==beg)
                    falg = false;
                for(int z=beg; z<star; z++)
                {
                    if(local[z]<r[i])
                    {
                        s[local[z]-1] = '(';
                        beg++;
                        break;
                    }
                    else if(z+1==star)
                        falg = false;
                }
            }
            if(j+1>lena)
            {
                next = false;
            }

        }
        if(next)
            for(int i=lena-1,j=lenb-1; i>=0; i--)
            {
                if(l[i]<r[j])
                    j--;
                else
                {
                    if(star==beg)
                        falg = false;
                    for(int z=star-1; z>=beg; z--)
                    {
                        if(local[z]>l[i])
                        {
                            s[local[z]-1] = ')';
                            star--;
                            break;
                        }
                        else if(z==beg)
                            falg = false;
                    }
                }
            }
        if(falg)
        {
            for(int i=0; i<len; i++)
            {
                if(s[i]!='*')
                    printf("%c",s[i]);
            }
            puts("");
        }
        else
        {
            puts("No solution!");
        }
    }
    return 0;
}