codeforces 222 div.1

本文从WordPress迁移而来, 查看全部WordPress迁移文章

A.因为一开始保证是只有一个连通块的,我们dfs遍历整个连通块的时候会得到一个dfs树,逆回来想,如果按照dfs树访问的逆顺序,逐一删除节点的话,树是不会断裂的,同样的,原图也不会断裂,所以我们得到dfs的访问顺序,从后面开始删除num个节点(将这num个节点变为 X )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <utility>
#include <vector>
#include <stack>
using namespace std;
#define LL long long
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define N 510

const int dx[4] = {-1,0,1,0};
const int dy[4] = {0,1,0,-1};

char map[N][N];
bool vis[N][N];
int row,col,num,stx,sty;
stack<pii>sta;

void dfs(int x,int y){
sta.push(mp(x,y));
vis[x][y] = true;
for(int k = 0; k < 4; k++){
int xx = x + dx[k];
int yy = y + dy[k];
if(map[xx][yy] == '#' || vis[xx][yy]) continue;
dfs(xx,yy);
}
}

int main(){
while(cin >> row >> col >> num){
for(int i = 1; i <= row; i++)
cin >> map[i]+1;
for(int i = 0; i <= col+1; i++)
map[0][i] = map[row+1][i] = '#';
for(int i = 0; i <= row+1; i++)
map[i][0] = map[i][col+1] = '#';
stx = sty = 1;
for(int i = 1; i <= row; i++)
for(int j = 1; j <= col; j++)
if(map[i][j] == '.'){
stx = i; sty = j;
}
while(!sta.empty()) sta.pop();
cl(vis,false);
dfs(stx,sty);
for(int kth = 0; kth < num; kth++){
pii temp = sta.top();
sta.pop();
int x = temp.first , y = temp.second;
map[x][y] = 'X';
}
for(int i = 1; i <= row; i++){
for(int j = 1; j <= col; j++)
printf("%c",map[i][j]);
puts("");
}
}
return 0;
}

B.有个比较明显的贪心策略就是,要解决一个bug的话,应该找,能力超过bug的学生中,收费最便宜的那个
不过没有想清楚这个问题是具有二分性质的。问题首先是要保证天数最少,所以二分天数,二分出天数day后,最贪心的做法是,每个选中的学生都解决day个bug(最后一个学生可能不满day个bug但没关系)。为什么能二分?因为,当day越大的时候,你需要选的学生越少,总的花费越少,另外,当你要选的学生越少,其实你可以选择的余地更大,更可能选到,所以是可以二分的。
二分出day后,当然要解决最大的那个bug,找到能解决这个bug的学生,再选花费最小的,这个学生,其实他有能力解决所有的bug(最难的都解决了),那么最难的day个bug都由他解决,然后我们跳到day个后,这个bug就是当前最难的bug了,同样的,找到能解决它的花费最小的学生………..
成功的方案是,所有bug被解决(学生够用,钱够用)
这里有个问题,“找到能解决这个bug的学生,再选花费最小的”,我最初想的是,直接暴力来找,也不会超时,TLE之后才想通的确是可能达到10^10的。再想想这个寻找的过程,其实只需要扫一次的,我们用一个优先队列来维护,优先队列满足的条件是 “对于当前的bug,在队列中的每个学生都有能力解决它” , 那么当然是取出队列中花费最小的那个
整个代码比较长,主要想清楚 怎么二分 , 优先队列怎么插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <utility>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define LL long long
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define N 100010
#define INF 1000000100

int nb,ns,money;
struct student{
int id,b,c;
bool operator > (const student &temp)const{
return c > temp.c;
}
}stu[N];
struct BUG{
int id,a,s;
}bug[N];
priority_queue< student , vector<student> , greater<student> > pqueue;

bool cmp_bug_a(BUG x,BUG y){
return x.a < y.a;
}
bool cmp_bug_id(BUG x,BUG y){
return x.id < y.id;
}
bool cmp_stu_b(student x,student y){
return x.b < y.b;
}

bool work(int day){
int index = ns;
int mm = money;
vector<student>ans;
ans.clear();
while(!pqueue.empty()) pqueue.pop();
for(int ith = nb; ith >= 1; ith -= day){
int tar = bug[ith].a;
while(index && stu[index].b >= tar){ //先插入PQ
pqueue.push(stu[index]);
index--;
}
if(pqueue.empty()) return false; //队列已经为空,找不到学生解决问题
student temp = pqueue.top(); //再出队
pqueue.pop();
ans.push_back(temp);
if(temp.c > mm) return false; //不够钱
mm -= temp.c;
}
//更新一次答案
for(int ith = nb,index = 0; ith >= 1; ith -= day,index++){
int id = ans[index].id;
int ed = ith , st = max(1,ed-day+1);
for(int k = st; k <= ed; k++)
bug[k].s = id;
}
return true;
}

int solve(){
int low = 1 , high = nb , LEN = -1;
while(low <= high){
int mid = (low + high) >> 1;
if(work(mid)){
LEN = mid; high = mid - 1;
}
else low = mid + 1;
}
return LEN;
}

int main(){
while(cin >> ns >> nb >> money){
for(int i = 1; i <= nb; i++){
bug[i].id = i; bug[i].s = -1;
cin >> bug[i].a;
}
for(int i = 1; i <= ns; i++)
stu[i].id = i;
for(int i = 1; i <= ns; i++)
cin >> stu[i].b;
for(int i = 1; i <= ns; i++)
cin >> stu[i].c;
sort(bug+1,bug+nb+1,cmp_bug_a);
sort(stu+1,stu+ns+1,cmp_stu_b);

int ans = solve();
if(ans == -1){
puts("NO"); continue;
}
puts("YES");
sort(bug+1,bug+nb+1,cmp_bug_id);
for(int i = 1; i <= nb; i++)
printf("%d ",bug[i].s);
puts("");
}
return 0;
}