250pt
题意：在一个N维的空间里，有一个人开始在原点，现在给出N<=50个指令序列，每个指令序列为某一维+1或者减一，问是否经过某个点至少2次。
思路：操作很小，直接模拟判断即可
code：
#line 7 "RouteIntersection.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; bool cmp(const pair<int, int>& a, const pair<int,int>& b){
return abs(a.second) > abs(b.second);
} class RouteIntersection
{
public:
vector< PII > P[];
bool equal(int a,int b){
if (P[a].size() != P[b].size()) return false;
for (int i = ; i < P[a].size(); ++i)
if (P[a] != P[b]) return false;
return true;
}
string isValid(int N, vector <int> coords, string moves)
{
int m = coords.size();
P[].clear();
for (int i = ; i <= m; ++i){
int p = -, x = coords[i-], y;
if (moves[i-] == '+') y = ;
else y = -;
P[i] = P[i-];
for (int j = ; j < P[i].size(); ++j)
if (P[i][j].first == x) p = j;
if (p == -) P[i].push_back(make_pair(x, y));
else P[i][p].second += y;
}
for (int i = ; i <= m; ++i){
sort(P[i].begin(), P[i].end(), cmp);
int sz = P[i].size();
while (sz > )
if (P[i][--sz].second == ) P[i].pop_back();
else break;
sort(P[i].begin(), P[i].end());
}
for (int i = ; i <= m; ++i){
// printf("%d\n", P[i].size());
// for (int j = 0; j < P[i].size(); ++j)
// printf("a = %d b = %d ", P[i][j].first, P[i][j].second);
// puts("");
if (!P[i].size()) return "NOT VALID";
for (int j = i+; j <= m; ++j)
if (equal(i, j)) return "NOT VALID";
}
return "VALID";
}
};
500pt
题意：题目给定N<=50的无向连通图，现要你生成一个生成树，并且满足每个点到0的距离正好为原图0到该点的最短路距离。求方案数。
思路：先求一边由0点出发的spfa，并统计每个点的最短路前驱有几个，接着乘法原理即可。
code：
#line 7 "TreesCount.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 Inf 0x3fffffff
#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)
#define M 1000000007
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef long long LL;
typedef pair<int,int> PII; class TreesCount
{
public:
int d[], dg[];
bool v[];
int count(vector <string> S)
{
int n = S.size();
memset(dg, , sizeof(dg));
memset(v, , sizeof(v));
for (int i = ; i < n; ++i) d[i] = Inf;
queue<int> q;
q.push();
d[] = ;
dg[] = ;
v[] = true;
int x, dst;
while (!q.empty()){
x = q.front();
for (int y = ; y < n; ++y){
dst = S[x][y] - '';
if (dst > && d[x] + dst <= d[y]){
if (d[x] + dst < d[y]){
dg[y] = ;
d[y] = d[x] + dst;
if (!v[y]) q.push(y), v[y] = true;
}
else ++dg[y];
}
}
v[x] = false;
q.pop();
}
long long ans = ;
for (int i = ; i < n; ++i)
ans = (ans * dg[i]) % M;
return ans;
}
};