• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            oyjpArt ACM/ICPC算法程序設計空間

            // I am new in programming, welcome to my blog
            I am oyjpart(alpc12, 四城)
            posts - 224, comments - 694, trackbacks - 0, articles - 6

            SRM387

            Posted on 2008-01-10 17:23 oyjpart 閱讀(1004) 評論(0)  編輯 收藏 引用 所屬分類: ACM/ICPC或其他比賽

            同SRM386,再度只做了第一題。。RATING保持不變。。算了,我就是弱。

            第一題其實相當于把非法的行刪掉并且保持列為1就可以了(去掉一行joker)
            我代碼寫的慢啊。。又是低分。。

            第二題是個DP,本來是不很難想的,感覺還是時間太緊,有點緊張了。。
            小小菜鳥再度100多分收場。。    

               public class Node implements Comparable { 
                    public int x, y;

                    public int compareTo(Object o) {
                        Node no = (Node) o;
                        if (this.x == no.x)
                            return this.y - no.y;
                        return this.x - no.x;
                    }

                    public Node(int x, int y) {
                        this.x = x;
                        this.y = y;
                    }
                }

                public int numberOfSubsets(int[] start, int[] finish) {
                    int n = start.length;
                    Node[] A = new Node[n+2];
                    int[] dp = new int[n+2];
                    for (int i = 0; i < n; ++i) {
                        A[i] = new Node(start[i], finish[i]);
                    }
                    A[n++] = new Node(1000, 1000);
                    A[n++] = new Node(0, 0);
                    Arrays.sort(A);
                    Arrays.fill(dp, 0);
                    dp[0] = 1;
                    int i, j, k;
                    for (i = 1; i < n; ++i) {
                        for (j = 0; j < i; ++j) {
                            if (!(A[i].x <= A[j].y && A[i].y >= A[j].x)) {
                                boolean ok = true;
                                for (k = j + 1; k < i; ++k) {
                                    if (!(A[k].x <= A[i].y && A[k].y >= A[i].x)
                                            && !(A[k].x <= A[j].y && A[k].y >= A[j].x)) {
                                        ok = false;
                                    }
                                }
                                if (ok) 
                                    dp[i] += dp[j];
                            }
                        }
                    }

                    return dp[n-1];
                }

            Analysis提供了一種O(nlogn)的方法,不難,有興趣的可以看看。

            There are several approaches to this problem. Most of them use dynamic programming, but some optimized brute-force solutions may also pass system test. Here will be explained an O(n^2) algorithm and it can be relatively easily modified to have O(n * lg(n)) complexity, where n is the number of intervals.

            First of all, let's sort intervals by their finish points. Then we'll define two functions, partial(x) and total(x). The total(x) returns the number of valid subsets of the set formed by first x + 1 intervals. The partial(x) returns the number of valid subsets, which contains x-th interval, of the set formed by the first x + 1 intervals. The solution would be total(n), where n is the number of intervals. Now, let's see how to calculate each of those two functions.

            logN來自二分查找i前面的最后一個不相交的線段。

            第三題也不是很難,但是,比如說我這種第二題都沒出的人就不用說了。。
            #pragma warning ( disable : 4786 )

            #include <vector>
            #include <list>
            #include <map>
            #include <set>
            #include <deque>
            #include <stack>
            #include <bitset>
            #include <queue>
            #include <algorithm>
            #include <functional>
            #include <numeric>
            #include <utility>
            #include <sstream>
            #include <iostream>
            #include <iomanip>
            #include <cstdio>
            #include <cmath>
            #include <cstdlib>
            #include <ctime>

            using namespace std;
            #define sz(x) ((int)(x).size())
            #define Max(a, b) ((a) > (b) ? (a) : (b))
            #define Min(a, b) ((a) < (b) ? (a) : (b))
            #define two(x) (1<<(x))
            #define contains(S, x) (((S)&two(x)) != 0)
            typedef long long LL;
            const int MAXINT = 1000000000;
            const double INF = 10e300;
            const double EPS = 1e-7;

            inline int dblcmp(double a, double b) { if(fabs(a-b) < EPS) return 0; if(a < b) return -1;  return 1; }  
            inline int bitcnt(int x) { int cnt = 0; while(x != 0) { cnt++; x &= (x-1); } return cnt; }
            template<typename T> string toString(const T& s) { ostringstream os; os << s; return s.str();}

            const int MOD = 1000000007;

            LL P[2600];
            LL power(LL a, LL b) { //actually returns a integer in [0, MOD)
             if(b == 0) return 1;
             if(b % 2 == 0) {
              LL t = power(a, b>>1);
              return t*t%MOD;
             }
             else
              return a%MOD*power(a, b-1)%MOD;
            }

            LL cal(int a0, LL q, LL times) {
             if(times == 0) return 0;
             LL t = cal(a0, q, times>>1);
             t *= (1+power(q, times>>1));
             t %= MOD;
             if(!(times & 1)) return t;
             return (t*q+a0)%MOD;
            }

            class StrangeArray
            {
            public:
             int calculateSum(vector <int> A, vector <int> B, string sN)
             {
              LL N;
              sscanf(sN.c_str(), "%lld", &N);
              int i, cycle = sz(A)*sz(B);
              for(i = 0; i < cycle; ++i) {
               P[i] = power(A[i%sz(A)], B[i%sz(B)] + i/sz(B));
              }

              LL ans = 0;
              for(i = 0; i < cycle; ++i) {
               LL times = (N-i-1+cycle)/cycle;
               LL q = power(A[i%sz(A)], sz(A));
               ans += cal(P[i], q, times);
               ans %= MOD;
              }
              return (int)ans;
             }
             
             
            };

             

            // Powered by FileEdit
            // Powered by TZTester 1.01 [25-Feb-2003]
            // Powered by CodeProcessor

            欧美牲交A欧牲交aⅴ久久| 国产成人综合久久精品红| 久久久久久国产精品免费无码 | 日韩精品无码久久久久久| 亚洲精品无码久久久久| AV无码久久久久不卡网站下载| 狠狠色综合久久久久尤物| 久久综合精品国产一区二区三区| 日韩欧美亚洲综合久久| 免费观看久久精彩视频| 久久人妻AV中文字幕| 99久久99久久久精品齐齐| 色婷婷久久综合中文久久一本| 久久久婷婷五月亚洲97号色| 久久久久亚洲?V成人无码| 大伊人青草狠狠久久| 久久精品国产亚洲av麻豆图片 | 久久久久人妻精品一区二区三区 | 性做久久久久久久久| 精品久久一区二区| 99久久无色码中文字幕人妻 | 亚洲国产精品成人久久| 久久久精品国产亚洲成人满18免费网站| 久久香综合精品久久伊人| 久久久久亚洲AV成人网人人软件| 久久久久亚洲Av无码专| 麻豆精品久久久久久久99蜜桃 | 久久精品国产福利国产琪琪| 久久男人Av资源网站无码软件 | 91久久九九无码成人网站| 色婷婷综合久久久久中文| 欧美日韩精品久久久免费观看| 久久久网中文字幕| 欧美麻豆久久久久久中文| 99久久国产热无码精品免费久久久久 | 99久久精品午夜一区二区| 亚洲熟妇无码另类久久久| 久久精品国产亚洲AV不卡| 日韩欧美亚洲综合久久| 久久亚洲国产精品成人AV秋霞| 亚洲国产视频久久|