藍雪的Online Judge日誌

2014年8月19日星期二

POJ 2411 Mondriaan's Dream

[DP]
JzDP

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#define LL long long int
using namespace std;
bool checkeven1(int a){
int c = 0;
while(a){
if(a&1)
c = 1-c;
else
if(c) return false;
a>>=1;
}
if(c) return false;
return true;
}
int main()
{
int h, w;
while(scanf("%d %d", &h, &w) == 2){
if((h == 0) and (w == 0)) break;
LL dp[13][1<<12];
for(int lx = 0;lx < (1<<w);lx++)
dp[0][lx] = (LL)checkeven1(lx);
for(int lh = 1;lh <= h;lh++){
for(int lx = 0;lx < (1<<w);lx++){
dp[lh][lx] = 0;
for(int ly = 0;ly < (1<<w);ly++)
if((lx|ly) == (1<<w)-1 and checkeven1(lx&ly))
dp[lh][lx] += dp[lh-1][ly];
}
}
printf("%lld\n", dp[h][0]);
}
return 0;
}

POJ 3254 Corn Fields

http://poj.org/problem?id=3254
[DP]

覺得難過QQ

只好來寫水題QQ

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#define MOD 100000000
using namespace std;
int main()
{
int M, N;scanf("%d %d", &M, &N);
int line[100];
for(int lx = 0;lx < M;lx++){
line[lx] = 0;
for(int ly = 0;ly < N;ly++){
int inp;scanf("%d", &inp);
line[lx] = line[lx]*2 + inp;
}
}
int dp[14][1<<12];
for(int lx = 0;lx < (1<<N);lx++)
dp[0][lx] = ((lx|line[0])^line[0]) == 0 and ((lx>>1)&(lx)) == 0;
for(int lm = 1;lm < M;lm++){
for(int lx = 0;lx < (1<<N);lx++)
if(((lx|line[lm])^line[lm]) == 0 and ((lx>>1)&(lx)) == 0)
for(int ly = 0;ly < (1<<N);ly++){
dp[lm][lx] += dp[lm-1][ly]*((lx&ly) == 0);
dp[lm][lx] %= MOD;
}
}
int cnt = 0;
for(int lx = 0;lx < (1<<N);lx++)
cnt = (cnt +dp[M-1][lx])%MOD;
printf("%d\n", cnt);
return 0;
}

2014年8月16日星期六

SPOJ Count on a tree 2

終於把這神奇的題目搞出來惹(汗

2014-08-16 17:03:17

accepted

73M

C++

4.3.2

四千大大神威<(_ _)>

經四千大大指導>w<

終於突破各種WA

超級有成就感的><

總之這題就是

把樹攤開後，把每個區間射到一個平面上，然後用平方分解的方式遍歷，可以保證複雜度在O(n*q^0.5)

是說還有看到強制在線的題目QQ 好可怕><

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cstring>

#include<vector>

#include<utility>

#include<map>

#include<set>

#include<cmath>

#define NN 40005

#define QQ 100005

using namespace std;

void assertTLE(bool check){

if(check == false)

while(1);

return;

}

void assertRE(bool check){

if(check == false)

printf("%d\n", 1/0);

return;

}

const int INFVAL = 100000000;

class RMQ{

public:

RMQ(){};

void setup(int _n, int *a){

all = _n;

/*printf("\nRMQ SETUP:\n");

for(int lx = 0;lx < _n;lx++)

printf("%d ", a[lx]);

puts("");*/

for(int lx = 0;lx < _n;lx++) value[lx] = a[lx];

for(int lx = 0;lx < _n;lx++) sp[lx][0] = lx;

for(int lx = 1;(1<<lx) < (_n+2);lx++){

for(int ly = 0;ly+(1<<lx)-1 < _n;ly++){

int m = ly + (1<<(lx-1));

sp[ly][lx] = minindex(sp[ly][lx-1], sp[m][lx-1]);

}

return;

}

int ask(int a, int b){

if(b < a) a^=b^=a^=b;

//assertRE(a<=b);

int k = (int)(log2(b-a+1));

//assertRE(a+(1<<k) - 1 >= b - (1<<k));

assertRE(a+(1<<k) - 1 <= b);

return minindex(sp[a][k], sp[b-(1<<k)+1][k]);

}

private:

int sp[8*NN][50];

int value[8*NN];

int all;

int minindex(int ind1, int ind2){

return (value[ind1]<value[ind2])? ind1: ind2;

}

};

int an[NN];

int tree[NN*2];

int tlca[NN*8];

int thei[NN*8];

int nodhei[NN];

int n, sqrtn; int tlcalen = 0;

pair<int,int> nodmap[NN];

int lcamap[NN];

typedef struct _query{ int x, y; int id;int ans;int na, nb;}query;

//void printq(query a){printf("q: nod=%d->%d rang=%d->%d\n",a.na, a.nb, a.x, a.y);return;}

query qs[QQ];

bool operator<(query a, query b){

if(a.x/sqrtn != b.x/sqrtn) return a.x/sqrtn < b.x/sqrtn;

return a.y < b.y;

}

struct _cmp_id{bool operator()(query a, query b){return a.id<b.id;}}cmp_id;

vector<int> link[NN];

RMQ LCA;

int _dfscnt = 0;

void dfs(int fat, int chd){

//printf("%d ", chd+1);

nodmap[chd].first = _dfscnt;

tree[_dfscnt++] = chd;

lcamap[chd] = tlcalen;

tlca[tlcalen++] = chd;

for(int lx = 0;lx < link[chd].size();lx++){

if(fat == link[chd][lx]) continue;

nodhei[link[chd][lx]] = nodhei[chd]+1;

dfs(chd, link[chd][lx]);

tlca[tlcalen++] = chd;

//printf("%d ", chd+1);

}

nodmap[chd].second = _dfscnt;

tree[_dfscnt++] = chd;

//printf("%d ", chd);

return;

}

//set<int>nodvis;

//map<int, int>valcnt;

bool nodvis[NN];

int valcnt[NN], valsz;

int autolca = -1;

int segleft = 0, segright = 0;

void init(int _n){

valsz = 0;

for(int lx = 0;lx < NN;lx++){

nodvis[lx] = false;

valcnt[lx] = 0;

}

return;

}

void writelca(int anc){ autolca = anc; return;}

void write(int a){

//printf("visit %d, val = %d\n", a, an[a]);

//assertRE(an[a]<=40000);

if(nodvis[a] == false){

nodvis[a] = true;

valcnt[an[a]]++;

if(valcnt[an[a]] == 1) valsz++;

}else{

nodvis[a] = false;

assertRE(valcnt[an[a]] > 0);

valcnt[an[a]]--;

if(valcnt[an[a]] == 0){

valsz--;

}

return;

}

int read(){

/*printf("read seg => lca = %d\n", autolca);

for(int lx = 0;lx < 10;lx++)

if(valcnt[lx] != 0)

printf("getval = %d\t", lx);

printf("\n");*/

int _sz = valsz;

if(autolca != -1)

_sz += valcnt[an[autolca]]==0;

return _sz;

}

int main()

{

int n, m;scanf("%d %d", &n, &m);

map<int, int> jizz;

for(int lx = 0;lx < n;lx++)

scanf("%d", an+lx);

// jizzan

for(int lx = 0;lx < n;lx++){

if(jizz.count(an[lx]) == 0){

int gtsz = jizz.size();

jizz[an[lx]] = gtsz;

an[lx] = gtsz;

}else

an[lx] = jizz[an[lx]];

//printf("%d ", an[lx]);

}

//printf("\n");

for(int lx = 0;lx < n-1;lx++){

int a,b;scanf("%d %d", &a,&b);

link[a-1].push_back(b-1);

link[b-1].push_back(a-1);

}

_dfscnt = 0;

nodhei[0] = 0;

dfs(-1, 0);

for(int lx = 0;lx < tlcalen;lx++)

thei[lx] = nodhei[tlca[lx]];

LCA.setup(tlcalen, thei);

/*printf("\npair result:\n");

for(int lx = 0;lx < n;lx++)

printf("%d -> %d, %d\n", lx, nodmap[lx].first, nodmap[lx].second);*/

for(int lx = 0;lx < m;lx++){

int na, nb;scanf("%d %d", &na, &nb); na--; nb--;

qs[lx].id = lx; qs[lx].na = na, qs[lx].nb = nb;

//printf("ask %d,%d -> %d,%d\n", nodmap[na].first, nodmap[na].second, nodmap[nb].first, nodmap[nb].second);

if((nodmap[na].first < nodmap[nb].first) and (nodmap[nb].second < nodmap[na].second)){

qs[lx].x = nodmap[na].first, qs[lx].y = nodmap[nb].first;

//printf("trig1\n");

}else if((nodmap[nb].first < nodmap[na].first) and (nodmap[na].second < nodmap[nb].second)){

qs[lx].x = nodmap[nb].first, qs[lx].y = nodmap[na].first;

//printf("trig2\n");

}else if(nodmap[na].second < nodmap[nb].first){

qs[lx].x = nodmap[na].second, qs[lx].y = nodmap[nb].first;

//printf("trig3\n");

}else if(nodmap[nb].second < nodmap[na].first){

qs[lx].x = nodmap[nb].second, qs[lx].y = nodmap[na].first;

//printf("trig4\n");

}else if(na == nb){

qs[lx].x = nodmap[nb].first, qs[lx].y = nodmap[nb].second;

}

//assertTLE(m >= 1);

sqrtn = (int)(n/sqrt(m));

sort(qs, qs+m);

init(n);

/*for(int lx = 0;lx < m;lx++)

printq(qs[lx]);*/

for(int lx = qs[0].x;lx <= qs[0].y;lx++)

write(tree[lx]);

writelca(tlca[LCA.ask(lcamap[qs[0].na], lcamap[qs[0].nb])]);

segleft = qs[0].x, segright = qs[0].y;

qs[0].ans = read();

for(int lxx = 1;lxx < m;lxx++){

if(segleft < qs[lxx].x){

for(int lx = segleft;lx <= qs[lxx].x-1;lx++){

write(tree[lx]);

}

}else if(segleft > qs[lxx].x){

for(int lx = segleft-1;lx >= qs[lxx].x;lx--){

write(tree[lx]);

}

if(segright < qs[lxx].y){

for(int lx = segright+1;lx <= qs[lxx].y;lx++){

write(tree[lx]);

}

}else if(segright > qs[lxx].y){

for(int lx = segright;lx >= qs[lxx].y+1;lx--){

write(tree[lx]);

}

segleft = qs[lxx].x, segright = qs[lxx].y;

writelca(tlca[LCA.ask(lcamap[qs[lxx].na], lcamap[qs[lxx].nb])]);

qs[lxx].ans = read();

}

sort(qs, qs+m, cmp_id);

for(int lx = 0;lx < m;lx++){

//printq(qs[lx]);

printf("%d\n", qs[lx].ans);

}

return 0;

}

testdata:

1 3 4 -1 2 1 2 9

1 2 2 3 3 4

1 5 5 6

5 7 7 8

2 6

3 6

1 8

3 7

1 6

2014年8月13日星期三

UVA 11039

greedy
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
int an[500005];
int __abs(int x){
if(x > 0) return x;
return -x;
}
struct cp{
bool operator()(int a, int b){
return __abs(a) < __abs(b);
}
}CP;
int main(){
int T;scanf("%d", &T);
while(T-->0){
int n;scanf("%d", &n);
for(int lx = 0;lx < n;lx++)
scanf("%d", an+lx);
sort(an, an + n, CP);
int neg = 0, pos = 0;
// int neg_ind = -1, pos_ind = -1;
for(int lx =0;lx < n;lx++){
if(an[lx] < 0) pos = max(pos, neg+1);
if(an[lx] > 0) neg = max(neg, pos+1);
}
printf("%d\n", max(neg, pos));
}
return 0;
}

2014年8月12日星期二

kth number RMQ revisit

http://poj.org/problem?id=2104

O((N+M)logN)

用ㄎㄠ線段樹:3

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#define min(x,y) (((x)>(y)) ? (y):(x))
#define max(x,y) (((x)>(y)) ? (x):(y))
#define NN 100015
using namespace std;
typedef struct _node{ int left_ind; int right_ind; int count; }node;
int an[NN];int n;
node tree[NN*40]; /** 2N + NlgN **/
int sz =0;
int tline[NN];
int tline_sz;
int cownod[NN];
int _step = 0;
void test_step(){_step++; if(_step/3000 >= 1000) printf("%d\n", 1/0);}
void _assert(bool t){if(t == false)printf("%d", 1/0); return;}
inline int make(int l, int r){
test_step();
int prc_ind = sz; sz++;
tree[prc_ind].count = 0;
tree[prc_ind].left_ind = -9999999, tree[prc_ind].right_ind =-9999999;
if(l >= r) return prc_ind;
int mid = (l+r)>>1;
tree[prc_ind].left_ind = make(l, mid);
tree[prc_ind].right_ind = make(mid+1, r);
return prc_ind;
}
int jizz(int rt_ind, int jiz_ind, int l, int r){
_assert(rt_ind>=0);
test_step();
int newrt_ind = sz; sz++;
tree[newrt_ind] = tree[rt_ind];
tree[newrt_ind].count++;
if(l == r) return newrt_ind;
_assert(jiz_ind >= l and jiz_ind <= r);
int mid = (l+r)>>1;
// left = l ~ mid, right = mid+1 ~ r
if(jiz_ind <= mid){ //left
int newleft_ind = jizz(tree[rt_ind].left_ind, jiz_ind, l, mid);
tree[newrt_ind].left_ind = newleft_ind;
}else{
int newright_ind = jizz(tree[rt_ind].right_ind, jiz_ind, mid+1, r);
tree[newrt_ind].right_ind = newright_ind;
}
return newrt_ind;
}

inline int read(int lrt, int rrt, int k){
//printf("read [%d~%d]\n", tleft, tright);
int tleft = 0, tright = tline_sz+1;
while(tleft < tright){
test_step();
int tmid = (tleft+tright)>>1;
int leftcnt = tree[tree[rrt].left_ind].count - tree[tree[lrt].left_ind].count;
if(k <= leftcnt){
lrt = tree[lrt].left_ind, rrt = tree[rrt].left_ind;
tright = tmid;
}else{
lrt = tree[lrt].right_ind, rrt = tree[rrt].right_ind;
tleft = tmid+1;
k -= leftcnt;
}
}
return tleft;
}
void printtree(int rt){
if(tree[rt].left_ind == -1){
printf("%d ", tree[rt].count);
return;
}
//printf(" %d:{", tree[rt].count);
printtree(tree[rt].left_ind);
printtree(tree[rt].right_ind);
//printf("}");
}
int main()
{
int m;scanf("%d %d", &n, &m);
for(int lx = 0;lx < n;lx++) scanf("%d", an+lx), tline[lx] = an[lx];
sort(tline, tline+n);
tline_sz = n;
//printf("%d\n", tline_sz);
map<int, int> arctline;
_assert(tline_sz == n);
cownod[0] = make(0, tline_sz+1);
for(int lx = 0;lx < n;lx++){
int pos = lower_bound(tline,tline+n,an[lx]) - tline;
cownod[1+lx] = jizz(cownod[lx], pos, 0, tline_sz+1);
}
/*for(int lx = 0;lx <= n;lx++){
printtree(cownod[lx]);puts("");
}*/
while(m-->0){
int ll, rr, k;scanf("%d %d %d", &ll, &rr, &k);
printf("%d\n", tline[read(cownod[ll-1], cownod[rr], k)]);
}
return 0;
}

2014年8月5日星期二

POJ 2104 kth-number

http://poj.org/problem?id=2104

第一次寫.....
O(N(lgN)^2 + M(lgN)^3)

過惹，沒被Tㄟ，好開心~

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<cmath>
//#define min(x,y) (((x)>(y)) ? (y):(x))
//#define max(x,y) (((x)>(y)) ? (x):(y))
#define N 100005
#define INF (1000*1000*1000 + 1)
using namespace std;
vector<int> tree[4*N];
int nodecnt[4*N];
int base;
int n;
int an[N];
void setup(){
base = (1<<(int)(ceil(log2(n+2)))) - 1;
for(int lx = 0;lx < n;lx++){
tree[base + 1 + lx + 1].push_back(an[lx]);
nodecnt[base + 1 + lx + 1] = 1;
}
tree[base + 1].push_back(INF);
nodecnt[base + 1] = 0;
for(int lx = n;lx <= base;lx++){
tree[base + 1 + lx + 1].push_back(INF);
nodecnt[base + 1 + lx + 1] = 0;
}
for(int lx = base;lx;lx--){
for(int ll = 0;ll < tree[2*lx].size();ll++)
tree[lx].push_back(tree[2*lx][ll]);
for(int ll = 0;ll < tree[2*lx+1].size();ll++)
tree[lx].push_back(tree[2*lx+1][ll]);
nodecnt[lx] = nodecnt[2*lx] + nodecnt[2*lx+1];
sort(tree[lx].begin(), tree[lx].end());
/*printf("node %d:\n", lx);
for(int ll = 0;ll < tree[lx].size();ll++)
if(tree[lx][ll] >= INF)
printf("inf ");
else
printf("%03d ", tree[lx][ll]);
printf("\n");*/
}
return;
}
int query(int a, int b, int k){
a++, b++;
int seg[100], segcnt = 0;
for(a+=base-1,b+=base+1; a^b^1;a>>=1, b>>=1){
if(~a&1){
seg[segcnt] = a^1;
segcnt++;
//printf("get seg: %d\n", a^1);
}
if(b&1){
seg[segcnt] = b^1;
segcnt++;
//printf("get seg: %d\n", b^1);
}
}
int max_ele = -INF, min_ele = INF;
for(int lx = 0;lx < segcnt;lx++){
max_ele = max(max_ele, tree[seg[lx]][0]);
max_ele = max(max_ele, tree[seg[lx]][tree[seg[lx]].size()-1]);
min_ele = min(min_ele, tree[seg[lx]][0]);
min_ele = min(min_ele, tree[seg[lx]][tree[seg[lx]].size()-1]);
}
while(min_ele < max_ele){
//printf("bsh %d -> %d\n", min_ele, max_ele);
int test = (min_ele + max_ele)/2;
int check = 1;
bool found = false;
for(int lx = 0;lx < segcnt;lx++){
int getindex = lower_bound(tree[seg[lx]].begin(), tree[seg[lx]].end(), test)-tree[seg[lx]].begin();
check += getindex;
found = found or (tree[seg[lx]][getindex] == test);
}
if(check == k){
if(found)
return test;
else{
min_ele = test+1;
//printf("giz\n");
}
}else if(check > k) max_ele = test - 1;
else if(check < k) min_ele = test + 1;
}
return min_ele;
}
int main()
{
int m;scanf("%d %d", &n, &m);
for(int lx = 0;lx < n;lx++)
scanf("%d", an+lx);
setup();
while(m--){
int a, b, k;scanf("%d %d %d", &a, &b, &k);
printf("%d\n", query(a, b, k));
}
return 0;
}

2014年8月3日星期日

UVA p920 Sunny Mountain

掃描線%%%

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<cmath>
#define min(x,y) (((x)>(y)) ? (y):(x))
#define max(x,y) (((x)>(y)) ? (x):(y))
using namespace std;
struct point{ int x, y;};
struct ccc{
bool operator()(point a, point b){return a.x < b.x;
}
}cccc;
int main()
{
int T;scanf("%d", &T);
while(T-->0){
int n; scanf("%d", &n);
point ps[200];
for(int lx = 0;lx < n;lx++)
scanf("%d %d", &ps[lx].x, &ps[lx].y);
sort(ps, ps+n , cccc);
double sum = 0;
double px = ps[n-1].x, py = ps[n-1].y;
for(int lx = n-2;lx >= 0;lx--){
if(ps[lx].y > py){
sum += (ps[lx].y-py) * sqrt( (ps[lx].x - ps[lx+1].x)*(ps[lx].x - ps[lx+1].x) +
(ps[lx].y - ps[lx+1].y)*(ps[lx].y - ps[lx+1].y))/(ps[lx].y-ps[lx+1].y);
py = ps[lx].y;
px = ps[lx].x;
}
}
printf("%.2f\n", sum);
}
return 0;
}

訂閱：文章 (Atom)

2014年8月19日 星期二

2014年8月16日 星期六

2014年8月13日 星期三

2014年8月12日 星期二

2014年8月5日 星期二

2014年8月3日 星期日

2014年8月19日星期二

2014年8月16日星期六

2014年8月13日星期三

2014年8月12日星期二

2014年8月5日星期二

2014年8月3日星期日