把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。

题目大意：

CF1535C Unstable String
题目大意：给一个串(2e5)，包含’1’,’0’,’?’，其中问号可以任意替换为0或1，求有多少个子串，子串中相邻位置不能相同（每个子串中的问号都可以任意变为0和1）。

解：

2e5的复杂度让区间问题成为不可能，于是容易想到是线性，对于这题来说，不同位置有明显的转化，’1’的位置可以作为’0’的位置的后继，反之亦然，而’?’可以作为任何一个字符的后继，于是定态dp[i][j]，i表示位置，j表示字符是0还是1，问号的时候两个一起转化，至于dp表示的值那就是结尾为i的合格串最长长度了，也就是说：
Dp[i][0]=dp[i-1][1] 为0
Dp[i][1]=dp[i-1][0] 为1
问号的时候两个都转移。
为什么取长度呢？因为知道结尾和满足条件的长度，那么合格的串数不就等于长度吗？但是这个问题里有所区别，因为子串只和头尾位置有关，那么同位置的串中即使问号表示的字符不同也算是同一个串，所以在求和的时候要求max(dp[i][0],dp[i][1])而不是相加。
算是有些细节的线性dp，蛮有意思的水题。

代码

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <stack>
#include <set>
#include <cstring>
#include <string>
#include <fstream>
#define ll long long
#define maxn 200005
#define mdl 998244353
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
#define cfast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pll pair<ll,ll>
#define pii pair<int,int>
#define inc(i,a,n) for(int i=a;i<n;i++)
#define vset(a,n,m) for(ll i=0;i<n;i++)a[i]=m;
#define endl '\n'
using namespace std;
ll dp[maxn][2];
int vis[maxn];
inline ll cntlen(ll len) {
    return (1 + len) * len / 2;
}
int main() {
    cfast;
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        ll res = 0;
        inc(i, 1, s.length() + 1) {
            if (s[i - 1]=='0') {
                dp[i][0] = dp[i - 1][1] + 1;         
            }
            else if (s[i - 1] == '1') {
                dp[i][1] = dp[i - 1][0] + 1;
            }
            else {
                dp[i][1] = dp[i - 1][0] + 1;
                dp[i][0] = dp[i - 1][1] + 1;
            }
            res += max(dp[i][0],dp[i][1]);
        }
        inc(i, 1, s.length() + 1) {
            dp[i][0] = 0;
            dp[i][1] = 0;
        }
        cout << res << endl;
        
    }
}
//2022.4.19 13:14
/*



*/