T1
Topcoder SRM 567 div1 Medium - StringGame
首先字母表定了之后两个人一定都会把字符串按字母表排序。对于这样的两个字符串，只需要数出两个串中每种字母分别有多少个，然后对着计数数组按字母表顺序比过去，在第一个不一样处更大的字典序小。因此先数一数每个字符串中每个字符出现的次数，把出现次数列成一张 \(n\) 行 \(26\) 列的表，然后问题相当于把每列视为整体，要你把所有列重排，要求某行严格最小（这里认为两行第一个不一样的列上的数大的行更小）。枚举每一行，依次决定把把哪一列扔到最前面去。第一次肯定要找一列使得别的行在这一列上的数都不大于当前行。把这一列扔到前面去了之后，我们可以删去这一列上的数小于当前行的行，然后重复这个过程。如果某次找不到合法列了，则这一行不可能成为最优行。如果到最后还有行没被删掉，那这一行也不可能成为最优行。否则就可以。
代码
#include <iostream>
#include <string.h>
#include <vector>
using namespace std;
int n;
bool vis[55];
int cnt[55][30];
vector<int> vec, tmp;
bool chs[30];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
string str;
cin >> str;
for (int j = 0; j < (int)str.size(); j++) cnt[i][str[j] - 'a']++;
}
for (int i = 1; i <= n; i++) {
bool ok = 1;
// cout << i << " i\n";
vec.clear();
for (int j = 1; j <= n; j++) {
if (j != i)
vec.emplace_back(j), vis[j] = 0;
}
memset(chs, 0, sizeof chs);
for (int asdf = 0; asdf < 26; asdf++) {
int lg = -1;
for (int j = 0; j < 26; j++) {
if (chs[j])
continue;
bool tmp = 1;
for (auto v : vec) tmp &= (cnt[v][j] <= cnt[i][j]);
if (tmp)
lg = j;
}
if (lg == -1) {
ok = 0;
break;
}
// cout << lg << " lg\n";
chs[lg] = 1;
for (auto v : vec) cnt[v][lg] < cnt[i][lg] ? void() : tmp.emplace_back(v);
vec.clear();
swap(vec, tmp);
}
ok &= vec.empty();
if (ok)
cout << i - 1 << " ";
}
cout << "\n";
return 0;
}
T2
Topcoder SRM 594 div1 Medium - FoxAndGo3
发现最终情况下白子和一个与他相邻的空格不会同时为空。所以在两者之间连边，发现是二分图。可以直接做二分图最大独立集。
代码
#include <iostream>
#include <string.h>
#include <queue>
#define int long long
using namespace std;
string str[55];
const int inf = 0x7ffffffffffffff;
int S = 2505, T = 2506;
int head[25005], nxt[100005], to[100005], res[100005], ecnt = 1;
void add(int u, int v, int ww) {
to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt, res[ecnt] = ww;
to[++ecnt] = u, nxt[ecnt] = head[v], head[v] = ecnt, res[ecnt] = 0;
}
queue<int> q;
int dep[25005];
int cur[25005];
bool bfs() {
q.push(S);
memset(dep, 0, sizeof dep);
dep[S] = 1;
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
if (!dep[v] && res[i] > 0) {
dep[v] = dep[x] + 1;
q.push(v);
}
}
}
return (dep[T] > 0);
}
int dfs(int x, int flow) {
if (!flow)
return 0;
if (x == T)
return flow;
int ret = 0;
for (int& i = cur[x]; i; i = nxt[i]) {
int v = to[i];
if (dep[v] == dep[x] + 1 && res[i]) {
int tmp = dfs(v, min(flow, res[i]));
res[i] -= tmp;
res[i ^ 1] += tmp;
flow -= tmp;
ret += tmp;
}
}
if (!ret)
dep[x] = 0;
return ret;
}
int Dinic() {
int ret = 0;
while (bfs()) {
for (int i = 1; i <= T; i++) cur[i] = head[i];
ret += dfs(S, inf);
}
return ret;
}
int n;
inline int f(int x, int y) { return (x - 1) * n + y; }
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> str[i];
str[i] = ' ' + str[i];
}
int t = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (str[i][j] == 'o') {
str[i - 1][j] == '.' ? add(f(i - 1, j), f(i, j), inf) : void();
str[i + 1][j] == '.' ? add(f(i + 1, j), f(i, j), inf) : void();
str[i][j - 1] == '.' ? add(f(i, j - 1), f(i, j), inf) : void();
str[i][j + 1] == '.' ? add(f(i, j + 1), f(i, j), inf) : void();
add(f(i, j), T, 1);
++t;
} else if (str[i][j] == '.') {
add(S, f(i, j), 1);
++t;
}
}
}
cout << t - Dinic() << "\n";
return 0;
}
T3
Topcoder SRM 521 div1 Hard - Chimney
发现填某一行时最多只有最上面三行是不完整的。所以可以大力分讨，合并等价状态，然后可以得到一个 \(9\) 个状态的 dp。然后将行内转移消去（即 如果 \(i \rightarrow j\)，\(j \rightarrow k\)，就直接 \(i \rightarrow k\)），发现这样只有四个状态会被转移到。所以只留这四个状态，就得到了一个 \(4\) 个状态的 dp。然后就可以直接矩乘了。由于最后答案所在的状态已经被删了，所以还要根据行内转移推出来。
代码
#include <iostream>
#define int long long
using namespace std;
const int P = 1000000007;
struct Matrix {
int a[4][4];
int* operator[](int x) { return a[x]; }
} I, E, T;
int t[4][4] = {
{ 2, 6, 32, 64 },
{ 2, 6, 32, 64 },
{ 1, 3, 16, 32 },
{ 0, 2, 12, 24 }
};
Matrix operator*(Matrix a, Matrix b) {
Matrix c;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
c[i][j] = 0;
for (int k = 0; k < 4; k++)
c[i][j] = (c[i][j] + a[i][k] * b[k][j] % P) % P;
}
}
return c;
}
Matrix qpow(Matrix x, int y) {
Matrix ret = E;
while (y) {
if (y & 1)
ret = ret * x;
y >>= 1;
x = x * x;
}
return ret;
}
int n;
signed main() {
cin >> n;
if (n == 1) {
cout << 24 << "\n";
return 0;
}
I[0][3] = 4;
for (int i = 0; i < 4; i++) {
E[i][i] = 1;
for (int j = 0; j < 4; j++)
T[i][j] = t[i][j];
}
I = I * qpow(T, n - 1);
cout << (16 * I[0][0] + 16 * I[0][1] + 8 * I[0][2] + 6 * I[0][3]) % P << "\n";
return 0;
}
T4
Topcoder SRM 431 div1 Hard - PerfectRectangles
怎么 d1t3 还放这种水题（
有一个很典的套路：枚举行，行上每个元素的值是这个元素往上到第一个不可选位置的距离，然后两遍单调栈求出每个位置往左往右最远到什么地方。注意到这样能够保证上左右边界极大，但是不保证下边界。所以只需要对每个位置再看它支配的区间在下面一行有没有不可选位置。如果有的话就计入答案，否则不计。
代码
#include <iostream>
#include <map>
#define int long long
using namespace std;
int n, m;
pair<int, int> stk[2005];
int sz;
int ans = 0;
int tol[2005], tor[2005];
bool a[2005][2005];
int up[2005][2005];
int X[4000005], Y[4000005];
int s[2005][2005];
map<pair<int, int>, int> mp[2005];
signed main() {
cin >> n >> m;
int X0, A, B, C, D, Y0;
cin >> X0 >> A >> B >> Y0 >> C >> D;
X[0] = X0 % n;
Y[0] = Y0 % n;
a[X[0] + 1][Y[0] + 1] = 1;
for (int i = 1; i < m; i++) {
X[i] = (X[i-1]*A+B) % n;
Y[i] = (Y[i-1]*C+D) % n;
a[X[i] + 1][Y[i] + 1] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
up[i][j] = (a[i][j] ? i : up[i - 1][j]);
s[i][j] = s[i][j - 1] + a[i][j];
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
stk[sz = 0] = make_pair(0, 0);
for (int j = 1; j <= n; j++) {
while (sz && i - up[i][j] <= stk[sz].first) --sz;
tol[j] = stk[sz].second + 1;
stk[++sz] = make_pair(i - up[i][j], j);
}
stk[sz = 0] = make_pair(0, n + 1);
for (int j = n; j; j--) {
while (sz && i - up[i][j] <= stk[sz].first) --sz;
tor[j] = stk[sz].second - 1;
stk[++sz] = make_pair(i - up[i][j], j);
}
for (int j = 1; j <= n; j++) mp[j].clear();
for (int j = 1; j <= n; j++) {
if (up[i][j] == i)
continue;
if (i == n || s[i + 1][tor[j]] != s[i + 1][tol[j] - 1]) {
if (mp[up[i][j]][make_pair(tol[j], tor[j])] == 0) {
mp[up[i][j]][make_pair(tol[j], tor[j])] = 1;
++ans;
}
}
}
}
cout << ans << "\n";
return 0;
}
T5
Topcoder SRM 437 div1 Hard - TheSum
后面再说。
代码
说了后面再说。
观察性质。
大力分讨。
不要乱改题目给的数据生成器！！！
标签：int,ret,dep,ecnt,2005,20240413,include From： https://www.cnblogs.com/forgotmyhandle/p/18139308