problem1 link

如果decisions的大小為0，那么每一輪都是$N$個(gè)人。答案為0.

否則，如果答案不為0，那么概率最大的一定是一開始票數(shù)最多的人。因?yàn)檫@個(gè)人每一輪都在可以留下來的人群中。

假設(shè)第一輪之后剩下$r_{1}$個(gè)人，那么第二輪之后將剩下$r_{2}=N$%$r_{1}$個(gè)人。不妨設(shè)$r_{1}<N$。第一輪能夠使得$r_{1}$個(gè)人的票數(shù)答案一樣多且最多（設(shè)這個(gè)票數(shù)為$x$），那么這個(gè)x一定是大于等于單純由decisions決定出的最大值。而現(xiàn)在$r_{1}<N$了，所以必然現(xiàn)在能投出的最大值還是大于等于第一輪的最大值。最后結(jié)果是：一些人的票數(shù)是$N/r_{1}$，另外一些是$N/r_{1}+1$，那么后一部分人將留下來到下一輪。

同理第$k$輪之后剩下$r_{k}=N$%$r_{k-1}$個(gè)人，直到剩下一個(gè)人。當(dāng)出現(xiàn)$N$%$r_{i}=0$時(shí)，說明出現(xiàn)循環(huán)，答案為0。

有解的話，答案為$\frac{r_{2}}{r_{1}}*\frac{r_{3}}{r_{2}}*...*\frac{r_{k}}{r_{k-1}}=\frac{r_{k}}{r_{1}}=\frac{1}{r_{1}}$

problem2 link

首先，最后的圖形的結(jié)果不會(huì)超出(-27,0)到(27,81)這個(gè)范圍。

由于給出的范圍都是整數(shù)，那么每次用給出的區(qū)間$R$與當(dāng)前圖形能擴(kuò)展出的最大區(qū)間$R_{i}$比較，如果$R$能包含$R_{i}$，那么直接計(jì)算即可。否則可將當(dāng)前線段繼續(xù)增長，出現(xiàn)三個(gè)小區(qū)間，繼續(xù)匹配即可。可以看出，最后最小的區(qū)間的大小為$1$x$1$。

對(duì)于一個(gè)線段$p_{1}p_{2}$，設(shè)還能增長$t$次，$L=|p_{1}p_{2}|$，那么最后的長度為$L(1+\frac{2}{3}t)$

problem3 link

$p_{5}$和$p_{7}$的個(gè)數(shù)就是5和7的個(gè)數(shù)。剩下的數(shù)字1，2，3，4，6，8，9出現(xiàn)的次數(shù)都不能確定。

可以枚舉2,4,8出現(xiàn)的次數(shù)，這樣根據(jù)$p_{2}$可以確定6出現(xiàn)的次數(shù)，再枚舉9出現(xiàn)的次數(shù)，然后根據(jù)$p_{3}$以及6和9的個(gè)數(shù)可以確定3的個(gè)數(shù)，最后根據(jù)$S$可以確定1的個(gè)數(shù)。假設(shè)數(shù)字$i$出現(xiàn)的個(gè)數(shù)為$c_{i}$，令總位數(shù)$n=\sum_{i=1}^{9}c_{i}$。那么假設(shè)最后的某一位為數(shù)字$i$的方案數(shù)有$f(i)=\frac{(n-1)!}{c_{1}c_{2}...(c_{i}-1)...c_{8}c_{9}}$。然后數(shù)字$i$可以在第$0$位到第$n-1$位的任何一位，那么數(shù)字$i$對(duì)答案的貢獻(xiàn)位$g(i)=f(i)*(1+10^{1}+...+10^{n-1})$

?

code for problem1

public class MafiaGame {public double probabilityToLose(int N, int[] decisions) {int[] c = new int[N];for (int x : decisions) {++ c[x];}int mx = 0;for (int x : c) {mx = Math.max(mx, x);}if (mx == 0) {return 0;}int tot = N - decisions.length;int r = 0;for (int i = 0; i < N; ++ i) {if (c[i] <= mx - 1) {tot -= mx - 1 - c[i];}else {r += 1;}}if (tot > 0) {r += tot;}double result = 1.0 / r;while (r != 1) {if (N % r == 0) {return 0;}r = N % r;}return result;}}

　　

code for problem2

public class FractalPicture {static class Point {int x, y;Point() {}Point(int x, int y) {this.x = x;this.y = y;}}static class Rect {int x1, x2, y1, y2;Rect() {}Rect(int x1, int y1, int x2, int y2) {this.x1 = x1;this.y1 = y1;this.x2 = x2;this.y2 = y2;}Rect intersect(Rect a) {return new Rect(Math.max(x1, a.x1),Math.max(y1, a.y1),Math.min(x2, a.x2),Math.min(y2, a.y2));}boolean contains(Rect r) {return x1 <= r.x1 && r.x2 <= x2&&y1 <= r.y1 && r.y2 <= y2;}}static Rect extend(Point p1, Point p2) {if (p1.x == p2.x) {int y1 = Math.min(p1.y, p2.y);int y2 = Math.max(p1.y, p2.y);int detx = Math.max(1, (y2 - y1) / 3);return new Rect(p1.x - detx, y1, p1.x + detx, y2);}else {int x1 = Math.min(p1.x, p2.x);int x2 = Math.max(p1.x, p2.x);int dety = Math.max(1, (x2 - x1) / 3);return new Rect(x1, p1.y - dety, x2, p1.y + dety);}}static int length(Point p1, Point p2) {if (p1.x == p2.x) {return Math.abs(p1.y - p2.y);}return Math.abs(p1.x - p2.x);}public double getLength(int x1, int y1, int x2, int y2) {Point p1 = new Point(0, 0);Point p2 = new Point(0, 81);Rect r = new Rect(x1, y1, x2, y2).intersect(extend(p1, p2));return dfs(r, p1, p2, 499);}static int segIntersectSeg(int L1, int R1, int L2, int R2) {return Math.max(0, Math.min(R1, R2) - Math.max(L1, L2));}static int rectIntersectSegment(Rect i, Point p1, Point p2) {assert i.x1 <= i.x2 && i.y1 <= i.y2;if (p1.x == p2.x) {int x = p1.x;int y1 = Math.min(p1.y, p2.y);int y2 = Math.max(p1.y, p2.y);if (i.x1 <= x && x <= i.x2) {return segIntersectSeg(i.y1, i.y2, y1, y2);}else {return 0;}}else {int y = p1.y;int x1 = Math.min(p1.x, p2.x);int x2 = Math.max(p1.x, p2.x);if (i.y1 <= y && y <= i.y2) {return segIntersectSeg(i.x1, i.x2, x1, x2);}else {return 0;}}}static double calculate(Point p1, Point p2, int t) {return length(p1, p2) * (1.0 + t * 2.0 / 3.0);}static double calculateUnit(Rect r, Point p1, Point p2, int t) {double tot = calculate(p1, p2, t);if (p1.x == p2.x) {int x = p1.x;int y1 = Math.min(p1.y, p2.y);int y2 = Math.max(p1.y, p2.y);if (r.x1 <= x && x <= r.x2 && r.y1 <= y1 && y2 <= r.y2) {if (r.x1 == x || r.x2 == x) {return (tot - 1) * 0.5 + 1;}return tot;}return 0;}else {int y = p1.y;int x1 = Math.min(p1.x, p2.x);int x2 = Math.max(p1.x, p2.x);if (r.y1 <= y && y <= r.y2 && r.x1 <= x1 && x2 <= r.x2) {if (r.y1 == y || r.y2 == y) {return (tot - 1) * 0.5 + 1;}return tot;}return 0;}}static Point[] explode(Point p1, Point p2) {if (p1.x == p2.x) {int len = p2.y - p1.y;Point pp1 = new Point(p1.x, p1.y + len / 3 * 2);Point pp2 = new Point(p1.x - len / 3, pp1.y);Point pp3 = new Point(p1.x + len / 3, pp1.y);return new Point[]{pp1, pp2, pp3};}else {int len = p2.x - p1.x;Point pp1 = new Point(p1.x + len / 3 * 2, p1.y);Point pp2 = new Point(pp1.x, p1.y - len / 3);Point pp3 = new Point(pp1.x, p1.y + len / 3);return new Point[]{pp1, pp2, pp3};}}double dfs(Rect r, Point p1, Point p2, int t) {if (r.x1 > r.x2 || r.y1 > r.y2) {return 0;}if (t == 0) {return rectIntersectSegment(r, p1, p2);}if (r.contains(extend(p1, p2))) {return calculate(p1, p2, t);}if (length(p1, p2) == 1) {return calculateUnit(r, p1, p2, t);}Point[] ps = explode(p1, p2);double result = rectIntersectSegment(r, p1, ps[0]);result += dfs(r, ps[0], ps[1], t - 1);result += dfs(r, ps[0], ps[2], t - 1);result += dfs(r, ps[0], p2, t - 1);return result;} }

code for problem3

import java.util.*; import java.math.*; import static java.lang.Math.*;public class ProductAndSum {final static int mod = 500500573;public int getSum(int p2, int p3, int p5, int p7, int S) {long[] p = new long[S + 1];long[] q = new long[S + 1];p[0] = q[0] = 1;for (int i = 1; i <= S; ++ i) {p[i] = p[i - 1] * i % mod;q[i] = pow(p[i], mod - 2);}long[] f = new long[S + 1];f[0] = 1;for (int i = 1, b = 1; i <= S; ++ i) {b = (int)(b * 10L % mod);f[i] = (f[i - 1] + b) % mod;}int[] c = new int[10];c[5] = p5;c[7] = p7;long result = 0;for (c[2] = 0; c[2] <= p2; ++ c[2]) {for (c[4] = 0; c[4] * 2 + c[2] <= p2; ++ c[4]) {for (c[8] = 0; c[8] * 3 + c[4] * 2 + c[2] <= p2; ++ c[8]) {c[6] = p2 - c[2] - c[4] * 2 - c[8] * 3;for (c[9] = 0; c[9] * 2 +c[6] <= p3; ++ c[9]) {c[3] = p3 - c[6] - c[9] * 2;c[1] = S;for (int i = 2; i <= 9; ++ i) {c[1] -= c[i] * i;}if (c[1] < 0) {continue;}int n = 0;for (int i = 1; i <= 9; ++ i) {n += c[i];}long k = p[n - 1];for (int i = 1; i <= 9; ++ i) {k = k * q[c[i]] % mod;}for (int i = 1; i <= 9; ++ i) {if (c[i] != 0) {result += k * p[c[i]] % mod * q[c[i] - 1] % mod * f[n - 1] % mod * i % mod;result %= mod;}}}}}}return (int)result;}static long pow(long a, long b) {a %= mod;long result = 1;while (b > 0) {if (b % 2 == 1) {result = result * a % mod;}a = a * a % mod;b >>= 1;}return result;} }

　　

?

轉(zhuǎn)載于:https://www.cnblogs.com/jianglangcaijin/p/7906349.html

總結(jié)

以上是生活随笔為你收集整理的topcoder srm 500 div1的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。