SRM480-创新互联

250pt:

题意：给定n个网站，以及n个网站的关键词，还有一个危险词库。如果一个网站的关键词中>=th的危险词，那么这个网站便是危险的。同时，他的所有关键词加入危险词库。问，有多少个危险网站。

成都创新互联公司十载专注成都高端网站建设定制网站服务,为客户提供专业的成都网站制作,成都网页设计,成都网站设计服务;成都创新互联公司服务内容包含成都网站建设,重庆小程序开发,软件开发,网络营销推广,网络运营服务及企业形象设计;成都创新互联公司拥有众多专业的高端网站制作开发团队,资深的高端网页设计团队及经验丰富的架构师高端网站策划团队;我们始终坚持从客户的角度出发,为客户量身订造网络营销方案，解决网络营销疑问。

思路：直接模拟。

code:

 1 #line 7 "InternetSecurity.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 
41 class InternetSecurity
42 {
43 public:
44         vector A[400];
45 bool v[400];
46         vector  determineWebsite(vector  wbs, vector  key, vector  dan, int th)
47         {
48  for (int i = 0; i < key.size(); ++i){
49  string tmp;
50                      stringstream ss;
51                      A[i].clear();
52                      ss << key[i];
53  while (ss >> tmp)  A[i].PB(tmp);
54  //   cout << A[i][A[i].size() - 1] << endl;55                }
56  set S;
57                memset(v, 0, sizeof(v));
58  for (int i = 0; i < dan.size(); ++i) S.insert(dan[i]);
59  bool keepLooking = true;
60  while (keepLooking){
61                      keepLooking = false;
62  for (int i = 0; i < key.size(); ++i)
63  if  (!v[i]){
64  int cnt = 0;
65  for (int j = 0; j < A[i].size(); ++j)
66  if (S.find(A[i][j]) != S.end()) ++cnt;
67  if (cnt >= th){
68                                    keepLooking = true;
69                                    v[i] = true;
70 for (int j = 0; j < A[i].size(); ++j)
71                                        S.insert(A[i][j]);     
72                               }   
73                         }   
74                }
75                vector ans;
76                ans.clear();
77  for (int i = 0; i < key.size(); ++i)
78   if (v[i]) ans.PB(wbs[i]);
79  return ans;
80         }
81 };

View Code

450pt:

题意：给定一个DAG的客户机及服务器之间的关系，服务器只有入边。现在求在那些边上装一些安全设置，使得所有客户机到服务器至少都有经过一个安全设置的边。

思路：因为是DAG，那么直接对原图进行一边搜索，记录直接点的状态，转移到根状态

code:

 1 #line 7 "NetworkSecurity.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 
41 class NetworkSecurity
42 {
43 public:
44 int n, m, ans;
45 bool vis[1010];
46         vector S, C;
47 long long S1[200];
48 void dfs(int u){
49   if (vis[u]) return;
50              vis[u] = true;
51              S1[u] = 0;
52   for (int i = 0; i < C[u].size(); ++i)
53  if (C[u][i] == 'Y'){
54                         dfs(i);
55                         S1[u] |= S1[i];
56                   }
57   for (int i = 0; i < S[u].size(); ++i)
58 if (S[u][i] == 'Y'){
59   if (!((1LL << i) & S1[u])){
60                           ++ans;
61                           S1[u] |= (1LL << i);
62                       }
63                  }
64         }
65 int secureNetwork(vector  clientCable, vector  serverCable)
66         {
67                 ans = 0;
68                 S = serverCable;
69                 C = clientCable;
70                 memset(vis, 0, sizeof(vis));
71   for (int i = 0; i < S.size(); ++i)
72  if(!vis[i]) dfs(i);
73   return ans;
74         }
75 };

View Code
分享标题：SRM480-创新互联
文章路径：http://myzitong.com/article/dghojh.html

SRM480-创新互联

其他资讯