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

            国产精品午夜久久| 久久夜色精品国产欧美乱| 久久午夜电影网| 男女久久久国产一区二区三区| 亚洲精品高清国产一线久久| 99久久婷婷免费国产综合精品| 国产亚洲精午夜久久久久久| 色婷婷久久综合中文久久一本| 久久久www免费人成精品| 国产成人精品久久一区二区三区 | 久久精品国产亚洲Aⅴ蜜臀色欲| 精品久久综合1区2区3区激情| 国产A三级久久精品| 97久久精品人人澡人人爽| 久久久久久国产精品无码下载| 69久久精品无码一区二区| 香蕉久久久久久狠狠色| 93精91精品国产综合久久香蕉| 人妻无码精品久久亚瑟影视| 久久久精品免费国产四虎| 亚洲女久久久噜噜噜熟女| 日韩电影久久久被窝网| 久久香蕉综合色一综合色88| 亚洲国产一成人久久精品| 手机看片久久高清国产日韩| 久久国产乱子精品免费女| 中文字幕人妻色偷偷久久| 四虎久久影院| 久久久免费观成人影院| 伊人久久综在合线亚洲2019| 欧美午夜精品久久久久免费视| 欧美久久久久久| 亚洲另类欧美综合久久图片区| 久久久久成人精品无码| 国内精品伊人久久久久网站| 国产99久久久久久免费看| 国产精品久久久久9999| 国产欧美久久一区二区| 国产精品久久影院| 久久九九有精品国产23百花影院| 97久久天天综合色天天综合色hd |