ZOJ Monthly, June 2014 月赛BCDEFGH题题解

时间:2023-11-09 22:05:08

比赛链接:点击打开链接

上来先搞了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

缩点拓扑序下求最长链

题解:点击打开链接