noip2012普及组解题报告已知正整数是两个不同的质数乘积试求出较大那个

Noip20121.质因数分解已知正整数n输入文件名为prime.in。输入只有一行，包含一个正整数n输出文件名为prime.out。输出只有一行，包含一个正整数p，prime.in 对于60%的数据，6≤n≤1000对于100%的数据，6≤n≤2*10^9【算法分析】算法1解根据”对于60%的数据，6≤n≤1000”，1trunc(sqrt(nn算法2筛选根据”对于100%的数据，6≤n≤2*10^9trunc(sqrt(2*10^9))<50000，可用筛选法求解，其他同算法1。期望得分：100实际得分：1003模拟法3分：100实际得分：100（1）算法2：usingnamespacestd;shortpr[50000]={0};intmain(){ifstreamfin("prime.in");ofstreamfout("prime.out");intn,maxi=1;for(inti=2;i<=(int)sqrt(n);i++){for(intj=i*2;j<=(int)sqrt(n);j+=i){}}}return0;}算法3：usingnamespacestd;intn;intmain(){for(inti=2;i<=44721;i++)if(n%i==0){cout<<n/i<<endl;break;}return0;}藏宝楼的门口竖着一个木板，上面写有几个大字：寻宝说明书。说明书的内容如下：藏宝楼共有N+1层，最上面一层是顶层，顶层有一个房间里面藏着宝藏。除了顶层外，藏宝楼另有N层，每层的楼梯，每层楼的楼梯设计可能不同。每个房间里有一个指示牌，指示牌上有一个数字x，表示从这个房间开始按逆时针方向选择第x个有楼梯的房间（k，从该房间上楼，上楼后到达上一层的k2，则按逆时针方向开始尝试，找到第2个有楼梯的房间，从该房间上楼。（即每层第一个进入输入文件为treasure.in第一行2个整数N和M，之间用一个空格隔开。N表示除了顶层外藏宝楼共N层楼，M表示除顶层外每层楼有M个房间。接下来N*M行，每行两个整数，之间用一个空格隔开，每行描述一个房间内的情况，其中第(i-1)*M+j行表示第i层j-1号房间的情况（i=1,2,…,N；j=1,2,…,M。第一个整数表示该房间是否有楼梯通往上一层（0表示没有，1表示有注意，从j号房间的楼梯爬到上一层到达的房间一定也是j示从藏宝楼底层的几号房间进入开始寻宝（注：房间编号从0开始。输出文件名为treasure.out会很大，请输出对20123取模的结果即可。treasure.in23120314011512150124；012首先进入第一层（底层）的1号房间，记下指示牌上的数字为3，然后从这个房间开始，沿逆时针方向选择第3个有楼梯的房间2号房间进入，上楼后到达第二层的2号房间，记下指示牌上的数字为2，由于当前房间本身有楼梯通向上层，该房间作为第一个有楼梯的房间。因此，此时沿逆时针方向选择第2个有楼梯的房间即为1号房间，进入后上楼梯到达顶层。这时把上述记下的指示牌上的数字加起来，即3+2=5，所以打开宝箱的密钥就是5。对于100%数据，有0<N≤10000，0<M≤100，0<x≤1,000,0001期望得分：50实际得分：50x算法1a:array[1..10000,0..100,1..2]of ,1..2]offorJ:=1tom*ndobeginfori:=1tondoforj:=1tomdoa[i,j-1,1]:=b[(i-a[i,j-1,2]:=b[(i-fori:=1tondoj:=0;t:=t-whilej<>xdot:=(t+1)modifa[i,t,1]=1thenj:=j+1;wrin(smod20123);2a:array[1..10005,1..105,1..2]oflongint;s:array[1..10005]oflongint;fori:=1tondoforj:=1tomdox:=(xmodm)+1;fori:=1tondoans:=(ans+a[i,x,2])mod20123;ifi=nthenbreak;a[i,x,2]:=a[i,x,2]modifa[i,x,2]=0thena[i,x,2]:=s[i];whiley<a[i,z,2]dobeginx:=(xmodm)+1;摆花的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共m盆。通过调查顾客的喜好，列出了顾客最喜欢的n种花，从1到n标号。为了在门口展出种花，规定第i种花过ai盆，摆花时同一种花放在一起，且不同种类的花需按标号的从小到大的顺序依输入文件flower.in，共2第一行包含两个正整数n和m，第二行有n个整数，每两个整数之间用一个空格隔开，依次表示a1、a2、……an输出文件名为flower.out。输出只有一行，一个整数，表示有多少种方案。注意：因为方案数可能很多，请输出方案数对 【输入输出样例1】flower.inflower.out2322(1，1，1，2)，(1，1，2，2)12对于20%数据，有对于50%数据，有对于100%数据，有0<n≤100，0<m≤100，0≤ai≤100算法120%0<n≤8，0<m≤8，0≤ai≤8；”问题的解法。期望得分：20实际得分算法2动态规划三种循环进行动态转移方程：f[i,j]:=(f[i,j]+f[i-1,j-k])mod 个最简单的01背包问题，只不过要看清题意，即可实现算法。期望得分：100实际得分算法1a,b,f:array[0..100]ofinteger; fori:=1tondofori:=1tomif(n<=8)and(m<=8)thenbeginwhilea[0]=0do forj:=1tom-1ifa[j]>a[j+1]thenbeginiftthenbeginforj:=1tomdoforj:=1tonif(f[j]>b[j])thenbeginiftthenl:=(l+1)mod whilea[k]=ndo k:=k-elsebeginforj:=1tondol:=l*b[j]mod l:=ldiv(m-n+1);2a:array[1..100]oflongint;f:array[0..100,0..100]oflongint;fori:=1tondoread(a[i]);fori:=1tondoforj:=0tomdofork:=0toa[i]doifj-k>=0then 文化之旅【问题描述】有一位使者要各国，他每到一个国家，都能学到一种文化，但他不愿意学习任何一种文化超过一次（即如果他学习了某种文化，则他就不能到达其他有这种文化的国家。不的起点和终点（在起点和终点也会学习当地的文化输入文件culture.in第一行为五个整数N，K，M，S，T，（国家编号为1到N，文化种数（文化编号为1到K号（保证S不等于T；第二行为N个整数，每两个整数之间用一个空格隔开，其中第i个数Ci，表示国家i文化为CiK行，每行Ki行的第j个数为aij，aij=1表示文化i排斥外来文化j（i等于j时表示排斥相同文化的外来人，aij=0表示不排斥（注意i排斥j并不保证j一定也排斥i。接下来的M行，每行三个整数u，v，d，每两个整数之间用一个空格隔开，表示国家u与国vd（uv。输出文件名为culture.out最少需要走的距离数（如果无解则输出-1。【输入输出样例1】culture.inculture.out12011012-由于到国家2必须要经过国家1，而国家2的文明却排斥国家1的文明，所以不可能到达国家2。信息学联赛（NOIP2012）复赛普及组第6页共6页【输入输出样例2culture.in221112010012路线为1->2。对于20%的数据，有2≤N≤8，K≤5；对于50%的数据，有2≤N≤20，K≤8；对于70%的数据，有2≤N≤100，K≤10；对于100%的数据，有2≤N≤100，1≤K≤100，1≤M≤N2，1≤ki≤K，1≤u,v≤N，1≤d≤1000，S≠T，1≤S,T≤N。算法1DFS+剪枝，不考虑-1：70实际得分：90算法2Dijkstra,Spfa1：70实际得分：100算法33：50实际得分算法1programculture;c:array[1..100]oflongint;a:array[1..100,1..100]oflongint;w:array[1..100,1..100]oflongint;ok:array[1..100]ofboolean;functioncan(i:longint):boolean;forj:=1tonifok[j]and(a[c[i],c[j]]=1)thenexit(false);proceduredfs(now,ans:longint);ifnow=tthenifmin=-1thenelseifans<minthen

if(ans>=min)and(min<>-1)thenexit;if(notok[i])and(w[now,i]<>0)and(c[now]<>c[i])andcan(i)thenbeginfori:=1tondoif(notok[i])and(i<>t)and(w[now,i]<>0)and(c[now]<>c[i])andcan(i)fori:=1tondoread(c[i]);fori:=1tokdoforj:=1tokdoread(a[i,j]);fori:=1tomdobeginw[u,v]:=d;w[v,u]:=d;ok[s]:=true;min:=-1;ans:=0;2ch,dis,pa,c:array[1..100]oflongint;ch1,ch2,pai:array[1..100,1..100]oflongint;bo:array[1..100,1..100]ofboolean;ins,boo:array[1..100]ofboolean;functioncmp(a,b:longint):boolean;vari:longint;fori:=1topa[c[b]]ifbo[a,pai[c[b],i]]=truethenprocedurespfa;de:array[1..100]oflongint;whilehead<>taildo head:=(headmodn)+1;fori:=1toch[de[head]]ifcmp(de[head],ch1[de[head],i])thenifboo[c[ch1[de[head],i]]]thenifdis[de[head]]+ch2[de[head],i]<dis[ch1[de[head],i]]then forj:=1tokdoifins[ch1[de[head],i]]=falsethenbegintail:=(tailmodn)+1;fori:=1tondoread(c[i]);fori:=1tokdoforj:=1tokdobeginifx=1thenbeginfori:=1tomdobeginfori:=1topa[c[t]]dofori:=1tondodis[i]:= ifdis[t]= elsewrin(dis[t]);3culture:array[1..100]ofinteger;graph:array[1..100,1..100]ofinteger;refuse:array[1..100,1..100]of0..1;procedurefile_open;procedurefile_close;fori:=1tondofori:=1tokdoforj:=1tokdofori:=1tondoforj:=1tondofor