codeforces 206 div.1

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

A.题意:每个物品有一个价值w[i],如果用机器人左臂去拿最左边的物品,每个物品还要wl,如果用机器人右臂去拿则wr,如果用左臂连续拿了几个物品,那么从第2个物品开始每个物品要附加一个权值ql;如果连续 用右臂拿物品从第2个物品开始每个物品附加一个权qr;取完所有物品花费最小

一开始想到DP,后来想清楚了,主要是用左臂拿还是右臂拿的问题,无论怎么拿,假设最后拿走的物品是第m个物品,那么可知 ,1到m-1号物品一定都是左臂拿的,因为拿东西只能从端点拿,m号是最后拿走的,那么之前它一直存在,1到m-1号的物品是不可能通过右臂拿到的,同理,m+1到n号的物品一定是通过右臂拿到的,至于m号物品,最后只剩下它,可以左臂或者右臂拿,枚举一次即可。另外1到m-1号是左臂拿的,m+1号到n号是右臂拿的,具体怎么拿,那肯定是错开开,左边拿一个,右边拿一个,这样才能最大限度地避免因为连续拿物品而产生的附加花费,但即便是错开拿,有些情况下还是要连续拿物品的(因为左边和右边的物品数不一定相同) 做法就是枚举最后拿的物品m,m把线段分成左右两部分,左边一定是左臂拿,右边一定右臂拿,另外枚举m是哪个臂拿,再计算连续拿东西产生的花费

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

int n,w[N],wl,wr,ql,qr;
int lw[N],rw[N],sumlw[N],sumrw[N];
int main(){
while(scanf("%d%d%d%d%d",&n,&wl,&wr,&ql,&qr)!=EOF){
cl(sumlw,0); cl(sumrw,0);
for(int i = 1; i <= n; i++){
scanf("%d",&w[i]);
lw[i] = w[i] * wl;
rw[i] = w[i] * wr;
}
sumlw[1] = lw[1];
for(int i = 2; i <= n; i++)
sumlw[i] = sumlw[i-1] + lw[i];
sumrw[1] = rw[n];
for(int i = 2; i <= n; i++)
sumrw[i] = sumrw[i-1] + rw[n-i+1];

int ANS = INF;
for(int last = 1; last <= n; last++){
int lenl = last - 1;
int lenr = n - last;
int res[2];
if(lenl == lenr){
res[0] = sumlw[last] + sumrw[lenr];
res[1] = sumlw[lenl] + sumrw[lenr+1];
}
else if(lenl > lenr){
res[0] = sumlw[last] + sumrw[lenr] + ql * (last-lenr-1);
res[1] = sumlw[lenl] + sumrw[lenr+1] + ql * (last-lenr-2);
}
else{
res[0] = sumlw[last] + sumrw[lenr] + qr * (lenr-lenl-1);
res[1] = sumlw[lenl] + sumrw[lenr+1] + qr * (lenr-lenl);
}
ANS = min(ANS , min(res[0],res[1]));
}
printf("%d\n",ANS);
}
return 0;
}
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
INF = 2000000000
n , wl , wr , ql , qr = map(int , raw_input().split())
w = map(int , raw_input().split())
lw = range(n+10)
rw = range(n+10)
sumlw = range(n+10)
sumrw = range(n+10)
for i in range(1,n+1) :
lw[i] = w[i-1] * wl
rw[i] = w[i-1] * wr
sumlw[1] = lw[1]
for i in range(2,n+1) :
sumlw[i] = sumlw[i-1] + lw[i]
sumrw[1] = rw[n]
for i in range(2,n+1) :
sumrw[i] = sumrw[i-1] + rw[n-i+1]
ANS = INF
for last in range(1,n+1) :
lenl = last - 1
lenr = n - last
res = range(2)
if lenl == lenr :
res[0] = sumlw[last] + sumrw[lenr]
res[1] = sumlw[lenl] + sumrw[lenr+1]
elif lenl > lenr :
res[0] = sumlw[last] + sumrw[lenr] + ql * (last - lenr - 1)
res[1] = sumlw[lenl] + sumrw[lenr+1] + ql * (last - lenr - 2)
else :
res[0] = sumlw[last] + sumrw[lenr] + qr * (lenr - lenl - 1)
res[1] = sumlw[lenl] + sumrw[lenr+1] + qr * (lenr-lenl)
if res[0] < ANS :
ANS = res[0]
if res[1] < ANS :
ANS = res[1]
print ANS

C.题意:给出一个序列,给一个值k,序列的每个元素都可以减少k以内的数字,通过适当地调整,使得整个序列的gcd最大,输出最大点的gcd
每个数字能减少k以内的数字,转而想表达的意思是,假设有一个数字G,序列中每个元素都满足 ai % G <= k,那么这个G就是一个可行的gcd,因为每个ai都可以通过减少数值使得自己可以被G整除

找出序列中的最小值mina

若 mina <= k+1 , 那么D答案就是mina,因为G = mina <= k+1 , ai % G < G <= k+1,即 ai % G <= k

若 mina > k+1 , 一个显然的事实是,G <= mina,那么就暴力枚举答案,从 mina—>k+2 枚举答案,不过不能暴力检验(ai%G<=k),要利用性质

假设G是 一个可行的gcd,那么对于 所有ai都满足 ai % G <= k,换言之,ai一定落在数轴的 [G,G+k] , [2G,2G+k] , [3G,3G+k] …… [mG,mG+k]里面,那么我们只要统计一下这些区间里面一共有多少个ai,如果数目是n个,表示全部命中,G是可行解

上面一个小细节是m最多是多少,m = maxa / G

所以我们先统计区间[G,G+k],利用二分,看看序列中多少数字在里面

接着统计区间[2G,2G+k],二分

……..

[mG,mG+k],二分

代码中人肉写了两个二分查找,不过学会了两个STL,lower_bound,upper_bound,能达到两个二分查找的效果

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

int a[N],n,k;

inline bool solve(int G){
for(int i = 0; i < n; i++)
if(!(a[i] % G <= k))
return false;
return true;
}

int binary1(int key){
int low = 0 , high = n-1 , ans = -1;
while(low <= high){
int mid = (low+high) >> 1;
if(a[mid] < key) low = mid + 1;
else{
ans = mid; high = mid - 1;
}
}
return ans;
}
int binary2(int key){
int low = 0 , high = n-1 , ans = -1;
while(low <= high){
int mid = (low+high) >> 1;
if(a[mid] > key) high = mid - 1;
else{
ans = mid; low = mid + 1;
}
}
return ans;
}

int main(){
while(scanf("%d%d",&n,&k)!=EOF){
int mina = INF;
for(int i = 0; i < n; i++){
scanf("%d",&a[i]);
mina = min(mina,a[i]);
}
if(mina <= k+1){
printf("%d\n",mina);
continue;
}
sort(a,a+n);
int res = k+1;
for(int G = mina; G > k+1; G--){
int cnt = 0;
for(int m = 1; m <= a[n-1]/G; m++){
int indexl = binary1(m*G); // >= m*G 且下标最小
int indexr = binary2(m*G+k); // <= m*G+k 且下标最大
cnt += (indexr - indexl + 1);
}
if(cnt == n){
res = G; break;
}
}
printf("%d\n",res);
}
return 0;
}