2009年12月10日 星期四

UVa 820 Internet Bandwidth [Flow]

820    Internet Bandwidth    Accepted    C++    0.056    2009-12-10 07:04:16                            .


第一題Flow  =w=

超基本的Maximum Flow

是說原來大家都寫相鄰矩陣好犯規


相鄰串列有一點不好co  QQ


是說被雙向邊表好久QQ


反正就這樣啦ˊˇˋ



唔code在筆電沒辦法貼...



2009年12月8日 星期二

TIOJ 1094 C.幼稚國王的獎賞 [DP...?]

poao899    5124K    4656MS    G++     0.45K     2009-12-08 23:34:40                      .

過是過了但是這速度...


算了(?


暴力用背包(汗


//****************************

#include<stdio.h>
bool can[1048576];
int last[1048576];
int n,x,max;
void set(int x,int i){
if(!can[x]){
can[x]=1;
last[x]=i;
}
}
main(){
while(scanf("%d",&n),n){
for(int i=0;i<1048576;i++)
can[i] = last[i] = 0;
set(0,max=0);
for(int i=1;i<=n;i++){
scanf("%d",&x);
for(int j=0;j<1048576;j++)
if(can[j] && last[j]!=i){
set(j^x,i);
if((j^x)>max)
max=(j^x);
}
}
printf("%d\n",max);
}
}


TIOJ 1088 [Interactive] 取石頭(二) [Math]

 poao899    4K    184MS    G++     0.28K     2009-12-08 15:46:09                            .

唔神奇xor

不過石頭堆是1~3我把他當0~2炸了n次orz



//*****************************

#include<stdio.h>
#include<1088_stone.h>
int a[3],t,p,x;
main(){
Initialize(a,a+1,a+2);
while(1){
x=a[0]^a[1]^a[2];
for(int i=0;i<3;i++)
if(a[i] && (x^a[i])<a[i]){
Take_Stone(i+1,a[i]-(x^a[i]),&t,&p);
a[i]=x^a[i];
a[t-1]-=p;
break;
}
}
}


TIOJ 1045 A.細菌培養 [discretization]

poao899    1520K    515MS    G++     1.37K     2009-12-08 13:58:43                                               .

離散化暴力。

//如果用二維線段樹複雜度會多lg^2 n耶XD也沒有比較好coˊˋ

你可以假設這個數字小於8*10^18 看成8*10^8是哪招orz


//***************************

//1045

#include<stdio.h>
#include<algorithm>
struct seq{
int ar[440],cnt;
int put(int v){
ar[cnt++]=v;
}
void show(){
for(int i=0;i<cnt;i++)
printf("%d\n",ar[i]);
puts("");
}
int bs(int val){
int l=0,r=cnt-1,mid;
while(l!=r){
mid=(l+r)/2;
if(ar[mid]<val)l=mid+1;
else r=mid;
}
return l;
}
}w,h;
long long val[440][440],n;
int wi[440][2],he[440][2];
main(){
while(scanf("%d",&n),n){
//Initialize
for(int i=0;i<440;i++)
for(int j=0;j<440;j++)
val[i][j]=1;
w.cnt = h.cnt = 0;
//Input
w.put(0);w.put(10000);
h.put(0);h.put(10000);
for(int i=0;i<n;i++){
scanf("%d%d%d%d",&wi[i][0],&he[i][0],&wi[i][1],&he[i][1]);
w.put(wi[i][0]);
w.put(wi[i][1]);
h.put(he[i][0]);
h.put(he[i][1]);
}
std::sort(w.ar,w.ar+w.cnt);
std::sort(h.ar,h.ar+h.cnt);
for(int i=0;i<n;i++){
int wl=w.bs(wi[i][0]),wr=w.bs(wi[i][1]),hl=h.bs(he[i][0]),hr=h.bs(he[i][1]);
for(int j=wl;j<wr;j++)
for(int k=hl;k<hr;k++)
val[j][k]*=2;
}
//w.show();h.show();
long long total=0;
for(int i=0;i<w.cnt-1;i++)
for(int j=0;j<h.cnt-1;j++)
total+=(long long)(w.ar[i+1]-w.ar[i])*(h.ar[j+1]-h.ar[j])*val[i][j];
printf("%I64d\n",total);
}
}

2009年12月7日 星期一

TIOJ 1382 約瑟問題 [segment tree]

poao899    3904K    1718MS    G++     0.80K     2009-12-07 20:09:32                                              .


線段樹越寫越簡陋=口=

是說poloo5582    3072K    1576MS    G++    0.50K     2009-11-10 22:36:00

小鬼學長超強!!


很好奇怎麼用平衡樹來寫

//*******************************

#include<stdio.h>
#define MAX 100010
struct seg{
seg *lch,*rch;
int l,r,rest;
int nth(int);
}s[MAX*2];
int n,pre,now,segCnt;
seg* get(int a,int b){
seg *p =s+segCnt++;
p->l=a;p->r=b;p->rest=b-a+1;
p->lch = p->rch = NULL;
return p;
}
int seg::nth(int i){
if(l==r){rest=0;return l;}
int mid=(l+r)/2,rp;
if(!lch){
lch=get(l,mid);
rch=get(mid+1,r);
}
if(lch->rest < i)
rp=rch->nth(i - lch->rest);
else
rp=lch->nth(i);
if(rp)rest--;
return rp;
}
main(){
while(~scanf("%d",&n)){
//Initialize
segCnt = 0;pre = 1;
get(1,n);
//Input
for(;n;putchar(--n?32:'\n') , pre=now){
scanf("%d",&now);
now = (now+pre-1)%n;
if(!now)now=n;
printf("%d",s->nth(now));
}
}
}


TIOJ 1272 The Agency [segment tree]

poao899    6496K    511MS    G++    2.10K     2009-12-07 18:51:45                                                      .


DFS + segment tree

唔笨了好久不開心~"~

是說沒被捏就不好想~"~


//*****************************
#include<stdio.h>
int stamp[200010],time=1;
int trans[100010][2];
int getint(){
int g=0,c=getchar();
while(c==10||c==32||c==9)c=getchar();
while(c>='0'&&c<='9'){
g=g*10+c-48;
c=getchar();
}
return g;
}
struct node{
node *bro,*son;
void set(node *p){
node *q = son;
son=p;
p->bro = q;
}
}N[100010],*s[100010];
struct segment{
segment *lch,*rch;
int l,r;
int change;
void sneeze(int,int);
int query(int);
}Seg[400080];
segment* get(int l,int r){
static int cnt = 1;
segment* p = Seg+cnt;
cnt++;
p->l = l;p->r = r;
return p;
}
void segment::sneeze(int _l , int _r){
if(l==_l && r==_r){change++;return;}
int mid = (l+r)/2;
if(lch == NULL){
lch = get(l , mid);
rch = get(mid+1 , r);
}
if(_r<=mid){
lch->sneeze(_l , _r);
}else if(_l>mid){
rch->sneeze(_l , _r);
}else{
lch->sneeze(_l , mid);
rch->sneeze(mid+1 , _r);
}
}
int segment::query(int i){
if(!lch)return change;
int mid = (l+r)/2;
if(i>mid)return rch->query(i)+change;
else return lch->query(i)+change;
}
int stack[100010],top=1;
int n,m,a,b;
int main(){
n=getint();
m=getint();
//Input
for(int i=1;i<=n;i++){
a=getint();
while(a--)(N+i)->set(N+getint());
}
//DFS
stack[top]=1;s[top]=(N+1)->son;
while(top){
if(!trans[stack[top]][0]){
stamp[time]=stack[top];
trans[stack[top]][0]=time++;
}
if(s[top]==NULL){
//printf("%d over top=%d\n",stack[top],top);
stamp[time]=stack[top];
trans[stack[top]][1]=time++;
top--;
}
else{
node *p=s[top];
s[top]=s[top]->bro;
top++;
stack[top]=p-N;
s[top]=p->son;
}
}
//Initialize
Seg->l=1;Seg->r=time-1;Seg->change=0;
//Query
while(m--){
a=getint();
b=getint();
if(a){
putchar(((Seg->query(trans[b][0]))&1)+48);
putchar('\n');
}else{
Seg->sneeze(trans[b][0] , trans[b][1]);
}
}
}


2009年12月1日 星期二

TIOJ 1305 啊嘶起啦集合 [segment tree]

poao899    6372K    417MS    G++     2.62K     2009-12-01 17:43:27                           .

離散化 + segment tree


是說是不是用兩個map來離散化頗詭異(?


//***************************

#include<stdio.h>
#include<map>
#include<algorithm>
#define MAX 300000
std::map<int,int> keyToVal;
std::map<int,int> valToKey;
struct segment{
int l,r,sub;
bool inSet;
segment *seg_l,*seg_r;
}Seg[MAX];
segment* set(int l,int r){
static int cnt = 1;
Seg[cnt].l=l;
Seg[cnt].r=r;
return Seg+cnt++;
}
bool insert(segment *p,int i){
int l=p->l,r=p->r;
if(l==r-1){
if(! p->inSet){
p->inSet=1;
p->sub=1;
return true;
}
return false;
}
segment *q;
int mid = ( l + r + 1 )/2;
if(mid > i){
if(p->seg_l==NULL){
q = set(l,mid);
p->seg_l=q;
}
q=p->seg_l;
}
else{
if(p->seg_r==NULL){
q = set(mid,r);
p->seg_r=q;
}
q=p->seg_r;
}
if(insert(q,i)){
p->sub++;
return true;
}
return false;
}
bool remove(segment *p,int i){
int l=p->l,r=p->r;
if(l==r-1){
if(p->inSet){
p->inSet=0;
p->sub=0;
return true;
}
return false;
}
segment *q;
int mid = ( l + r + 1 )/2;
if(mid > i){
if(p->seg_l==NULL)
return false;
q=p->seg_l;
}
else{
if(p->seg_r==NULL)
return false;
q=p->seg_r;
}
if(remove(q,i)){
p->sub--;
return true;
}
return false;
}
int ask(segment *p,int i){
int l=p->l,r=p->r;
if(l==r-1){return l;}
if(p->seg_l!=NULL){
if(p->seg_l->sub>=i){
return ask(p->seg_l,i);
}
}
if(p->seg_r!=NULL){
if(p->seg_l!=NULL){
return ask(p->seg_r,i-p->seg_l->sub);
}
return ask(p->seg_r,i);
}
}
void get(char &c,int &n){
c=getchar();
int s=1;n=0;
char g=getchar();
while((g<'0'||g>'9') && g!='-'){
if(g=='\n')return;
g=getchar();
}
if(g=='-')g=getchar(),s=-1;
while(g>='0'&&g<='9'){
n=n*10+g-48;
g=getchar();
}
n*=s;
}
char com[MAX];
int num[MAX];
int comCnt,keyCnt;
int dsc[MAX];
int kCnt=1;
int main(){
while(1){
get(com[comCnt],num[comCnt]);
if(com[comCnt]=='e')break;
if(com[comCnt]!='a'){
dsc[keyCnt]=num[comCnt];
keyCnt++;
}
comCnt++;
}
std::sort(dsc,dsc+keyCnt);
for(int i=0;i<keyCnt;i++){
if(valToKey[dsc[i]]==0){
valToKey[dsc[i]]=kCnt;
keyToVal[kCnt]=dsc[i];
kCnt++;
}
}
Seg->sub=0;
Seg->l=1;
Seg->r=kCnt;
for(int i=0;i<comCnt;i++){
switch(com[i]){
case'a':
if(num[i]<=0 || num[i]>Seg->sub)
puts("error");
else printf("%d\n" ,keyToVal[ask(Seg,num[i])]);
break;
case'i':
insert (Seg,valToKey[num[i]]);
break;
case'r':
remove(Seg,valToKey[num[i]]);
break;
}
}
}