[NKU]sweet ＠ Google && TopCoder && CodeForces

:: 管理

33 Posts :: 1 Stories :: 15 Comments :: 0 Trackbacks

昨天在老图，借得一本随机算法的书，乍一看目录，卧槽，NB了，什么都能随机……果断借走……
第一章介绍了蒙特卡罗算法和拉斯维加斯算法，Qsort就是拉斯维加斯算法，随机的结果只影响程序速度；而下面这个题，无源无汇的最小割，则是蒙特卡罗算法……随机的结果都不见得对，但是，多随机几次，得到最优解的概率会增大不少

算法很简单，在图中随机选择一条边，并将他们连接的顶点（顶点集合更为妥当……）合并，直到只剩下两个顶点集合，则这两个集合间的边至少是个割………多次随机则应该就能得到最小割了……
每次得到最小割的概率，书上证明是 2/n^2 ，可以说是相当之小……利用高等数学的知识，找不到的概率应该是1-2/n^2，于是乎，执行N^2/2次，还找不到答案的概率就是1/e……而每次随机一条边大概是O（M）的级别吧……整个算法大概是O(n*n*m)的（确切说是omega，一定是这么多次），还不保证对……

想起AC哥说过，去年FZU的B，HDU3691是这么个题，于是搞了搞，轻松拍完，样例无压力过了……之后各种TLE……毕竟300*300*50000还是压力较大的……然后各种调整随机次数，期间翻译至java……仍然TLE……一怒之下，把随机次数调整成了N次，至少能WA了……C++版本需要2400+MS，java版本需要1700+MS……（java版程序套用了我的java模板，IO是类似getchar的优化，C++是scanf，可见数据之WS……）于是把java版程序的随机次数改成5*N次，居然过了……

现在想来，数据可能水了；也可能书上理论证明的时候，放缩的太厉害，然后几百次方之后，正确率实际上比理论计算会高出很多……
无代码无真相

  1 import java.util.*;
  2 import java.io.*;
  3 import java.math.*;
  4
  5
  6 public class HDU3691 {
  7     public static void main(String args[]) throws IOException {
  8         new Prob().solve();
  9     }
10 }
11
12 class Prob {
13     int[] f = new int[50010];
14     int[] t = new int[50010];
15     int[] c = new int[50010];
16     int[] fa = new int[310];
17     int n,m,tot;
18     int ans;
19     Random rand = new Random();
20
21     int find(int x) {
22         if (x == fa[x]) return x;
23         return fa[x] = find(fa[x]);
24     }
25
26     void change(int x,int y) {
27         x = find(x);
28         y = find(y);
29         fa[x] = y;
30     }
31
32     int work() {
33         for (int i = 1; i <= n; i++) {
34             fa[i] = i;
35         }
36         int cnt = n;
37         while (cnt > 2) {
38             int now = rand.nextInt(tot);
39             if (find(f[now]) == find(t[now])) {
40                 int tmp = f[now]; f[now] = f[tot-1]; f[tot-1] = tmp;
41                 tmp = t[now]; t[now] = t[tot-1]; t[tot-1] = tmp;
42                 tmp = c[now]; c[now] = c[tot-1]; c[tot-1] = tmp;
43                 tot --;
44             } else {
45                 cnt --;
46                 change(f[now],t[now]);
47             }
48         }
49         int ans = 0;
50         for (int i = 0; i < m; i++) {
51             if (find(f[i])!=find(t[i])) {
52                 ans += c[i];
53             }
54         }
55         return ans;
56     }
57
58     final int TIMES = 5;
59
60     void solve() throws IOException {
61         MyReader in = new MyReader();
62         for (;;) {
63             n = in.nextInt();
64             m = in.nextInt();
65             tot = in.nextInt();
66             if (n + m + tot == 0) break;
67             for (int i = 0; i < m; i++) {
68                 f[i] = in.nextInt();
69                 t[i] = in.nextInt();
70                 c[i] = in.nextInt();
71             }
72             ans = 0x7fffffff;
73             int times = TIMES * n;
74             while (times-- > 0) {
75                 tot = m;
76                 int tmp = work();
77                 if (tmp < ans) {
78                     ans = tmp;
79                 }
80             }
81             System.out.println(ans);
82         }
83     }
84     void debug(Object

x) {
85         System.out.println(Arrays.deepToString(x));
86     }
87 }
88
89 class MyReader {
90     BufferedReader br = new BufferedReader (
91             new InputStreamReader (System.in));
92     StringTokenizer in;
93     String next() throws IOException {
94         if (in == null || !in.hasMoreTokens()) {
95             in = new StringTokenizer(br.readLine());
96         }
97         return in.nextToken();
98     }
99     int nextInt() throws IOException {
100         return Integer.parseInt(next());
101     }
102 }

posted @ 2011-04-02 14:00 sweetsc 阅读(455) | 评论 (0) | 编辑收藏

来个旁门左道……

今天看了看java的并行……写了一个实验品……
照书抄的，无须解释，看看估计就懂了……
但是把这个用在做题中会怎样呢？…… =_=

1 import java.util.concurrent.Executors;
2 import java.util.concurrent.ExecutorService;
3
4 class SumTask implements Runnable {
5     long Left;
6     long Right;
7     long ans;
8     final long MOD = 199999997;
9     SumTask(long L,long R) {
10         Left = L;
11         Right = R;
12     }
13     public void run() {
14         for (long i = Left; i < Right; i++) {
15             ans = (ans + i) % MOD;
16         }
17         System.out.println(ans);
18     }
19 }
20
21 public class mul {
22     public static void main(String args[]) {
23         long MOD = 199999997;
24         long ans = 0;
25         for (long i = 0; i < 400000000; i++) {
26             ans = (ans + i) % MOD;
27         }
28         System.out.println(ans);
29         SumTask task1 = new SumTask(0,100000000);
30         SumTask task2 = new SumTask(100000000,200000000);
31         SumTask task3 = new SumTask(200000000,300000000);
32         SumTask task4 = new SumTask(300000000,400000000);
33         System.out.println("4 threads Start!!");
34         ExecutorService runner = Executors.newFixedThreadPool(4);
35         runner.execute(task1);
36         runner.execute(task2);
37         runner.execute(task3);
38         runner.execute(task4);
39         runner.shutdown();
40     }
41 }

posted @ 2011-03-21 19:16 sweetsc 阅读(174) | 评论 (0) | 编辑收藏

诡异的SRM500

今天早上0：00，SRM500……

注册时，定睛一看，有个TC的Member阵亡了…你是否同意把这次比赛奖金捐给他…本以为是11区人在海啸中阵亡，没想到是俄罗斯人，据传闻说是劳累过度之类的……（大帝：你看看，你看看，又是听说 =_=），讽刺的是这条新闻正文里面套着FB，然后墙了…………
不过奖金啥的也只能YY了……
250是个很硬的题……前几名里都有人彻底放弃了的……System挂掉了至少100人……
题意是这样：给N个人（N<=500），需要投票选出一个，其中M（M<=min(50,N)）人有确定的想法，其他人投票只投给当前票数最少的人，如果平票则在平票人中投第二轮，第三轮，原先如果有人确定想投某人，但是这人没晋级下一轮，则之后他就成无想法了………这样肯定有一些人被选出来的概率比较大，求最大的概率

Sample：
3
{1, 1, 1}
答案：1，1号一定被选出

5
{1, 2, 3}
答案：0，不可能选的完
（投完123后，人的得票数为01110，剩下两个，一个投0一个投4，又从头来了……）

20
{1, 2, 3, 4, 5, 6, 7, 1, 2, 3, 4, 5, 6, 7, 18, 19, 0}
答案：0，第一轮：1234567，第二轮：剩下其中的6个，第三轮：剩下两个，第四轮就选不出来了……

23
{17, 10, 3, 14, 22, 5, 11, 10, 22, 3, 14, 5, 11, 17}

答案：0.142857.....，第一轮剩下7个，第二轮剩下2个，第三轮能选出来1个，每个人被选出的概率都是一样的……

这个问题不太好理解，多数人都卡在了读题上……而且很容易没有想法……
先写了个模拟，然后逐渐摸清门道了……
当时发现，前几轮的走势是必然的，后面的就有随机性了
譬如
20
{1, 2, 3, 4, 5, 6, 7, 1, 2, 3, 4, 5, 6, 7, 18, 19, 0}
第一轮剩下的人，必然是1234567，但是后面，支持1234567的那14个人一定会给他们投票；其他6个没想法的人就不一定投给谁了…
于是先模拟出来那些必然现象，然后，就是纯粹和数字相关，和人无关的这么一件事情了……
大概就是N个人，M人候选这样……由于N个人中，包含M＊X个有想法的人，会给这M人分别投M票，剩下N－M＊X个没想法的人会给票少的人投，最后，下一轮的候选人就是N％M……一个小递归验证就行了……如果当前M可以得到1，则有解，如果最后N％M ＝＝ 0，就是上面那种20个人给2个人投票那样，投不出来……

事后看了别人的代码想明白了，只需要模拟一步……
代码：

1 class MafiaGame {
2     public double probabilityToLose(int N, int[] decisions) {
3         int[] cnt = new int[N];
4         int NoIdeaMan = N;
5         for (int i :decisions) {
6             cnt[i] ++;
7             NoIdeaMan --;
8         }
9         while (NoIdeaMan-->0) {
10             int min = 99999999;
11             for (int i : cnt) {
12                 if (i < min) min = i;
13             }
14             for (int i = 0; i < N; i++) {
15                 if (cnt[i] == min) {
16                     cnt[i] ++;
17                     break;
18                 }
19             }
20         }
21         int Group = 0;
22         int max = 0;
23         for (int i : cnt) {
24             if (i > max) {
25                 max = i;
26                 Group = 0;
27             }
28             if (i == max) {
29                 Group ++;
30             }
31         }
32         System.out.println(Group);
33         if (check(N,Group)) {
34             return 0.0;
35         }
36         return 1.0/Group;
37     }
38
39     boolean check(int N,int Group) {
40         if (Group == 1) return false;
41         if (N % Group == 0) return true;
42         return check(N,N%Group);
43     }
44 }

最后Systemtest阶段，哥从400＋爬到了324……前面至少挂了100人……
rating -> 1591，再创历史新高…………

posted @ 2011-03-20 17:35 sweetsc 阅读(305) | 评论 (0) | 编辑收藏

Ural1186【小型编译器】

很少写这种题目……这种题目体力消耗是大于技术含量的……
题意是这样，给你两个化学反应式，让你判断是否元素守恒 =_=

传送门

比较关键的语法部分：

<formula> ::= [<number>] <sequence> { '+' [<number>] <sequence> }
<sequence> ::= <element> [<number>] { <element> [<number>] }
<element> ::= <chem> | '(' <sequence> ')'
<chem> ::= <uppercase_letter> [ <lowercase_letter> ]
<uppercase_letter> ::= 'A'..'Z'
<lowercase_letter> ::= 'a'..'z'
<number> ::= '1'..'9' { '0'..'9' }

首先要解决一个根本问题，如何说两个式子就相等了……比较科学的想法还是找一个“标准”表示法，让他无论式子啥样，翻译出来，都应该是那个格式，然后再比较是否相等；于是乎，我们使用TreeMap来干这件事……

接下来就好办了……挨层递归，把这个Formula变成若干sequence，然后把sequence变成 element；element变回sequence或者返回一个包含关键字[<chem>,1]的Treemap……然后递归回去，把TreeMap里面的东西乘NUMBER（如果有的话）逐层合并成一个TreeMap……
感觉上应该可以利用Scanner和正则表达式整的更简单，但是我不知道括号里套括号的情况正则表达式会搞成什么样（譬如：（Si(O)2），如果用类似(*)这样的，匹配出来是(Si(O)还是（Si(O)2），如果我就想要后者应该怎么搞……求神人路过指点吧……）

1 class Prob {
2
3     TreeMap<String,Integer> merge(TreeMap<String,Integer> a,
4         TreeMap<String,Integer> b , int cnt) {
5         for (Map.Entry<String,Integer> i : b.entrySet()) {
6             String pos = i.getKey();
7             int delta = a.get(pos) == null ? 0 : a.get(pos);
8             a.put(pos,delta + i.getValue()*cnt);
9         }
10         return a;
11     }
12
13     TreeMap<String,Integer> workElements(String now) {
14         if (now.charAt(0) == '(') {
15             return workSequence(now.substring(1,now.length()-1));
16         }
17         TreeMap<String,Integer> ans = new TreeMap<String,Integer>();
18         ans.put(now,1);
19         return ans;
20     }
21
22     TreeMap<String,Integer> workSequence(String now) {
23         TreeMap<String,Integer> ans = new TreeMap<String,Integer>();
24         while (now.length() > 0) {
25             int r = 1;
26             if (now.charAt(0) == '(') {
27                 int cnt = 1;
28                 while (cnt > 0){
29                     if (now.charAt(r) == '(') cnt ++;
30                     if (now.charAt(r) == ')') cnt --;
31                     r++;
32                 }
33             } else {
34                 while (r < now.length()
35                     && now.charAt(r) >= 'a' && now.charAt(r) <='z') {
36                     r++;
37                 }
38             }
39             String tmp = now.substring(0,r);
40             now = now.substring(r);
41             int cnt = 0;
42             while (now.length() > 0 && now.charAt(0) <= '9' && now.charAt(0) >='0') {
43                 cnt = cnt * 10 + now.charAt(0) - '0';
44                 now = now.substring(1);
45             }
46             if (cnt == 0) cnt = 1;
47             ans = merge(ans,workElements(tmp),cnt);
48         }
49         return ans;
50     }
51
52     TreeMap<String,Integer> workFormula (String now) {
53         TreeMap<String,Integer> ans = new TreeMap<String,Integer>();
54         StringTokenizer buf = new StringTokenizer(now,"+");
55         while (buf.hasMoreTokens()){
56             String tmp = buf.nextToken();
57             int cnt = 0;
58             while (tmp.charAt(0) <= '9' && tmp.charAt(0) >='0') {
59                 cnt = cnt * 10 + tmp.charAt(0) - '0';
60                 tmp = tmp.substring(1);
61             }
62             if (cnt == 0) cnt = 1;
63             ans = merge(ans,workSequence(tmp),cnt);
64         }
65         return ans;
66     }
67
68     void solve() throws IOException {
69         MyReader in = new MyReader();
70         String samp = in.next();
71         TreeMap<String,Integer> sampTree = workFormula(samp);
72         for (int ii = in.nextInt(); ii > 0; ii--) {
73             String now = in.next();
74             TreeMap<String,Integer> nowTree = workFormula(now);
75             System.out.print(samp);
76             if (nowTree.equals(sampTree)) {
77                 System.out.print("==");
78             } else {
79                 System.out.print("!=");
80             }
81             System.out.println(now);
82         }
83         //

.
84 }
85 void debug(Object

x) {
86 System.out.println(Arrays.deepToString(x));
87 }
88 }

posted @ 2011-02-24 22:54 sweetsc 阅读(117) | 评论 (0) | 编辑收藏

贴个裸模板……求引玉……

1 import java.util.*;
2 import java.io.*;
3 import java.math.*;
4
5
6 class Main {
7     public static void main(String args[]) throws IOException {
8         new Prob().solve();
9     }
10 }
11
12 class Prob {
13     void solve() throws IOException {
14         MyReader in = new MyReader();
15         //

.
16 }
17 void debug(Object

x) {
18         System.out.println(Arrays.deepToString(x));
19     }
20 }
21
22 class MyReader {
23     BufferedReader br = new BufferedReader (
24         new InputStreamReader (System.in));
25     StringTokenizer in;
26     String next() throws IOException {
27   while (in == null || !in.hasMoreTokens()) {
28             in = new StringTokenizer(br.readLine());
29         }
30         return in.nextToken();
31     }
32     int nextInt() throws IOException {
33         return Integer.parseInt(next());
34     }
35 }

posted @ 2011-02-23 14:32 sweetsc 阅读(422) | 评论 (3) | 编辑收藏

Ural1056【找出一个树的所有核】

所谓树的核，就是树的中心
中心是指到其它节点距离的最大值最小的节点

1 - 2 - 5
|   |
3   4



样例里的1和2就是这个树的中心……

本题是要找出树的所有中心

由于时限2S，ural的机器又快，节点数不过10000，N^2枚举+DFS验证是无压力的……

但是身为一个有志青年，是不能轻言满足的……



由于无根树不好办事，我们不妨令根为1；

然后采用两遍DFS的方法

第一次从根开始DFS，处理每个顶点最多能够沿DFS的方向走多远，直接DFS就行

（在下面程序保存为rdeep）

这一部分处理完了，接下来的部分是每个顶点向该点的父节点反着走，能走多远

（在下面程序保存为fdeep）

这里的处理方法是这样：假设现在是这样：A的父亲为FA，有子节点B，C，D，沿着B向下DFS能走距离Db，C：Dc，D：Dd；

那么由B反着走到A，然后再往远走，最远能到哪里呢？……有3个选择，沿着FA向上，沿着C向下，沿着D向下

选择一个最长的就行了；

假设某个节点的子节点数很多，实际上只用保留两种情况：能走最远的字节点，以及能走第二远的字节点；

其他字节点都往该节点父节点或者最远的子节点走；最远的那个往该节点父节点或者第二远的子节点走；



代码如下：

1 class Prob {
  2 //临接表
  3     ArrayList< LinkedList<Integer> > adj;
  4 //加速控制台IO
  5     BufferedReader br = new BufferedReader(
  6         new InputStreamReader(System.in));
  7
  8 //计算正向DFS的最远深度
  9     int[] rdeep;
10     int dfs(int now,int fa) {
11         for (Integer i : adj.get(now)) {
12             if (i == fa) continue;
13             int tmp = dfs(i,now);
14             if (tmp > rdeep[now]) {
15                 rdeep[now] = tmp;
16             }
17         }
18         return rdeep[now] + 1;
19     }
20
21 //反向DFS的深度
22     int[] fdeep;
23 //falen是从当前节点向FA反过去走能到的最远距离
24     void dfs(int now,int fa,int faLen) {
25 //找顺着走最远的子节点
26         int fIND = -1;
27         for (Integer i : adj.get(now)) {
28             if (i == fa) continue;
29             if (fIND == -1 || rdeep[i] > rdeep[fIND]) {
30                 fIND = i;
31             }
32         }
33 //找不到，当前就是叶子节点，退出
34         if (fIND == -1) {
35             fdeep[now] = faLen;
36             return;
37         }
38 //找第二远的节点
39         int sIND = -1;
40         for (Integer i : adj.get(now)) {
41             if (i == fa) continue;
42             if (i == fIND) continue;
43             if (sIND == -1 || rdeep[i] > rdeep[sIND]) {
44                 sIND = i;
45             }
46         }
47 //没有第二远，只能向FA反向走
48         if (sIND == -1) {
49             fdeep[now] = faLen;
50             dfs(fIND,now,faLen+1);
51             return;
52         }
53 //向最远的走或者向FA走哪个更远
54         int v1 = rdeep[fIND] + 1 > faLen ? rdeep[fIND] + 1 : faLen;
55 //向第二远的走或向FA走哪个更远
56         int v2 = rdeep[sIND] + 1 > faLen ? rdeep[sIND] + 1 : faLen;
57
58 //更新当前faLen
59         fdeep[now] = faLen > v1? faLen : v1;
60         fdeep[now] = fdeep[now] > v2? fdeep[now] : v2;
61
62 //更新子节点
63         for (Integer i : adj.get(now)) {
64             if (i == fa) continue;
65 //最远的那个子节点：沿着第二个走
66 //其他沿着最远的走
67             if (i == fIND) {
68                 dfs(i,now,v2+1);
69             } else {
70                 dfs(i,now,v1+1);
71             }
72         }
73     }
74
75
76     void solve() throws IOException {
77 //读入
78         int n = Integer.parseInt(br.readLine());
79         adj = new ArrayList< LinkedList<Integer> >();
80         rdeep = new int[n+1];
81         fdeep = new int[n+1];
82         for (int i = 0; i <= n; i++) {
83             adj.add(new LinkedList<Integer>());
84         }
85         for (int i = 2; i <= n; i++) {
86             int j = Integer.parseInt(br.readLine());
87             adj.get(i).add(j);
88             adj.get(j).add(i);
89         }
90         dfs(1,0);
91         dfs(1,0,0);
92         Set<Integer> ans = new TreeSet<Integer>();
93         int now = n + n;
94 //        debug(fdeep);
95 //        debug(rdeep);
96 //按要求从小到大输出所有答案
97         for (int i = 1; i <= n; i++) {
98             int deep = fdeep[i] > rdeep[i] ? fdeep[i] : rdeep[i];
99             if (deep < now) {
100                 now = deep;
101                 ans.clear();
102             }
103             if (deep == now) {
104                 ans.add(i);
105             }
106         }
107         for (Integer i: ans) {
108             System.out.print(i + " ");
109         }
110     }
111     void debug(Object

x) {
112 System.err.println(Arrays.deepToString(x));
113 }
114 }

posted @ 2011-02-22 23:25 sweetsc 阅读(232) | 评论 (0) | 编辑收藏

SRM497 [乱中升黄]

上午10：00，绝好的SRM时间……

250：给出一个字符串，长度为N（N<=50），由字母'D'和‘I’构成，‘D’表示 a[i]>a[i+1]; 'I' 表示 a[i]<a[i+1]; 根据这个字符串，求一个长度为N+1的排列，如果多解存在，求字典序最小的……
乍一看有点懵……然后自然想到想办法缩减问题规模……刚开始想给1定位，然后缩减成2～N的子问题，不太好想……
于是反过来给N定位，由于要求字典序最小，我们尽量把N往右边放；因为N是最大的，所以肯定是“I”上去的……于是找到最右边的I，让他=N……然后如果后面有D，则顺序的N-1，N-2……然后问题就缩小了……

class PermutationSignature {
    public int[] reconstruct (String str){
        Str = "I"+str;
        int n = str.length();
        int[] ans = new int[n];
        int right = n;
        int now = n;
        for (int i = n-1;i >= 0;i--){
            if (str.charAt(i)=='I') {
                for (int j = i;j<right;j++) {
                    ans[j] = now --;
                }
                right = i;
            }
        }
        return ans;
    }
}

之后的550，一个小编译器式的问题……我表示这种题我最苦手了……战略放弃……
之后的1000，大概是给你A，B，N，K，Upper_bound 和Lower_bound（long 级别），问 A*K %N , (A+1)*K %N ....(B)*K%N这些数里面，有多少个<=Upper_bound 且 >=Lower_bound的，写了写……最后交了个样例都不过的程序，瞬间被cha……
看了看神人的程序，思路大方向没问题，但是计数上面我的方法太拙劣了……

然后，不幸的是数据似乎出了点问题，一直都在rejudge……
最后rating 1493->1565，历史最高……又黄回去了～～

posted @ 2011-02-11 13:55 sweetsc 阅读(206) | 评论 (0) | 编辑收藏

World Finals Warmup I @UVA [块状链表]

摘要: 难得做一场五小时的比赛……本以为这比赛，前两个小时做完水题就该手手睡了……没想到做完了五小时……不错不错…… 题目传送门刚上来必然是看A题……A题乍一看有想法，实际上加上那个序之后比较恶心……想了五六分钟不看了…… ... 阅读全文

posted @ 2011-02-06 10:19 sweetsc 阅读(779) | 评论 (4) | 编辑收藏

近日 && SRM496

由于潜心期末考试，SRM有一阵都没有做…然后回到了家，午夜档的SRM也都没有做……
终于大年二十九，晚上八点，天时地利人和，做比赛的好日子啊……
第一题是个水模拟……说一个50*50的格子，能竖着画红线或者横着画蓝线，如果他们交了，交点是绿的……给你一个地图，求最少几笔画出……
毫无玄机……

1 public class ColoredStrokes{
2     public int getLeast(String[] pic){
3         int ans=0;
4         for (int i=0;i<pic.length;i++)
5         for (int j=0;j<pic[0].length();j++){
6             if (pic[i].charAt(j)=='R' || pic[i].charAt(j)=='G'){
7                 ans++;
8                 while (pic[i].charAt(j)=='R' || pic[i].charAt(j)=='G'){
9                     j++; if (j==pic[0].length()) break;
10                 }
11                 j--;
12             }
13         }
14         for (int j=0;j<pic[0].length();j++)
15         for (int i=0;i<pic.length;i++){
16             if (pic[i].charAt(j)=='R' || pic[i].charAt(j)=='G'){
17                 ans++;
18                 while (pic[i].charAt(j)=='R' || pic[i].charAt(j)=='G'){
19                     i++; if (i==pic.length) break;
20                 }
21                 i--;
22             }
23         }
24         return ans;
25     }
26 }

第二题大意是这样……给出一个数轴，数轴上分布着N个小球（N<=50），然后给出另一个数轴，上面有M个小球（N<=M<=50），已知第一个数轴上的小球移动速度都相等但是方向不同，移来移去……然后加了几个小球，就成第二个数轴那样了……求小球间有多少可能对应的方案数……

这次思路还算对，先得枚举速度……之后就是个二分图了…而且顶点度<=2…然后就是匹配数计数了……可惜不会，写了个爆的，然后Cha阶段瞬间就被挂了……
Rating+=4，1493，还是蓝的……
争取这9个月左右可以奋斗到稳黄甚至黄满吧……

posted @ 2011-02-02 11:32 sweetsc 阅读(175) | 评论 (0) | 编辑收藏

SRM490……

只看了一题……
题意大概是这样，每隔M分钟会来一个飞船并开始等待，每隔N分钟会有一个传送门，传送走等待的飞船……求飞船平均等待时间
（N，M<=1000000000）
相当于求N-(M*i)%N的和（M*i%n==0需要特判停止之类的）……前面一部分可以拆开，求和，上公式，但是后面不行……
于是乎，用新会用的HashMap算了个循环节……但是面对极限数据（循环节＝＝N）貌似还是挂……
万般无奈之际，我通过观察规律，还真发现了一个规律…直接上代码吧……

1 class Starport{
2
3     long gcd(long n,long m){
4         if (m==0) return n;
5         return gcd(m,n%m);
6     }
7
8     public double getExpectedTime(int n,int m){
9         long tmp=gcd(n,m);
10         long sum=n*n;
11         sum-=n*(n+tmp)/2;
12         double ans=sum;
13         ans/=n;
14         System.out.println(ans);
15         return ans;
16     }
17 }

当然，发现了这个规律之后，可以除n化简之类的，不叙……
Challenge时间，搞掉了一个硬爆的，有个爷们是直接循环的，但是貌似问题不在速度，我没Cha掉……有个爷们代码前面一堆废话，我以为是类似hash的思路，后来才发现最后没用那堆废话，实际上程序还是公式……结果没赚没赔……
rating->1487……又掉成蓝了……我了个去……
其实蓝的不冤，毕竟现在思路还是不咋样，有些东西其实感觉最终可以想出来，但是速度却不能满足竞赛要求……
总之还是奋战吧……

posted @ 2010-12-09 02:23 sweetsc 阅读(144) | 评论 (0) | 编辑收藏

仅列出标题

[NKU]sweet ＠ Google && TopCoder && CodeForces

常用链接

留言簿(2)

我参与的团队

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜