2016-2017 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2016)
A Artwork
题目链接
题意：给你一个n*m的图，在这张图上选择(x1,y1)到(x2,y2)的矩形涂黑，问每一步之后剩下联通的白色块有多少个。
思路：并查集每个联通块，从后往前类撕封条的方法，将每个从黑变白的块与四周并查集，记录答案。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 5;
struct node {
int x1, x2, y1, y2;
}op[10005];
int g[maxn][maxn];
int fa[maxn*maxn];
int ans[10005];
int dir[2][2] = {
-1,0,
0,-1
};
int dir2[4][2] = {
-1, 0,
0, -1,
1, 0,
0, 1};
int n, m, p;
int ok(int x, int y) {
return x > 0 && y > 0 && x <= n && y <= m;
}
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
void mix(int x, int y) {
int fx = find(x);
int fy = find(y);
fa[fx] = fy;
}
void init() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int id = (i - 1) * m + j;
fa[id] = id;
}
}
}
int main() {
scanf("%d%d%d", &n, &m, &p);
init();
for (int i = 1; i <= p; i++) {
scanf("%d%d%d%d", &op[i].x1, &op[i].y1, &op[i].x2, &op[i].y2);
if (op[i].x1 == op[i].x2) {
for (int y = op[i].y1; y <= op[i].y2; y++) {
g[op[i].x1][y] ++;
}
}
else {
for (int x = op[i].x1; x <= op[i].x2; x++) {
g[x][op[i].y1] ++;
}
}
}
// cout << "yyy" << endl;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
for (int k = 0; k < 2; k++) {
int x = dir[k][0] + i;
int y = dir[k][1] + j;
if (ok(x, y) && !g[i][j] && !g[x][y]) {
mix(((x - 1)*m + y), (i - 1)*m + j);
}
}
}
}
set<int>st;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if(!g[i][j]){
int id = (i - 1) * m + j;
fa[id] = find(fa[id]);
st.insert(fa[id]);
// cout << i<<' '<<j << " *** " << fa[id] << endl;
}
}
}
ans[p] = st.size();
for (int i = p; i >1; i--) {
ans[i-1] = ans[i];
if (op[i].x1 == op[i].x2) {
for (int y = op[i].y1; y <= op[i].y2; y++) {
g[op[i].x1][y] --;
// cout <<"!!"<< op[i].x1 << ' ' << y << ' ' << g[op[i].x1][y] << endl;
if(!g[op[i].x1][y]){
int id = (op[i].x1 - 1) * m + y;
fa[id] = id;
ans[i-1]++;
for (int k = 0; k < 4;k++){
int tx=op[i].x1+dir2[k][0];
int ty = y + dir2[k][1];
if(ok(tx,ty)&&!g[tx][ty]){
if(find((tx - 1) * m + ty)!=find(id)){
mix((tx - 1) * m + ty, id);
ans[i-1]--;
}
}
}
}
}
}
else {
for (int x = op[i].x1; x <= op[i].x2; x++) {
g[x][op[i].y1] --;
// cout << "??" << x << ' ' << op[i].y1 << ' ' << g[x][op[i].y1] << endl;
if(!g[x][op[i].y1]){
int id = (x - 1) * m + op[i].y1;
fa[id] = id;
ans[i-1]++;
for (int k = 0; k < 4;k++){
int tx=x+dir2[k][0];
int ty = op[i].y1 + dir2[k][1];
// cout << tx << " " << ty <<" "<<g[tx][ty]<< endl;
if(ok(tx,ty)&&!g[tx][ty]){
if(find((tx - 1) * m + ty)!=find(id)){
mix((tx - 1) * m + ty, id);
ans[i-1]--;
}
}
}
}
}
}
// cout << ans[i - 1] << endl;
}
for (int i = 1;i<=p;i++)
printf("%d\n", ans[i]);
// system("pause");
return 0;
}
/*
4 6 5
2 2 2 6
1 3 4 3
2 5 3 5
4 6 4 6
1 6 4 6
*/ B Bless You Autocorrect!
题目链接
题意：给定若干个字符串，可以打出若干个字符+tab进行自动补全，给你一个字符串求如何打步数最小
思路：字典树建边+bfs，注意单向边和双向边不同
#include <bits/stdc++.h>
#define maxn 1000005
using namespace std;
int n,m;
char s[maxn];
int trie[maxn][30];
int tot=0;
int root;
vector <int>G[maxn];
int val[maxn];
int step[maxn];
int pre[maxn];
void insert(){
int len=strlen(s);
root=0;
for(int i=0;i<len;i++){
int id=s[i]-'a';
if(!trie[root][id])
trie[root][id]=++tot;
val[trie[root][id]]++;
G[root].push_back(trie[root][id]);
G[trie[root][id]].push_back(root);
pre[trie[root][id]]=root;
root=trie[root][id];
}
int lst=root;
for(int i=lst;i!=0;i=pre[i]){
if(i==lst)continue;
if(val[i]==1){
G[i].push_back(lst);
}else
break;
}
}
void find(){
int len=strlen(s);
root=0;
int ans=0;
for(int i=0;s[i];i++){
int x=s[i]-'a';
if(trie[root][x]==0)
break;
root=trie[root][x];
ans++;
}
if(!root)
printf("%d\n",len);
else
printf("%d\n",len-ans+step[root]);
}
void bfs(){
queue <int>q;
q.push(0);
step[0]=0;
while(!q.empty()){
int f=q.front();
q.pop();
for(int i=0;i<G[f].size();i++){
if(G[f][i]==f)continue;
if(!step[G[f][i]]){
step[G[f][i]]=step[f]+1;
q.push(G[f][i]);
}
}
}
}
void input(){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++){
scanf("%s",s);
insert();
}
bfs();
}
void solve(){
for(int i=0;i<m;i++){
scanf("%s",s);
find();
}
}
int main(){
input();
solve();
}
/*
5 5
austria
autocorrect
program
programming
computer
autocorrelation
*/ C Card Hand Sorting
题目链接
题意：52张扑克，现在给你n张牌，要求最后排序的方式是同一类花色在一块并且单调递增，求最小需要更改几张顺序。
思路：52张扑克同一花色连续且递增的方案可以枚举写出，对于给定的序列，和枚举出的结果进行求最长公共子序列。n-得到最大答案就是答案。
#include <bits/stdc++.h>
using namespace std;
char hs[4] = {'s', 'h', 'd', 'c'};
int hs1[4] = {0,1, 2, 3};
char val[13] = {'2', '3', '4', '5', '6', '7', '8', '9','T', 'J', 'Q', 'K', 'A'};
char str[55][3];
char cmpstr[4][13][5];
int n, dp[102][102];
void input(){
scanf("%d", &n);
for (int i = 1; i <= n;i++){
scanf("%s", str[i]);
}
// for (int i = 1; i <= n;i++){
// printf("%s ", str[i]);
// }
int maxx = -1;
do
{
int flag[4] = {0};
for (int i = 0; i < 16; i++)
{
for (int j = 0; j < 4; j++)
{
if ((i & (1 << j) )== 0)
flag[j] = 0;
else
flag[j] = 1;
}
int cnt = 0;
// for (int j = 0; j < 4;j++)
// printf("%d:%d\n", j, flag[j]);
for (int j = 0; j < 4;j++){
cnt = 0;
if(flag[j]==0){
for (int k = 0; k < 13;k++){
cmpstr[j][cnt][0] = val[k];
cmpstr[j][cnt][1] = hs[hs1[j]];
cmpstr[j][cnt][2] = '\0';
cnt++;
}
}else
{
for (int k = 12; k >=0;k--){
cmpstr[j][cnt][0] = val[k];
cmpstr[j][cnt][1] = hs[hs1[j]];
cmpstr[j][cnt][2] = '\0';
cnt++;
}
}
}
// for (int j = 0; j < 4;j++){
// for (int k = 0; k < cnt; k++)
// printf("%s", cmpstr[j][k]);
// }
// printf("\n");
for (int j = 0; j < 4;j++){
for (int l = 0; l< cnt;l++){
for (int k = 1; k <= n;k++){
// cout<<cmpstr[j][l]<<" "<<str[k]<<endl;
if(strcmp(cmpstr[j][l],str[k])==0)
dp[j * cnt + l + 1][k - 1 + 1] = dp[j * cnt + l][k - 1] + 1;
else
dp[j * cnt + l + 1][k - 1 + 1] = max(dp[j * cnt + l+1][k - 1], dp[j * cnt + l][k - 1+1]);
}
}
}
maxx = max(maxx, dp[4*cnt][n]);
}
} while (next_permutation(hs1, hs1 + 4));
printf("%d", n - maxx);
}
int main(){
input();
// solve();
}
/*
4
2h Th 8c Qh
*/ D Daydreaming Stockbroker
题目链接
题意：股票模拟，主人公有100元钱，给出n天里每天的股票价格，即x元1股，主人公同时持有股不得超过1e5，问主人公最终最多能持有多少钱。
思路：最低点买入最高点卖出
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<string>
#include<cmath>
#include<stack>
#include<functional>
#include<bitset>
#define ll long long
#define maxn 100002
const int mod = 1e9 + 7;
using namespace std;
int main(void){
ll num[402];
ll t, i, has = 0, price, money = 100;
scanf("%lld",&t);
for(i = 0;i < t;i++){
scanf("%lld",&num[i]);
}
for(i = 0;i < t - 1;i++){
if(num[i] < num[i + 1]){
if(has < 100000){
if(100000 * num[i] < money){
price = num[i];
has = 100000;
money -= num[i] * 100000;
}
else{
price = num[i];
has += money / num[i];
money %= num[i];
}
}
}
else{
money += has * num[i];
has = 0;
}
}
if(num[t - 1] >= price){
money += has * num[t - 1];
}
else{
money += has * t;
}
printf("%lld\n",money);
return 0;
} E Exponial
题目链接
题意：欧拉降幂
F Fleecing the Raffle
题目链接
题意：现在一个抽奖箱里面有n张写有n个人名字的卡片，需要从中抽取p张作为得奖主。现在你想在抽奖箱中加入k张写有你的名字的卡片，你需要确定一个k，使得抽到你且仅抽到你一次的概率最大。并输出该最大概率。
思路：概率化简计算
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<string>
#include<cmath>
#include<stack>
#include<functional>
#include<bitset>
#define ll long long
#define maxn 100002
const int mod = 1e9 + 7;
using namespace std;
int main(void){
double pre = 0;
int n, p, i, j;
scanf("%d %d",&n,&p);
for(i = 1;;i++){
double temp = 1.0 * i * p / (n - p + 1);
for(j = 0;j < p;j++){
temp = temp * (n - j) / (n - j + i);
}
if(temp > pre){
pre = temp;
}
else{
break;
}
}
printf("%.10f\n",pre);
return 0;
} G Game Rank
题目链接
题意：炉石的晋级规则，给出胜利和失败的次数求最后等级
思路：模拟
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<string>
#include<cmath>
#include<stack>
#include<functional>
#include<bitset>
#define ll long long
#define maxn 100002
const int mod = 1e9 + 7;
using namespace std;
char ch[10002];
int rk, star, win;
void add(int x){
star += x;
if(rk > 20){
if(star > 2){
star -= 2;
rk--;
}
}
else if(rk > 15){
if(star > 3){
star -= 3;
rk--;
}
}
else if(rk > 10){
if(star > 4){
star -= 4;
rk--;
}
}
else if(rk){
if(star > 5){
star -= 5;
rk--;
}
}
}
void sub(int x){
if(rk < 20&&rk||rk == 20&&star){
star--;
if(star < 0){
rk++;
if(rk <= 10){
star = 4;
}
else if(rk <= 15){
star = 3;
}
else{
star = 2;
}
}
}
}
int main(void){
int i, len;
scanf("%s",ch);
strlen(ch);
rk = 25;
star = win = 0;
len = strlen(ch);
for(i = 0;i < len;i++){
if(ch[i] == 'W'){
win++;
if(win >= 3&&rk >= 6){
add(2);
}
else{
add(1);
}
}
else{
win = 0;
sub(1);
}
}
if(rk){
printf("%d\n",rk);
}
else{
puts("Legend");
}
return 0;
} J Jumbled Compass
题目链接
题意：指南针 给出原度数和现度数，求旋转角度差
思路：水
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define maxn 1005
typedef long long ll;
using namespace std;
int n1, n2;
void input(){
scanf("%d%d", &n1, &n2);
int ans = n2 - n1;
if(ans<0)
ans+=360;
if(ans>180)
ans = ans - 360;
printf("%d\n", ans);
}
int main(){
input();
// solve();
// printf("\n");
// system("pause");
return 0;
}
京公网安备 11010502036488号