有关ACM算法的一道题，请各位大牛帮帮忙！！！_百度知道
有关ACM算法的一道题，请各位大牛帮帮忙！！！
又到学期末，小明迎来了又一次的期末考试。虽然每学期都要考试，但是这次期末考试对小明来说意义重大。因为小明爱慕已久的女神说，如果小明这次考了全班前三名就做他女朋友。虽说小明没有十足的信心，但是女神的话不能不听啊。
考完试后，小明拿到...
for(i=1;i&b+1;,&a[i]);0)
s++; }return 0;} 这是我写的代码，在vc 6.0上运行正常;%d\n&
printf(& int a[1010]; scanf(&
for(i=1;%d&quot#include &,&n); for(i=n;i++)
scanf(&i&b+1;i++)
{if(a[i]-a[c]&%d&quot.h&int main(){ int n,i,b,c,s=0 ;i&0;i--) {
scanf(&%d%d&;,s)
我有更好的答案
。直接拿小明的分数 遍历一遍 跟其他分数比较一下不就好了吗。。。for(i=n;i&0;i--){scanf(&quot。。 懂了吗;i&b+1;i++)scanf(&%d&;%d%d&quot根本没什么算法啊;,&b;for(i=1;i&b+1;i++){if(a[i]-a[c]&gt,&a[i]);
for(i=1。。,&c)。。;}你 里面的for 循环 是用 i
外面for也用i;0)s++。。
我知道啊，但是vc 6.0上运行正常，但是acm系统运行出错，消息上面有，不知道为什么有那么多1和浪费那么多时间
以后 这种问题要自己找， 实在找不到 再来问， 找问题对自己的提升很大。我以前通宵刷题的时候， 一道题 卡1,2天都很正常。 呵呵，不过已经是好久的以前的事情了。还是挺怀念的
我就是不明白，在VC运行结果正常，在ACm系统就不正常，一直想不明
你代码 本来就是错的啊， ACM系统里面 有很多组样例， 而你自己只跑了一组样例而已
采纳率：43%
不是很明显吗。。。你把下面printf(&%d\n&quot。。这个题最简单的算法，就是排序。最还在用的时候定义 。，你要习惯这一点;,s); 上面一行就行了。还有就是循环变量多次使用，然后找到小明的位置i，结果就是i 数组最好还是从0开始;s=0;放到循环里面去了。放到return 0
我试过不行，它要输入几组的。你试下在vc运行我的看看，正常。但是网上的系统就同上图出错，好烦。
不行的原因，上一位已经说了啊。就是i的问题，你把它多次使用了。外层循环用i了。内层就要用不同的变量。
我也谢谢你，最后是你让我明白原因的。但是只能给一个，如果还要分的话，我出个简单计算题，再给分你吧。
为您推荐：
其他类似问题
acm的相关知识
换一换
回答问题，赢新手礼包君，已阅读到文档的结尾了呢~~
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口关于编程大赛的一道题目，一个正整数有可能可以被表示为n(n&=2)个连续正整数之和，找出这样的数并输出！_百度知道
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。
关于编程大赛的一道题目，一个正整数有可能可以被表示为n(n&=2)个连续正整数之和，找出这样的数并输出！
题目描述：一个正整数有可能可以被表示为n(n&=2)个连续正整数之和，如：
15=1+2+3+4+5
请编写程序，根据输入的任何一个正整数，找出符合这种要求的所有连续正整数序列。
例如：输入15，则输出
15=1+2+3+4+5
i;&a&%d不能被表示成n连续正整数之和\n&quot.baidu,int(a+i))./zhidao/wh%3D600%2C800/sign=75070faf0cdc729d0475ba/f3d3572c11dfa9ecd0f for(n=2;,input):设：an=a+(n-1)*d&a;}<img class="ikqb_img" src="http，a实质是整数，那么强制转化类型不影响结果
for(i=1;i++)
printf(&（这里d=1）a1=aan=a+n-1sn=(a1+an)n/2=(2a-1+n)/2再回到这个编程上来：我们的输入数据其实就是//flag初始为0，通过上面的循环，如果有满足的在则不为0，为0则说明不能写成等差数列
printf(&&nbsp，需要找到以a开始的n个连续的递增数列使得和为sn。这里我们可以用循环来判定，给定一个n，sn已知;0)//如果为整整数，则满足要求
printf(&%d=%d&quot,&input);n++) {
a=(2*input+n-n*n)/(2.0*n);input://h，就可以求出a，如果a为正整数那么就可以找到等差数列的首项，加上n给定，d=1，那么就可以写出这个和式子;+%d&。代码如下，装换类型
printf(&\n&);
flag++;//flag记录满足要求的数列数
} if(flag==0)&nbsp,n;//等差数列的其他项也为整数，a+i实质是整数：#include&stdio.h&gt://h;//求的首项
if(int(a)==a&void&main(){ int&nbsp, float&i&=n-1; printf(&输入判断的整数:\n&); scanf(&%d&：先讲数学;&nbsp.jpg" esrc="http这个问题看起来不是很简单，需要设计一个算法;n&=input
采纳率：56%
来自团队：
为您推荐：
其他类似问题
正整数的相关知识
&#xe675;换一换
回答问题，赢新手礼包&#xe6b9;我分到的是模4余0和余1的题目
int main()
cout&&&Hello World!&&&
int main()
scanf(&%d&, &f);
printf(&Celsius = %d\n&, 5*(f-32)/9);
L1-005. 考试座位号
代码长度限制
每个PAT考生在参加考试时都会被分配两个座位号，一个是试机座位，一个是考试座位。正常情况下，考生在入场时先得到试机座位号码，入座进入试机状态后，系统会显示该考生的考试座位号码，考试时考生需要换到考试座位就座。但有些考生迟到了，试机已经结束，他们只能拿着领到的试机座位号码求助于你，从后台查出他们的考试座位号码。
输入&#26684;式：
输入第一行给出一个正整数N（&=1000），随后N行，每行给出一个考生的信息：“准考证号 试机座位号 考试座位号”。其中准考证号由14位数字组成，座位从1到N编号。输入保证每个人的准考证号都不同，并且任何时候都不会把两个人分配到同一个座位上。
考生信息之后，给出一个正整数M（&=N），随后一行中给出M个待查询的试机座位号码，以空&#26684;分隔。
输出&#26684;式：
对应每个需要查询的试机座位号码，在一行中输出对应考生的准考证号和考试座位号码，中间用1个空&#26684;分隔。
输入样例：
输出样例：
建立第二个数和第一个数的映射以及第二个数和第三个数的映射
const int maxn = 1010;
int mmap1[maxn];
string mmap2[maxn];
int main()
scanf(&%d&, &n);
rep(i, n){
cin&&s;scanf(&%d%d&, &x, &y);
mmap1[x] = mmap2[x] =
scanf(&%d&, &m);
rep(i, m){
scanf(&%d&, &x);
printf(&%s %d\n&, mmap2[x].c_str(), mmap1[x]);
L1-008. 求整数段和
代码长度限制
给定两个整数A和B，输出从A到B的所有整数以及这些数的和。
输入&#26684;式：
输入在一行中给出2个整数A和B，其中-100&=A&=B&=100，其间以空&#26684;分隔。
输出&#26684;式：
首先顺序输出从A到B的所有整数，每5个数字占一行，每个数字占5个字符宽度，向右对齐。最后在一行中输出全部数字的和。
输入样例：
输出样例：
这题一是注意%5d的运用，二是注意换行，尤其是输出完之后的额外一次换行
int main()
int l,r; scanf(&%d%d&, &l, &r);
For(i, l, r){
printf(&%5d&, i);
if ((i-l) % 5 == 4)
if ((r-l) % 5 != 4)
printf(&Sum = %d\n&, (l+r) * (r-l+1) / 2);
L1-009. N个数求和
代码长度限制
本题的要求很简单，就是求N个数字的和。麻烦的是，这些数字是以有理数“分子/分母”的形式给出的，你输出的和也必须是有理数的形式。
输入&#26684;式：
输入第一行给出一个正整数N（&=100）。随后一行按&#26684;式“a1/b1 a2/b2 ...”给出N个有理数。题目保证所有分子和分母都在长整型范围内。另外，负数的符号一定出现在分子前面。
输出&#26684;式：
输出上述数字和的最简形式 —— 即将结果写成“整数部分 分数部分”，其中分数部分写成“分子/分母”，要求分子小于分母，且它们没有公因子。如果结果的整数部分为0，则只输出分数部分。
输入样例1：
2/5 4/15 1/30 -2/60 8/3
输出样例1：
输入样例2：
输出样例2：
输入样例3：
1/3 -1/6 1/8
输出样例3：
一个很不好做的模拟题，首先要写一个比较简单的分数类，重载一个加法
struct frac{
frac(int _up = 0, int _down = 0) : up(_up), down(_down){}
frac operator + (const frac& b){
tmp.down = down * b.
tmp.up = up * b.down + down * b.
int gcd1 = gcd(abs(tmp.up), abs(tmp.down));
tmp.down /= gcd1; tmp.up /= gcd1;
这当中还要用到数论中的gcd
然后读入进行模拟，这题的输出要分5种情况
1、答案是0
2、分母是1
4、正假分数
5、负假分数
对于第五种情况，题面没有说清楚应该怎么输出，比如-11/3是输出-4&#43;1/3还是-3-2/3呢？
这个经过探索，应该用第二种处理方式
int gcd(int a, int b){
return a % b == 0 ? b : gcd(b, a % b);
struct frac{
frac(int _up = 0, int _down = 0) : up(_up), down(_down){}
frac operator + (const frac& b){
tmp.down = down * b.
tmp.up = up * b.down + down * b.
int gcd1 = gcd(abs(tmp.up), abs(tmp.down));
tmp.down /= gcd1; tmp.up /= gcd1;
frac a[1000];
int main(){
scanf(&%d&, &n);
rep(i, n) scanf(&%d/%d&, &a[i].up, &a[i].down);
ans = frac(0,1);
ans = ans + a[i];
if (ans.up == 0) printf(&0&);
else if (ans.down == 1) printf(&%d&, ans.up);
else if (abs(ans.up) & ans.down) printf(&%d/%d&, ans.up, ans.down);
else if (ans.up & 0){
int z1 = ans.up / ans.
ans.up %= ans.
printf(&%d %d/%d&, z1, ans.up, ans.down);
ans.up = -ans.
int z1 = ans.up / ans.
ans.up %= ans.
printf(&-%d %d/%d&, z1, ans.up, ans.down);
L1-012. 计算指数
代码长度限制
真的没骗你，这道才是简单题 —— 对任意给定的不超过10的正整数n，要求你输出2n。不难吧？
输入&#26684;式：
输入在一行中给出一个不超过10的正整数n。
输出&#26684;式：
在一行中按照&#26684;式“2^n = 计算结果”输出2n的&#20540;。
输入样例：
输出样例：
记得用位运算。
int main()
scanf(&%d&, &n);
printf(&%d^%d = %d&, 2, n, 1&&n);
int main()
scanf(&%d&, &n);
int sum = 0, mul = 1;
rep1(i, n){
printf(&%d\n&, sum);
L1-016. 查验身份证
代码长度限制
一个合法的身份证号码由17位地区、日期编号和顺序编号加1位校验码组成。校验码的计算规则如下：
首先对前17位数字加权求和，权重分配为：{7，9，10，5，8，4，2，1，6，3，7，9，10，5，8，4，2}；然后将计算的和对11取模得到&#20540;Z；最后按照以下关系对应Z&#20540;与校验码M的&#20540;：
Z：0 1 2 3 4 5 6 7 8 9 10
M：1 0 X 9 8 7 6 5 4 3 2
现在给定一些身份证号码，请你验证校验码的有效性，并输出有问题的号码。
输入&#26684;式：
输入第一行给出正整数N（&= 100）是输入的身份证号码的个数。随后N行，每行给出1个18位身份证号码。
输出&#26684;式：
按照输入的顺序每行输出1个有问题的身份证号码。这里并不检验前17位是否合理，只检查前17位是否全为数字且最后1位校验码计算准确。如果所有号码都正常，则输出“All passed”。
输入样例1：
输出样例1：
输入样例2：
输出样例2：
All passed
模拟题，那些权重分配用数组初始化是最方便的。
顺带一提，第一个权重分配其实不用都抄，是有规律的
char s[100];
int map1[] = {7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2};
char map2[] = &10X&;
int main()
scanf(&%d&, &n);
int flag = 1;
rep(i, n){
scanf(&%s&, s);
int sum = 0;
rep(i, 17) sum += map1[i] * (s[i] - '0');
sum %= 11;
if (s[17] != map2[sum]){
printf(&%s\n&, s);
if (flag) printf(&All passed\n&);
L1-017. 到底有多二
代码长度限制
一个整数“犯二的程度”定义为该数字中包含2的个数与其位数的比&#20540;。如果这个数是负数，则程度增加0.5倍；如果还是个偶数，则再增加1倍。例如数字“-”是个11位数，其中有3个2，并且是负数，也是偶数，则它的犯二程度计算为：3/11*1.5*2*100%，约为81.82%。本题就请你计算一个给定整数到底有多二。
输入&#26684;式：
输入第一行给出一个不超过50位的整数N。
输出&#26684;式：
在一行中输出N犯二的程度，保留小数点后两位。
输入样例：
输出样例：
char s[100];
int main()
scanf(&%s&, s);
int len = s[0] == '-' ? strlen(s) - 1 : strlen(s);
double base = 1;
if (s[0] == '-') base *= 1.5;
if ( (s[strlen(s)-1] - '0') % 2 == 0) base *= 2;
int cnt = 0;
rep(i, strlen(s)) if ( (s[i] - '0') == 2) ++
base = base * cnt /
printf(&%.2f%\n&, base * 100);
L1-020. 帅到没朋友
代码长度限制
当芸芸众生忙着在朋友圈中发照片的时候，总有一些人因为太帅而没有朋友。本题就要求你找出那些帅到没有朋友的人。
输入&#26684;式：
输入第一行给出一个正整数N（&=100），是已知朋友圈的个数；随后N行，每行首先给出一个正整数K（&=1000），为朋友圈中的人数，然后列出一个朋友圈内的所有人——为方便起见，每人对应一个ID号，为5位数字（从0），ID间以空&#26684;分隔；之后给出一个正整数M（&=10000），为待查询的人数；随后一行中列出M个待查询的ID，以空&#26684;分隔。
注意：没有朋友的人可以是根本没安装“朋友圈”，也可以是只有自己一个人在朋友圈的人。虽然有个别自恋狂会自己把自己反复加进朋友圈，但题目保证所有K超过1的朋友圈里都至少有2个不同的人。
输出&#26684;式：
按输入的顺序输出那些帅到没朋友的人。ID间用1个空&#26684;分隔，行的首尾不得有多余空&#26684;。如果没有人太帅，则输出“No one is handsome”。
注意：同一个人可以被查询多次，但只输出一次。
输入样例1：
输出样例1：
输入样例2：
输出样例2：
No one is handsome
一是注意注意%05d的运用
二是每个人至多被查询一次
三是怎么输出，因为行末要求没有空&#26684;的，我的做法就是输出第一个答案的时候不输出空&#26684;，其他数先输出一个空&#26684;
int vis[100010];
int main()
scanf(&%d&, &n);
rep(i, n){
int k,x; scanf(&%d&, &k);
rep(i, k){
scanf(&%d&, &x);
if (k != 1)vis[x] = 1;
scanf(&%d&, &m);
int flag = 0;
rep(i, m) {
scanf(&%d&, &x);
if (vis[x] == 0){
vis[x] = 1;
if (flag) printf(& &);
printf(&%05d&, x);
if (flag == 0) printf(&No one is handsome\n&);
int main()
rep(i, 3) printf(&I'm gonna WIN!\n&);
int main()
scanf(&%d&, &x);
printf(&%d\n&, (x+1) % 7 + 1);
L2-001. 紧急救援
代码长度限制
作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。
输入&#26684;式：
输入第一行给出4个正整数N、M、S、D，其中N（2&=N&=500）是城市的个数，顺便假设城市的编号为0~(N-1)；M是快速道路的条数；S是出发地的城市编号；D是目的地的城市编号。第二行给出N个正整数，其中第i个数是第i个城市的救援队的数目，数字间以空&#26684;分隔。随后的M行中，每行给出一条快速道路的信息，分别是：城市1、城市2、快速道路的长度，中间用空&#26684;分开，数字均为整数且不超过500。输入保证救援可行且最优解唯一。
输出&#26684;式：
第一行输出不同的最短路径的条数和能够召集的最多的救援队数量。第二行输出从S到D的路径中经过的城市编号。数字间以空&#26684;分隔，输出首尾不能有多余空&#26684;。
输入样例：
20 30 40 10
输出样例：
这题是最短路的一个拓展。
首先要去一个靠谱的网站学习最短路，我推荐VisuAlgo
用一种最短路算法得到结果，比如叫dis数组，dis[u]表示从起点到u的最短路
这样就有一棵隐式的最短路径树出来了，d[v] = d[u] &#43; dis(u,v)成立则(u,v)有边，容易知道这是一个有向无环图
对于最短路条数的计数，在这个树上进行dp，dp[u] = sum(dp[v]) (u,v在最短路径树上有边) &注意起点的dp&#20540;为0
救援队最多也是类&#20284;的做法，设val[u]为u点的救援队数量，dp[u] = max(dp[v]) &#43; val[u]); (u,v在最短路径树上有边) dp的同时记录下那个v，这样就能输出路径了。
我们觉得最短路的条数可能是阶乘级的，但斗胆没有写大整数，阶乘级的答案时间都是个问题
const int maxn = 550;
typedef pair&int,int&
struct edge{
& & int v,
& & edge(int _v = 0, int _w = 0) : v(_v), w(_w){}
vector&edge& g[maxn];
int dis[maxn], v[maxn], d2[maxn], n, m, st, ed, prv[maxn];
ll d[maxn];
vector&int&
void add1(int u, int v, int w){
& & g[u].push_back(edge(v, w));
& & g[v].push_back(edge(u, w));
void dijkstra(int s){
& & priority_queue&pii, vector&pii&, greater&pii& &&
& & rep(i, n) dis[i] =
& & dis[s] = 0;&
& & q.push(make_pair(dis[s], s));
& & while(!q.empty()){
& & & & pii tmp = q.top(); q.pop();
& & & & int u = tmp.
& & & & if (dis[u] != tmp.first)
& & & & rep(i, g[u].size()){
& & & & & & edge e = g[u][i];
& & & & & & if (dis[e.v] & dis[u] + e.w){
& & & & & & & & dis[e.v] = dis[u] + e.w;
& & & & & & & & q.push(make_pair(dis[e.v], e.v));
& & & & & & }
//计算最短路径的条数&
ll dp(int u){
& & if (d[u] != -1) return d[u];
& & ll &ans = d[u];
& & ans = 0;
& & if (u == st) ans = 1;
& & & & rep(i, g[u].size()){
& & & & & & edge e = g[u][i];
& & & & & & if (dis[u] == dis[e.v] + e.w) ans += dp(e.v);
//计算点权和的最大值&
int dp2(int u){
& & if (d2[u] != -1) return d2[u];
& & int &ans = d2[u];
& & ans = v[u];
& & int tmp =
& & rep(i, g[u].size()){
& & & & edge e = g[u][i];
& & & & if (dis[u] == dis[e.v] + e.w && dp2(tmp) & dp2(e.v))
& & & & tmp = e.v;
& & if (u == st) prv[u] = -1;
& & else { prv[u] = ans += dp2(tmp); }
int main()
& & scanf(&%d%d%d%d&, &n, &m, &st, &ed);
& & rep(i, n) scanf(&%d&, v + i);
& & rep(i, m){
& & & & int u, v, scanf(&%d%d%d&, &u, &v, &w);
& & & & add1(u, v, w);
& & dijkstra(st);
& & memset(d, -1, sizeof(d));
& & memset(d2, -1, sizeof(d2));
& & printf(&%lld %d\n&, dp(ed), dp2(ed));
& & int now =
& & while(now != -1){
& & & & ans.push_back(now);
& & & & now = prv[now];
& & printf(&%d&, ans[ans.size()-1]);
& & for(int i = ans.size()-2; i &= 0; i--)printf(& %d&, ans[i]);
& & return 0;
L2-004. 这是二叉搜索树吗？
代码长度限制
一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点，
其左子树中所有结点的键&#20540;小于该结点的键&#20540;；
其右子树中所有结点的键&#20540;大于等于该结点的键&#20540;；
其左右子树都是二叉搜索树。
所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。
给定一个整数键&#20540;序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。
输入&#26684;式：
输入的第一行给出正整数N（&=1000）。随后一行给出N个整数键&#20540;，其间以空&#26684;分隔。
输出&#26684;式：
如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果，则首先在一行中输出“YES”，然后在下一行输出该树后序遍历的结果。数字间有1个空&#26684;，一行的首尾不得有多余空&#26684;。若答案是否，则输出“NO”。
输入样例1：
8 6 5 7 10 8 11
输出样例1：
5 7 6 8 11 10 8
输入样例2：
8 10 11 8 6 7 5
输出样例2：
11 8 10 7 5 6 8
输入样例3：
8 6 8 5 10 9 11
输出样例3：
假设左子树更小右子树更大的情况，另一种情况可以类&#20284;地考虑。
以样例为例来说明。
先看样例1，8显然是树根，8后面的6个数是8的左子树或右子树，而左子树里的元素比8小，右子树里的元素大于等于8
可以得出6 5 7这三个元素是左子树里的，另三个是右子树里的。
再看6 5 7，显然6是这个子树的根，5是6的左儿子，7是6的右儿子。
按照这个思路进行递归处理就能完成判断和建树，然后做后序遍历即可。
对于样例3，8的左子树只能到6，但后面5个元素里有比8小的，因此无法构造，按相反顺序做一遍也不行，因此不行。
const int maxn = 1010;
int a[maxn],
vector&int&
bool cmp(int x, int y, int t){
if (t == 0) return x &=
else return x &
//判断a[l,r]是否合法，x=0代表递增的情况，x=1代表递减的情况
bool judge(int l, int r, int x){
if (l &= r)
int key = a[l],
for(k = l + 1; k &= k++)
if (cmp(a[k], key, x))
for(int i = k+1; i &= i++)
if (!cmp(a[i], key, x))
return judge(l+1, k-1, x) && judge(k, r, x);
struct node{
node* ch[2];
node* build(int l, int r, int x){
if (l & r) return NULL;
node* tmp =
int key = a[l],
tmp-&val = tmp-&ch[0] = tmp-&ch[1] = NULL;
if (l == r)
for(k = l + 1; k &= k++)
if (cmp(a[k], key, x))
tmp-&ch[0] = build(l+1, k-1, x);
tmp-&ch[1] = build(k, r, x);
void dfs(node *x){
rep(i, 2) if (x-&ch[i] != NULL) dfs(x-&ch[i]);
ans.push_back(x-&val);
int main()
int flag[2]; node *
scanf(&%d&, &n);
rep1(i, n) scanf(&%d&, &a[i]);
rep(i, 2) flag[i] = judge(1, n, i);
if (flag[0] || flag[1]){
printf(&YES\n&);
rep(i, 2) if (flag[i]) root = build(1, n, i);
dfs(root);
printf(&%d&, ans[0]);
rep1(i, ans.size()-1) printf(& %d&, ans[i]);
}else printf(&NO\n&);
L2-005. 集合相&#20284;度
代码长度限制
给定两个整数集合，它们的相&#20284;度定义为：Nc/Nt*100%。其中Nc是两个集合都有的不相等整数的个数，Nt是两个集合一共有的不相等整数的个数。你的任务就是计算任意一对给定集合的相&#20284;度。
输入&#26684;式：
输入第一行给出一个正整数N（&=50），是集合的个数。随后N行，每行对应一个集合。每个集合首先给出一个正整数M（&=104），是集合中元素的个数；然后跟M个[0, 109]区间内的整数。
之后一行给出一个正整数K（&=2000），随后K行，每行对应一对需要计算相&#20284;度的集合的编号（集合从1到N编号）。数字间以空&#26684;分隔。
输出&#26684;式：
对每一对需要计算的集合，在一行中输出它们的相&#20284;度，为保留小数点后2位的百分比数字。
输入样例：
3 99 87 101
4 87 101 5 87
7 99 101 18 5 135 18 99
输出样例：
这题我采用类&#20284;归并排序的办法进行合并。读入后对每个每个集合进行排序和去重，动态维护两个指针l1和l2，如果a[l1]&a[l2]则l1&#43;&#43;;使用类&#20284;这样的办法进行维护即可
const int maxn = 10010;
int b[60], a[60][maxn], n,&
int main()
& & scanf(&%d&, &n);
& & rep1(i, n){
& & & & scanf(&%d&, b + i);
& & & & rep(j, b[i]) scanf(&%d&, &a[i][j]);
& & & & sort(a[i], a[i] + b[i]);
& & & & b[i] = unique(a[i], a[i] + b[i]) - a[i];
& & scanf(&%d&, &q);
& & rep(kk, q){
& & & & int x, scanf(&%d%d&, &x, &y);
& & & & int cnt0 = 0, l1 = 0, l2 = 0; &//cnt0对相等元素进行计数,l1和l2代表两个指针&
& & & & while(l1 & b[x] || l2 & b[y]){
& & & & & & if (l2 &= b[y] || l1 & b[x] && a[x][l1] & a[y][l2]) ++l1;
& & & & & & else if (l1 & b[x] && a[x][l1] == a[y][l2]){
& & & & & & & & ++cnt0; ++l1; ++l2;
& & & & & & }else ++l2;
& & & & int cnt1 = 0; l1 = l2 = 0; &//cnt1对所有元素进行计数&
& & & & while(l1 & b[x] || l2 & b[y]){
& & & & & & if (l2 &= b[y] || l1 & b[x] && a[x][l1] & a[y][l2]) ++l1;
& & & & & & else if (l1 & b[x] && a[x][l1] == a[y][l2]){
& & & & & & & & ++l1; ++l2;
& & & & & & }else ++l2;
& & & & & & ++cnt1;
& & & & printf(&%.2f%\n&, cnt0 * 100.0 / cnt1);
& & return 0;
L2-006. 树的遍历
代码长度限制
给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键&#20540;都是互不相等的正整数。
输入&#26684;式：
输入第一行给出一个正整数N（&=30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空&#26684;分隔。
输出&#26684;式：
在一行中输出该树的层序遍历的序列。数字间以1个空&#26684;分隔，行首尾不得有多余空&#26684;。
输入样例：
2 3 1 5 7 6 4
1 2 3 4 5 6 7
输出样例：
4 1 6 3 5 7 2
和2-004是一样的思路，这题无需判断正确性
struct node{
node* ch[2];
const int maxn = 10010;
int a[maxn], b[maxn],
node* build(int l1, int r1, int l2, int r2){
if (l1 & r1) return NULL;
if (l1 == r1){
node *t = new node();
t-&val = a[l1];
t-&ch[0] = t-&ch[1] = NULL;
int v = a[r1], m2;
for(m2 = l2; m2 &= r2; m2++) if (b[m2] == v)
node *t = new node();
t-&ch[0] = build(l1, l1 + m2 - l2 - 1, l2, m2 - 1);
t-&ch[1] = build(l1 + m2 - l2, r1 - 1, m2 + 1, r2);
int main(){
root = NULL;
scanf(&%d&, &n);
for(int i = 1; i &= i++) scanf(&%d&, &a[i]);
for(int i = 1; i &= i++) scanf(&%d&, &b[i]);
root = build(1, n, 1, n);
queue&node*& q.push(root);
while(q.size()){
node* t = q.front(); q.pop();
if (t == root) printf(&%d&, t-&val);
else printf(& %d&, t-&val);
if (t-&ch[0] != NULL) q.push(t-&ch[0]);
if (t-&ch[1] != NULL) q.push(t-&ch[1]);
L2-007. 家庭房产
代码长度限制
给定每个人的家庭成员和其自己名下的房产，请你统计出每个家庭的人口数、人均房产面积及房产套数。
输入&#26684;式：
输入第一行给出一个正整数N（&=1000），随后N行，每行按下列&#26684;式给出一个人的房产：
编号 父 母 k 孩子1&... 孩子k&房产套数 总面积
其中&编号&是每个人独有的一个4位数的编号；父&和&母&分别是该编号对应的这个人的父母的编号（如果已经过世，则显示-1）；k（0&=k&=5）是该人的子女的个数；孩子i是其子女的编号。
输出&#26684;式：
首先在第一行输出家庭个数（所有有亲属关系的人都属于同一个家庭）。随后按下列&#26684;式输出每个家庭的信息：
家庭成员的最小编号 家庭人口数 人均房产套数 人均房产面积
其中人均&#20540;要求保留小数点后3位。家庭信息首先按人均面积降序输出，若有并列，则按成员编号的升序输出。
输入样例：
-1 0 2 300
3 34 1 100
1 3 63 1 100
输出样例：
.600 100.000
.750 100.000
const int maxn = 10010;
int n, vis[maxn], cnt_h[maxn], cnt_m[maxn], sum_h[maxn], sum_m[maxn], sum_ch[maxn], fa[maxn];
struct family{
int num, double avg_h, avg_m;
family(int _id = 0, int _num = 0, double _h = 0, double _m = 0) : id(_id), num(_num), avg_h(_h), avg_m(_m){}
vector&family&
int find1(int x){
return fa[x] == x ? x : fa[x] = find1(fa[x]);
void union1(int x, int y){//合并的时候选择id更小的作为父亲
vis[x] = vis[y] = 1;
int fx = find1(x), fy = find1(y);
if (fx & fy) fa[fy] =
else fa[fx] =
int cmp(family x, family y){
if (abs(x.avg_m - y.avg_m) & 1e-7) return x.avg_m & y.avg_m;
return x.id & y.
int main(){
scanf(&%d&, &n);
for(int i = 0; i & 10000; i++) fa[i] =
for(int tt = 0; tt & tt++){
int n1, n2, n3,
scanf(&%d%d%d%d&, &n1, &n2, &n3, &m);
vis[n1] = 1;
if (n2 != -1) union1(n1, n2);
if (n3 != -1)
union1(n1, n3);
for(int i = 0; i & i++){
scanf(&%d&, &x);
union1(n1, x);
scanf(&%d%d&, &cnt_h[n1], &cnt_m[n1]);
for(int i = 0; i & 10000; i++) if (vis[i]){
int fi = find1(i);
sum_h[fi] += cnt_h[i];
sum_m[fi] += cnt_m[i];
sum_ch[fi]++;
for(int i = 0; i & 10000; i++) if (vis[i] == 1 && find1(i) == i)
a.push_back(family(i, sum_ch[i], (double)sum_h[i]/sum_ch[i], (double)sum_m[i]/sum_ch[i]));
sort(a.begin(), a.end(), cmp);
printf(&%d\n&, a.size());
for(int i = 0; i & a.size(); i++)
printf(&%04d %d %.3f %.3f\n&, a[i].id, a[i].num, a[i].avg_h, a[i].avg_m);
并查集。由于要输出id最小的成员，合并的时候将id更小的作为父亲即可
L2-008. 最长对称子串
代码长度限制
对给定的字符串，本题要求你输出最长对称子串的长度。例如，给定&Is PAT&TAP symmetric?&，最长对称子串为&s PAT&TAP s&，于是你应该输出11。
输入&#26684;式：
输入在一行中给出长度不超过1000的非空字符串。
输出&#26684;式：
在一行中输出最长对称子串的长度。
输入样例：
Is PAT&TAP symmetric?
输出样例：
这题可以使用线性的Manacher算法，但因为数据小，我采用平方级暴力做法也通过了。
枚举&对称中心“然后向外扩展，扩展到不能扩展为止，这样做每次枚举是线性的，再加上线性级的枚举对称中心，就是平方级的了。
const int maxn = 1010;
char s[maxn];
int test(int l, int r){
while (l &= 0 && r & len && s[l] == s[r]){
return r - l + 1;
int main(){
fgets(s, maxn, stdin);
len = strlen(s);
int ans = 0;
rep(i, len) ans = max(ans, test(i, i));
rep(i, len-1) ans = max(ans, test(i, i+1));
printf(&%d\n&, ans);
L2-012. 关于堆的判断
代码长度限制
将一系列给定数字顺序插入一个初始为空的小顶堆H[]。随后判断一系列相关命题是否为真。命题分下列几种：
“x is the root”：x是根结点；
“x and y are siblings”：x和y是兄弟结点；
“x is the parent of y”：x是y的父结点；
“x is a child of y”：x是y的一个子结点。
输入&#26684;式：
每组测试第1行包含2个正整数N（&= 1000）和M（&= 20），分别是插入元素的个数、以及需要判断的命题数。下一行给出区间[-1]内的N个要被插入一个初始为空的小顶堆的整数。之后M行，每行给出一个命题。题目保证命题中的结点键&#20540;都是存在的。
输出&#26684;式：
对输入的每个命题，如果其为真，则在一行中输出“T”，否则输出“F”。
输入样例：
46 23 26 24 10
24 is the root
26 and 23 are siblings
46 is the parent of 23
23 is a child of 10
输出样例：
学会堆的操作之后，这题就不困难了。
有两种常见的建堆方式，一种是把所有数都放进去一次维护，另一是加入一个数就维护一次。本题的要求是按第二种方式进行模拟
模拟完成之后，按照题目要求进行判断即可。
这题的读入比较麻烦，我的处理也不够完美，仅供参考。
const int maxn = 2010;
int a[maxn], n, q,
map&int,int&
void insert(int x){
a[++len] =
while(now & 1 && a[now/2] & a[now]){
swap(a[now/2], a[now]);
int main()
scanf(&%d%d&, &n, &q);
rep(i, n){
scanf(&%d&, &x);
insert(x);
rep1(i, len) mmap[a[i]] =
char c = getchar();
rep(kk, q){
char s[100], s1[100],s2[100],s3[100],s4[100];
fgets(s, 100, stdin);
int len = strlen(s), x, y,
if (s[len-2] == 't'){
sscanf(s, &%d&, &x); x = mmap[x];
ans = x == 1;
}else if (s[len-2] == 's'){
sscanf(s, &%d and %d&, &x, &y);
x = mmap[x]; y = mmap[y];
ans = x / 2 == y / 2;
sscanf(s, &%d%s%s%s%s%d&, &x, s1,s2,s3,s4,&y);
x = mmap[x]; y = mmap[y];
if (s2[0] == 't'){
ans = y / 2 ==
ans = x / 2 ==
printf(ans ? &T& : &F&);
L2-013. 红色警报
代码长度限制
战争中保持各个城市间的连通性非常重要。本题要求你编写一个报警程序，当失去一个城市导致国家被分裂为多个无法连通的区域时，就发出红色警报。注意：若该国本来就不完全连通，是分裂的k个区域，而失去一个城市并不改变其他城市之间的连通性，则不要发出警报。
输入&#26684;式：
输入在第一行给出两个整数N（0 & N &=500）和M（&=5000），分别为城市个数（于是默认城市从0到N-1编号）和连接两城市的通路条数。随后M行，每行给出一条通路所连接的两个城市的编号，其间以1个空&#26684;分隔。在城市信息之后给出被攻占的信息，即一个正整数K和随后的K个被攻占的城市的编号。
注意：输入保证给出的被攻占的城市编号都是合法的且无重复，但并不保证给出的通路没有重复。
输出&#26684;式：
对每个被攻占的城市，如果它会改变整个国家的连通性，则输出“Red Alert: City k is lost!”，其中k是该城市的编号；否则只输出“City k is lost.”即可。如果该国失去了最后一个城市，则增加一行输出“Game Over.”。
输入样例：
输出样例：
City 1 is lost.
City 2 is lost.
Red Alert: City 0 is lost!
City 4 is lost.
City 3 is lost.
Game Over.
利用离线思想，即不要求对于每个输入立即给出输出，可以处理所有的输入再一起输出。
将问题倒着考虑，变成一个不断加点求联通快个数的问题，用并查集可以轻松解决。
const int maxn = 510;
vector&int& g[maxn];
int a[maxn], ans[maxn], sz, fa[maxn], n, m, k, vis[maxn];
//sz : 当前联通块个数
int find1(int x){
return x == fa[x] ? x : fa[x] = find1(fa[x]);
void union1(int x, int y){
int fx = find1(x), fy = find1(y);
if (fx != fy){
int main()
scanf(&%d%d&, &n, &m);
for(int i = 0; i & i++){
int u, scanf(&%d%d&, &u, &v);
g[u].push_back(v); g[v].push_back(u);
scanf(&%d&, &k);
for(int i = 0; i & i++) {
vis[i] = 1; fa[i] =
for(int i = 1; i &= i++) {
scanf(&%d&, &a[i]);
vis[a[i]] = 0;
for(int i = 0; i & i++) if (vis[i] == 1)
for(int j = 0; j & g[i].size(); j++) if (vis[g[i][j]] == 1)
union1(i, g[i][j]);
for(int i = i &= 1; i--){
int u = a[i];
sz++; vis[u] = 1;
for(int j = 0; j & g[u].size(); j++) if (vis[g[u][j]] == 1)
union1(u, g[u][j]);
ans[i-1] =
for(int i = 1; i &= i++){
if (ans[i] & ans[i-1]) printf(&Red Alert: &);
printf(&City %d is lost&, a[i]);
if (ans[i] & ans[i-1]) printf(&!&); else printf(&.&);
printf(&\n&);
if (n == k) printf(&Game Over.\n&);
L3-001. 凑零钱
代码长度限制
韩梅梅喜欢满宇宙到处逛街。现在她逛到了一家火星店里，发现这家店有个特别的规矩：你可以用任何星球的硬币付钱，但是绝不找零，当然也不能欠债。韩梅梅手边有104枚来自各个星球的硬币，需要请你帮她盘算一下，是否可能精确凑出要付的款额。
输入&#26684;式：
输入第一行给出两个正整数：N（&=104）是硬币的总个数，M（&=102）是韩梅梅要付的款额。第二行给出N枚硬币的正整数面&#20540;。数字间以空&#26684;分隔。
输出&#26684;式：
在一行中输出硬币的面&#20540; V1&&= V2&&= ... &= Vk，满足条件 V1&&#43; V2&&#43; ... &#43; Vk&=
M。数字间以1个空&#26684;分隔，行首尾不得有多余空&#26684;。若解不唯一，则输出最小序列。若无解，则输出“No Solution”。
注：我们说序列{A[1], A[2], ...}比{B[1], B[2], ...}“小”，是指存在 k &= 1 使得 A[i]=B[i] 对所有 i & k 成立，并且 A[k] & B[k]。
输入样例1：
5 9 8 7 2 3 4 1
输出样例1：
输入样例2：
输出样例2：
No Solution
这题的判断是否有解就是一个背包。
对于方案的输出，我的做法是放弃滚动数组优化，二维的dp数组能很清晰的看到转移的&历史记录&，计算完成后倒着找方案。
由于要求输出字典序最小的方案，我先对每个硬币按照价&#20540;降序排序，倒着找方案的时候找尽可能小的硬币即可。
int d[1], n, m, v[10010];
vector&int&
int cmp(int x, int y){
return x &
int main()
scanf(&%d%d&, &n, &m);
rep1(i, n) scanf(&%d&, &v[i]);
sort(v + 1, v + n + 1, cmp);
rep(i, n+1) d[i][0] = 1;
rep1(i, n){
for(int j = j &= v[i]; j--)
if (d[i-1][j-v[i]] || d[i-1][j]) d[i][j] = 1;
if (d[n][m] == 0) printf(&No Solution\n&);
int now = m, pos =
while(now & 0){
while(d[pos-1][now-v[pos]] == 0) pos--;
ans.push_back(v[pos]);
now -= v[pos]; pos--;
printf(&%d&, ans[0]);
rep1(i, ans.size()-1) printf(& %d&, ans[i]);
L3-008. 喊山
代码长度限制
喊山，是人双手围在嘴边成喇叭状，对着远方高山发出“喂—喂喂—喂喂喂……”的呼唤。呼唤声通过空气的传递，回荡于深谷之间，传送到人们耳中，发出约定俗成的“讯号”，达到声讯传递交流的目的。原来它是彝族先民用来求援呼救的“讯号”，慢慢地人们在生活实践中发现了它的实用价&#20540;，便把它作为一种交流工具世代传袭使用。（图文摘自：/newsshow-8018.html）
一个山头呼喊的声音可以被临近的山头同时听到。题目假设每个山头最多有两个能听到它的临近山头。给定任意一个发出原始信号的山头，本题请你找出这个信号最远能传达到的地方。
输入&#26684;式：
输入第一行给出3个正整数n、m和k，其中n（&=10000）是总的山头数（于是假设每个山头从1到n编号）。接下来的m行，每行给出2个不超过n的正整数，数字间用空&#26684;分开，分别代表可以听到彼此的两个山头的编号。这里保证每一对山头只被输入一次，不会有重复的关系输入。最后一行给出k（&=10）个不超过n的正整数，数字间用空&#26684;分开，代表需要查询的山头的编号。
输出&#26684;式：
依次对于输入中的每个被查询的山头，在一行中输出其发出的呼喊能够连锁传达到的最远的那个山头。注意：被输出的首先必须是被查询的个山头能连锁传到的。若这样的山头不只一个，则输出编号最小的那个。若此山头的呼喊无法传到任何其他山头，则输出0。
输入样例：
输出样例：
这题放在L3有点过了，就是一个普通的无权图最短路，定下起点bfs即可
const int maxn = 10010;
const int inf = 1&&29;
int d[maxn], n, m,
vector&int& g[maxn];
int main()
scanf(&%d%d%d&, &n, &m, &qq);
rep(i, m){
int u, scanf(&%d%d&, &u, &v);
g[u].push_back(v); g[v].push_back(u);
rep(kk, qq){
scanf(&%d&, &s);
queue&int& q.push(s);
rep1(i, n) d[i] = d[s] = 0;
while(q.size()){
int u = q.front(); q.pop();
rep(i, g[u].size()){
int v = g[u][i];
if (d[v] == inf){
d[v] = d[u] + 1;
q.push(v);
int ans = 0;
rep1(i, n)
if (d[i] != inf && i != s && (ans == 0 || d[ans] & d[i])) ans =
printf(&%d\n&, ans);
本文已收录于以下专栏：
相关文章推荐
这次校赛的目的，是为了省赛测试各种程序是否有问题
蓝桥杯习题
蓝桥杯练习系统习题加答案，总共分为6部分，90%习题使用C语言解答，部分使用C++或者Java。大部分习题为搜索参考或者别人提供所得，不足之处在所难免，恳请批评指正（预计200多题...
第七届蓝桥杯部分练习题答案—————————————————————————————————————————————————————
今天闲来无事，把之前在蓝桥杯试题集中做的发给大家参考一下，其中（...
查验身份证(15)
代码长度限制
一个合法的身份证号码由17...
今天写了一道判断身份证对错的题，才发现身份证也有算法。。怪不得我以前自己乱编身份证不能通过。。
科普一下：
一个合法的身份证号码由17位地区、日期编号和顺序编号加1位校验码组成。校验码的计算规则如...
一个合法的身份证号码由17位地区、日期编号和顺序编号加1位校验码组成。校验码的计算规则如下：
首先对前17位数字加权求和，权重分配为：{7，9，10，5，8，4，2，1，6，3，7，9，10，5...
转自： /a/1648938/
给定两个整数A和B，输出从A到B的所有整数以及这些数的和。
输入格式：
输入在一行中给出2个整数A和B，其中-100
输出格式：
首先顺序输出从A到B的所有整数，每5个数字占一...
给定两个整数A和B，输出从A到B的所有整数以及这些数的和。
输入格式：
输入在一行中给出2个整数A和B，其中-100
输出格式：
首先顺序输出从A到B的所有整数，每5个数字占一...
给定两个整数A和B，输出从A到B的所有整数以及这些数的和。输入格式：输入在一行中给出2个整数A和B，其中-100...
他的最新文章
讲师：李江龙
讲师：司徒正美
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)}