day3

正睿提高

2018.9.8

预计：100+100+70
实际：100+100+70

有点zz，题3上来就想到了n^3区间dp，然后却没想到枚举左右端点。
然后最后回一区的路上想起了T3的正解。

T1

字典序最小，所以维护两个指针，先放小的。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<vector>
#include<queue>
#include<map>
using namespace std;
typedef long long LL;
inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
const int N = 200010;
int a[N], b[N], c[N];
int main() {
    int n = read(), m = read();
    for (int i=1; i<=m; ++i) {
        a[i] = read(); c[a[i]] = 1;
    }
    int p = 0;
    for (int i=1; i<=n; ++i) {
        if (!c[i]) b[++p] = i;
    }
//  puts("");
    int p1 = 1, p2 = 1;
    while (p1 <= m && p2 <= p) {
        if (a[p1] < b[p2]) {
            printf("%d\n",a[p1]);
            p1 ++;
        }
        else {
            printf("%d\n",b[p2]);
            p2 ++;
        }
    }
    for (int i=p1; i<=m; ++i) printf("%d\n",a[i]);
    for (int i=p2; i<=p; ++i) printf("%d\n",b[i]);
    return 0;
}

T2

一个数轴，很多线段。很多给定的点。对于线段有多少种选择方案，使选的线段在同一个点上。

如果只有一个点，那么就是线段的所有的组合方式。两个点并且没有个一个线段覆盖两个点话，也可以直接2^k求。现在就是求一些线段覆盖了很多个点的时候，不重复的计算。

对于一个点上的很多线段，有x条是第一次出现，y条是以前出现了的（假设y条在上一个点计算了在上一个点的贡献，只考虑这个点的贡献）。那么x条就是$2^x-1$随便选。y条那么考虑它和x一起组合的方案，就是$(2 ^ x - 1) \times (2 ^ y - 1)$。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<vector>
#include<queue>
#include<map>
using namespace std;
typedef long long LL;
inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
const int N = 200100;
const LL mod = 998244353;
struct Edge{
    int l,r;
    bool operator < (const Edge &A) const {
        return r < A.r;
    }
}A[N];
int B[N];
int s[N << 2], C[N << 2];
bool pd[N << 2];
vector<int> R[N << 2];
LL mi[N];
int main() {
    int n = read(), m = read(), cnt = 0;
    mi[0] = 1;
    for (int i=1; i<=n; ++i) mi[i] = 1ll * mi[i - 1] * 2 % mod;
    for (int i=1; i<=n; ++i) {
        A[i].l = read(), A[i].r = read();
        s[++cnt] = A[i].l; s[++cnt] = A[i].r;
    }
    for (int i=1; i<=m; ++i) {
        B[i] = read(); s[++cnt] = B[i];
    }
    sort(s + 1, s + cnt + 1);
    int lim = cnt; cnt = 1;
    for (int i=2; i<=lim; ++i) if (s[i] != s[cnt]) s[++cnt] = s[i];
    for (int i=1; i<=n; ++i) {
        A[i].l = lower_bound(s + 1, s + cnt + 1, A[i].l) - s;
        A[i].r = lower_bound(s + 1, s + cnt + 1, A[i].r) - s;
        C[A[i].l] ++; C[A[i].r + 1] --;
        R[A[i].l].push_back(A[i].r);
    }
    for (int i=1; i<=m; ++i) 
        B[i] = lower_bound(s + 1, s + cnt + 1, B[i]) - s;
    sort(B + 1, B + m + 1);
    int pos = 1, now = 0;
    LL Ans = 0;
    for (int i=1; i<=m; ++i) {
        int add = 0;
        while (pos <= B[i]) {
            now += C[pos];
            for (int sz=R[pos].size(),j=0; j<sz; ++j) 
                if (R[pos][j] >= B[i]) add++;
            pos ++;
        }
        Ans = (Ans + 1ll * (mi[add] - 1)) % mod;
        Ans = (Ans + 1ll * (mi[add] - 1) * (mi[now - add] - 1) % mod) % mod;
    }
    cout << Ans % mod;
    return 0;
}
/*
7 2
1 2
1 2
2 4
2 4
2 4
4 5
4 5
2 4
*/

T3

求多少合法的括号序列，括号有26种。

就是求多少个区间中的匹配是合法的。首先n^3dp。然后n^2的更简单，直接枚举左右端点，用一个栈判断。

考虑O(n)的做法。假设一个匹配时这样的，a......a....a那么第一个a只要找到它往右第一个合法的匹配（就是第二个a），然后直接加上第二个a的合法匹配就行了。那么如何找第一个合法匹配呢。
ab....ba
从后往前，假设后面的已经找到了最近的合法匹配，并保存了下来，然后可以直接判断它的最近的合法匹配的下一位是否与a相同（上面就是b找到第二个b，然后a判断第二个b的下一位）。
ab....bc..ca
如果一样，那么在找下一位的最近的合法匹配（就是c找到下一个c）
其中b....b和c..c都是合法的两段，它们不影响。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cctype>
using namespace std;
typedef long long LL;
inline int read() {
    int x=0,f=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
    return x*f;
}
const int N = 1000100;
char s[N];
int pos[N];
LL cnt[N];
void solve(int n) {
    LL Ans = 0;
    pos[n] = n + 1;
    for (int i=n; i>=1; --i) {
        int j = i + 1;
        while (j <= n && s[i] != s[j]) j = pos[j] + 1;
        pos[i] = j > n ? n + 1 : j;
        if (j <= n) cnt[i] += cnt[j + 1] + 1;
        Ans += cnt[i];
    }
    cout << Ans;
}
int main() {
    scanf("%s",s+1);
    int n = strlen(s + 1);
    solve(n);
    return 0;
}