普及组第二题

绝地灬酷狼 2024-04-17 21:53 36阅读 0赞

> noip2017 图书管理员

链接：[https://www.luogu.org/problem/P3955][https_www.luogu.org_problem_P3955]

### 题目描述 ###

图书馆中每本书都有一个图书编码，可以用于快速检索图书，这个图书编码是一个 正整数。 每位借书的读者手中有一个需求码，这个需求码也是一个正整数。如果一本书的图 书编码恰好以读者的需求码结尾，那么这本书就是这位读者所需要的。 小 D 刚刚当上图书馆的管理员，她知道图书馆里所有书的图书编码，她请你帮她写 一个程序，对于每一位读者，求出他所需要的书中图书编码最小的那本书，如果没有他 需要的书，请输出-1−1。

### 输入格式 ###

第一行，包含两个正整数 n , qn,q，以一个空格分开，分别代表图书馆里 书的数量和读者的数量。

接下来的 nn 行，每行包含一个正整数，代表图书馆里某本书的图书编码。

接下来的 qq 行，每行包含两个正整数，以一个空格分开，第一个正整数代表图书馆 里读者的需求码的长度，第二个正整数代表读者的需求码。

### 输出格式 ###

qq 行，每行包含一个整数，如果存在第 ii 个读者所需要的书，则在第 ii 行输出第 ii 个读者所需要的书中图书编码最小的那本书的图书编码，否则输出-1−1。

### 输入输出样例 ###

**输入 \#1**复制

5 5 
    2123 
    1123 
    23 
    24 
    24 
    2 23 
    3 123 
    3 124 
    2 12 
    2 12

**输出 \#1**复制

23 
    1123 
    -1 
    -1 
    -1

### 说明/提示 ###

【数据规模与约定】

对于 20\\%20%的数据，1 ≤ n ≤ 21≤n≤2。

另有 20\\%20%的数据，q = 1q=1。

另有 20\\%20%的数据，所有读者的需求码的长度均为 11。

另有 20\\%20%的数据，所有的图书编码按从小到大的顺序给出。

对于 100\\%100%的数据，1 ≤ n ≤ 1,000,1 ≤ q ≤ 1,0001≤n≤1,000,1≤q≤1,000，所有的图书编码和需求码均 不超过 10,000,00010,000,000。

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int a[1005];
    int m[7]={10,100,1000,10000,100000,1000000,10000000};
    int main()
    {
    //	freopen("librarian.txt","r",stdin);
    //	freopen("librarian2.txt","w",stdout);
    	int n,q,a1,b1;
    	scanf("%d%d",&n,&q);
    	for(int i=1; i<=n; ++i)
    	{
    		scanf("%d",&a[i]);
    	}
    	sort(a+1,a+1+n);
    	for(int i=1; i <=q; ++i)
    	{
    		int c=0,k=0,flag=0;
    		scanf("%d%d",&a1,&b1);
    		for(int j = 1; j <= n; ++j)
    		{
    			c = a[j]%m[a1-1];//得到a[j]的后a1位数 。比如2123%100=23 
    			if(c==b1) 
    			{
    				k=a[j];
    				flag = 1;
    				break;
    			}
    		}
    		if(flag)
    			printf("%d\n",k);
    		else
    			printf("-1\n");
    	}
    	return 0;
    }

#include<iostream>
    #include<algorithm>
    using namespace std;
    int a[1005];//图书编码 
    int d[10]={10,100,1000,10000,100000,1000000,10000000};//用来分离数位 
    int main()
    {
    //	freopen("librarian.in","r",stdin);
    //	freopen("librarian.out","w",stdout);
    	int n,q;
    	cin >> n >> q;
    	for(int i = 1; i <= n; ++i)//输入图书编码 
    	{
    		cin >> a[i];
    	}
    	sort(a+1,a+1+n); //对图书编码从小到大排序
    	for(int i = 1; i <= q; ++i)
    	{
    		int b,c;//b需求码的长度，c读者的需求码 
    		cin >> b >> c;
    		bool p = 0; 
    		for(int j = 1; j <= n; ++j)//判断每一个图书编码是否符合条件
    		{
    			int k = a[j]%d[b-1];//分离出图书编码的后面b位  1123%100 = 23
    			if(k == c)
    			{
    				cout << a[j] << endl;//只用输出第一个满足条件的图书编码（最小图书编码） 
    				p = 1;//已经有输出了 
    				break;
    			}	
    		} 
    		if(p == 0) cout << "-1" << endl; 
    	} 
    	return 0;
    }

> noip2016 回文日期

链接：[https://www.luogu.org/problem/P2010][https_www.luogu.org_problem_P2010]

### 题目描述 ###

在日常生活中，通过年、月、日这三个要素可以表示出一个唯一确定的日期。

牛牛习惯用88位数字表示一个日期，其中，前44位代表年份，接下来22位代表月 份，最后22位代表日期。显然：一个日期只有一种表示方法，而两个不同的日期的表 示方法不会相同。

牛牛认为，一个日期是回文的，当且仅当表示这个日期的8位数字是回文的。现 在，牛牛想知道：在他指定的两个日期之间包含这两个日期本身），有多少个真实存 在的日期是回文的。

一个88位数字是回文的，当且仅当对于所有的i ( 1 \\le i \\le 8)i(1≤i≤8)从左向右数的第i个 数字和第9-i9−i个数字（即从右向左数的第ii个数字）是相同的。

例如：

•对于2016年11月19日，用88位数字2016111920161119表示，它不是回文的。

•对于2010年1月2日，用88位数字2010010220100102表示，它是回文的。

•对于2010年10月2日，用88位数字2010100220101002表示，它不是回文的。

每一年中都有1212个月份：

其中，1,3,5,7,8,10,121,3,5,7,8,10,12月每个月有3131天；4,6,9,114,6,9,11月每个月有3030天；而对于22月，闰年时有2929天，平年时有2828天。

一个年份是闰年当且仅当它满足下列两种情况其中的一种：

1.这个年份是44的整数倍，但不是100100的整数倍；

2.这个年份是400400的整数倍。

例如：

•以下几个年份都是闰年：2000,2012,20162000,2012,2016。

•以下几个年份是平年：1900,2011,20141900,2011,2014。

### 输入格式 ###

两行，每行包括一个88位数字。

第一行表示牛牛指定的起始日期。

第二行表示牛牛指定的终止日期。

保证date\\\_idate\_i和都是真实存在的日期，且年份部分一定为44位数字，且首位数字不为00。

保证date 1date1 —定不晚于date 2date2。

### 输出格式 ###

一个整数，表示在date1date1和date2date2之间，有多少个日期是回文的。

### 输入输出样例 ###

**输入 \#1**复制

20110101
    20111231

**输出 \#1**复制

**输入 \#2**复制

20000101
    20101231

**输出 \#2**复制

### 说明/提示 ###

【样例说明】

对于样例1，符合条件的日期是2011110220111102。

对于样例2，符合条件的日期是2001100220011002和2010010220100102。

【子任务】

对于60\\%60%的数据，满足date1 = date2date1=date2。

> 解析：本题可以构造回文数。已知月份和天构成的4位数字，只需要构造前面的4位数字即可。
> 
> 所以现在需要枚举月份和天数构造的数字，由于2月29天0229的唯一回文数是92200229，而9220是瑞年，所以满足条件。因此可以直接把2月算成29天。
> 
> 构造前面的4位数的代码，用到了拆分数字。（将构造的回文数全部放在b\[\]中，然后判断date1-date2范围内有多少个数在b\[\]中即可）
> 
> p = i\*100+j;  
> b\[++q\] = (p%10\*1000+p/10%10\*100+p/100%10\*10+p/1000)\*10000+p;
> 
> 比如p=2358:
> 
> 拆分时分别用取模运算把8 5 3 2四个数拆分出来，然后乘以相应的位数即可。
> 
> 2358%10=8 2358/10 = 235
> 
> 235%10 = 5 235/10 = 23
> 
> 23%10 = 3 23/10=2
> 
> 2%10=2
> 
> 8\*1000+5\*100+3\*10+2=8532
> 
> 8532\*10000+2358=85322358

#include<iostream>
    #include<cstdio>
    using namespace std;
    int a1[15]={0,31,29,31,30,31,30,31,31,30,31,30,31};
    int b[100000000];
    int main()
    {
    	//freopen("a.txt","r",stdin);
    	int date1,date2;
    	cin >> date1>>date2;
    	int q = 0,sum=0,p = 0;
     	for(int i = 1; i <= 12; ++i)
     	{
     		for(int j = 1; j <= a1[i]; ++j)
     		{
     			p = i*100+j;
    			b[++q] = (p%10*1000+p/10%10*100+p/100%10*10+p/1000)*10000+p;
    		//	cout << i << " " << j << ":" << b[q] << endl; 
     			if(b[q]>=date1 && b[q] <= date2)
     			{
     				sum ++;
     			//	cout << b[q] << endl;
    			 }	
    		}
    	}
    	cout << sum << endl;
    	return 0;
    }

> noip 2015 扫雷游戏

### 【题目描述】 ###

扫雷游戏是一款十分经典的单机小游戏。在n行m列的雷区中有一些格子含有地雷（称之为地雷格），其他格子不含地雷（称之为非地雷格）。玩家翻开一个非地雷格时，该格将会出现一个数字——提示周围格子中有多少个是地雷格。游戏的目标是在不翻出任何地雷格的条件下，找出所有的非地雷格。

现在给出n行m列的雷区中的地雷分布，要求计算出每个非地雷格周围的地雷格数。

注：一个格子的周围格子包括其上、下、左、右、左上、右上、左下、右下八个方向上与之直接相邻的格子。

### 【输入】 ###

第一行是用一个空格隔开的两个整数n和m，分别表示雷区的行数和列数。

接下来n行，每行m个字符，描述了雷区中的地雷分布情况。字符’\*’表示相应格子是地雷格，字符’?’表示相应格子是非地雷格。相邻字符之间无分隔符。

### 【输出】 ###

包含n行，每行m个字符，描述整个雷区。用’\*’表示地雷格，用周围的地雷个数表示非地雷格。相邻字符之间无分隔符。

### 【输入样例】 ###

3 3
    *??
    ???
    ?*?

### 【输出样例】 ###

*10
    221
    1*1

### 【提示】 ###

样例测试点\#2：

输入：

2 3

?\*?

\*??

输出：

2\*1

\*21

对于 100%的数据， 1≤n≤100， 1≤m≤100。

#include<iostream>
    #include<cstring>
    #define MAXN 105
    using namespace std;
    int n,m;
    char a[105][105];
    //sum[105][105];
    int fx[10]={1,1,0,-1,-1,-1,0,1};//向上下左右斜对角线八个方向搜索 
    int fy[10]={0,1,1,1,0,-1,-1,-1};
    /*
    void dfs(int x, int y)
    {
    	for(int i = 0; i < 8; ++i)
    	{
    		int xx = x + fx[i];
    		int yy = y + fy[i];
    		if(xx >= 1 && xx <= n && yy >= 1 && yy <= m )
    		{
    			if(a[xx][yy] == '*') sum[xx][yy]++;
    		}
    	}
    }
    */
    int main()
    {
    	cin >> n >> m;
    	//memset(sum,0,sizeof(sum));
    	for(int i = 1; i <= n; ++i)
    	{
    		for(int j = 1; j <= m; ++j)
    		{
    			cin >> a[i][j];
    		}
    	}
    	//for(int j = 1; j <= m; ++j) a[0][j] = a[m+1][j] = '?';
    //	for(int i = 1; i <= n; ++i) a[i][0] = a[i][n+1] = '?';
    	//dfs(1,1);
    	for(int i = 1; i <= n; ++i)
    	{
    		for(int j = 1; j <= m; ++j)
    		{
    			int sum = 0;
    			if(a[i][j] == '*')//*就原样输出 
    				cout << a[i][j];
    			else
    			{
    				for(int k = 0; k < 8; ++k)//搜索八个方向 
    				{
    					if(a[i+fx[k]][j+fy[k]] == '*')//对八个方向的*号计数 
    						sum++;
    				}
    				cout << sum;
    			}	
    		}
    		cout << endl;
    	}
    	
    	return 0;
    }

> noip2014 比例简化

### 【题目描述】 ###

在社交媒体上，经常会看到针对某一个观点同意与否的民意调查以及结果。例如，对某一观点表示支持的有 1498 人，反对的有 902 人，那么赞同与反对的比例可以简单的记为1498:902。

不过，如果把调查结果就以这种方式呈现出来，大多数人肯定不会满意。因为这个比例的数值太大，难以一眼看出它们的关系。对于上面这个例子，如果把比例记为 5:3，虽然与真实结果有一定的误差，但依然能够较为准确地反映调查结果，同时也显得比较直观。

现给出支持人数 A，反对人数 B，以及一个上限 L，请你将 A 比 B 化简为 A’比 B’，要求在 A’和 B’均不大于 L 且 A’和 B’互质（两个整数的最大公约数是 1）的前提下，A’/B’ ≥ A/B且 A’/B’ - A/B 的值尽可能小。

### 【输入】 ###

输入共一行，包含三个整数 A，B，L，每两个整数之间用一个空格隔开，分别表示支持人数、反对人数以及上限。

### 【输出】 ###

输出共一行，包含两个整数 A’，B’，中间用一个空格隔开，表示化简后的比例。

### 【输入样例】 ###

1498 902 10

### 【输出样例】 ###

5 3

### 【提示】 ###

【数据说明】

对于 100%的数据，1 ≤ A ≤ 1,000,000，1 ≤ B ≤ 1,000,000，1 ≤ L ≤ 100， A/B ≤ L。

> 解析：本题主要是精度的控制和min初始化为最大值。
> 
> 对于A'、B'的结果只需要一一枚举，找到符合判断要求的结果即可。

#include<iostream>
    using namespace std;
    int gcd(int x,int y)//最大公约数 
    {
    	if(x%y == 0) return y;
    	else return gcd(y,x%y);
    }
    int main()
    {
     	int A,B,A1,B1,A2,B2,L;
    	double min,c;
    	cin >> A >> B >> L;
    	min = 1.0*L;//min初始化为最大的数 
    	for(int A1 = 1; A1 <= L; ++ A1)
    	{
    		for(int B1 = 1; B1 <= L; ++B1)
    		{
    			if(gcd(A1,B1) == 1 && A1*1.0/B1 >= A*1.0/B) 
    			{
    				 if((A1*1.0/B1 - A*1.0/B) <= min)//更新最小值 
    				 {
    				 	min = A1*1.0/B1 - A*1.0/B;
    				 	A2 = A1;//记录更新后的结果 
    				 	B2 = B1;
    				 }
    			}
    		}
    	}
    	cout << A2 << " " << B2 << endl; 
    	return 0;
    }

> 2013:表达式求值

<table> 
 <tbody> 
  <tr> 
   <td style="text-align:left;"> <h3>1962：【13NOIP普及组】表达式求值</h3> <br> 时间限制: 1000 ms &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; 内存限制: 131072 KB<br> 提交数: 423 &nbsp;&nbsp;&nbsp; 通过数: 195&nbsp; <h3>【题目描述】</h3> <p>给定一个只包含加法和乘法的算术表达式，请你编程计算表达式的值。</p> <h3>【输入】</h3> <p>输入仅有一行，为需要你计算的表达式，表达式中只包含数字、加法运算符“+”和乘法运算符“*”，且没有括号，所有参与运算的数字均为 0 到 231-1 之间的整数。输入数据保证这一行只有 0~ 9、+、*这 12 种字符。</p> <p>&nbsp;</p> <h3>【输出】</h3> <p>输出只有一行，包含一个整数，表示这个表达式的值。注意：当答案长度多于 4 位时，</p> <p>请只输出最后 4 位，前导 0 不输出。</p> <p>&nbsp;</p> <h3>【输入样例】</h3> <pre><code>1+1*3+4</code></pre> <h3>【输出样例】</h3> <pre><code>8</code></pre> <h3>【提示】</h3> <p>【输入输出样例 2】</p> <p>输入：</p> <p>1+1234567890*1</p> <p>输出:</p> <p>7891</p> <p>【输入输出样例 3】</p> <p>输入：</p> <p>1+1000000003*1</p> <p>输出:</p> <p>4</p> <p>【输入输出样例说明】</p> <p>样例 1 计算的结果为 8，直接输出 8。</p> <p>样例 2 计算的结果为 1234567891，输出后 4 位，即 7891。</p> <p>样例 3 计算的结果为 1000000004，输出后 4 位，即 4。</p> <p>【数据范围】</p> <p>对于 30%的数据，0≤表达式中加法运算符和乘法运算符的总数≤100；</p> <p>对于 80%的数据，0≤表达式中加法运算符和乘法运算符的总数≤1000；</p> <p>对于 100%的数据，0≤表达式中加法运算符和乘法运算符的总数≤100000。</p> <p>&nbsp;</p> </td> 
  </tr> 
 </tbody> 
</table>

#include<iostream>
    #include<string>
    using namespace std;
    long long t1=0,t2=1,f=0;//t1+,t2*
    bool p = true,p2=true;
    string s;
    //先运算乘法，再运算加法，t1是最终累加的结果，t2是每次乘法运算的结果 
    int main()
    {
    	cin >> s;
    	int len = s.length();
    	for(int i = 0; i < len; ++i)//枚举每一个字符 
    	{
    		switch(s[i])
    		{
    			case '+':
    			{
    				if(p == true)//如果不涉及乘法项，就直接与数字求和 
    				{
    					t1+=f;
    					t1 = t1%10000;
    				}
    				else
    				{
    					t1 += f*t2;//涉及乘法项，则先运算乘法，然后再1求和 
    					t2 = t2%10000;
    					p == true;
    					t2 = 1;//乘法运算重新初始化 
    				}
    				f = 0;//数字重新初始化 
    				break;
    			}
    			case '*':
    			{
    				t2*=f;//乘法直接与数字相乘即可 
    				t2=t2%10000;
    				p = false;//涉及乘法运算，则选用第二种加法运算 
    				f = 0;//数字重新初始化 
    				break;
    			}
    			default:
    			{
    				if(s[i] >= '0' && s[i] <= '9')//将数字字符转成数字 
    					f = (f*10+s[i]-'0')%10000;//f表示当前的数字 
    				break;
    			}
    		}
    	}
    	if(p == true)//判断最后一个数的情况，如果只有加法运算，直接相加即可 
    	{
    		t1 = t1+f;
    		t1 = t1%10000;
    	}
    	else//如果有乘法运算，则需要先算乘法 
    	{
    		t1 = t1 + t2*f;
    		t1 = t1%10000;
    	}
    	cout << t1 << endl;
    	return 0;
    }

[https_www.luogu.org_problem_P3955]: https://www.luogu.org/problem/P3955
[https_www.luogu.org_problem_P2010]: https://www.luogu.org/problem/P2010