1. 编程号首页

洛谷unaccepted_ig对grf的详细比赛数据

编程小号 • • 未分类

洛谷unaccepted_ig对grf的详细比赛数据今天笔者感觉有点手生了，找了个洛谷入门赛共10道题练练手，题目比较简单，也有两个题目比较经典，望读者不喜勿喷

今天笔者感觉有点手生了，找了个洛谷入门赛共10道题练练手，题目比较简单，也有两个题目比较经典，望读者不喜勿喷。
在这里插入图片描述

【深基附B例】数列求和

题目来源

https://www.luogu.com.cn/problem/P5745

题目描述

给定 n 个正整数组成的数列 a1,a2,⋯ ,an和一个整数 M。要求从这个数列中找到一个子区间 [i,j]，也就是在这个数列中连续的数字 ai,ai+1,⋯ ,aj−1,aj使得这个子区间的和在不超过 M的情况下最大。输出 i、j 和区间和。如果有多个区间符合要求，请输出 i 最小的那一个。对于所有测试数据，ai≤105, M≤109。

输入格式

输入第一行两个数，代表n和m。 第二行共有n个数，第i个数代表a[i]。

输出格式

输出符合题意的区间的左端点、右端点和累加和，中间用空格隔开。

输入输出样例

输入 #1

5 10
2 3 4 5 6

输出 #1

1 3 9

说明/提示

子任务 1（10分）：n≤200 ；

子任务 2（20分）：n≤3000 ；

子任务 3（30分）：n≤105；

子任务 4（40分）：n≤4×106 。

解题思路

由于n特别大，如果采用最直观的方法寻找最佳的i，最佳的j，一共两层for循环，再加上求个sum(i,j)，时间复杂度为O(n3)，显然会超时，这里想办法将时间复杂度降为O(n)，通过一次遍历求出best。

维护一个队列，让数组中的元素依次入队，并记录这个队列的元素和，若大于m,则让对首出列，更新答案，再让后面的数字继续入队，并更新答案，不断的这么操作，直到所有数字都入过队了为止。

AC代码
#include <iostream>
#include<stdio.h>
#include<stdlib.h>
#include<queue>
#include<bits/stdc++.h>
using namespace std;
//维护一个队列，让数组中的数依次入队，
//并记录其的元素和，若大于m,则让对首出列，更新答案，
//再让后面的数字继续入队，并更新答案，不断的这么操作，直到所有数字都入过队了为止。
int a[4000001];
//定义一个队列
queue<int>bestx;
int main()
{ 
   
	int n;
	long long m;
	long long best = 0;
	long long temp = 0;
	cin>>n>>m;
	int start,endd,besti,bestj;
	//start，endd为当前维护队列的首尾元素在数组中的下标位置
	//besti，bestj为当前最优值所对应的数组的起，止元素下标
	
	for(int i = 1;i<=n;i++)
		cin>>a[i];
		
	start = endd = 1;
	for(int i = 1;i<=n;i++){ 
   
		//对每一个a[i]都入队 
		endd = i;
		bestx.push(a[i]);
		temp += a[i];

		while(temp > m){ 
   
			bestx.pop();//队首元素弹出，此时队首元素为a[start]
			temp = temp - a[start];
			start++;//队列中的第一个下标为start
		}
		
		//判断更新最优值
		if(best < temp){ 
   
			besti = start;
			bestj = endd;
			best = temp;
		}

	}//for

	cout<<besti<<" "<<bestj<<" "<<best;

    return 0;
}

【深基2.例5】苹果采购

题目来源

https://www.luogu.com.cn/problem/P5703

题目描述

现在需要采购一些苹果，每名同学都可以分到固定数量的苹果，并且已经知道了同学的数量，请问需要采购多少个苹果？

输入格式

输入两个不超过 109 正整数，分别表示每人分到的数量和同学的人数。

输出格式

一个整数，表示答案。保证输入和答案都在int范围内的非负整数。
输入输出样例
输入 #1

5 3

输出 #1

15

解题思路

没有什么解题思路，题目都说保证输入和答案都在int可表示的范围内了，直接cout<<x*y;

AC代码
#include <iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
int main()
{ 
   
	int x,y;
	cin>>x>>y;
	cout<<x*y;
    return 0;
}

【深基2.习6】Apples Prologue

题目来源

https://www.luogu.com.cn/problem/P5709

题目描述

八尾勇喜欢吃苹果。她现在有 m(m≤100) 个苹果，吃完一个苹果需要花费 t(t≤100)分钟，吃完一个后立刻开始吃下一个。现在时间过去了 s(s≤10000) 分钟，请问她还有几个完整的苹果？

输入格式

输入三个非负整数表示 m 、t 和 s。

输出格式

输出一个整数表示答案。

输入输出样例

输入 #1

50 10 200

输出 #1

30

解题思路

这个题看起来是不是超级简单，但是不可能会这么容易过的，要注意跳坑。笔者就掉进去了一次，而且这题目在特定情况下也有毛病。

  1. 当 t != 0的时候，当s/t整除(即s%t == 0)时，输出m-s/t;当s/t不整除(即s%t != 0)时，输出m-s/t-1.
  2. 你以为上面是对的吗？不对，如果m-s/t 或者 m-s/t-1 小于0怎么办？显然剩余的完整苹果数一定是一个非负整数，当此类情况出现时，要输出0.
  3. 当t == 0时，这就是争议的地方，意思是八尾勇一瞬间可以吃完一个苹果，所以按照常理，那么剩余的完整苹果数应该为0呀！笔者这么做只能得90分，看了题解讨论之后发现这种情况输出m才可以AC通过，这就是笔者认为不合理得地方。
AC代码
#include <iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;

int main()
{ 
   
	int m,t,s;
	cin>>m>>t>>s;
	//如果吃一个苹果为0分钟
	if(t == 0){ 
   
		cout<<m;//题目有毛病，特判
		return 0;
	}
	int p;
	p = s/t;
	if(s%t != 0)//特判
		p++;
	m = m - p;
	//如果苹果不够吃
	if(m <= 0)
		cout<<0;//则剩余完整的苹果数为0
	else
		cout<<m;
    return 0;
}

【深基3.例8】三位数排序

题目来源

https://www.luogu.com.cn/problem/P5715

题目描述

给出三个整数 a,b,c(0≤a,b,c≤100)，要求把这三位整数从小到大排序。

输入格式

无

输出格式

无

输入输出样例

输入 #1

1 14 5

输出 #1

1 5 14

输入 #2

2 2 2

输出 #2

2 2 2

解题思路

直接冒泡排序了，反正3个数时间复杂度也不会高，应该能AC。

AC代码
#include <iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;

//给出三个整数 a,b,c(0≤a,b,c≤100)a,b,c
//a,b,c(0≤a,b,c≤100)，要求把这三位整数从小到大排序。

int a[4];
int main()
{ 
   
	for(int i=1;i<=3;i++)
		cin>>a[i];
	//冒泡排序
	for(int i=1;i<=3;i++)
	for(int j=1;j<=3-i;j++)
		if(a[j]>a[j+1])
		swap(a[j],a[j+1]);
	//遍历输出
	for(int i=1;i<=3;i++)
		cout<<a[i]<<" ";
    return 0;
}

【深基4.例6】数字直角三角形

题目来源

https://www.luogu.com.cn/problem/P5721

题目描述

给出n(1≤n≤13)，请输出一个直角边长度是 n 的数字直角三角形。所有数字都是 2 位组成的，如果没有 2 位则加上前导 0。

输入格式

无

输出格式

无

输入输出样例

输入 #1

5

输出 #1

0102030405
06070809
101112
1314
15

解题思路

计算了一下，第一层n个数，第n层1个数，一共(n+1)*n/2个数，n最大13，最多有91个数，都是两位数，不存在三位数或者更高位得数，只有前导0得问题。

水题，两层for循环遍历

AC代码
#include <iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
//给出n(1≤n≤13)
//请输出一个直角边长度是 nnn 的数字直角三角形。
//所有数字都是 2 位组成的，如果没有 2 位则加上前导 0。
int main()
{ 
   
	int n;//
	cin>>n;
	int cnt = 1;
	for(int i = 1;i <= n; i++){ 
   
		for(int j = 1; j <= n+1-i; j++){ 
   
			if(cnt < 10){ 
   //补上前导0
				cout<<0<<cnt;
			}
			else
				cout<<cnt;
			cnt++;
		}
		cout<<endl;//每行换行
	}
    return 0;
}

【深基5.例3】冰雹猜想

题目来源

https://www.luogu.com.cn/problem/P5727

题目描述

给出一个正整数 n(n≤100)，然后对这个数字一直进行下面的操作：如果这个数字是奇数，那么将其乘 3 再加 1，否则除以 2。经过若干次循环后，最终都会回到 1。经过验证很大的数字（7×1011）都可以按照这样的方式比变成 1，所以被称为“冰雹猜想”。例如当 n是 20，变化的过程是 [20, 10, 5, 16, 8, 4, 2, 1]。

根据给定的数字，验证这个猜想，并从最后的 1 开始，倒序输出整个变化序列。

输入格式

无

输出格式

无

输入输出样例

输入 #1

20

输出 #1

1 2 4 8 16 5 10 20

解题思路

可以递归求解，我想法比较直观，求出每一次的变换的数，直到最后为1，将这些数全部装到数组里，然后逆序输出就行。

为防止中间数据太长，数组长度开到104。

AC代码
#include <iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
int a[10000];
int hanshu(int m)
{ 
   
	if (m == 1)
		return 1;
	else if(m%2 == 0)
		return m/2;
	else
		return 3*m + 1;
}

int main()
{ 
   
	int n,x;//n<=1000
	cin>>n;
	int i = 1;
	a[1] = n;
	while(1){ 
   
		if(a[i] == 1)
			break;
		a[i+1] = hanshu(a[i]);
		i++;
	}
	for(int t = i;t >= 1;t--)
		cout<<a[t]<<" ";
    return 0;
}

【深基6.例1】自动修正

题目来源

https://www.luogu.com.cn/problem/P5733

题目描述

大家都知道一些办公软件有自动将字母转换为大写的功能。输入一个长度不超过 100 且不包括空格的字符串。要求将该字符串中的所有小写字母变成大写字母并输出。

输入格式

无

输出格式

无

输入输出样例

输入 #1

Luogu4!

输出 #1

LUOGU4!

解题思路

啥也不多说了，水题。

AC代码
#include <iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;

int main()
{ 
   
	string str;
	cin>>str;
	int len = str.length();
	for(int i=0;i<len;i++){ 
   
		if(str[i]>='a' && str[i]<='z')
			str[i] = (char)(((str[i] - 'a')+ 26)%26+'A');
	}
	cout<<str;
    return 0;
}

【深基7.例7】计算阶乘

题目来源

https://www.luogu.com.cn/problem/P5739

题目描述

求 n!(n≤12)，也就是 1×2×3…×n。

挑战：尝试不使用循环语句（for、while）完成这个任务。

输入格式

无

输出格式

无

输入输出样例

输入 #1

3

输出 #1

6

解题思路

递归函数，最低级的递归。

AC代码
#include <iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
//计算阶乘
long long fact(int n)
{ 
   
	if(n==0 || n==1)
		return 1;
	else
		return n*fact(n-1);
}
int main()
{ 
   
	int n;
	cin>>n;
	cout<<fact(n);
    return 0;
}

【深基15.例2】寄包柜

题目来源

https://www.luogu.com.cn/problem/P3613

题目描述

超市里有 n(n≤105)个寄包柜。每个寄包柜格子数量不一，第 i 个寄包柜有 ai(ai≤105)个格子，不过我们并不知道各个 ai 的值。对于每个寄包柜，格子编号从 1 开始，一直到 ai​。现在有 q(q≤105) 次操作：

1 i j k：在第 i个柜子的第 j个格子存入物品 k(0≤k≤109)。当 k=0时说明清空该格子。
2 i j：查询第 i个柜子的第 j个格子中的物品是什么，保证查询的柜子有存过东西。

已知超市里共计不会超过 107 个寄包格子，ai是确定然而未知的，但是保证一定不小于该柜子存物品请求的格子编号的最大值。当然也有可能某些寄包柜中一个格子都没有。

输入格式

第一行 2 个整数 n 和 q，寄包柜个数和询问次数。

接下来 q 行整数，每行表示一次操作。

输出格式

对于查询操作时，输出答案。

输入输出样例

输入 #1

5 4
1 3 10000 114514
1 1 1 1
2 3 10000
2 1 1

输出 #1

114514
1

解题思路

因为保证每次查询的数都是可以查询的，那么可以为每一个格子定义一个结构体

typedef struct
{ 
   
	int x;
	int y;
	int value;
}fangge;

但是每次查询时都得在这个结构体数组中进行查询，当输入的两个量分别和x,y相等时才是所要的数据，这个时间复杂度为O(n)，由于n≤105，ai≤105，很显然应该会超时。
笔者试过，80分代码如下：

#include <iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;

typedef struct
{ 
   
	int x;
	int y;
	int value;
}shopping;

int main()
{ 
   
	int n,q;
	cin>>n>>q;
	shopping a[q+1];
	int key[q+1];//存放每次查询结果，方便一并输出
	int opt,x,y,z;
	int t = 1,sqm = 1;
	for(int i = 1;i<=q;i++){ 
   
		cin>>opt;//输入操作码
		if(opt == 1){ 
     //新节点
			cin>>x>>y>>z;
			a[t].x = x;
			a[t].y = y;
			a[t].value = z;
			t++;
		}
		else if(opt == 2){ 
   
			cin>>x>>y;   //查询
			for(int j = 1;j<=t;j++)
				if(a[j].x == x && a[j].y == y)
					key[sqm] = a[j].value;
			sqm++;
		}
	}
	//输出查询结果
	//查询结果数为 sqm - 1
	for(int i = 1;i<sqm;i++)
		cout<<key[i]<<endl;
    return 0;
}

在这里插入图片描述我们可以通过直接索引的方式将每次查找的时间复杂度降为O(1)。
用到STL中的map。

#include<bits/stdc++.h>
map<int int>a1[100001];

AC代码如下：

AC代码
#include <iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<bits/stdc++.h>
using namespace std;
map<int,int>a1[100001];

int main()
{ 
   
	int n,q;
	cin>>n>>q;
	int key[q+1];
	int opt,x,y,z;//每一行先输入一个数，是1表示装入，是2表示查询
	int sqm = 1;
	for(int i = 1;i<=q;i++){ 
   
		cin>>opt;
		if(opt == 1){ 
   
			cin>>x>>y>>z;
			a1[x][y] = z;
		}
		else if(opt == 2){ 
   
			cin>>x>>y;
			//索引查找
			key[sqm] = a1[x][y];
			sqm++;
		}
	}
	//输出查询结果
	//查询结果总数为 sqm - 1
	for(int i = 1;i<sqm;i++)
		cout<<key[i]<<endl;
    return 0;
}

【深基17.例6】学籍管理

题目来源

https://www.luogu.com.cn/problem/P5266

题目描述

您要设计一个学籍管理系统，最开始学籍数据是空的，然后该系统能够支持下面的操作（不超过 100000条）：

插入与修改，格式1 NAME SCORE：在系统中插入姓名为 NAME(由字母和数字组成不超过 20 个字符的字符串，区分大小写) ，分数为 SCORE(0<SCORE<10000) 的学生。如果已经有同名的学生则更新这名学生的成绩为 SCORE。如果成功插入或者修改则输出OK。
查询，格式2 NAME：在系统中查询姓名为 NAME 的学生的成绩。如果没能找到这名学生则输出Not found，否则输出该生成绩。
删除，格式3 NAME：在系统中删除姓名为 NAME 的学生信息。如果没能找到这名学生则输出Not found，否则输出Deleted successfully。
汇总，格式4：输出系统中学生数量。
输入格式

无

输出格式

无

输入输出样例

输入 #1

5
1 lxl 10
2 lxl
3 lxl
2 lxl
4

输出 #1

OK
10
Deleted successfully
Not found
0

解题思路

还是运用STL中的map，因为学生的成绩和学生的姓名是一个从字符串到整型数据的一种映射关系，而map正好能够解决这种问题。

同时，题目中的几种操作，查询，删除，更新和汇总，正是map最基本的成员函数的运用。

在这里插入图片描述

#include<bits/stdc++.h>
map <string ,int> a;  //定义map
AC代码
#include <iostream>
#include<stdio.h>
#include<stdlib.h>
#include<bits/stdc++.h>
using namespace std;
map <string ,int> a;  //定义map

int main()
{ 
   
	int n;
	cin>>n;
	int opt;//操作码
	string name;
	int score;
	for(int i = 1;i <= n;i++){ 
   
		cin>>opt;
		//插入和修改
		if(opt == 1){ 
   
			cin>>name>>score;
			a[name] = score;
			cout<<"OK"<<endl;
		}
		//查询
		else if(opt == 2){ 
   
			cin>>name;
			//该生在系统中,可查询
			if(a.count(name) == 1)
				cout<<a[name]<<endl;
			else
				cout<<"Not found"<<endl;

		}
		//删除
		else if(opt == 3){ 
   
			cin>>name;
			//该生在系统中，可删除
			if(a.count(name) == 1){ 
   
				a.erase(name);
				cout<<"Deleted successfully"<<endl;
			}
			else
				cout<<"Not found"<<endl;
		}
		//汇总
		else if(opt == 4){ 
   
			cout<<a.size()<<endl;
		}

	}//for
    return 0;
}

总结

C/C++入门级训练，笔者今天做了之后觉得还比较简单。
在这里插入图片描述

今天的文章洛谷unaccepted_ig对grf的详细比赛数据分享到此就结束了，感谢您的阅读。

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/63973.html

赞 (0)
编程小号编程小号
0

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注