ABC186E Throne
有 \(n\) 个圆形排列的椅子，一开始你在 \(s+1\) 上，每次可以向右移动 \(k\) 个位置，求移动到 \(1\) 的最小步数，或报告无解。
\(2\le n,k\le 10^9\)
很容易想到构造方程：
\[s+qk\equiv 0\pmod n \]\[q\equiv (n-s)k^{-1}\pmod n \]直接 exgcd 求逆元，算出在 \([1,n-1]\) 范围内的解即可。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
void exgcd(int a,int b,int &inv,int &x,int &y){
if(!b) inv=a,x=1,y=0;
else exgcd(b,a%b,inv,y,x), y-=(a/b)*x;
}
int T;
signed main(){
cin>>T;
while(T--){
int n,s,k,inv,x,y;
cin>>n>>s>>k;
int gcd=__gcd(__gcd(n,s),k);
n/=gcd;s/=gcd;k/=gcd;
exgcd(k,n,inv,x,y);
if(inv!=1){
cout<<-1<<'\n';
}else{
inv=(x+n)%n;
cout<<(n-s)*inv%n<<'\n';
}
}
return 000;
}
ABC186F Rook on Grid
有一个 \(n\times m\) 的网格，其中有 \(k\) 个障碍 \((x_i,y_i)\)，有个猴子，它每走一步可以沿着一个方向走任意格，不能穿过障碍，求猴子在两步及以内可以到达的格子数。
\(n,m,k\le 2\times 10^5\)
设 \(X_i\) 为第 \(i\) 列从上到下可以到达的最大坐标，\(Y_i\) 为第 \(i\) 行从左到右可以到达的最大坐标。
先处理出从左往右可以到达的格子数 \(\sum Y_i\)，然后考虑从上到下且不重复的格子，若对于 \(j\in[1,X_i],Y_j<i\)，则将格子 \((i,j)\) 加入答案，这个限制直接用树状数组二维数点维护即可。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+34;
int n,m,k;
int x[maxn],y[maxn];
int ans=0;
int tree[maxn];
vector<int>query[maxn];
int lowbit(int x){return x&-x;}
void add(int pos,int c){pos++;for(;pos<=200030;pos+=lowbit(pos)) tree[pos]+=c;}
int q(int pos){pos++;int res=0;for(;pos;pos-=lowbit(pos)) res+=tree[pos];return res;}
signed main(){
cin>>n>>m>>k;
// assert(m<=n);
for(int i=1;i<=max(n,m);i++) x[i]=n+1;
for(int i=1;i<=max(n,m);i++) y[i]=m+1;
for(int i=1,X,Y;i<=k;i++){
cin>>X>>Y;
x[Y]=min(x[Y],X);
y[X]=min(y[X],Y);
}
for(int i=1;i<=x[1]-1;i++) ans+=y[i]-1, query[y[i]].emplace_back(i);
for(int i=x[1];i<=n;i++) query[1].emplace_back(i);
for(int i=1;i<y[1];i++){
for(int j:query[i]) add(j,1);
ans+=q(x[i]-1);
}
cout<<ans;
return 0;
}
ABC185E Sequence Matching
给一棵树，\(Q\) 次操作：
- 对于编号为 \(x\) 的边，和其一个端点 \(u\)，将 \(u\) 不经过 \(E_x=(u,v)\) 就能到达的点的分数加上 \(k\)。
求操作完后每个点的分数。
\(n\le 2\times 10^5\)
考虑进行标记（差分）。钦定 1 为根，处理出每个点的父亲，则对于每个询问，若 \(u=fa_v\) 则将 \(u\) 子树外的点加上 \(k\)，这等价于将全树的分数加上 \(k\) 再将 \(v\) 子树内的点减掉 \(k\)；否则，直接将 \(u\) 子树内的点加 \(k\) 即可。
时间复杂度 \(O(n+Q)\)。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+3;
vector<int>e[maxn];
int tag[maxn],f[maxn],n,q;
struct{
int u,v;
}E[maxn];
void dfs(int u,int fa){
f[u]=fa;
for(int v:e[u]){
if(v!=fa) dfs(v,u);
}
}
void dfs1(int u,int fa){
for(int v:e[u]){
if(v!=fa){
tag[v]+=tag[u];
dfs1(v,u);
}
}
}
signed main(){
cin>>n;
for(int i=1,u,v;i<n;i++){
cin>>u>>v;
E[i]={u,v};
e[u].emplace_back(v);
e[v].emplace_back(u);
}
dfs(1,0);
cin>>q;
while(q--){
int t,id,x,u,v;
cin>>t>>id>>x;
if(t==1){
u=E[id].u,v=E[id].v;
}else{
u=E[id].v,v=E[id].u;
}
if(u==f[v]){
tag[1]+=x;
tag[v]-=x;
}else{
tag[u]+=x;
}
}
dfs1(1,0);
for(int i=1;i<=n;i++){
cout<<tag[i]<<'\n';
}
return 0;
}
ABC367F Rearrange Query
给你两个序列 \(a,b\)，\(q\) 次询问 \(a[l,r],b[L,R]\) 之间每个元素的个数是否相等。
\(a_i,b_i,l,r,L,R\le n\le 2\times 10^5\)
朴素的思路是 \(n^2\) 的，就是考虑开个 \(n^2\) 的桶，对于每个元素进行判断，但是显然爆炸，而且优化不了。
所以只能舍弃正确性，保证复杂度，将每一个数映射到一个随机数（这里将 \(x\) 映射到 \(h^x\)）上，由于问题的必要条件是两个的和相等，而因为随机，所有和相等而不满足的概率极小，可以保证正确性。使用乘法，异或来判断也可以。
时间复杂度 \(O(n\log n)\)。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5+3;
int a1[maxn],a2[maxn],b1[maxn],b2[maxn];
int l,r,L,R,n,q;
const int mod1=1000000241;
const int mod2=1000000931;
int ha1(int x){
int ret=1,de=41;
for(;x;x>>=1,de=de*de%mod1) if(x&1) ret=ret*de%mod1;
return ret;
}
int ha2(int x){
int ret=1,de=37;
for(;x;x>>=1,de=de*de%mod2) if(x&1) ret=ret*de%mod2;
return ret;
}
signed main(){
cin>>n>>q;
for(int i=1,x;i<=n;i++){
cin>>x;
a1[i]=(a1[i-1]+ha1(x))%mod1;
// a2[i]=(a2[i-1]+ha2(x))%mod2;
}
for(int i=1,x;i<=n;i++){
cin>>x;
b1[i]=(b1[i-1]+ha1(x))%mod1;
// b2[i]=(b2[i-1]+ha2(x))%mod2;
}
while(q--){
cin>>l>>r>>L>>R;
if(R-L!=r-l){
cout<<"No\n";
continue;
}
int l1=(a1[r]-a1[l-1]+mod1)%mod1;
// int r1=(a2[r]-a2[l-1]+mod2)%mod2;
int l2=(b1[R]-b1[L-1]+mod1)%mod1;
// int r2=(b2[R]-b2[L-1]+mod2)%mod2;
if(l1==l2){
cout<<"Yes\n";
}else{
cout<<"No\n";
}
}
return 0;
}
// 单模数都能过
ABC365E Xor Sigma Problem
给你一个序列 \(a\)，求其每个子段的异或和的和。
\(n\le 2\times 10^5,a_i\le V\le 10^8\)
由于异或的可加性，求异或和可以用前缀和处理掉，设前缀数组为 \(b\)，则题目转化为求 \(\sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n} b_{j} \oplus b_{i-1}\)
加法和异或并不具有交换结合律，但是可以发现每次的 \(b_j\) 数量是递减的，而异或是按位运算，所以考虑拆位，每位开一个桶 \(t_x\) 记录二进制第 \(x\) 为为 \(1\) 的个数，对于一个 \(b_i\) 只有 \(b_j\) 在第 \(x\) 位上不同才有贡献，这样计算是 \(O(\log V)\) 的，同样从桶中删除一个 \(b\) 也是 log 的，所以总复杂度为 \(O(n\log V)\)。
最终的式子：
\[ans=\sum\limits_{i=1}^n\sum\limits_{j=1}^{\log_2 b_i+1}2^j f(i,j) \]\[f(i,j)=\begin{cases}n-i-t_j&b_{i}\And 2^j=1\\t_j&b_{i}\And 2^j=0 \end{cases} \]点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5+3;
int a[maxn],b[maxn];
int n;
int ton[64];
bitset<32>bit[maxn];
signed main(){
cin>>n;
bit[0]=0;
for(int i=1,x;i<=n;i++){
cin>>x;
a[i]=x;
b[i]=b[i-1]^x;
bit[i]=b[i];
for(int j=0;j<31;j++){
ton[j]+=bit[i][j];
}
}
int ans=0;
for(int i=1;i<n;i++){
for(int j=0;j<31;j++){
ton[j]-=bit[i][j];
}
for(int j=0;j<31;j++){
int cnt=bit[i-1][j]?n-i-ton[j]:ton[j];
ans+=(1ll<<j)*cnt;
}
}
cout<<ans;
return 0;
}
三倍经验：
P9236 [蓝桥杯 2023 省 A] 异或和之和
ABC371E I Hate Sigma Problems
设 \(f(i,j)\) 为 \([i,j]\) 内不同数字的个数，求 \(\sum\limits_{i=1}^n\sum\limits_{j=i}^n f(i,j)\)。
\(a_i\le n\le 2\times 10^5\)
设 \(g_i\) 为 \(i\) 位置前面第一个与 \(a_i\) 相同的位置，则每个 \(i\) 的贡献区间为 \([l_i,r_i](l_i\in[g_i,i],r_i\in[i,n])\)，其贡献为 \((i-g_i)(n-i+1)\)，时间复杂度 \(O(n)\)。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+3;
int n,ans;
int a[maxn],f[maxn];
vector<int>v[maxn];
signed main(){
cin>>n;
for(int i=1;i<=n;i++) v[i].emplace_back(0);
for(int i=1;i<=n;i++){
cin>>a[i];
f[i]=v[a[i]].back();
v[a[i]].emplace_back(i);
}
for(int i=1;i<=n;i++){
ans=ans+(i-f[i])*(n-i+1);
}
cout<<ans;
return 0;
}
ABC268E Chinese Restaurant (Three Star Version)
给你一个排列 \(p\)，求 \(\min\limits_{d=0}^{n-1}\sum\limits_{i=0}^{n-1} dis(i,p_{(i+d)\bmod n})\)。
\(n\le 2\times 10^5\)
考虑到对于一个 \(p_i\)，它离 \(i\) 的距离大概如图
由两段单调区间构成，分别单增和单减。我们可以统计初始态时上升与下降的个数之差 \(x\)，每次 \(d\to d+1\) 时就把初始 \(d=0\) 的和加上 \(x\)，再判断是否到达断点（相当于将贡献反向，原来 \(+1\) 的贡献在断点 \(-2\) 后就变为 \(-1\)），再而，\(n\) 为奇数时，\(dis_{\max}\) 有两个点 \(t,t+1\) 取到，所以在这两个点时，先是将 \(+1\to 0\)，再在 \(t+1\) 将 \(0\to -1\)，开一个桶记录每个 \(d\) 的 \(x\) 的增减即可，时间复杂度 \(O(n)\)，代码使用 \(O(n\log n)\) 的写法。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5+3;
int n,a[maxn],b[maxn],c[maxn],ad,de,sum,ans=0x3f3f3f3f3f3f3f3f;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
signed main(){
cin>>n;
if(n&1){
for(int i=0;i<n;i++){
cin>>a[i];
int dis=min(abs(a[i]-i),n-abs(a[i]-i));
int dit=min(abs(a[i]-(i+1)),n-abs(a[i]-(i+1)));
int pos1=a[i],pos2=(a[i]+n/2)%n,pos3=(a[i]+n/2+1)%n,dis1=pos1-i,dis2=pos2-i,dis3=pos3-i;
if(dis<dit) ad++;
else if(dis>dit) ad--;
if(i>pos1) dis1+=n;
if(i>pos2) dis2+=n;
if(i>pos3) dis3+=n;
q.push({dis1,2});
q.push({dis2,-1});
q.push({dis3,-1});
sum+=dis;
}
}else{
for(int i=0;i<n;i++){
cin>>a[i];
int dis=min(abs(a[i]-i),n-abs(a[i]-i));
int dit=min(abs(a[i]-(i+1)),n-abs(a[i]-(i+1)));
int pos1=a[i],pos2=(a[i]+n/2)%n,dis1=pos1-i,dis2=pos2-i;
if(dis<dit) ad++;
else ad--;
if(i>pos1) dis1+=n;
if(i>pos2) dis2+=n;
q.push({dis1,2});
q.push({dis2,-2});
sum+=dis;
}
}
while(!q.empty()&&!q.top().first) q.pop();
ans=sum;
for(int d=1;d<=n;d++){
sum+=ad;
while(!q.empty()&&q.top().first==d){
ad+=q.top().second;
q.pop();
}
ans=min(ans,sum);
}
cout<<ans;
return 0;
}
ABC374E Sensor Optimization Dilemma 2
唐氏 trick 题。
加工每个产品有 \(n\) 步，每步中可以选择机器 \(S_i\)，用 \(p_i\) 费用加工 \(a_i\) 个产品；或者选择机器 \(T_i\)，用 \(q_i\) 费用加工 \(b_i\) 个产品，求在总费用不超过 \(x\) 的情况下，求最大可加工的产品数。
\(n,a_i,b_i\le 100,p_i,q_i,x\le 10^7\)
显然可以二分。二分一个 \(t\) 表示产品数，枚举 \(S_i\) 的数量，进而可以算出 \(T_i\) 的数量，时间复杂度 \(O(xn\log xn)\)（AT 少爷机可过），但是考虑到 \(a_i,b_i\) 的范围很小，实际上我们是枚举 \(Cp_i+Dq_i\ge x\)，令 \(w=Cp_i+Dq_i-x\)，\(w\) 的循环节为 \(\gcd(a_i,b_i)\le 100\)，所以我们只要枚举 \(100\) 个 \(C/D\) 即可，时间复杂度 \(O(nT_{w}\log xn)\)，槽点是它 \(n\) 怎么开这么小，导致想了一会费用流
标签：le,const,int,long,ABC,maxn,杂题,dis From： https://www.cnblogs.com/DEV3937/p/18520279