欧美高清视频一区二区,亚洲亚洲精品三区日韩精品在线视频 ,亚洲男人的天堂在线

P2352

為樹狀樹組量身打造的題...
不過我是線段樹..

#include <iostream>

#include <stdio.h>

using namespace std;

const int MAXN=32005;

struct node

{

int l,r;

int d;

};

node t[MAXN*4];

int ans[MAXN];

void build(int l_,int r_,int p)

{

t[p].l=l_;

t[p].r=r_;

t[p].d=0;

if (l_!=r_)

{

build(l_,(l_+r_)/2,p<<1);

build((l_+r_)/2+1,r_,(p<<1)+1);

}

int find(int r_,int p)

{

if (t[p].r<=r_) return t[p].d;

int l=t[p].l;

int r=t[p].r;

int sum=0;

if (r_<=(l+r)/2) sum+=find(r_,p*2);

else sum+=t[p*2].d+find(r_,p*2+1);

return sum;

}

void insert(int x,int p)

{

int l=t[p].l;

int r=t[p].r;

t[p].d++;

if (l==r) return;

if (x<=(l+r)/2) insert(x,p*2); else insert(x,p*2+1);

}

int n;

int main()

{

memset(ans,0,sizeof(ans));

build(0,MAXN,1);

cin>>n;

for (int i=1;i<=n;i++)

{

int x,y;

scanf("%d %d",&x,&y);

ans[find(x,1)]++;

insert(x,1);

}

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

cout<<ans[i]<<endl;

// system("pause");

return 0;

}

posted @ 2009-10-15 18:08 Vincent 閱讀(178) | 評論 (0) | 編輯收藏

P2418

可用2叉樹.可用快排掃描統計,可直接用map....

#include <map>

#include <string>

#include <stdio.h>

using namespace std;

int main()

{

map < string , int> tree;

char temp[50] ;

string str;

int total=0;

while(gets(temp))

{

str=temp;

tree[aaa]++;

total++;

}

map<string,int>::iterator itr;

for(itr = tree.begin(); itr != tree.end(); itr++)

{

cout<<itr -> first<<" ";

printf("%.4lf\n",100*double(itr -> second)/double(total));

}

return 0;

}

posted @ 2009-10-15 12:07 Vincent 閱讀(136) | 評論 (0) | 編輯收藏

P1001

orz.啊..orz..
就是一個普通的高精度..注意下格式的細節就可以..
- -我用的dev c++..忘寫#include <string>編譯過了..
然后提交的時候不知道..就編譯錯誤...
然后把重載運算符改成了普通方法..
然后把class改成了struct..
總只有點暈..
后來才發現是少寫了#include......

#include <iostream>

#include <string>

#include <math.h>

using namespace std;

const int MAXN=10000;

struct Decimal

{

private:

int len;//總長度

int point_pos;//小數點位置

int number[MAXN];//具體數

public:

Decimal();

Decimal(string);

void print();

Decimal ch(Decimal);

};

Decimal::Decimal()

{

}

Decimal Decimal::ch(Decimal x)

{

int num[MAXN],n_len=0;

memset(num,0,sizeof(num));

n_len=x.len+Decimal::len;

for (int i=1;i<=x.len;i++)

{

for (int j=1;j<=Decimal::len;j++)

{

num[i+j-1]+=x.number[i]*Decimal::number[j];

num[i+j]+=num[i+j-1]/10;

num[i+j-1]%=10;

}

int point_pos=x.point_pos+Decimal::point_pos;

if (num[n_len]==0) n_len--;

Decimal result;

result.len=n_len;

result.point_pos=point_pos;

for (int i=1;i<=n_len;i++)

result.number[i]=num[i];

return result;

}

Decimal::Decimal(string x)

{

int i=x.length();

int sign=0;

for (int j=0;j<x.length();j++)

if (x[j]=='.') sign=1;

int point_pos=0;

int len=i-sign;

i=len;

for (int j=0;j<x.length();j++)

{

if (x[j]=='.') point_pos=i;

if (x[j]<='9'&&x[j]>='0')

{

number[i--]=x[j]-48;

//cout<<number[i]<<endl;

}

Decimal::point_pos=point_pos;

Decimal::len=len;

}

void Decimal::print()

{

int pe=1;

while (number[pe]==0&&pe<=point_pos) pe++;

int p=len;

while (number[p]==0&&p>point_pos&&point_pos>pe) p--;

//cout<<pe<<endl;

for (int i=p;i>=pe;i--)

{

if (point_pos==i) cout<<".";

cout<<number[i];

}

cout<<endl;

}

int main()

{

string x;

int n;

while(cin>>x>>n)

{

Decimal d(x);

// d.print();

Decimal result("1.0");

// result.print();

for (int i=1;i<=n;i++)

{

result=result.ch(d);

}

result.print();

}

system("pause");

return 0;

}

posted @ 2009-10-14 22:34 Vincent 閱讀(224) | 評論 (0) | 編輯收藏

P3349

hash..
tle了2次都沒有想起來是我用了輸入輸出流的原因..
后來看了討論才想起來...
呃.這題代碼寫的有點orz

#include <iostream>

#include <stdio.h>

using namespace std;

const int MAXN=100000;

const long mod=999991;

int n;

long hash[mod];

long c[7];

int len=-1;

struct node

{

long c[7];

long son;

};

bool isFind=false;

node list[MAXN];

int p[13];

void find_node(long x)

{

for (int i=1;i<=6;i++)

{

int count=0;

for (int j=i;j<=i+6-1;j++)

{

if (p[j]==list[x].c[j-i+1]) count++;

}

if (count==6)

{

isFind=true;

return;

}

count=0;

for (int j=i;j<=i+6-1;j++)

{

if (p[j]==list[x].c[6-(j-i+1)+1]) count++;

}

if (count==6)

{

isFind=true;

return;

}

if (list[x].son!=-1) find_node(list[x].son);

else

{

len++;

list[x].son=len;

list[len].son=-1;

for (int i=1;i<=6;i++)

{

list[len].c[i]=c[i];

}

return;

}

void find(long x)

{

if (hash[x]==-1)

{

len++;

hash[x]=len;

list[len].son=-1;

for (int i=1;i<=6;i++)

{

list[len].c[i]=c[i];

}

return;

}

// cout<<x<<endl;

for (int i=1;i<=6;i++)

p[i]=c[i];

for (int i=7;i<=12;i++)

p[i]=c[i-6];

find_node(hash[x]);

}

int main()

{

scanf("%ld",&n);

for (int i=0;i<mod;i++)

hash[i]=-1;

// memset(hash,-1,sizeof(hash));

for (int i=1;i<=n;i++)

{

long ans=0;

for (int j=1;j<=6;j++)

{

scanf("%ld",c+j);

ans+=c[j];

}

long x=ans%mod;

// cout<<x<<endl;

find(x);

}

if (isFind) cout<<"Twin snowflakes found."<<endl;

else

cout<<"No two snowflakes are alike."<<endl;

//system("pause");

return 0;

}

posted @ 2009-10-13 21:28 Vincent 閱讀(155) | 評論 (0) | 編輯收藏

P3481

摘要: 裸treap...學會了刪除..orz.. #include <iostream>//#include <fstream>using namespace std;//ifstream fin("t3481.in");const int MAXN=100000;const int IN... 閱讀全文

posted @ 2009-10-13 16:23 Vincent 閱讀(95) | 評論 (0) | 編輯收藏

摘要: treap..有幾個地方寫的很尷尬...其實我沒寫過平衡樹...任何的平衡樹..所以我就把對于size的維護寫錯了..orz..然后我又把砍掉一棵子樹那部分寫錯了..我感覺這樣砍樹是會造成一定的不平衡的..但不平衡會很小.呃..其實也不能這么說..應該說..會造成不平衡..但這個不平衡帶給我的負擔不會高于我曾經的負擔..orz..貌似是這樣 #include <iostream&... 閱讀全文

posted @ 2009-10-13 11:27 Vincent 閱讀(263) | 評論 (0) | 編輯收藏

P3020

2分圖
構圖
兩個集合是一樣的,都是所有的*號
如果某兩個*之間挨著,就連線
求最大匹配
可以輕易得出這個最大匹配把每個*都求了2遍
因此除以2,再加上未匹配的*,得解..
難點就是構圖..
事實上匹配,網絡流等的難點也就是構圖

#include <iostream>

//#include <fstream>

using namespace std;

//ifstream fin("t3020.in");

struct node

{

int x,y;

};

const int MAXN=401;

node edge[MAXN];

bool connect[MAXN][MAXN];

bool hash[MAXN];

int v[MAXN];

int n;

int h,w;

int len;

bool find(int x)

{

for (int i=1;i<=len;i++)

{

if (!connect[x][i]) continue;

if (!hash[i])

{

hash[i]=true;

if (v[i]==0||find(v[i]))

{

v[i]=x;

return true;

}

return false;

}

int main()

{

cin>>n;

while(n--)

{

cin>>h>>w;

len=0;

for (int i=1;i<=h;i++)

for (int j=1;j<=w;j++)

{

char ch;

cin>>ch;

if ('*'==ch)

{

len++;

edge[len].x=i;

edge[len].y=j;

}

//init

memset(connect,0,sizeof(connect));

for (int i=1;i<=len;i++)

for (int j=1;j<=len;j++)

{

if (i==j) continue;

if (1==abs(edge[i].x-edge[j].x)+abs(edge[i].y-edge[j].y))

connect[i][j]=true;

}

//

memset(v,0,sizeof(v));

int answer=0,ans=0;

for (int i=1;i<=len;i++)

{

memset(hash,0,sizeof(hash));

if (find(i)) answer++;

else

ans++;

}

cout<<answer/2+ans<<endl;

// system("pause");

}

return 0;

}

posted @ 2009-10-08 11:58 Vincent 閱讀(120) | 評論 (0) | 編輯收藏

P3041

2分圖/匈牙利
第一遍寫疵了..

#include <iostream>

#include <fstream>

using namespace std;

const int MAXN=501;

int n,k;

bool edge[MAXN][MAXN];

bool hash[MAXN];

int v[MAXN];

bool find(int x)

{

for (int j=1;j<=n;j++)

{

if (!edge[x][j]) continue;

if (!hash[j])

{

hash[j]=true;

if (v[j]==0||find(v[j]))

{

v[j]=x;

return true;

}

return false;

}

int main()

{

memset(edge,0,sizeof(edge));

cin>>n>>k;

for (int i=1;i<=k;i++)

{

int x,y;

cin>>x>>y;

edge[x][y]=true;

}

int count=0;

for (int i=1;i<=n;i++)

{

memset(hash,0,sizeof(hash));

if (find(i)) count++;

}

cout<<count<<endl;

// system("pause");

return 0;

}

posted @ 2009-10-07 19:21 Vincent 閱讀(95) | 評論 (0) | 編輯收藏

P1094

拓撲排序..
這個真是WA了n多次..orz..
總之就是有很多細節..因為結果的可能性太多..而樣例實在是只給了太少的可能性- -..

#include <iostream>

#include <queue>

#include <string>

using namespace std;

int n,m;

const int MAXN=27;

bool edge[MAXN][MAXN];

int d[MAXN];

int state;

void jude(int ix)

{

state=0;

string str="";

int count=0;

queue<int> q;

int u[MAXN];

for (int i=1;i<=n;i++)

{

u[i]=d[i];

// cout<<u[i]<<endl;

if (0==d[i]) q.push(i);

}

if (q.size()>1) {state=3;}

while(q.size()>0)

{

int v=q.front();

int c_ount=0;

for (int i=1;i<=n;i++)

if (edge[i][v])

{

u[i]--;

if (0==u[i]) {c_ount++;q.push(i);}

}

if (c_ount>1) {state=3;}

q.pop();count++;str=char(v+64)+str;

}

// cout<<count<<" "<<n<<endl;

if (count<n)

{

cout<<"Inconsistency found after "<<ix<<" relations."<<endl;

state=2;return;

}

if (state==3) return;

cout<<"Sorted sequence determined after "<<ix<<" relations: ";

cout<<str<<"."<<endl;

state=1;return;

}

int main()

{

while(1)

{

memset(edge,0,sizeof(edge));

memset(d,0,sizeof(d));

state=0;

cin>>n>>m;

if (0==n&&0==m) break;

char str[3];

for (int i=1;i<=m;i++)

{

cin>>str;

if (state==1) continue;

if (state==2) continue;

int x=int(str[0])-64;

int y=int(str[2])-64;

if (edge[x][y]) continue;

d[x]=d[x]+1;

edge[x][y]=true;

jude(i);

}

if (state==3) cout<<"Sorted sequence cannot be determined."<<endl;

}

return 0;

}

posted @ 2009-10-07 18:25 Vincent 閱讀(151) | 評論 (0) | 編輯收藏

P1258 By kruskal

kruskal..

/*

Kruskal

*/

#include <iostream>

using namespace std;

const int MAXN=101;

const int INF=0x7fffffff;

int n;

struct node

{

int x,y;

int value;

};

node edge[MAXN*MAXN+1];

bool hash[MAXN];

int dist[MAXN];

int father[MAXN];

int len;

void sort(int l,int r)

{

int ll=l,rr=r,mid=edge[(l+r)/2].value;

while(ll<=rr)

{

while (edge[ll].value<mid) ll++;

while (edge[rr].value>mid) rr--;

if (ll<=rr)

{

swap(edge[ll],edge[rr]);

ll++;

rr--;

}

if (ll<r) sort(ll,r);

if (rr>l) sort(l,rr);

}

int getFather(int x)

{

if (x==father[x]) return x;

father[x]=getFather(father[x]);

x=father[x];

return x;

}

void kruskal()

{

sort(1,len);

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

father[i]=i;

int ans=0;

for (int i=1;i<=len;i++)

{

int fx=getFather(edge[i].x);

int fy=getFather(edge[i].y);

if (fx!=fy)

{

ans+=edge[i].value;

father[fx]=fy;

}

cout<<ans<<endl;

}

int main()

{

while(cin>>n)

{

len=0;

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

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

{

int x;

cin>>x;

if (i==j) continue;

node p;

p.x=i;p.y=j;p.value=x;

edge[++len]=p;

}

kruskal();

}

return 0;

}

posted @ 2009-10-07 15:26 Vincent 閱讀(495) | 評論 (0) | 編輯收藏

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

巢穴

My Links

Blog Stats

News

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

文章檔案

Link

搜索

最新評論

閱讀排行榜

評論排行榜

P2352

P2418

P1001

P3349

P3481

NOI2004 cashier

P3020

P3041

P1094

P1258 By kruskal