P1514 引水入城
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int A = 5e2 + 11;
const int inf = 0x3f3f3f3f;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {-1, 1, 0, 0};
inline int read() {
char c = getchar();
int x = 0, f = 1;
for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
struct node { int x, y; };
struct llrr { int l, r; } c[A];
int n, m, sum, h[A][A], l[A][A], r[A][A], vis[A][A];
inline bool cmp(llrr a, llrr b) {
return a.l != b.l ? a.l < b.l : a.r < b.r;
}
inline void bfs(int a[A][A], int sx, int sy, int v, int tag) {
if (a[sx][sy]) return;
queue <node> Q;
Q.push((node){sx, sy});
a[sx][sy] = v;
while (!Q.empty()) {
int x = Q.front().x, y = Q.front().y;
Q.pop();
for (int i = 0; i < 4; i++) {
int bx = x + dx[i], by = y + dy[i];
if (bx < 1 || bx > n || by < 1 || by > m || a[bx][by]) continue;
if (!tag && h[bx][by] >= h[x][y]) continue;
if (tag && h[bx][by] <= h[x][y]) continue;
Q.push((node){bx, by});
a[bx][by] = a[x][y];
}
}
}
int main() {
n = read(), m = read();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) h[i][j] = read();
for (int i = 1; i <= m; i++) bfs(vis, 1, i, 1, 0);
for (int i = 1; i <= m; i++) if (!vis[n][i]) sum++;
if (sum) return cout << "0
" << sum << '
', 0;
for (int i = 1; i <= m; i++) if (!l[n][i]) bfs(l, n, i, i, 1);
for (int i = m; i >= 1; i--) if (!r[n][i]) bfs(r, n, i, i, 1);
for (int i = 1; i <= m; i++) {
c[i].l = l[1][i], c[i].r = r[1][i];
}
sort(c + 1, c + 1 + m, cmp);
int to = 0, now = 1, ans = 0;
for (int i = 1; i <= m; i++) {
if (now >= c[i].l) to = max(to, c[i].r);
else ans++, now = to + 1, to = max(to, c[i].r);
}
if (now - 1 < m) ans++;
cout << "1
" << ans << '
';
return 0;
}
P1120 小木棍 ［数据加强版］
就使劲剪枝
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int A = 1e5 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
int n, len, sum, maxn, tot, a[A], vis[A];
bool cmp(int a, int b) {
return a > b;
}
bool dfs(int now, int lo, int last) {
if (now == n + 1 && lo == len) return true;
if (lo == len) lo = 0, last = 0;
for (int i = last + 1; i <= tot; i++) {
if (vis[i]) continue;
if (a[i] + lo > len) continue;
vis[i] = 1;
if (dfs(now + 1, lo + a[i], i)) return true;
vis[i] = 0;
//if (lo == 0 || lo + a[i] == len) return false;
while (a[i] == a[i + 1]) i++;
}
return false;
}
int main() {
n = read();
for (int i = 1; i <= n; i++) {
int x = read();
if (x <= 50) {
a[++tot] = x;
maxn = max(maxn, a[tot]);
sum += a[tot];
}
}
n = tot;
stable_sort(a + 1, a + 1 + tot, cmp);
for (len = maxn; len <= sum / 2; len++) {
if (sum % len) continue;
if (dfs(1, 0, 0)) {
cout << len << '
';
return 0;
}
}
cout << sum << '
';
return 0;
}
P1434 [SHOI2002]滑雪
直接乱搞
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int A = 1e3 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
int n, m, ans;
int f[A][A], a[A][A];
int work(int x, int y) {
if (f[x][y] != 0) return f[x][y];
int ans = 0;
if (x - 1 > 0)
if (a[x - 1][y] > a[x][y])
ans = max(ans, work(x - 1, y));
if (x + 1 > 0)
if (a[x + 1][y] > a[x][y])
ans = max(ans, work(x + 1, y));
if (y - 1 > 0)
if (a[x][y - 1] > a[x][y])
ans = max(ans, work(x, y - 1));
if (y + 1 > 0)
if (a[x][y + 1] > a[x][y])
ans = max(ans, work(x, y + 1));
f[x][y] = ans + 1;
return f[x][y];
}
int main() {
n = read(), m = read();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
a[i][j] = read();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (f[i][j] == 0)
f[i][j] = work(i, j);
ans = max(ans, f[i][j]);
}
}
cout << ans << "
";
return 0;
}
P1074 靶形数独
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int A = 5e5 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
const int score[10][10] = {
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 6, 6, 6, 6, 6, 6, 6, 6, 6},
{0, 6, 7, 7, 7, 7, 7, 7, 7, 6},
{0, 6, 7, 8, 8, 8, 8, 8, 7, 6},
{0, 6, 7, 8, 9, 9, 9, 8, 7, 6},
{0, 6, 7, 8, 9,10, 9, 8, 7, 6},
{0, 6, 7, 8, 9, 9, 9, 8, 7, 6},
{0, 6, 7, 8, 8, 8, 8, 8, 7, 6},
{0, 6, 7, 7, 7, 7, 7, 7, 7, 6},
{0, 6, 6, 6, 6, 6, 6, 6, 6, 6}, };
int pd(int i, int j) {
if(i <= 3 && j <= 3) return 1;
if(i <= 3 && j <= 6) return 2;
if(i <= 3 && j <= 9) return 3;
if(i <= 6 && j <= 3) return 4;
if(i <= 6 && j <= 6) return 5;
if(i <= 6 && j <= 9) return 6;
if(i <= 9 && j <= 3) return 7;
if(i <= 9 && j <= 6) return 8;
if(i <= 9 && j <= 9) return 9;
}
int a[11][11], hang[11][11], lie[11][11], sma[11][11];
int tot, ans = -1;
struct node { int sum, line; } qwq[11];
bool cmp(node a, node b) {
return a.sum < b.sum;
}
void coun() {
int now = 0;
for(int i = 1; i <= 9; i++)
for(int j = 1; j <= 9; j++)
now += a[i][j] * score[i][j];
ans = max(ans, now);
return;
}
void dfs(int cnt, int ho, int li) { //行、列、这一行填了多少个
if(cnt == 10) { coun(); return; }
if(li == 10) dfs(cnt + 1, qwq[cnt + 1].line, 1);
if(!a[ho][li]) {
for(int i = 1; i <= 9; i++) {
if(!hang[ho][i] && !lie[li][i] && !sma[pd(ho, li)][i]) {
hang[ho][i] = lie[li][i] = sma[pd(ho, li)][i] = 1;
a[ho][li] = i; dfs(cnt, ho, li + 1); a[ho][li] = 0;
hang[ho][i] = lie[li][i] = sma[pd(ho, li)][i] = 0;
}
}
}
else dfs(cnt, ho, li + 1);
}
int main() {
for(int i = 1; i <= 9; i++) {
tot = 0;
for(int j = 1; j <= 9; j++) {
a[i][j] = read();
if(a[i][j]) {
sma[pd(i, j)][a[i][j]] = 1;
hang[i][a[i][j]] = 1;
lie[j][a[i][j]] = 1;
}
else tot++;
qwq[i].line = i, qwq[i].sum = tot;
}
}
sort(qwq + 1, qwq + 1 + 9, cmp);
dfs(1, qwq[1].line, 1);
cout << ans; return 0;
}