首页 > 代码库 > 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;
}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。