我不太喜欢发题解。。但一般不保存hdu的代码，在加上惨痛的教训，所以还是发一个吧。还有很多题，后面补上。
1003
由于B数组是非严格的单调递增的。所以B数组的形式应该就是(
...，
...，
...，...，
...)。所以可以分成一段一段区间，而对于一段区间，其最小值是
（a为1的个数，b为0的个数）。这样，利用栈的性质，将要弹进去的与栈顶比较，不过比栈顶小就合并，在比较，最终得出所有答案。
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 | /************************************************************************* > File Name: 1003.cpp > Author: skt > Mail: sktsxy@gmail.com > Created Time: 2014年08月07日 星期四 17时16分16秒 ************************************************************************/ #include <cstdio> #include <cstring> #include <vector> #include <iostream> #include <map> #include <set> #include <utility> #include <string> #include <stack> using namespace std; #define LL long long #define eps 1e-8 #define MAXN 100005 #define pb push_back #define mp make_pair #define x first #define y second template <typename T> inline T Max(T a, T b) {return a>b?a:b;} template <typename T> inline T Min(T a, T b) {return a<b?a:b;} typedef pair <int, int> PII; typedef vector <int> vi; int T, n, a[MAXN], cnt; double ans; stack <PII> ss; vector <PII> pnt; vi vec; double calc(int a, int b) { return 1.0 * (double)a / (double)(0.0 + a + b); } double calc1(int a, int b) { return 1.0 * (double)a * (double)b / (double)(0.0 + a + b); } void work() { scanf("%d", &n); for (int i = 1; i <= n; i ++) { scanf("%d", &a[i]); } for (int i = 1; i <= n; i ++) { PII now = mp(a[i] == 1, a[i] == 0); while (!ss.empty()) { PII top = ss.top(); if (calc(top.x, top.y) < calc(now.x, now.y)) { break; } ss.pop(); now.x = now.x + top.x; now.y = now.y + top.y; } ss.push(now); } ans = 0; while (!ss.empty()) { PII top = ss.top(); ss.pop(); ans = ans + calc1(top.x, top.y); } printf("%.6lf\n", ans); } int main() { scanf("%d", &T); while (T --) { work(); } return 0; } |
1005
水题
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 | /************************************************************************* > File Name: 1005.cpp > Author: skt > Mail: sktsxy@gmail.com > Created Time: 2014年08月07日 星期四 12时00分26秒 ************************************************************************/ #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <map> #include <set> #include <utility> #include <queue> using namespace std; #define LL long long #define pb push_back #define mp make_pair #define eps 1e-8 #define MAXN 105 template <typename T> inline T Max(T a, T b) {return a>b?a:b;} template <typename T> inline T Min(T a, T b) {return a<b?a:b;} int T, n, m, a[MAXN][MAXN]; LL ans; LL get() { LL ans = 0; for (int i = 1; i <= n; i ++) { for (int j = 1; j <= m; j ++) { if (a[i][j]) { int cnt = 0; if (a[i][j-1] == 0) cnt ++; if (a[i-1][j] == 0) cnt ++; if (a[i+1][j] == 0) cnt ++; if (a[i][j+1] == 0) cnt ++; ans = ans + (1 << cnt); } } } return ans; } void work() { memset(a, -1, sizeof(a)); scanf("%d %d", &n, &m); for (int i = 1; i <= n; i ++) { int x = 0; if (i & 1) x = 1; for (int j = 1; j <= m; j ++) { a[i][j] = x; x ^= 1; } } ans = get(); for (int i = 1; i <= n; i ++) { int x = 1; if (i & 1) x = 0; for (int j = 1; j <= m; j ++) { a[i][j] = x; x ^= 1; } } ans = Max(ans, get()); cout << ans << endl; } int main() { scanf("%d", &T); while (T --) { work(); } return 0; } |
1007
Java大数，利用递推的方式，计算排列数
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 | import java.io.File; import java.io.FileInputStream; import java.io.PrintWriter; import java.math.BigInteger; import java.util.Scanner; /** * @author: skt E-mail:sktsxy@gmai.com * @Create：Aug 7, 2014 12:44:48 PM * @filename: Main.java */ public class Main { static int T, n; static int MAXN = 3005; static BigInteger ans; static BigInteger a[] = new BigInteger[MAXN]; static BigInteger c[] = new BigInteger[MAXN]; public static void work(Scanner in, PrintWriter out) { n = in.nextInt(); for (int i = 1; i <= n; i ++) { a[i] = in.nextBigInteger(); } for (int i = 0; i < n; i ++) { if (i == 0 || i == n - 1) c[i] = BigInteger.ONE; else { c[i] = c[i-1].multiply(BigInteger.valueOf(n - i)).divide(BigInteger.valueOf(i)); } } ans = BigInteger.ZERO; for (int i = 1; i <= n; i ++) { BigInteger one = BigInteger.ONE; if (i % 2 == 0) { one = one.multiply(BigInteger.valueOf(-1)); } ans = ans.add(a[n - i + 1].multiply(c[i-1]).multiply(one)); } out.println(ans); } public static void main(String[] args) throws Exception { Scanner in = new Scanner(System.in); PrintWriter out = new PrintWriter(System.out); T = in.nextInt(); while (T -- != 0) { work(in, out); } in.close(); out.close(); } } |
1010
斗地主的小模拟。注意一把出完牌的情况。
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 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 | /************************************************************************* > File Name: 1010.cpp > Author: skt > Mail: sktsxy@gmail.com > Created Time: 2014年08月07日 星期四 13时15分19秒 ************************************************************************/ #include <cstdio> #include <vector> #include <algorithm> #include <cstring> #include <iostream> #include <cmath> #include <map> #include <set> #include <utility> #include <string> using namespace std; #define LL long long #define pb push_back #define mp make_pair #define eps 1e-8 template <typename T> inline T Max(T a, T b) {return a>b?a:b;} template <typename T> inline T Min(T a, T b) {return a<b?a:b;} int T; string a, b; struct People { int num[20], flag, size; void init(string a) { size = a.length(); memset(num, 0, sizeof(num)); flag = 0; for (int i = 0; i < a.length(); i ++) { if (a[i] == 'X') { num[14] = 1; } else if (a[i] == 'Y') { num[15] = 1; } else if (a[i] == 'A') { num[12] ++; } else if (a[i] == 'K') { num[11] ++; } else if (a[i] == 'Q') { num[10] ++; } else if (a[i] == 'J') { num[9] ++; } else if (a[i] == 'T') { num[8] ++; } else { int x = a[i] - '0'; x = x - 2; if (x == 0) x += 13; num[x] ++; } } } int Solo() { for (int i = 15; i >= 1; i --) { if (num[i]) { if (size == 1) flag = 1; return i; } } return 0; } int Pair() { for (int i = 13; i >= 1; i --) { if (num[i] >= 2) { if (size == 2) flag = 1; return i; } } return 0; } int Trio() { for (int i = 13; i >= 1; i --) { if (num[i] >= 3) { if (size == 3) flag = 1; return i; } } return 0; } int Trio_Solo() { for (int i = 13; i >= 1; i --) { if (num[i] == 3 && size > 3) { if (size == 4) flag = 1; return i; } } return 0; } int Trio_Pair() { for (int i = 13; i >= 1; i --) { if (num[i] == 3) { for (int j = 1; j <= 13; j ++) { if (num[j] == 2) { if (size == 5) flag = 1; return i; } } } } return 0; } int four_dual() { for (int i = 13; i >= 1; i --) { if (num[i] == 4 && size >= 6) { if (size == 6) flag = 1; return i; } } return 0; } int Nuke() { if (num[14] && num[15]) { if (size == 2) flag = 1; return 1; } return 0; } int Bomb() { for (int i = 13; i >= 1; i --) { if (num[i] == 4) { if (size == 4) flag = 1; return i; } } return 0; } } p1, p2; void work() { cin >> a; cin >> b; p1.init(a), p2.init(b); if (p1.Solo() && p1.Solo() >= p2.Solo() && !p2.Nuke() && !p2.Bomb()) { printf("Yes\n"); return ; } if (p1.Pair() && p1.Pair() >= p2.Pair() && !p2.Nuke() && !p2.Bomb()) { printf("Yes\n"); return ; } if (p1.Trio() && p1.Trio() >= p2.Trio() && !p2.Nuke() && !p2.Bomb()) { printf("Yes\n"); return ; } if (p1.Trio_Solo() && p1.Trio_Solo() >= p2.Trio_Solo() && !p2.Nuke() && !p2.Bomb()) { printf("Yes\n"); return ; } if (p1.Trio_Pair() && p1.Trio_Pair() >= p2.Trio_Pair() && !p2.Nuke() && !p2.Bomb()) { printf("Yes\n"); return ; } if (p1.four_dual() && p1.four_dual() >= p2.four_dual() && !p2.Nuke() && !p2.Bomb()) { printf("Yes\n"); return ; } if (p1.Nuke()) { printf("Yes\n"); return ; } if (p1.Bomb() && p1.Bomb() >= p2.Bomb() && !p2.Nuke()) { printf("Yes\n"); return ; } if (p1.flag) { printf("Yes\n"); return ; } printf("No\n"); } int main() { scanf("%d", &T); while (T --) { work(); } return 0; } |