首页 > 代码库 > ZOJ Monthly, June 2014 月赛BCDEFGH题题解
ZOJ Monthly, June 2014 月赛BCDEFGH题题解
比赛链接:点击打开链接
上来先搞了f、c,,然后发现状态不正确,一下午都是脑洞大开,,
无脑wa,无脑ce。。。一样的错犯2次。。
硬着头皮搞了几发,最后20分钟码了一下G,不知道为什么把1直接当成不能加油的站就会wa。。太弱。。
唔···太懒第二天才发题解。。
B:Gears
并查集
题解:点击打开链接
C:Consecutive Blocks
离散化一下然后模拟
题解:点击打开链接
D:An Easy Game
设dp[i][j]为前i个位置已经匹配了j个位置的方法数。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <math.h> #include <queue> #include <string> #include <vector> #include <stack> #include <map> #include <set> #include <algorithm> #include <iostream> using namespace std; #define ll long long #define mod 1000000009 #define N 105 int n, K, m; int dp[N][N]; int C[N][N]; string s1; string s2; int dfs(int differ, int left) { if (left == 0) { return differ == 0; } else { if (~dp[differ][left]) { return dp[differ][left]; } int &ans = dp[differ][left]; ans = 0; int a = differ; int b = n - differ; for (int i = 0; i <= differ && i <= m; ++i) { if (b >= m - i) { ans += (int)((ll)C[b][m - i] * C[a][i] % mod * dfs(differ - i + (m - i), left - 1) % mod); ans %= mod; } } return ans; } } int main(){ for (int i = 0; i < N; ++i) { C[i][i] = 1; for (int j = 0; j < i; ++j) { C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; C[i][j] %= mod; } } while (cin >> n >> K >> m){ cin >> s1 >> s2; int nSum = 0; int nLen = s1.length(); for (int i = 0; i < nLen; ++i) { if (s1[i] != s2[i]) { ++nSum; } } memset(dp, -1, sizeof(dp)); int ans = dfs(nSum, K); printf("%d\n", ans); } return 0; }
E:Romantic Value
简单最小割。
题解:点击打开链接
F:First Digit
屌丝题。。
#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <math.h> #include <stdlib.h> #include <time.h> using namespace std; int main() { int T ,m,u,v,w; scanf("%d",&T); while(T--){ scanf("%d%d",&u,&v);puts("1"); } return 0; }
G:Greedy Driver
spfa2次,,
题解:点击打开链接
H:Grouping
缩点拓扑序下求最长链
题解:点击打开链接
ZOJ Monthly, June 2014 月赛BCDEFGH题题解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。