[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 閱讀(464) | 評論 (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 閱讀(193) | 評論 (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 閱讀(313) | 評論 (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 閱讀(124) | 評論 (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 閱讀(455) | 評論 (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 閱讀(239) | 評論 (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 閱讀(213) | 評論 (0) | 編輯收藏

World Finals Warmup I @UVA [塊狀鏈表]

摘要: 難得做一場五小時的比賽……本以為這比賽，前兩個小時做完水題就該手手睡了……沒想到做完了五小時……不錯不錯…… 題目傳送門剛上來必然是看A題……A題乍一看有想法，實際上加上那個序之后比較惡心……想了五六分鐘不看了…… ... 閱讀全文

posted @ 2011-02-06 10:19 sweetsc 閱讀(798) | 評論 (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 閱讀(186) | 評論 (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 閱讀(151) | 評論 (0) | 編輯收藏

僅列出標題

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

常用鏈接

留言簿(2)

我參與的團隊

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜