D1T1> 神奇的幻方
模拟即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define drep(i, a, b) for (int i = a; i >= b; i--)
#define REP(i, a, b) for (int i = a; i < b; i++)
#define pb push_back
#define mp make_pair
#define clr(x) memset(x, 0, sizeof(x))
#define xx first
#define yy second using namespace std; typedef long long i64;
typedef pair<int, int> pii;
const int inf = ~0U >> ;
const i64 INF = ~0ULL >> ;
//****************************** int map[][];
int main() {
int n;
scanf("%d", &n);
pii last = mp(, n / + );
map[][n / + ] = ;
rep(i, , n * n) {
if (last.xx == && last.yy != n) {
map[n][last.yy + ] = i;
last = mp(n, last.yy + );
}
else if (last.yy == n && last.xx != ) {
map[last.xx - ][] = i;
last = mp(last.xx - , );
}
else if (last.xx == && last.yy == n) {
map[last.xx + ][last.yy] = i;
last = mp(last.xx + , last.yy);
}
else if (last.xx != && last.yy != n && !map[last.xx - ][last.yy + ]) {
map[last.xx - ][last.yy + ] = i;
last = mp(last.xx - , last.yy + );
}
else {
map[last.xx + ][last.yy] = i;
last = mp(last.xx + , last.yy);
}
}
rep(i, , n) {
rep(j, , n) {
if (j != ) printf(" ");
printf("%d", map[i][j]);
}
puts("");
}
return ;
}
D1T2> 信息传递
一个点只有一个出度 => 环不会交叉
1)dfs找环 2)tarjan找scc
考试的时候就直接写了tarjan...
#include <cstdio>
#include <cstring>
#include <algorithm>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define drep(i, a, b) for (int i = a; i >= b; i--)
#define REP(i, a, b) for (int i = a; i < b; i++)
#define pb push_back
#define mp make_pair
#define clr(x) memset(x, 0, sizeof(x))
#define xx first
#define yy second using namespace std; typedef long long i64;
typedef pair<int, int> pii;
const int inf = ~0U >> ;
const i64 INF = ~0ULL >> ;
//****************************** const int maxn = ; struct Ed {
int u, v, nx; Ed() {}
Ed(int _u, int _v, int _nx)
:u(_u), v(_v), nx(_nx) {}
} a[maxn];
int fst[maxn], cnt;
void addedge(int u, int v) {
a[++cnt] = Ed(u, v, fst[u]);
fst[u] = cnt;
} int dfn[maxn], low[maxn], Index, vis[maxn];
int stack[maxn], top;
int scc_cnt;
int belong[maxn], size[maxn];
void tarjan(int u) {
dfn[u] = low[u] = ++Index;
vis[u] = ;
stack[++top] = u;
for (int i = fst[u]; i; i = a[i].nx) {
int v = a[i].v;
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if (vis[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
scc_cnt++;
while (stack[top] != u) {
belong[stack[top]] = scc_cnt;
vis[stack[top]] = ;
size[scc_cnt]++;
top--;
}
belong[stack[top]] = scc_cnt;
vis[stack[top]] = ;
size[scc_cnt]++;
top--;
}
} int main() {
int n;
scanf("%d", &n);
rep(i, , n) {
int id;
scanf("%d", &id);
addedge(i, id);
} rep(i, , n) {
if (!dfn[i]) tarjan(i);
} int ans = 0x3f3f3f3f;
rep(i, , scc_cnt) if (size[i] != ) ans = min(ans, size[i]); printf("%d\n", ans);
return ;
}
D1T3> 斗地主
搜索题，以前在contest hunter上见过，没有订正...
因为1 2 3 4 5不能顺, 1 1 1 2 2 2不能连出，可以在读入时将牌的编号重新分配，只需要将 A 调整到 K 后，2 和 A 断开即可。
考试的时候想把所有可行的方案预处理出来，压位压在一起，然后状压dp，这样是不可行的，因为方案数多了后时间复杂度会爆炸。
以下代码可以过NOIP官方数据，但是过不了UOJ的加强版题目，会WA，这篇代码的思路主要是在每次判断时，人为地把4张和3张出掉，强剪枝。
#include <bits/stdc++.h>
#define rep(i, a, b) for (register int i = a; i <= b; i++)
#define drep(i, a, b) for (register int i = a; i >= b; i--)
#define REP(i, a, b) for (int i = a; i < b; i++)
#define pb push_back
#define mp make_pair
#define clr(x) memset(x, 0, sizeof(x))
#define xx first
#define yy second using namespace std; typedef long long i64;
typedef pair<int, int> pii;
const int inf = ~0U >> ;
const i64 INF = ~0ULL >> ;
//******************************** const int maxn = ; inline int read() {
int l = , s = ;
char ch = getchar();
while (ch < '' || ch > '') { if (ch == '-') l = -; ch = getchar(); }
while (ch >= '' && ch <= '') { s = (s << ) + (s << ) + ch - ''; ch = getchar(); }
return l * s;
} int poker[maxn]; int ans = inf; void dfs(int); void group(int base, int len, int dep) {
rep(st, , - len) {
if (poker[st] < base) continue;
int end;
for (end = st; end <= ; end++) if (poker[end] < base) break;
if (--end - st + < len) continue;
drep(k, end, st + len - ) {
rep(i, st, k) poker[i] -= base;
poker[] -= (k - st + ) * base;
dfs(dep + );
rep(i, st, k) poker[i] += base;
poker[] += (k - st + ) * base;
}
}
} int n, tong[maxn]; void dfs(int dep) {
if (dep > ans) return;
if (poker[] == ) return;
rep(i, , ) tong[poker[i]]++;
int sum();
while (tong[] > ) {
sum++;
tong[]--;
if (tong[] >= ) tong[] -= ;
else if (tong[] >= ) tong[] -= ;
}
while (tong[] > ) {
sum++;
tong[]--;
if (tong[] >= ) tong[] -= ;
else if (tong[] >= ) tong[] -= ;
}
if (tong[] >= && poker[] >= && poker[] >= ) sum--;
if (sum + tong[] + tong[] + dep < ans) ans = sum + tong[] + tong[] + dep;
tong[] = tong[] = ; group(, , dep);
group(, , dep);
group(, , dep);
} int main() {
int T;
T = read(), n = read();
while (T--) {
memset(poker, , sizeof(poker));
rep(i, , n) {
int rb, id;
id = read(); rb = read();
if (id >= && id <= ) poker[id - ]++;
else if (id == ) poker[]++;
else if (id == ) poker[]++;
else if (id == && poker[] == ) poker[]++;
else poker[]++;
}
poker[] = n;
ans = inf;
dfs();
printf("%d\n", ans);
}
return ;
}
这一篇代码依然可以过NOIP官方数据，但是在UOJ加强版上在第9个extra test上t了，不知道卡时是否可以。
这个思路考虑了 AAAA2222 在一次出完的情况， 还考虑了在4带2时可以破坏3个一样的牌的情况，分别写出来就好了。
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define drep(i, a, b) for (int i = a; i >= b; i--)
#define REP(i, a, b) for (int i = a; i < b; i++)
#define pb push_back
#define mp make_pair
#define clr(x) memset(x, 0, sizeof(x))
#define xx first
#define yy second using namespace std; typedef long long i64;
typedef pair<int, int> pii;
const int inf = ~0U >> ;
const i64 INF = ~0ULL >> ;
//******************************** const int maxn = ; int poker[maxn]; int ans = inf; void dfs(int dep, int order) {
if (dep > ans) return;
if (dep + poker[] < ans) ans = dep + poker[];
if (poker[] == ) return; //AAABBBCCC
if (order <= )
rep(st, , ) {
if (poker[st] < ) continue;
int end;
for (end = st; end <= ; end++) if (poker[end] < ) break;
end--; if (end - st < ) break;
rep(k, st + , end) {
rep(i, st, k) poker[i] -= ;
poker[] -= (k - st + ) * ;
dfs(dep + , );
rep(i, st, k) poker[i] += ;
poker[] += (k - st + ) * ;
}
} //AABBCC
if (order <= )
rep(st, , ) {
if (poker[st] < ) continue;
int end;
for (end = st; end <= ; end++) if (poker[end] < ) break;
end--; if (end - st + < ) continue;
rep(k, st + , end) {
rep(i, st, k) poker[i] -= ;
poker[] -= (k - st + ) * ;
dfs(dep + , );
rep(i, st, k) poker[i] += ;
poker[] += (k - st + ) * ;
}
} //ABCDE
if (order <= )
rep(st, , ) {
if (poker[st] < ) continue;
int end;
for (end = st; end <= ; end++) if (poker[end] < ) break;
end--; if (end - st + < ) continue;
rep(k, st + , end) {
rep(i, st, k) poker[i] -= ;
poker[] -= k - st + ;
dfs(dep + , );
rep(i, st, k) poker[i] += ;
poker[] += k - st + ;
}
} //AAAABC
if (order <= )
rep(st, , ) {
if (poker[st] < ) continue;
rep(i, , ) {
if (poker[i] < || i == st) continue;
poker[i] -= ;
rep(j, i, ) {
if (poker[j] < || j == st) continue;
poker[st] -= ; poker[j] -= ;
poker[] -= ;
dfs(dep + , );
poker[st] += ; poker[j] += ;
poker[] += ;
}
poker[i] += ;
}
} //AAAABBCC
if (order <= )
rep(st, , ) {
if (poker[st] < ) continue;
rep(i, , ) {
if (poker[i] < || i == st) continue;
poker[i] -= ;
rep(j, i, ) {
if (poker[j] < || j == st) continue;
poker[st] -= , poker[j] -= ;
poker[] -= ;
dfs(dep + , );
poker[st] += , poker[j] += ;
poker[] += ;
}
poker[i] += ;
}
} //AAABB
if (order <= )
rep(st, , ) {
if (poker[st] < ) continue;
rep(i, , ) {
if (poker[i] < || i == st) continue;
poker[st] -= , poker[i] -= ;
poker[] -= ;
dfs(dep + , );
poker[st] += , poker[i] += ;
poker[] += ;
}
} //AAAB
if (order <= )
rep(st, , ) {
if (poker[st] < ) continue;
rep(i, , ) {
if (poker[i] < || i == st) continue;
poker[st] -= , poker[i] -= ;
poker[] -= ;
dfs(dep + , );
poker[st] += , poker[i] += ;
poker[] += ;
}
} //AAAA
if (order <= )
rep(st, , ) {
if (poker[st] < ) continue;
poker[st] -= , poker[] -= ;
dfs(dep + , );
poker[st] += , poker[] += ;
} //AAA
if (order <= )
rep(st, , ) {
if (poker[st] < ) continue;
poker[st] -= , poker[] -= ;
dfs(dep + , );
poker[st] += , poker[] += ;
} //AA
if (order <= )
rep(st, , ) {
if (poker[st] < ) continue;
poker[st] -= , poker[] -= ;
dfs(dep + , );
poker[st] += , poker[] += ;
} //Joker
if (order <= )
if (poker[] && poker[]) {
poker[] = poker[] = ;
poker[] -= ;
dfs(dep + , );
poker[] = poker[] = ;
poker[] += ;
}
} int main() {
int T, n;
scanf("%d%d", &T, &n);
while (T--) {
memset(poker, , sizeof(poker));
rep(i, , n) {
int rb, id;
scanf("%d%d", &id, &rb);
if (id >= && id <= ) poker[id - ]++;
else if (id == ) poker[]++;
else if (id == ) poker[]++;
else if (id == && poker[] == ) poker[]++;
else poker[]++;
}
poker[] = n;
ans = inf;
dfs(, );
printf("%d\n", ans);
}
return ;
}
D2T1> 跳石头
二分+贪心。
noi.openjudge.cn的原题，首先二分答案，在二分答案的情况下，扫一遍n个石头，如果这个石头与前一个石头的距离小于二分的答案，那么就把前一个石头取消。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define drep(i, a, b) for (int i = a; i >= b; i--)
#define REP(i, a, b) for (int i = a; i < b; i++)
#define pb push_back
#define mp make_pair
#define clr(x) memset(x, 0, sizeof(x))
#define xx first
#define yy second using namespace std; typedef long long i64;
typedef pair<int, int> pii;
const int inf = ~0U >> ;
const i64 INF = ~0ULL >> ;
//****************************** int map[][];
int main() {
int n;
scanf("%d", &n);
pii last = mp(, n / + );
map[][n / + ] = ;
rep(i, , n * n) {
if (last.xx == && last.yy != n) {
map[n][last.yy + ] = i;
last = mp(n, last.yy + );
}
else if (last.yy == n && last.xx != ) {
map[last.xx - ][] = i;
last = mp(last.xx - , );
}
else if (last.xx == && last.yy == n) {
map[last.xx + ][last.yy] = i;
last = mp(last.xx + , last.yy);
}
else if (last.xx != && last.yy != n && !map[last.xx - ][last.yy + ]) {
map[last.xx - ][last.yy + ] = i;
last = mp(last.xx - , last.yy + );
}
else {
map[last.xx + ][last.yy] = i;
last = mp(last.xx + , last.yy);
}
}
rep(i, , n) {
rep(j, , n) {
if (j != ) printf(" ");
printf("%d", map[i][j]);
}
puts("");
}
return ;
}
D2T2> 子串
dp。
用f[i][j][k][2]表示第一个字符串中的前i位，取出k段，按顺序组合，拼出第二个字符串前j位的方案数，最后一位若为1则表示第i位被考虑在内(被选取)，为0则为不被选取。
那么当S[i] == T[j]时(S 为 第一个字符串，T 为 第二个字符串)
f[i][j][k][1] = f[i - 1][j - 1][k][1] + f[i - 1][j - 1][k - 1][0] + f[i - 1][j - 1][k - 1][1];
f[i][j][k][0] = f[i - 1][j][k][0];
否则 f[i][j][k][1] = 0, f[i][j][k][0] = f[i - 1][j][k][0] + f[i - 1][j][k][1];
解释:当前字符能否接下去(假若S[i] ==T[j])实则取决于第i - 1个字符是否选取。
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define drep(i, a, b) for (int i = a; i >= b; i--)
#define REP(i, a, b) for (int i = a; i < b; i++)
#define pb push_back
#define mp make_pair
#define clr(x) memset(x, 0, sizeof(x))
#define xx first
#define yy second using namespace std; typedef long long i64;
typedef pair<int, int> pii;
const int inf = ~0U >> ;
const i64 INF = ~0ULL >> ;
//******************************* const int maxn = , maxm = ;
const int mod = ; int read() {
int s = , l = ;
char ch = getchar();
while (ch < '' || ch > '') { if (ch == '-') l = -; ch = getchar(); }
while (ch >= '' && ch <= '') { s = (s << ) + (s << ) + ch - ''; ch = getchar(); }
return l * s;
} char str1[maxn], str2[maxm];
i64 f[][maxm][maxm][]; int main() {
int n, m, k;
n = read(), m = read(), k = read();
scanf("%s%s", str1 + , str2 + );
f[][][][] = f[][][][] = ;
int flag = ;
rep(i, , n) {
flag ^= ;
int up = min(i, m);
rep(j, , up) {
if (str1[i] == str2[j]) rep(kk, , j) {
f[flag][j][kk][] = (f[ ^ flag][j][kk][] + f[ ^ flag][j][kk][]) % mod;
f[flag][j][kk][] = (f[ ^ flag][j - ][kk][] + f[ ^ flag][j - ][kk - ][] + f[ ^ flag][j - ][kk - ][]) % mod;
}
else rep(kk, , j) {
f[flag][j][kk][] = (f[ ^ flag][j][kk][] + f[ ^ flag][j][kk][]) % mod;
f[flag][j][kk][] = ;
}
}
}
printf("%lld\n", (f[flag][m][k][] + f[flag][m][k][]) % mod);
return ;
}
D2T3> 运输计划
两天内改完......
总结:考得挺扯蛋的，335，非常不满意:(
暴力分没有拿全，对算法的掌握不够深刻，最恶心的是做过的题也不会。
这TM混蛋的人生又干掉了我的希望，就这样吧，也没什么好说的...