swust oj 342变位词 348花生采摘413: Quick Sort430: 国名排序445: 选择问题
342变位词
题目描述如果两个单词的组成字母完全相同，只是字母的排列顺序不一样，则它们就是变位词，两个单词相同也被认为是变位词。如tea 与eat , nic 与cin, ddc与dcd, abc与abc 等。你的任务就是判断它们是否是变位词。
输入第一行一个N,表示下面有N行测试数据。每行测试数据包括两个单词，如tea eat ,它们之间用空格割开 输出
对于每个测试数据，如果它们是变位词，输出Yes,否则输出No. 样例输入复制
3 tea eat ddc cdd dee dde 样例输出复制
Yes Yes No
源代码及注释
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
while(n--)
{
char str1[1000]={' '}; //所有元素初始化为空字符 ' '。
char str2[1000]={' '};
cin>>str1>>str2;
sort(str1,str1+strlen(str1)); //用于计算字符串的长度。
sort(str2,str2+strlen(str2));
if(strcmp(str1,str2)==0) //用于比较两个字符串的大小。它逐个比较两个字符串对应位置的字符，按照字符的 ASCII 码值进行比较。如果两个字符串完全相同，返回 0；
{
printf("Yesn");
}
else
{
printf("Non");
}
}
}
348花生采摘
题目描述鲁宾逊先生有一只宠物猴，名叫多多。这天，他们两个正沿着乡间小路散步，突然发现路边的告示牌上贴着一张小小的纸条：“欢迎免费品尝我种的花生！——熊字”。 鲁宾逊先生和多多都很开心，因为花生正是他们的最爱。在告示牌背后，路边真的有一块花生田，花生植株整齐地排列成矩形网格（如图1）。
有经验的多多一眼就能看出，每棵花生植株下的花生有多少。为了训练多多的算术，鲁宾逊先生说：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此类推，不过你一定要在我限定的时间内回到路边。” 我们假定多多在每个单位时间内，可以做下列四件事情中的一件：
1) 从路边跳到最靠近路边（即第一行）的某棵花生植株；
2) 从一棵植株跳到前后左右与之相邻的另一棵植株；
3) 采摘一棵植株下的花生；
4) 从最靠近路边（即第一行）的某棵花生植株跳回路边。
现在给定一块花生田的大小和花生的分布，请问在限定时间内，多多最多可以采到多少个花生？注意可能只有部分植株下面长有花生，假设这些植株下的花生个数各不相同。
例如在图2所示的花生田里，只有位于(2, 5), (3, 7), (4, 2), (5, 4)的植株下长有花生，个数分别为13, 7, 15, 9。沿着图示的路线，多多在21个单位时间内，最多可以采到37个花生。
输入的第一行包括三个整数，M, N和K，用空格隔开；表示花生田的大小为M * N（1 <= M, N <= 20），多多采花生的限定时间为K（0 <= K <= 1000）个单位时间。接下来的M行，每行包括N个非负整数，也用空格隔开；第i + 1行的第j个整数Pij（0 <= Pij <= 500）表示花生田里植株(i, j)下花生的数目，0表示该植株下没有花生。
输出输出包括一行，这一行只包含一个整数，即在限定时间内，多多最多可以采到花生的个数。
样例输入复制6 7 21 0 0 0 0 0 0 0 0 0 0 0 13 0 0 0 0 0 0 0 0 7 0 15 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 样例输出复制
37
源代码及注释
#include <bits/stdc++.h>
using namespace std;
//typedef long long ll;
int m,n,k,ans=0;
int a[25][25];
void dfs(int x,int y,int time)
{
int max=-(1<<30),nx,ny; // 初始化最大花生点为极小值，以及对应的坐标,将数字 1 左移 30 位
//max最大的花生点
//nx最大花生点的x坐标
//ny最大花生点的y坐标
for(int i=1;i<=m;i++) //i=1
for(int j=1;j<=n;j++)
if(a[i][j]>max)
{
max=a[i][j];
nx=i;
ny=j;
//更新
}
if(y==0) y=ny; // 如果起始纵坐标为 0，则更新为找到的最大花生点纵坐标（边界处理）
int nt=abs(nx-x)+abs(ny-y)+nx+1;// 表示从当前位置到达这个最大花生点并进行相关操作总共需要的时间步数。nx + 1 这里可能是考虑到到达该点后还需要额外一步操作（比如采摘等）。
// 如果采这棵花生花费的时间超过剩余时间或该位置花生数为 0，则返回
if(time<nt || a[nx][ny]==0) return;
//边界返回条件
else
{
ans+=a[nx][ny];
//可以选择，ans更新
a[nx][ny]=0;//这行代码是将刚刚采摘过的最大花生点位置（坐标为 nx 和 ny ）处的花生数量设置为 0 ，表示已经采摘过了，后续不再考虑这个位置的花生。
dfs(nx,ny,time-abs(nx-x)-abs(ny-y)-1);
}
}
int main()
{
cin>>m>>n>>k; // 输入行数、列数、剩余时间
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j];
dfs(0,0,k); // 从起始位置开始进行深度优先搜索
cout<<ans<<endl;
return 0;
}
//这个题目描述了鲁宾逊先生和他的宠物猴多多在花生田里采摘花生的情景。他们要在限定的时间内，按照一定规则采摘花生。具体规则包括：
//多多每次可以从路边跳到最靠近路边的某棵花生植株。
//多多可以从一棵植株跳到前后左右与之相邻的另一棵植株。
//多多可以采摘一棵植株下的花生。
//多多可以从最靠近路边的某棵花生植株跳回路边。
//现在给定了花生田的大小和花生的分布，以及多多采花生的限定时间，要求计算多多最多可以采到多少个花生。
//输入描述了花生田的大小为 M * N，限定时间为 K 个单位时间。接下来的 M 行每行包括 N 个非负整数，表示花生田里每个植株下的花生数目。
//输出则是一个整数，表示在限定时间内，多多最多可以采到的花生个数。
//举例来说，如果花生田的情况是一个 6 * 7 的网格，其中有几个植株下长有花生，其个数分别为 (2, 5), (3, 7), (4, 2), (5, 4)，那么在限定的 21 个单位时间内，多多最多可以采到的花生数目是 37。
413: Quick Sort
题目描述Quicksort is a well-known sorting algorithm developed by C. A. R.
Hoare that, on average, makes Θ(n log n) comparisons to sort n items. However, in the worst case, it makes Θ(n2) comparisons. Typically, quicksort is significantly faster in practice than other Θ(n log n) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data it is possible to make design choices which minimize the possibility of requiring quadratic time.
Quicksort sorts by employing a divide and conquer strategy to divide a list into two sub-lists.
The steps are:
1. Pick an element, called a pivot, from the list.
2. Reorder the list so that all elements which are less than the pivot come before the pivot and so that all elements greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
3. Recursively sort the sub-list of lesser elements and the sub-list of greater elements. The base case of the recursion are lists of size zero or one, which are always sorted. The algorithm always terminates because it puts at least one element in its final place on each iteration (the loop invariant).
Quicksort in action on a list of random numbers. The horizontal lines are pivot values. Write a program to sort ascending int number by QuickSort ,n less than 50000.
输入two lows, the first low is numbers , less and equal than 50000. the second low is a set integer numbers
输出a set integer numbers of sort ascending
样例输入复制10 4 2 1 5 7 6 9 8 0 3 样例输出复制
0 1 2 3 4 5 6 7 8 9
源代码及注释
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
int a[50005];
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
sort(a,a+n);
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
return 0;
}
430: 国名排序
题目描述问题描述： 小李在准备明天的广交会，明天有来自世界各国的客房跟他们谈生意，小李要尽快的整理出名单给经理，你能帮他把客户来自的国家按英文字典次序排好吗？ 例如小李手上有来自加拿大，美国，中国的名单，排好的名单应是美国，加拿大，中国
输入第一行为一个n（n<=100）表示n个国家，第２行到第n＋１行分别为n个国家的名字． 输出
输出n个国家按字典顺序的排列． 样例输入复制
3 China Canada America 样例输出复制
America Canada China
源代码及注释
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
string a[100];
for (int i = 0; i < n; i++)
cin >> a[i];
sort(a, a + n);//默认从小到大
for (int i = 0; i < n; i++)
cout << a[i] << endl;
return 0;
}
445: 选择问题
题目描述上期的基础训练中我们提到了快速排序，它在最坏的情况下其时间复杂性是O（n^2）。而在分治算法的分支里还有一个是选择算法。它是一种能够以O(n)时间选取数组的中值元素或任意的第K小元素的算法。基本思路是：在分治算法的递归调用的每一个划分步骤里，放弃一个固定部分的元素，对其余元素进行递归。于是，问题的规模便以几何级数递减如果第一次递归放弃处理1/3的元素，那么第二次递归时，只要处理原来的2/3的元素，在第三次递归时，只要处理原来的4/9的元素，如此等等。请根据此算法，解决以下问题。按递增顺序，以比较快的速度查找出N(N<=10000)个元素的第K小的元素。
输入整数N(N<=10000)和K，接下来输入N个数据。 输出
输出只有一个数据，即输出N个数据中第K小的元素。 样例输入复制
10 6 10 9 3 8 4 5 2 1 7 6 样例输出复制
6
源代码及注释
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,k,a[10001];
cin>>n>>k;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
sort(a,a+n);
cout<<a[k-1]<<endl;
return 0;
}
相关知识
swust oj 342变位词 348花生采摘413: Quick Sort430: 国名排序445: 选择问题
SWUST oj 348: 花生采摘
swust oj 384花生采摘
SWUSTOJ #348 花生采摘
花生问题——百练OJ：2950:摘花生与1928:The Peanuts
[NOIP普及组 2004] 花生采摘 {快速排序}
P1086 花生采摘(C++)
信息学奥赛一本通题目解析：1927：【04NOIP普及组】花生采摘（模拟）
(SWUST OJ)《算法分析设计与实践》题库
P1086 [NOIP2004 普及组] 花生采摘（模拟）
网址: swust oj 342变位词 348花生采摘413: Quick Sort430: 国名排序445: 选择问题 https://m.mcbbbk.com/newsview558128.html
| 上一篇: 极品珍藏！10部让人大开眼界的宠 |
下一篇: 百练2950：摘花生 |
