250pt:
题意：给定n个网站，以及n个网站的关键词，还有一个危险词库。如果一个网站的关键词中>=th的危险词，那么这个网站便是危险的。同时，他的所有关键词加入危险词库。问，有多少个危险网站。
思路：直接模拟。
code:
#line 7 "InternetSecurity.cpp"
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
using namespace std; #define PB push_back
#define MP make_pair #define REP(i,n) for(i=0;i<(n);++i)
#define FOR(i,l,h) for(i=(l);i<=(h);++i)
#define FORD(i,h,l) for(i=(h);i>=(l);--i) typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef long long LL;
typedef pair<int,int> PII; class InternetSecurity
{
public:
vector<string> A[];
bool v[];
vector <string> determineWebsite(vector <string> wbs, vector <string> key, vector <string> dan, int th)
{
for (int i = ; i < key.size(); ++i){
string tmp;
stringstream ss;
A[i].clear();
ss << key[i];
while (ss >> tmp) A[i].PB(tmp);
// cout << A[i][A[i].size() - 1] << endl;
}
set<string> S;
memset(v, , sizeof(v));
for (int i = ; i < dan.size(); ++i) S.insert(dan[i]);
bool keepLooking = true;
while (keepLooking){
keepLooking = false;
for (int i = ; i < key.size(); ++i)
if (!v[i]){
int cnt = ;
for (int j = ; j < A[i].size(); ++j)
if (S.find(A[i][j]) != S.end()) ++cnt;
if (cnt >= th){
keepLooking = true;
v[i] = true;
for (int j = ; j < A[i].size(); ++j)
S.insert(A[i][j]);
}
}
}
vector<string> ans;
ans.clear();
for (int i = ; i < key.size(); ++i)
if (v[i]) ans.PB(wbs[i]);
return ans;
}
};
450pt:
题意：给定一个DAG的客户机及服务器之间的关系，服务器只有入边。现在求在那些边上装一些安全设置，使得所有客户机到服务器至少都有经过一个安全设置的边。
思路：因为是DAG，那么直接对原图进行一边搜索，记录直接点的状态，转移到根状态
code:
#line 7 "NetworkSecurity.cpp"
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
using namespace std; #define PB push_back
#define MP make_pair #define REP(i,n) for(i=0;i<(n);++i)
#define FOR(i,l,h) for(i=(l);i<=(h);++i)
#define FORD(i,h,l) for(i=(h);i>=(l);--i) typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef long long LL;
typedef pair<int,int> PII; class NetworkSecurity
{
public:
int n, m, ans;
bool vis[];
vector<string> S, C;
long long S1[];
void dfs(int u){
if (vis[u]) return;
vis[u] = true;
S1[u] = ;
for (int i = ; i < C[u].size(); ++i)
if (C[u][i] == 'Y'){
dfs(i);
S1[u] |= S1[i];
}
for (int i = ; i < S[u].size(); ++i)
if (S[u][i] == 'Y'){
if (!((1LL << i) & S1[u])){
++ans;
S1[u] |= (1LL << i);
}
}
}
int secureNetwork(vector <string> clientCable, vector <string> serverCable)
{
ans = ;
S = serverCable;
C = clientCable;
memset(vis, , sizeof(vis));
for (int i = ; i < S.size(); ++i)
if(!vis[i]) dfs(i);
return ans;
}
};