250.Dating

给你一个串,大写字母代表是男的,小写是女的,围成一个圈,然后循环报数,第K个出列,然后找一个最小的异性组成一对,输出最后所能组成的情况.

string dates(string circle, int k)

直接模拟就好了,看了大牛们的代码学到一个非常好用的函数,rotate,用法入下

int num[] = {0,1,2,3,4,5,6,7,8,9};
rotate(num+2,num+4,num+7);
FF(i,10) printf("%d ",num[i]);
输出结果为0 1 4 5 6 2 3 7 8 9
三个参数分别是起始位子,左旋到的位子,终止位子+1(a <= b <= c)
那么约瑟夫环也就是上题就应该这样旋转
rotate(circle.begin() , circle.begin()+circle.size()%K , circle.end());

500.JumpyNum

Jumpy Number定义:一个数各个相邻数位的差都不小于2.

举例:JUMPY:290464, 13131313, 97539753, 5;

NOT JUMPY: 28459, 28549, 1091919, 97753, 111111.

现在问你low到high之间有多少个Jumpy Number

int howMany(int low, int high)

有边界的DP,这让我想起了HDU2010.1.2月赛中AC大牛出的题目,那是我做的第一个边界DP,当时我用两个DP数组计算,写了挺久的,非常的麻烦.在研究大牛们的代码之后发现这类题目用dfs记忆化搜索非常的好写,可以用一个limit参数标志是不是边界.下边附AC大牛题目的AC代码

1000.AllWoundUp

题目大意就是：一个女孩按一定的轨迹走成一个回路，男孩(站在x轴上却不能在女孩的路径上)目不转睛的盯这女孩，问他最多能顺时针旋转几圈

int maxWind(vector <int> x, vector <int> y)

女孩路径和x轴相交会把x轴分成好几段，然后在每一段上任意找一个点做一个for循环统计转过的圈数，取最大值
以上是官方解法，我在想能不能把轨迹和x轴的交点分为向下(-1)和向上(+1)，然后按坐标排序，再做一次for循环，cnt加上每个交点的权值，求最大值，这样就变成只有排序nlogn的复杂度了，比官方的n^2好很多.不过轨迹和x轴重合的地方不好处理，继续YY中…

附HDU3271 AC代码

?View Code CPP
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

int num[99];
int dp[99][301][2];
int B;
 
int dfs(int n,int M,int limit) {
	if(M == 0)    return 1;
	if(n == -1)    return 0;
	int &ret = dp[n][M][limit];
	if(ret != -1)    return ret;
	ret = 0;
	int temp = min((limit ? num[n] : B - 1) , M);
	for(int i = 0 ; i <= temp; i ++) {
		ret += dfs(n-1,M-i,limit && i == num[n]);
	}
	return ret;
}
 
int func(int key,int M) {
	if(key == -1) {
		return 0;
	}
	int n = 0;
	while(key) {
		num[n++] = key%B;
		key /= B;
	}
	CC(dp,-1);
	return dfs(n-1,M,1);
}
 
int main() {
	int op;
	int cas = 1;
	while(scanf("%d",&op) == 1) {
		printf("Case %d:\n",cas++);
		int X,Y,M;
		scanf("%d%d%d%d",&X,&Y,&B,&M);
		if(X > Y) swap(X,Y);
		int big = func(Y,M);
		int small = func(X-1,M);
		if(op == 1) {
			printf("%d\n",big - small);
		} else {
			int K;
			scanf("%d",&K);
			if(big - small < K) {
				puts("Could not find the Number!");
				continue;
			}
			LL lo = X;
			LL hi = Y;
			while(lo <= hi) {
				LL mid = (lo + hi) >> 1;//AC大牛的神题,虽然lo和hi是int,但是相加会超int,=3=
				int key = func(mid,M);
				if(key - small >= K) {
					hi = mid - 1;
				} else {
					lo = mid + 1;
				}
			}
			printf("%lld\n",hi + 1);
		}
	}
	return 0;
}

Popularity: 6% [?]