T1 瑞神的序列

题目描述

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

求解思路

从头开始向后扫描，temp记录当前段的数字，遇到不同数字时，则记录当前段，进入下一段，更新 temp。

代码

#include<iostream>
#include<stdio.h>
using namespace std;int arr[1005];
int main()
{int n;cin >> n;for (int i = 1; i <= n; i++){cin >> arr[i];}int coun = 1;int temp = arr[1];for (int i = 1; i <= n; i++){if (arr[i] != temp){coun++;temp = arr[i];}}cout << coun;
}

T2 消消乐大师——Q老师

题目描述

Q老师是个很老实的老师，最近在积极准备考研。Q老师平时只喜欢用Linux系统，所以Q老师的电 脑上没什么娱乐的游戏，所以Q老师平时除了玩Linux上的赛车游戏SuperTuxKart之外，就是喜欢 消消乐了。 游戏在一个包含有 n 行 m 列的棋盘上进行，棋盘的每个格子都有一种颜色的棋子。当一行或一列 上有连续三个或更多的相同颜色的棋子时，这些棋子都被消除。当有多处可以被消除时，这些地方的棋子将同时被消除。 一个棋子可能在某一行和某一列同时被消除。 由于这个游戏是闯关制，而且有时间限制，当Q老师打开下一关时，Q老师的好哥们叫Q老师去爬 泰山去了，Q老师不想输在这一关，所以它来求助你了！！
输入描述
输入第一行包含两个整数n,m，表示行数和列数 接下来n行m列，每行中数字用空格隔开，每个数字代表这个位置的棋子的颜色。数字都大于0.
输出描述
输出n行m列，每行中数字用空格隔开，输出消除之后的棋盘。（如果一个方格中的棋子被消除， 则对应的方格输出0，否则输出棋子的颜色编号。）

求解思路

题目关键点在于多处可以被消除时，这些地方的棋子将同时被消除。 一个棋子可能在某一行和某一列同时被消除。因此，分别计算消除行和消除列后的棋盘，输出时只有消除行和消除列都没有消掉，才输出原数字，否则输出0。

代码

#include<iostream>
#include<stdio.h>
using namespace std;int chessrow[32][32];
int chesscol[32][32];
int n, m;
void solve()
{for (int i = 1; i <= n; i++){int temp = chessrow[i][1];int num = 1;for (int j = 1; j <= m; j++){if (chessrow[i][j] != temp){if (j - num >= 3)//find row{for (int k = num; k < j; k++){chessrow[i][k] = 0;}}temp = chessrow[i][j];num = j;}}if (m - num >= 2)//{for (int k = num; k <=m; k++){chessrow[i][k] = 0;}}}for (int j = 1; j <= m; j++){int temp = chesscol[1][j];int num = 1;for (int i = 1; i <= n; i++){if (chesscol[i][j] != temp){if (i - num >= 3)//find col{for (int k = num; k < i; k++){chesscol[k][j] = 0;}}temp = chesscol[i][j];num = i;}}if (n - num >= 2)//{for (int k = num; k <= n; k++){chesscol[k][j] = 0;}}}for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){if (chesscol[i][j] != 0 && chessrow[i][j] != 0){cout << chesscol[i][j];			}else{cout << 0 ;}if (j != m){cout << " ";}}if (i != n){cout << endl;}}}
int main()
{cin >> n >> m;for (int i = 1; i <= n; i++)for(int j=1;j<=m;j++){cin >> chessrow[i][j];chesscol[i][j] = chessrow[i][j];}solve();
}

T4 咕咕东学英语

题目描述

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

求解思路

数据差距较大，采用不同的处理方式。

• 对于数据较小的数据点：采用solve1()的方法，遍历所有子串A，对于每个子串A，判断子串A的子串B是否为回文子串，若是，则标记该回文子串每个元素的state为1.最后，判断A的所有元素是否都为1，若是，说明A是Delicious的。
• 对于数据较大的数据点：采用solve2()的方法，直接计算有多少Delicious的子串，因为只由大写字母A、B构成字符串，所以可以先计算该字符串中连续的相同的最长整数序列的左右端点，长度为n的字符串的子串个数共有n * (n - 1) / 2个，去掉不是Delicious的子串数量，即为答案。
• 如下图所示，每个序列的交界位置的字母和相邻序列组成的子串会出现不是Delicious的，计算方式可以是n * (n - 1) / 2- 2 *（每个序列的长度）+ 边缘序列的长度（多减了一次）+ 序列交界处个数（n-1）（AB、BA多减了一次）
  

代码

#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;long long n;
char str[300005];
long long state[300005];
bool jud(long long l, long long r)
{long long left = l;long long right = r;while (left < right){if (str[left] != str[right]){return false;}state[left] = 1;state[right] = 1;left++;right--;}state[left] = 1;return true;
}bool judstr(long long l, long long r)
{long long left = l;//1long long right = r;//4for (long long i = left; i <= right; i++){state[i] = 0;}for (long long i = 2; i <= right - left + 1; i++)for (long long j = left; j <= right + 1 - i; j++){bool judge = false;judge = jud(j, j + i - 1);}for (long long i = left; i <= right; i++){if (state[i] == 0){return false;}}return true;
}long long coun;
void solve1()
{for (long long i = 2; i <= n; i++)for (long long j = 0; j <= n - i; j++){bool judge = false;judge = judstr(j, j + i - 1);if (judge)//yes{coun++;}}cout << coun;
}vector<long long> vleft;
vector<long long> vright;
void solve2()
{char ch = str[0];long long num = 0;for (long long i = 0; i < n; i++){if (str[i] != ch){vleft.push_back(num);vright.push_back(i - 1);ch = str[i];num = i;}}vleft.push_back(num);vright.push_back(n - 1);long long ans = n * (n - 1) / 2;for (long long i = 0; i < vleft.size(); i++){ans = ans - (vright[i] - vleft[i] + 1) * 2;}cout << ans + (vright[0] - vleft[0] + 1) + (vright.back() - vleft.back() + 1) + vleft.size() - 1;
}int main()
{cin >> n;cin >> str;coun = 0;if (n < 11){solve1();return 0;}if (n < 101){solve1();return 0;}if (n < 234){solve1();return 0;}solve2();//ERROR
}