• <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

            超级97碰碰碰碰久久久久最新| 亚洲国产成人久久综合一区77| 模特私拍国产精品久久| 香蕉久久夜色精品国产尤物| 精品久久久久成人码免费动漫 | 国产精品久久国产精麻豆99网站| 97r久久精品国产99国产精| 国产一区二区精品久久凹凸| 一级A毛片免费观看久久精品| 亚洲国产精品无码成人片久久| 免费观看久久精彩视频| 青草久久久国产线免观| 久久久久久国产精品免费无码| 国产一区二区三精品久久久无广告| 久久久久久免费视频| 夜夜亚洲天天久久| 午夜欧美精品久久久久久久 | 久久天天躁狠狠躁夜夜avapp| 99久久国产综合精品麻豆| 亚洲成av人片不卡无码久久| 久久国产精品-久久精品| 国产99久久久国产精品小说| 爱做久久久久久| 久久99精品国产| 久久丫精品国产亚洲av不卡| 久久久人妻精品无码一区| 日本免费久久久久久久网站| 久久99国产综合精品女同| 久久精品人妻中文系列| 婷婷国产天堂久久综合五月| 久久久久亚洲av成人无码电影| 久久99国产精品久久| 久久精品aⅴ无码中文字字幕重口 久久精品a亚洲国产v高清不卡 | 波多野结衣中文字幕久久| 伊人久久大香线蕉AV一区二区| 久久综合狠狠综合久久激情 | 精品免费久久久久国产一区| 久久国产欧美日韩精品| 97精品伊人久久久大香线蕉| 久久久亚洲欧洲日产国码是AV| 久久久久亚洲国产|