同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