同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