本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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
P8270 [USACO22OPEN] Subset Equality S
题目考察：dp，状态压缩，字符串。
题目简述：
给你两个字符串 $s,t$，$q$ 次询问，每次给定一个字符串 $op$，求若 $s$ 和 $t$ 只包含 $op$ 里面的字符，$s$ 和 $t$ 是否相等。
数据范围：
- $1\le |s|,|t|,q\le 10^5$
- $1\le |op|\le r$（$r=18$）
- $\forall i\in[1,|s|],\forall j\in[1,|t|],\forall k\in[1,|op|],s_i,t_j,op_k$ 都是
a到r的字符。
这个题有一个结论：若 $|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\pprox \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;
}
鲁ICP备2025150228号