SRM474-创新互联

250pt

题意：在一个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的无向连通图，现要你生成一个生成树，并且满足每个点到0的距离正好为原图0到该点的最短路距离。求方案数。

思路：先求一边由0点出发的spfa，并统计每个点的最短路前驱有几个，接着乘法原理即可。

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-创新互联
文章链接：http://cdweb.net/article/dgdped.html

NEWS

网站建设资讯

SRM474-创新互联

其他资讯