网站建设计,地方网站方案,货运app开发公司,saas系统是什么意思啊2022-12-10青少年软件编程#xff08;C语言#xff09;等级考试试卷#xff08;六级#xff09;解析T1、区间合并 给定 n 个闭区间 [ai; bi]#xff0c;其中i1,2,...,n。任意两个相邻或相交的闭区间可以合并为一个闭区间。例如#xff0c;[1;2] 和 [2;3] 可以合并为 [1;3…2022-12-10青少年软件编程C语言等级考试试卷六级解析T1、区间合并 给定 n 个闭区间 [ai; bi]其中i1,2,...,n。任意两个相邻或相交的闭区间可以合并为一个闭区间。例如[1;2] 和 [2;3] 可以合并为 [1;3][1;3] 和 [2;4] 可以合并为 [1;4]但是[1;2] 和 [3;4] 不可以合并。 我们的任务是判断这些区间是否可以最终合并为一个闭区间如果可以将这个闭区间输出否则输出no。 时间限制1000 内存限制65536 输入 第一行为一个整数n3 ≤ n ≤ 50000。表示输入区间的数量。 之后n行在第i行上1 ≤ i ≤ n为两个整数 ai 和 bi 整数之间用一个空格分隔表示区间 [ai; bi]其中 1 ≤ ai ≤ bi ≤ 10000。 输出 输出一行如果这些区间最终可以合并为一个闭区间输出这个闭区间的左右边界用单个空格隔开否则输出 no。 样例输入 5 5 6 1 5 10 10 6 9 8 10 样例输出 1 10
//样例代码 结构体排序
#include bits/stdc.h
using namespace std;
struct Nod{int x,y;friend bool operator (Nod a,Nod b){if(a.x!b.x)return a.xb.x;else return a.yb.y;}
}node[50005];
int main()
{ int n;cinn;for(int i0;in;i)cinnode[i].xnode[i].y;sort(node,noden);int lfnode[0].x;int rtnode[0].y;for(int i1;in;i){if(lfnode[i].xnode[i].xrt){rtmax(rt,node[i].y);}else {coutno;return 0;}}coutlf rt;return 0;
}
T2、电话号码 给你一些电话号码请判断它们是否是一致的即是否有某个电话是另一个电话的前缀。比如 Emergency 911 Alice 97 625 999 Bob 91 12 54 26 在这个例子中我们不可能拨通Bob的电话因为Emergency的电话是它的前缀当拨打Bob的电话时会先接通Emergency所以这些电话号码不是一致的。 时间限制1000 内存限制65536 输入 第一行是一个整数t1 ≤ t ≤ 40表示测试数据的数目。 每个测试样例的第一行是一个整数n1 ≤ n ≤ 10000其后n行每行是一个不超过10位的电话号码。 输出 对于每个测试数据如果是一致的输出“YES”如果不是输出“NO”。 样例输入 2 3 911 97625999 91125426 5 113 12340 123440 12345 98346 样例输出 NO YES
//示例代码
#include bits/stdc.h
using namespace std;
const int N1e510;
struct Trie
{int c[10],s;Trie(){memset(c,0,sizeof(c));s0;}
}t[N];int tot;
void clear(int x)
{t[x].s0;for(int i0;i9;i)if(t[x].c[i])clear(t[x].c[i]),t[x].c[i]0;
}
char s[15];
bool bt(int x)
{int lenstrlen(s1);bool bkfalse;for(int i1;ilen;i){int ys[i]-0;if(!t[x].c[y])t[x].c[y]tot;else if(ilen)bktrue;xt[x].c[y];if(t[x].s)bktrue;}t[x].s;return bk;
}
int main()
{int T;scanf(%d,T);while(T--){bool bkfalse;clear(0);tot0;int n;scanf(%d,n);for(int i1;in;i){scanf(%s,s1);if(bk)continue;if(bt(0))bktrue;}if(bk)puts(NO);else puts(YES);}return 0;
}T3、扑克牌排序 假设这里有36张扑克牌分别为A1~A9,B1~B9,C1~C9,D1~D9其中A代表方片B代表草花C代表红桃D代表黑桃那么设定如下的排序规则 1.对于两张卡牌X1Y1与X2Y2X1与X2表示ADY1与Y2表示19如果X1与X2不同那么依照DCBA的方式进行排序 2.假如有X1与X2相同时那么就比较Y1与Y2的大小。 例如对于如下的四张牌有如下的升序排序结果 D3C4A4C1 升序排序的结果为A4C1C4D3 有人提出了如下的排序策略 先建立9个队列用于存放点数的大小将卡牌依点数存放入各自的队列之中然后再按队列1到队列9依次出队。 例如对于上面的结果依次进队后结果如下 队列1C1队列3D3队列4C4A4 将其依次出队后结果为C1D3C4A4 然后再建立4个队列用于存放花色。将卡牌依花色AD存放入队列14中然后再按队列1到队列4依次出队。 例如对于上面刚刚出队的序列C1D3C4A4将其依次进队结果如下 队列1A4队列3C1C4队列4D3 将其依次出队后结果为A4C1C4D3排序结束。 请根据上面的算法编写一个用队列对扑克牌排序的程序要求依照上面的排序规则根据先花色后点数的方法进行排序。 时间限制1000 内存限制65536 输入 输入分为两行第一行为一个整数n表示一共有n张牌1n100 第二行用XY的形式表示每一张牌其中X为ADY为19 输出 输出三个部分 第一个部分为第一次进队出队的结果用Queue1:...表示共9行结果用空格分隔下同 第二部分为第二次进队出队的结果用QueueA:...表示共4行 第三部分为一行即将卡牌排序后的结果升序排序 样例输入 8 D8 A6 C3 B8 C5 A1 B5 D3 样例输出 Queue1:A1 Queue2: Queue3:C3 D3 Queue4: Queue5:C5 B5 Queue6:A6 Queue7: Queue8:D8 B8 Queue9: QueueA:A1 A6 QueueB:B5 B8 QueueC:C3 C5 QueueD:D3 D8 A1 A6 B5 B8 C3 C5 D3 D8 提示 第二次入队出队时可以复用第一次时9个队列中的4个。所以其实只需要开辟9个队列即可。
//示例代码 队列的基本操作 模拟一下即可
#include bits/stdc.h
using namespace std;
int main()
{ int n;string s;queuestring qn[9];queuestring color[4];queuestring qs;cinn;for(int i1;in;i){cins;int ts[1]-0-1;qn[t].push(s);}for(int i0;i8;i){coutQueuei1:;while(!qn[i].empty()){sqn[i].front();switch (s[0]) {case A:color[0].push(s);break;case B:color[1].push(s);break;case C:color[2].push(s);break;case D:color[3].push(s);break;}qn[i].pop();couts ;}coutendl; }for(int i0;i3;i){coutQueue(char)(Ai):;while(!color[i].empty()){scolor[i].front();color[i].pop();qs.push(s);couts ;}coutendl; }while(!qs.empty()){coutqs.front() ;qs.pop();}return 0;
}
T4、现代艺术 在对二维艺术作品感到厌烦之后伟大的艺术牛Picowso决定从事创作一项更为小众的艺术形式一维画。 尽管目前她的画作可以用一个由颜色组成的长度为N(1~100000)的数组表示但她的创作风格依然保持不变从一张空白的矩形画布上不断地画上一些矩形在一维的情况下这些矩形就只是一个区间。她用N种颜色颜色编号为1~N进行创作每种颜色只使用一次之后使用的颜色可以完全的覆盖之前在相同位置上的颜色。 令Picowso感到十分沮丧的是她的竞争对手Moonet似乎弄明白了如何复制她的这些一维画作Moonet会画一些不相交的间隔等待这些颜色晾干然后再画另外的一些间隔直到画完。Moonet每次每种颜色最多只能画一个间隔但是他可以一次画不同颜色不相交的多个间隔只要这些间隔没有重叠部分。之后Moonet再进行下一轮绘制。请计算Moonet为了复制一幅画需要画几个回合。 时间限制10000 内存限制65536 输入 第一行是一个整数N之后N行包含了N个整数范围0到N表示纸带每个格点的颜色0表示没有涂色。 输出 输出一行需要复制这幅画作的最少回合数如果这幅画不可能是Picowso的画作输出-1比如说这幅画不可能是通过一次在一条上画一层的方法进行创作的 样例输入 7 0 1 4 5 1 3 3 样例输出 2 提示 在这个样例中第一轮涂成0111133第二轮涂成0145133所以共需两轮。
// 示例代码 栈的灵活应用
#includebits/stdc.h
using namespace std;
const int N100010;
int end_pos[N], a[N];
int n, result, flag 1;
char v[N];
stackint s;
int main(){scanf(%d, n);for(int i 1;i n;i 1){scanf(%d, a[i]);end_pos[a[i]] i; //记录每个颜色的终点位置}v[0] 1;// 初始化 将0视为覆盖整个画布的第一种颜色end_pos[0] n 1;s.push(0); for(int i 1;i n flag;i){if(s.top() ! a[i]){if(v[a[i]]) flag 0;//颜色被使用过 标记非法s.push(a[i]); //加入新的颜色}v[a[i]] 1; //标记该颜色被使用过result max(result, (int)s.size()); if(i end_pos[a[i]]){s.pop();//该颜色最后一次被使用 弹出改颜色} }if(!flag) cout-1;else coutresult-1;return 0;
}
