2023牛客寒假算法基础集训营6 (B 思维+二分)(D 字符串匹配dp)(E 生成树+思维)(I 思维+bfs)
题目大意：
给定一个长度为n的数组a，有q次操作。
- 修改：数组末尾增加一个数x
- 查询：有多少个i(i>x)，满足a\(_i\)是a\(_x\)的倍数
解题思路：
对于每个数我们考虑其所有因子，比如数6的因子有1,2,3,6，那么对于1,2,3,6,来说6就是他们的倍数，所以我们定义一个vector<int> pos[N]表示数x的倍数出现的位置，我们每次分解数x的因子为v，然后:pos[v].push_back(i),表示v的倍数出现在位置i
举个例子：a[] =
通过分解他们的因子最终我们会得到如下的一个表
| pos |
id |
| pos\(_1\) |
1、2、3、4 |
| pos\(_2\) |
1、2、4 |
| pos\(_3\) |
1、3、4 |
| pos\(_6\) |
1、4 |
当我们需要查询3的倍数的时候，也就是查询[3+1,n]这个区间内为3的倍数的数字，所以我们只需要对pos[3]进行upper_bound求出[1,3]这个区间的长度，然后用pos[3].size()减去这个长度就是剩余i>3的a\(_i\)为a\(_3\)的倍数的个数了
同时我们因为要对所有数都进行一次拆分因子，所以我们可以通过预处理将数据范围内的所有数的因子提前处理出来(O(nlogn))存在fac[]中
代码实现：
代码
# include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
vector<int> fac[N];
vector<int> pos[N];
int main(){
//处理因子
for(int i = 1;i < N;++i){
for(int j = i;j<N;j+=i){
fac[j].push_back(i);
}
}
int n,q;
cin>>n>>q;
vector<int> a(n+1);
for(int i = 1;i <= n;++i){
cin>>a[i];
for(auto v:fac[a[i]]) pos[v].push_back(i);
}
while(q--){
int op,x;
cin>>op>>x;
if(op == 1){
n++;
a.push_back(x);
for(auto v:fac[x]) pos[v].push_back(n);
}
else{
int val = a[x];
//在pos数组中查询[1,x]的个数
int p = (upper_bound(pos[val].begin(),pos[val].end(),x)-pos[val].begin());
//总的减去不要的
int ans = pos[val].size()-p;
cout<<ans<<endl;
}
}
return 0;
}
题目大意：
给定一个S串和一个T串(T = "udu"),问如果只修改S串中的一个字母，如何修改能够使得T字串出现的次数最少。
解题思路
我们考虑如果对第i为进行修改后，[1,i-1]和[i+1,n]这两段序列出现怎么样的情况才会产生udu子序列
| [1,i-1] |
[i+1,n] |
| 空序列 |
udu |
| u |
du |
| ud |
u |
| udu |
空序列 |
只有如下的四种情况会产生udu子序列，所以实际上我们可以考虑一个经典dp
定义f[ i ][ j ]表示对于S串的前i个字符匹配到了T串的第j个字符的个数
这样我们就可以得到了对于[1,i-1]中四种可能的个数
而对于[i+1,n]我们可以先翻转S串再进行匹配，最终得到两个dp数组，dpz,dpf
对于每一位，我们只需要将对应的情况相乘再相加就表示修改这一位所能够产生的udu子序列个数
代码实现
代码
# include<bits/stdc++.h>
using namespace std;
# define int long long
const int N = 2e5+10;
string udu = "*udu";
int dpz[N][4],dpf[N][4];
int n;
string s;
int dp[N];
void work(int dp[][4]){
dp[0][0] = 1;
for(int i = 1;i <= n;++i){
dp[i][0] = 1;
for(int j = 1;j <= 3;++j){
dp[i][j] = dp[i-1][j];
if(s[i] == udu[j]) dp[i][j] += dp[i-1][j-1];
}
}
}
signed main(){
cin>>s;
n = s.size();
s = '?'+s;
work(dpz);
reverse(s.begin()+1,s.end());
work(dpf);
int now = 1e18,ans = 0;
for(int i = 1;i <= n;++i){
dp[i] += dpz[i-1][0]*dpf[n-i][3];
dp[i] += dpz[i-1][1]*dpf[n-i][2];
dp[i] += dpz[i-1][2]*dpf[n-i][1];
dp[i] += dpz[i-1][3]*dpf[n-i][0];
if(dp[i]<now){
now = dp[i];
ans = i;
}
}
reverse(s.begin()+1,s.end());
for(int i = 1;i < ans;++i){
cout<<s[i];
}
cout<<'z';
for(int i = ans+1;i <= n;++i){
cout<<s[i];
}
return 0;
}
题目大意
给定一个有n个节点的完全图，编号从1到n，对于任意两个节点i,j，如果abs(i-j)<=k,那么它们之间有一条边权为lcm(i,j)的边，否则有一条gcd(i,j)的边。
求这个图的最小生成树。
解题思路
对于[k+2,n]的节点，我们可以考虑直接和1连，因为gcd(1,i)=1，此时的边权都是最小的
而对于[2,k+1]的节点，有两种可能，第一种和1连一条lcm(1,i) = i的边，此时的lcm是最小的，否则考虑在区间[i+k+1,n]是否存在一个点gcd(i,j) == 1或者gcd(i,j)<i，因为在2e5的数据范围内，任意两个质数的距离不会超过1000，所以,这个遍历的过程不会太长，可以暴力的遍历
代码实现
代码
# include<bits/stdc++.h>
using namespace std;
# define int long long
signed main(){
int n,k;
cin>>n>>k;
//[k+2,n]都连1,gcd==1最小
int ans= n-min(n,k+1);
//[2,k+1]考虑是否有gcd(i,x) == 1，x在[i+1,i+k-1]中，是质数
for(int i = 2;i <= min(k+1,n);++i){
int now = i;
for(int j = i+k+1;j<=n;++j){
now = min(now,(int)__gcd(i,j));
if(now == 1) break;
}
ans += now;
}
cout<<ans<<endl;
return 0;
}
题目大意
给定n个点，阿宁最初处于点1,她的目标是点n，她拥有一个技能，她可以让一个边的边权为1，同时摧毁另一条边。
问她到达点n的最小边权之和。
解题思路
我们考虑阿宁可以以如下的思路使用技能：
对于一个图1\(\rightarrow\) 2 \(\rightarrow\) 3 \(\rightarrow\) 4 \(\rightarrow\) 5
当阿宁通过边1 \(\rightarrow\) 2,到达了点2后，她可以使用技能将边2 \(\rightarrow\) 3的边权变为1，同时摧毁已经经过的边1 \(\rightarrow\) 2。
以这样的思路不断往下走，最后她可以以w[1 \(\rightarrow\) 2]+(1*4)的代价最终到达点5
所以实际上处理最开始的一号点，其他到达终点的边的边权都可以是1，我们只需要考虑最初的边权也能否这样变化。
如果想要第一条边的边权也变成1，那么就必须要有多余的边存在。
我们可以考虑一个dix数组表示到达点i的最小边权和，经过bfs之后最终我们会到达点n
之后我们可以判断：
- dix[n] == m:此时每一条边都是必须经过的，所以第一条边的边权不能变成1，所以ans = dix[n]-1+w[1]
- dix[n] != m:此时存在多余的边，所以可以将第一条边的边权变为1，ans = dix[n]
代码实现
代码
#include<bits/stdc++.h>
using namespace std;
# define int long long
const int N= 2e5+ 10,inf = 1e18;
vector<int> e[N];
int vis[N];
int dix[N];
signed main(){
int n,m;
cin>>n>>m;
for(int i = 1;i <= n;++i) dix[i] = inf;
int res = 0;
for(int i = 1;i <= m;++i){
int a,b,w;
cin>>a>>b>>w;
e[a].push_back(b);
e[b].push_back(a);
if(a == 1||b == 1) res = w;
}
queue<int> q;
q.push(1);
dix[1] = 0;
vis[1] = 1;
while(q.size()){
auto a = q.front();
q.pop();
for(auto v:e[a]){
if(vis[v]) continue;
dix[v] = dix[a]+1;
vis[v] = 1;
q.push(v);
}
}
if(dix[n] == m){
int ans =dix[n]-1+res;
cout<<ans<<endl;
}
else{
cout<<dix[n]<<endl;
}
return 0;
}