牛客练习赛#70 题解

¶A.重新排列 #尺取法

¶题目链接

¶题意

给定字符串，你需要将该字符串中的某个子串重新排列，使得该子串变为"puleyaknoi"。现要你求出最短的这类子串的长度。

¶分析

因为子串要求连续性，“连续性”和“多个满足条件中选择最优的”，可以联想到尺取法。

怎么判断是否满足条件？由于子串能够重新排列，我们只需要统计相应区间中模式串对应字符的数量即可。

#include <string>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <stack>
#include <queue>
#include <map>
#include <vector>
#include <deque>
#include <cmath>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long ll;
string t = {"puleyaknoi"}, tmp;
int vis[300];
int q, cnt = 0;
void Cal(char cur){
    for (int j = 0; j < t.length(); j++){
        if(cur == t[j]){
            if(vis[cur] == 0) cnt++;
            vis[cur]++;
            break;
        }
    }
}
int main(){
    scanf("%d", &q);
    while(q--){
        cin >> tmp;
        int len = tmp.length(), hi = -1;
        int minlen = 0x3f3f3f3f;
        memset(vis, 0, sizeof(vis));
        cnt = 0;
        for (int lo = 0; lo <= len - t.length(); lo++){
            while(hi < len && cnt < t.length()){
                hi++;
                Cal(tmp[hi]); //计入新元素
            }
            if(hi >= len) break; 
            if (cnt >= (int)t.length() && hi - lo + 1 < minlen) //更新长度
                minlen = hi - lo + 1;
            if(vis[tmp[lo]] >= 1){ //排除末元素
                vis[tmp[lo]]--;
                if(vis[tmp[lo]] == 0) cnt--;
            }
        }
        if(minlen < 0x3f3f3f3f) printf("%d\n", minlen);
        else printf("-1\n");
    }
    return 0;
}

¶B.拼凑 #线性DP

¶题目链接

¶题意

给定字符串，你需要从该字符串中找出一子序列，使得该子序列为"puleyaknoi"。现要你求出最短的这类子串的长度。

¶分析

因为子序列是原串中一部分字符（不一定是连续的）按原有次序排列而得的序列。碰到“子序列”相关问题，往往从DP方向考虑。

定义$dp[i][j]$，$i$表示主串的下标$i$，$j$表示模式串下标$j$，当$j==模式串长度$时，$dp$数组记录最短子序列长度。其转移方程在代码中有注释。

#include <string>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <stack>
#include <queue>
#include <map>
#include <vector>
#include <deque>
#include <cmath>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
string s = {"puleyaknoi"}, tmp;
int dp[MAXN][12], q;
int main(){
    scanf("%d", &q);
    while(q--){
        cin >> tmp;
        int n = tmp.length(), m = s.length();
        memset(dp, 0x3f, sizeof(dp));
        for (int i = 1; i <= n; i++) dp[i][0] = 0;
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= min(i, m); j++){
                //判断是否能从主串起点i-1转移过来
                dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1);
                if(tmp[i - 1] == s[j - 1]) //说明当前字符匹配
                    dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1);
                    //判断是否能从主串起点i-1、模式串起点j-1转移过来
            }
        }
        int ans = 0x3f3f3f3f;
        for (int i = m; i <= n; i++) ans = min(ans, dp[i][m]); 
        printf("%d\n", ans < 0x3f3f3f3f ? ans : -1);
    }
}

¶C.Mu函数 #质因数分解 #模拟 #打表观察性质

¶题目链接

¶题意

定义函数$mu(x)$，满足：

$$mu(x) = \begin{cases} 1 &,x = 1 \\ （-1）^a &,x无平方因数且x=\prod_{i=1}^a{p_i}，p_i为质数）\\ 0 &,x含大于1的平方数因数 \end{cases}$$

设函数$f(x)=x+mu(x)$，给定$n,k$，求$f(n)$的$k（k\leq10^{18}）$次迭代

¶分析

这题Wa了十多发，看到好多题解需要莫比乌斯反演(?)，没学过。

参考了@为神的思路，我们要解决几个问题：

1. 如何判断$x$是否存在平方数因数？直接枚举即可。
2. 如何对$x$质因数分解？先用线性筛，记录每个数是否为质数的同时，给每一个合数存下相应的最小质因子。接下来对$x$不断地用其最小质因子去除，直到商为质数即可统计出原来的$x$有多少个质因子。
3. 如何处理$10^{18}$的$k$？如此数据规模，暗示我们要从中找出算法提前终止的条件与有规律性的结果。
   • 如果$x$满足$mu(x)$的条件三，说明接下来的增量都为$0$，$f(x)$始终不变，直接退出；
   • 如果$x$满足$mu(x)$的条件二，实际上就是对$x$自减或者自增。我们通过小范围打表发现，到达一定的$k$时，$mu(x)$会在$-1$和$+1$之间周期变化，也就说上一增量和下一增量之和就是$0$，由此我们通过周期规律，预先知道未来的结果。

#include <string>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <stack>
#include <queue>
#include <map>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 1e7 + 5;
int q, n, prim[MAXN], notPrim[MAXN]; //notPrim[x]存储x的最小质因子
ll k;
void getPrime(){
    int cnt = 0;
    for(ll i = 2; i <= (ll)1e7+3; i++){
        if(notPrim[i] == 0) //i并非合数 即 i是质数
            prim[++cnt] = i;
        for(int j = 1; i * (ll)prim[j] <= (ll)1e7+3 && j <= cnt; j++){
            notPrim[i * prim[j]] = prim[j];
            if(i % prim[j] == 0) break;
        }
    }
}
int res;
bool Judge(int x){
    res = 0;
    for(int i = 2; i * i <= x; i++)
        if(x % (i * i) == 0) return false; //满足条件三
    while(notPrim[x] > 0){ //说明x此时仍不是质数
        x = x / notPrim[x];
        res++;
    }
    if(x != 1) res++;
    return true;
}
int main(){
    scanf("%d", &q);
    getPrime();
    while(q--){
        scanf("%d%lld", &n, &k);
        int last = 0, diff = 0;
        while(k--){
            last = diff;
            if(Judge(n)){//满足条件二
                diff = 1 - 2 * (res % 2);
                n += diff;
                if(diff + last == 0){
                    if(k % 2 != 0) n += last;
                    break;
                }
            }
            else break; //满足条件三
        }
        printf("%d\n", n);
    }
}

¶D.数树 #树的性质 #STL

¶题目链接

¶题意

现有三种操作：1. 添加一条边；2. 切断一条边；3.询问现有多少个规模不为1的树。

操作中有可能连出重边，或者切断根本不存在的边，可以忽略。

¶分析

由于每一棵树满足"边数+1=节点数"，我们可以用总边数-节点数，便能求出森林中树的数量。但注意，这些树都是由度数不为1的节点组成的。另外，由于会出现重边，或者删除不存在的边，我们需要用哈希表去记录边的数量。又因为节点编号达到$10^8$，需要用到$map$和$pair$来维护与记录。

#include <string>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <stack>
#include <queue>
#include <map>
#include <vector>
#include <deque>
#include <cmath>
#include <algorithm>
#include <unordered_map>
#include <set>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 5;
map< pair<int, int>, int> Evis;
map<int, int> deg;
int ans = 0, n, cnt, tot;
int main() {
    scanf("%d", &n);
    while (n--) {
        int opt, u, v;
        scanf("%d", &opt);
        if (opt == 1) {
            scanf("%d%d", &u, &v);
            if(Evis.count({u, v})) continue; //忽略操作
            Evis[{u, v}] = Evis[{v, u}] = 1;
            cnt++; //边数+1
            deg[u]++; //度数+1
            deg[v]++; 
            if(deg[u] == 1) tot++; //度数不为1的顶点数+1
            if(deg[v] == 1) tot++;
        }
        else if (opt == 2) {
            scanf("%d%d", &u, &v);
            if(!Evis.count({u, v})) continue; //忽略操作
            Evis.erase({u, v});
            Evis.erase({v, u});
            cnt--; //边数-1
            deg[u]--; //度数-1
            deg[v]--;
            if(deg[u] == 0) tot--; 
            if(deg[v] == 0) tot--; //tot始终记录度数不为1的顶点数
        }
        else if (opt == 3) {
            printf("%d\n", tot - cnt); //不成一个点的树的条数 = 度数不为1的顶点数 - 边数
        }
    }
}