程序设计思维与实践 CSP-M3 补题 (3/4/数据班)

A - csp-m3-t1

题目

瑞神的数学一向是最好的，连强大的咕咕东都要拜倒在瑞神的数学水平之下，虽然咕咕东很苦恼，但是咕咕东拿瑞神一点办法都没有。
5.1期间大家都出去玩了，只有瑞神还在孜孜不倦的学习，瑞神想到了一个序列，这个序列长度为n，也就是一共有n个数，瑞神给自己出了一个问题：数列有几段？
段的定义是连续的相同的最长整数序列

分析

根据当前的字符判断,和上一个相同就使用一个变量记录出现过的长度,不相同就找到一段的终点,使用长度和当前最长的长度对比取最长

代码

#include<iostream>

using namespace std;
int main(){
	int num,count=1;scanf("%d",&num);
	int pos;scanf("%d",&pos);
	for(int i=1;i<num;i++){
		int q;scanf("%d",&q);
		if(q!=pos) {
			count++;
			pos=q;
		}
	}
	printf("%d",count);
	return 0;
}

B - csp-m3-t2

题意

Q老师是个很老实的老师，最近在积极准备考研。Q老师平时只喜欢用Linux系统，所以Q老师的电脑上没什么娱乐的游戏，所以Q老师平时除了玩Linux上的赛车游戏SuperTuxKart之外，就是喜欢消消乐了。
游戏在一个包含有n 行m 列的棋盘上进行，棋盘的每个格子都有一种颜色的棋子。当一行或一列上有连续三个或更多的相同颜色的棋子时，这些棋子都被消除。当有多处可以被消除时，这些地方的棋子将同时被消除。
一个棋子可能在某一行和某一列同时被消除。
由于这个游戏是闯关制，而且有时间限制，当Q老师打开下一关时，Q老师的好哥们叫Q老师去爬泰山去了，Q老师不想输在这一关，所以它来求助你了！！

分析

这道题数据也不大,直接使用暴力来计算就可以,记录一个内容的矩阵,一个是否消除的矩阵,遍历每一个三元的单位,如果都一样,就在消除的矩阵里标记,最后输出标记的矩阵的判断就可以完成

代码

#include<iostream>
#include<cstring>
using namespace std;
int pp[40][40];
bool flag[40][40];
int main(){
	int n,m;
	memset(pp,false,sizeof(pp));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;++j)
			scanf("%d",&pp[i][j]);
	for(int i=1;i<=n;++i){
		int l=1,r=3;
		while(r<=m){
			if(pp[i][l]==pp[i][l+1]&&pp[i][l+1]==pp[i][l+2]){
				for(int w=l;w<=r;++w)
					flag[i][w]=true;
			}
			l++,r++;
		}
	}
	for(int i=1;i<=m;++i){
		int l=1,r=3;
		while(r<=n){
			if(pp[l][i]==pp[l+1][i]&&pp[l+1][i]==pp[l+2][i]){
				for(int w=l;w<=r;++w)
					flag[w][i]=true;
			}
			l++,r++;
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(flag[i][j]) printf("0");
			else printf("%d",pp[i][j]);
			if(j!=m) printf(" ");
		}
		printf("\n");
	}
	return 0;
}

T4 咕咕东学英语

题意

咕咕东很聪明，但他最近不幸被来自宇宙的宇宙射线击中，遭到了降智打击，他的英语水平被归零了！这一切的始作俑者宇宙狗却毫不知情！
此时咕咕东碰到了一个好心人——TT，TT在吸猫之余教咕咕东学英语。今天TT打算教咕咕东字母A和字母B，TT给了咕咕东一个只有大写A、B组成的序列，让咕咕东分辨这些字母。
但是咕咕东的其他学科水平都还在，敏锐的咕咕东想出一个问题考考TT：咕咕东问TT这个字符串有多少个子串是Delicious的。
TT虽然会做这个问题，但是他吸完猫发现辉夜大小姐更新了，不想回答这个问题，并抛给了你，你能帮他解决这个问题吗？
Delicious定义：对于一个字符串，我们认为它是Delicious的当且仅当它的每一个字符都属于一个大于1的回文子串中。

分析

通过多次的检查各种字符串,我发现,只有在a和b交接处才会出现不是delicious的字符串,像A[n]B[n],或者B[n]An才会不符合条件,使用所有的字符串(n-1)*n/2减去不符合的就是符合的了
对于不符合的字符串,AB[n]这样的,会有n个字符串不符合,分别是AB[1],AB[2]…aB[n],但对于中间的B[n]一段,除了他是最前面或者最后面一段,他会有前后两个A,所以这一段要算两次,总结下来就是最前面和最后面的一段连续的段算一次,其余的段都算两次,这样我们的基本思路就有了.
我首先搞出来一个数组,里面的内容是各个连续串的长度,之后都好说了

代码

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int nmax=3E5+10;
char str[nmax];
int key[nmax];
int main(){
	int num;
        scanf("%d",&num);
	fill(key,key+nmax,0);
	scanf("%s",str);
	int len=num;
	long long res=(long long)len*(len-1)/2;
	char pos=str[0];
	int count=1,pp=0;
	for(int i=1;i<len;++i){
		if(pos==str[i]) {
			count++;
		}
		else {
			key[pp++]=count;
			count=1;
			pos=str[i];
		}
	}
	key[pp++]=count;
	if(pp==1){
		printf("%lld",res);
		return 0;
	}
	res-=key[0];
	for(int i=1;i<pp-1;i++) {res-=2*key[i];}
	res-=key[pp-1];
	res+=pp-1;
	printf("%lld",res);
	return 0;
}