第一题 [NOIP2006 普及组] 明明的随机数
题目描述
明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了 N 个 1 到 1000 之间的随机整数 ( N ≤ 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
8 15 20 32 40 67 89 300 400
解题思路
1）sort 进行排序。
2）bool 数组进行查重。
参考代码
#include<bits/stdc++.h> 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]<<" "; }
第二题 最大子段和
题目描述
给出一个长度为 n 的序列 a，选出其中连续且非空的一段使得这段和最大。
输入格式
第一行是一个整数，表示序列的长度 n。
第二行有 n 个整数，第 i个整数表示序列的第 i 个数字 a i 。
输出格式
输出一行一个整数表示答案。
样例 #1
样例输入 #1
7 2 -4 3 -1 2 -4 3
样例输出 #1
4
提示
样例 1 解释
选取 [ 3 , 5 ]子段 { 3 , − 1 , 2 } ，其和为 4。
数据规模与约定
对于 40 %的数据，保证 n ≤ 2 × 
。
对于 100 % 的数据，保证 1 ≤ n ≤ 2 ×
，− 
≤ a i ≤ 
。
解题思路
1）经典的动态规划问题。
2）通过简单的导可以得到 dp 方程dp[i]=max(dp[i-1]+a[i],a[i])
3）遍历 dp 方程，找到最大子段和。
参考代码
#include<bits/stdc++.h> 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; }
第三题 [NOIP2009 普及组] 多项式输出
题目描述
一元 n次多项式可用如下的表达式表示：
其中，
称为 i次项，a i 称为 i 次项的系数。给出一个一元多项式各项的次数和系数，请按照如下规定的格式要求输出该多项式：
多项式中自变量为 x，从左到右按照次数递减顺序给出多项式。
多项式中只包含系数不为 0 的项。
如果多项式 n 次项系数为正，则多项式开头不出 + 号，如果多项式 n次项系数为负，则多项式以 - 号开头。
对于不是最高次的项，以 + 号或者 - 号连接此项与前一项，分别表示此项系数为正或者系数为负。紧跟一个正整数，表示此项系数的绝对值（如果一个高于 0 次的项，其系数的绝对值为 1 ，则无需输出 1 ）。如果 x的指数大于 1，则接下来紧跟的指数部分的形式为
，其中 b 为 x 的指数；如果 x 的指数为 1，则接下来紧跟的指数部分形式为 x；如果 x 的指数为 0，则仅需输出系数即可。
多项式中，多项式的开头、结尾不含多余的空格。
输入格式
输入共有 2 行
第一行 1 个整数，n，表示一元多项式的次数。
第二行有 n + 1个整数，其中第 i 个整数表示第 n − i + 1 次项的系数，每两个整数之间用空格隔开。
输出格式
输出共 1行，按题目所述格式输出多项式。
样例 #1
样例输入 #1
5 100 -1 1 -3 0 10
样例输出 #1
100x^5-x^4+x^3-3x^2+10
样例 #2
样例输入 #2
3 -50 0 0 1
样例输出 #2
-50x^3+1
提示
对于100%数据，0 ≤ n ≤ 100，$-100 \le 系数 \le 100$
解题思路
1）模拟问题，题目要求怎么样就怎么样写。
参考代码
#include<bits/stdc++.h> 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; }
第四题 一中校运会之百米跑
题目背景
在一大堆秀恩爱的 ** 之中，来不及秀恩爱的苏大学神踏着坚定（？）的步伐走向了 100 米跑的起点。这时苏大学神发现，百米赛跑的参赛同学实在是太多了，连体育老师也忙不过来。这时体育老师发现了身为体育委员的苏大学神，便来找他帮忙。
可是苏大学神需要热身，不然跑到一半就会抽（筋）、于是他就找到了你。。。如果你帮助体育老师解决了问题，老师就会给你 5个积分。
题目描述
假设一共有 N（2 ≤ N ≤ 2 × 
）个参赛选手。（尼玛全校学生都没这么多吧）
老师会告诉你这 N 个选手的名字。
接着会告诉你 M（1 ≤ M ≤ 
）句话，即告诉你学生 A 与学生 B 在同一个组里。
如果学生 A 与学生 B 在同一组里，学生 B 与学生 C 也在同一组里，就说明学生 A 与学生 C 在同一组。
然后老师会问你 K1 ≤ K ≤ 
）句话，即学生 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
No. Yes. Yes.
解题思路
1）字符串加并查集题目。
2）可以建立一个由字符串到字符串的映射代替数组father。
参考代码
#include<bits/stdc++.h> 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; }
