Topcoder 酱油记

　　SRM 632 Div.2 (58/688):

　　这场是除了我第一场之外最简单的一场了，前两道太简单，一下就秒了。最后一题复杂度很微妙，感觉深搜会超时，结果貌似没超...看了一下别人的代码，觉得那些用map的人的代码很好，也学着写了一下。现在感觉map真是太有用了。

 1 // BEGIN CUT HERE
 2 
 3 // END CUT HERE
 4 #line 5 "GoodSubset.cpp"
 5 
 6 #include <string>
 7 #include <vector>
 8 #include <map>
 9 #include <iostream>
10 using namespace std;
11 typedef long long LL;
12 #define foreach(it,v) for(__typeof((v).rbegin()) it=(v).rbegin();it!=(v).rend();it++)
13 const int size = 50001;
14 
15 map<int, int> ans;
16 class GoodSubset {
17     public:
18     int numberOfSubsets(int goodValue, vector <int> d) {
19         for (int i = 0; i < d.size(); i++)
20         {
21             foreach(it, ans)
22             {
23                 LL y = it->first;
24                 if (y * d[i] >goodValue) continue;
25                 ans[y * d[i]] = (ans[y * d[i]] + it->second) % 1000000007ll;
26             }
27             ans[d[i]]++;
28         }
29         return ans[goodValue];
30     }
31 };

1000

　　SRM 633 Div.2 :

　　还是没升到Div.1...

　　1000是道简单的搜索题，被我想复杂了。注意到a*b=gcd(a,b)*lcm(a,b)，所以知道了a之后，我们就可以求出b了。所以对于每个连通分量，我们只需要枚举其中一个数的大小就行了。复杂度O(n*10000)。（这题我用最小最大值优化后挂了...所以对于竞赛来说，能不优化就不优化吧...）

　　做算法题不能只是注重算法，还是要分析所给数据范围。

 1 // BEGIN CUT HERE
 2 
 3 // END CUT HERE
 4 #line 5 "GCDLCMEasy.cpp"
 5 
 6 #include <string>
 7 #include <vector>
 8 #include <iostream>
 9 using namespace std;
10 typedef long long LL;
11 typedef vector<int> vi;
12 #define pb push_back
13 #define foreach(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
14 #define rep(i,n) for(int i=0;i<(n);i++)
15 #define FOR(i,l,r) for (int i=(l);i<=(r);i++)
16 const int maxn = 501, maxm = 500001;
17 
18 int x[maxn];
19 int g[maxn], l[maxn];
20 vi mat[maxn];
21 
22 bool vis[maxn];
23 int dl[maxn], po;
24 void bl(int v, vector <int> A, vector <int> B)
25 {
26     int l = 1, r = 1;
27     dl[r] = v; vis[v] = 1;
28     for (; l <= r; v = dl[++l])
29         for (auto i : mat[v])
30             if (!vis[A[i] ^ B[i] ^ v])
31                 dl[++r] = A[i] ^ B[i] ^ v, vis[dl[r]] = 1;
32     po = r;
33 }
34 class GCDLCMEasy {
35     public:
36     int gcd(int a, int b)
37     {
38         int temp;
39         while (b != 0) temp = b, b = a % b, a = temp;
40         return a;
41     }
42     string possible(int n, vector <int> A, vector <int> B, vector <int> G, vector <int> L) {
43         for (int i = 0; i < A.size(); i++)
44             mat[A[i]].pb(i), mat[B[i]].pb(i);
45         bool ans = 1;
46         for (int u = 0, v; u < n; u++) if (!vis[u])
47         {
48             bl(u, A, B);
49             for (x[u] = 1; x[u] <= 10000; x[u]++)
50             {
51                 for (int z = 2; z <= po; z++)
52                     x[dl[z]] = 0;
53                 bool exist = 1;
54                 for (int z = 1; z <= po; z++)
55                 {
56                     v = dl[z];
57                     for (auto i : mat[v])
58                     {
59                         int ww = A[i] ^ B[i] ^ v;
60                         if (!x[ww]) x[ww] = G[i] * L[i] / x[v];
61                         if (gcd(x[v], x[ww]) != G[i]
62                             || x[v] * x[ww] / gcd(x[v], x[ww]) != L[i]) { exist = 0; break; }
63                     }
64                     if (!exist) break;
65                 }
66                 if (exist) break;
67             }
68             ans &= (x[u] != 10001);
69         }
70         return ans ? "Solution exists" : "Solution does not exist";
71     }
72 };

//1000