洛谷上的 AtCoder 水(难)题(C++)【第六到十题】

洛谷上的 AtCoder 水(难)题(C++)【第六到十题】

啊，又是刷题的一天~~

想看第一到五题的朋友可以康康这里~~

这次讲解为了方便理解，我把一些题面改得通俗了一点，有的原题实在看不下去

好——了，不——多——废——话——刷——题——吧~~

第六题：寿司タワー - 洛谷

题目描述:

一个寿司由一个米饭和一个菜组成。 现在想用N个寿司来做寿司塔。（包含N个米饭和N个菜）

装1个寿司的方法有以下3种。

1、原封不动:按米饭、菜的顺序。

2、翻过来:按照菜、米饭的顺序。

3、拆开装:分开米饭和菜，分别装。

例如，想把3个寿司从下面开始依次装成“菜、米饭、菜、菜、米饭、米饭”的寿司塔，可以按以下顺序。

1、把一个寿司拆开，装上菜。

2、直接装一个寿司。

3、把一个寿司翻过来装。

4、装上留下的白米饭。 因为拆开寿司很费工夫，所以想尽量减少拆开寿司的个数。

求完成目标寿司塔需要拆开的寿司个数的最小值。

输入格式： 两行。 第一行给出了寿司的个数N。 第二行给出了长度为2N的字符串s，表示寿司塔的堆叠顺序（从下往上）。s是由0和1构成的字符串，其中0代表米饭，1代表菜。

输出格式： 一行。 完成目标寿司塔需要拆开的寿司个数的最小值。在输出的末尾加上换行符。

样例1

输入：

3
101100

输出：

1

样例2

输入：

5
0000111011

输出：

3

思路：

这道题暴力是不可能暴力的，这辈子都不可能暴力的；

我们可以采用一下思路：

1.统计没有被拆分的寿司

2.再用总数减去完整的寿司即可

Code：

#include
using namespace std;
string s;
int n,t;
int main() {
	scanf("%d",&n);
	cin>>s;
	int len=s.size();
	for(int i=0;i 
第七题：おとぎの国の高橋君 - 洛谷 
题目描述：
 
高桥君所住的AtCoder国，和我们一样，也普遍使用着10进制的10个阿拉伯数字(0-9)(0−9)。
 
但是，AtCoder国的数字的大小关系与我们普遍使用的数字的大小关系不同。举例来说：当AtCoder国的数字从小到大为的顺序时，在AtCoder国中8就比9大，而72也比97大。
 
给出AtCoder国的每个阿拉伯数字的大小关系，请将AtCoder国中的一些数按升序排列。
 
另外，和我们普遍使用的数字一样，AtCoder国中最小的数字一定是0
 
样例1
 
输入：
 
0 8 1 3 5 4 9 7 6 2
10
1
2
3
4
5
6
7
8
9
10
 
输出：
 
8
1
3
5
4
9
7
6
2
10
 
样例2
 
输入：
 
0 9 8 7 6 5 4 3 2 1
3
13467932
98738462
74392
 
输出：
 
74392
98738462
13467932
 
思路： 
这道题我们要将AtCoder王国里的数字转化成正常的数字，再用用结构体，记录两个元素：一个是AtCoder王国里的数字，一个是正常的数字。
 
Code： 
#include
using namespace std;
struct yin {
	int a;//AtCoder王国里的数字 
	int b;//正常的数字 
} yy[77777];
int a[10],n,k;
int woc(int aa) {//将AtCoder王国里的数字转化成正常的数字 
	int ans=0;
	int k=1;
	while(aa) {
		int h=aa%10;
		ans+=a[h]*k;
		aa/=10;
		k*=10;
	}
	return ans;
}
bool cmp(yin x,yin y) {//按照正常的值从小到大排序 
	return x.b 
第八题：(iwi) - 洛谷 
题目描述：
 
定义对称如下：
 
空串一个字母'i'一个字母'w'在两个字母('i'或'w')中包含一个对称的字符串，如  "iwi"  ,  "wiw"  ,  "ii"  ,  "www"在括号中包含一个对称的字符串，注意括号有两种形式，                                                        1、"()"                                                                                                                                              2、")("，即"(i)"和")i("均为合法对称字符串。
求最少进行几次更改 *** 作，使一个字符串变为对称。
 
输入一个由'i','w','('和')'组成的字符串。
 
输出一个正整数，即最少更改次数。
 
样例1
 
输入：
 
(iwi)
 
输出：
 
0
 
样例2
 
输入：
 
ii(((((ww
 
输出：
 
5
 
思路： 
这道题就是模拟啦！
 
假设字符串的长度为N，
 
如果第位是'i'，那么第位也要是’i‘；
 
如果第位是'w'，那么第位也要是’w‘；
 
如果第位是'('，那么第位就要是’)‘；
 
如果第位是')'，那么第位就要是’(‘；
 
Code 
#include
using namespace std;
string s;
bool yin(char x,char y) {
	if(x=='i'&&y=='i') return 1;
	if(x=='w'&&y=='w') return 1;
	if(x=='('&&y==')') return 1;
	if(x==')'&&y=='(') return 1;
 
	return 0;
}
int k=0;
int main() {
	cin>>s;
	int si=s.size();
	for(int i=0;i<(si+1)/2;i++) {
		if(!yin(s[i],s[si-i-1])) k++;//如果不符合规定 ， k++ 
	}
	printf("%dn",k);
	return 0;
}
 
第九题：和がNの区間 - 洛谷 
题目描述：
 
 给你一组n的排列，记为，问存在多少对L,R，满足
 
样例1 
 
输入：
 
7
7 6 5 4 3 2 1
 
输出：
 
2
 
样例2
 
输入：
 
20
19 11 10 7 8 9 17 18 20 4 3 15 16 1 5 14 6 2 13 12
 
输出：
 
3
 
思路： 
这道题用前缀和来做，再模拟左右端点即可
 
Code： 
#include
using namespace std;
int n,a[100010];
int ans=0;
int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);//输入 
		a[i]=a[i-1]+a[i];//前缀和 
	}
	for(int i=1;i<=n;i++) {//模拟左端点 
		for(int j=i;j<=n;j++){//模拟右端点 
			if(a[j]-a[i-1]>n)//解释一下 a[j]-a[i-1] 就是从a[i]加到a[j] 
			//如果和大于n，就没必要再加下去了，和只会越来越大 
			    break;
			if(a[j]-a[i-1]==n)//如果和等于n 
			    ans++;
		}
	}
	printf("%dn",ans);
	return 0;
}
 
第十题：[ARC076A] Reconciled? - 洛谷 
题目描述
 
すぬけ君养了N只狗和M 只猴。すぬけ君想把这N+M只动物排成一列。
 
すぬけ君希望狗与狗不能互相挨着，猴与猴不能互相挨着。
 
这样的排列方式有多少种？请输出答案对取模的结果。不过，狗与狗间，猴与猴间相互区别。
 
样例1
 
输入：
 
2 2
 
 输出：
 
8
 
样例2
 
输入：
 
100000 100000
 
输出：
 
530123477
 
思路： 
这道题
 
猴与狗的排列无疑都是交叉排列的；
 
我们又可以把他们拆开成一队全是狗的队伍和全是猴的队伍
 
全是狗的队伍可有！N（N的阶乘）种
 
全是猴的队伍可有！M（M的阶乘）种
 
整个队伍有！N*！M种排法
 
我们可以发现：
 
1.首先，N与M的绝对值不能大于1；
 
2.如果N-M==1,那么有以下两种可能：
 
   (1  猴 狗 猴 狗 猴 狗 ... 猴 （以猴开头，以猴结尾）
 
   (2  狗 猴 狗 猴 狗 猴 ... 狗 （以狗开头，以狗结尾）
 
整个队伍有！N  *  ！M种排法
 
3.如果N==M，那么狗与猴子的排列，一种情况就有有两种排法：
 
   (1  猴 狗 猴 狗 猴 狗 ... 猴 狗（以猴开头，以狗结尾）
 
   (2  狗 猴 狗 猴 狗 猴 ... 猴 狗（以狗开头，以猴结尾） 
 
因为一种情况就有有两种排法
 
整个队伍有！N  *  ！M  *  2种排法
 
Code： 
#include
using namespace std;
const int Mod=1000000007;
long long n,m;
long long jc(int x) {//阶乘 
	long long ans=1;
	for(int i=1; i<=x; i++)
		ans*=(i%Mod),ans%=Mod;//每一步都要取摸 
	return ans;
}
int main() {
	scanf("%lld%lld",&n,&m);
	if(abs(n-m)>=2) {//n,m的绝对值如果大于2 
		printf("%dn",0);//则没有排列方法 
		return 0;
	}
	n=jc(n),m=jc(m); 
	if(n==m)//如果N==M,整个队伍有！N * ！M * 2种排法
		printf("%lldn",m*n%Mod*2%Mod);
	else//如果N-M==1,整个队伍有 ！N * ！M 种排法
		printf("%lldn",m*n%Mod);
	return 0;
}
 
Oh，最后，千万别忘了——  
 
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5714618.html