2013南京现场赛

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

A. hdu 4802 GPA

简单题,注意P,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
35
36
37
38
39
40
41
42
43
44
45
46
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <cstring>
#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 make_pair
#define CL(xx,yy) memset((xx),(yy),sizeof((xx)))

const char STR[11][5] = {"A","A-","B+","B","B-","C+","C","C-","D","D-","F"};
const double NUM[11] = {4.0,3.7,3.3,3.0,2.7,2.3,2.0,1.7,1.3,1.0,0.0};

int find(char str[]){
for(int i = 0; i < 11; i++)
if(!strcmp(str,STR[i]))
return i;
return -1;
}

int main(){
int n;
while(scanf("%d",&n)!=EOF){
double up = 0.0;
int down = 0;
for(int i = 0; i < n; i++){
int num; char str[10];
scanf("%d%s",&num,str);
if(!strcmp(str,"P") || !strcmp(str,"N")) continue;
int id = find(str);
down += num;
up += NUM[id] * num;
}
if(up == 0.0) puts("0.00");
else{
printf("%.2lf\n",up/down);
}
}
return 0;
}

J. hdu 4811 Ball

有红蓝黄3种颜色的球,个数不定,放入第一个球没分数,从第2个球开始,没放入一个球得到的分数是x1+x2,x1表示它左边的球的颜色种数,x2表示它右边的球的颜色种数(如果放在两端,同样成立,则x1或x2其中一个为0),问怎么放,最后得到的分数最多

因为只有3种颜色,所以最好的情况就是,左边有3色,右边有3色,然后不断地在中间放球,每次得到的分数就是6,所以想方法令左边3色右边3色

1
2
3
4
5
6
R
R Y
RB Y
RB RY
RBY RY
RBY BRY

这样放之后,两端都有3色了,剩下的球,全部放在中间即可,另外,这样放,已经得到的分数是15

可以看到RBY的个数都是2,但是如果RBY中个数可能少于2,就不一定这样放了,举一个例子

1
2
3
4
5
6
R = 2 , B = 2 , Y = 1
R
R Y
RB Y
RB BY
RB RBY

这样放是最优的

所以道理就很显然了,就是先让两边的颜色种类尽量多,然后往中间放球

我的代码是列举了所有情况

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
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <cstring>
#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 make_pair
#define CL(xx,yy) memset((xx),(yy),sizeof((xx)))

const char str[7] = "RYBRYB";

int main(){
int num[3],val[3];
while(scanf("%d%d%d",&num[0],&num[1],&num[2])!=EOF){
int fir = 0,sec = 0;
LL sum = 0LL;
LL ans = 0LL;
for(int i = 0; i < 3; i++)
if(num[i]){ fir++; num[i]--; }
for(int i = 0; i < 3; i++)
if(num[i]){ sec++; num[i]--; }
for(int i = 0; i < 3; i++)
sum += (LL)num[i];
if(fir == 3){
if(sec == 3){
ans += 15LL;
ans += sum * 6LL;
}
else if(sec == 2){
ans += 10LL;
ans += sum * 5LL;
}
else if(sec == 1){
ans += 6LL;
ans += sum * 4LL;
}
else{
ans += 3LL;
}
}
else if(fir == 2){
if(sec == 2){
ans += 6LL;
ans += sum * 4LL;
}
else if(sec == 1){
ans += 3LL;
ans += sum * 3LL;
}
else{
ans += 1LL;
}
}
else if(fir == 1){
if(sec == 1){
ans += 1LL;
ans += sum * 2LL;
}
else{
ans += 0LL;
}
}
else{
ans = 0LL;
}
cout << ans << endl;
}
return 0;
}

I.hdu 4810 Wall Painting

有n个数字,枚举K从1到n,对应输出n个数字,K代表的含义是,从n个数字中选K个,将他们异或得到一个数值,累加所有n选K的情况,最后输出
直接的思维是

枚举K从1到n

对于当前的K,枚举n选K个数的全部情况,对于每个得到的情况,将他们异或,然后累加输入输出

显然超时

既然异或是按位来做的,我们就可以按位来思考这个问题

对于那n个数,我们全部看做一个31位的二进制,从低位一直考虑到高位

对于第b位,n个数字只有0和1,假设有zero个0,one个1,zero + one = n

我们要选出K个数字,那么最后选出来的数字中,第b位,一定有n1个0,K-n1个1,对于这一位产生的结果,就是n1个0和K-n1个1异或的结果再乘上2^b。而对于这些0和1的异或,只需要看1的个数,1有奇数个则最后异或结果为1,1有偶数个则最后异或结果为0.

另外选n1个0,K-n1个1,本身就有很多可能,但可以用组合数算出来

C[zero][n1],C[one][K-n1],全部0中选n1个,全部1中选K-n1,两个C乘起来即可

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
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <cstring>
#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 make_pair
#define CL(xx,yy) memset((xx),(yy),sizeof((xx)))
#define N 1010
#define MOD 1000003LL
#define B 63

int CNT[B+10][2];
LL CC[N][N];

void work(int m,int *bit){
int id = 0;
while(m){
bit[id++] = m % 2;
m /= 2;
}
}

LL DO(int K,int bit){
int zero = CNT[bit][0] , one = CNT[bit][1];
LL ans = 0LL;
for(int __num = 1; __num <= one && __num <= K; __num += 2){
int num = K - __num;
if(num > zero) continue;
LL cnt = CC[zero][num];
LL __cnt = CC[one][__num];
LL res = (cnt * __cnt) % MOD;
ans = ( ans + (res*(1<<bit)%MOD) % MOD ) % MOD;
}
return ans;
}

LL solve(int K){
LL ans = 0LL;
for(int b = 0; b < B; b++){
ans = (ans + DO(K,b))%MOD;
}
return ans;
}

void INIT(){
CC[0][0] = CC[1][0] = CC[1][1] = 1LL;
for(int n = 2; n <= 1000; n++){
CC[n][0] = CC[n][n] = 1LL;
CC[n][1] = (LL)n;
for(int i = 2; i < n; i++){
CC[n][i] = (CC[n-1][i-1] + CC[n-1][i])%MOD;
}
}
}

int main(){
INIT();
int n;
LL a[N];
while(scanf("%d",&n)!=EOF){
CL(CNT,0);
for(int i = 0 ; i < n; i++){
int bit[B+10];
CL(bit,0);
scanf("%I64d",&a[i]);
work(a[i],bit);
for(int i = 0; i < B; i++){
//printf("%d",bit[i]);
if(bit[i]) CNT[i][1]++;
else CNT[i][0]++;
}
//puts("");
}
for(int K = 1; K <= n; K++){
LL ans = solve(K);
printf("%I64d",ans);
if(K != n) printf(" ");
else printf("\n");
}
}
return 0;
}

B.hdu 4803 Poor Warehouse Keeper

数量为x,总价为y,一开始x = y = 1

两种操作

  1. x++:这种操作是,y先变为 y = (y/x) * (x+1) , x再变为 x = x+1 (/是真正意义上的除法,y为浮点数)
  2. y++: 这种操作就是 y = y+1
  3. 两种操作,没做一次计数一次

给出目标值X,Y,最后x=X,y的整数部分=Y,未达到目标,最少操作次数

设总价sum,数量num,单价val = sum/num

  1. 可发现,x++操作是不改变单价的
  2. y++操作会提高单价
  3. 所以单价只会保持不变或越来越大,所以最后的Y/X >= 1 ,所以如果 Y < X , 无解输出-1
  4. 如果执行了x++,会使得以后单价的上升更加困难,例如

数量为1,总价2,单价是2,要让单价变为4,只需要总价变为4,执行了2次y++操作

数量为2,总价为4,单价也是2,要让单价变为4,需要让总价变为8,执行了4次y++操作

所以即使现在单价相同,由于数量num的不同,以后单价的增幅是不同的,num越大,单价上升就越难

一开始单价为 v = 1/1 = 1 , 最后单价至少为 V = Y/X (因为Y只是整数部分),其实这就是个不断提升单价的过程(单价只升不降)

为了从v尽快提升到V,我们应该多利用y++操作(只有y++操作才提升单价),但不可使用太多,因为一旦中途某一次单价超过了V,以后都不能再变小

所以这里面就有一个贪心的性质,和单调性的性质

要最快达到目标单价,就要尽量多使用y++操作

另外,如果使用了x++操作,提高了x的值,那么将来y++操作效果就没那么明显,所以应该尽早使用y++

另外注意到一点,x变为X,其实就是进行了X-x次x++操作,另外X很小,只有10,我们可以枚举

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
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define LL long long

int main(){
double sum;
int num,ANS;
LL X,Y;
while(scanf("%I64d%I64d",&X,&Y)!=EOF){
if(Y < X) { puts("-1"); continue; }
if(X == 1LL) { printf("%I64d\n",Y-1); continue; }
num = 1; sum = 1.0; ANS = 0;
for(int cnt = 1; cnt < X; cnt++){
int low = 0 , high = Y , ans = -1;
while(low <= high){
int mid = (low + high) >> 1;
LL res = (LL)((sum+mid) / num * X);
if(res <= Y){
ans = mid;
low = mid + 1;
}
else high = mid - 1;
}
if(ans > 0){
ANS += ans;
sum = sum + ans;
}
ANS++;
sum = (sum / num) * (num+1);
num++;
}
LL res = (LL)sum;
if(res < Y) ANS += (LL)(Y-res);
printf("%d\n",ANS);
}
return 0;
}