A - Artwork
Gym - 101550A
题意：给一个n*m的格子，进行q(1 ≤ q ≤ 1e4)次涂色（涂成黑色），每次涂完询问有几个白色联通块。
ProblemA
思路：用并查集模拟，每一次涂色，把被涂色的部分标记为-1，查这一部分周围一圈的位置开始搜，ans -= number.size()，搜出来一个新的就ans++。队友写的代码wrong answer on test 5，但不知道为什么ˊ_>ˋ 我们出了很多测试数据都能过…（后来各种手动加栈发现其实是爆栈了emm，加栈之后这样就超时了emm）
正确的思路应该是 离线并查集 。先全部读入，处理好最后一张图的结果，然后一步一步删操作还原做的。
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
题意：打字预选词系统，现在词库里有n个词，问打出一个单词的最少操作次数。
SampleInput1
如样例1：
autocorrelation - 按下 a + u + t + tab 出现 "autocorrect", 按2次退格键，输入l + a + t + I + o + n 共12次
ProblemB
思路：字典树+BFS
建字典树：相临节点建双向边（可以退格）。分支上第一次出现的字母可以与单词末尾建单向边（可以通过按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); //相临两个节点之间建双向边
if(i != len-1)
vec.push_back(tot); //存下该节点，用于之后建单向边
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)和数字(2,3,4,5,6,7,8,9,T,J,Q,K,A)，你可以将其中的一张牌抽出，放到另一个位置。要求把牌排序，首先按花色分开，其次每个花色内部数字要么升序要么降序，问最少要操作多少次。
思路：模拟+最长上升子序列
D - Daydreaming Stockbroker
Gym - 101550D
题意：股票模拟，主人公有100元钱，给出n天里每天的股票价格，即x元1股，主人公同时持有股不得超过1e5，问主人公最终最多能持有多少钱。
思路：水题，在最低点买入最高点卖出即可，注意边界的判断，例如极大值要大于前一点，大于等于后一点。
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
题意：现在一个抽奖箱里面有n张写有n个人名字的卡片，需要从中抽取p张作为得奖主。现在你想在抽奖箱中加入k张写有你的名字的卡片，你需要确定一个k，使得抽到你且仅抽到你一次的概率最大。并输出该最大概率。
思路：概率计算：
化简
概率P(k) 应该是有一个峰值的，那么看
令 得
即
代码求解即可
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
题意：炉石传说天梯赛模拟，队友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
题意：一个指南针，从a到b最少可以转多少度
思路：注意180度的时候应该输出正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;
}
