problem1 link

如果decisions的大小为0,那么每一轮都是$N$个人。答案为0.

否则,如果答案不为0,那么概率最大的一定是一开始票数最多的人。因为这个人每一轮都在可以留下来的人群中。

假设第一轮之后剩下$r_{1}$个人,那么第二轮之后将剩下$r_{2}=N$%$r_{1}$个人。不妨设$r_{1}<N$。第一轮能够使得$r_{1}$个人的票数答案一样多且最多(设这个票数为$x$),那么这个x一定是大于等于单纯由decisions决定出的最大值。而现在$r_{1}<N$了,所以必然现在能投出的最大值还是大于等于第一轮的最大值。最后结果是:一些人的票数是$N/r_{1}$,另外一些是$N/r_{1}+1$,那么后一部分人将留下来到下一轮。

同理第$k$轮之后剩下$r_{k}=N$%$r_{k-1}$个人,直到剩下一个人。当出现$N$%$r_{i}=0$时,说明出现循环,答案为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

首先,最后的图形的结果不会超出(-27,0)到(27,81)这个范围。

由于给出的范围都是整数,那么每次用给出的区间$R$与当前图形能扩展出的最大区间$R_{i}$比较,如果$R$能包含$R_{i}$,那么直接计算即可。否则可将当前线段继续增长,出现三个小区间,继续匹配即可。可以看出,最后最小的区间的大小为$1$x$1$。

对于一个线段$p_{1}p_{2}$,设还能增长$t$次,$L=|p_{1}p_{2}|$,那么最后的长度为$L(1+\frac{2}{3}t)$

problem3link

$p_{5}$和$p_{7}$的个数就是5和7的个数。剩下的数字1,2,3,4,6,8,9出现的次数都不能确定。

可以枚举2,4,8出现的次数,这样根据$p_{2}$可以确定6出现的次数,再枚举9出现的次数,然后根据$p_{3}$以及6和9的个数可以确定3的个数,最后根据$S$可以确定1的个数。假设数字$i$出现的个数为$c_{i}$,令总位数$n=\sum_{i=1}^{9}c_{i}$。那么假设最后的某一位为数字$i$的方案数有$f(i)=\frac{(n-1)!}{c_{1}c_{2}...(c_{i}-1)...c_{8}c_{9}}$。然后数字$i$可以在第$0$位到第$n-1$位的任何一位,那么数字$i$对答案的贡献位$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;
}
}

  

最新文章

  1. 使用RequireJS并实现一个自己的模块加载器 (一)
  2. CSS继承总结
  3. mac 进程管理
  4. entity refenrece 在views中的运用
  5. 【转】 远程到服务器安装visualSVN server,出现Service &#39;VisualSVN Server&#39; failed to start的解决方法
  6. Java SortedSet接口
  7. sublimeformaya
  8. 01 Hello, Python!
  9. EJB
  10. Java排序算法(四):Shell排序
  11. Java项目中打开本地文件的方法
  12. 背景background
  13. 第一次在手机上跑动ane
  14. Opticks依赖库的下载和编译
  15. 《java入门第一季》之面向对象(多态练习)
  16. 也谈如何获取真实正确的 Windows 系统版本号
  17. ARM三级流水线
  18. Indidual Homework Assignment
  19. electron 主进程,和渲染进程的通信
  20. 实现项目WC

热门文章

  1. MYSQL 5.7修改密码,登录问题
  2. sqli-labs(十)(过滤注释符)
  3. LA 4992 Jungle Outpost(半平面交)
  4. Lua class
  5. Mysql导出(多张表)表结构及表数据 mysqldump用法
  6. 软工网络15团队作业4——Alpha阶段敏捷冲刺6.0
  7. [7] Windows内核情景分析---线程同步
  8. C. Primes or Palindromes?
  9. IDEA相关知识整理
  10. Selenium自动化测试,接口自动化测试开发,性能测试从入门到精通