排位赛 13 题解
题型
- A - 贪心 √
- B - 后缀数组 √
- C - 环形DP
- D - 二维树状数组/二维线段树 √
- E - DFS找连通块 √
- F - 快速傅里叶变换（FFT）
- G - DFS/二分 √
- H - 最小比率生成树/二分/迭代
A - domino
题意
给出放骨牌位置之间的距离，和可以推骨牌的次数，求最少的骨牌高度和。
思路
贪心。统计只推一次所需要的骨牌高度，然后排序，减去最高高度即可。
代码
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
//#define LOCAL
#define LL __int64 // 1e5*1e5会爆int
const int maxn = 1e5+7;
int h[maxn];
int main(){
#ifdef LOCAL
freopen("in.txt", "r", stdin);
#endif
int t; scanf("%d", &t);
while (t--) {
int n, k;
scanf("%d%d", &n, &k);
for (int i = 0; i < n-1; ++i)
scanf("%d", h+i);
sort(h, h+n-1);
LL ans = 0;
for (int i = 0; i < n-k; ++i)
ans += h[i];
ans += n;
printf("%I64d\n", ans);
}
return 0;
}
B - Sequence
题意
给出一个数字串，将其分为三段，每段都翻转过来，求可以得到的字典序最小的串。
思路
后缀数组。现学现卖系列。本来用贪心法，结果发现不能过，翻了大白书才发现是后缀数组。先将整个数列翻转过来求SA，然后找到第一个位置不在最后两个的后缀，作为一个的指针位置。然后求第二个指针位置。这里要注意一点，要将后面的串复制一遍然后求后缀数组。
代码
\\用的不是正统倍增法，而是用sort简化了
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define LOCAL
const int maxn = 200000+107;
int n, num[maxn], rev_num[maxn], k;
int rank[maxn], temp[maxn], sa[maxn];
bool cmp(int i, int j) {
if (rank[i] != rank[j]) return rank[i] < rank[j];
int x = i+k<=n?rank[i+k]:-1;
int y = j+k<=n?rank[j+k]:-1;
return x < y;
}
void get_sa(int a[], int m) {
for (int i = 0; i <= m; ++i) {
sa[i] = i;
rank[i] = i<n? a[i] : -1;
}
for (k = 1; k <= n; k<<=1) {
sort(sa, sa+m+1, cmp);
temp[sa[0]] = 0;
for (int i = 1; i <= m; ++i)
temp[sa[i]] = temp[sa[i-1]] + (cmp(sa[i-1], sa[i])?1:0);
for (int i = 0; i <= n; ++i)
rank[i] = temp[i];
}
}
int main(){
#ifdef LOCAL
freopen("in.txt", "r", stdin);
#endif
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d", num+i);
reverse_copy(num, num+n, rev_num);
get_sa(rev_num, n);
int cur1;
for (int i = 0; i <= n; ++i) {
cur1 = n - sa[i];
if (cur1 >= 1 && n-cur1 >= 2) break;
}
int m = n - cur1;
reverse_copy(num+cur1, num+n, rev_num);
reverse_copy(num+cur1, num+n, rev_num+m);
get_sa(rev_num, m*2);
int cur2;
for (int i = 0; i <= m*2; ++i) {
cur2 = n - sa[i];
if (cur2-cur1 >= 1 && n-cur2 >= 1) break;
}
reverse(num, num+cur1);
reverse(num+cur1, num+cur2);
reverse(num+cur2, num+n);
for (int i = 0; i < n; ++i)
printf("%d\n", num[i]);
return 0;
}
D - Matrix
题意
有一个$n\times n$的01矩阵，有两种操作，一种是将一个矩形内的元素全部异或1，另一种是单点查询。要求实现这些操作。
思路
关于树状数组区间染色，有一篇论文可以看——《浅谈信息学竞赛中的“0”和“1”》。其中第一块就用到了这个例题。只要对区间边缘的点更新，就能记录区间染色的次数，然后区间求前缀和就能得到染色了多少次，得到答案。
很菜的是，有二重循环的bug调了一个小时才过。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+7;
int n, tree[maxn][maxn];
int lowbit(int x) {
return x&(-x);
}
void add(int x, int y) {
for (int i = x; i <= n; i += lowbit(i))
for (int j = y; j <= n; j += lowbit(j))
++tree[i][j];
}
int query(int x, int y) {
int rt = 0;
for (int i = x; i; i -= lowbit(i))
for (int j = y; j; j -= lowbit(j))
rt += tree[i][j];
return rt;
}
void solve() {
char ins[2]; int t;
scanf("%d%d", &n, &t);
memset(tree, 0, sizeof tree);
while (t--) {
scanf("%s", ins);
if (ins[0] == 'C') {
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
add(x1, y1); add(x1, y2+1);
add(x2+1, y1); add(x2+1, y2+1);
}
else {
int x, y; scanf("%d%d", &x, &y);
printf("%d\n", query(x, y)&1);
}
}
}
int main(){
#ifdef LOCAL
freopen("in.txt", "r", stdin);
#endif
int t; scanf("%d", &t);
while (t--) solve();
return 0;
}
E - PaintBall
题意
一张1000*1000的图上有n个圆形障碍物，求是否能从最左侧走到最右侧。
思路
对每个障碍物缩点，然后从上边界开始DFS遍历所有相邻的障碍物，如果遍历到的障碍物可以接触到下边界就无解。遇到与左边界相邻的障碍物就更新入口位置，出口为右边界。
代码
/**
* Author: wzhzzmzzy
* Question: UVa - 11853
* Algorithm: DFS
**/
#include <bits/stdc++.h>
using namespace std;
//#define LOCAL
const int maxn = 1<<10;
int n, flag, vis[maxn];
double ent, exi;
struct { double x, y, r; } node[maxn];
bool check(int u, int v) {
return hypot(node[u].x-node[v].x, node[u].y-node[v].y) < node[u].r+node[v].r;
}
int dfs(int s) {
if (!flag) return 0;
vis[s] = 1;
if (node[s].y - node[s].r <= 0)
return flag = 0;
for (int i = 0; i < n; ++i)
if (!vis[i] && check(s, i)) dfs(i);
if (node[s].x - node[s].r <= 0)
ent = min(ent, node[s].y - sqrt(node[s].r*node[s].r-node[s].x*node[s].x));
if (node[s].x + node[s].r >= 1000)
exi = min(exi, node[s].y - sqrt(node[s].r*node[s].r-(1000-node[s].x)*(1000-node[s].x)));
}
int main(){
#ifdef LOCAL
freopen("in.txt", "r", stdin);
#endif
while (~scanf("%d", &n)) {
memset(vis, 0, sizeof vis);
flag = 1, ent = exi = 1000;
for (int i = 0; i < n; ++i)
scanf("%lf%lf%lf", &node[i].x, &node[i].y, &node[i].r);
for (int i = 0; i < n; ++i)
if (!vis[i] && node[i].y+node[i].r >= 1000) dfs(i);
if (!flag) puts("IMPOSSIBLE");
else printf("0.00 %.2f 1000.00 %.2f\n", ent, exi);
}
return 0;
}
G - ztr loves lucky numbers
题意
找出一个最小的大于n的由相同数量的4和7组成的数字。
思路
先DFS打表，然后二分查找。
代码
/**
* Author: wzhzzmzzy
* Question: HDU - 5676
* Algorithm: 二分
**/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
//#define LOCAL
#define LL __int64
const int maxn = 1<<21;
LL n, num[maxn];
int cur;
void dfs(int u, int v, LL w) {
if (!u && !v) {
num[++cur] = w;
return;
}
if (u) dfs(u-1, v, w*10+4);
if (v) dfs(u, v-1, w*10+7);
}
void solve() {
scanf("%I64d", &n);
if (n > 777777777444444444) {
puts("44444444447777777777");
return;
}
int l = 1, r = cur;
LL ans;
while (l <= r) {
int mid = (l+r)>>1;
if (num[mid] >= n)
r = mid-1, ans = num[mid];
else l = mid+1;
}
printf("%I64d\n", ans);
}
void init() {
cur = 0;
for (int i = 2; i <= 18; i+=2)
dfs(i>>1, i>>1, 0);
sort(num+1, num+1+cur);
}
int main(){
#ifdef LOCAL
freopen("in.txt", "r", stdin);
#endif
init();
int t; scanf("%d", &t);
while (t--) solve();
return 0;
}
