设为首页 加入收藏

TOP

ZOJ Monthly, June 2014 月赛BCDEFGH题题解
2015-07-24 06:51:33 来源: 作者: 【大 中 小】 浏览:76次
Tags：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 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              #include 
             
               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 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
          #include 
          
            #include 
           
             #include 
            
              #include 
             
               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

缩点拓扑序下求最长链

题解：点击打开链接
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：cf 250 div2 下一篇：插入排序：表插入

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: