信息学奥赛-入门级 题库
海港 (port)
【问题描述】
小K是一个海港的海关工作人员,每天都有许多船只到达海港,船上通常有很多来 自不同国家的乘客。
小K对这些到达海港的船只非常感兴趣,他按照时间记录下了到达海港的每一艘船 只情况;对于第 i 艘到达的船,他记录了这艘船到达的时间 ti (单位:秒),船上的乘 客数量 ki ,以及每名乘客的国籍 xi, 1 , xi,2 , . . . , xi,ki 。
小K统计了n 艘船的信息,希望你帮忙计算出以每一艘船到达时间为止的 24 小时 ( 24 小时 = 86400 秒) 内所有乘船到达的乘客来自多少个不同的国家。
形式化地讲,你需要计算 n 条信息。 对于输出的第 i 条信息,你需要统计满足
的船只p ,在所有的 xp,j 中,总共有多少个不同的数。
【输入格式】
从文件port.in 中读入数据。
第一行输入一个正整数n ,表示小K统计了n 艘船的信息。
接下来 n 行,每行描述一艘船的信息:前两个整数 ti 和 ki 分别表示这艘船到达海 港的时间和船上的乘客数量,接下来 ki 个整数 xi,j 表示船上乘客的国籍。
保证输入的ti 是递增的,单位是秒;表示从小K第一次上班开始计时,这艘船在第 ti 秒到达海港。

【输出格式】
输出到文件port.out 中。
输出n 行,第 i 行输出一个整数表示第i 艘船到达后的统计信息。
【样例1输入】
3
1 4 4 1 2 2
2 2 2 3
10 1 3
【样例1输出】
3
4
4
【样例1说明】
第一艘船在第 1 秒到达海港,最近 24 小时到达的船是第一艘船,共有 4 个乘客, 分别是来自国家 4, 1, 2, 2 ,共来自 3 个不同的国家;
第二艘船在第 2 秒到达海港,最近 24 小时到达的船是第一艘船和第二艘船,共有 4 + 2 = 6 个乘客,分别是来自国家 4, 1, 2, 2, 2, 3 ,共来自4 个不同的国家;
第三艘船在第 10 秒到达海港,最近 24 小时到达的船是第一艘船、第二艘船和第 三艘船,共有 4 + 2 + 1 = 7 个乘客,分别是来自国家 4, 1, 2, 2, 2, 3, 3 ,共来自4 个不同 的国家。
【样例2输入】
4
1 4 1 2 2 3
3 2 2 3
86401 2 3 4
86402 1 5
【样例2输出】
3
3
3
4
【样例2说明】
第一艘船在第 1 秒到达海港,最近 24 小时到达的船是第一艘船,共有 4 个乘客, 分别是来自国家 1, 2, 2, 3 ,共来自 3 个不同的国家;
第二艘船在第 3 秒到达海港,最近 24 小时到达的船是第一艘船和第二艘船,共有 4 + 2 = 6 个乘客,分别是来自国家 1, 2, 2, 3, 2, 3 ,共来自 3 个不同的国家;
第三艘船在第 86401 秒到达海港,最近 24 小时到达的船是第二艘船和第三艘船, 共有 2 + 2 = 4 个乘客,分别是来自国家 2, 3, 3, 4 ,共来自 3 个不同的国家;
第四艘船在第 86403 秒到达海港,最近 24 小时到达的船是第二艘船、第三艘船和 第四艘船,共有 2 + 2 + 1 = 5 个乘客,分别是来自国家 2, 3, 3, 4, 5 ,共来自4 个不同的 国家。

#include<iostream>
#include<queue>
using namespace std;
struct node
{
int t,c;
};
queue<node> q;
int a[100005];
int main()
{
int i,n,t,j,k,c,cnt=0;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>t>>k;
for(j=1;j<=k;j++)
{
cin>>c;
q.push(node({t,c}));
if(a[c]==0)
cnt++;
a[c]++;
}
while(q.back().t- q.front() .t>=86400)
{
if((--a[q.front().c ])==0)
cnt--;
q.pop();
}
cout<<cnt<<endl;
}
return 0;
}
魔法阵 (magic)
【问题描述】
六十年一次的魔法战争就要开始了,大魔法师准备从附近的魔法场中汲取魔法能 量。
大魔法师有 m 个魔法物品,编号分别为 1, 2, . . . , m 。每个物品具有一个魔法值,我 们用xi 表示编号为 i 的物品的魔法值。每个魔法值xi 是不超过n 的正整数,可能有多 个物品的魔法值相同。
大魔法师认为,当且仅当四个编号为a, b, c, d 的魔法物品满足 xa < xb < xc < xd , xb - xa = 2(xd - xc ) ,并且 xb - xa < (xc - xb ) ÷ 3 时,这四个魔法物品形成了一个魔法阵, 他称这四个魔法物品分别为这个魔法阵的A 物品,B 物品,C 物品,D 物品。
现在,大魔法师想要知道,对于每个魔法物品,作为某个魔法阵的A 物品出现的 次数,作为B物品的次数,作为C 物品的次数,和作为D 物品的次数。
【输入格式】
从文件magic.in 中读入数据。
输入文件的第一行包含两个空格隔开的正整数 n 和m 。
接下来 m 行,每行一个正整数,第 i + 1 行的正整数表示xi ,即编号为 i 的物品的 魔法值。
保证
每个 xi 是分别在合法范围内等概率 随机生成的。
【输出格式】
输出到文件magic.out 中。
共输出 m 行,每行四个整数。 第 i 行的四个整数依次表示编号为 i 的物品作 为A,B,C,D 物品分别出现的次数。
保证标准输出中的每个数都不会超过
每行相邻的两个数之间用恰好一个空格隔开。
【样例1输入】
30 8
1
24
7
28
5
29
26
24
【样例1输出】
4 0 0 0
0 0 1 0
0 2 0 0
0 0 1 1
1 3 0 0
0 0 0 2
0 0 2 2
0 0 1 0
【样例1说明】
共有 5 个魔法阵,分别为:
物品 1, 3, 7, 6 ,其魔法值分别为 1, 7, 26, 29 ;
物品 1, 5, 2, 7 ,其魔法值分别为 1, 5, 24, 26 ;
物品 1, 5, 7, 4 ,其魔法值分别为 1, 5, 26, 28 ;
物品 1, 5, 8, 7 ,其魔法值分别为 1, 5, 24, 26 ;
物品 5, 3, 4, 6 ,其魔法值分别为 5, 7, 28, 29 。
以物品 5 为例,它作为A 物品出现了 1 次,作为B物品出现了 3 次,没有作为C 物 品或者D 物品出现,所以这一行输出的四个数依次为 1, 3, 0, 0 。
此外,如果我们将输出看作一个 m 行 4 列的矩阵,那么每一列上的 m 个数之和都 应等于魔法阵的总数。所以,如果你的输出不满足这个性质,那么这个输出一定不正 确。你可以通过这个性质在一定程度上检查你的输出的正确性。
【样例2输入】
15 15
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
【样例2输出】
5 0 0 0
4 0 0 0
3 5 0 0
2 4 0 0
1 3 0 0
0 2 0 0
0 1 0 0
0 0 0 0
0 0 0 0
0 0 1 0
0 0 2 1
0 0 3 2
0 0 4 3
0 0 5 4
0 0 0 5
【子任务】
每个测试点的详细数据范围见下表。

#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[40001];
int f[5][15001]/*作为第i个物品时,魔法值为j的次数*/;
int d[15001]/*魔法值为i的物品个数*/;
int sum=0,cnt=0;
int main(){
memset(f,0,sizeof(f));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d",&a[i]);
d[a[i]]++;
}
for(int t=1;t*9+2<=n;t++){
sum=0;cnt=0;
for(int dd=9*t+2;dd<=n;dd++){
int cc=dd-t;//第三个物品
int bb=cc-6*t-1;//第二个物品
int aa=bb-2*t;//第一个物品
sum+=d[aa]*d[bb];//递推计算前缀和
f[3][cc]+=sum*d[dd];//魔法值为d的个数可能不是/不止1个
f[4][dd]+=sum*d[cc];//同理
}
for(int aa=n-9*t-1;aa>=1;aa--){
int bb=aa+2*t;//第二个物品
int cc=bb+6*t+1;//第三个物品
int dd=cc+t;//第四个物品
cnt+=d[cc]*d[dd];
f[1][aa]+=cnt*d[bb];
f[2][bb]+=cnt*d[aa];
}
}
for(int i=1;i<=m;i++){
for(int j=1;j<=4;j++){
printf("%d ",f[j][a[i]]);
}
printf("\n");
}
return 0;
}
数字反转
【问题描述】
给定一个整数,请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形 式,即除非给定的原数为零,否则反转后得到的新数的最高位数字不应为零(参见样例2)。
【输入】
输入文件名为reverse.in。
输入共1行, 一个整数N。
【输出】
输出文件名为reverse.out。
输出共1行, 一个整数,表示反转后的新数。
【输入输出样例1】

【输入输出样例2】

【数据范围】
-1,000,000,000≤ N≤1,000,000,000。
#include<stdio.h>
int main(){
int m,i;
scanf("%d",&m);
if(m==0) printf("0");
if(m<0) {
m=-m;
printf("-");
}
do{
i=m%10;
m=m/10;
if(i!=0)printf("%d",i);
}while(i==0);
while(m!=0){
i=m%10;
m=m/10;
printf("%d",i);
}
return 0;
}
瑞士轮
【背景】
在双人对决的竞技性比赛,如乒乓球、羽毛球、国际象棋中,最常见的赛制是淘汰赛和 循环赛。前者的特点是比赛场数少,每场都紧张刺激,但偶然性较高。后者的特点是较为公 平,偶然性较低,但比赛过程往往十分冗长。
本题中介绍的瑞士轮赛制,因最早使用于1895年在瑞士举办的国际象棋比赛而得名。 它可以看作是淘汰赛与循环赛的折衷,既保证了比赛的稳定性,又能使赛程不至于过长。
【问题描述】
2*N名编号为1~2N的选手共进行R轮比赛。每轮比赛开始前,以及所有比赛结束后, 都会按照总分从高到低对选手进行一次排名。选手的总分为第一轮开始前的初始分数加上已 参加过的所有比赛的得分和。总分相同的,约定编号较小的选手排名靠前。
每轮比赛的对阵安排与该轮比赛开始前的排名有关:第1 名 和 第 2 名 、 第 3 名 和 第 4 名、 … … 、第2K - 1名和第2K名、 … … 、第2N - 1名和第2N名,各进行 一 场比赛。每 场比赛胜者得1分,负者得0分。也就是说除了首轮以外,其它轮比赛的安排均不能事先确 定,而是要取决于选手在之前比赛中的表现。
现给定每个选手的初始分数及其实力值,试计算在R轮比赛过后,排名第Q的选手编号是多少。我们假设选手的实力值两两不同,且每场比赛中实力值较高的总能获胜。
【输入】
输入文件名为swiss .in。
输入的第一行是三个正整数N、R、Q,每两个数之间用一个空格隔开,表示有2*N名 选手、R轮比赛,以及我们关心的名次Q。
第二行是2*N个非负整数s1,s2,…,S2N,每两个数之间用一个空格隔开,其中si表示编 号为i的选手的初始分数。
第三行是2*N个正整数w1,w2,…,w2N,每两个数之间用一个空格隔开,其中wi表示编 号为i的选手的实力值。
【输出】
输出文件名为swiss . out。
输出只有一行,包含一个整数,即R轮比赛结束后,排名第Q的选手的编号。
【输入输出样例】

【输入输出样例说明】

【数据范围】
对于30%的数据,1≤N≤100;
对于50%的数据,1≤N≤10,000;
对于100% 的数据,1≤N≤100,000,1≤R≤50,1≤Q≤2N,0≤S1,S2, … ,S2N≤10⁸,l≤wi, w2, …,w2N≤10⁸。
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxm = 2e5 + 10;
struct node
{
int id;
int score;
int power;
}stu[maxm],w[maxm],l[maxm];
bool cmp(node a,node b)
{
if (a.score==b.score)
return a.id < b.id;
return a.score > b.score;
}
bool cmp2(int s1,int s2,int id1,int id2)
{
if (s1==s2)
return id1 < id2;
return s1 > s2;
}
void merge(int ll,int rr)
{
int l1 = ll,l2 = ll,k = ll;
while (l1<=rr && l2<=rr)
if (cmp2(w[l1].score,l[l2].score,w[l1].id,l[l2].id))
stu[k++] = w[l1++];
else stu[k++] = l[l2++];
while (l1<=rr) stu[k++] = w[l1++];
while (l2<=rr) stu[k++] = l[l2++];
}
int main()
{
int n,r,q,i;
scanf("%d %d %d",&n,&r,&q);
for (i=1;i<=2*n;i++)
{
scanf("%d",&stu[i].score);
stu[i].id = i;
}
for (i=1;i<=2*n;i++)
scanf("%d",&stu[i].power);
sort(stu+1,stu+2*n+1,cmp);
while (r--)
{
int lo = 0,wi = 0;
for (i=1;i<=2*n;i+=2)
{
if (stu[i].power>stu[i+1].power)
{
w[++wi] = stu[i];
l[++lo] = stu[i+1];
w[wi].score++;
}
else
{
l[++lo] = stu[i];
w[++wi] = stu[i+1];
w[wi].score++;
}
}
merge(1,n);
}
printf("%d\n",stu[q].id);
return 0;
}
推销员
【问题描述】
阿明是一名推销员,他奉命到螺丝街推销他们公司的产品。螺丝街是一条死胡同,出口与入口是同一个,街道的一侧是围墙,另一侧是住户。螺丝街一共有 N 家住户,第 i 家住户到入口的距离为 Si 米。由于同一栋房子里可以有多家住户,所以可能有多家住户与入口的距离相等。阿明会从入口进入,依次向螺丝街的 X 家住户推销产品,然后再原路走出去。
阿明每走 1 米就会积累 1 点疲劳值,向第 i 家住户推销产品会积累 Ai点疲劳值。阿明是工作狂,他想知道,对于不同的 X,在不走多余的路的前提下,他最多可以积累多少点疲劳值。
【输入格式】
输入文件名为 salesman.in。
第一行有一个正整数 N,表示螺丝街住户的数量。
接下来的一行有 N 个正整数,其中第 i 个整数 Si表示第 i 家住户到入口的距离。数据保证
接下来的一行有 N 个正整数,其中第 i 个整数 Ai表示向第 i 户住户推销产品会积累的疲劳值。数据保证
【输出格式】
输出文件名为 salesman.out。
输出 N 行,每行一个正整数,第 i 行整数表示当 X=i 时,阿明最多积累的疲劳值。
【输入输出样例 1】

【输入输出样例 1 说明】
X=1: 向住户 5 推销,往返走路的疲劳值为 5+5,推销的疲劳值为 5,总疲劳值为15。
X=2: 向住户 4、5 推销,往返走路的疲劳值为 5+5,推销的疲劳值为 4+5,总疲劳值为 5+5+4+5=19。
X=3: 向住户 3、4、5 推销,往返走路的疲劳值为 5+5,推销的疲劳值 3+4+5,总疲劳值为 5+5+3+4+5=22。
X=4: 向住户 2、3、4、5 推销,往返走路的疲劳值为 5+5,推销的疲劳值 2+3+4+5,总疲劳值 5+5+2+3+4+5=24。
X=5: 向住户 1、2、3、4、5 推销,往返走路的疲劳值为 5+5,推销的疲劳值 1+2+3+4+5,总疲劳值 5+5+1+2+3+4+5=25。
【输入输出样例 2】

【输入输出样例 2 说明】
X=1:向住户 4 推销,往返走路的疲劳值为 4+4,推销的疲劳值为 4,总疲劳值 4+4+4=12。
X=2:向住户 1、4 推销,往返走路的疲劳值为 4+4,推销的疲劳值为 5+4,总疲劳值4+4+5+4=17。
X=3:向住户 1、2、4 推销,往返走路的疲劳值为 4+4,推销的疲劳值为 5+4+4,总疲劳值 4+4+5+4+4=21。
X=4:向住户 1、2、3、4 推销,往返走路的疲劳值为 4+4,推销的疲劳值为 5+4+3+4,总疲劳值 4+4+5+4+3+4=24。或者向住户 1、2、4、5 推销,往返走路的疲劳值为 5+5,推销的疲劳值为 5+4+4+1,总疲劳值 5+5+5+4+4+1=24。
X=5:向住户 1、2、3、4、5 推销,往返走路的疲劳值为 5+5,推销的疲劳值为 5+4+3+4+1,总疲劳值 5+5+5+4+3+4+1=27。
【数据说明】
对于 20%的数据,1≤N≤20;
对于 40%的数据,1≤N≤100;
对于 60%的数据,1≤N≤1000;
对于 100%的数据,1≤N≤100000。
#include<bits/stdc++.h>
struct pl{
int s,val;
}a[100005];
int maxx,j,k,ans;
using namespace std;
bool cmp(pl x,pl y)
{
return x.val>y.val;
}
int main()
{
int n;
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i].s);
}
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i].val);
}
sort(a+1,a+n+1,cmp);
for (int i=1;i<=n;i++)
if (2*a[i].s+a[i].val>maxx)
{
maxx=2*a[i].s+a[i].val;
j=k=i;
}
ans+=maxx;
printf("%d\n",ans);
for (int i=1;i<=n;i++)
{
if (i==k)
{
continue;
}
if (a[j].s<a[i].s)
{
ans=ans-2*a[j].s+2*a[i].s+a[i].val;
j=i;
printf("%d\n",ans);
}
else
{
ans+=a[i].val;
printf("%d\n",ans);
}
}
return 0;
}
螺旋矩阵
【问题描述】
一个 n 行 n 列的螺旋矩阵可由如下方法生成:
从矩阵的左上角(第 1 行第 1 列)出发,初始时向右移动;如果前方是未曾经过的格子,则继续前进,否则右转;重复上述操作直至经过矩阵中所有格子。根据经过顺序,在格子中依次填入 1, 2, 3, ... ,
,便构成了一个螺旋矩阵。
下图是一个 n = 4 时的螺旋矩阵。

现给出矩阵大小 n 以及 i 和 j,请你求出该矩阵中第 i 行第 j 列的数是多少。
【输入】
输入文件名为 matrix.in。
输入共一行,包含三个整数 n,i,j,每两个整数之间用一个空格隔开,分别表示矩阵大小、待求的数所在的行号和列号。
【输出】
输出文件名为 matrix.out。
输出共一行,包含一个整数,表示相应矩阵中第 i 行第 j 列的数。
【输入输出样例】

【数据说明】
对于 50%的数据,1 ≤ n ≤ 100;
对于 100%的数据,1 ≤ n ≤ 30,000,1 ≤ i ≤ n,1 ≤ j ≤ n。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
int main()
{
freopen("matrix.in","r",stdin);
freopen("matrix.out","w",stdout);
int n,i,j;
scanf("%d %d %d",&n,&i,&j);
int x=j,y=i;
int a=n/2;
if(n%2==0)//判断该数属于第几行
{
if(x>a)
x=1+(n-x);
if(y>a)
y=1+(n-y);
}
else
{
if(x>a+1)
x=1+(n-x);
if(y>a+1)
y=1+(n-y);
}
int ceng=x<y?x:y;
x=1;y=1;
int p=1;
for(int m=1;m<ceng;m++)
{
p+=4*(n-1);
n-=2;
x++;
y++;
}
if(y==i)
{
p+=j-x;
printf("%d",p);
return 0;
}
p+=n-1;
x+=n-1;
if(x==j)
{
p+=i-y;
printf("%d",p);
return 0;
}
p+=n-1;
y+=n-1;
if(y==i)
{
p+=x-j;
printf("%d",p);
return 0;
}
p+=n-1;
x-=n-1;
if(x==j)
{
p+=y-i;
printf("%d",p);
return 0;
}
return 0;
}
子矩阵
【问题描述】
给出如下定义:
1. 子矩阵:从一个矩阵当中选取某些行和某些列交叉位置所组成的新矩阵(保持行与列的相对顺序)被称为原矩阵的一个子矩阵。
例如,下面左图中选取第 2、4 行和第 2、4、5 列交叉位置的元素得到一个 2*3 的子矩阵如右图所示。

2. 相邻的元素:矩阵中的某个元素与其上下左右四个元素(如果存在的话)是相邻的。
3. 矩阵的分值:矩阵中每一对相邻元素之差的绝对值之和。
本题任务:给定一个 n 行 m 列的正整数矩阵,请你从这个矩阵中选出一个 r 行 c 列的子矩阵,使得这个子矩阵的分值最小,并输出这个分值。
【输入】
输入文件名为 submatrix.in。
第一行包含用空格隔开的四个整数 n,m,r,c,意义如问题᧿述中所述,每两个整数之间用一个空格隔开。
接下来的 n 行,每行包含 m 个用空格隔开的整数,用来表示问题᧿述中那个 n 行 m 列的矩阵。
【输出】
输出文件名为 submatrix.out。
输出共 1 行,包含 1 个整数,表示满足题目描述的子矩阵的最小分值。
【输入输出样例 1】

【输入输出样例 1 说明】
该矩阵中分值最小的 2 行 3 列的子矩阵由原矩阵的第 4 行、第 5 行与第 1 列、第 3 列、

【输入输出样例 2】

【输入输出样例 2 说明】
该矩阵中分值最小的 3 行 3 列的子矩阵由原矩阵的第 4 行、第 5 行、第 6 行与第 2 列、第 6 列、第 7 列交叉位置的元素组成,选取的分值最小的子矩阵为
【数据说明】

#include<bits/stdc++.h>
using namespace std;
const int N = 20;
int n, m, r, c;
int num[N][N], ch[N], gs = 1;
int lc[N], hc[N][N];
int f[N][N];
/*
具体思路:
首先想到暴力方法
枚举每个rc大小的矩阵,然后计算差值和,但复杂度过高
需要优化:
首先枚举n行中的r行
利用dfs()枚举每种可能,当dfs()进行到已经不能完成r行时停止
预处理选出来的r行每一列之间的行与行的差值和即lc[i]
在预处理c列中任意两列之间的差值和即hc[i][j] 第i列和第j列的差值和
利用线性dp处理即可
f[i][j]表示前i列中选j列的最小值(选第j列)
f[i][j] = min(f[i][j], f[k][j - 1] + lc[i] + hc[i][k])
*/
void Init()
{
for(int i = 1; i <= m; i++)
{
lc[i] = 0;
for(int j = 1; j < r; j++)
{
lc[i] += abs(num[ch[j]][i] - num[ch[j + 1]][i]);//
}
}
for(int i = 2; i <= m; i++)
{
for(int j = 1; j < i; j++)
{
hc[i][j] = 0; //第i列减第j列的中r行的差值差值
for(int k = 1; k <= r; k++)
{
hc[i][j] += abs(num[ch[k]][i] - num[ch[k]][j]);
}
}
}
}
int minn = 2e9;
int cmin;
void dp()
{
for(int i = 1; i <= m; i++) //前i行
{
cmin = min(i, c);
for(int j = 1; j <= cmin; j++)//选j行
{
if(j == 1)
f[i][j] = lc[i];
else
{
if(i == j)
{
f[i][j] = f[i - 1][j - 1] + lc[i] + hc[i][j - 1];
}
else
{
f[i][j] = 2e8;
for(int k = j - 1; k < i; k++)
{
f[i][j] = min(f[i][j], f[k][j - 1] + lc[i] + hc[i][k]);
}
}
}
if(j == c) minn = min(minn, f[i][c]);//前i列选c列
}
}
}
void dfs(int node)
{
if(node > n)
{
Init();
dp();
return;
}
if(r - gs + 1 == n - node + 1)//已经取地行数还没取得行数 优化剪枝
{
ch[gs ++] = node;
dfs(node + 1);
ch[gs --] = 0;
return;
}
dfs(node + 1);
if(gs <= r)
{
ch[gs ++] = node;
dfs(node + 1);
ch[gs --];
}
}
int main()
{
cout << 2<<20 << e
scanf("%d%d%d%d", &n, &m, &r, &c);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
scanf("%d", &num[i][j]);
dfs(1);
printf("%d", minn);
return 0;
}
记数问题
【问题描述】
试计算在区间 1 到 n 的所有整数中,数字 x(0 ≤ x ≤ 9)共出现了多少次?例如,在 1到 11 中,即在 1、2、3、4、5、6、7、8、9、10、11 中,数字 1 出现了 4 次。
【输入】
输入文件名为 count.in。
输入共 1 行,包含 2 个整数 n、x,之间用一个空格隔开。
【输出】
输出文件名为 count.out。
输出共 1 行,包含一个整数,表示 x 出现的次数。
【输入输出样例】

【数据说明】
对于 100%的数据,1≤ n ≤ 1,000,000,0 ≤ x ≤ 9。
#include<iostream>
using namespace std;
int main()
{
long long n,i,x,b,c,t=0;
cin>>n>>x;//输入范围与要查的数字;
for(i=1;i<=n;i++)//一到n进行循环;
{
b=i;//为了不改变i的值,就把i赋值给一个数;
while(b!=0)//如果b不等于0,继续循环;
{
c=b%10;//求是否是x,是的话计数器加一;
b=b/10;//求下一个数字是否为x;
if(c==x) t++;计数器加一;
}
}
cout<<t<<endl;//输出计数器的数字;
return 0;//结束
}
文化之旅
【问题描述】
有一位使者要游历各国,他每到一个国家,都能学到一种文化,但他不愿意学习任何一种文化超过一次(即如果他学习了某种文化,则他就不能到达其他有这种文化的国家)。不同的国家可能有相同的文化。不同文化的国家对其他文化的看法不同,有些文化会排斥外来文化(即如果他学习了某种文化,则他不能到达排斥这种文化的其他国家)。
现给定各个国家间的地理关系,各个国家的文化,每种文化对其他文化的看法,以及这位使者游历的起点和终点(在起点和终点也会学习当地的文化),国家间的道路距离,试求从起点到终点最少需走多少路。
【输入】
输入文件 culture.in。
第一行为五个整数 N,K,M,S,T,每两个整数之间用一个空格隔开,依次代表国家个数(国家编号为 1 到 N),文化种数(文化编号为 1 到 K),道路的条数,以及起点和终点的编号(保证 S 不等于 T);
第二行为 N 个整数,每两个整数之间用一个空格隔开,其中第 i 个数 Ci,表示国家 i的文化为 Ci。
接下来的 K 行,每行 K 个整数,每两个整数之间用一个空格隔开,记第 i 行的第 j 个数为 aij,aij= 1 表示文化 i 排斥外来文化 j(i 等于 j 时表示排斥相同文化的外来人),aij= 0 表示不排斥(注意 i 排斥 j 并不保证 j 一定也排斥 i)。
接下来的 M 行,每行三个整数 u,v,d,每两个整数之间用一个空格隔开,表示国家 u与国家 v 有一条距离为 d 的可双向通行的道路(保证 u 不等于 v,两个国家之间可能有多条道路)。
【输出】
输出文件名为 culture.out。
输出只有一行,一个整数,表示使者从起点国家到达终点国家最少需要走的距离数(如果无解则输出-1)。
【输入输出样例 1】

【输入输出样例说明】
由于到国家 2 必须要经过国家 1,而国家 2 的文明却排斥国家 1 的文明,所以不可能到达国家 2。
【输入输出样例 2】

【输入输出样例说明】
路线为 1 -> 2。
【数据范围】
对于 20%的数据,有 2≤N≤8,K≤5;
对于 30%的数据,有 2≤N≤10,K≤5;
对于 50%的数据,有 2≤N≤20,K≤8;
对于 70%的数据,有 2≤N≤100,K≤10;
对于 100%的数据,有


#include<bits/stdc++.h>
using namespace std;
int n,k,m,s,t;
int c[101];
int a[101][101],road[101][101];
int main()
{
scanf("%d%d%d%d%d",&n,&k,&m,&s,&t);
for(int i=1;i<=n;i++)
scanf("%d",&c[i]);
for(int i=1;i<=k;i++)
for(int j=1;j<=k;j++)
{
scanf("%d",&a[i][j]);
a[j][i]=a[i][j];
}
memset(road,0x3f3f3f3f,sizeof(road));
for(int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
road[u][v]=road[v][u]=w;
if(a[c[u]][c[v]]==1)
road[u][v]=road[v][u]=0x3f3f3f3f;
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(i!=j&&i!=k&&j!=k)
{
if(a[i][j]!=1&&a[i][k]!=1&&a[j][k]!=1)
road[i][j]=min(road[i][j],road[i][k]+road[k][j]);
}
}
if(road[s][t]<1001)
cout<<road[s][t]<<endl;
else
cout<<-1<<endl;
}
数字统计
【问题描述】
请统计某个给定范围[L, R]的所有整数中,数字 2 出现的次数。
比如给定范围[2, 22],数字 2 在数2中出现了 1次,在数 12中出现 1 次,在数 20 中出现 1 次,在数 21 中出现 1 次,在数 22 中出现 2 次,所以数字 2 在该范围内一共出现了 6次。
【输入】
输入文件名为 two.in。
输入共 1 行,为两个正整数 L 和 R,之间用一个空格隔开。
【输出】
输出文件名为 two.out。
输出共 1 行,表示数字 2 出现的次数。
【输入输出样例1】

【输入输出样例2】

【数据范围】
1 ≤ L ≤R≤ 10000。
#include<cstdio>
int main()
{
int l,r,i,k,ans=0;
scanf("%d%d",&l,&r);
for(i=l;i<=r;i++)
for(k=i;k>0;k/=10)
if(k%10==2)ans++;
printf("%d\n",ans);
return 0;
}
接水问题
【问题描述】
学校里有一个水房,水房里一共装有 m 个龙头可供同学们打开水,每个龙头每秒钟的供水量相等,均为 1。
现在有 n 名同学准备接水,他们的初始接水顺序已经确定。将这些同学按接水顺序从 1到 n 编号,i号同学的接水量为 wi。接水开始时,1 到 m号同学各占一个水龙头,并同时打开水龙头接水。当其中某名同学 j 完成其接水量要求 wj 后,下一名排队等候接水的同学 k马上接替 j 同学的位置开始接水。这个换人的过程是瞬间完成的,且没有任何水的浪费。即j 同学第x 秒结束时完成接水, 则 k 同学第 x+1 秒立刻开始接水。 若当前接水人数 n’不足 m,则只有 n’个龙头供水,其它 m−n’个龙头关闭。
现在给出 n名同学的接水量,按照上述接水规则,问所有同学都接完水需要多少秒。
【输入】
输入文件名为 water.in。
第 1 行2 个整数 n 和 m,用一个空格隔开,分别表示接水人数和龙头个数。
第 2 行 n 个整数 w1、w2、……、wn,每两个整数之间用一个空格隔开,wi表示 i 号同学的接水量。
【输出】
输出文件名为 water.out。
输出只有一行,1 个整数,表示接水所需的总时间。
【输入输出样例1】

【输入输出样例1解释】
第 1 秒,3 人接水。第 1秒结束时,1、2、3 号同学每人的已接水量为 1,3 号同学接完水,4 号同学接替 3 号同学开始接水。
第 2 秒,3 人接水。第 2 秒结束时,1、2 号同学每人的已接水量为 2,4 号同学的已接水量为 1。
第 3 秒,3 人接水。第 3 秒结束时,1、2 号同学每人的已接水量为 3,4 号同学的已接水量为 2。4号同学接完水,5 号同学接替 4 号同学开始接水。
第 4 秒,3 人接水。第 4 秒结束时,1、2 号同学每人的已接水量为 4,5 号同学的已接水量为 1。1、2、5 号同学接完水,即所有人完成接水。
总接水时间为 4 秒。
【输入输出样例2】

【数据范围】
1 ≤ n ≤ 10000,1 ≤m≤ 100 且 m≤ n;
1 ≤wi ≤ 100。
#include <bits/stdc++.h>
using namespace std;
int s[11000],ans;
int main(){
int n,m;
cin >> n >> m;
for(int i = 1;i <= n;i ++){
cin >> s[i];
}
int t = m + 1;
while(t <= n + m){
for(int i = 1;i <= m;i ++){
s[i]--;
if(s[i] == 0){
s[i] = s[t];
t ++;
}
}
ans ++;
}
cout << ans;
return 0;
}
导弹拦截
【问题描述】
经过 11 年的韬光养晦,某国研发出了一种新的导弹拦截系统,凡是与它的距离不超过其工作半径的导弹都能够被它成功拦截。当工作半径为 0 时,则能够拦截与它位置恰好相同的导弹。但该导弹拦截系统也存在这样的缺陷:每套系统每天只能设定一次工作半径。而当天的使用代价,就是所有系统工作半径的平方和。
某天,雷达捕捉到敌国的导弹来袭。由于该系统尚处于试验阶段,所以只有两套系统投入工作。如果现在的要求是拦截所有的导弹,请计算这一天的最小使用代价。
【输入】
输入文件名 missile.in。
第一行包含 4 个整数x1、y1、x2、y2,每两个整数之间用一个空格隔开,表示这两套导弹拦截系统的坐标分别为(x1, y1)、(x2, y2)。
第二行包含 1 个整数 N,表示有 N颗导弹。接下来 N行,每行两个整数 x、y,中间用
一个空格隔开,表示一颗导弹的坐标(x, y)。不同导弹的坐标可能相同。
【输出】
输出文件名 missile.out。
输出只有一行,包含一个整数,即当天的最小使用代价。
【提示】
两个点(x1, y1)、(x2, y2)之间距离的平方是
两套系统工作半径 r1、r2的平方和,是指 r1、r2 分别取平方后再求和,即 
【输入输出样例1】

【样例 1 说明】
样例1中要拦截所有导弹,在满足最小使用代价的前提下,两套系统工作半径的平方分别为 18 和 0。
【输入输出样例2】

【样例 2 说明】
样例中的导弹拦截系统和导弹所在的位置如下图所示。要拦截所有导弹,在满足最小使用代价的前提下,两套系统工作半径的平方分别为 20 和 10。

【数据范围】
对于 10%的数据,N = 1
对于 20%的数据,1 ≤ N ≤ 2
对于 40%的数据,1 ≤ N ≤ 100
对于 70%的数据,1 ≤ N ≤ 1000
对于 100%的数据,1 ≤ N ≤ 100000,且所有坐标分量的绝对值都不超过 1000。
#include<bits/stdc++.h>
using namespace std;
const int N=100002;
struct fire
{
int x,y;
}a[N];
int f[N];
bool cmp(fire x,fire y)
{
return x.x<y.x;
}
int main()
{
int x1,y1,x2,y2,n,ans=1e9;
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&n);
for(int i=1;i<=n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
a[i].x=(x1-x)*(x1-x)+(y1-y)*(y1-y);//不需要考虑坐标为负
a[i].y=(x2-x)*(x2-x)+(y2-y)*(y2-y);
}
sort(a+1,a+n+1,cmp);
for(int i=n;i>=1;i--)
f[i]=max(f[i+1],a[i].y);//其实顺推逆推无所谓
for(int i=1;i<=n;i++)
ans=min(f[i+1]+a[i].x,ans);
printf("%d",ans);
}
多项式输出
【问题描述】
一元 n 次多项式可用如下的表达式表示:

其中,
称为 i 次项,
称为 i 次项的系数。给出一个一元多项式各项的次数和系数,请按照如下规定的格式要求输出该多项式:
1. 多项式中自变量为 x,从左到右按照次数递减顺序给出多项式。
2. 多项式中只包含系数不为 0 的项。
3. 如果多项式 n 次项系数为正,则多项式开头不出现“+”号,如果多项式 n 次项系数为负,则多项式以“-”号开头。
4. 对于不是最高次的项,以“+”号或者“-”号连接此项与前一项,分别表示此项系数为正或者系数为负。紧跟一个正整数,表示此项系数的绝对值(如果一个高于 0 次的项,其系数的绝对值为 1,则无需输出 1)。如果 x 的指数大于 1,则接下来紧跟的指数部分的形式为“x^b”,其中 b 为 x 的指数;如果 x 的指数为 1,则接下来紧跟的指数部分形式为“x”;如果 x 的指数为 0,则仅需输出系数即可。
5. 多项式中,多项式的开头、结尾不含多余的空格。
【输入】
输入文件名为 poly.in,共有 2 行
第一行 1 个整数,n,表示一元多项式的次数。
第二行有 n+1 个整数,其中第 i 个整数表示第 n-i+1 次项的系数,每两个整数之间用空格隔开。
【输出】
输出文件 poly.out 共 1 行,按题目所述格式输出多项式。
【输入输出样例 1】

【输入输出样例 2】

【数据范围】
1≤ n≤ 100,多项式各次项系数的绝对值均不超过 100。
#include<bits/stdc++.h>
using namespace std;
int a[101];
int main() {
int n;
cin>>n;
for(int i=1; i<=n+1; i++)
scanf("%d",&a[i]);
if(a[1]<0)
cout<<'-';
if(abs(a[1])>1)
cout<<abs(a[1]);
cout<<"x^"<<n;
int nn=n-1;
for(int i=2; i<=n+1; i++) {
if(a[i]==0) {
nn--;
continue;
}
if(a[i]>0)
cout<<'+';
else
cout<<'-';
if(abs(a[i])!=1||i==n+1)
cout<<abs(a[i]);
if(nn==1)
cout<<'x';
else if(nn==0)
continue;
else
cout<<"x^"<<nn;
nn--;
}
return 0;
}
分数线划定
【问题描述】
世博会志愿者的选拔工作正在 A 市如火如荼的进行。为了选拔最合适的人才,A 市对所有报名的选手进行了笔试,笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数的150%划定,即如果计划录取m名志愿者,则面试分数线为排名第m*150%(向下取整)名的选手的分数,而最终进入面试的选手为笔试成绩不低于面试分数线的所有选手。
现在就请你编写程序划定面试分数线,并输出所有进入面试的选手的报名号和笔试成绩。
【输入】
输入文件名为 score.in。
第一行,两个整数 n,m(5 ≤ n ≤ 5000,3 ≤ m ≤ n),中间用一个空格隔开,其中 n 表示报名参加笔试的选手总数,m 表示计划录取的志愿者人数。输入数据保证 m*150%向下取整后小于等于 n。第二行到第 n+1 行,每行包括两个整数,中间用一个空格隔开,分别是选手的报名号 k(1000 ≤ k ≤ 9999)和该选手的笔试成绩 s(1 ≤ s ≤ 100)。数据保证选手的报名号各不相同。
【输出】
输出文件 score.out。
第一行,有两个整数,用一个空格隔开,第一个整数表示面试分数线;第二个整数为进入面试的选手的实际人数。从第二行开始,每行包含两个整数,中间用一个空格隔开,分别表示进入面试的选手的报名号和笔试成绩,按照笔试成绩从高到低输出,如果成绩相同,则按报名号由小到大的顺序输出。
【输入输出样例】

【样例说明】
m*150% = 3*150% = 4.5,向下取整后为 4。保证 4 个人进入面试的分数线为 88,但因为 88
有重分,所以所有成绩大于等于 88 的选手都可以进入面试,故最终有 5 个人进入面试。
#include <iostream>
#include <algorithm>
using namespace std;
const int N=5000;
struct people{
int k; //报名号
int s; //笔试成绩
};
int cmp(const people &a, const people &b){
if(a.s != b.s)
return a.s > b.s;
else
return a.k < b.k;
}
int main()
{
int n, m, pass_number;
cin >> n >> m;
people p[n];
pass_number = m * 1.5;
for(int i=0; i<n; i++)
cin >> p[i].k >> p[i].s ;
sort(p, p+n, cmp); //按要求排序
for(int i=pass_number; i<n; i++){
if(p[i].s == p[pass_number-1].s)
pass_number ++;
else
break;
} //考虑分数在及格线的选手有多名的情况
cout << p[pass_number-1].s << " " << pass_number << endl;
for(int i=0; i<pass_number; i++){
cout << p[i].k << " " << p[i].s << endl;
}
return 0;
}
道路游戏
【问题描述】
小新正在玩一个简单的电脑游戏。
游戏中有一条环形马路,马路上有 n 个机器人工厂,两个相邻机器人工厂之间由一小段马路连接。小新以某个机器人工厂为起点,按顺时针顺序依次将这 n 个机器人工厂编号为1~n,因为马路是环形的,所以第 n 个机器人工厂和第 1 个机器人工厂是由一段马路连接在一起的。小新将连接机器人工厂的这 n 段马路也编号为 1~n,并规定第 i 段马路连接第 i 个机器人工厂和第 i+1 个机器人工厂(1≤ i≤ n-1),第 n 段马路连接第 n 个机器人工厂和第 1个机器人工厂。
游戏过程中,每个单位时间内,每段马路上都会出现一些金币,金币的数量会随着时间发生变化,即不同单位时间内同一段马路上出现的金币数量可能是不同的。小新需要机器人的帮助才能收集到马路上的金币。所需的机器人必须在机器人工厂用一些金币来购买,机器人一旦被购买,便会沿着环形马路按顺时针方向一直行走,在每个单位时间内行走一次,即从当前所在的机器人工厂到达相邻的下一个机器人工厂,并将经过的马路上的所有金币收集给小新,例如,小新在 i(1≤ i≤ n)号机器人工厂购买了一个机器人,这个机器人会从 i 号机器人工厂开始,顺时针在马路上行走,第一次行走会经过 i 号马路,到达 i+1 号机器人工厂(如果 i=n,机器人会到达第 1 个机器人工厂),并将 i 号马路上的所有金币收集给小新。
游戏中,环形马路上不能同时存在 2 个或者 2 个以上的机器人,并且每个机器人最多能够在环形马路上行走 p 次。小新购买机器人的同时,需要给这个机器人设定行走次数,行走次数可以为1~p 之间的任意整数。当马路上的机器人行走完规定的次数之后会自动消失,小新必须立刻在任意一个机器人工厂中购买一个新的机器人,并给新的机器人设定新的行走次数。
以下是游戏的一些补充说明:
1. 游戏从小新第一次购买机器人开始计时。
2. 购买机器人和设定机器人的行走次数是瞬间完成的,不需要花费时间。
3. 购买机器人和机器人行走是两个独立的过程,机器人行走时不能购买机器人,购买完机器人并且设定机器人行走次数之后机器人才能行走。
4. 在同一个机器人工厂购买机器人的花费是相同的,但是在不同机器人工厂购买机器人的花费不一定相同。
5. 购买机器人花费的金币,在游戏结束时再从小新收集的金币中扣除,所以在游戏过程中小新不用担心因金币不足,无法购买机器人而导致游戏无法进行。也因为如此,游戏结束后,收集的金币数量可能为负。
现在已知每段马路上每个单位时间内出现的金币数量和在每个机器人工厂购买机器人需要的花费,请你告诉小新,经过 m 个单位时间后,扣除购买机器人的花费,小新最多能收集到多少金币。
【输入】
输入文件名为 game.in。
第一行 3 个正整数,n,m,p,意义如题目所述。
接下来的 n 行,每行有 m 个正整数,每两个整数之间用一个空格隔开,其中第 i 行描
述了 i 号马路上每个单位时间内出现的金币数量(1 ≤ 金币数量 ≤ 100),即第 i 行的第 j
(1≤ j≤ m)个数表示第 j 个单位时间内 i 号马路上出现的金币数量。
最后一行,有 n 个整数,每两个整数之间用一个空格隔开,其中第 i 个数表示在 i 号机
器人工厂购买机器人需要花费的金币数量(1≤ 金币数量≤ 100)。
【输出】
输出文件 game.out 共一行,包含 1 个整数,表示在 m 个单位时间内,扣除购买机器人
花费的金币之后,小新最多能收集到多少金币。
【输入输出样例】

【数据范围】
对于 40%的数据,2≤ n≤ 40,1≤ m ≤ 40。
对于 90%的数据,2≤ n≤ 200,1≤ m ≤ 200。
对于 100%的数据,2≤ n≤ 1000,1≤ m≤ 1000,1≤p≤ m。
#include <bits/stdc++.h>
using namespace std;
int n,m,p,b[1001],a[1001][1001],f[1001];
int main(){
scanf("%d%d%d",&n,&m,&p);//n表示工厂和马路的数量,m表示游戏时间,p表示机器人能穿过的工厂数量
memset(f,-1000000,sizeof(f));
f[0]=0;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
scanf("%d",&a[i][j]);//a[i,j]表示在第i段马路上 在第j秒时的金币数量
for(int i=1; i<=n; i++)
scanf("%d",&b[i]);//b[i]表示在第i个工厂购买机器人的价格
for(int i=1; i<=m; i++)
for(int j=1; j<=n; j++){//j表示机器人的编号
int pre=j-1;// 机器人上一次在第pre个工厂
if(pre==0) pre=n;//如果t等于0(被1减了),那么就是从第n个过来的
int sum=a[pre][i];//sum表示在第pre段马路上第i秒时的金币数量
for(int k=1; k<=p; k++){//k表示在第i秒时第j个机器人走了k步
if(i-k<0) break;//时间不会是负的
f[i]=max(f[i],f[i-k]+sum-b[pre]);// f[i]表示第i秒时能获得的最大钱数
pre--;
if(pre==0) pre=n;//跑道环形
sum+=a[pre][i-k];
}
}
printf("%d",f[m]);
return 0;
}
排座椅
【问题描述】
上课的时候总有一些同学和前后左右的人交头接耳,这是令小学班主任十分头疼的一件事情。不过,班主任小雪发现了一些有趣的现象,当同学们的座次确定下来之后,只有有限的D对同学上课时会交头接耳。同学们在教室中坐成了M行N列,坐在第i行第j列的同学的位置是(i,j),为了方便同学们进出,在教室中设置了K条横向的通道,L条纵向的通道。于是,聪明的小雪想到了一个办法,或许可以减少上课时学生交头接耳的问题:她打算重新摆放桌椅,改变同学们桌椅间通道的位置,因为如果一条通道隔开了两个会交头接耳的同学,那么他们就不会交头接耳了。
请你帮忙给小雪编写一个程序,给出最好的通道划分方案。在该方案下,上课时交头接耳的学生对数最少。
【输入】
输入文件seat.in的第一行,有5各用空格隔开的整数,分别是M,N,K,L,D(2<=N,M<=1000,0<=K<M,0<=L<N,D<=2000)。
接下来D行,每行有4个用空格隔开的整数,第i行的4个整数Xi,Yi,Pi,Qi,表示坐在位置(Xi,Yi)与(Pi,Qi)的两个同学会交头接耳(输入保证他们前后相邻或者左右相邻)。
输入数据保证最优方案的唯一性。
【输出】
输出文件seat.out共两行。
第一行包含K个整数,a1a2……aK,表示第a1行和a1+1行之间、第a2行和第a2+1行之间、…、第aK行和第aK+1行之间要开辟通道,其中ai< ai+1,每两个整数之间用空格隔开(行尾没有空格)。
第二行包含L个整数,b1b2……bk,表示第b1列和b1+1列之间、第b2列和第b2+1列之间、…、第bL列和第bL+1列之间要开辟通道,其中bi< bi+1,每两个整数之间用空格隔开(行尾没有空格)。
【输入输出样例】

【输入输出样例解释】

上图中用符号*、※、+ 标出了3对会交头接耳的学生的位置,图中3条粗线的位置表示通道,图示的通道划分方案是唯一的最佳方案。
#include<bits/stdc++.h>
using namespace std;
struct node{
int x1,x2,y1,y2;
}a[2005];
bool cmp(int a,int b){
return a>b;
}
int k1[1005],l1[1005],l2[1005],k2[1005],ansk[1000],ansl[1000];
int n,m,k,l,d,z=1,y=1;
int main(){
//freopen("seat.in","r",stdin);
//freopen("seat.out","w",stdout);
cin>>n>>m>>k>>l>>d;
for(int i=1;i<=d;i++){
cin>>a[i].x1>>a[i].x2>>a[i].y1>>a[i].y2;
if(a[i].x2==a[i].y2) k1[min(a[i].x1,a[i].y1)]++;//这块可以对照图理解一下
else if(a[i].x1==a[i].y1) l1[min(a[i].x2,a[i].y2)]++;
}
memcpy(k2,k1,sizeof(k1));
memcpy(l2,l1,sizeof(l1));
sort(k1+1,k1+n,cmp);//排序
sort(l1+1,l1+m,cmp);
for(int i=1;i<=k;i++){//重新匹配
for(int j=1;j<n;j++){
if(k2[j]==k1[i]){
k2[j]=0;//去重
ansk[i]=j;
break;
}
}
}
for(int i=1;i<=l;i++){//重新匹配
for(int j=1;j<m;j++){
if(l2[j]==l1[i]){
l2[j]=0;//去重
ansl[i]=j;
break;
}
}
}
sort(ansk+1,ansk+k+1);//特别坑,输出要按顺序
sort(ansl+1,ansl+l+1);
for(int i=1;i<=k;i++){
cout<<ansk[i]<<" ";
}
cout<<endl;
for(int i=1;i<=l;i++){
cout<<ansl[i]<<" ";
}
return 0;
}/*
4 5 1 2 3
4 2 4 3
2 3 3 3
2 5 2 4
*/
传球游戏
【问题描述】
上体育课的时候,小蛮的老师经常带着同学们一起做游戏。这次,老师带着同学们一起做传球游戏。
游戏规则是这样的:n个同学站成一个圆圈,其中的一个同学手里拿着一个球,当老师吹哨子时开始传球,每个同学可以把球传给自己左右的两个同学中的一个(左右任意),当老师再次吹哨子时,传球停止,此时,拿着球没传出去的那个同学就是败者,要给大家表演一个节目。
聪明的小蛮提出一个有趣的问题:有多少种不同的传球方法可以使得从小蛮手里开始传的球,传了m次以后,又回到小蛮手里。两种传球的方法被视作不同的方法,当且仅当这两种方法中,接到球的同学按接球顺序组成的序列是不同的。比如有3个同学1号、2号、3号,并假设小蛮为1号,球传了3次回到小蛮手里的方式有1->2->3->1和1->3->2->1,共2种。
【输入】
输入文件ball.in共一行,有两个用空格隔开的整数n,m(3<=n<=30,1<=m<=30)。
【输出】
输出文件ball.out共一行,有一个整数,表示符合题意的方法数。
【输入输出样例】

【限制】
40%的数据满足:3<=n<=30,1<=m<=20
100%的数据满足:3<=n<=30,1<=m<=30
#include<stdio.h>
#include<iostream>
using namespace std;
int ans[31][31];
int main()
{
int n, m;
cin >> n >> m;
//ans[i][j]=ans[i-1][j-1]+ans[i+1][j-1]
ans[1][0] = 1;
for (int j = 1; j <= m;j++) //务必次数放在第一层循环
for (int i = 1; i <= n; i++)
{
int a = i - 1;//a为左边的同学
int b = i + 1;//b为右边的同学
if (a == 0)a = n;//如果超出限制就改变一下
if (b > n)b = 1;
ans[i][j] = ans[a][j - 1] + ans[b][j - 1];
}
cout << ans[1][m];
return 0;
}
纪念品分组
【题目描述】
元旦快到了,校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡,他要把购来的纪念品根据价格进行分组,但每组最多只能包括两件纪念品,并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品,乐乐希望分组的数目最少。
你的任务是写一个程序,找出所有分组方案中分组数最少的一种,输出最少的分组数目。
【输入】
输入文件group.in包含n+2行:
第1行包括一个整数w,为每组纪念品价格之和的上限。
第2行为一个整数n,表示购来的纪念品的总件数。
第3~n+2行每行包含一个正整数pi (5 <= pi <= w),表示所对应纪念品的价格。
【输出】
输出文件group.out仅一行,包含一个整数,即最少的分组数目。
【输入输出样例】

【限制】
50%的数据满足:1 <= n <= 15
100%的数据满足:1 <= n <= 30000, 80 <= w <= 200
#include <stdio.h>
#include <stdlib.h>
#define MAXN 30010
int save[MAXN];
int n,l,r,ans,max;
int cmp(const void *a,const void *b)
{
return *(int *)a- *(int *)b;
}
int main()
{
scanf("%d%d",&max,&n);
for (int i = 0; i < n; ++i)
scanf("%d",&save[i]);
qsort(save,n,sizeof(int),cmp); //排序
r = n - 1;
l=0;
while (l <= r)
{
if (save[l] + save[r] <= max) //大加小,与规定价格比较
{
++l;
--r;
++ans;
}
else
{
--r;
++ans;
}
}
printf("%d\n",ans);
return 0;
}
开心的金明
【问题描述】
金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间他自己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过N元钱就行”。今天一早金明就开始做预算,但是他想买的东西太多了,肯定会超过妈妈限定的N元。于是,他把每件物品规定了一个重要度,分为5等:用整数1~5表示,第5等最重要。他还从因特网上查到了每件物品的价格(都是整数元)。他希望在不超过N元(可以等于N元)的前提下,使每件物品的价格与重要度的乘积的总和最大。
设第j件物品的价格为v[j],重要度为w[j],共选中了k件物品,编号依次为j1,j2,……,jk,则所求的总和为:
v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。(其中*为乘号)
请你帮助金明设计一个满足要求的购物单。
【输入文件】
输入文件happy.in 的第1行,为两个正整数,用一个空格隔开:
N m
(其中N(<30000)表示总钱数,m(<25)为希望购买物品的个数。)
从第2行到第m+1行,第j行给出了编号为j-1的物品的基本数据,每行有2个非负整数
v p
(其中v表示该物品的价格(v<=10000),p表示该物品的重要度(1~5))
【输出文件】
输出文件happy.out只有一个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的最大值(<100000000)。
【输入样例】
1000 5
800 2
400 5
300 5
400 3
200 2
【输出样例】
3900
#include<bits/stdc++.h>
using namespace std;
int n,m;
int v[26],p[26];
int f[30001];
int main(){
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++)scanf("%d%d",&v[i],&p[i]),p[i]*=v[i];
for(int i=1;i<=n;i++)
for(int j=m;j>=v[i];j--)
f[j]=max(f[j],f[j-v[i]]+p[i]);
printf("%d",f[m]);
return 0;
}
陶陶摘苹果
【问题描述】
陶陶家的院子里有一棵苹果树,每到秋天树上就会结出10个苹果。苹果成熟的时候,陶陶就会跑去摘苹果。陶陶有个30厘米高的板凳,当她不能直接用手摘到苹果的时候,就会踩到板凳上再试试。
现在已知10个苹果到地面的高度,以及陶陶把手伸直的时候能够达到的最大高度,请帮陶陶算一下她能够摘到的苹果的数目。假设她碰到苹果,苹果就会掉下来。
【输入文件】
输入文件apple.in包括两行数据。第一行包含10个100到200之间(包括100和200)的整数(以厘米为单位)分别表示10个苹果到地面的高度,两个相邻的整数之间用一个空格隔开。第二行只包括一个100到120之间(包含100和120)的整数(以厘米为单位),表示陶陶把手伸直的时候能够达到的最大高度。
【输出文件】
输出文件apple.out包括一行,这一行只包含一个整数,表示陶陶能够摘到的苹果的数目。
【样例输入】
100 200 150 140 129 134 167 198 200 111
110
【样例输出】
5