G-rated

What are you waiting for?

0%

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;
}