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
", minlen);
else printf("-1
");
}
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
", ans < 0x3f3f3f3f ? ans : -1);
}
}
C.Mu函数 #质因数分解 #模拟 #打表观察性质
题目链接
题意
定义函数(mu(x))，满足：
[mu(x) = egin{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（kleq10^{18}）)次迭代
分析
这题Wa了十多发，看到好多题解需要莫比乌斯反演(?)，没学过。
参考了@为神的思路，我们要解决几个问题：
- 如何判断(x)是否存在平方数因数？直接枚举即可。
- 如何对(x)质因数分解？先用线性筛，记录每个数是否为质数的同时，给每一个合数存下相应的最小质因子。接下来对(x)不断地用其最小质因子去除，直到商为质数即可统计出原来的(x)有多少个质因子。
- 如何处理(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);
}
}
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
", tot - cnt); //不成一个点的树的条数 = 度数不为1的顶点数 - 边数
}
}
}