巢穴 - C++博客

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 阅读(154) | 评论 (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 阅读(112) | 评论 (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 阅读(198) | 评论 (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 阅读(130) | 评论 (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 阅读(72) | 评论 (0) | 编辑收藏

摘要: treap..有几个地方写的很尴尬...其实我没写过平衡树...任何的平衡树..所以我就把对于size的维护写错了..orz..然后我又把砍掉一棵子树那部分写错了..我感觉这样砍树是会造成一定的不平衡的..但不平衡会很小.呃..其实也不能这么说..应该说..会造成不平衡..但这个不平衡带给我的负担不会高于我曾经的负担..orz..貌似是这样 #include <iostream&... 阅读全文

posted @ 2009-10-13 11:27 Vincent 阅读(237) | 评论 (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 阅读(95) | 评论 (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 阅读(75) | 评论 (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 阅读(123) | 评论 (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 阅读(477) | 评论 (0) | 编辑收藏

巢穴

My Links

Blog Stats

News

常用链接

留言簿(1)

随笔分类

随笔档案

文章档案

Link

搜索

最新评论

阅读排行榜

评论排行榜

P2352

P2418

P1001

P3349

P3481

NOI2004 cashier

P3020

P3041

P1094

P1258 By kruskal