codeforces 194 div.1

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

A:题意——·有1,3,9,27….的硬币,给出限制值n,要求医用硬币凑出总值要大于n,且最接近n(并且老板无法找回零钱给你),在这个基础上,使用的硬币越多越好,输出最多的硬币数。

贪心的思路,使用最小的硬币,这样就能使硬币数最多,所以全部使用1元硬币最多,但是可以发现,1元硬币是无法使用的

易证,假设使用了1个元硬币,1+x>n,则x>=n,若x=n,这不符合题意,因为老板可以把你给的那个1元找回去给你。x>n,那么x比1+x更靠近n,1元硬币是多余的,所以1元硬币其实根本不能用

那么就全部用3元硬币,则使用硬币数最多了,但受到1元硬币启发,不难发现3元硬币也有不能用的情况

当n = 3 * m,不能使用3元硬币,因为后面的硬币9,27,81其实都是3个倍数,用了一个等于用了多个3而已,如果其他面值凑起来的值已经大于n,那么没有用3的必要,如果不够n,又因为n是3的倍数,之前用的硬币都是3的倍数,所以如果用3个话,一定能准确筹够n,这也是不符合题意的

所以算法就明确了,从最小的3开始枚举,如果n被3整除,那3不能用,要用9,若还整除,则用27,直到不能被整除,就使用这个面值的硬币筹够n即可

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
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
#define LL long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define MAX 55

LL three[MAX];

int main(){
three[0] = 1LL;
for(int i = 1; i <= 50; i++) three[i] = 3LL * three[i-1];
LL n;
while(cin >> n){
for(int id = 1; id <= 50; id++)
if(n % three[id] != 0LL){
LL ans = n / three[id] + 1LL;
cout << ans << endl;
break;
}
}
return 0;
}

B:题意——n*m的格子棋盘,其中一些格子有陷阱,然后在棋盘的4条边上(但不包括4个角)放棋子,每次所有棋子都向其对面走1格。格子不能掉进陷阱,不能同时到达同一个格子,不能越过棋子,问满足这3个条件,最多能放多少棋子。这题目如果先考虑没有陷阱要怎么走,可以发现,从外到里一圈一圈的考虑的话,其实每一圈都是最多能放4个棋子的。现在有了陷阱,只是令到本来能走的一些棋子现在不能走了,只要对应地减掉即可

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
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
#define LL long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define N 1010

bool row[N],col[N];
int n,m;

int main(){
while(cin >> n >> m){
cl(row,true); cl(col,true);
while(m--){
int r,c;
cin >> r >> c;
row[r] = col[c] = false;
}
int ans = 0;
for(int i = 2; i <= n/2; i++){
int r1 = i , r2 = n-i+1;
int c1 = i , c2 = n-i+1;
if(row[r1]) ans++;
if(row[r2]) ans++;
if(col[c1]) ans++;
if(col[c2]) ans++;
}
if(n & 1){
int r = n/2+1 , c = n/2+1;
if(row[r] || col[c]) ans++;
}
cout << ans << endl;
}
return 0;
}

C:题意:给一个序列,8位数字,可以利用*,-,+,括号,合并,计算得到最终结果,合并就是指把几位合为一个数字。给定目标值k,方案数m,要求找到至多m种互异的方案,因为有合并操作,所以要构造出目标值变得容易很多。注意目标值k<=10000,我们可以把可用的8位数字分为前半和后半,用前半去构造得到一个数值res,保证res>=0,那么后半的4位数字,全部合并起来变为一个数字,值就是abs(k-res),当然要保证abs(k-res)<10000,这样是一定可以成功的,前半部分的构造就使用暴力即可

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
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <set>
#include <iterator>
using namespace std;
#define LL long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int tar,num;
set<int>ans;

inline void make_d(int *d,int val){
for(int i = 3; i >= 0; i--){
d[i] = val % 10;
val /= 10;
}
}

int cal(int *__d,int *__op){
//处理合并
int d[4],op[4];
for(int i = 0; i < 4; i++){
d[i] = __d[i]; op[i] = __op[i];
}
int cnt = 4,val = 0,id = 0;
for(int i = 0; i < cnt; i++){
val = val * 10 + d[i];
if(op[i] != 0){
d[id] = val; op[id++] = op[i]; val = 0;
}
}
if(id == 1) return d[0];
//处理乘法
cnt = id; id = 0; val = 1;
for(int i = 0; i < cnt; i++){
val *= d[i];
if(op[i] != 1){
d[id] = val; op[id++] = op[i]; val = 1;
}
}
if(id == 1) return d[0];
cnt = id; val = d[0];
for(int i = 1; i < cnt; i++){
if(op[i-1] == 2) val -= d[i];
else val += d[i];
}
return val;
}

void solve(){
int d[4],op[4];
for(int val = 0; val < 10000; val++){
make_d(d,val);
for(op[0] = 0; op[0] < 4; op[0]++)
for(op[1] = 0; op[1] < 4; op[1]++)
for(op[2] = 0; op[2] < 4; op[2]++){
op[3] = -1;
int res = cal(d,op);
if(res >= 0 && abs(res-tar) < 10000){
ans.insert(val*10000 + abs(res-tar));
if(ans.size() == num) return ;
}
}
}
}

int main(){
while(cin >> tar >> num){
ans.clear();
solve();
for(set<int>::iterator it = ans.begin(); it != ans.end(); it++){
printf("%08d\n",*it);
}
}
return 0;
}

D:给一个n*m的矩阵,选择一个子矩阵(长,宽至少都要2),取4个角的最小值作为这个这个子矩阵的值,选出一个子矩阵,使得值最大,就是最小值最大。

最小值最大,那就二分答案吧,把整个矩阵的值都取出来排序,然后二分枚举,每枚举一个key值就去检验。怎么检验?得到一个值,看它是否合法,其实只需要找到一个矩形,它的4个角的值都>=key,那么这个key就是合法。所以我们枚举矩形,枚举矩形的话,方法很多,虽然复杂度算起来是一样的,但是写法不同则会TLE

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
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
#define LL long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define N 1010
#define MAX 1000010
#define INF 0x3f3f3f3f

int a[N][N],num[MAX],n,m;
bool vis[N][N];
vector<int>List;

bool check(int key){
cl(vis,false);
for(int r1 = 0; r1 < n; r1++){
List.clear();
for(int c = 0; c < m; c++)
if(a[r1][c] >= key) List.pb(c);
for(int r2 = r1+1; r2 < n; r2++){
for(int i = 0; i < List.size(); i++){
int c = List[i];
if(a[r2][c] >= key){
if(vis[r1][r2]) return true;
vis[r1][r2] = true;
}
}
}
}
return false;
}

int main(){
while(scanf("%d%d",&n,&m)!=EOF){
int id = 0;
for(int i = 0 ; i < n; i++)
for(int j = 0 ; j < m; j++){
scanf("%d",&a[i][j]);
num[id++] = a[i][j];
}
sort(num,num+n*m);
int low = 0 , high = n*m-1 , ans = -1;
while(low <= high){
int mid = (low + high) >> 1;
int key = num[mid];
if(check(key)){
ans = key;
low = mid + 1;
}
else high = mid - 1;
}
printf("%d\n",ans);
}
return 0;
}

E:题意——给出n个点,作为圆的圆心,选出3个点,画3个圆大小相同,这些圆不能相交(可相切),问半径最长多少。即选3个点,画成一个三角形,最小那条边的一半就是圆心,现在就是要让这个最小边最大。

用贪心的方法,对两两点的连线长度进行降序排序,然后不断地添加边,只要一旦出现1个三角形就找到了答案,所以问题变为怎么判断出现了三角形。

当前添加了边u—v,如果u已经直接连接一个点t,v也直接连接一个点t,那么u,v,t形成三角形,所以要时刻维护每个点与哪些点直接相连。可以开辟一个二维矩阵来记录的,但是复杂度太高了,所以实现同样的功能,用biset辅助一下即可,对于每个点u,都对应一个bitset,用于记录与u直接相连的点

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
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <bitset>
using namespace std;
#define LL long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define N 3010
#define MAX 9000010

struct edge{
int u,v,w;
edge(){}
edge(int __u,int __v,int __w){
u = __u; v = __v; w = __w;
}
bool operator<(const edge temp)const{
return w > temp.w;
}
}e[MAX];
bitset<N>bs[N];
int n,x[N],y[N];

inline int dis(int i,int j){
return (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]);
}

int main(){
while(cin >> n){
for(int i = 0; i < n; i++)
cin >> x[i] >> y[i];
int id = 0;
for(int i = 0 ; i < n; i++)
for(int j = i+1; j < n; j++){
e[id++] = edge(i,j,dis(i,j));
}
sort(e,e+id);
for(int i = 0 ; i < n; i++)
bs[i].reset();
int ans;
for(int i = 0 ; i < id; i++){
int u = e[i].u , v = e[i].v , w = e[i].w;
bitset<N>temp;
temp = bs[u] & bs[v];
if(temp.any()){
ans = w; break;
}
bs[u].set(v);
bs[v].set(u);
}
printf("%.20lf\n",sqrt(1.*ans)/2);
}
return 0;
}