A - Artwork
Gym - 101550A
題意：給一個(gè)n*m的格子，進(jìn)行q(1 ≤ q ≤ 1e4)次涂色（涂成黑色）禽拔，每次涂完詢問有幾個(gè)白色聯(lián)通塊睹栖。
ProblemA
思路：用并查集模擬野来，每一次涂色，把被涂色的部分標(biāo)記為-1豁辉，查這一部分周圍一圈的位置開始搜舀患，ans -= number.size()，搜出來一個(gè)新的就ans++餐抢。隊(duì)友寫的代碼wrong answer on test 5弹澎，但不知道為什么ˊ_>ˋ 我們出了很多測試數(shù)據(jù)都能過…（后來各種手動(dòng)加棧發(fā)現(xiàn)其實(shí)是爆棧了emm，加棧之后這樣就超時(shí)了emm）
正確的思路應(yīng)該是 離線并查集 殴胧。先全部讀入佩迟，處理好最后一張圖的結(jié)果报强，然后一步一步刪操作還原做的。
AC代碼：
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
const int maxn = 1e6+5;
const int maxn_v = 1e3+5;
const int maxn_q = 1e4+5;
int n, m, q;
int f[maxn];
bool vis[maxn_v][maxn_v];
int g[maxn];
int ans[maxn_q];
int turn[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int sum;
struct node {
int x1, y1, x2, y2;
}nd[maxn_q];
void init_() {
memset(vis, 0, sizeof vis);
for(int i = 1; i <= n*m; ++i)
f[i] = I;
}
int find_(int x) {
if(f[x] != x)
f[x] = find_(f[x]);
return f[x];
}
void union_(int x, int y) {
int xx = find_(x), yy = find_(y);
if( xx != yy ) {
f[xx] = yy;
--sum;
return;
}
return;
}
void dfs(int x, int y, int id) {
vis[x][y] = true;
f[x*m+y+1] = id;
for(int i = 0; i < 4; ++i) {
int xx = x + turn[i][0], yy = y + turn[i][1];
if(xx >= 0 && xx < n && yy >= 0 && yy < m && !vis[xx][yy] && !g[xx*m+yy+1]) {
dfs(xx, yy, id);
}
}
return;
}
void check() {
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
printf("%3d", f[i*m+j+1]);
}
printf("\n");
}
}
int main()
{
scanf("%d%d%d", &m, &n, &q);
init_();
int x1, y1, x2, y2;
for(int q_ = 0; q_ < q; ++q_) {
scanf("%d%d%d%d", &y1, &x1, &y2, &x2);
x1--, y1--, x2--, y2--;
if(y1 == y2) {
if(x1 > x2) swap(x1, x2);
for(int i = x1; i <= x2; ++i) {
++g[i*m+y1+1];
//f[i*m+y1+1] = -1;
}
}
else if(x1 == x2) {
if(y1 > y2) swap(y1, y2);
for(int j = y1; j <= y2; ++j) {
++g[x1*m+j+1];
//f[x1*m+j+1] = -1;
}
}
nd[q_].x1 = x1, nd[q_].y1 = y1, nd[q_].x2 = x2, nd[q_].y2 = y2;
}
sum = 0;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
if(!g[i*m+j+1] && !vis[i][j]) {
dfs(i, j, i*m+j+1);
++sum;
}
}
}
//cout << sum << endl;
//check();
int xx, yy;
for(int q_ = q - 1; q_ >= 0; --q_) {
ans[q_] = sum;
x1 = nd[q_].x1, y1 = nd[q_].y1, x2 = nd[q_].x2, y2 = nd[q_].y2;
if(y1 == y2) {
for(int i = x1; i <= x2; ++i) {
--g[i*m+y1+1];
if(!g[i*m+y1+1]) {
++sum;
for(int k = 0; k < 4; ++k) {
xx = i + turn[k][0], yy = y1 + turn[k][1];
if(xx >= 0 && xx < n && yy >= 0 && yy < m && !g[xx*m+yy+1]) {
union_(xx*m+yy+1, i*m+y1+1);
}
}
}
}
}
else if(x1 == x2) {
for(int j = y1; j <= y2; ++j) {
--g[x1*m+j+1];
if(!g[x1*m+j+1]) {
++sum;
for(int k = 0; k < 4; ++k) {
xx = x1 + turn[k][0], yy = j + turn[k][1];
if(xx >= 0 && xx < n && yy >= 0 && yy < m && !g[xx*m+yy+1]) {
union_(xx*m+yy+1, x1*m+j+1);
}
}
}
}
}
}
for(int q_ = 0; q_ < q; ++q_)
printf("%d\n", ans[q_]);
return 0;
}
B - Bless You Autocorrect!
Gym - 101550B
題意：打字預(yù)選詞系統(tǒng)召嘶，現(xiàn)在詞庫里有n個(gè)詞，問打出一個(gè)單詞的最少操作次數(shù)甲喝。
SampleInput1
如樣例1：
autocorrelation - 按下 a + u + t + tab 出現(xiàn) "autocorrect", 按2次退格鍵埠胖，輸入l + a + t + I + o + n 共12次
ProblemB
思路：字典樹+BFS
建字典樹：相臨節(jié)點(diǎn)建雙向邊（可以退格）淳玩。分支上第一次出現(xiàn)的字母可以與單詞末尾建單向邊（可以通過按tab直接輸出完整單詞）
BFS跑最短路凯肋，query()直接查詢
建圖
AC代碼：
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 1e6+5;
const int maxsize = 26;
int n, m;
char str[maxn];
struct Trie {
int tot;
int tree[maxn][maxsize], d[maxn];
queue<int> que;
vector<int> g[maxn];
void init_() {
tot = 1;
memset(d, -1, sizeof d);
}
void insert_(char *s) {
vector<int> vec;
int u = 0, v;
int len = strlen(s);
for(int i = 0; i < len; ++i) {
v = s[i] - 'a';
if(!tree[u][v]) {
memset(tree[tot], 0, sizeof tree[tot]);
g[u].push_back(tot);
g[tot].push_back(u); //相臨兩個(gè)節(jié)點(diǎn)之間建雙向邊
if(i != len-1)
vec.push_back(tot); //存下該節(jié)點(diǎn)侮东，用于之后建單向邊
tree[u][v] = tot++;
}
u = tree[u][v];
}
for(int i = 0; i < (int)vec.size(); ++i) {
g[vec[i]].push_back(u);
}
vec.clear();
}
int Query(char *s) {
int len = strlen(s);
int ans = len;
int u = 0, v;
for(int i = 0; i < len; ++i) {
v = s[i] - 'a';
if(!tree[u][v])
break;
u = tree[u][v];
ans = min(ans, d[u] + len - i - 1);
}
//cout << ans << endl;
return ans = min(ans, len);
}
void BFS() {
que.push(0);
d[0] = 0;
int u, v;
while(!que.empty()) {
u = que.front();
que.pop();
for(int i = 0; i < (int)g[u].size(); ++i) {
v = g[u][I];
if(d[v] == -1) {
d[v] = d[u] + 1;
que.push(v);
}
}
}
}
}trie;
int main() {
scanf("%d%d", &n, &m);
trie.init_();
for(int i = 0; i < n; ++i) {
scanf("%s", str);
trie.insert_(str);
}
trie.BFS();
for(int i = 0; i < m; ++i) {
scanf("%s", str);
printf("%d\n", trie.Query(str));
}
return 0;
}
/*
5 5
austria
autocorrect
program
programming
computer
autocorrelation
programming
competition
zyx
austria
*/
C - Card Hand Sorting
題意：給n(1≤n≤52)張牌悄雅，包含花色(s, h, d, c)和數(shù)字(2,3,4,5,6,7,8,9,T,J,Q,K,A)铁蹈，你可以將其中的一張牌抽出，放到另一個(gè)位置容诬。要求把牌排序览徒，首先按花色分開，其次每個(gè)花色內(nèi)部數(shù)字要么升序要么降序纽什，問最少要操作多少次躲叼。
思路：模擬+最長上升子序列
D - Daydreaming Stockbroker
Gym - 101550D
題意：股票模擬，主人公有100元錢让蕾，給出n天里每天的股票價(jià)格或听，即x元1股神帅，主人公同時(shí)持有股不得超過1e5，問主人公最終最多能持有多少錢找御。
思路：水題霎桅，在最低點(diǎn)買入最高點(diǎn)賣出即可，注意邊界的判斷遇革，例如極大值要大于前一點(diǎn)揭糕，大于等于后一點(diǎn)。
AC代碼：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <map>
using namespace std;
typedef long long ll;
const int maxn = 400;
ll a[maxn];
int main(){
int d;
ll money = 100;
ll gu = 0;
scanf("%d", &d);
for(int i = 0; i < d; ++i) {
scanf("%lld", &a[I]);
}
for(int i = 0; i < d; ++i) {
if( (i==0 && a[i] < a[i+1]) || (i != d-1 && (a[i] <= a[i-1] && a[i] < a[i+1])) ) {
if(a[i] > money)
continue;
gu = money / a[I];
if(gu > 100000) {
money -= a[i] * 100000;
gu = 100000;
}
else {
money -= a[i] * gu;
}
}
else if(i != 0 && (a[i] > a[i-1] && a[i] >= a[i+1])) {
money += gu * a[I];
}
}
printf("%lld\n", money);
return 0;
}
E - Exponial
F - Fleecing the Raffle
題意：現(xiàn)在一個(gè)抽獎(jiǎng)箱里面有n張寫有n個(gè)人名字的卡片，需要從中抽取p張作為得獎(jiǎng)主±艨冢現(xiàn)在你想在抽獎(jiǎng)箱中加入k張寫有你的名字的卡片，你需要確定一個(gè)k昂勒，使得抽到你且僅抽到你一次的概率最大戈盈。并輸出該最大概率。
思路：概率計(jì)算：
化簡
概率P(k) 應(yīng)該是有一個(gè)峰值的涣觉，那么看
令 得
即
代碼求解即可
AC代碼：
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
int n, p, k;
long double getjc(){
long double ans = 1;
for(int i = n, j = n + k; i >= n-p+2 && j >= n+k-p+1; i--, j--) {
ans *= (long double)I;
ans /= (long double)j;
}
ans /= (long double)(n+k-p+1);
return ans;
}
int main() {
scanf("%d%d", &n, &p);
k = (p - n - 1) / (1 - p);
k += 1;
long double ans = (long double)k * (long double)p * getjc();
printf("%.10Lf\n", ans);
return 0;
}
G - Game Rank
題意：爐石傳說天梯賽模擬官册，隊(duì)友A的膝宁。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
using namespace std;
string str;
int ran, star;
int num[50];
void init() {
for(int i = 1; i <= 10; ++i)
num[i] = 5;
for(int i = 11; i <= 15; ++i)
num[i] = 4;
for(int i = 16; i <= 20; ++i)
num[i] = 3;
for(int i = 21; i <= 25; ++i)
num[i] = 2;
ran = 25;
star = 0;
}
void solve() {
int n = 0;
for(int i = 0; i < str.length(); ++i) {
if(str[i] == 'W' || str[i] == 'w') {
++n;
if(n >= 3 && ran > 5)
star += 2;
else
++star;
if(star > num[ran]) {
star = star - num[ran];
--ran;
if(ran < 1)
return ;
}
}
else if(str[i] == 'L' || str[i] == 'l') {
n = 0;
if(ran < 21) {
--star;
if(star < 0) {
if(ran < 20) {
++ran;
star = num[ran] - 1;
}
else
star = 0;
}
}
}
//cout << ran << ' ' << star << endl;
}
}
int main()
{
getline(cin, str);
init();
solve();
if(ran)
cout << ran << endl;
else
cout << "Legend" << endl;
return 0;
}
H - Highest Tower
I - Interception
J - Jumbled Compass
Gym - 101550J
題意：一個(gè)指南針员淫，從a到b最少可以轉(zhuǎn)多少度
思路：注意180度的時(shí)候應(yīng)該輸出正180击敌，不要輸出-180
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
int a, b;
scanf("%d%d", &a, &b);
int ans = 360 - a + b;
int ans2 = b - a;
int ans3 = 360 + a - b;
if( abs(ans2) < 180 ) {
printf("%d\n", ans2);
}
else{
if(abs(ans) > abs(ans3) ){
if(ans3 == 180) {
printf("%d\n", ans3);
}
else
printf("-%d\n", ans3);
}
else
printf("%d\n", ans);
}
return 0;
}
