SRM474-創(chuàng)新互聯(lián)

250pt

題意：在一個N維的空間里，有一個人開始在原點，現(xiàn)在給出N<=50個指令序列，每個指令序列為某一維+1或者減一，問是否經過某個點至少2次。

10年積累的成都網站設計、做網站經驗，可以快速應對客戶對網站的新想法和需求。提供各種問題對應的解決方案。讓選擇我們的客戶得到更好、更有力的網絡服務。我雖然不認識你，你也不認識我。但先網站制作后付款的網站建設流程，更有茅箭免費網站建設讓你可以放心的選擇與我們合作。

思路：操作很小，直接模擬判斷即可

code：

 1 #line 7 "RouteIntersection.cpp"
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 #include 
 8 #include 
 9 #include 
10 #include 
11 #include 
12 #include 
13 #include 
14 #include 
15 #include 
16 #include 
17 #include 
18 #include 
19 #include 
20 #include 
21 #include 
22 #include 
23 #include 
24 #include 
25 using namespace std;
26 
27 #define PB push_back
28 #define MP make_pair
29 
30 #define REP(i,n) for(i=0;i<(n);++i)
31 #define FOR(i,l,h) for(i=(l);i<=(h);++i)
32 #define FORD(i,h,l) for(i=(h);i>=(l);--i)
33 
34 typedef vector VI;
35 typedef vector VS;
36 typedef vector VD;
37 typedef long long LL;
38 typedef pair PII;
39 
40 bool cmp(const pair& a, const pair& b){
41 return abs(a.second) > abs(b.second);
42 }
43 
44 class RouteIntersection
45 {
46 public:
47         vector< PII > P[65];
48 bool equal(int a,int b){
49 if (P[a].size() != P[b].size()) return false;
50 for (int i = 0; i < P[a].size(); ++i)
51   if (P[a] != P[b]) return false;
52 return true;
53         }
54 string isValid(int N, vector  coords, string moves)
55         {
56  int m = coords.size();
57                P[0].clear();
58  for (int i = 1; i <= m; ++i){
59  int p = -1, x = coords[i-1], y;
60  if (moves[i-1] == '+') y = 1;
61  else y = -1;
62                      P[i] = P[i-1];
63  for (int j = 0; j < P[i].size(); ++j)
64  if (P[i][j].first == x) p = j;
65  if (p == -1) P[i].push_back(make_pair(x, y));
66  else  P[i][p].second += y;
67                }
68  for (int i = 1; i <= m; ++i){
69                     sort(P[i].begin(), P[i].end(), cmp);
70 int sz = P[i].size();
71 while (sz > 0)
72  if (P[i][--sz].second == 0) P[i].pop_back();
73  else break;
74                     sort(P[i].begin(), P[i].end());
75                }
76  for (int i = 1; i <= m; ++i){
77  //  printf("%d
", P[i].size());
78   // for (int j = 0; j < P[i].size(); ++j)
79  //       printf("a = %d b = %d   ", P[i][j].first, P[i][j].second);
80   //    puts("");81 if (!P[i].size()) return "NOT VALID";
82 for (int j = i+1; j <= m; ++j)
83 if (equal(i, j)) return"NOT VALID";
84                }
85  return "VALID";
86         }
87 };

View Code

500pt

題意：題目給定N<=50的無向連通圖，現(xiàn)要你生成一個生成樹，并且滿足每個點到0的距離正好為原圖0到該點的最短路距離。求方案數。

思路：先求一邊由0點出發(fā)的spfa，并統(tǒng)計每個點的最短路前驅有幾個，接著乘法原理即可。

code：

 1 #line 7 "TreesCount.cpp"
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 #include 
 8 #include 
 9 #include 
10 #include 
11 #include 
12 #include 
13 #include 
14 #include 
15 #include 
16 #include 
17 #include 
18 #include 
19 #include 
20 #include 
21 #include 
22 #include 
23 #include 
24 #include 
25 using namespace std;
26 #define PB push_back
27 #define MP make_pair
28 #define Inf 0x3fffffff
29 #define REP(i,n) for(i=0;i<(n);++i)
30 #define FOR(i,l,h) for(i=(l);i<=(h);++i)
31 #define FORD(i,h,l) for(i=(h);i>=(l);--i)
32 #define M 1000000007
33 typedef vector VI;
34 typedef vector VS;
35 typedef vector VD;
36 typedef long long LL;
37 typedef pair PII;
38 
39 
40 class TreesCount
41 {
42 public:
43 int d[120], dg[120];
44 bool v[120];
45 int count(vector  S)
46         {
47 int n = S.size();
48               memset(dg, 0 , sizeof(dg));
49               memset(v, 0, sizeof(v));
50 for (int i = 0; i < n; ++i) d[i] = Inf;
51               queue q;
52               q.push(0);
53               d[0] = 0;
54               dg[0] = 1;
55               v[0] = true;
56 int x, dst;
57 while (!q.empty()){
58                    x = q.front();
59   for (int y = 0; y < n; ++y){
60                         dst = S[x][y] - '0';
61  if (dst > 0 && d[x] + dst <= d[y]){
62  if (d[x] + dst < d[y]){
63                                       dg[y] = 1;
64                                       d[y] = d[x] + dst;
65 if (!v[y]) q.push(y), v[y] = true;
66                               }
67  else ++dg[y];
68                         }
69                    }
70                    v[x] = false;
71                    q.pop();
72               }
73 long long ans = 1;
74 for (int i = 0; i < n; ++i)
75                  ans =  (ans * dg[i]) % M;
76 return ans;
77         }
78 };

View Code
文章題目：SRM474-創(chuàng)新互聯(lián)
本文URL：http://weahome.cn/article/dgdped.html

真实的国产乱ⅩXXX66竹夫人,五月香六月婷婷激情综合,亚洲日本VA一区二区三区,亚洲精品一区二区三区麻豆

SRM474-創(chuàng)新互聯(lián)

其他資訊

網站制作

企業(yè)服務

網站建設

服務器托管