G-rated

What are you waiting for?

0%

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
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#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,这样是一定可以成功的,前半部分的构造就使用暴力即可

```cpp
#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;
}