程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> BestCoder Round #25 A，B

BestCoder Round #25 A，B

編輯：C++入門知識

BestCoder Round #25 A，B

挺好的一場比賽，完全被自己的智商給碾壓了啊。。。都是淚啊。。

A，判斷有向圖中是否有環，數據很小簡單粗暴的暴力算法可解啊。暴力枚舉有關系兩個點判斷反向是否可以找到，如果可以就說明有環。。。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#define eps 1e-9
///#define M 1000100
///#define LL __int64
#define LL long long
///#define INF 0x7ffffff
#define INF 0x3f3f3f3f
#define PI 3.1415926535898
#define zero(x) ((fabs(x) g[maxn];

int flag;


void dfs(int x, int y)
{
    if(x == y)
    {
        flag = 1;
        return;
    }
    if(vis[x]) return;
    vis[x] = 1;
    int n = g[x].size();
    for(int i = 0; i < n; i++) dfs(g[x][i], y);
}

int main()
{
    int n;
    int m;
    while(cin >>n>>m)
    {
        int x, y;
        flag = 0;
        memset(mp, 0, sizeof(mp));
        for(int i = 0; i <= n; i++) g[i].clear();
        for(int i = 0; i < m; i++)
        {
            scanf("%d %d",&x, &y);
            mp[x][y] = 1;
            g[x].push_back(y);
        }
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(!mp[i][j]) continue;
                memset(vis, 0, sizeof(vis));
                dfs(j, i);
                if(flag) break;
            }
            if(flag) break;
        }
        if(flag) cout<<"NO"<

B，dp題目。我們一行一行的考慮。dp[i][j],表示前i行，都滿足了每一行至少有一個寶石的條件，而只有j列滿足了有寶石的條件的情況有多少種。枚舉第i+1行放的寶石數k，這k個當中有t個是放在沒有寶石的列上的，那麼我們可以得到轉移方程：

dp[i+1][j+t]+=dp[i][j]*c[m-j][t]*c[j][k-t]，其中c[x][y]，意為在x個不同元素中無序地選出y個元素的所有組合的個數。 
題解裡面解釋的很清楚了啊。。不再瞎說了啊。
 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#define eps 1e-9
///#define M 1000100
///#define LL __int64
#define LL long long
///#define INF 0x7ffffff
#define INF 0x3f3f3f3f
#define PI 3.1415926535898
#define zero(x) ((fabs(x)= 0; t--)
                    {
                        if(m-j < 0 || k-t < 0) continue;
                        dp[i+1][j+t] += (dp[i][j]*cnk[m-j][t]%mod)*cnk[j][k-t]%mod;
                        dp[i+1][j+t] %= mod;
                    }
                }
            }
        }
        cout<