|
|
July 02 初步安排：
七月上旬 回家补办身份证
七月中旬 暑期实践
七月中下旬 周边玩一两天
七月下旬至九月上旬 集训
July 01 最近发生很多事，一些事一些人让我感觉很不爽！但回头想想，这些事这些人，只是我生命中的过眼烟云而已，何必在意。那些人，不喜欢，就忽略他，当他不存在。那些事，只要自己尽力了，又何必太在意结果呢？最愚蠢的事就是为那些愚蠢的人所做的愚蠢的事而生气！一切都只是个过程，不以物喜，不以己悲，以平和的心态去应对一切。并不是所有的事都能如愿，并不是所有的付出都有回报。 June 16 帮豆豆选课，上午刷了一上午没刷进去，下午装个“按键精灵”，一分钟刷两次，刷了一下午还是没刷进去，直到晚上11点多了才刷进去，这什么破系统！要强烈地鄙视一下！ June 15 都不知道是怎么花的，创历史新高了，历史上最高的一次是大一刚进来的时候，半个月花掉1800RMB。不知道的还以为我是追女生花的。汗，上个月是在追女生，不过花在女生身上的除了吃了几顿饭，逛街的时候送了一件我非常喜欢的很普通的衣服，根本没有花其他的钱（不是我吝啬，是她不接受，汗...）。而且在我送她衣服的第二天她就送回给我一个包，当时我差点晕倒！
算来算去我的钱到底是花哪里了呢，电话费虽然比较多，但也就300RMB多点啊，自己买了一双沙滩鞋，一件衬衫，两件T恤，也就500左右吧，吃饭差不多也就500左右吧，零食200也差不多了吧，出去玩什么的，500也差不多了啊。还有1000哪里去了？我靠，以后一定要记账，一定要学会理财！
现在钱包丢了，银行卡，身份证什么的都没了。每天还要用小猫咪的饭卡吃饭，真是郁闷！不过惊喜地发现这个月的开支惊人的小，看来口袋里钱还是不要装太多的好。 月下、小黑、高博、蓝天他们这些ACM元老们都要毕业了，也许这是我们最后一次相聚了。还有DOOM3，也要离开ACM了。我本来也要离开的，但由于种种原因，还是决定留下来继续搞一年，老刘也是。
月下临风，在我大一刚开始接触ACM的时候在论坛上看到这个账号感觉就很特别。后来我们认识了，虽然平时接触不多，但他一直很关照我，给了我很多建议，让我明白了一些事情，少走了一些弯路。真的要谢谢你！
小黑，大牛一个，RP很好，很乐于助人，很有耐心，在QQ上问了他很多问题，从来没有烦过，而且还会很认真地去解答。
高博，从刚接触ACM到现在，我们一直是队友。人很稳重，做事很踏实。省赛拿了金牌，全国赛也拿了铜牌，又考上了浙大的研究生，可谓功成身就了。
DOOM3，我们是一起入门ACM的，然后一直并肩作战到现在的战友。关于他们，就不多写了，我怕一写就收不住了：）
别的不多说了，只希望各位师兄都能在各自的道路上一路走好！ June 09 身份证 银行卡 学生证 图书证 饭卡 money全没了，似乎预示着什么，难道今年期末有大劫？！ June 07 豆豆、徐升 and me 去小蓓妹妹家玩了一个周末（其实是在那边吃了一个周末），好开心！我们以前做菜，然后吃饭，然后剩下可怜的我收拾残局。然后一起看电视，去逛街，去电玩，去奶吧，去淋雨，去吃pizza，去......真的很开心！小蓓妹妹真是多才多艺，会做饭，会家务，会打排球，会数模，会ACM，会古筝，会......果然是浙江最强MM啊！我这个做哥哥的，惭愧死了。她比我大一年级，她要我叫她学姐，也许我真该叫她学姐，但还是喜欢做她哥，呵呵。在一起呆了两天，发现小蓓比我原来印象中的小蓓要可爱得多。想想我这个大哥做得真够不称职的，这几天，也没好好关心关心她，满脑子只想着豆豆，当意识到时，却马上要回杭州了，汗......希望放假她能来杭州玩几天
还有这几天，特别在火车上，我只顾着跟豆豆聊，忽略他，他很生气，问题很严重，对不起啦，我不是故意的，希望你能原谅，相信你会原谅的（^_^）
周六晚上，小蓓先睡了，我跟豆豆继续看电视，豆豆哭了，我的T恤被她的眼泪湿了一大批，原来她不是麻木的，内心有太多东西一直压着。女孩子有时候不需要那么坚强的，否则会很难受的。
周日下午三点的火车，要回杭州了，要准备期末了，心情异常失落，真想多呆几天。下一次相聚又不知是几时了，希望不要太久:P June 01 豆豆送了我一个levis的包，很漂亮，我很喜欢。晚上走路她还挽了我的手，我的心噗通噗通的，幸福死了 May 31 晚上第一次给小豆豆买衣服，其中有一件娃娃衣，穿上去很漂亮，很可爱，我挑的，呵呵！ May 14 其实参加这次省赛，已经完全没以前的激情了，完全是为了自己的一个承诺，还有那期待已久的棒棒糖，而坚持了下来。省赛终于结束了，虽然不是很理想，但应该来说还是比较圆满的。大家都可以光荣退役了，我也拿到了那久违的棒棒糖了，已经没有再留下来的理由了。
这一年来的AC生涯是令人难忘的，认识了一个好老师和一帮志同道合的好朋友。现在要散了，心里面真的有点伤感。人总是要往前走的，虽然这里的风景很美，但还是无法停留太久！再见，朋友们，再见，ACM。愿我们在以后各自的人生轨迹上都能走出自己的一片天地！永远怀念你们！ August 19 前几天回了一趟家,可谓有喜有忧!
喜的是,在家共5天,吃了4天的七月半(家乡的一种节日聚餐).自己家一天,同学家两天,亲戚家两天.一个字--"爽"!明年也一定要这个时候回家,呵呵!
忧的是,由于我不在,前天PKU上的连续赛我们队惨败!目前总排名已经掉到学校三个队中的最后了.危险啊!明天下午ZOJ上又有练习赛了,如果再输,我们组参加全国赛的可能就比较渺茫了,而且将严重影响士气!所以明天的练习赛对我们来说是关键的一场,只能赢,不能输!
#include <stdio.h>
#include <vector>
using namespace std;
const Maxn=10; //配置最大的结点个数
const Maxint=2000000000;
struct Linktype
{
int v,w;
};
struct Sttype
{
int v,p,d;
} Q[Maxn+1];
int Q_pos[Maxn+1];
vector <vector<Linktype> > Gr;
void Swap(int a,int b) //Q堆中第a个顶点与第b个顶点交换
{
int i;
Sttype t;
t=Q[a];
Q[a]=Q[b];
Q[b]=t;
i=Q_pos[Q[a].v];
Q_pos[Q[a].v]=Q_pos[Q[b].v];
Q_pos[Q[b].v]=i;
}
void Decrease(int v,int k) //将Q堆中第v个顶点的d值设为k,并将该顶点放到Q堆的合适位置
{
Q[v].d=k;
while (v!=1 && Q[v].d<Q[v/2].d)
{
Swap(v,v/2);
v/=2;
}
}
void Heapfy(int i,int hs) //堆排序,使得以i为根的子树成为一个堆
{
int m;
m=i;
do
{
i=m; //求顶点i与左右孩子三个顶点间d值最小的顶点序号m
if ((i*2<=hs)&&(Q[i*2].d<Q[m].d))
{
m=i*2;
}
if ((i*2+1<=hs)&&(Q[i*2+1].d<Q[m].d))
{
m=i*2+1;
}
if (i!=m) Swap(i,m);
}while (i!=m);
}
void Relax(int u,int v,int w) //对权值为w的边进行松弛操作
{
if (Q[Q_pos[v]].d>Q[Q_pos[u]].d+w)
{
Q[Q_pos[v]].p=u; //把v的父顶点设为u
Decrease(Q_pos[v],Q[Q_pos[u]].d+w); //修正v的d值并重新对Q进行堆排序
}
}
void Dijkstra(Sttype Q[],int root,int n)
{
int i,u,hs;
vector<Linktype>::iterator p;
for (i=1;i<=n;i++)
{
Q[i].v=i;
Q[i].d=Maxint;
Q_pos[i]=i;
}
Q[root].d=0;
Swap(1,root);
hs=n; //Q表长度初始化为n
while (hs>0)
{
u=Q[1].v;
Swap(1,hs);
hs--;
Heapfy(1,hs);
for (p=Gr[u].begin();p!=Gr[u].end();p++) //对Q队列中所有与u相连的边进行松弛操作
{
if (Q_pos[p->v]<=hs) Relax(u,p->v,p->w);
}
}
}
void input(int &n,int &root,int &s)
{
int u;
Linktype t;
scanf("%d%d%d",&n,&root,&s); //输入顶点数,起始点,终点
Gr.clear();
Gr.resize(n+1);
while (scanf("%d%d%d",&u,&t.v,&t.w)!=EOF) //读入邻接表
{
Gr[u].push_back(t);
}
}
void outpath(int root,int s)
{
if (root==s) return;
outpath(root,Q[Q_pos[s]].p);
printf(" ->%d",s);
}
void output(int root,int s)
{
printf("%d\n",Q[Q_pos[s]].d);
printf("%d",root);
if (root!=s)
outpath(root,s);
printf("\n");
}
int main()
{
int root,n,s;
input(n,root,s);
Dijkstra(Q,root,n);
output(root,s);
return 0;
}
首先介绍一下伪素数。伪素数：如果n>1是一个奇数,且a^(n-1) ≡1（mod n）（a!=n），则我们说n是一个满足基于a的伪素数。
当a=2时，在小于10000的n值中，只会产生22个不是素数的伪素数。如果n是伪素数为了增加n是素数的概率，我们可以对a随机取多个不同的值进行验证。如果对于多个a，n都为伪素数，那么基本上可以确定n就是素数。但n还是有伪素数的危险，要完全排除伪素数也是可以的，不过稍微麻烦一点。还要加条件：对于n-1的每一个素因子q，有a^(n-1)/q !≡1 (mod n)。
在计算过程中会用到一个很有用的命题：a^b mod n=((a mod n)*a mod n)*b mod n…。
这个方法应用到搜索的剪枝中，很有效果。
一般来说，大凡搜索问题在开始搜索之前要尽量做好准备工作，如搜索中要反复使用的数据要预先算好储存。或者其中的某一类数据会反复用到，那么在第一次计算出值的时候就对它们进行保存，等再次用到时，直接读取就OK了。这也就是搜索中的DP思想。又如对一些规模比较大的问题，可以考虑先用贪心法获得一个较优的上界，再搜索。 August 13 /*
Code by weigang Lee 2005-11-2；
可在10-100000000范围内配置进制；
可配置安全优先活效率优先，主要针对不规范初始化引起的一些错误，一般情况下建议以安全优先的模式运行；
效率测试：
测试平台：普通笔记本
测试环境：XP SP2
编译器：VC++
测试项目：计算10000!
测试结果：1.安全优先模式，10进制，耗时15秒
2.效率优先模式，10进制，耗时13秒
3.安全优先模式，100000000进制，耗时2秒
4.效率优先模式，100000000进制，耗时2秒
结果分析：安全优先或效率优先对效率的影响不大，而使用较高的进制对效率的影响相对明显；
为了使用方便jia,...,jia4,jian,...,jian4,chen,...,chen4基本上都独立实现,因而有较多的冗余代码；
*/
#include <stdio.h>
#include <ctime>
#include <string>
const bool SafeFirst=false; //一般当同时使用了两个或两个以上大数运算时应设置为true;设置安全优先还是效率优先.若效率优先(false),一定要保证传入到函数中的数据都是规格的大数,否则可能出错.效率差常数倍,一般是1倍,要看具体数据,数据越小,而lmax开得越大,差距越大.一般建议用true
const int nw=8; //jz中0的个数,nw<=8
const int jz=100000000; //配置进制,只能是10^nw
const int lmax=100000; //大数数组开的大小,(lmax-1)*nw为大数的位数
void jia(const int a[],const int b[],int c[]) //大数a[]加大数b[],结果存在c[]中
{
int i,top;
top=a[0]>b[0]?a[0]:b[0];
if (SafeFirst) //在false情况下,如果传入的c[]非规格的,不能保证返回的c[]规格
{
memset(c,0,sizeof(int)*lmax);
}else
{
c[top+1]=0;
}
for (i=1;i<=top;i++)
{
c[i]+=a[i]+b[i];
if (c[i]>=jz)
{
c[i]-=jz;
c[i+1]++;
}
}
if (c[top+1]>0)
c[0]=top+1;
else
c[0]=top;
}
void jia2(int a[],const int b[]) //对大数a[]累加另一大数b[]
{
int i,top;
if (SafeFirst)
memset(a+a[0]+1,0,sizeof(int)*(lmax-a[0]-1));
top=a[0]>b[0]?a[0]:b[0];
for (i=1;i<=b[0];i++)
{
a[i]+=b[i];
if (a[i]>=jz)
{
a[i]-=jz;
a[i+1]++;
}
}
if (a[top+1]>0)
a[0]=top+1;
else
a[0]=top;
}
void jia3(const int a[],const int b,int c[]) //大数a[]加上小数b,存在c[]中
{
int i;
unsigned int t;
if (SafeFirst) memset(c,0,sizeof(int)*lmax);
memcpy(c,a,sizeof(int)*(a[0]+1));
t=c[1]+b;
c[1]=t%jz;
i=1;
while (t>=jz)
{
t/=jz;
t+=c[i+1];
c[i+1]=t%jz;
i++;
}
if (c[0]<i) c[0]=i;
}
void jia4(int a[],const int b) //对大数a[]累加b
{
int i;
unsigned int t;
if (SafeFirst)
memset(&a[a[0]+1],0,sizeof(int)*(lmax-a[0]-1));
t=a[1]+b;
a[1]=t%jz;
i=1;
while (t>=jz)
{
t/=jz;
t+=a[i+1];
a[i+1]=t%jz;
i++;
}
if (a[0]<i) a[0]=i;
}
/***********************************************************************************************/
void jian(const int a[],const int b[],int c[]) //c[]=a[]-b[],a[]>=b[]
{
int i,jw;
if (SafeFirst) //若为false,不能保证传出的c[]是规格的
{
memset(c,0,sizeof(int)*lmax);
}
jw=0;
for (i=1;i<=b[0];i++)
{
if (a[i]-jw>=b[i])
{
c[i]=a[i]-jw-b[i];
jw=0;
}
else
{
c[i]=a[i]+jz-jw-b[i];
jw=1;
}
}
for (i=b[0]+1;i<=a[0];i++)
{
if (a[i]-jw>=0)
{
c[i]=a[i]-jw;
jw=0;
}else
{
c[i]=a[i]+jz-jw;
jw=1;
}
}
i=a[0];
while (c[i]==0) i--;
if (i>0) c[0]=i;
else
c[0]=1;
}
void jian2(int a[],const int b[]) //a[]-=b[];a[]>b[]
{
int i;
if (SafeFirst) memset(&a[a[0]+1],0,sizeof(int)*(lmax-a[0]-1));
for (i=1;i<=b[0];i++)
{
a[i]-=b[i];
if (a[i]<0)
{
a[i]+=jz;
a[i+1]--;
}
}
while (a[i]<0 && i<a[0])
{
a[i]+=jz;
a[i+1]--;
i++;
}
i=a[0];
while (a[i]==0)
i--;
if (i>0) a[0]=i;
else a[0]=1;
}
void jian3(const int a[],const int b,int c[]) //a[]>=b
{
int i;
memcpy(c,a,sizeof(int)*(a[0]+1));
if (SafeFirst) memset(&c[c[0]+1],0,sizeof(int)*(lmax-a[0]-1));
c[1]-=b;
i=1;
while (c[i]<0)
{
c[i+1]+=c[i]/jz;
c[i]%=jz;
if (c[i]<0)
{
c[i+1]--;
c[i]+=jz;
}
i++;
}
i=c[0];
while (c[i]==0) i--;
if (i>0) c[0]=i;
else
c[0]=1;
}
void jian4(int a[],const int b)
{
int i;
a[1]-=b;
i=1;
while (a[i]<0)
{
a[i+1]+=a[i]/jz;
a[i]%=jz;
if (a[i]<0)
{
a[i+1]--;
a[i]+=jz;
}
i++;
}
i=a[0];
while (a[i]==0) i--;
if (i>0) a[0]=i;
else
a[0]=1;
}
/***********************************************************************************************/
inline void chen(const int a[],const int b[],int c[]) //大数乘大数
{
__int64 t=0;
int up=0,i,j,k;
if (SafeFirst)
memset(c,0,sizeof(int)*lmax);
for (i=1;i<=a[0];i++)
{
up=0;
for (j=1;j<=b[0];j++)
{
k=i+j-1;
t=(__int64)a[i]*b[j]+up;
c[k]+=t%jz;
up=t/jz;
while (c[k]>=jz)
{
c[k+1]++;
c[k]-=jz;
}
}
if (up>0)
{
c[i+b[0]]+=up;
}
}
i=a[0]+b[0];
while (c[i]==0) i--;
if (i>0) c[0]=i;
else
c[0]=1;
}
inline void chen2(const int a[],const int b,int c[]) //大数乘小数
{
__int64 t;
int up=0,i;
if (SafeFirst)
memset(c,0,sizeof(int)*lmax);
for (i=1;i<=a[0];i++)
{
t=(__int64)a[i]*b+up;
c[i]=t%jz;
up=t/jz;
}
c[i]+=up;
while (c[i]>=jz)
{
c[i+1]=c[i]/jz;
c[i]%=jz;
i++;
}
if (c[i]==0) i--;
if (i>0) c[0]=i;
else
c[0]=1;
}
/***********************************************************************************************/
void chghtl(const int a[],int b[])
{
int t,i,j,p=0;
memset(b,0,sizeof(int)*nw*lmax);
for (i=1;i<=a[0];i++)
{
t=a[i];
for (j=1;j<=nw;j++)
{
p++;
b[p]=t%10;
t/=10;
}
}
while (b[p]==0) p--;
if (p>0) b[0]=p;
else b[0]=1;
}
void chglth(const int a[],int b[])
{
int i,j,top;
memset(b,0,sizeof(int)*lmax);
for (i=1;i<=a[0];i+=nw)
{
b[0]++;
top=i+nw-1;
if (top>a[0]) top=a[0];
for (j=top;j>=i;j--)
{
b[b[0]]=b[b[0]]*10+a[j];
}
}
}
void chu(int a[],const int b[],int c[]) //c[]=a[]%b[],a[]/=b[];a[]>=0 && b[]>0;
{
int *a1=new int[nw*lmax],*b1=new int[nw*lmax],*c1=new int[nw*lmax],i,j,lcount;
bool ok;
memset(a1,0,sizeof(int)*nw*lmax);
memset(b1,0,sizeof(int)*nw*lmax);
memset(c1,0,sizeof(int)*nw*lmax);
chghtl(a,a1);
chghtl(b,b1);
for (i=a1[0];i>=b1[0];i--)
{
if (i<a1[0])
{
a1[i]+=a1[i+1]*10;
a1[i+1]=0;
}
ok=true;
for (j=b1[0];j>=1;j--)
if (a1[i+j-b1[0]]<b1[j])
{
ok=false;
break;
}else if (a1[i+j-b1[0]]>b1[j])
{
ok=true;
break;
}
lcount=0;
while (ok)
{
for (j=1;j<=b1[0];j++)
{
a1[i+j-b1[0]]-=b1[j];
if (a1[i+j-b1[0]]<0)
{
a1[i+j-b1[0]]+=10;
a1[i+j-b1[0]+1]--;
}
}
lcount++;
for (j=b1[0];j>=1;j--)
if (a1[i+j-b1[0]]<b1[j])
{
ok=false;
break;
}else if (a1[i+j-b1[0]]>b1[j])
{
ok=true;
break;
}
}
c1[i-b1[0]+1]=lcount;
}
i=a1[0];
while (c1[i]==0) i--;
if (i>0) c1[0]=i;
else
c1[0]=1;
i=b1[0];
while (a1[i]==0) i--;
if (i>0) a1[0]=i;
else
a1[0]=1;
for (i=1;i<=a1[0];i++)
if (a1[i]>9)
{
a1[i+1]+=a1[i]/10;
a1[i]%=10;
}
while (a1[i]>9)
{
a1[i+1]=a1[i]/10;
a1[i]%=10;
i++;
}
if (a1[i]==0) i--;
if (i>0) a1[0]=i;
else
a1[0]=1;
chglth(a1,c);
chglth(c1,a);
delete []a1;
delete []b1;
delete []c1;
}
void chu2(const int a[],const int b[],int c[], int d[]) //c[]=a[]/b[];d[]=a[]%b[]
{
memcpy(c,a,sizeof(int)*lmax);
chu(c,b,d);
}
void chu3(int a[],const int b,int c[]) //c[]=a[]%b; a[]/=b;
{
__int64 t;
int i;
memcpy(c,a,sizeof(int)*lmax);
for (i=c[0];i>=1;i--)
{
if (i<c[0])
{
t=(__int64)c[i]+(__int64)c[i+1]*jz;
c[i+1]=0;
}else
{
t=c[i];
}
c[i]=t%b;
a[i]=t/b;
}
i=a[0];
while (a[i]==0) i--;
if (i>0) a[0]=i;
else
a[0]=1;
i=1;
while (c[i]>=jz)
{
c[i+1]=c[i]/jz;
c[i]%=jz;
i++;
}
if (c[i]==0) i--;
if (i>0) c[0]=i;
else
c[0]=1;
}
void chu4(const int a[],const int b,int c[],int d[]) //c[]=a[]/b; d[]=a[]%b;
{
memcpy(c,a,sizeof(int)*lmax);
chu3(c,b,d);
}
/***********************************************************************************************/
void chgstn(const char s[],int a[]) //字符串转大数
{
int i,t1,l,j,t;
memset(a,0,sizeof(a));
l=strlen(s);
for (i=l-1;i>=0;i-=nw)
{
t=0;
t1=i-nw+1;
if (t1<0) t1=0;
for (j=t1;j<=i;j++)
t=t*10+s[j]-'0';
a[0]++;
a[a[0]]=t;
}
}
void output(const int c[]) //大数输出
{
int i,w,j,n;
printf("%d",c[c[0]]);
for (i=c[0]-1;i>0;i--)
{
n=c[i];
w=0;
while (n>0)
{
w++;
n/=10;
}
for (j=0;j<nw-w;j++)
printf("0");
if (c[i]>0) printf("%d",c[i]);
}
printf("\n");
}
void jiecheng(int n=-1)
{
int begin,i,cost,*t=new int[lmax],*a=new int[lmax];
memset(t,0,sizeof(t)*lmax);
memset(a,0,sizeof(a)*lmax);
if (n<0)
scanf("%d",&n);
begin=time(0);
a[0]=1;
a[1]=1;
for (i=2;i<=n;i++)
{
for (int j=1;j<=a[0];j++)
t[j]=a[j];
t[0]=a[0];
chen2(t,i,a);
}
cost=time(0)-begin;
output(a);
printf("Cost time : %d\n",cost);
delete []t;
delete []a;
}
void chenfang(const int a[],int n,int c[]) //求a[]的n次方
{
int i,*b=new int[lmax];
memcpy(b,a,sizeof(int)*lmax);
memcpy(c,a,sizeof(int)*lmax);
for (i=2;i<=n;i++)
{
chen(b,a,c);
memcpy(b,c,sizeof(int)*lmax);
}
delete []b;
}
void examinechenfang() //检测chenfang()的正确性
{
int a[lmax]={0},b[lmax]={0},n;
char s[nw*lmax];
while (scanf("%s",s)!=EOF)
{
scanf("%d",&n);
chgstn(s,a);
chenfang(a,n,b);
output(b);
}
}
void examinejia()
{
int a[lmax]={0},b[lmax]={0},c[lmax]={0},n,i;
char s[nw*lmax];
while (scanf("%s",s)!=EOF)
{
scanf("%d",&n);
chgstn(s,a);
memset(c,0,sizeof(c));
for (i=1;i<=n;i++)
{
memcpy(b,c,sizeof(int)*lmax);
jia(a,b,c);
}
output(c);
}
}
void examinejia2()
{
int a[lmax]={0},c[lmax]={0},n,i;
char s[nw*lmax];
while (scanf("%s",s)!=EOF)
{
scanf("%d",&n);
chgstn(s,a);
memset(c,0,sizeof(c));
for (i=1;i<=n;i++)
{
jia2(c,a);
}
output(c);
}
}
void examinejia3()
{
int a[lmax],b,c[lmax],n,i;
char s[lmax*nw];
while (scanf("%s%d%d",s,&b,&n))
{
// memset(c,0,sizeof(c));
chgstn(s,a);
for (i=1;i<=n;i++)
{
jia3(a,b,c);
memcpy(a,c,sizeof(int)*lmax);
}
output(c);
}
}
void examinejia4()
{
int a[lmax],b,n,i;
char s[lmax*nw];
while (scanf("%s%d%d",s,&b,&n))
{
chgstn(s,a);
for (i=1;i<=n;i++)
{
jia4(a,b);
}
output(a);
}
}
void examinejian()
{
int a[lmax]={0},b[lmax]={0},c[lmax]={0},n,i;
char s[nw*lmax];
while (scanf("%s",s)!=EOF)
{
scanf("%d",&n);
chgstn(s,a);
memset(c,0,sizeof(c));
for (i=1;i<=n;i++)
{
memcpy(b,c,sizeof(int)*lmax);
jia(a,b,c);
}
output(c);
for (i=1;i<=n;i++)
{
memcpy(b,c,sizeof(c));
jian(b,a,c);
}
output(c);
}
}
void examinejian2()
{
int a[lmax]={0},b[lmax]={0},c[lmax]={0},n,i;
char s[nw*lmax];
while (scanf("%s",s)!=EOF)
{
scanf("%d",&n);
chgstn(s,a);
memset(c,0,sizeof(c));
for (i=1;i<=n;i++)
{
memcpy(b,c,sizeof(int)*lmax);
jia(a,b,c);
}
output(c);
for (i=1;i<=n;i++)
{
jian2(c,a);
}
output(c);
}
}
void examinejian3()
{
int a[lmax],b,c[lmax],n,i;
char s[lmax*nw];
while (scanf("%s%d%d",s,&b,&n))
{
// memset(c,0,sizeof(c));
chgstn(s,a);
for (i=1;i<=n;i++)
{
jia3(a,b,c);
memcpy(a,c,sizeof(int)*lmax);
}
output(a);
for (i=1;i<=n;i++)
{
jian3(a,b,c);
memcpy(a,c,sizeof(int)*lmax);
}
output(a);
}
}
void examinejian4()
{
int a[lmax],b,n,i;
char s[lmax*nw];
while (scanf("%s%d%d",s,&b,&n))
{
chgstn(s,a);
for (i=1;i<=n;i++)
{
jia4(a,b);
}
output(a);
for (i=1;i<=n;i++)
{
jian4(a,b);
}
output(a);
}
}
void examinechu()
{
int a[lmax],b[lmax],c[lmax];
char s[lmax*nw];
while (scanf("%s",s))
{
chgstn(s,a);
scanf("%s",s);
chgstn(s,b);
chu(a,b,c);
output(a);
output(c);
}
}
void examinechu2()
{
int a[lmax],b[lmax],c[lmax],d[lmax];
char s[lmax*nw];
while (scanf("%s",s)!=EOF)
{
chgstn(s,a);
scanf("%s",s);
chgstn(s,b);
chu2(a,b,c,d);
output(c);
output(d);
}
}
void examinechu4()
{
int a[lmax],c[lmax],d[lmax],b;
char s[nw*lmax];
while (scanf("%s%d",s,&b)!=EOF)
{
chgstn(s,a);
chu4(a,b,c,d);
output(c);
output(d);
}
}
int main()
{
// 以下用来检测各函数的正确性
jiecheng(10000);
// examinechenfang();
// examinejia();
// examinejia2();
// examinejia3();
// examinejia4();
// examinejian();
// examinejian2();
// examinejian3();
// examinejian4();
// examinechu();
// examinechu2();
// examinechu4();
return 0;
}
August 12 #include <stdio.h>
int extended_euclid(int a,int b,int &x,int &y)
/*
d=gcd(a,b)=ax+by (x,y可能为0或负数);
输入整数a、b，返回gcd(a，b)和对应等式ax+by中的x,y;
详细证明见《黑书》P63
*/
{
int t1,t2;
if (b==0)
{
x=1;
y=0;
return a;
}else
{
t1=extended_euclid(b,a%b,x,y);
t2=x;
x=y;
y=t2-(a/b)*y;
return t1;
}
}
int china(int a[],int b[],int n)
/*
c≡a[i](mod b[i]);
b[i]>0;
b[i]与b[j]互质(i!=j);
求a;
详细证明见《黑书》P69
*/
{
int t2,t1,t,i,x,y;
t=1;
for (i=0;i<n;i++)
{
t*=b[i];
}
t2=0;
for (i=0;i<n;i++)
{
t1=t/b[i];
extended_euclid(b[i],t1,x,y);
t2=(t2+a[i]*t1*(y%b[i]))%t;
}
if (t2>0)
return t2;
else
return t2+t;//因为b[]互质，所以t为他们的最小公倍数
}
int main()
{
int i,n,a[100],b[100];
while (scanf("%d",&n)!=EOF)
{
for (i=0;i<n;i++)
scanf("%d%d",&a[i],&b[i]);
printf("%d\n",china(a,b,n));
}
return 0;
} August 11 #include <stdio.h>
int extended_euclid(int a,int b,int &x,int &y)
/*
d=gcd(a,b)=ax+by (x,y可能为0或负数);
输入整数a、b，返回gcd(a，b)和对应等式ax+by中的x,y;
详细证明见《黑书》P63
*/
{
int t1,t2;
if (b==0)
{
x=1;
y=0;
return a;
}else
{
t1=extended_euclid(b,a%b,x,y);
t2=x;
x=y;
y=t2-(a/b)*y;
return t1;
}
}
void modular_linear_equation_solver(int a,int b,int n)
/*
ax≡b(mod n)或ax+ny=b的整数解
详解见《黑书》P64
*/
{
int d,x,y,e,i,t;
d=extended_euclid(a,n,x,y);
if (b%d>0)
{
printf("No answer\n");
}else
{
e=x*(b/d)%n;
if (e<0) e+=n;
for (i=0;i<d;i++)
{
t=(e+i*(n/d))%n;
printf("%d\t",t);
}
printf("\n");
}
}
int main()
{
int a,b,n;
while (scanf("%d%d%d",&a,&b,&n)!=EOF)
{
modular_linear_equation_solver(a,b,n);
}
return 0;
} #include <stdio.h>
int extended_euclid(int a,int b,int &x,int &y)
/*
d=gcd(a,b)=ax+by (x,y可能为0或负数);
输入整数a、b，返回gcd(a，b)和对应等式ax+by中的x,y;
详细证明见《黑书》P63
*/
{
int t1,t2;
if (b==0)
{
x=1;
y=0;
return a;
}else
{
t1=extended_euclid(b,a%b,x,y);
t2=x;
x=y;
y=t2-(a/b)*y;
return t1;
}
}
int main()
{
int a,b,x,y,t;
while (scanf("%d%d",&a,&b)!=EOF)
{
t=extended_euclid(a,b,x,y);
printf("gcd(%d,%d)=%d*%d+%d*%d=%d\n",a,b,a,x,b,y,t);
}
return 0;
} /*
ZOJ-1986 -Bridging Signals;
http://acm.zju.edu.cn/show_problem.php?pid=1986
求最大;
DP + 二分;
空间复杂度O(n),时间复杂度O(nlogn);
PS:此法只能求最长不下降子序列的元素个数，无法得到具体序列;
*/
#include <stdio.h>
int a[40000];
int lsearch(int m,int p,int q)//二分查找
{
int t;
while (p<=q)
{
t=(p+q)/2;
if (a[t]<=m)
{
p=t+1;
}else
{
if (t-1<0||a[t-1]<=m)
return t;
else
q=t-1;
}
}
return -1;
}
int main()
{
int ncase,i,n,p,j,cases;
scanf("%d",&ncase);
for (cases=1;cases<=ncase;cases++)
{
scanf("%d",&n);
for (i=0;i<n;i++)
scanf("%d",&a[i]);
j=0;
for (i=1;i<n;i++)
{
if (a[i]<a[0])
{
a[0]=a[i];
}else if (a[i]>=a[j])
{
j++;
a[j]=a[i];
}else
{
p=lsearch(a[i],0,j);
a[p]=a[i];
}
}
printf("%d\n",j+1);
}
return false;
}
|
Tools 
Help
