第一题 [NOIP2006 普及组] 明明的随机数

题目描述

明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了 $N$ 个 $1$ 到 $1000$ 之间的随机整数 $(N\le 100)$，对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。

输入格式

输入有两行，第 $1$ 行为 $1$ 个正整数，表示所生成的随机数的个数 $N$。

第 $2$ 行有 $N$ 个用空格隔开的正整数，为所产生的随机数。

输出格式

输出也是两行，第 $1$ 行为 $1$ 个正整数 $M$，表示不相同的随机数的个数。

第 $2$ 行为 $M$ 个用空格隔开的正整数，为从小到大排好序的不相同的随机数。

样例 #1

样例输入 #1

10
20 40 32 67 40 20 89 300 400 15
1
2

样例输出 #1

8
15 20 32 40 67 89 300 400
1
2

解题思路

• 1）sort 进行排序。
• 2）bool 数组进行查重。

参考代码

#include
using namespace std;
int a[105];
bool p[1005];
int main()
{
    int n,tmp,cnt=0;
    cin>>n;
    for(int i=0;i<n;i++)
    {
    	cin>>tmp;
    	if(p[tmp]==1)continue;
    	p[tmp]=1;
    	a[cnt++]=tmp;
    }
    sort(a,a+cnt);
    cout<<cnt<<endl;
    for(int i=0;i<cnt;i++)cout<<a[i]<<" ";
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

第二题 最大子段和

题目描述

给出一个长度为 $n$ 的序列 $a$，选出其中连续且非空的一段使得这段和最大。

输入格式

第一行是一个整数，表示序列的长度 $n$。

第二行有 $n$ 个整数，第 $i$ 个整数表示序列的第 $i$ 个数字 $a_i$。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1

7
2 -4 3 -1 2 -4 3
1
2

样例输出 #1

4
1

提示

样例 1 解释

选取 $[3,5]$ 子段 { 3 , − 1 , 2 } \{3, -1, 2\} {3,−1,2}，其和为 $4$。

数据规模与约定

• 对于 $40\%$ 的数据，保证 $n\le 2\times 10^3$。
• 对于 $100\%$ 的数据，保证 $1\le n\le 2\times 10^5$，$-10^4\le a_i\le 10^4$。

解题思路

• 1）经典的动态规划问题。
• 2）通过简单的导可以得到 dp 方程dp[i]=max(dp[i-1]+a[i],a[i])
• 3）遍历 dp 方程，找到最大子段和。

参考代码

#include
using namespace std;
int dp[200005];
int main()
{
	int a[200005];
	int n;
	cin>>n; 
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	dp[0]=a[0];
	for(int i=1;i<n;i++)
	{
		dp[i]=max(a[i],dp[i-1]+a[i]);
	}
	int max=-9999999;
	for(int i=0;i<n;i++)
	{
		if(dp[i]>max)max=dp[i];
	}
	cout<<max;
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

第三题 [NOIP2009 普及组] 多项式输出

题目描述

一元 $n$ 次多项式可用如下的表达式表示：

$$f(x)=a_n{x}^n+a_{n-1}{x}^{n-1}+\cdots +a_{1}x+a_0,a_n\ne 0$$

其中，$a_i{x}^i$ 称为 $i$ 次项，$a_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. 多项式中，多项式的开头、结尾不含多余的空格。

输入格式

输入共有 $2$ 行

第一行 $1$ 个整数，$n$，表示一元多项式的次数。

第二行有 $n+1$ 个整数，其中第 $i$ 个整数表示第 $n-i+1$ 次项的系数，每两个整数之间用空格隔开。

输出格式

输出共 $1$ 行，按题目所述格式输出多项式。

样例 #1

样例输入 #1

5 
100 -1 1 -3 0 10
1
2

样例输出 #1

100x^5-x^4+x^3-3x^2+10
1

样例 #2

样例输入 #2

3 
-50 0 0 1
1
2

样例输出 #2

-50x^3+1
1

提示

对于100%数据，$0\le n\le 100$，$-100 \le $系数$ \le 100$

解题思路

• 1）模拟问题，题目要求怎么样就怎么样写。

参考代码

#include
using namespace std;
int main()
{
	int n;
	cin>>n;
	for(int i=n;i>=0;i--)
	{
		int a;
		cin>>a;
		if(a>0&&i!=n) cout<<"+";
		if(a<0) cout<<"-";
		if(abs(a)>1||a&&i==0) cout<<abs(a);
		if(a&&i>1) cout<<"x"<<"^"<<i;
		if(a&&i==1) cout<<"x"; 
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

第四题 一中校运会之百米跑

题目背景

在一大堆秀恩爱的 ** 之中，来不及秀恩爱的苏大学神踏着坚定（？）的步伐走向了 $100$ 米跑的起点。这时苏大学神发现，百米赛跑的参赛同学实在是太多了，连体育老师也忙不过来。这时体育老师发现了身为体育委员的苏大学神，便来找他帮忙。

可是苏大学神需要热身，不然跑到一半就会抽（筋）、于是他就找到了你。。。如果你帮助体育老师解决了问题，老师就会给你 $5$ 个积分。

题目描述

假设一共有 $N$（$2\le N\le 2\times 10^4$）个参赛选手。（尼玛全校学生都没这么多吧）

老师会告诉你这 $N$ 个选手的名字。

接着会告诉你 $M$（$1\le M\le 10^6$）句话，即告诉你学生 A 与学生 B 在同一个组里。

如果学生 A 与学生 B 在同一组里，学生 B 与学生 C 也在同一组里，就说明学生 A 与学生 C 在同一组。

然后老师会问你 $K$（$1\le K\le 10^6$）句话，即学生 X 和学生 Y 是否在同一组里。

若是则输出 Yes.，否则输出 No.。

输入格式

第一行输入 $N$ 和 $M$。

接下来 $N$ 行输入每一个同学的名字。

再往下 $M$ 行每行输入两个名字，且保证这两个名字都在上面的 $N$ 行中出现过，表示这两个参赛选手在同一个组里。

再来输入 $K$。

接下来输入 $K$ 个体育老师的询问。

输出格式

对于每一个体育老师的询问，输出 Yes. 或 No.。

样例 #1

样例输入 #1

10 6
Jack
Mike
ASDA
Michel
brabrabra
HeHe
HeHE
papapa
HeY
Obama
Jack Obama
HeHe HeHE
brabrabra HeHe
Obama ASDA
papapa Obama
Obama HeHE
3
Mike Obama
HeHE Jack
papapa brabrabra
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

样例输出 #1

No.
Yes.
Yes.
1
2
3

解题思路

• 1）字符串加并查集题目。
• 2）可以建立一个由字符串到字符串的映射代替数组father。

参考代码

#include
using namespace std;
int n,m,k;
string f[20001],mz[20001];
int fname(string name)
{
	for (int i=1;i<=n;i++){
		if (name==mz[i]) return i;
	}
}
string find(string name)
{
	if (f[fname(name)]==name) return name;
	return f[fname(name)]=find(f[fname(name)]);
} 
int main()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++)
    {
    	cin>>f[i];
    	mz[i]=f[i];
	} 
	for (int i=1;i<=m;i++){
		string a,b;
		cin>>a>>b;
		f[fname(find(a))]=find(b);
	}
	cin>>k;
	for (int i=1;i<=k;i++){
		string a,b;
		cin>>a>>b;
		if (find(a)==find(b)) cout<<"Yes."<<endl;
		else cout<<"No."<<endl;
	}
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37