都写了三份了，实在不想加重以前随笔的负担
所以只好另起炉灶。
F：Face Formations这道题据说是组合数学的题，但是我是用动态规划作的
上windows实在听不进课，就在草稿纸上胡写乱画，莫名其妙的模拟出来了
主要我是要填表，状态方程，我不知道该怎么写，我模拟下过程好了：
4
1 2 4 7
1
37 37 22 7
2 0 15 15 6
3 0 0 9 5
4 0 0 4 4
5 0 0 0 3
6 0 0 0 2
7 0 0 0 1
ps: 这个表我的填表过程是从下至上，从右至左
结果是在[1][1]的位置上，我代码实现的时候只开了一个数组，因为并不需要把整个表都存下来
以下是我的代码：
#include<iostream>
#include<algorithm>
using namespace std;
#define Max 35
__int64 num[Max],dice[Max];
bool cmp(__int64 a,__int64 b)
{
return a<b;
}
void solve(int n)
{
__int64 i,j;
for(i=1;i<=dice[n];i++)
num[i]=1;
for(i=n;i>=1;i--)
for(j=dice[i]-1;j>=0;j--)
num[j]+=num[j+1];
}
int main()
{
int n,i;
while(scanf("%d",&n)!=EOF&&n){
memset(dice,0,sizeof(dice));
memset(num,0,sizeof(num));
for(i=1;i<=n;i++)
scanf("%I64d",&dice[i]);
sort(dice+1,dice+n+1,cmp);
solve(n);
printf("%I64d\n",num[1]);
}
return 0;
}
ps:这道题要Long long
posted @
2008-04-11 00:06 zoyi 阅读(296) |
评论 (3) |
编辑 收藏2008年4月10日23:52:47
第一个问题：
由平面中的n条直线确定的最大区域数Ln
L0=1；
Ln=Ln-1+n(n>0);
Ln=1+n*(n+1)/2;
第二个问题：
是平面直线的变形问题，用弯曲的线来代替直线，每一个弯曲线含有一个“锯齿形的转角”，同样确定平面区域的最大个数Zn
（我们把一条弯曲折线抽象为两条，但是合并了某些区域）
Zn=L2n-2*n=2*n*n-n+1;(n>=0);
第三个问题：
就是一下这个问题：
count the regions
若当前有n-1条边，那么在往里面加一条边，这条新加的边最多和以前的边有9*(n-1)个交点，
那么会添加 9*（n-1）+1个面
这条规律对于上面两种也是用，加x个点，那么就会添加x+1个面
那么总结下来 Xn=Xn-1+9*(n-1)+1
即Xn=(9/2)*n*n-(7/2)*n+1;
以下是我的代码：
#include<stdio.h>
int main()
{
long long n;
long long ans;
while(scanf("%lld",&n)!=EOF){
ans=9*n*n-7*n+2;
ans/=2;
printf("%lld\n",ans);
}
return 0;
}
posted @
2008-04-10 23:36 zoyi 阅读(295) |
评论 (2) |
编辑 收藏
摘要: 大家有好的代码请发我邮箱：zhangjia888334@sohu.com 今天就作了广搜三道题，做个小节。首先要纠正脑子里的一个错误观念，以前的我的广搜模式就是开个队列，走过的点不能走，队列的类型我还必定是用结构体来做结构体里放个x,y,n，x-->横坐标，y-->纵坐标，n-->步数再来几个标准的二维数组，map[Maxh][Maxw]-->描述地图,visit...
阅读全文
posted @
2008-04-10 00:57 zoyi 阅读(340) |
评论 (0) |
编辑 收藏这道题是直接拿前几天写得模版改的；做了几个修改
首先删掉了search，这道题的确不需要，本来没删，代码实在太长,逼得我没办法
第二个，把trie中num[]的意思改掉了，num[]现在存的是字符串在一个数组的标记，
相当于map的实现，通过这样我把一个字符串和一个标号对应上了，方便了并查集的操作
果然很久没碰并查集了，一写就出问题，
主要是我union_set是居然忘了要先find_set一下，这样写针对下面这组数据就会出现问题：
a b
b a
a a
还有一个就是这道题的空输入问题，要输出possible，而不是Impossible
一下是我的垃圾代码，跑了500多，有谁有更好的发我邮箱哈: zhangjia888334@sohu.com
#include<iostream>
#include<cstring>
#define keyNum 26
#define MaxN 500005
struct node{
int parent;
int rank;
int num;//这个颜色出现的次数
node()
{
num=rank=0;
parent=-1;
}
};
node colour[MaxN];
int id=0;//数组标记
struct trie{
struct trieNode{//trie结点的结构
trieNode *link[keyNum];//下标为 'a' , 'b' , 'c' , , 'z' 的指针数组
int num[keyNum];//插入这个单词在数组中的位置
trieNode(){
memset(num,-1,sizeof(num));//-1表示还未插入数组
memset(link,NULL,sizeof(link));
}
void init(){
memset(link,NULL,sizeof(link));
memset(num,-1,sizeof(num));
}
};
trieNode* root;
trie()
{
root=(trieNode*)malloc(sizeof(trieNode));//初始化时为root申请了空间
root->init();
}
int Insert(char []);//返回数组中的位置
void Delete(trieNode*);//释放空间
};
void trie::Delete(trieNode* t)
{
int i;
for(i=0;i<keyNum;i++)
if(t->link[i])Delete(t->link[i]);
memset(t->num,0,sizeof(t->num));
delete(t);
}
int trie::Insert(char x[])
{
trieNode *current=root;
int i=1;
while(x[i]){
if(current->link[x[i-1]-'a']==NULL){
current->link[x[i-1]-'a']=(trieNode*)malloc(sizeof(trieNode));
(current->link[x[i-1]-'a'])->init();
}
current=current->link[x[i-1]-'a'];
i++;
}
if(current->num[x[i-1]-'a']==-1)
current->num[x[i-1]-'a']=id++;
colour[current->num[x[i-1]-'a']].num++;//出现的次数++
return current->num[x[i-1]-'a'];
}
void init()
{
int i;
for(i=0;i<MaxN;i++)
colour[i].parent=i;
}
void union_set(int x,int y)
{
if(colour[x].rank>colour[y].rank)
colour[y].parent=x;
else {
colour[x].parent=y;
if(colour[x].rank==colour[y].rank)
colour[y].rank++;
}
}
int find_set(int x)
{
if(x!=colour[x].parent)
colour[x].parent=find_set(colour[x].parent);
return colour[x].parent;
}
bool comman_father()
{
int i,p=0;
p=find_set(0);
for(i=1;i<id;i++)
if(find_set(i)!=p)return false;
return true;
}
void solve()
{
if(comman_father()==false){
printf("Impossible\n");
return;
}
int i,head_end=0;
for(i=0;i<id;i++)
if(colour[i].num%2==1)//判断头和尾
head_end++;
if(head_end==2||!head_end)//一个没回路，一个是有回路
printf("Possible\n");
else printf("Impossible\n");
}
int main()
{
char colr1[12],colr2[12];
trie a;
int ncolr1,ncolr2;
init();
while(scanf("%s%s",colr1,colr2)!=EOF){
ncolr1=a.Insert(colr1);
ncolr2=a.Insert(colr2);
union_set(find_set(ncolr1),find_set(ncolr2));
}
//下面判断有几个parent，若有多个失败
solve();
a.Delete(a.root);
return 0
}
posted @
2008-04-08 18:35 zoyi 阅读(874) |
评论 (1) |
编辑 收藏寝室里很乱，明天我要收拾，收拾好它也收拾好自己
还是很想把博客经营下去，以前不想写，其实是害怕别人看，我贴的都是水题
丢人呐，但是这是我成长的过程
隐藏东西的感觉还真好玩我是棵小白菜，从来都是，也没奢望过会成为参天大树
但是我会慢慢浇灌，小白菜总不至于被我浇成葱了吧，哈哈
呵呵，继续隐藏就这样，待续.........
fighting~~!!!
posted @
2008-04-08 00:55 zoyi 阅读(196) |
评论 (2) |
编辑 收藏
我的青蛙终于过了
完全忘了算法导论上说的理论了~~其实以前写的就只有一个小错误
ax+ny=b;
当求解x时，我们先用扩展欧几里德extended_eculid(a,n,&x',&y');
通过计算的x'和y'来计算x
x可能没解，也可能有d个不同的解
当求解某些问题的时候，我们要求得到最小正解，如果x'*(b/d)<0时，我们应该在此解的基础上继续加n/d
青蛙问题我就是这里错了，我是在最小解的基础上加n,
最好不要忘了对n取模。
http://acm.pku.edu.cn/JudgeOnline/problem?id=1061
//SA-SB=kL(k为整数)
//SA=x+pm SB=y+pn
//(x-y)+p(m-n)=kL
//p(n-m)+kL=x-y
//ax+by=n<=>a'x+b'y=n/gcd(a,b)(此时a'与b'互质)
//若x0,y0为欧几里得所得解
//x=x0+b't y=y0-a't
#include<iostream>
__int64 Ext_Euclid(__int64 a,__int64 b,__int64* x,__int64* y)
{
__int64 p,q,d;
if(a==0){*x=0;*y=1;return b;}
if(b==0){*x=1;*y=0;return a;}
d=Ext_Euclid(b,a%b,&p,&q);
*x=q;
*y=p-(a/b)*q;
return d;
}
int main()
{
/*freopen("1.IN","r",stdin);
freopen("my.OUT","w",stdout);*/
__int64 x,y,m,n,l;//x为A的起始点,y为B的起始点
//m为x的步长，n为y的步长，l为纬度长
__int64 c,a,d;
__int64 p,q;
while(scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&m,&n,&l)!=EOF){
if(n==m)printf("Impossible\n");
else {
if(m>n){a=m-n;c=y-x;}
else {a=n-m;c=x-y;}
d=Ext_Euclid(a,l,&p,&q);
if((x>y?(x-y):(y-x))%d)printf("Impossible\n");
else {
p*=c/d;
while(p<0)p+=l/d;//这里错了，最小的那个不是这么加的
p=p%l;
printf("%I64d\n",p);
}
}}
return 0;
}
E
Encrypted
这道题就是简单的应用扩展的欧几里德，并不涉及模线性方程
#include<iostream>
#define MaxN 100005
char word[MaxN];
int data[MaxN],keys[MaxN];
typedef struct node{
int d;
int x;
int y;
void operator=(node b)
{
d=b.d;
x=b.x;
y=b.y;
}}NODE;
NODE EXTENDED_EUCLID(int a,int b)
{
NODE first,sec;
if(b==0){
sec.d=a;
sec.x=1;
sec.y=0;
return sec;
}
first=EXTENDED_EUCLID(b,(a%b+b)%b);
sec.d=first.d;
sec.x=first.y;
sec.y=first.x-(a/b)*first.y;
return sec;
}
int main()
{
int n,i;
node tmp;
while(scanf("%s",word)!=EOF){
memset(data,0,sizeof(data));
memset(keys,0,sizeof(keys));
int len=strlen(word);
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&data[i]);
for(i=0;i<n;i++)
scanf("%d",&keys[i]);
for(i=0;i<n;i++){
tmp=EXTENDED_EUCLID(data[i],keys[i]);
while(tmp.x<0)
tmp.x+=keys[i]/tmp.d;
printf("%c",word[tmp.x%len]);
}
printf("\n");
}
return 0;
}
posted @
2008-04-08 00:42 zoyi 阅读(189) |
评论 (0) |
编辑 收藏
http://202.120.80.191/problem.php?problemid=1868
这道题想法其实不难，可是开始的方向就错了，做的时候有种投机取巧的感觉，虽然知道是错的，但是我也要去试，呵呵，一头撞到底
首先打质数表，然后找到小与N的每个质数的最大系数，开始一头就扎进了用俩数的乘积去除公约数的方法做，这显然不对啊，要去模的阿，哎
下面是垃圾代码：
#include<iostream>
#include<math.h>
#define MaxN 500005
#define M 987654321
int notP[MaxN];
using namespace std;
void init()
{
int i,j;
memset(notP,0,sizeof(notP));
notP[1]=1;
for(i=2;i<sqrt((double)MaxN);i++)
if(notP[i]==0){
for(j=2;j*i<MaxN;j++)
notP[j*i]=1;
}
}
int solve(int n)
{
int i,ans=1,t;
for(i=2;i<=n;i++){
if(notP[i])continue;
t=n;
while(t>=i){
ans=(((__int64)ans)*i)%M;
t/=i;
}
}
return ans;
}
int main()
{
int N,ans;
init();
while(scanf("%d",&N)!=EOF){
ans=solve(N);
printf("%d\n",ans);
}
return 0;
}
B题等会儿再说，他是我的痛
http://202.120.80.191/problem.php?problemid=1869
C题Cards
http://202.120.80.191/problem.php?problemid=1870
这道题开始用o(n2)的做的，并没有想到该怎么做，后面超时，才是是这用o(n)的做，开始想的一直都不清楚
主要是在每次当前移除情况下又出现了present_numR>present_numB的情况，就要更新切牌点，并且也要同时更新切牌而移除的红牌或黑牌
一下是我的没人品的代码：（我这么说一点都不过分）
#include<iostream>
#include<cstring>
#define MaxN 100005
char deck[MaxN];
int main()
{
int numR,numS,i,k,remR,remS,len;
while(scanf("%s",deck)!=EOF){
remR=remS=numR=numS=k=0;
len=(int)strlen(deck);
for(i=0;i<len;i++){
if(deck[i]=='R')numR++;
else numS++;
if(numR-remR>numS-remS){
remR=numR;
remS=numS;
k=i+1;}
}
printf("%d\n",k);
}
return 0;
}
D题 DICE
这是按照解题报告写得，是一道动态规划题，动态规划还是要坚持继续做，每次都靠蒙着想到是不行的
要用眼睛直接发现它。
这道题首先用一compute函数把每次用size[]的筛子，掷numSize下的所得每种可能结果的概率保存在p中
void compute(double p[],int size[],int numSize)
在主函数中我们分别把A,B的结果的计算出来
而后对B进行处理，这里同样是利用动态规划的思想，将pB[i]中，点数〈i的概率保存在tmp[i]中
然后结合tmp[],pA[]，计算结果输出。
容易出错点：
在compute函数中for(j=MaxS-1;j>=0;j--){
p[j]=0;//这里要先初始化为0，在下一格6个size中，每种size的概率都要加
for(t=0;t<6;t++)
if(j-size(t)>0)//这里也是容易出错的，runtime error的起源
p[j]+=p[j-size[t]]/6.0;//这里也是，6.0，而不是6，要养成习惯
#include<iostream>
#define MaxS 23*100//每次最多丢到100
int sizeA[6],sizeB[6];
double pA[MaxS],pB[MaxS];
int numDiceA,numDiceB;
void compute(double p[],int size[],int numSize)
{
int i,j,t;
for(i=1;i<numSize;i++)
for(j=MaxS-1;j>=0;j--){
p[j]=0;//important
for(t=0;t<6;t++)
if(j-size[t]>0)
p[j]+=p[j-size[t]]/6.0;
}
}
int main()
{
int i;
double ans,tmp[MaxS];
while(scanf("%d%d",&numDiceA,&numDiceB)!=EOF){
ans=0.0;
memset(tmp,0,sizeof(tmp));
memset(pA,0,sizeof(pA));
memset(pB,0,sizeof(pB));
for(i=0;i<6;i++){
scanf("%d",&sizeA[i]);
pA[sizeA[i]]+=1/6.0;}
for(i=0;i<6;i++){
scanf("%d",&sizeB[i]);
pB[sizeB[i]]+=1/6.0;}
compute(pA,sizeA,numDiceA);
compute(pB,sizeB,numDiceB);
for(i=1;i<MaxS;i++)
tmp[i]=tmp[i-1]+pB[i-1];
for(i=1;i<MaxS;i++)
ans+=pA[i]*tmp[i];
printf("%.9lf\n",ans);
}
return 0;
}
未完待续..............
posted @
2008-04-07 21:47 zoyi 阅读(184) |
评论 (0) |
编辑 收藏
好不容易写的一个模版~本来是想按照我们数据结构教程的trie树来写，但是他的实现我实在觉得太难
所以还是采用简化版的trie树
这个应该算是比较标准的trie树结构，但是他的插入实现起来不仅仅是插入本身的单词，可能还需要修改原来的数结构
比如说本身已经存在了bobwhite，现在添加bobwhq，就要在第二层的基础上继续扩展，bobwhite的位置也要重新定位，删除操作也是这样
可能还要上移某些单词，这个昨天试了很久，写出来的都不行。
而且对这种字典树的结构本身我的理解就很混乱。
简化版的trie树
以下这种实现方法是根据别人改编的，昨天被逼得没办法还是觉得简化版的，突然发现个牛人的写法和我的很相似（这着实还让我激动了下下），就边学习边改了，呵呵
它是根据杭电的一道题来写的，以下是我的代码：
http://acm.hdu.edu.cn/showproblem.php?pid=1247
#include<iostream>
#define keyNum 26
#define MaxN 50
struct trie{
struct trieNode{//trie结点的结构
trieNode *link[keyNum];//下标为 'A' , 'B' , 'C' , 
, 'Z' 的指针数组
int num[keyNum];//插入key的次数
trieNode(){
memset(num,0,sizeof(num));
memset(link,NULL,sizeof(link));
}
void init(){
memset(link,NULL,sizeof(link));
memset(num,0,sizeof(num));
}
};
trieNode* root;
trie()
{
root=(trieNode*)malloc(sizeof(trieNode));//初始化时为root申请了空间
root->init();
}
bool Search(char *);
void Insert(char []);
void Delete(trieNode*);
};
bool trie::Search(char * x)
{
if(*x==0)return false;
trieNode* current=root;
x++;
while(*x){
if(current->link[*(x-1)-'a'])
current=current->link[*(x-1)-'a'];
else break;
x++;
}
if(*x==0&¤t->num[*(x-1)-'a'])
return true;
else return false;
}
void trie::Delete(trieNode* t)
{
int i;
for(i=0;i<keyNum;i++)
if(t->link[i])Delete(t->link[i]);
memset(t->num,0,sizeof(t->num));
delete(t);
}
void trie::Insert(char x[])
{
trieNode *current=root;
int i=1;
while(x[i]){
if(current->link[x[i-1]-'a']==NULL){
current->link[x[i-1]-'a']=(trieNode*)malloc(sizeof(trieNode));
(current->link[x[i-1]-'a'])->init();
}
current=current->link[x[i-1]-'a'];
i++;
}
(current->num[x[i-1]-'a'])++;
}
char c[ 50000 ][MaxN],tmp;
int main()
{
trie a;
int i=0,j,num;
while(scanf("%s",c[i])!=EOF)
a.Insert(c[i++]);
num=i;
for(i=0;i<num;i++)
for(j=1;c[i][j];j++){
tmp=c[i][j];
c[i][j]=0;
if(a.Search(c[i])){
c[i][j]=tmp;
if(a.Search(&c[i][j])){
printf("%s\n",c[i]);
break;}
}
else c[i][j]=tmp;
}
a.Delete(a.root);
return 0;
}
这个模版还不是很完善~用起来还是不大方便，比如删除节点，我的删除只是写了删所有的，用递归写的。
还有遍历节点，都不是很方便的。
以上代码解释几点：
首先我构造了一格trie的结构：在此结构中有root，和这棵树的基本三个操作
再次trie结构中的每个节点都是trieNode的结构，包括root也是
这棵树是动态生成的，所以对trieNode的init很重要，这点写过的就知道，不Init会出现很多问题的,
在trieNode结构中主要有26个link和26个num，刚开始我自己写的时候就是这26个num搞不清，只写了一个num，这是对树结构的理解混乱造成的
num在这里是标记这个单词插入的次数，为0表示这个单词还没有被插入过
trieNode还有个很重要的成员函数就是init了。
posted @
2008-04-06 13:09 zoyi 阅读(3141) |
评论 (3) |
编辑 收藏
摘要:
1***********1934******************************** 2----------------------------------------------- 3#include<iostream> 4#define Max 30 5using name...
阅读全文
posted @
2008-03-09 14:05 zoyi 阅读(227) |
评论 (1) |
编辑 收藏
本来都打定主意叫它几十次，这道题考虑了很多细节，想了很多边界条件，一次交过了还是没想到的
我也不知道这道题到底要不要考虑那些边界条件，不过看交过的比例，要注意的肯定很多，也许还有应该要想到的
这是第一次作实数的高精度，写的很乱，很多都是发现问题后不上去的
1#include<iostream>
2using namespace std;
3#define Max 200
4#define Max_b 7
5typedef struct bigint{
6 int data[Max];//从0开始存储
7 int len;
8 int i;//表示小数位
9 bigint()
10 {
11 memset(data,0,sizeof(data));
12 len=1;
13 i=0;
14 }
15 friend bigint operator+(bigint,bigint);
16 friend bigint operator*(bigint,bigint);
17 void print();//小数点在第i位上，后面有i个小数位
18 void operator=(const bigint&y){
19 len=y.len;
20 for(int j=0;j<y.len;j++)
21 data[j]=y.data[j];
22 i=y.i;
23 }
24}BIGINT;
25BIGINT operator+(BIGINT x,BIGINT y)
26{
27 BIGINT r;
28 int rlen=x.len>y.len?x.len:y.len;
29 int tmp,i,jinwei=0;
30 for(i=0;i<rlen;i++){
31 tmp=x.data[i]+y.data[i]+jinwei;
32 r.data[i]=tmp%10;
33 jinwei=tmp/10;}
34 if(jinwei)r.data[rlen++]=jinwei;
35 r.len=rlen;
36 return r;
37}
38BIGINT operator*(BIGINT x,BIGINT y)
39{
40 BIGINT r;
41 int i,j;
42 memset(r.data,0,sizeof(r.data));
43 r.len=x.len+y.len;
44 for(i=0;i<x.len;i++)
45 for(j=0;j<y.len;j++)
46 r.data[i+j]+=x.data[i]*y.data[j];
47 for(i=0;i<r.len;i++){
48 r.data[i+1]+=r.data[i]/10;
49 r.data[i]%=10;}
50 while(r.data[i]){
51 r.data[i+1]+=r.data[i];
52 r.data[i]%=10;
53 i++;}
54 while(i>=0&&!r.data[i])i--;//这个已经消除了开头的零
55 //末尾不存在零，不用考虑
56 if(i!=-1)r.len=i+1;
57 else r.len=1;//r为0的情况
58 r.i=x.i+y.i;
59 return r;
60}
61void BIGINT::print()
62{
63 int j,k;
64 for(j=this->len-1;j>=this->i;j--)//输出了len-i个或是一个也还没输出
65 printf("%d",this->data[j]);
66 if(j==-1){
67 putchar('\n');
68 return;}
69 putchar('.');
70 if(j<this->i)//小数点后要补零
71 for(k=this->i-1;k>j;k--)
72 putchar('0');
73 for(;j>=0;j--)
74 printf("%d",this->data[j]);
75 putchar('\n');
76}
77BIGINT cToBigint(char c[])
78{
79 int clen=(int)strlen(c),i=0,j=clen-1,k;
80 BIGINT result;
81 memset(result.data,0,sizeof(result.data));
82 while(c[i]=='0'&&i<clen-1)i++;
83 while(c[j]=='0'&&j>=0)j--;
84 if(j>i){
85 result.len=j-i;
86 for(j=result.len-1;c[i]!='.';j--,i++)
87 result.data[j]=c[i]-'0';
88 result.i=j+1;
89 for(i++;j>=0;j--,i++)
90 result.data[j]=c[i]-'0';}
91 else if(j<i){//
92 result.len=1;
93 result.i=0;}
94 else if(i==j&&c[i]!='.'){//完全就是整数，没有小数点
95 for(j=clen-1,k=0;j>=i;j--,k++)
96 result.data[k]=c[j]-'0';
97 result.len=k;
98 result.i=0;
99 }
100 return result;
101}
102int main()
103{
104 BIGINT R,result;
105 int n,i;
106 char c[Max_b];
107 while(scanf("%s %d",c,&n)!=EOF){
108 memset(result.data,0,sizeof(result.data));
109 result.i=0;
110 result.len=1;
111 R=cToBigint(c);
112 result.data[0]=1;
113 for(i=1;i<=n;i++)
114 result=result*R;
115 result.print();
116 }
117 return 0;
118}
posted @
2008-03-09 14:00 zoyi 阅读(548) |
评论 (0) |
编辑 收藏