题意

给定一个字符串$s$，求其中出现$k$次的子串的个数。

题解

后缀自动机。

代码

题意

给定$M$个显示屏和$K$个不同颜色的信号源。求最少连多少条数据线，可以使得任选$K$个显示屏，都可以恰好显示$K$个不同颜色。

题解

找规律。

考虑信号源$1$和显示屏$[1,M-K+1]$相连，信号源$2$和显示屏$[2,M-K+2]$相连……信号源$K$和显示屏$[K,M]$相连。故：$res=(M-K+1)*K$。

代码

#include 
    
     using namespace std;typedef long long ll;ll m, k;int main() {    while (~scanf("%lld%lld", &m, &k)) {        printf("%lld\n", (m - k + 1) * k);    }}
    

题意

给定$n$个数$a_i$，爸爸和儿子玩游戏，爸爸每次可以选最左和最右的数，儿子先选且每次选最左最右中最大的（相同选最左），最终和最大的人获胜。爸爸想让儿子获胜，求最小差值。

题解

$DFS$。

代码

题意

给定$n$个数$A_i$，判断能否去掉$k$个数使其变成不上升或不下降序列。

题解

$DP$。

求最长不下降和最长不上升子序列的长度，和$n-k$比较即可。

代码

#include 
    
     using namespace std;const int N = 1e5+9;int n, k, a[N], b[N], d[N];inline int read() {    int s = 1, x = 0; char ch = getchar();    while (ch < '0' || ch > '9') {if (ch == '-') s = -1; ch = getchar();}    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}    return s * x;}inline int dp(int c[N]) {    int len = 0;     d[++len] = c[1];    for (int i = 2; i <= n; i++) {        if (c[i] >= d[len]) d[++len] = c[i];        else *upper_bound(d + 1, d + len + 1, c[i]) = c[i];    }    return len;}int main() {    int T = read();    while (T--) {        n = read(), k = read();        for (int i = 1; i <= n; i++) a[i] = read();        for (int i = 1; i <= n; i++) b[i] = -a[i];        puts((dp(a) >= n - k || dp(b) >= n - k) ? "A is a magic array." : "A is not a magic array.");    }    return 0;}
    

题意

定义能用$k$项斐波拉契数列之和表示的数为“好数”，否则是“坏数”。给定$k$，求最小的“坏数”。

题解

找规律。

根据前几项我们发现：对于$k$，最小的坏数为$F_{2k+3}-1$。矩阵快速幂算一下即可。

代码

#include 
    
     using namespace std;typedef long long ll;const int N = 3;const int Q = 998244353;struct Mat {    ll mat[N][N];}f, g;int k;Mat operator *(Mat a, Mat b) {    Mat c; memset(c.mat, 0, sizeof(c.mat));    for (int k = 1; k <= 2; k++) {        for (int i = 1; i <= 2; i++) {            for (int j = 1; j <= 2; j++) {                c.mat[i][j] += (a.mat[i][k] % Q * b.mat[k][j] % Q);                c.mat[i][j] %= Q;            }        }    }    return c;}Mat operator ^(Mat a, int n) {    Mat c; memset(c.mat, 0, sizeof(c.mat));    for (int i = 1; i <= 2; i++) {        for (int j = 1; j <= 2; j++) {            c.mat[i][j] = (i == j);        }    }    for (; n; n >>= 1) {        if (n & 1) c = c * a;        a = a * a;    }    return c;}int main() {    while (~scanf("%d", &k)) {        memset(f.mat, 0, sizeof(f.mat));        f.mat[1][1] = f.mat[1][2] = f.mat[2][1] = 1;        g = f ^ (2 * k + 1);        f.mat[1][2] = 0;        g = g * f;        printf("%d\n", g.mat[1][1] - 1);    }    return 0;}
    

题意

给定$n$个价值为$V_i$的宝石，两个人从左往右取宝石，第一个人可以取$1$或$2$个，之后若一个人先取了$k$个，则另一个人只能取$k+1$个，当无法再取时游戏结束。求两个人所取宝石的最小差值。

题解

$DP$。

本来以为是个博弈论的，还是图样。。。

考虑动态规划，用$dp[0/1][i][j]$表示某一个人从第$i$个宝石开始取$j$或$j+1$个宝石的最优结果。

转移方程：

$\begin{equation}

dp[0][i][j]=\sum_{i}^{i+j-1}{V_i}+max

\begin{cases}

dp[1][i+j][j]\newline

dp[1][i+j+1][j+1]+V_{i+j} \newline

\end{cases}

\end{equation}$

$\begin{equation}

dp[1][i][j]=-\sum_{i}^{i+j-1}{V_i}+min

\begin{cases}

dp[0][i+j][j] \newline

dp[0][i+j+1][j+1]-V_{i+j} \newline

\end{cases}

\end{equation}$

考虑第三维的范围：极端情况第$k$轮取$k+1$个，有$\frac{(k+1)(k+2)}{2}< n$。故：第三维的$j\leq 200$。

这样时间复杂度为：$\Theta(400n)$。

下面来优化空间复杂度：

考虑不会超过$long\space long$，$dp$数组用$int$型即可；

考虑第二维转移有空间浪费，用滚动数组即可。

HDOJ是缺内存还是怎么滴啊。。$MLE$很难受啊。。

代码

#include 
    
     using namespace std;const int N = 2e4+9;const int K = 209;const int Q = 255;const int M = 255+9;int sum[N], dp[2][M][K];inline int read() {    int s = 1, x = 0; char ch = getchar();    while (ch < '0' || ch > '9') {if (ch == '-') s = -1; ch = getchar();}    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}    return s * x;}int main() {    int T = read();    while (T--) {        int n = read();        memset(sum, 0, sizeof(sum));        for (int i = 1; i <= n; i++) {            int v = read();            sum[i] = sum[i - 1] + v;        }        memset(dp, 0, sizeof(dp));        for (int i = n; i; i--) {            for (int j = K - 1; j; j--) {                if (i + j <= n) {                    dp[0][i&Q][j] = sum[i+j-1] - sum[i-1] + max(dp[1][(i+j)&Q][j], dp[1][(i+j+1)&Q][j+1] + sum[i+j] - sum[i+j-1]);                    dp[1][i&Q][j] = sum[i-1] - sum[i+j-1] + min(dp[0][(i+j)&Q][j], dp[0][(i+j+1)&Q][j+1] - sum[i+j] + sum[i+j-1]);                    continue;                }                if (i + j - 1 <= n) {                    dp[0][i&Q][j] = dp[1][(i+j)&Q][j] + sum[i+j-1] - sum[i-1];                    dp[1][i&Q][j] = dp[0][(i+j)&Q][j] - sum[i+j-1] + sum[i-1];                }            }        }        printf("%d\n", dp[0][1][1]);    }}
    

题意

题解

代码

题意

给定一个$n$个节点的树，每个点有一个点权$p_i$。选定两个节点$S$和$T$，使得【$p_T-p_S-$路径上的边权】最大，求这个最大值。

题解

树形$DP$。

考虑将$S$到$T$的路径拆成两部分即可。

代码

#include 
    
     using namespace std;typedef long long ll;typedef pair
     
       pii;const int N = 1e5+9;const int INF = 0x3f3f3f3f;int T, n, p[N];vector
      
        g[N];ll res,dp[2][N];inline int read() {    int s = 1, x = 0; char ch = getchar();    while (ch < '0' || ch > '9') {if (ch == '-') s = -1; ch = getchar();}    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}    return s * x;}inline void dfs(int u, int fa) {    dp[0][u] = dp[1][u] = p[u];    for (auto e : g[u]) {        int v = e.first, w = e.second;        if (v != fa) {            dfs(v, u);            dp[0][u] = max(dp[0][u], dp[0][v] - w);            dp[1][u] = min(dp[1][u], dp[1][v] + w);        }    }    res = max(res, dp[0][u] - dp[1][u]);}int main() {    T = read();    while (T--) {        memset(p, 0, sizeof(p));        n = read();        for (int i = 1; i <= n; i++) p[i] = read();        for (int i = 1; i <= n; i++) g[i].clear();        for (int i = 1; i < n; i++) {            int x = read(), y = read(), z = read();            g[x].push_back( make_pair(y, z) );            g[y].push_back( make_pair(x, z) );        }        res = 0; dfs(1, 0);        printf("%lld\n", res);    }}
      
     
    

题意

题解

$DFS$。

代码

题意

题解

代码

题意

题解

代码

题意

给定$n$堆数组成一个圈，每堆数有$a_i$和$b_i$两个参数。选一个堆数开始按顺序取，每次加上$a_i-b_i$直到和小于$0$停止。要求取数的$a_i$之和最大，求应该从哪一堆开始取。

题解

尺取法。

先将$n$堆数重复成$2n$堆数变成环，考虑我们只需要尺取$n$堆数。当$[i,j]$不满足时，即$\sum_{k=i}^{j}{a_k-b_k}< 0$，上式对$[i,j]$内的$i$都成立，因此我们只需要把$i$移动到$j+1$即可。时间复杂度是线性的。

代码

#include 
    
     using namespace std;const int N = 2e6 + 9;int n, a[N], b[N], c[N];inline int read() {    int s = 1, x = 0; char ch = getchar();    while (ch < '0' || ch > '9') {if (ch == '-') s = -1; ch = getchar();}    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}    return s * x;}int main() {    while (~scanf("%d", &n)) {        for (int i = 0; i < n; i++) a[i] = read(), a[i + n] = a[i];        for (int i = 0; i < n; i++) b[i] = read(), b[i + n] = b[i];        for (int i = 0; i < n << 1; i++) c[i] = a[i] - b[i];        int cur = 0, sum = 0, SUM = 0, res = 0;        for (int i = 0, j = 0; j < n << 1; j++) {            if (cur + c[j] < 0) {                sum += a[j];                if (sum > SUM) SUM = sum, res = i;                cur = sum = 0, i = j + 1;            }             else                 cur += c[j], sum += a[j];            if (j - i == n - 1 && sum > SUM) {                SUM = sum, res = i;                break;            }        }        printf("%d\n", res);    }    return 0;}