1. Font Size
二分字体大小即可。
#include<stdlib.h>
#include<time.h>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<set>
#include<queue>
#include<bitset>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef unsigned long long UL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define sz(x) ((int)(x.size()))
#define sqr(x) ((x)*(x))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const int N = 1e3 + 7;
const int M = 1e4 + 7;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const LL LINF = 1e17 + 7;
const double Pi = acos(-1.);
const double EPS = 1e-8;
int n, w, h, p, a[N];
bool check(LL S) {
LL sum = 0;
LL perLine = w / S;
if (perLine == 0)
return false;
for (int i = 0; i < n; ++i) {
LL li = (a[i] - 1LL) / perLine + 1LL;
sum += li;
}
LL perPage = h / S;
return sum <= perPage * p;
}
int main() {
int TASK;
scanf("%d", &TASK);
while (TASK--) {
scanf("%d%d%d%d", &n, &p, &w, &h);
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
}
int L = 1, R = INF;
while (L + 1 < R) {
int MID = (L + R) >> 1;
check(MID) ? L = MID : R = MID;
}
int ans = check(R) ? R : L;
printf("%d\n", ans);
}
return 0;
}
2. 403 Forbidden
字典树
#include<stdlib.h>
#include<time.h>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<set>
#include<queue>
#include<bitset>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef unsigned long long UL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define sz(x) ((int)(x.size()))
#define sqr(x) ((x)*(x))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const int N = 1e3 + 7;
const int M = 1e4 + 7;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const LL LINF = 1e17 + 7;
const double Pi = acos(-1.);
const double EPS = 1e-8;
int n, m;
char str[N];
struct Node {
int st, time;
Node *nxt[2];
Node() {
clear();
}
void clear() {
st = 0;
time = INF;
nxt[0] = nxt[1] = NULL;
}
}*rt;
Node* newNode(int st = 0) {
Node *ret = (Node *) malloc(sizeof(Node));
ret->st = st;
ret->time = INF;
ret->nxt[0] = ret->nxt[1] = NULL;
return ret;
}
void insert(Node *nd, int x, int p, int st, int time) {
for (int i = 31; i >= 32 - p; --i) {
int y = ((x >> i) & 1);
if (nd->nxt[y] == NULL)
nd->nxt[y] = newNode();
nd = nd->nxt[y];
}
if (nd->st == 0) {
nd->st = st;
nd->time = time;
}
}
int check(Node *nd, int x) {
int ret = rt->st, time = rt->time;
for (int i = 31; i >= 0; --i) {
int y = ((x >> i) & 1);
if (nd->nxt[y] == NULL)
break;
nd = nd->nxt[y];
if (nd->st != 0 && nd->time < time) {
time = nd->time;
ret = nd->st;
}
}
if (time == INF)
return 0;
return ret;
}
void P(int x) {
for (int i = 31; i >= 0; --i) {
if ((i + 1) % 8 == 0)
putchar(' ');
printf("%d", (x >> i) & 1);
}
puts("");
}
int main() {
scanf("%d %d", &n, &m);
rt = newNode();
for (int i = 0; i < n; ++i) {
scanf(" %s", str);
int st = (str[0] == 'a' ? 1 : -1);
scanf(" %s", str);
int x = 0, y = 0, p = 32;
for (int j = 0; str[j]; ++j)
if (str[j] == '/') {
p = 0;
while (str[++j])
p = p * 10 + (str[j] - '0');
break;
} else if ('0' <= str[j] && str[j] <= '9') {
y = 0;
while ('0' <= str[j] && str[j] <= '9') {
y = (y * 10 + (str[j] - '0'));
++j;
}
--j;
x = ((x << 8) | y);
}
insert(rt, x, p, st, i);
}
for (int i = 0; i < m; ++i) {
scanf(" %s", str);
int x = 0, y = 0;
for (int j = 0; str[j]; ++j)
if ('0' <= str[j] && str[j] <= '9') {
y = 0;
while ('0' <= str[j] && str[j] <= '9') {
y = y * 10 + (str[j] - '0');
++j;
}
--j;
x = ((x << 8) | y);
}
int ret = check(rt, x);
puts(~ret ? "YES" : "NO");
}
return 0;
}
3. Demo Day
f[i][j]表示从(1,1)到(i,j)最少操作次数。 f[i][j]=min(f[k][j]+cost((k,j)→(i,j))+(a[i+1][j]!='b'),f[i][k]+cost((i,k)→(i,j))+(a[i][j+1]!='b'))
#include<stdlib.h>
#include<time.h>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<set>
#include<queue>
#include<bitset>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef unsigned long long UL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define sz(x) ((int)(x.size()))
#define sqr(x) ((x)*(x))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const int N = 1e2 + 7;
const int M = 1e6 + 7;
const int INF = 1e6 + 7;
const int MOD = 1e9 + 7;
const LL LINF = 1e17 + 7;
const double Pi = acos(-1.);
const double EPS = 1e-8;
int n, m, a[N][N], f[N][N], col[N][N], row[N][N];
char nxtChar() {
char ch = getchar();
while (!(ch == '.' || ch == 'b'))
ch = getchar();
return ch;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
a[i][j] = (nxtChar() == '.');
}
// for (int i = 1; i <= n; ++i) {
// for (int j = 1; j <= m; ++j)
// printf("%d ", a[i][j]);
// puts("");
// }
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
row[i][j] = row[i][j - 1] + (a[i][j] ^ 1);
}
for (int j = 1; j <= m; ++j)
for (int i = 1; i <= n; ++i) {
col[j][i] = col[j][i - 1] + (a[i][j] ^ 1);
}
for (int j = 1; j <= m; ++j) {
f[1][j] = row[1][j] + a[1][j + 1];
}
for (int i = 2; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
f[i][j] = INF;
for (int k = 1; k < i; ++k) {
f[i][j] = min(f[i][j],
f[k][j] + col[j][i] - col[j][k] + a[i + 1][j]);
}
for (int k = 1; k < j; ++k) {
f[i][j] = min(f[i][j],
f[i][k] + row[i][j] - row[i][k] + a[i][j + 1]);
}
}
printf("%d", f[n][m]);
return 0;
}
4. Building in Sandbox
放置方块的时候,判断6个方向相邻位置是否有方块。 方块的是否裸露,则反过来做,每次挖掉方块然后更新方块的状态,即是否暴露在外面。
#include<stdlib.h>
#include<time.h>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<set>
#include<queue>
#include<bitset>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef unsigned long long UL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define sz(x) ((int)(x.size()))
#define sqr(x) ((x)*(x))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const int N = 1e2 + 7;
const int M = 1e6 + 7;
const int INF = 2e5 + 7;
const int MOD = 1e9 + 7;
const LL LINF = 1e17 + 7;
const double Pi = acos(-1.);
const double EPS = 1e-8;
const int dx[] = { 0, 0, 0, 0, -1, 1 };
const int dy[] = { 0, 0, -1, 1, 0, 0 };
const int dz[] = { -1, 1, 0, 0, 0, 0 };
queue<int> que;
int n, p[M];
int v[N][N][N], f[N][N][N];
void init() {
memset(f, 0, sizeof(f));
memset(v, 0, sizeof(v));
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j) {
v[i][j][0] = 1;
}
}
bool chk(int x) {
return 0 <= x && x < N;
}
int F(int x, int y, int z) {
return (z << 16) | (y << 8) | (x);
}
void D(int S, int &x, int &y, int &z) {
x = (S & 255);
y = ((S >> 8) & 255);
z = ((S >> 16) & 255);
}
void bfs(int x, int y, int z) {
int xx, yy, zz;
while (!que.empty())
que.pop();
f[x][y][z] = true;
que.push(F(x, y, z));
while (!que.empty()) {
D(que.front(), x, y, z);
que.pop();
for (int j = 0; j < 6; ++j) {
xx = x + dx[j];
yy = y + dy[j];
zz = z + dz[j];
if (chk(xx) && chk(yy) && chk(zz) && !v[xx][yy][zz]
&& !f[xx][yy][zz]) {
f[xx][yy][zz] = true;
que.push(F(xx, yy, zz));
}
}
}
}
bool place() {
bool ret = true;
for (int i = 0; i < n; ++i) {
int x, y, z, xx, yy, zz;
scanf("%d%d%d", &x, &y, &z);
if (v[x][y][z] > 0)
ret = false;
bool flag = false;
for (int j = 0; j < 6; ++j) {
xx = x + dx[j];
yy = y + dy[j];
zz = z + dz[j];
if (chk(xx) && chk(yy) && chk(zz) && v[xx][yy][zz] > 0) {
flag = true;
break;
}
}
if (!flag) {
// printf("p %d %d %d\n", x, y, z);
ret = false;
}
++v[x][y][z];
p[i] = F(x, y, z);
}
return ret;
}
bool access() {
for (int i = n - 1; i >= 0; --i) {
int x, y, z, xx, yy, zz;
D(p[i], x, y, z);
bool flag = false;
for (int j = 0; j < 6; ++j) {
xx = x + dx[j];
yy = y + dy[j];
zz = z + dz[j];
if (chk(xx) && chk(yy) && chk(zz) && f[xx][yy][zz]) {
flag = true;
break;
}
}
if (!flag) {
// printf("a %d %d %d\n", x, y, z);
return false;
}
--v[x][y][z];
if (!v[x][y][z])
bfs(x, y, z);
}
return true;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
init();
bool ans = place();
if (ans) {
bfs(N - 1, N - 1, N - 1);
ans = access();
}
puts(ans ? "Yes" : "No");
}
return 0;
}