【2024暑假】-普及6 讲解

zrl123456 · 2024-07-13 13:52:38 · 题解

P8649 [蓝桥杯 2017 省 B] k 倍区间

题目考察：前缀和，桶。
题目简述：
给你一个序列 \{a_n\}，求：

\sum_{i=1}^n\sum_{j=i}^n[(\sum_{x=i}^ja_x)\bmod k=0]

数据范围：

1\le n,k,a_i\le 10^5
设 sum_i=\sum_{j=1}^ia_j，由于 (sum_r-sum_{l-1})\bmod k=0，所以 sum_r\equiv sum_{l-1}\pmod k，那么我们开一个桶，每次将 t_{sum_i\bmod k} 加 1，累加答案即可。

时间复杂度为 \Theta(n)。
代码：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define inl inline
#define reg register
#define rep(i,x,y) for(reg int i=x;i<=y;++i)
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int N=1e5+5;
int n,k,a[N],sum[N],mp[N],ans;
signed main(){
    fst;
    cin>>n>>k;
    rep(i,1,n) cin>>a[i];
    rep(i,1,n) sum[i]=(sum[i-1]+a[i])%k;
    ++mp[0];
    rep(i,1,n) ans+=mp[sum[i]]++;
    cout<<ans;
    return 0;
}

P8247 皇室战争

题目考察：斜率。
题目简述：
有一位战士，他有一些箭，他要射死一些敌人。他的箭能穿透，求他最少要射几次。
数据范围：

1\le n\times m\le 10^6
我们要求战士到敌人的斜率，斜率相同的就是能一箭射死的。
由于斜率要求浮点数，浮点数的精度可能会出问题，我们需要像一种其他的方法。
如果 \displaystyle\frac{a}{b}=\frac{c}{d}，则 a\div \gcd(a,b)=c\div\gcd(c,d),b\div\gcd(a,b)=d\div\gcd(c,d)，那么我们将其除以 |\gcd(a,b)| 即可。

时间复杂度为 \Theta(nm\log_2(nm))。
代码：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define inl inline
#define reg register
#define rep(i,x,y) for(reg int i=x;i<=y;++i)
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define pii pair<int,int>
#define prr make_pair
using namespace std;
const int N=1e6+5;
int n,m,sx,sy,k;
vector<char>g[N];
char ch;
map<pii,bool>mp;
signed main(){
    fst;
    cin>>n>>m;
    rep(i,1,n) g[i].pb(' ');
    rep(i,1,n)
        rep(j,1,m){
            cin>>ch;
            g[i].pb(ch);
        }
    rep(i,1,n)
        rep(j,1,m)
            if(g[i][j]=='S'){
                sx=i;
                sy=j;
            }
    rep(i,1,n)
        rep(j,1,m)
            if(g[i][j]=='K'){
                k=abs(__gcd(i-sx,j-sy));
                mp[prr((i-sx)/k,(j-sy)/k)]=1;
            }
    cout<<mp.size();
    return 0;
}

P1131 [ZJOI2007] 时态同步

题目考察：树，dp，dfs。
题目简述：
给你一颗以 s 为根的树，有一种操作：

选择一条边，将其边权增加 1。

求使 s 节点到所有叶子节点的距离都相等的操作数。
数据范围：

1\le n\le 5\times 10^5
首先我们肯定可以通过一遍 dfs 得出以任意一点为根的子树的最大的 s 节点到子树内叶子节点的距离（mx_u），那么如果 mx_u<mx_s，说明在这个点和其父节点的这条边上操作 mx_s-mx_u 次是最合适的，这样我们再来一遍 dfs 就可以了。

时间复杂度为 \Theta(n)。
代码：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define inl inline
#define reg register
#define rep(i,x,y) for(reg int i=x;i<=y;++i)
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define pii pair<int,int>
#define prr make_pair
#define at(v,x) for(reg auto v:x)
using namespace std;
const int N=5e5+5;
struct node{
    int v,w;
    inl node(){
        v=w=0;
    }
    inl node(int v,int w):v(v),w(w){}
};
vector<node>g[N];
int n,s,u,v,w,mx[N],c[N],ans;
bool vis[N];
inl void dfs(int u,int t){
    vis[u]=1;
    mx[u]=t;
    at(x,g[u])
        if(!vis[x.v]){
            dfs(x.v,t+x.w);
            mx[u]=max(mx[u],mx[x.v]);
        }
    vis[u]=0;
}
inl void dfs2(int u){
    vis[u]=1;
    at(x,g[u])
        if(!vis[x.v]){
            mx[x.v]+=c[u];
            c[x.v]+=c[u];
        }
    c[u]=0;
    at(x,g[u])
        if(!vis[x.v]){
            c[x.v]+=mx[s]-mx[x.v];
            ans+=mx[s]-mx[x.v];
            mx[x.v]=mx[s];
            dfs2(x.v);
        }
    vis[u]=0;
}
signed main(){
    fst;
    cin>>n>>s;
    rep(i,2,n){
        cin>>u>>v>>w;
        g[u].pb(node(v,w));
        g[v].pb(node(u,w));
    }
    dfs(s,0);
    dfs2(s);
    cout<<ans;
    return 0;
}

P8270 [USACO22OPEN] Subset Equality S

题目考察：dp，状态压缩，字符串。
题目简述：
给你两个字符串 s,t，q 次询问，每次给定一个字符串 op，求若 s 和 t 只包含 op 里面的字符，s 和 t 是否相等。
数据范围：

1\le |s|,|t|,q\le 10^5
------------ 这个题有一个结论：若 $|op|\ge 3$ 且他的任意子序列的方案是合法的，则他就是合法的。下面我们来证明：两个字符串： $$\text{abc},\text{acb}$$ 则 $\text{bc},\text{cb}$ 方案不是合法的。所以我们暴力跑出 $|op|\le 2$ 的合法性，然后进行状压 dp 即可。

时间复杂度为 \Theta(r^2(n+m)+2^rr+q)。
代码：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define inl inline
#define reg register
#define rep(i,x,y) for(reg int i=x;i<=y;++i)
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define pii pair<int,int>
#define prr make_pair
#define at(v,x) for(reg auto v:x)
using namespace std;
const int N=25,M=(1<<18)+5;
string s,t,tmps,tmpt,op;
int q,n,m,sum[N],tmp;
bool dp[M];
signed main(){
    fst;
    cin>>s>>t>>q;
    n=s.size();
    m=t.size();
    s=' '+s;
    t=' '+t;
    rep(i,1,n) ++sum[s[i]-'a'+1];
    rep(i,1,m) --sum[t[i]-'a'+1];
    rep(i,1,18) dp[1ll<<i-1]=!sum[i];
    rep(i,1,18)
        rep(j,i+1,18){
            tmps=tmpt="";
            rep(k,1,n)
                if(s[k]==i+'a'-1||s[k]==j+'a'-1) tmps+=s[k];
            rep(k,1,m)
                if(t[k]==i+'a'-1||t[k]==j+'a'-1) tmpt+=t[k];
            dp[1ll<<i-1|1ll<<j-1]=tmps==tmpt;
        }
    rep(i,0,(1ll<<18)-1)
        if(__builtin_popcount(i)>=3){
            dp[i]=1;
            rep(j,1,18)
                if(i>>j-1&1) dp[i]&=dp[i&~(1ll<<j-1)];
        }
    rep(i,1,q){
        tmp=0;
        cin>>op;
        at(ch,op) tmp|=1ll<<ch-'a';
        if(dp[tmp]) cout<<"Y";
        else cout<<"N";
    }
    return 0;
}

P6280 [USACO20OPEN] Exercise G 讲解

P6280 [USACO20OPEN] Exercise G

题目考察：数学，数论，素数筛，dp。
题目简述：
给你一个 n，求满足下列条件的数 k 的和对 m 取模的结果：

有一个排列 \{a_n\}，k 个新排列 \{b_n\}，b_{0,i}=i，使 b_{l,a_i}=b_{l-1,i}，最后使 \forall i\in[1,n],b_{0,i}=b_{k,i}。

数据范围：

1\le n\le 10^4
1\le m\le 10^9+7
m\in\text{prime}
假设相邻两个排列之间有一些置换群，例如 \{1,2,3,4,5\} 和 \{2,3,1,5,4\}，1,2,3 和 4,5 就是置换群，则设置换群的大小为 siz_i，那么会进行 \text{lcm}_{i=1}^{size}siz_i 轮，则：
\displaystyle\sum_{i=1}^{size}siz_i\le n
\text{lcm}_{i=1}^{size}siz_i=k

由于 \text{lcm} 只与质数及其幂次有关，所以我们先将这 cnt 个质数筛出来（cnt\approx \frac{n}{\log_2n}）。
现在我们就可以进行 dp，设 dp_{i,j} 为进行到第 i 个质数，和已有了 j 的和，易得状态转移方程：

dp_{i,j}=\sum_{k=1}^{\lfloor\log_{prime_i}n\rfloor}dp_{i-1,j-prime_i^k}\times prime_i^k

同样的我们可以压掉第一维。

时间复杂度为 \Theta(n^2)。
代码：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define inl inline
#define reg register
#define rep(i,x,y) for(reg int i=x;i<=y;++i)
#define per(i,x,y) for(reg int i=x;i>=y;--i)
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define pii pair<int,int>
#define prr make_pair
#define at(v,x) for(reg auto v:x)
using namespace std;
const int N=1e4+5;
int n,m,cnt,prime[N],f[N],ans,tmp;
bool isprime[N];
inl void init(int x){
    rep(i,2,x)
        if(!isprime[i]){
            prime[++cnt]=i;
            rep(j,2,x/i) isprime[i*j]=1;
        }
}
signed main(){
    fst;
    cin>>n>>m;
    init(n);
    f[0]=1;
    rep(i,1,cnt)
        per(j,n,prime[i]){
            tmp=prime[i];
            while(tmp<=j){
                (f[j]+=f[j-tmp]*tmp%m)%=m;
                tmp*=prime[i];
            }
        }
    rep(j,0,n) (ans+=f[j])%=m;
    cout<<ans;
    return 0;
}