bestcoder round 73 div2

Rikka with Chess
 Time Limit: 2000/1000 MS (Java/Others)
 
 Memory Limit: 65536/65536 K (Java/Others)
問題の説明

  n \times mn×m        ，                    。                    。

説明の入力

        T(T \leq 10)T(T≤10)       。

       ,       n,m(n \leq 10^9, m \leq 10^9)n,m(n≤10​9​​,m≤10​9​​)。

出力の説明

              ，           。

入力サンプル

3
1 2
2 2
3 3

出力サンプル

1
2
2

第一題では、直感的に法則を探さなければならないので、いくつかの簡単な例を試して、もう一度当ててみると、法則はn/2+m/2で、この結論の証明については、sorry、I can't.

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
int t,n,m;
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        cout<<n/2+m/2<<endl;
    }
    return 0;
}

Rikka with Graph
 Time Limit: 2000/1000 MS (Java/Others)
 
 Memory Limit: 65536/65536 K (Java/Others)
問題の説明

    ，          ，                ，         ：

     nn    n+1n+1       ，        （    ）  。

                        。

  ，                   ，       ？

説明の入力

              T(T \leq 30)T(T≤30)。

              n(n \leq 100)n(n≤100)。

    n+1n+1         u,vu,v         。

出力の説明

                 。

入力サンプル

1
3
1 2
2 3
3 1
1 3

出力サンプル

9

ここには重要な図論的性質があり、n個の頂点を持つ図があり、それを連通させるにはn-1個の辺が必要であるため、私たちはせいぜい2個しか削除できず、少なくとも1個削除することができ、それではn^2で削除した辺を列挙することができますが、どのようにそれが連通しているかどうかを判断しますか?最初は隣接行列(>0から、=0まではいけません.重いエッジがある可能性があるので)を前処理し、列挙するたびに対応するものを減らして、1から広く検索して、キュー長=nだけでいいです.しかしBFSでは、現在のキューポイントに接続されているノードをfori:=1 to n doで列挙することはできません.順方向テーブルを使うべきです(私は息子の表現法と呼んでいます)、最初からどの点がある点で達成できるかを記録して、広く探してそのすべての息子を列挙すればいいです.

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int a[105],b[105],p[105],g[105],son[105];
int f[105][105],s[105][105];
int tt,t,w,n,ans;
int main()
{
    cin>>tt;
    while(tt--)
    {
        cin>>n;
        ans=0;
        memset(f,0,sizeof(f));
        memset(son,0,sizeof(son));
        for(int i=1;i<=n+1;i++)
        {
            cin>>a[i]>>b[i];
            f[a[i]][b[i]]++;
            f[b[i]][a[i]]++;
            son[a[i]]++;
            son[b[i]]++;
            s[a[i]][son[a[i]]]=b[i];
            s[b[i]][son[b[i]]]=a[i];
        }
        for(int i=1;i<=n+1;i++)
        for(int j=1;j<=n+1;j++)
        if(i<=j)
        {
            memset(p,0,sizeof(p));
            f[a[i]][b[i]]--;
            f[b[i]][a[i]]--;
            if(i!=j)
            {
                f[a[j]][b[j]]--;
                f[b[j]][a[j]]--;
            }
            int t=0;
            int w=1;
            g[1]=1;
            p[1]=1;
            while(t<w)
            {
                t++;
                for(int k=1;k<=son[g[t]];k++)
                {
                    int id=s[g[t]][k];
                    if(f[g[t]][id]>=1&&p[id]==0)
                    {
                        w++;
                        g[w]=id;
                        p[id]=1;
                    }
                }
            }
            if(t==n) ans++;
            f[a[i]][b[i]]++;
            f[b[i]][a[i]]++;
            if(i!=j)
            {
                f[a[j]][b[j]]++;
                f[b[j]][a[j]]++;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}