T1 瑞神的序列
題目描述
瑞神的數學一向是最好的，連強大的咕咕東都要拜倒在瑞神的數學水準之下，雖然咕咕東很苦惱，但是咕咕東拿瑞神一點辦法都沒有。
5.1期間大家都出去玩了，隻有瑞神還在孜孜不倦的學習，瑞神想到了一個序列，這個序列長度為n，也就是一共有n個數，瑞神給自己出了一個問題：數列有幾段？
段的定義是連續的相同的最長整數序列
輸入描述
輸入第一行一個整數n，表示數的個數
接下來一行n個空格隔開的整數，表示不同的數字
輸出描述
輸出一行，這個序列有多少段
樣例輸入
12
2 3 3 6 6 6 1 1 4 5 1 4
**樣例輸出 **
8
思路
記錄上一個字元，記錄不同的次數，并且注意更新上一個字元即可。
代碼
#include<iostream>
using namespace std;
int main(){
int n;
cin>>n;
int ans = 0;
int last,now;
for(int i=0;i<n;i++){
if(i==0){
scanf("%d",&last);
ans++;
}
else{
scanf("%d",&now);
if(now!=last) ans++;
last = now;
}
}
cout<<ans<<endl;
return 0;
}
T2 消消樂大師——Q老師
題目描述
Q老師是個很老實的老師，最近在積極準備考研。Q老師平時隻喜歡用Linux系統，是以Q老師的電腦上沒什麼娛樂的遊戲，是以Q老師平時除了玩Linux上的賽車遊戲SuperTuxKart之外，就是喜歡消消樂了。
遊戲在一個包含有n 行m 列的棋盤上進行，棋盤的每個格子都有一種顔色的棋子。當一行或一列上有連續三個或更多的相同顔色的棋子時，這些棋子都被消除。當有多處可以被消除時，這些地方的棋子将同時被消除。
一個棋子可能在某一行和某一列同時被消除。
由于這個遊戲是闖關制，而且有時間限制，當Q老師打開下一關時，Q老師的好哥們叫Q老師去爬泰山去了，Q老師不想輸在這一關，是以它來求助你了！！
輸入描述
輸入第一行包含兩個整數n,m，表示行數和列數
接下來n行m列，每行中數字用空格隔開，每個數字代表這個位置的棋子的顔色。數字都大于0.
輸出描述
輸出n行m列，每行中數字用空格隔開，輸出消除之後的棋盤。（如果一個方格中的棋子被消除，
則對應的方格輸出0，否則輸出棋子的顔色編号。）
**樣例輸入1 **
4 5
2 2 3 1 2
3 4 5 1 4
2 3 2 1 3
2 2 2 4 4
**樣例輸出1 **
2 2 3 0 2
3 4 5 0 4
2 3 2 0 3
0 0 0 4 4
思路
使用一個寬度為5的十字架，若滿足十字架上的連續地方數字相同，則對其進行消除即可。此題的關鍵點在于對于邊界的方格，十字架的寬度和高度就不确定了，是以采用擴充方格對周圍進行擴充，就可以直接使用十字架進行比較了。
代碼
#include<iostream>
#include<vector>
using namespace std;
int mt[40][40];
int main() {
int n,m;
cin>>n>>m;
vector<pair<int,int> > v;
for(int i=0; i<40; i++) {
for(int j=0; j<40; j++) mt[i][j] = -1;
}
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
scanf("%d",&mt[i+2][j+2]);
}
}
int index;
for(int i=2; i<n+2; i++) {
for(int j=2; j<m+2; j++) {
int x[5],y[5];
for(int k=0; k<5; k++) {
x[k] = mt[i-2+k][j];
}
for(int k=0; k<5; k++) {
y[k] = mt[i][j-2+k];
}
if(x[2]==x[0]&&x[2]==x[1]) v.push_back(pair<int,int>(i,j));
else if(x[2]==x[3]&&x[2]==x[1]) v.push_back(pair<int,int>(i,j));
else if(x[2]==x[3]&&x[2]==x[4]) v.push_back(pair<int,int>(i,j));
else if(y[2]==y[0]&&y[2]==y[1]) v.push_back(pair<int,int>(i,j));
else if(y[2]==y[3]&&y[2]==y[1]) v.push_back(pair<int,int>(i,j));
else if(y[2]==y[3]&&y[2]==y[4]) v.push_back(pair<int,int>(i,j));
}
}
for(int i=0; i<v.size(); i++) {
int di = v[i].first,dj = v[i].second;
mt[di][dj] = 0;
}
for(int i=2; i<n+1; i++) {
for(int j=2; j<m+1; j++) {
cout<<mt[i][j]<<" ";
}
cout<<mt[i][m+1]<<endl;
}
for(int j=2; j<m+1; j++) {
cout<<mt[n+1][j]<<" ";
}
cout<<mt[n+1][m+1];
return 0;
}
T4 咕咕東學英語
題目描述
咕咕東很聰明，但他最近不幸被來自宇宙的宇宙射線擊中，遭到了降智打擊，他的英語水準被歸零了！這一切的始作俑者宇宙狗卻毫不知情！
此時咕咕東碰到了一個好心人——TT，TT在吸貓之餘教咕咕東學英語。今天TT打算教咕咕東字母A和字母B，TT給了咕咕東一個隻有大寫A、B組成的序列，讓咕咕東分辨這些字母。
但是咕咕東的其他學科水準都還在，敏銳的咕咕東想出一個問題考考TT：咕咕東問TT這個字元串有多少個子串是Delicious的。
TT雖然會做這個問題，但是他吸完貓發現輝夜大小姐更新了，不想回答這個問題，并抛給了你，你能幫他解決這個問題嗎？
Delicious定義：對于一個字元串，我們認為它是Delicious的當且僅當它的每一個字元都屬于一個
大于1的回文子串中。
輸入描述
輸入第一行一個正整數n，表示字元串長度
接下來一行，一個長度為n隻由大寫字母A、B構成的字元串。
輸出描述
輸出僅一行，表示符合題目要求的子串的個數。
**樣例輸入 **
5 A
ABBB
**樣例輸出 **
6
樣例解釋
對于該樣例，符合條件的六個子串分别是：
s1-s2 s1-s4 s1-s5 s3-s4 s3-s5 s4-s5
思路
印象中是參照了某個大佬的部落格，首先從頭向後周遊，由于均有AB組成，是以找到前後不同的位置，并記錄之間的長度，然後從後向前再次周遊，使用總個數減去這些不能構成回文的子串即可，例如AAAAB這種的就不滿足，同理ABBBB也不滿足。
由于AB和BA一樣，是以需要加上一遍。
代碼
#include<iostream>
using namespace std;
string s;
char c[300000+10];
int main() {
long long n;
cin>>n;
cin>>s;
long long delta = 0;
long long lastIndex = 0;
for(int i=1;i<=n;i++){
c[i] = s.c_str()[i-1];
}
long long tc = 0;
for(long long i=1;i<=n-1;i++){
if(c[i]!=c[i+1]){
delta += (i-lastIndex);
// cout<<c[i]<<":"<<c[i+1]<<endl;
// cout<<lastIndex<<endl;
lastIndex = i;
tc ++;
}
}
lastIndex = n+1;
for(long long i=n;i>=2;i--){
if(c[i]!=c[i-1]){
delta += (lastIndex - i);
// cout<<c[i]<<":"<<c[i+1]<<endl;
// cout<<lastIndex<<endl;
lastIndex = i;
}
}
cout<<(n-1)*n/2 - delta + tc<<endl;
return 0;
}