同SRM386,再度只做了第一題。。RATING保持不變。。算了，我就是弱。
第一題其實(shí)相當(dāng)于把非法的行刪掉并且保持列為1就可以了（去掉一行joker)
我代碼寫的慢啊。。又是低分。。
第二題是個(gè)DP，本來(lái)是不很難想的，感覺(jué)還是時(shí)間太緊，有點(diǎn)緊張了。。
小小菜鳥(niǎo)再度100多分收?qǐng)觥！?nbsp;
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來(lái)自二分查找i前面的最后一個(gè)不相交的線段。
第三題也不是很難，但是，比如說(shuō)我這種第二題都沒(méi)出的人就不用說(shuō)了。。
#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