京东购物app下载安装,蚌埠seo推广,天空影院手机免费观看在线,兰州做系统优化的公司P1003 [NOIP2011 提高组] 铺地毯
题目描述
原题点这里--P1003 [NOIP2011 提高组] 铺地毯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
为了准备一个独特的颁奖典礼#xff0c;组织者在会场的一片矩形区域#xff08;可看做是平面直角坐标系的第一象限#xff09;铺…P1003 [NOIP2011 提高组] 铺地毯
题目描述
原题点这里--P1003 [NOIP2011 提高组] 铺地毯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
为了准备一个独特的颁奖典礼组织者在会场的一片矩形区域可看做是平面直角坐标系的第一象限铺上一些矩形地毯。一共有 n 张地毯编号从 11 到 n。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设后铺的地毯覆盖在前面已经铺好的地毯之上。
地毯铺设完成后组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意在矩形地毯边界和四个顶点上的点也算被地毯覆盖。
输入格式
输入共 n2 行。
第一行一个整数 n表示总共有 n 张地毯。
接下来的 n 行中第 i1 行表示编号 i 的地毯的信息包含四个整数a,b,g,k每两个整数之间用一个空格隔开分别表示铺设地毯的左下角的坐标 (a,b) 以及地毯在 x 轴和 y 轴方向的长度。
第 n2 行包含两个整数 x 和 y表示所求的地面的点的坐标 (x,y)。
输出格式
输出共 1 行一个整数表示所求的地毯的编号若此处没有被地毯覆盖则输出 -1。
输入输出样例
输入 #1
3
1 0 2 3
0 2 3 3
2 1 3 3
2 2输出 #1
3输入 #2
3
1 0 2 3
0 2 3 3
2 1 3 3
4 5
输出 #2
-1
说明/提示
【样例解释 1】
如下图11 号地毯用实线表示22 号地毯用虚线表示33 号用双实线表示覆盖点 (2,2)(2,2) 的最上面一张地毯是 33 号地毯。 【数据范围】
对于 30%30% 的数据有 n≤2。 对于 50%50% 的数据0≤a,b,g,k≤100。 对于 100%100% 的数据有 0≤n≤10000, 0≤a,b,g,k≤100000。
解题过程
找到最后一块覆盖目标点的地毯即可所以我们从后往前遍历每块地毯寻找能覆盖目标点的地毯。如果地毯的左下角横纵坐标小于等于目标点的横纵坐标并且地毯的右上角横纵坐标大于等于目标点的横纵坐标说明该地毯覆盖目标点。
源代码
#includestdio.htypedef struct{int x,y,lx,ly;//地毯左下角坐标和地毯xy轴上的长度
}DT;DT dt[10010];//储存每块地毯的数据 int main()
{int n,kx,ky;scanf(%d,n);for(int i1;in;i){scanf(%d%d%d%d,dt[i].x,dt[i].y,dt[i].lx,dt[i].ly);} scanf(%d%d,kx,ky);//从最后一块地毯往前遍历 for(int in;i1;i--) {//如果地毯的左下角横纵坐标小于等于目标点的横纵坐标并且地毯的右上角横纵坐标大于等于目标点的横纵坐标说明该地毯覆盖该点 if(dt[i].xkxdt[i].ykydt[i].xdt[i].lxkxdt[i].ydt[i].lyky){printf(%d,i);return 0;}}//没有覆盖目标点的地毯输出-1 printf(-1);return 0;
}P1067 [NOIP2009 普及组] 多项式输出
题目描述
原题点这里--P1067 [NOIP2009 普及组] 多项式输出 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
一元 n 次多项式可用如下的表达式表示
f(x)anxnan−1xn−1⋯a1xa0,an0
其中aixi 称为 i 次项ai 称为 i 次项的系数。给出一个一元多项式各项的次数和系数请按照如下规定的格式要求输出该多项式 多项式中自变量为 x从左到右按照次数递减顺序给出多项式。 多项式中只包含系数不为 0 的项。 如果多项式 n 次项系数为正则多项式开头不出 号如果多项式 n 次项系数为负则多项式以 - 号开头。 对于不是最高次的项以 号或者 - 号连接此项与前一项分别表示此项系数为正或者系数为负。紧跟一个正整数表示此项系数的绝对值如果一个高于0 次的项其系数的绝对值为 11则无需输出 1。如果 x 的指数大于 1则接下来紧跟的指数部分的形式为“xb”其中 b 为 x 的指数如果 x 的指数为 1则接下来紧跟的指数部分形式为 x如果 x 的指数为 0则仅需输出系数即可。 多项式中多项式的开头、结尾不含多余的空格。
输入格式
输入共有 2 行
第一行 1 个整数n表示一元多项式的次数。
第二行有 n1 个整数其中第 i 个整数表示第 n−i1 次项的系数每两个整数之间用空格隔开。
输出格式
输出共 1 行按题目所述格式输出多项式。
输入输出样例
输入 #1
5
100 -1 1 -3 0 10
输出 #1
100x^5-x^4x^3-3x^210
输入 #2
3
-50 0 0 1 输出 #2
-50x^31 说明/提示
NOIP 2009 普及组 第一题
对于100%数据0≤n≤100−100≤系数≤100
解题过程
将输出内容拆成两部分系数部分和指数部分考虑即可。需要充分考虑各种情况。
源代码
#includestdio.hint main()
{int n;scanf(%d,n);int a;int tn;while(t0){scanf(%d,a);//输出系数部分if(n0){printf(%d,a);} else if(a0){}else if(tn){if(a!1a!-1)printf(%d,a);if(a-1)printf(-);}else if(t!0){if(a!1a!-1)printf(%d,a);if(a-1)printf(-);if(a1)printf();}else{printf(%d,a);}//输出次数部分if(at){if(t1)printf(x);elseprintf(x^%d,t);}t--; }return 0;
}P1540 [NOIP2010 提高组] 机器翻译
题目描述
原题点这里--P1540 [NOIP2010 提高组] 机器翻译 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
小晨的电脑上安装了一个机器翻译软件他经常用这个软件来翻译英语文章。
这个翻译软件的原理很简单它只是从头到尾依次将每个英文单词用对应的中文含义来替换。对于每个英文单词软件会先在内存中查找这个单词的中文含义如果内存中有软件就会用它进行翻译如果内存中没有软件就会在外存中的词典内查找查出单词的中文含义然后翻译并将这个单词和译义放入内存以备后续的查找和翻译。
假设内存中有 M 个单元每单元能存放一个单词和译义。每当软件将一个新单词存入内存前如果当前内存中已存入的单词数不超过 M−1软件会将新单词存入一个未使用的内存单元若内存中已存入 M 个单词软件会清空最早进入内存的那个单词腾出单元来存放新单词。
假设一篇英语文章的长度为 N 个单词。给定这篇待译文章翻译软件需要去外存查找多少次词典假设在翻译开始前内存中没有任何单词。
输入格式
共 2 行。每行中两个数之间用一个空格隔开。
第一行为两个正整数M,N代表内存容量和文章的长度。
第二行为 N 个非负整数按照文章的顺序每个数大小不超过 1000代表一个英文单词。文章中两个单词是同一个单词当且仅当它们对应的非负整数相同。
输出格式
一个整数为软件需要查词典的次数。
输入输出样例
输入 #1
3 7
1 2 1 5 4 4 1输出 #1
5说明/提示
样例解释
整个查字典过程如下每行表示一个单词的翻译冒号前为本次翻译后的内存状况
1查找单词 1 并调入内存。1 2查找单词 2 并调入内存。1 2在内存中找到单词 1。1 2 5查找单词 5 并调入内存。2 5 4查找单词 4 并调入内存替代单词 1。2 5 4在内存中找到单词 4。5 4 1查找单词 1 并调入内存替代单词 2。
共计查了 55 次词典。
数据范围
对于 10%10% 的数据有 M1N≤5对于 100%100% 的数据有 11≤M≤1001≤N≤1000。 解题过程
第n-1个需要存入内存的数存储在内存的第n-1%M个位置从第0个位置开始存。
源代码
#includestdio.hbool a[1005];//a[i]用于判断i是否在内存中
int nc[105];//记录内存中储存的数
int b0;
int main()
{int m,n;scanf(%d%d,m,n);//初始化nc数组中的数为-1 for(int i0;im;i)nc[i]-1;int t;for(int i0;in;i){scanf(%d,t);if(!a[t])//内存中没有 {a[nc[b%m]]false;a[t]true; nc[b%m]t;//将t存入内存将内存中的第b%m位移出内存 b;//每次内存中找不到都需要往内存中存储一次 }}printf(%d,b);return 0;
}
