挺好的一场比赛，完全被自己的智商给碾压了啊。。。都是泪啊。。
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< ? ?
题解里面解释的很清楚了啊。。不再瞎说了啊。
#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< ? ?