250pt:
水题set处理。
500pt：
题意：
给你一个图，每条边关联的两点为朋友，题目要求假设x的金钱为y，则他的左右的朋友当中的钱数z，取值为y - d <= z <= y + d.求使得任意两点的最大金钱差值，若果是inf输出-1.
思路：
求任意两点的最短的的最大值即可，比赛时不知道哪地方写搓了，直接被系统样例给虐了，老师这么悲剧500有思路能写，老师不仔细哎..
floyd求任意两点的最短距离好写一些。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
#include <string>
#include <set>
#include <functional>
#include <numeric>
#include <sstream>
#include <stack>
#include <map>
#include <queue> #define CL(arr, val) memset(arr, val, sizeof(arr)) #define lc l,m,rt<<1
#define rc m + 1,r,rt<<1|1
#define pi acos(-1.0)
#define ll __int64
#define L(x) (x) << 1
#define R(x) (x) << 1 | 1
#define MID(l, r) (l + r) >> 1
#define Min(x, y) (x) < (y) ? (x) : (y)
#define Max(x, y) (x) < (y) ? (y) : (x)
#define E(x) (1 << (x))
#define iabs(x) (x) < 0 ? -(x) : (x)
#define OUT(x) printf("%I64d\n", x)
#define lowbit(x) (x)&(-x)
#define keyTree (chd[chd[root][1]][0])
#define Read() freopen("din.txt", "r", stdin)
#define Write() freopen("dout.txt", "w", stdout); #define M 25000
#define N 207 using namespace std; const int inf = 0x7f7f7f7f;
const int mod = ; int f[N][N];
int n;
void floyd()
{
for (int k = ; k <= n; ++k)
{
for (int i = ; i <= n; ++i)
{
for (int j = ; j <= n; ++j)
{
if (f[i][k] != inf && f[k][j] != inf && f[i][j] > f[i][k] + f[k][j])
{
f[i][j] = f[i][k] + f[k][j];
}
}
}
} }
class Egalitarianism
{
public:
int maxDifference(vector <string> isF, int d)
{
n = isF.size();
for (int i = ; i <= n; ++i)
{
for (int j = ; j <= n; ++j) f[i][j] = inf;
}
for (int i = ; i < n; ++i)
{
for (int j = ; j < n; ++j)
{
if (isF[i][j] == 'Y')
{
f[i + ][j + ] = ;
}
}
}
floyd();
int Ma = ;
for (int i = ; i <= n; ++i)
{
for (int j = ; j <= n; ++j)
{
if (i == j) continue;
Ma = max(Ma,f[i][j]);
}
}
if (Ma == inf) return -;
else return Ma*d;
}
};
100pt：
题意：
有n个城市，给出每个城市的类型kind[i]表示i城市属于kind[i]类，然后给出已经发现的类型found[i]表示发现了found[i]类型， 然后给出k求满足有k个城市，并且这k个城市包含了m中已将发现的类型。（k个城市都是从已经发现的类型里面选的） 也即：知道m种数的每种数个数，然后将这些数放入K个箱子里面连，每个箱子只能放一个，要求放完后这k个箱子的数的种数为m
思路：
才开始想用组和公式方看看怎么放，可是那样考虑会有很多重复，而且不好去重。
dp其实很简单，可是就是想不到，弱逼的DP啊。 dp[i][j] 表示一共放了j个箱子，并且放了i种 则dp[i][j] += dp[i - 1][j - p]*c[found[i]][p];
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
#include <string>
#include <set>
#include <functional>
#include <numeric>
#include <sstream>
#include <stack>
#include <map>
#include <queue> #define CL(arr, val) memset(arr, val, sizeof(arr)) #define lc l,m,rt<<1
#define rc m + 1,r,rt<<1|1
#define pi acos(-1.0)
#define ll long long
#define L(x) (x) << 1
#define R(x) (x) << 1 | 1
#define MID(l, r) (l + r) >> 1
#define Min(x, y) (x) < (y) ? (x) : (y)
#define Max(x, y) (x) < (y) ? (y) : (x)
#define E(x) (1 << (x))
#define iabs(x) (x) < 0 ? -(x) : (x)
#define OUT(x) printf("%I64d\n", x)
#define lowbit(x) (x)&(-x)
#define keyTree (chd[chd[root][1]][0])
#define Read() freopen("din.txt", "r", stdin)
#define Write() freopen("dout.txt", "w", stdout); #define M 25000
#define N 107 using namespace std; const int inf = 0x7f7f7f7f;
const int mod = ;
ll dp[N][N];
ll c[][];
void init()
{
for (int i = ; i <= ; ++i)
{
c[i][i] = c[i][] = ;
}
for (int i = ; i <= ; ++i)
{
for (int j = ; j < i; ++j)
{
c[i][j] = c[i - ][j] + c[i - ][j - ];
}
}
}
class Excavations2
{
public:
int num[N]; long long count(vector <int> kind, vector <int> found, int K)
{
init();
int n = kind.size();
int m = found.size();
CL(num,); for (int i = ; i < n; ++i) num[kind[i]]++;
CL(dp,); dp[][] = ; for (int i = ; i < m; ++i)
{
for (int j = ; j <= K; ++j)
{
for (int p = ; p <= num[found[i]]; ++p)
{
if (j - p >= )
dp[i + ][j] += dp[i][j - p]*c[num[found[i]]][p];
}
}
}
return dp[m][K];
}
};