首页 > 代码库 > 2014多校联合六(HDU 4923 HDU 4925 HDU 4927 HDU 4930)

2014多校联合六(HDU 4923 HDU 4925 HDU 4927 HDU 4930)

HDU 4923 Room and Moor

题意:给出A序列  求满足题目所写的B序列  使得方差最小

思路:可以想到最后的结果中  B序列的值一定是一段一段的  那么我们可以类似贪心去搞  对于一段序列我们可以求出什么样的b值使得方差最小  即序列中1的个数除以序列长度  又因为B是单调的  可以用一个单调栈去模拟  复杂度远远小于n^2  不要被吓怕…

代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 100010

int t, n, top;
int a[N], f[2][N];
struct st {
    int head;
    double val;
} g[N];

int main() {
    int i, idx, num;
    double tmp1, ans;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            f[0][i] = f[0][i - 1];
            f[1][i] = f[1][i - 1];
            f[a[i]][i]++;
        }
        f[0][n + 1] = f[0][n];
        f[1][n + 1] = f[1][n];
        g[0].head = 1;
        g[0].val = -1;
        top = 0;
        for (i = 1; i <= n; i++) {
            idx = i;
            tmp1 = a[i];
            while (top >= 0 && g[top].val > tmp1) {
                idx = g[top].head;
                tmp1 = 1.0 * (f[1][i] - f[1][idx - 1]) / (i - idx + 1);
                top--;
            }
            top++;
            g[top].head = idx;
            g[top].val = tmp1;
        }
        ans = 0;
        g[top + 1].head = n + 1;
        for (i = 1; i <= top; i++) {
            tmp1 = g[i].val;
            num = f[0][g[i + 1].head - 1] - f[0][g[i].head - 1];
            ans += tmp1 * tmp1 * num;
            num = f[1][g[i + 1].head - 1] - f[1][g[i].head - 1];
            ans += (1.0 - tmp1) * (1.0 - tmp1) * num;
        }
        printf("%.6f\n", ans);
    }
    return 0;
}

HDU 4925 Apple Tree

题意:n*m的格子  要么种苹果  要么施化肥  施肥后的格子的相邻格子如果种了苹果  则苹果数翻倍  问最多产生几个苹果

思路:明显就是按矩形黑白染色的方法来种树和施肥  那么枚举两种情况  即是黑格子还是白格子种苹果  最后取max

代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int t, n, m;

int main() {
    int i, j, ans, res, k;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        res = ans = 0;
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= m; j++) {
                k = 1;
                if (i + 1 <= n)
                    k *= 2;
                if (i - 1 >= 1)
                    k *= 2;
                if (j + 1 <= m)
                    k *= 2;
                if (j - 1 >= 1)
                    k *= 2;
                if ((i + j) & 1)
                    ans += k;
                else
                    res += k;
            }
        }
        printf("%d\n", max(ans, res));
    }
    return 0;
}

HDU 4927 Series1

题意:一个序列A  每次根据这个方程ai=ai+1-ai使整个序列数字个数-1  问n-1次操作后剩下哪个数

思路:水题  只要把式子化简即可  注意高精度

代码:

import java.io.*;
import java.util.*;
import java.math.*;

public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int t, n, T, i, j;
        BigInteger[] a = new BigInteger[3010];
        BigInteger[] c = new BigInteger[3010];
        T = cin.nextInt();
        for (t = 1; t <= T; t++) {
            n = cin.nextInt();
            c[0] = BigInteger.ONE;
            for (i = 1; i <= n; i++)
                c[i] = c[i - 1].multiply(BigInteger.valueOf(n - i)).divide(
                        BigInteger.valueOf(i));
            for (i = 1; i <= n; i++)
                a[i] = cin.nextBigInteger();
            BigInteger ans;
            ans = BigInteger.ZERO;
            int sign = 1;
            for (j = n; j >= 1; j--) {
                if (sign == 1) {
                    ans = ans.add(a[j].multiply(c[n - j]));
                    sign = -1;
                } else {
                    ans = ans.subtract(a[j].multiply(c[n - j]));
                    sign = 1;
                }
            }
            System.out.println(ans);
        }
        cin.close();
    }
}

HDU 4930 Fighting the Landlords

题意:斗地主- -b  如果一下把手牌出光就算赢  或者  你出一次对手管不上就算赢  问能不能赢

思路:模拟题…  细心就好   逻辑如下

先看是否一次能出完  如果不能  判断大小王  在自己手里必胜在别人手里必输

如果还没有结果   判炸弹  如果还没结果  就分所有能出牌的可能判断

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int kind[10][5];
int cas, flag;
char str[20];
int p1[20], p2[20], vis[20], only[10][5];

int change(char x) {
	if (x == 'Y')
		return 17;
	else if (x == 'X')
		return 16;
	else if (x == '2')
		return 15;
	else if (x == 'A')
		return 14;
	else if (x == 'K')
		return 13;
	else if (x == 'Q')
		return 12;
	else if (x == 'J')
		return 11;
	else if (x == 'T')
		return 10;
	else
		return x - '0';
}

bool cmp(int a, int b) {
	return a > b;
}

int main() {
	int i, j, len1, len2;
	scanf("%d", &cas);
	getchar();
	while (cas--) {
		memset(kind, -1, sizeof(kind));
		memset(only, 0, sizeof(only));
		flag = 0;
		gets(str);
		len1 = strlen(str);
		for (i = 0; i < len1; i++) {
			p1[i] = change(str[i]);
		}
		gets(str);
		len2 = strlen(str);
		for (i = 0; i < len2; i++) {
			p2[i] = change(str[i]);
		}
		sort(p1, p1 + len1, cmp);
		sort(p2, p2 + len2, cmp);

		//7
		if (len1 >= 2 && p1[0] == 17 && p1[1] == 16) {
			kind[7][1] = 1;
			//    printf("1\n");
			printf("Yes\n");
			continue;
		}
		if (len2 >= 2 && p2[0] == 17 && p2[1] == 16) {
			kind[7][2] = 1;
			if (len2 == 2)
				only[7][2] = 1;
		}

		//8
		for (i = 3; i < len1; i++) {
			if (p1[i - 3] == p1[i - 2] && p1[i - 2] == p1[i - 1]
					&& p1[i - 1] == p1[i]) {
				kind[8][1] = p1[i];
				if (len1 == 4) {
					//    printf("2\n");
					printf("Yes\n");
					flag = 1;
				}
				break;
			}
		}
		if (flag)
			continue;
		for (i = 3; i < len2; i++) {
			if (p2[i - 3] == p2[i - 2] && p2[i - 2] == p2[i - 1]
					&& p2[i - 1] == p2[i]) {
				kind[8][2] = p2[i];
				if (len2 == 4)
					only[8][2] = 1;
				break;
			}
		}
		if ((kind[8][1] > kind[8][2]) && (kind[7][2] == -1)) {
			//    printf("3\n");
			printf("Yes\n");
			continue;
		}

		//1
		kind[1][1] = p1[0];
		kind[1][2] = p2[0];
		if (len1 == 1) {
			//    printf("4\n");
			printf("Yes\n");
			continue;
		}
		if (kind[1][1] != -1 && kind[1][1] >= kind[1][2]) {
			if ((kind[7][2] == -1) && (kind[8][2] == -1)) {
				//    printf("5\n");
				printf("Yes\n");
				continue;
			}
		}

		//2
		for (i = 1; i < len1; i++) {
			if (p1[i - 1] == p1[i]) {
				kind[2][1] = p1[i];
				if (len1 == 2)
					only[2][1] = 1;
				break;
			}
		}
		if (only[2][1]) {
			//printf("6\n");
			printf("Yes\n");
			continue;
		}
		for (i = 1; i < len2; i++) {
			if (p2[i - 1] == p2[i]) {
				kind[2][2] = p2[i];
				break;
			}
		}
		//printf("2....%d %d\n",kind[2][1],kind[2][2]);
		if (kind[2][1] != -1 && kind[2][1] >= kind[2][2]) {
			if ((kind[7][2] == -1) && (kind[8][2] == -1)) {
				//printf("7\n");
				printf("Yes\n");
				continue;
			}
		}

		//3
		for (i = 2; i < len1; i++) {
			if (p1[i - 1] == p1[i] && p1[i - 2] == p1[i - 1]) {
				kind[3][1] = p1[i];
				if (len1 == 3)
					only[3][1] = 1;
				break;
			}
		}
		if (only[3][1]) {
			//printf("8\n");
			printf("Yes\n");
			continue;
		}
		for (i = 2; i < len2; i++) {
			if (p2[i - 1] == p2[i] && p2[i - 2] == p2[i - 1]) {
				kind[3][2] = p2[i - 1];
				break;
			}
		}
		if (kind[3][1] != -1 && kind[3][1] >= kind[3][2]) {
			if ((kind[7][2] == -1) && (kind[8][2] == -1)) {
				//printf("9\n");
				printf("Yes\n");
				continue;
			}
		}
		//4
		for (i = 2; i < len1; i++) {
			if (p1[i - 1] == p1[i] && p1[i - 2] == p1[i - 1]) {
				if ((i + 1 < len1 && p1[i + 1] != p1[i])
						|| (i + 2 < len1 && p1[i + 2] != p1[i])
						|| (i - 3 >= 0 && p1[i - 3] != p1[i])
						|| (i - 4 >= 0 && p1[i - 4] != p1[i])) {
					kind[4][1] = p1[i];
					if (len1 == 4)
						only[4][1] = 1;
					break;
				}
			}
		}
		if (only[4][1]) {
			printf("Yes\n");
			continue;
		}
		for (i = 2; i < len2; i++) {
			if (p2[i - 1] == p2[i] && p2[i - 2] == p2[i - 1]) {
				if ((i + 1 < len2 && p2[i + 1] != p2[i])
						|| (i + 2 < len2 && p2[i + 2] != p2[i])
						|| (i - 3 >= 0 && p2[i - 3] != p2[i])
						|| (i - 4 >= 0 && p2[i - 4] != p2[i])) {
					kind[4][2] = p2[i];
					break;
				}
			}
		}
		if (kind[4][1] != -1 && kind[4][1] >= kind[4][2]) {
			if ((kind[7][2] == -1) && (kind[8][2] == -1)) {
				printf("Yes\n");
				continue;
			}
		}

		//5
		memset(vis, 0, sizeof(vis));
		for (i = 2; i < len1; i++) {
			if (p1[i - 1] == p1[i] && p1[i - 2] == p1[i - 1]) {
				vis[i - 2] = 1;
				vis[i - 1] = 1;
				vis[i] = 1;
				for (j = 1; j < len1; j++) {
					if ((!vis[j - 1]) && (!vis[j]) && p1[j] == p1[j - 1]) {
						kind[5][1] = p1[i];
						if (len1 == 5)
							only[5][1] = 1;
						break;
					}
				}
				vis[i - 2] = 0;
				vis[i - 1] = 0;
				vis[i] = 0;
				if (kind[5][1] != -1)
					break;
			}
		}
		if (only[5][1]) {
			printf("Yes\n");
			continue;
		}
		memset(vis, 0, sizeof(vis));
		for (i = 2; i < len2; i++) {
			if (p2[i - 1] == p2[i] && p2[i - 2] == p2[i - 1]) {
				vis[i - 2] = 1;
				vis[i - 1] = 1;
				vis[i] = 1;
				for (j = 1; j < len2; j++) {
					if ((!vis[j - 1]) && (!vis[j]) && p2[j] == p2[j - 1]) {
						kind[5][2] = p2[i];
						break;
					}
				}
				vis[i - 2] = 0;
				vis[i - 1] = 0;
				vis[i] = 0;
				if (kind[5][2] != -1)
					break;
			}
		}
		if (kind[5][1] != -1 && kind[5][1] >= kind[5][2]) {
			if ((kind[7][2] == -1) && (kind[8][2] == -1)) {
				printf("Yes\n");
				continue;
			}
		}
		//6
		for (i = 3; i < len1; i++) {
			if (p1[i - 3] == p1[i - 2] && p1[i - 2] == p1[i - 1]
					&& p1[i - 1] == p1[i]) {
				if (len1 >= 6) {
					kind[6][1] = p1[i];
					if (len1 == 6)
						only[6][1] = 1;
					break;
				}
			}
		}
		if (only[6][1]) {
			printf("Yes\n");
			continue;
		}
		for (i = 3; i < len2; i++) {
			if (p2[i - 3] == p2[i - 2] && p2[i - 2] == p2[i - 1]
					&& p2[i - 1] == p2[i]) {
				if (len2 >= 6) {
					kind[6][2] = p2[i];
					break;
				}
			}
		}
		if (kind[6][1] != -1 && kind[6][1] >= kind[6][2]) {
			if ((kind[7][2] == -1) && (kind[8][2] == -1)) {
				printf("Yes\n");
				continue;
			}
		}
		printf("No\n");
	}

	return 0;
}