topcoder 643 DIV2

太弱了，太弱了！

A:基本的判断吧，然后就是边界问题，写了好久，结果发现时房间第二个交的。。

B:真心跪了，还好想出来了，思路想的太慢太慢，结果交上去，落后太多，不过HACK时很多人挂了，

这也是DIV1的A题。做法是：

如果对于一个long long 的数质因数分解师很难做到的。

但是题目告诉了m/2个数，m是分解后质因数的个数。

然后我们想先刷法求出1-10^6的质因数。

如果n有大于10^6的质因数最多2个（n<=10^18)对吧。

然后已经写出了1个，一定会写出一个。

所以我们对其用1-10^6的素数刷选。

留下的n!=1的也是素数。保存的数再排序。

C:题给跪了，

看的出来时比较简单的题目，比以前的题目都要简单，可就是想不出。

看看别人的代码，只剩下ORZ。

 #include <string>

 #include <vector>

 #include<iostream>

 #include<string.h>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 typedef long long ll;

 int dp[][][];

 int b[][][];

 vector<int>mp[];

 #define inf 0x3f3f3f

 int n;

 int son[];

 class TheKingsTree {

     public:

     int dfs(int u,int red,int green)

     {

         if (b[u][red][green]) return dp[u][red][green];

         b[u][red][green]=;

         int c1=red+;

         int c2=green+;

         for (int i=;i<mp[u].size();i++)

         {

             c1+=dfs(mp[u][i],red+,green);

             c2+=dfs(mp[u][i],red,green+);

         }

         return dp[u][red][green]=min(c1,c2);

     }

     int getNumber(vector <int> parent) {

     for (int i=;i<parent.size();i++)

     mp[parent[i]].push_back(i+);

     return dfs(,,);

     }

 };

 // Powered by FileEdit

 // Powered by TZTester 1.01 [25-Feb-2003]

 // Powered by CodeProcessor

我把我理解的大概写一下：

DFS（0,0,0）是从节点0开始遍历且其子节点red=0,green=0;

还要记录状态是否保存了。记忆花搜索

c1=red+1;（采用的是一种我认为的倒序方式）

当前节点为red 然后要加上其值，

c1+=dfs(v,red+1,green);

是把v染成red的值。c1要加上其值。

C2是代表green 依次类推

PS:这种方程在比赛中时怎么也写不出来的。

巴特西

topcoder 643 DIV2

最新文章

热门文章