本文包含CCF-CSP模拟考试系统中历年考试全部第二题的答案，目前更新至202012-2。
【题目背景】
考虑到安全指数是一个较大范围内的整数、小菜很可能搞不清楚自己是否真的安全，顿顿决定设置一个阈值 θ，以便将安全指数 y 转化为一个具体的预测结果——“会挂科”或“不会挂科”。
因为安全指数越高表明小菜同学挂科的可能性越低，所以当 y≥θ 时，顿顿会预测小菜这学期很安全、不会挂科；反之若 y<θ，顿顿就会劝诫小菜：“你期末要挂科了，勿谓言之不预也。”
那么这个阈值该如何设定呢？顿顿准备从过往中寻找答案。
【题目描述】
具体来说，顿顿评估了 m 位同学上学期的安全指数，其中第 i（1≤i≤m）位同学的安全指数为 yi，是一个 [0,10^8] 范围内的整数；同时，该同学上学期的挂科情况记作 resulti∈0,1，其中 0 表示挂科、1 表示未挂科。
相应地，顿顿用 predictθ(y) 表示根据阈值 θ 将安全指数 y 转化为的具体预测结果。
如果 predictθ(yj) 与 resultj 相同，则说明阈值为 θ 时顿顿对第 j 位同学是否挂科预测正确；不同则说明预测错误。
最后，顿顿设计了如下公式来计算最佳阈值 θ*：
该公式亦可等价地表述为如下规则：
1.最佳阈值仅在 yi 中选取，即与某位同学的安全指数相同；
2.按照该阈值对这 m 位同学上学期的挂科情况进行预测，预测正确的次数最多（即准确率最高）；
3.多个阈值均可以达到最高准确率时，选取其中最大的。
【输入格式】
从标准输入读入数据。
输入的第一行包含一个正整数 m。
接下来输入 m 行，其中第 i（1≤i≤m）行包括用空格分隔的两个整数 yi 和 resulti，含义如上文所述。
【输出格式】
输出到标准输出。
输出一个整数，表示最佳阈值 θ*。
【样例1输入】
6
0 0
1 0
1 1
3 1
5 1
7 1
【样例1输出】
3
【样例1解释】
按照规则一，最佳阈值的选取范围为 0,1,3,5,7。
θ=0 时，预测正确次数为 4；
θ=1 时，预测正确次数为 5；
θ=3 时，预测正确次数为 5；
θ=5 时，预测正确次数为 4；
θ=7 时，预测正确次数为 3。
阈值选取为 1 或 3 时，预测准确率最高；
所以按照规则二，最佳阈值的选取范围缩小为 1,3。
依规则三，θ* = max1,3 = 3。
【样例2输入】
8
5 1
5 0
5 0
2 1
3 0
4 0
100000000 1
1 0
【样例2输出】
100000000
【子任务】
70% 的测试数据保证 m≤200；
全部的测试数据保证 2≤m≤10^5。
#include <bits/stdc++.h>
using namespace std;
struct node {
int y;
int result;
};
int cmp(node n1, node n2) {
return n1.y < n2.y;
}
node nodes[100005];
int smaller0[100005];
int bigger1[100005];
int main() {
int n;
cin>>n;
node* nodes = new node[n];
nodes[0].y = -1;
for(int i = 1; i <= n; i++) {
cin>>nodes[i].y>>nodes[i].result;
}
sort(nodes + 1, nodes + 1 + n, cmp);
for(int i = 1; i <= n; i++) {
if(nodes[i].result == 0) {
smaller0[i] = smaller0[i - 1] + 1;
} else {
smaller0[i] = smaller0[i - 1];
}
}
for(int i = n; i >= 1; i--) {
if(nodes[i].result == 1) {
bigger1[i] = bigger1[i + 1] + 1;
} else {
bigger1[i] = bigger1[i + 1];
}
}
int besty;
int bestsum = 0;
for(int i = 1; i <= n; i++) {
if(nodes[i].y == nodes[i - 1].y) { //相同y值，只判断第一个
continue;
}
int sum = 0;
sum = smaller0[i - 1] + bigger1[i];
if(sum >= bestsum) {
bestsum = sum;
besty = nodes[i].y;
}
}
cout<<besty;
return 0;
}
【题目背景】
某地疫情爆发后，出于“应检尽检”的原则，我们想要通知所有近期经过该高危区域的居民参与核酸检测。
【问题描述】
想要找出经过高危区域的居民，分析位置记录是一种简单有效的方法。
具体来说，一位居民的位置记录包含 t 个平面坐标 (x1,y1),(x2,y2),…,(xt,yt)，其中 (xt,yt) 表示该居民 i 时刻所在位置。
高危区域则可以抽象为一个矩形区域（含边界），左下角和右上角的坐标分别为 (xl,yd) 和 (xr,yu)，满足 xl<xr 且 yd<yu。
考虑某位居民的位置记录，如果其中某个坐标位于矩形内（含边界），则说明该居民经过高危区域；进一步地，如果其中连续 k 个或更多坐标均位于矩形内（含边界），则认为该居民曾在高危区域逗留。需要注意的是，判定经过和逗留时我们只关心位置记录中的 t 个坐标，而无需考虑该居民在 i 到 i+1 时刻之间位于何处。
给定高危区域的范围和 n 位居民过去 t 个时刻的位置记录，试统计其中经过高危区域的人数和曾在高危区域逗留的人数。
【输入格式】
输入共 n+1 行。
第一行包含用空格分隔的七个整数 n、k、t、xl、yd、xr 和 yu，含义如上文所述。
接下来 n 行，每行包含用空格分隔的 2t 个整数，按顺序表示一位居民过去 t 个时刻的位置记录 (x1,y1),(x2,y2),…,(xt,yt)。
【输出格式】
输出共两行，每行一个整数，分别表示经过高危区域的人数和曾在高危区域逗留的人数。
【样例输入1】
5 2 6 20 40 100 80
100 80 100 80 100 80 100 80 100 80 100 80
60 50 60 46 60 42 60 38 60 34 60 30
10 60 14 62 18 66 22 74 26 86 30 100
90 31 94 35 98 39 102 43 106 47 110 51
0 20 4 20 8 20 12 20 16 20 20 20
【样例输出1】
3
2
【样例1说明】
如下图红色标记所示，前三条位置记录经过了高危区域；
但第三条位置记录（图中左上曲线）只有一个时刻位于高危区域内，不满足逗留条件。
【样例输入2】
1 3 8 0 0 10 10
-1 -1 0 0 0 0 -1 -1 0 0 -1 -1 0 0 0 0
【样例输出2】
1
0
【样例2说明】
该位置记录经过了高危区域，但最多只有连续两个时刻位于其中，不满足逗留条件。
【评测用例规模与约定】
全部的测试点满足 1≤n≤20，1≤k≤t≤10^3，所有坐标均为整数且绝对值不超过 10^6。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
int k;
int t;
int xl, yd, xr, yu;
cin>>n>>k>>t>>xl>>yd>>xr>>yu;
int pass = 0, stay = 0;
for(int i = 0; i < n; i++) {
int* pos = new int[t * 2];
for(int j = 0; j < t * 2; j++) {
cin>>pos[j];
}
int passFlag = 0, stayFlag = 0;
int stayCount = 0;
for(int j = 0; j < t * 2; j += 2) {
if(pos[j] >= xl && pos[j] <= xr && pos[j + 1] >= yd && pos[j + 1] <= yu) {
stayCount++;
passFlag = 1;
if(stayCount == k) {
stayFlag = 1;
break;
}
} else {
stayCount = 0;
}
}
if(stayFlag == 1) {
pass++;
stay++;
} else if(passFlag == 1) {
pass++;
}
}
cout<<pass<<endl<<stay;
return 0;
}
【题目描述】
对于一个n维整数向量v∈Zn，其在第index个维度上的取值记作vindex。这里我们约定index的取值从1开始，即v=(v1,v2,…vn)。下面介绍一种向量的稀疏表示方法。
如果v仅在少量维度上的取值不为0，则称其为稀疏向量。
例如当n=10时，v=(0,0,0,5,0,0,-3,0,0,1)就是一个稀疏向量。
由于稀疏向量的非零值较少，我们可以通过仅存储非零值的方式来节省空间。具体来说，每个非零值都可以用一个(index,value)对来表示，即该向量在第index个维度上的取值vindex=value≠0。在上面的例子中，v就可以表示为[(4,5),(7,-3),(10,1)]。
接下来给出这种稀疏表示一般化的定义。
·对于任意一个n维整数向量v∈Zn，如果其在且仅在a个维度上取值不为0，则可以唯一表示为：
[(index1,value1),(index2,value2),…,(indexa,valuea)]
·其中所有的index均为整数且满足
1≤index1<index2<…<indexa≤n
· valuei表示向量v在对应维度indexi上的非零值。
给出两个n维整数向量u,v∈Zn的稀疏表示，试计算它们的内积。
【输入格式】
从标准输入读入数据。
输入的第一行包含用空格分隔的三个正整数n、a和b，其中n表示向量u、v的维数，a和b分别表示两个向量所含非零值的个数。
第二行到第a+1行输入向量u的稀疏表示。第i+1行(1≤i≤a)包含用空格分隔的两个整数indexi和valuei，表示vindexi=valuei≠0。
第a+2行到第a+b+1行输入向量v的稀疏表示。第j+a+1行(1≤j≤b)包含用空格分隔的两个整数indexj和valuej，表示vindexj=valuej≠0。
【输出格式】
输出到标准输出。
输出一个整数，表示向量u和v的内积u·v。
【样例输入】
10 3 4
4 5
7 -3
10 1
1 10
4 20
5 30
7 40
【样例输出】
-20
【样例解释】
u=(0,0,0,5,0,0,-3,0,0,1)
v=(10,0,0,20,30,0,40,0,0,0)
u·v=5×20+(-3)×40=-20
【子任务】
·输入数据保证0<a,b<n；
·向量u和v在每一维度上取值的绝对值|ui|,|vi|≤10^6(1≤i≤n)。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,a,b;
cin>>n>>a>>b;
map<int,int> m;
int i;
int index,value;
for(i=0;i<a;i++)
{
cin>>index>>value;
m[index]=value;
}
long long sum=0; //sum使用int型会越界
for(i=0;i<b;i++)
{
cin>>index>>value;
if(m[index]!=0) //u、v在同一维度上值均不为0，积才不为0
sum+=m[index]*value;
}
cout<<sum;
return 0;
}
【题目背景】
开学了，可是校园里堆积了不少垃圾杂物。
热心的同学们纷纷自发前来清理，为学校注入正能量~
【题目描述】
通过无人机航拍我们已经知晓了n处尚待清理的垃圾位置，其中第i（1≤i≤n）处的坐标为(xi,yi)，保证所有的坐标均为整数。
我们希望在垃圾集中的地方建立些回收站。具体来说，对于一个位置(x,y)是否适合建立回收站，我们主要考虑以下几点：
·(x,y)必须是整数坐标，且该处存在垃圾；
·上下左右四个邻居位置，即(x,y+1)、(x,y-1)、(x+1,y)和(x-1,y)处，必须全部存在垃圾；
·进一步地，我们会对满足上述两个条件的选址进行评分，分数为不大于4的自然数，表示在(x±1,y±1)四个对角位置中有几处存在垃圾。
现在，请你统计一下每种得分的选址个数。
【输入格式】
从标准输入读入数据。
输入总共有n+1行。
第1行包含一个正整数n，表示已查明的垃圾点个数。
第1+i行（1≤i≤n）包含由一个空格分隔的两个整数xi和yi，表示第i处垃圾的坐标。
保证输入的n个坐标互不相同。
【输出格式】
输出到标准输出。
输出共五行，每行一个整数，依次表示得分为0、1、2、3和4的回收站选址个数。
【样例1输入】
7
1 2
2 1
0 0
1 1
1 0
2 0
0 1
【样例1输出】
0
0
1
0
0
【样例1解释】
如图所示，仅有(1,1)可选为回收站地址，评分为2。
【样例2输入】
2
0 0
-100000 10
【样例2输出】
0
0
0
0
0
【样例2解释】
不存在可选地址。
【样例3输入】
11
9 10
10 10
11 10
12 10
13 10
11 9
11 8
12 9
10 9
10 11
12 11
【样例3输出】
0
2
1
0
0
【样例3解释】
1分选址：(10,10)和(12,10)；
2分选址：(11,9)。
【子任务】
·测试点1和2，保证对于任意的i皆满足0≤xi,yi≤2；
·测试点3、4和5，保证对于任意的i皆满足0≤xi,yi≤500；
·测试点6、7和8，保证对于任意的i皆满足0≤xi,yi≤10^9；
·测试点9和10，保证对于任意的i皆满足|xi|,|yi|≤10^9，即坐标可以是负数。
所有的测试点保证1≤n≤10^3。
【提示】
本题中所涉及的坐标皆为整数，且保证输入的坐标两两不同。
#include <bits/stdc++.h>
using namespace std;
struct Trash{
int x;
int y;
int isstation; //是否可作为回收站
int score; //回收站分数
};
int main()
{
int n;
cin>>n;
Trash t[n];
int i,j;
for(i=0;i<n;i++)
{
cin>>t[i].x>>t[i].y;
t[i].isstation=0;
t[i].score=0;
}
int count;
for(i=0;i<n;i++)
{
count=0;
for(j=0;j<n;j++) //判断上下左右四个邻居位置是否存在垃圾
{
if(t[j].x==t[i].x+1 && t[j].y==t[i].y)
count++;
else if(t[j].x==t[i].x-1 && t[j].y==t[i].y)
count++;
else if(t[j].y==t[i].y+1 && t[j].x==t[i].x)
count++;
else if(t[j].y==t[i].y-1 && t[j].x==t[i].x)
count++;
}
if(count==4) //邻居位置全部存在垃圾，可作为回收站
{
t[i].isstation=1;
for(j=0;j<n;j++) //计算回收站得分
{
if(t[j].x==t[i].x+1 && t[j].y==t[i].y+1)
t[i].score++;
else if(t[j].x==t[i].x+1 && t[j].y==t[i].y-1)
t[i].score++;
else if(t[j].x==t[i].x-1 && t[j].y==t[i].y+1)
t[i].score++;
else if(t[j].x==t[i].x-1 && t[j].y==t[i].y-1)
t[i].score++;
}
}
}
int score0=0,score1=0,score2=0,score3=0,score4=0;
for(i=0;i<n;i++)
{
if(t[i].isstation==1)
{
if(t[i].score==0)
score0++;
else if(t[i].score==1)
score1++;
else if(t[i].score==2)
score2++;
else if(t[i].score==3)
score3++;
else if(t[i].score==4)
score4++;
}
}
cout<<score0<<endl<<score1<<endl<<score2<<endl<<score3<<endl<<score4;
return 0;
}
【题目描述】
小明在他的果园里种了一些苹果树，这些苹果树排列成一个圆。为了保证苹果的品质，在种植过程中要进行疏果操作。为了更及时地完成疏果操作，小明会不时地检查每棵树的状态，根据需要进行疏果。检查时，如果发现可能有苹果从树上掉落，小明会重新统计树上的苹果个数（然后根据之前的记录就可以判断是否有苹果掉落了）。在全部操作结束后，请帮助小明统计相关的信息。
【输入格式】
从标准输入读入数据。
第1行包含一个正整数N，表示苹果树的棵数。
第1+i行（1≤i≤N），每行的格式为mi,ai1,ai2,…,ai,mi。其中，第一个正整数mi表示本行后面的整数个数。后续的mi个整数表示小明对第i棵苹果树的操作记录。若aij(1≤j≤mi)为正整数，则表示小明进行了重新统计该棵树上的苹果个数的操作，统计的苹果个数为aij；若为零或负整数，则表示一次疏果操作，去掉的苹果个数是|aij|。
输入保证一定是正确的，满足：
1.ai1>0，即对于每棵树的记录，第一个操作一定是统计苹果的个数（初始状态，此时不用判断是否有苹果掉落）；
2.每次疏果操作保证操作后树上的苹果个数仍为正。
【输出格式】
输出到标准输出。
输出只有一行，包含三个整数T、D、E。其中，
·T为全部疏果操作结束后所有苹果树上剩下的苹果总数（假设每棵苹果树在最后一次统计苹果个数操作后苹果不会因为疏果以外的原因减少）；
·D为发生苹果掉落的苹果树的棵数；
·E为相邻连续三棵树发生苹果掉落情况的组数。
对于第三个统计量的解释：N棵苹果树A1,A2,…,AN排列成一个圆，那么A1与A2相邻，A2与A3相邻，…，AN-1与AN相邻，AN与A1相邻。如果Ai-1,Ai,Ai+1这三棵树都发生了苹果掉落的情况，则记为一组。形式化的，有
E=|{Ai|Drop(Pred(Ai))∧Drop(Ai)∧Drop(Succ(Ai))}|.
其中，Drop(Ai)表示苹果树Ai是否发生苹果掉落的情况，Pred(Ai)表示Ai的前一棵树Ai-1（如果i>1）或者AN（如果i=1），Succ(Ai)表示Ai的后一棵树Ai+1（如果i<N）或者A1（如果i=N）。
【样例1输入】
4
4 74 -7 -12 -5
5 73 -8 -6 59 -4
5 76 -5 -10 60 -2
5 80 -6 -15 59 0
【样例1输出】
222 1 0
【样例1解释】
全部操作结束后，第1棵树上剩下的苹果个数为74-7-12-5=50，第2棵为59-4=55，第3棵为60-2=58，第4棵为59-0=59。因此T=50+55+58+59=222。
其中，第3棵树在第2次统计之前剩下的苹果个数为76-5-10=61>60，因此发生了苹果掉落的情况。可以检验其他的树没有这种情况，因此D=1。
没有连续三棵树都发生苹果掉落的情况，因此E=0。
【样例2输入】
5
4 10 0 9 0
4 10 -2 7 0
2 10 0
4 10 -3 5 0
4 10 -1 8 0
【样例2输出】
39 4 2
【样例2解释】
第1、2、4、5棵树发生了苹果掉落的情况，因此D=4。其中，连续三棵树都发生苹果掉落情况的有(5,1,2)和(4,5,1)，因此E=2。
【子任务】
·mi≤1000，对所有1≤i≤N
·|aij|≤10^6，对所有1≤i≤N，1≤j≤mi
【提示】
·如果你的程序没有实现统计D和E的功能，请按照D=0，E=0输出结果，这样如果T的统计正确能够得到一部分分数。
·如果你的程序没有实现统计E的功能，请按照E=0输出结果，这样如果T和D的统计正确能够得到一部分分数。
#include <bits/stdc++.h>
using namespace std;
struct Tree{
int apple;
int isfall;
};
int main()
{
int n;
cin>>n;
Tree t[n+1];
int i,j;
for(i=1;i<=n;i++)
{
int num;
cin>>num;
t[i].isfall=0;
for(j=0;j<num;j++)
{
int val;
cin>>val;
if(val>0)
{
if(j!=0)
{
if(val!=t[i].apple) //因苹果掉落重新统计
t[i].isfall=1;
}
t[i].apple=val;
}
else //疏果操作
{
t[i].apple+=val;
}
}
}
int sum=0,falltree=0,fall3=0;
for(i=1;i<=n;i++)
{
sum+=t[i].apple;
if(t[i].isfall==1)
falltree++;
if(t[i].isfall==1 && t[i%n+1].isfall==1 && t[(i+1)%n+1].isfall==1)
fall3++;
}
cout<<sum<<" "<<falltree<<" "<<fall3;
return 0;
}
【题目背景】
二十四点是一款著名的纸牌游戏，其游戏的目标是使用3个加减乘除运算使得4张纸牌上数字的运算结果为24。
【题目描述】
定义每一个游戏由4个从1-9的数字和3个四则运算符组成，保证四则运算符将数字两两隔开，不存在括号和其他字符，运算顺序按照四则运算顺序进行。其中加法用符号+表示，减法用符号-表示，乘法用小写字母x表示，除法用符号/表示。在游戏里除法为整除，例如2 / 3 = 0，3 / 2 = 1，4 / 2 = 2。
老师给了你n个游戏的解，请你编写程序验证每个游戏的结果是否为24。
【输入格式】
从标准输入读入数据。
第一行输入一个整数n，从第2行开始到第n+1行中，每一行包含一个长度为7的字符串，为上述的24点游戏，保证数据格式合法。
【输出格式】
输出到标准输出。
包含n行，对于每一个游戏，如果其结果为24则输出字符串Yes，否则输出字符串No。
【样例1输入】
10
9+3+4x3
5+4x5x5
7-9-9+8
5x6/5x4
3+5+7+9
1x1+9-9
1x9-5/9
8/5+6x9
6x7-3x6
6x4+4/5
【样例1输出】
Yes
No
No
Yes
Yes
No
No
No
Yes
Yes
【样例1解释】
9 + 3 + 4 x 3 = 24
5 + 4 x 5 x 5 = 105
7 - 9 - 9 + 8 = -3
5 x 6 / 5 x 4 = 24
3 + 5 + 7 + 9 = 24
1 x 1 + 9 - 9 = 1
1 x 9 - 5 / 9 = 9
8 / 5 + 6 x 9 = 55
6 x 7 - 3 x 6 = 24
6 x 4 + 4 / 5 = 24
【子任务】
#include <bits/stdc++.h>
using namespace std;
vector<int> val; //计算数
vector<char> opt; //计算符
int main()
{
int n;
cin>>n;
int i;
while(n--)
{
string str;
cin>>str;
val.clear(); //计算新的一行表达式前将计算数向量清空
opt.clear(); //计算新的一行表达式前将计算符向量清空
for(i=0;i<4;i++)
{
val.push_back(str[i*2]-'0');
if(i<3)
opt.push_back(str[i*2+1]);
}
for(i=0;i<opt.size();i++) //先计算乘法和除法
{
if(opt[i]=='x')
{
int tmp;
tmp=val[i]*val[i+1]; //计算乘法结果
val.erase(val.begin()+i+1); //去掉乘数
val.erase(val.begin()+i); //去掉乘数
val.insert(val.begin()+i,tmp); //插入乘法结果
opt.erase(opt.begin()+i); //去掉乘号
i--;
}
else if(opt[i]=='/')
{
int tmp;
tmp=val[i]/val[i+1]; //计算除法结果
val.erase(val.begin()+i+1); //去掉除数
val.erase(val.begin()+i); //去掉被除数
val.insert(val.begin()+i,tmp); //插入除法结果
opt.erase(opt.begin()+i); //去掉除号
i--;
}
}
int ans; //表达式计算结果
ans=val[0];
for(i=0;i<opt.size();i++) //计算加法和减法
{
if(opt[i]=='+')
ans+=val[i+1];
else if(opt[i]=='-')
ans-=val[i+1];
}
if(ans==24)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}
【题目背景】
汉东省政法大学附属中学所在的光明区最近实施了名为“智慧光明”的智慧城市项目。具体到交通领域，通过“智慧光明”终端，可以看到光明区所有红绿灯此时此刻的状态。小明的学校也安装了“智慧光明”终端，小明想利用这个终端给出的信息，估算自己放学回到家的时间。
【问题描述】
一次放学的时候，小明已经规划好了自己回家的路线，并且能够预测经过各个路段的时间。同时，小明通过学校里安装的“智慧光明”终端，看到了出发时刻路上经过的所有红绿灯的指示状态。请帮忙计算小明此次回家所需要的时间。
【输入格式】
输入的第一行包含空格分隔的三个正整数 r、y、g，表示红绿灯的设置。这三个数均不超过 106。
输入的第二行包含一个正整数 n，表示小明总共经过的道路段数和路过的红绿灯数目。
接下来的 n 行，每行包含空格分隔的两个整数 k、t。k=0 表示经过了一段道路，将会耗时 t 秒，此处 t 不超过 10^6；k=1、2、3 时，分别表示出发时刻，此处的红绿灯状态是红灯、黄灯、绿灯，且倒计时显示牌上显示的数字是 t，此处 t 分别不会超过 r、y、g。
【输出格式】
输出一个数字，表示此次小明放学回家所用的时间。
【样例输入】
30 3 30
8
0 10
1 5
0 11
2 2
0 6
0 3
3 10
0 3
【样例输出】
46
【样例说明】
小明先经过第一段路，用时 10 秒。第一盏红绿灯出发时是红灯，还剩 5 秒；小明到达路口时，这个红绿灯已经变为绿灯，不用等待直接通过。接下来经过第二段路，用时 11 秒。第二盏红绿灯出发时是黄灯，还剩两秒；小明到达路口时，这个红绿灯已经变为红灯，还剩 11 秒。接下来经过第三、第四段路，用时 9 秒。第三盏红绿灯出发时是绿灯，还剩 10 秒；小明到达路口时，这个红绿灯已经变为红灯，还剩两秒。接下来经过最后一段路，用时 3 秒。共计 10+11+11+9+2+3 = 46 秒。
【评测用例规模与约定】
有些测试点具有特殊的性质：
* 前 2 个测试点中不存在任何信号灯。
测试点的输入数据规模：
* 前 6 个测试点保证 n ≤ 10^3。
* 所有测试点保证 n ≤ 10^5。
#include <bits/stdc++.h>
using namespace std;
struct Road{
int type; //路程或红绿灯
int time;
};
int main(){
int r,y,g;
cin>>r>>y>>g;
int n;
cin>>n;
Road road[n];
int i;
for(i=0;i<n;i++)
cin>>road[i].type>>road[i].time;
long long sumtime=0;
long long tmp;
//模拟回家路程
for(i=0;i<n;i++)
{
//道路
if(road[i].type==0)
{
sumtime+=road[i].time;
continue;
}
//红绿灯
else
{
tmp=sumtime%(r+y+g);
if(road[i].type==1) //初始为红灯
{
if(tmp<road[i].time) //到达时为初始红灯
sumtime+=road[i].time-tmp;
else if(tmp-road[i].time<g) //到达时为绿灯
sumtime+=0;
else if(tmp-road[i].time-g<y) //到达时为黄灯
sumtime+=y-(tmp-road[i].time-g)+r;
else //到达时为红灯
sumtime+=r-(tmp-road[i].time-g-y);
}
if(road[i].type==2) //初始为黄灯
{
if(tmp<road[i].time) //到达时为初始黄灯
sumtime+=road[i].time-tmp+r;
else if(tmp-road[i].time<r) //到达时为红灯
sumtime+=r-(tmp-road[i].time);
else if(tmp-road[i].time-r<g) //到达时为绿灯
sumtime+=0;
else //到达时为黄灯
sumtime+=y-(tmp-road[i].time-r-g)+r;
}
if(road[i].type==3) //初始为绿灯
{
if(tmp<road[i].time) //到达时为初始绿灯
sumtime+=0;
else if(tmp-road[i].time<y) //到达时为黄灯
sumtime+=y-(tmp-road[i].time)+r;
else if(tmp-road[i].time-y<r) //到达时为红灯
sumtime+=r-(tmp-road[i].time-y);
else //到达时为绿灯
sumtime+=0;
}
}
}
cout<<sumtime;
return 0;
}
【问题描述】
小H和小W来到了一条街上，两人分开买菜，他们买菜的过程可以描述为，去店里买一些菜然后去旁边的一个广场把菜装上车，两人都要买n种菜，所以也都要装n次车。具体的，对于小H来说有n个不相交的时间段[a1,b1],[a2,b2]…[an,bn]在装车，对于小W来说有n个不相交的时间段[c1,d1],[c2,d2]…[cn,dn]在装车。其中，一个时间段[s, t]表示的是从时刻s到时刻t这段时间，时长为t-s。
由于他们是好朋友，他们都在广场上装车的时候会聊天，他们想知道他们可以聊多长时间。
【输入格式】
输入的第一行包含一个正整数n，表示时间段的数量。
接下来n行每行两个数ai，bi，描述小H的各个装车的时间段。
接下来n行每行两个数ci，di，描述小W的各个装车的时间段。
【输出格式】
输出一行，一个正整数，表示两人可以聊多长时间。
【样例输入】
4
1 3
5 6
9 13
14 15
2 4
5 7
10 11
13 14
【样例输出】
3
【数据规模和约定】
对于所有的评测用例，1 ≤ n ≤ 2000, ai < bi < ai+1，ci < di < ci+1,对于所有的i(1 ≤ i ≤ n)有，1 ≤ ai, bi, ci, di ≤ 1000000。
#include <bits/stdc++.h>
using namespace std;
struct Load{
int begin;
int end;
};
int main()
{
int n;
cin>>n;
Load h[n],w[n];
int i,j;
int maxtime=0;
for(i=0;i<n;i++)
{
cin>>h[i].begin>>h[i].end;
if(h[i].end>maxtime)
maxtime=h[i].end;
}
for(i=0;i<n;i++)
{
cin>>w[i].begin>>w[i].end;
if(w[i].end>maxtime)
maxtime=w[i].end;
}
int p[maxtime+1]={};
for(i=0;i<n;i++) //某时刻有人在装车
{
for(j=h[i].begin;j<h[i].end;j++)
p[j]++;
for(j=w[i].begin;j<w[i].end;j++)
p[j]++;
}
int talktime=0;
for(i=0;i<=maxtime;i++)
{
if(p[i]==2)
talktime++;
}
cout<<talktime;
return 0;
}
【问题描述】
数轴上有一条长度为L（L为偶数)的线段，左端点在原点，右端点在坐标L处。有n个不计体积的小球在线段上，开始时所有的小球都处在偶数坐标上，速度方向向右，速度大小为1单位长度每秒。
当小球到达线段的端点（左端点或右端点）的时候，会立即向相反的方向移动，速度大小仍然为原来大小。
当两个小球撞到一起的时候，两个小球会分别向与自己原来移动的方向相反的方向，以原来的速度大小继续移动。
现在，告诉你线段的长度L，小球数量n，以及n个小球的初始位置，请你计算t秒之后，各个小球的位置。
【提示】
因为所有小球的初始位置都为偶数，而且线段的长度为偶数，可以证明，不会有三个小球同时相撞，小球到达线段端点以及小球之间的碰撞时刻均为整数。
同时也可以证明两个小球发生碰撞的位置一定是整数（但不一定是偶数）。
【输入格式】
输入的第一行包含三个整数n, L, t，用空格分隔，分别表示小球的个数、线段长度和你需要计算t秒之后小球的位置。
第二行包含n个整数a1, a2, …, an，用空格分隔，表示初始时刻n个小球的位置。
【输出格式】
输出一行包含n个整数，用空格分隔，第i个整数代表初始时刻位于ai的小球，在t秒之后的位置。
【样例输入】
3 10 5
4 6 8
【样例输出】
7 9 9
【样例说明】
初始时，三个小球的位置分别为4, 6, 8。
一秒后，三个小球的位置分别为5, 7, 9。
两秒后，第三个小球碰到墙壁，速度反向，三个小球位置分别为6, 8, 10。
三秒后，第二个小球与第三个小球在位置9发生碰撞，速度反向（注意碰撞位置不一定为偶数），三个小球位置分别为7, 9, 9。
四秒后，第一个小球与第二个小球在位置8发生碰撞，速度反向，第三个小球碰到墙壁，速度反向，三个小球位置分别为8, 8, 10。
五秒后，三个小球的位置分别为7, 9, 9。
【样例输入】
10 22 30
14 12 16 6 10 2 8 20 18 4
【样例输出】
6 6 8 2 4 0 4 12 10 2
【数据规模和约定】
对于所有评测用例，1 ≤ n ≤ 100，1 ≤ t ≤ 100，2 ≤ L ≤ 1000，0 < ai < L。L为偶数。
保证所有小球的初始位置互不相同且均为偶数。
#include <bits/stdc++.h>
using namespace std;
struct Ball{
int site;
int go;
};
int main()
{
int n,L,t;
cin>>n>>L>>t;
Ball b[n];
int i,j;
for(i=0;i<n;i++)
{
cin>>b[i].site;
b[i].go=1;
}
int time;
//判断小球下一秒向哪边走
for(time=0;time<t;time++)
{
for(i=0;i<n;i++)
{
if(b[i].site==L || b[i].site==0) //达到端点，改变方向
{
b[i].go*=-1;
}
for(j=0;j<n;j++) //与其他小球位置比较，若位置相同则发生碰撞
{
if(i==j)
continue;
else
if(b[i].site==b[j].site) //发生碰撞，改变方向
b[i].go*=-1;
}
}
for(i=0;i<n;i++) //小球移动
b[i].site+=b[i].go;
}
for(i=0;i<n;i++)
cout<<b[i].site<<" ";
return 0;
}
【问题描述】
有n个小朋友围成一圈玩游戏，小朋友从1至n编号，2号小朋友坐在1号小朋友的顺时针方向，3号小朋友坐在2号小朋友的顺时针方向，……，1号小朋友坐在n号小朋友的顺时针方向。
游戏开始，从1号小朋友开始顺时针报数，接下来每个小朋友的报数是上一个小朋友报的数加1。若一个小朋友报的数为k的倍数或其末位数（即数的个位）为k，则该小朋友被淘汰出局，不再参加以后的报数。当游戏中只剩下一个小朋友时，该小朋友获胜。
例如，当n=5, k=2时：
1号小朋友报数1；
2号小朋友报数2淘汰；
3号小朋友报数3；
4号小朋友报数4淘汰；
5号小朋友报数5；
1号小朋友报数6淘汰；
3号小朋友报数7；
5号小朋友报数8淘汰；
3号小朋友获胜。
给定n和k，请问最后获胜的小朋友编号为多少？
【输入格式】
输入一行，包括两个整数n和k，意义如题目所述。
【输出格式】
输出一行，包含一个整数，表示获胜的小朋友编号。
【样例输入】
5 2
【样例输出】
3
【样例输入】
7 3
【样例输出】
4
【数据规模和约定】
对于所有评测用例，1 ≤ n ≤ 1000，1 ≤ k ≤ 9。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,k;
cin>>n>>k;
int p[n];
int i;
for(i=0;i<n;i++)
p[i]=i+1;
int num=1;
int kid=n;
i=0;
//游戏过程
while(kid>1)
{
if(i==n) //第n个小朋友后为第1个小朋友
i=0;
if(p[i]==0) //已被淘汰，跳过
{
i++;
continue;
}
if(num%k==0 || num%10==k) //根据游戏规则，被淘汰
{
p[i]=0;
kid--;
}
i++;
num++;
}
for(i=0;i<n;i++)
{
if(p[i]!=0)
cout<<p[i];
}
return 0;
}
【问题描述】
有一个学校的老师共用N个教室，按照规定，所有的钥匙都必须放在公共钥匙盒里，老师不能带钥匙回家。每次老师上课前，都从公共钥匙盒里找到自己上课的教室的钥匙去开门，上完课后，再将钥匙放回到钥匙盒中。
钥匙盒一共有N个挂钩，从左到右排成一排，用来挂N个教室的钥匙。一串钥匙没有固定的悬挂位置，但钥匙上有标识，所以老师们不会弄混钥匙。
每次取钥匙的时候，老师们都会找到自己所需要的钥匙将其取走，而不会移动其他钥匙。每次还钥匙的时候，还钥匙的老师会找到最左边的空的挂钩，将钥匙挂在这个挂钩上。如果有多位老师还钥匙，则他们按钥匙编号从小到大的顺序还。如果同一时刻既有老师还钥匙又有老师取钥匙，则老师们会先将钥匙全还回去再取出。
今天开始的时候钥匙是按编号从小到大的顺序放在钥匙盒里的。有K位老师要上课，给出每位老师所需要的钥匙、开始上课的时间和上课的时长，假设下课时间就是还钥匙时间，请问最终钥匙盒里面钥匙的顺序是怎样的？
【输入格式】
输入的第一行包含两个整数N, K。
接下来K行，每行三个整数w, s, c，分别表示一位老师要使用的钥匙编号、开始上课的时间和上课的时长。可能有多位老师使用同一把钥匙，但是老师使用钥匙的时间不会重叠。
保证输入数据满足输入格式，你不用检查数据合法性。
【输出格式】
输出一行，包含N个整数，相邻整数间用一个空格分隔，依次表示每个挂钩上挂的钥匙编号。
【样例输入】
5 2
4 3 3
2 2 7
【样例输出】
1 4 3 2 5
【样例说明】
第一位老师从时刻3开始使用4号教室的钥匙，使用3单位时间，所以在时刻6还钥匙。第二位老师从时刻2开始使用钥匙，使用7单位时间，所以在时刻9还钥匙。
每个关键时刻后的钥匙状态如下（X表示空）：
时刻2后为1X345；
时刻3后为1X3X5；
时刻6后为143X5；
时刻9后为14325。
【样例输入】
5 7
1 1 14
3 3 12
1 15 12
2 7 20
3 18 12
4 21 19
5 30 9
【样例输出】
1 2 3 5 4
【评测用例规模与约定】
对于30%的评测用例，1 ≤ N, K ≤ 10, 1 ≤ w ≤ N, 1 ≤ s, c ≤ 30；
对于60%的评测用例，1 ≤ N, K ≤ 50，1 ≤ w ≤ N，1 ≤ s ≤ 300，1 ≤ c ≤ 50；
对于所有评测用例，1 ≤ N, K ≤ 1000，1 ≤ w ≤ N，1 ≤ s ≤ 10000，1 ≤ c ≤ 100。
#include <bits/stdc++.h>
using namespace std;
struct Class{
int key;
int begin;
int last;
};
bool comp(Class a,Class b){
if(a.begin+a.last==b.begin+b.last)
return a.key<b.key;
else
return a.begin+a.last<b.begin+b.last;
}
int main()
{
int n,k;
cin>>n>>k;
int keys[n+1];
int i,j;
//初始化钥匙盒，钥匙编号从小到大
for(i=1;i<=n;i++)
keys[i]=i;
Class c[k];
int maxtime;
for(i=0;i<k;i++)
{
cin>>c[i].key>>c[i].begin>>c[i].last;
if(c[i].begin+c[i].last>maxtime)
maxtime=c[i].begin+c[i].last;
}
//将教室使用按照归还钥匙时间从小到大排序，若归还时间相同，按钥匙编号从小到大排序
sort(c,c+k,comp);
int time;
//模拟时间增加
for(time=1;time<=maxtime;time++)
{
for(i=0;i<k;i++)
{
//时间为下课时间，先归还钥匙
if(time==(c[i].begin+c[i].last))
{
for(j=1;j<=n;j++)
{
if(keys[j]==0)
{
keys[j]=c[i].key;
break;
}
}
}
//时间为上课时间，后取走钥匙
if(time==c[i].begin)
{
for(j=1;j<=n;j++)
{
if(keys[j]==c[i].key)
{
keys[j]=0;
break;
}
}
}
}
}
for(i=1;i<=n;i++)
cout<<keys[i]<<" ";
return 0;
}
【问题描述】
体育老师小明要将自己班上的学生按顺序排队。他首先让学生按学号从小到大的顺序排成一排，学号小的排在前面，然后进行多次调整。一次调整小明可能让一位同学出队，向前或者向后移动一段距离后再插入队列。
例如，下面给出了一组移动的例子，例子中学生的人数为8人。
0）初始队列中学生的学号依次为1, 2, 3, 4, 5, 6, 7, 8；
1）第一次调整，命令为“3号同学向后移动2”，表示3号同学出队，向后移动2名同学的距离，再插入到队列中，新队列中学生的学号依次为1, 2, 4, 5, 3, 6, 7, 8；
2）第二次调整，命令为“8号同学向前移动3”，表示8号同学出队，向前移动3名同学的距离，再插入到队列中，新队列中学生的学号依次为1, 2, 4, 5, 8, 3, 6, 7；
3）第三次调整，命令为“3号同学向前移动2”，表示3号同学出队，向前移动2名同学的距离，再插入到队列中，新队列中学生的学号依次为1, 2, 4, 3, 5, 8, 6, 7。
小明记录了所有调整的过程，请问，最终从前向后所有学生的学号依次是多少？
请特别注意，上述移动过程中所涉及的号码指的是学号，而不是在队伍中的位置。在向后移动时，移动的距离不超过对应同学后面的人数，如果向后移动的距离正好等于对应同学后面的人数则该同学会移动到队列的最后面。在向前移动时，移动的距离不超过对应同学前面的人数，如果向前移动的距离正好等于对应同学前面的人数则该同学会移动到队列的最前面。
【输入格式】
输入的第一行包含一个整数n，表示学生的数量，学生的学号由1到n编号。
第二行包含一个整数m，表示调整的次数。
接下来m行，每行两个整数p, q，如果q为正，表示学号为p的同学向后移动q，如果q为负，表示学号为p的同学向前移动-q。
【输出格式】
输出一行，包含n个整数，相邻两个整数之间由一个空格分隔，表示最终从前向后所有学生的学号。
【样例输入】
8
3
3 2
8 -3
3 -2
【样例输出】
1 2 4 3 5 8 6 7
【评测用例规模与约定】
对于所有评测用例，1 ≤ n ≤ 1000，1 ≤ m ≤ 1000，所有移动均合法。
#include <bits/stdc++.h>
using namespace std;
struct Move{
int stu;
int mov;
};
int main()
{
int n;
cin>>n;
list<int> l;
int i;
for(i=1;i<=n;i++)
l.push_back(i);
int m;
cin>>m;
Move move[m];
for(i=0;i<m;i++)
cin>>move[i].stu>>move[i].mov;
list<int>::iterator it,it1,it2;
for(i=0;i<m;i++)
{
it1=l.begin();
while(*it1!=move[i].stu)
it1++;
if(move[i].mov>0) //向后移动
{
it2=it1;
while(move[i].mov>=0)
{
it2++;
move[i].mov--;
}
}
else //向前移动
{
it2=it1;
while(move[i].mov<0)
{
it2--;
move[i].mov++;
}
}
l.insert(it2,*it1); //在指定位置插入学生
l.erase(it1); //删除原位置的学生
}
for(it=l.begin();it!=l.end();it++)
cout<<*it<<" ";
return 0;
}
【问题描述】
小明的公司每个月给小明发工资，而小明拿到的工资为交完个人所得税之后的工资。假设他一个月的税前工资（扣除五险一金后、未扣税前的工资）为S元，则他应交的个人所得税按如下公式计算：
1） 个人所得税起征点为3500元，若S不超过3500，则不交税，3500元以上的部分才计算个人所得税，令A=S-3500元；
2） A中不超过1500元的部分，税率3%；
3） A中超过1500元未超过4500元的部分，税率10%；
4） A中超过4500元未超过9000元的部分，税率20%；
5） A中超过9000元未超过35000元的部分，税率25%；
6） A中超过35000元未超过55000元的部分，税率30%；
7） A中超过55000元未超过80000元的部分，税率35%；
8） A中超过80000元的部分，税率45%；
例如，如果小明的税前工资为10000元，则A=10000-3500=6500元，其中不超过1500元部分应缴税1500×3%=45元，超过1500元不超过4500元部分应缴税(4500-1500)×10%=300元，超过4500元部分应缴税(6500-4500)×20%=400元。总共缴税745元，税后所得为9255元。
已知小明这个月税后所得为T元，请问他的税前工资S是多少元。
【输入格式】
输入的第一行包含一个整数T，表示小明的税后所得。所有评测数据保证小明的税前工资为一个整百的数。
【输出格式】
输出一个整数S，表示小明的税前工资。
【样例输入】
9255
【样例输出】
10000
【评测用例规模与约定】
对于所有评测用例，1 ≤ T ≤ 100000。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
int s;
if(t<=3500)
s=t;
if(t>3500 && t<=4955)
s=(t-105)/97*100;
if(t>4955 && t<=7655)
s=(t-455)/90*100;
if(t>7655 && t<=11255)
s=(t-1255)/80*100;
if(t>11255 && t<=30755)
s=(t-1880)/75*100;
if(t>30755 && t<=44755)
s=(t-3805)/70*100;
if(t>44755 && t<=61005)
s=(t-6730)/65*100;
if(t>61005)
s=(t-15080)/55*100;
cout<<s;
return 0;
}
【问题描述】
请实现一个铁路购票系统的简单座位分配算法，来处理一节车厢的座位分配。
假设一节车厢有20排、每一排5个座位。为方便起见，我们用1到100来给所有的座位编号，第一排是1到5号，第二排是6到10号，依次类推，第20排是96到100号。
购票时，一个人可能购一张或多张票，最多不超过5张。如果这几张票可以安排在同一排编号相邻的座位，则应该安排在编号最小的相邻座位。否则应该安排在编号最小的几个空座位中（不考虑是否相邻）。
假设初始时车票全部未被购买，现在给了一些购票指令，请你处理这些指令。
【输入格式】
输入的第一行包含一个整数n，表示购票指令的数量。
第二行包含n个整数，每个整数p在1到5之间，表示要购入的票数，相邻的两个数之间使用一个空格分隔。
【输出格式】
输出n行，每行对应一条指令的处理结果。
对于购票指令p，输出p张车票的编号，按从小到大排序。
【样例输入】
4
2 5 4 2
【样例输出】
1 2
6 7 8 9 10
11 12 13 14
3 4
【样例说明】
1) 购2张票，得到座位1、2。
2) 购5张票，得到座位6至10。
3) 购4张票，得到座位11至14。
4) 购2张票，得到座位3、4。
【评测用例规模与约定】
对于所有评测用例，1 ≤ n ≤ 100，所有购票数量之和不超过100。
#include <bits/stdc++.h>
using namespace std;
// 座位排
struct Row{
int no; //排号
int remain; //剩余座位
};
int main()
{
Row r[20];
int i,j,k;
for(i=0;i<20;i++)
{
r[i].no=i;
r[i].remain=5;
}
int n;
cin>>n;
int p[n];
for(i=0;i<n;i++)
{
cin>>p[i];
}
for(i=0;i<n;i++)
{
for(j=0;j<20;j++)
{
//最小排号的剩余座位多于购买座位数
if(p[i]<=r[j].remain)
{
while(p[i]>0)
{
r[j].remain--; //剩余座位-1
cout<<(j+1)*5-r[j].remain<<" "; //输出购买座位号
p[i]--;
}
cout<<endl;
break;
}
}
//购买的票无法安排在相邻座位
if(j==20)
{
for(k=0;k<20;k++)
{
//安排在编号最小的几个空座位中
if(r[k].remain>0)
{
while(p[i]>0 && r[k].remain>0)
{
r[k].remain--;
cout<<(k+1)*5-r[k].remain<<" ";
p[i]--;
}
if(p[i]==0)
break;
}
}
}
}
return 0;
}
【问题描述】
俄罗斯方块是俄罗斯人阿列克谢·帕基特诺夫发明的一款休闲游戏。
游戏在一个15行10列的方格图上进行，方格图上的每一个格子可能已经放置了方块，或者没有放置方块。每一轮，都会有一个新的由4个小方块组成的板块从方格图的上方落下，玩家可以操作板块左右移动放到合适的位置，当板块中某一个方块的下边缘与方格图上的方块上边缘重合或者达到下边界时，板块不再移动，如果此时方格图的某一行全放满了方块，则该行被消除并得分。
在这个问题中，你需要写一个程序来模拟板块下落，你不需要处理玩家的操作，也不需要处理消行和得分。
具体的，给定一个初始的方格图，以及一个板块的形状和它下落的初始位置，你要给出最终的方格图。
【输入格式】
输入的前15行包含初始的方格图，每行包含10个数字，相邻的数字用空格分隔。如果一个数字是0，表示对应的方格中没有方块，如果数字是1，则表示初始的时候有方块。输入保证前4行中的数字都是0。
输入的第16至第19行包含新加入的板块的形状，每行包含4个数字，组成了板块图案，同样0表示没方块，1表示有方块。输入保证板块的图案中正好包含4个方块，且4个方块是连在一起的（准确的说，4个方块是四连通的，即给定的板块是俄罗斯方块的标准板块）。
第20行包含一个1到7之间的整数，表示板块图案最左边开始的时候是在方格图的哪一列中。注意，这里的板块图案指的是16至19行所输入的板块图案，如果板块图案的最左边一列全是0，则它的左边和实际所表示的板块的左边是不一致的（见样例）
【输出格式】
输出15行，每行10个数字，相邻的数字之间用一个空格分隔，表示板块下落后的方格图。注意，你不需要处理最终的消行。
【样例输入】
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0 0
1 1 1 0 0 0 1 1 1 1
0 0 0 0 1 0 0 0 0 0
0 0 0 0
0 1 1 1
0 0 0 1
0 0 0 0
3
【样例输出】
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0 0
1 1 1 1 1 1 1 1 1 1
0 0 0 0 1 1 0 0 0 0
#include <bits/stdc++.h>
using namespace std;
struct node{
int line;
int row;
};
int all[15][10];
int block[4][4];
int main()
{
int i,j;
//输入方格图
for(i=14;i>=0;i--)
{
for(j=0;j<10;j++)
{
cin>>all[i][j];
}
}
//输入板块图案
node n[4];
int k=0;
for(i=3;i>=0;i--)
{
for(j=0;j<4;j++)
{
cin>>block[i][j];
if(block[i][j]==1)
{
n[k].line=i;
n[k].row=j;
k++;
}
}
}
//消除板块图案下方空白(一行全为0)
bool flag1=false;
for(i=0;i<4;i++)
{
for(j=0;j<4;j++)
{
if(block[i][j]==1)
{
flag1=true;
break;
}
if(j==3)
{
for(k=0;k<4;k++)
{
n[k].line--;
}
}
}
if(flag1==true)
{
break;
}
}
int line,row;
cin>>row;
row-=1;
//模拟板块图案下降
bool flag2=false;
for(line=11;line>=0;line--)
{
for(i=0;i<4;i++)
{
if(all[line+n[i].line][row+n[i].row]==1) //下降产生重叠的第一行
{
flag2=true;
break;
}
}
if(flag2==true)
{
break;
}
}
line++; //产生重叠的第一行的上一行为可放置最低行
for(i=0;i<4;i++) //将板块图案加入方格图
{
all[line+n[i].line][row+n[i].row]=1;
}
for(i=14;i>=0;i--) //输出方格图
{
for(j=0;j<10;j++)
{
cout<<all[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
【问题描述】
消除类游戏是深受大众欢迎的一种游戏，游戏在一个包含有n行m列的游戏棋盘上进行，棋盘的每一行每一列的方格上放着一个有颜色的棋子，当一行或一列上有连续三个或更多的相同颜色的棋子时，这些棋子都被消除。当有多处可以被消除时，这些地方的棋子将同时被消除。
现在给你一个n行m列的棋盘，棋盘中的每一个方格上有一个棋子，请给出经过一次消除后的棋盘。
请注意：一个棋子可能在某一行和某一列同时被消除。
【输入格式】
输入的第一行包含两个整数n, m，用空格分隔，分别表示棋盘的行数和列数。
接下来n行，每行m个整数，用空格分隔，分别表示每一个方格中的棋子的颜色。颜色使用1至9编号。
【输出格式】
输出n行，每行m个整数，相邻的整数之间使用一个空格分隔，表示经过一次消除后的棋盘。如果一个方格中的棋子被消除，则对应的方格输出0，否则输出棋子的颜色编号。
【样例输入】
4 5
2 2 3 1 2
3 4 5 1 4
2 3 2 1 3
2 2 2 4 4
【样例输出】
2 2 3 0 2
3 4 5 0 4
2 3 2 0 3
0 0 0 4 4
【样例说明】
棋盘中第4列的1和第4行的2可以被消除，其他的方格中的棋子均保留。
【样例输入】
4 5
2 2 3 1 2
3 1 1 1 1
2 3 2 1 3
2 2 3 3 3
【样例输出】
2 2 3 0 2
3 0 0 0 0
2 3 2 0 3
2 2 0 0 0
【样例说明】
棋盘中所有的1以及最后一行的3可以被同时消除，其他的方格中的棋子均保留。
【评测用例规模与约定】
所有的评测用例满足：1 ≤ n, m ≤ 30。
#include <bits/stdc++.h>
using namespace std;
struct Piece{
int num; //棋子颜色
int cane; //是否该被消除
};
int main()
{
int n,m;
cin>>n>>m;
Piece p[n][m];
int i,j;
for(i=n-1;i>=0;i--)
{
for(j=0;j<m;j++)
{
cin>>p[i][j].num;
p[i][j].cane=0;
}
}
//判定每行哪些棋子可被消除
for(i=0;i<n;i++)
{
for(j=0;j<m-2;j++)
{
if(p[i][j].num==p[i][j+1].num && p[i][j].num==p[i][j+2].num)
{
p[i][j].cane=1;
p[i][j+1].cane=1;
p[i][j+2].cane=1;
}
}
}
//判定每列哪些棋子可被消除
for(j=0;j<m;j++)
{
for(i=0;i<n-2;i++)
{
if(p[i][j].num==p[i+1][j].num && p[i][j].num==p[i+2][j].num)
{
p[i][j].cane=1;
p[i+1][j].cane=1;
p[i+2][j].cane=1;
}
}
}
//消除
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(p[i][j].cane==1)
{
p[i][j].num=0;
}
}
}
//输出
for(i=n-1;i>=0;i--)
{
for(j=0;j<m;j++)
{
cout<<p[i][j].num<<" ";
}
cout<<endl;
}
return 0;
}
【问题描述】
给定一个年份y和一个整数d，问这一年的第d天是几月几日？
注意闰年的2月有29天。满足下面条件之一的是闰年：
1） 年份是4的整数倍，而且不是100的整数倍；
2） 年份是400的整数倍。
【输入格式】
输入的第一行包含一个整数y，表示年份，年份在1900到2015之间（包含1900和2015）。
输入的第二行包含一个整数d，d在1至365之间。
【输出格式】
输出两行，每行一个整数，分别表示答案的月份和日期。
【样例输入】
2015
80
【样例输出】
3
21
【样例输入】
2000
40
【样例输出】
2
9
#include <bits/stdc++.h>
using namespace std;
int main()
{
int y,d;
cin>>y>>d;
bool runy=false;
if((y%4==0 && y%100!=0) || (y%400==0))
runy=true;
int pingday[12]={31,28,31,30,31,30,31,31,30,31,30,31};
int runday[12]={31,29,31,30,31,30,31,31,30,31,30,31};
int i=0;
while(d>0)
{
if(runy)
{
d-=runday[i];
}
if(!runy)
{
d-=pingday[i];
}
i++;
}
if(runy)
{
d+=runday[i-1];
}
if(!runy)
{
d+=pingday[i-1];
}
cout<<i<<endl<<d;
return 0;
}
【问题描述】
给定n个整数，请统计出每个整数出现的次数，按出现次数从多到少的顺序输出。
【输入格式】
输入的第一行包含一个整数n，表示给定数字的个数。
第二行包含n个整数，相邻的整数之间用一个空格分隔，表示所给定的整数。
【输出格式】
输出多行，每行包含两个整数，分别表示一个给定的整数和它出现的次数。按出现次数递减的顺序输出。如果两个整数出现的次数一样多，则先输出值较小的，然后输出值较大的。
【样例输入】
12
5 2 3 3 1 3 4 2 5 2 3 5
【样例输出】
3 4
2 3
5 3
1 1
4 1
【评测用例规模与约定】
1 ≤ n ≤ 1000，给出的数都是不超过1000的非负整数。
#include <bits/stdc++.h>
using namespace std;
//定义比较函数
bool comp(pair<int,int> a,pair<int,int> b){
if(a.second==b.second)
{
return a.first<b.first;
}
else
{
return a.second>b.second;
}
}
int main()
{
int n;
cin>>n;
int val;
map<int,int> m;
int i;
//输入map，键为数字，值为次数
for(i=0;i<n;i++)
{
cin>>val;
m[val]++;
}
vector< pair<int,int> > v;
map<int,int>::iterator it1;
//将map中键值对根据value排序方法：将map中键值对以pair形式存入vector，使用自定义比较函数比较
for(it1=m.begin();it1!=m.end();it1++)
{
v.push_back(pair<int,int>(it1->first,it1->second));
}
//根据自定义比较函数比较大小
sort(v.begin(),v.end(),comp);
//输出
vector< pair<int,int> >::iterator it2;
for(it2=v.begin();it2!=v.end();it2++)
{
cout<<it2->first<<" "<<it2->second<<endl;
}
return 0;
}
【问题描述】
在图像编码的算法中，需要将一个给定的方形矩阵进行Z字形扫描(Zigzag Scan)。给定一个n×n的矩阵，Z字形扫描的过程如下图所示：
对于下面的4×4的矩阵，
1 5 3 9
3 7 5 6
9 4 6 4
7 3 1 3
对其进行Z字形扫描后得到长度为16的序列：
1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3
请实现一个Z字形扫描的程序，给定一个n×n的矩阵，输出对这个矩阵进行Z字形扫描的结果。
【输入格式】
输入的第一行包含一个整数n，表示矩阵的大小。
输入的第二行到第n+1行每行包含n个正整数，由空格分隔，表示给定的矩阵。
【输出格式】
输出一行，包含n×n个整数，由空格分隔，表示输入的矩阵经过Z字形扫描后的结果。
【样例输入】
4
1 5 3 9
3 7 5 6
9 4 6 4
7 3 1 3
【样例输出】
1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3
【评测用例规模与约定】
1≤n≤500，矩阵元素为不超过1000的正整数。
#include <bits/stdc++.h>
using namespace std;
int a[501][501]={};
int main()
{
int n;
cin>>n;
int i,j;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
cin>>a[i][j];
}
}
for(i=0;i<=2*(n-1);i++)
{
int x,y;
if(i<n && i%2==0)
{
x=i;
while(x>=0)
{
y=i-x;
cout<<a[x][y]<<" ";
x--;
}
}
if(i<n && i%2==1)
{
x=0;
while(x<=i)
{
y=i-x;
cout<<a[x][y]<<" ";
x++;
}
}
if(i>=n && i%2==0)
{
x=n-1;
while(x>=i-(n-1))
{
y=i-x;
cout<<a[x][y]<<" ";
x--;
}
}
if(i>=n && i%2==1)
{
x=i-(n-1);
while(x<=n-1)
{
y=i-x;
cout<<a[x][y]<<" ";
x++;
}
}
}
return 0;
}
【问题描述】
在一个定义了直角坐标系的纸上，画一个(x1,y1)到(x2,y2)的矩形指将横坐标范围从x1到x2，纵坐标范围从y1到y2之间的区域涂上颜色。
下图给出了一个画了两个矩形的例子。第一个矩形是(1,1) 到(4, 4)，用绿色和紫色表示。第二个矩形是(2, 3)到(6, 5)，用蓝色和紫色表示。图中，一共有15个单位的面积被涂上颜色，其中紫色部分被涂了两次，但在计算面积时只计算一次。在实际的涂色过程中，所有的矩形都涂成统一的颜色，图中显示不同颜色仅为说明方便。
给出所有要画的矩形，请问总共有多少个单位的面积被涂上颜色。
【输入格式】
输入的第一行包含一个整数n，表示要画的矩形的个数。
接下来n行，每行4个非负整数，分别表示要画的矩形的左下角的横坐标与纵坐标，以及右上角的横坐标与纵坐标。
【输出格式】
输出一个整数，表示有多少个单位的面积被涂上颜色。
【样例输入】
2
1 1 4 4
2 3 6 5
【样例输出】
15
【评测用例规模与约定】
1<=n<=100，0<=横坐标、纵坐标<=100。
#include <bits/stdc++.h>
using namespace std;
struct rec{
int x1;
int y1;
int x2;
int y2;
};
int a[101][101]={};
int main()
{
int n;
cin>>n;
rec r[n];
int i,j,k;
for(i=0;i<n;i++)
{
cin>>r[i].x1>>r[i].y1>>r[i].x2>>r[i].y2;
}
int sum=0;
i=0;
while(i<n)
{
for(j=r[i].x1;j<r[i].x2;j++)
{
for(k=r[i].y1;k<r[i].y2;k++)
{
if(a[j][k]==0)
{
a[j][k]=1;
sum++;
}
}
}
i++;
}
cout<<sum;
return 0;
}
【问题描述】
在某图形操作系统中,有 N 个窗口,每个窗口都是一个两边与坐标轴分别平行的矩形区域。窗口的边界上的点也属于该窗口。窗口之间有层次的区别,在多于一个窗口重叠的区域里,只会显示位于顶层的窗口里的内容。
当你点击屏幕上一个点的时候,你就选择了处于被点击位置的最顶层窗口,并且这个窗口就会被移到所有窗口的最顶层,而剩余的窗口的层次顺序不变。如果你点击的位置不属于任何窗口,则系统会忽略你这次点击。
现在我们希望你写一个程序模拟点击窗口的过程。
【输入格式】
输入的第一行有两个正整数,即 N 和 M。(1 ≤ N ≤ 10,1 ≤ M ≤ 10)
接下来 N 行按照从最下层到最顶层的顺序给出 N 个窗口的位置。 每行包含四个非负整数 x1, y1, x2, y2,表示该窗口的一对顶点坐标分别为 (x1, y1) 和 (x2, y2)。保证 x1 < x2,y1 2。
接下来 M 行每行包含两个非负整数 x, y,表示一次鼠标点击的坐标。
题目中涉及到的所有点和矩形的顶点的 x, y 坐标分别不超过 2559 和1439。
【输出格式】
输出包括 M 行,每一行表示一次鼠标点击的结果。如果该次鼠标点击选择了一个窗口,则输出这个窗口的编号(窗口按照输入中的顺序从 1 编号到 N);如果没有,则输出"IGNORED"(不含双引号)。
【样例输入】
3 4
0 0 4 4
1 1 5 5
2 2 6 6
1 1
0 0
4 4
0 5
【样例输出】
2
1
1
IGNORED
【样例说明】
第一次点击的位置同时属于第 1 和第 2 个窗口,但是由于第 2 个窗口在上面,它被选择并且被置于顶层。
第二次点击的位置只属于第 1 个窗口,因此该次点击选择了此窗口并将其置于顶层。现在的三个窗口的层次关系与初始状态恰好相反了。
第三次点击的位置同时属于三个窗口的范围,但是由于现在第 1 个窗口处于顶层,它被选择。
最后点击的 (0, 5) 不属于任何窗口。
#include <bits/stdc++.h>
using namespace std;
int screen[2560][1440]={0};
int main()
{
int n,m;
cin>>n>>m;
int i,j,k;
int window[n+1][4];
for(i=1;i<=n;i++) //输入窗口信息
{
cin>>window[i][0]>>window[i][1]>>window[i][2]>>window[i][3];
}
int dot[m+1][2];
for(i=1;i<=m;i++) //输入点信息
{
cin>>dot[i][0]>>dot[i][1];
}
for(i=1;i<=n;i++) //窗口初始化
{
for(j=window[i][0];j<=window[i][2];j++)
{
for(k=window[i][1];k<=window[i][3];k++)
{
screen[j][k]=i;
}
}
}
for(i=1;i<=m;i++)
{
if(screen[dot[i][0]][dot[i][1]]==0)
{
cout<<"IGNORED"<<endl;
}
else
{
int w=screen[dot[i][0]][dot[i][1]];
cout<<w<<endl;
for(j=window[w][0];j<=window[w][2];j++) //将点击窗口移至最上层
{
for(k=window[w][1];k<=window[w][3];k++)
{
screen[j][k]=w;
}
}
}
}
return 0;
}
【问题描述】
每一本正式出版的图书都有一个ISBN号码与之对应，ISBN码包括9位数字、1位识别码和3位分隔符，其规定格式如“x-xxx-xxxxx-x”，其中符号“-”是分隔符（键盘上的减号），最后一位是识别码，例如0-670-82162-4就是一个标准的ISBN码。ISBN码的首位数字表示书籍的出版语言，例如0代表英语；第一个分隔符“-”之后的三位数字代表出版社，例如670代表维京出版社；第二个分隔之后的五位数字代表该书在出版社的编号；最后一位为识别码。
识别码的计算方法如下：
首位数字乘以1加上次位数字乘以2……以此类推，用所得的结果mod 11，所得的余数即为识别码，如果余数为10，则识别码为大写字母X。例如ISBN号码0-670-82162-4中的识别码4是这样得到的：对067082162这9个数字，从左至右，分别乘以1，2，…，9，再求和，即0×1+6×2+……+2×9=158，然后取158 mod 11的结果4作为识别码。
编写程序判断输入的ISBN号码中识别码是否正确，如果正确，则仅输出“Right”；如果错误，则输出是正确的ISBN号码。
【输入格式】
输入只有一行，是一个字符序列，表示一本书的ISBN号码（保证输入符合ISBN号码的格式要求）。
【输出格式】
输出一行，假如输入的ISBN号码的识别码正确，那么输出“Right”，否则，按照规定的格式，输出正确的ISBN号码（包括分隔符“-”）。
【样例输入】
0-670-82162-4
【样例输出】
Right
【样例输入】
0-670-82162-0
【样例输出】
0-670-82162-4
#include <bits/stdc++.h>
using namespace std;
int main()
{
string isbn;
getline(cin,isbn); //获取包含字符的一行输入
int sum;
sum=(isbn[0]-'0')*1+(isbn[2]-'0')*2+(isbn[3]-'0')*3+(isbn[4]-'0')*4+(isbn[6]-'0')*5+(isbn[7]-'0')*6+(isbn[8]-'0')*7+(isbn[9]-'0')*8+(isbn[10]-'0')*9;
int sign;
sign=sum%11;
if(sign==10) //标识码为X时，ASCII码转换
{
sign='X'-'0';
}
if(sign==isbn[12]-'0')
{
cout<<"Right";
}
else
{
isbn[12]=sign+'0';
cout<<isbn;
}
return 0;
}