#T1 扫雷
#题意简述
一个 (n imes m(n,mleq200)) 的网格，每个格子中的数字表示以该格子为中心的 (3 imes3) 的方格中地雷的数量，问总共有多少个地雷。
#大体思路
我们不需要知道地雷具体怎么摆放，所以只要找到一组点各自的势力范围能恰好覆盖整张地图即可，于是我们可以直接上下、左右各相隔三个进行选点。
#Code
const int N = 210;
int n, m, a[N][N], ans;
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= m; ++ j)
scanf("%d", &a[i][j]);
/*特别注意填充开始的边界*/
for (int i = n % 3 ? 1 : 2; i <= n; i += 3)
for (int j = m % 3 ? 1 : 2; j <= m; j += 3)
ans += a[i][j];
printf("%d", ans);
return 0;
}
#T2 翻转
#题意简述
有一个 (n imes m(n,mleq100)) 的 01 矩阵，现在需要将所有位置变为 (1)，改变的规则如下：
- 对于 ((a,b))，若 (exists xin[1,n],yin[1,m])，其中 ((a,y),(x,b),(x,y)) 均为 (1)，那么修改 ((a,b)) 的代价为 (3)，否则为 (4).
问最小代价。
#大体思路
考虑如何判断是否 (exists xin[1,n],yin[1,m])，其中 ((a,y),(x,b),(x,y)) 均为 (1)，不难发现，如果将 ((i,j)=1) 看作将第 (i) 行（(L.i)）和第 (j) 列（(A.j)）连接的话，那么意味着 (L.a,L.x,A.b,A.y) 应当在同一连通块内，而最终的状态一定有全图为一个连通块，于是我们一定需要将所有初始连通块连成一块，这需要以 (4) 的代价修改连通块数量减 (1) 个点，最后剩下的点的修改代价都为 (3).
#Code
const int N = 100010;
const int INF = 0x3fffffff;
/*用并查集维护连通块信息*/
struct DSU {
int siz[N], f[N], tot;
inline void init(int x) {
tot = x;
for (int i = 0; i <= x; ++ i)
f[i] = i, siz[i] = 1;
}
inline int find(int x) {
while (x != f[x]) x = f[x] = f[f[x]];
return x;
}
inline void merge(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
if (siz[x] > siz[y]) swap(x, y);
f[x] = y, siz[y] += siz[x], -- tot;
}
} dsu;
int n, m, tcnt, ans; char c;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> m; dsu.init(n + m);
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= m; ++ j) {
cin >> c; if (c == '1') dsu.merge(i, j + n), ++ tcnt;
}
ans = (dsu.tot - 1) * 4 + (n * m - tcnt - dsu.tot + 1) * 3;
cout << ans; return 0;
}
#T3 斜率
#题意简述
平面直角坐标系上 (n(nleq10^6)) 个点，可任选 (2) 个点连直线，找到斜率最接近 (frac P Q) 的直线的斜率。
#大体思路
我们考虑有一条斜率为 (frac PQ) 的直线在坐标系上平移，我们可以得到所有点按此方向在 (x) 轴上的投影，不难发现，斜率最接近 (frac PQ) 的两个点的投影一定相邻，这一点简单画图不难发现，于是我们直接按照投影位置进行排序即可。
#Code
#define db double
#define ll long long
const int N = 1000010;
const db INF = 1e10;
template <typename T> inline T ABS(const T &x) {return x < 0 ? -x : x;}
double tana, ans_gap = INF;
int n; ll p, q, nx, ny;
struct Point {
ll x, y;
bool operator < (const Point & b) const {
return -x * p + y * q < -b.x * p + b.y * q;
}
} a[N];
ll gcd(ll x, ll y) {return y ? gcd(y, x % y) : x;}
db calc(Point x, Point y) {
return x.x == y.x ? INF : (db)(x.y - y.y) / (db)(x.x - y.x);
}
int main() {
scanf("%d%lld%lld", &n, &p, &q);
tana = (db)p / (db)q;
for (int i = 1; i <= n; ++ i)
scanf("%lld%lld", &a[i].x, &a[i].y);
sort(a + 1, a + n + 1);
for (int i = 1; i < n; ++ i) {
db now_gap = ABS(calc(a[i], a[i + 1]) - tana);
if (now_gap < ans_gap) {
ans_gap = now_gap;
nx = ABS(a[i].x - a[i + 1].x);
ny = ABS(a[i].y - a[i + 1].y);
}
}
ll g = gcd(ny, nx);
printf("%lld/%lld", ny / g, nx / g);
return 0;
}
#T4 任务
#题意简述
有 (n(nleq 350)) 个人和 (n) 个不同的任务，第 (i) 个人高兴当且仅当他被分到 (i) 个任务，问将所有任务都分配下去后至少有一个人高兴的方案数（(mod10^9+7)）。
#大体思路
这种计数问题还是要去尝试 DP，设 (f_{i,j}) 表示前 (i) 个人分 (j) 个任务，至少有 (1) 个人高兴的方案数，考虑第 (i) 个人是否高兴。
第 (i) 个人高兴，则可以挑出 (i) 个直接给第 (i) 个人，剩下的 (j-i) 个可以随意的给 (i-1) 个人，于是方案总数为 (dbinom jicdot(i-1)^{j-i})
如果第 (i) 个人不高兴，那么设给了第 (i) 个人 (k(k e i)) 个任务，那么此时的方案数为前 (i-1) 个人分 (j-k) 个的方案数，于是该情况的总方案数为
#Code
#define ll long long
const int N = 510;
const int MOD = 1e9 + 7;
const int INF = 0x3fffffff;
int n; ll C[N][N], f[N][N];
inline void init_C(int x) {
for (int i = 0; i <= x; ++ i) C[i][0] = C[i][i] = 1;
for (int i = 1; i <= x; ++ i)
for (int j = 1; j < i; ++ j)
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
}
ll fpow(ll a, ll b) {
ll res = 1;
while (b) {
if (b & 1) (res *= a) %= MOD;
(a *= a) %= MOD, b >>= 1;
}
return res;
}
int main() {
scanf("%d", &n); init_C(n);
for (int i = 1; i <= n; ++ i)
for (int j = 0; j <= n; ++ j) {
if (j >= i) f[i][j] = fpow(i - 1, j - i) * C[j][i] % MOD;
for (int k = 0; k <= j; ++ k) {
if (k == i) continue;
(f[i][j] += f[i - 1][j - k] * C[j][k] % MOD) %= MOD;
}
}
printf("%lld", f[n][n]);
return 0;
}