排位賽 13 題解
題型
- A - 貪心 √
- B - 后綴數(shù)組 √
- C - 環(huán)形DP
- D - 二維樹狀數(shù)組/二維線段樹 √
- E - DFS找連通塊 √
- F - 快速傅里葉變換（FFT）
- G - DFS/二分 √
- H - 最小比率生成樹/二分/迭代
A - domino
題意
給出放骨牌位置之間的距離遮怜，和可以推骨牌的次數(shù)，求最少的骨牌高度和嚎幸。
思路
貪心才顿。統(tǒng)計(jì)只推一次所需要的骨牌高度惹想，然后排序，減去最高高度即可。
代碼
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
//#define LOCAL
#define LL __int64 // 1e5*1e5會(huì)爆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
題意
給出一個(gè)數(shù)字串裤翩，將其分為三段拳亿，每段都翻轉(zhuǎn)過來晴股，求可以得到的字典序最小的串。
思路
后綴數(shù)組》慰現(xiàn)學(xué)現(xiàn)賣系列电湘。本來用貪心法，結(jié)果發(fā)現(xiàn)不能過鹅经，翻了大白書才發(fā)現(xiàn)是后綴數(shù)組寂呛。先將整個(gè)數(shù)列翻轉(zhuǎn)過來求SA，然后找到第一個(gè)位置不在最后兩個(gè)的后綴瘾晃，作為一個(gè)的指針位置贷痪。然后求第二個(gè)指針位置。這里要注意一點(diǎn)酗捌，要將后面的串復(fù)制一遍然后求后綴數(shù)組呢诬。
代碼
\\用的不是正統(tǒng)倍增法，而是用sort簡(jiǎn)化了
#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
題意
有一個(gè)$n\times n$的01矩陣胖缤，有兩種操作尚镰，一種是將一個(gè)矩形內(nèi)的元素全部異或1，另一種是單點(diǎn)查詢哪廓。要求實(shí)現(xiàn)這些操作狗唉。
思路
關(guān)于樹狀數(shù)組區(qū)間染色，有一篇論文可以看——《淺談信息學(xué)競(jìng)賽中的“0”和“1”》涡真。其中第一塊就用到了這個(gè)例題分俯。只要對(duì)區(qū)間邊緣的點(diǎn)更新，就能記錄區(qū)間染色的次數(shù)哆料，然后區(qū)間求前綴和就能得到染色了多少次缸剪，得到答案。
很菜的是东亦，有二重循環(huán)的bug調(diào)了一個(gè)小時(shí)才過杏节。
代碼
#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個(gè)圓形障礙物，求是否能從最左側(cè)走到最右側(cè)。
思路
對(duì)每個(gè)障礙物縮點(diǎ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
題意
找出一個(gè)最小的大于n的由相同數(shù)量的4和7組成的數(shù)字。
思路
先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;
}
