本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-09-24 14:36:09
T2 优美区间
区间问题，区间[l,r]都是ai的倍数，就是最小公倍数是a[i]
方法1.区间最小公倍数可以进行区间合并。$st$表可以解决。 然后再通过二分答案找到最大长度。 最后枚举最大长度，输出答案。时间复杂度$o(nlog^n)$。
方法2.找到一个数$a[i]$可扩展的左侧区间和右侧区间。 怎样快速的找到？
例如：4 4 2 6 8 6 9 3 9 12 8
当$a_i$向右扩展到最后一个可扩展的数$a_j$后，$a_{i+1}..a_j$没有必要再扩展。直接跳到$j+1$即可。所以一个数被向同一个放心扩展的时候，不管是作为除数还是被除数，只需要访问1次。时间复杂度$o(n)$.
方法一参考代码：
#include <bits\/stdc++.h>
#define pb push_back
using namespace std;
const int N=3e5+50,LOG_N=20;
int gcd(int a,int b){ return !b?a:gcd(b,a%b); }
int n,f[N][LOG_N],g[N][LOG_N],lg[N],a[N];
vector<int> ans;
int qf(int l,int r){
int k=lg[r-l+1];
return min(f[l][k],f[r-(1<<k)+1][k]);
}
int qg(int l,int r){
int k=lg[r-l+1];
return gcd(g[l][k],g[r-(1<<k)+1][k]);
}
bool check(int len){
int i;
for(i=1;i+len-1<=n;++i){
if(qf(i,i+len-1)==qg(i,i+len-1))return true;
}
return false;
}
int main(int argc,char *argv[]){
int i,k,mid;
scanf("%d",&n);
for(i=1;i<=n;++i){
scanf("%d",&a[i]);
f[i][0]=g[i][0]=a[i];
}
lg[0]=-1;
for(i=1;i<=n;++i)lg[i]=lg[i>>1]+1;
for(k=1;k<20;++k){
for(i=1;i+(1<<k)-1<=n;++i){
f[i][k]=min(f[i][k-1],f[i+(1<<(k-1))][k-1]);
g[i][k]=gcd(g[i][k-1],g[i+(1<<(k-1))][k-1]);
}
}
int l=1,r=n+1;
while(r-l>1){
mid=(l+r)>>1;
if(check(mid))l=mid;
else r=mid;
}
for(i=1;i+l-1<=n;++i)
if(qf(i,i+l-1)==qg(i,i+l-1))ans.pb(i);
printf("%d %d\n",(int)ans.size(),l);
for(auto t:ans) printf("%d ",t); puts("");
return 0;
}
方法二参考代码：
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int N = 300030;
int n,c[N],l[N],r[N],cnt,maxn;
queue<int>q;
int main()
{
scanf("%d",&n);
for(int i=1;i <= n;i++)
scanf("%d",&c[i]);
int x = 1;
for(int i=1;i <= n;i = x){
while(x <= n && c[x]%c[i] == 0) x++;
r[i] = x-1;
}
x = n;
for(int i=n;i >= 1;i--){
if(r[i]){
x = i;
while(x >= 1 && c[x]%c[i] == 0) x--;
l[i] = x+1;
i = x+1;
}
}
for(int i=1;i <= n;i++){
if(!l[i])
continue;
if(r[i]-l[i]+1 == maxn)
q.push(l[i]) , cnt++;
if(r[i]-l[i]+1 > maxn){
maxn = r[i]-l[i]+1 , cnt = 1;
while(!q.empty())
q.pop();
q.push(l[i]);
}
}
printf("%d %d\n",cnt,maxn);
while(!q.empty())
printf("%d ",q.front()) , q.pop();
puts("");
return 0;
}
T3
题目分析
设lowbit(x^y)=2^t
则x的t-1位和y的t-1位相同。
不断把数分组，找到对应的位数。
30\% 的数据，$o(n^2)$暴力枚举。
10\% $a_i \leq1$, 分为两个集合，0集合和1集合，ij分别属于这两个集合才可行。
10\% $a_i \leq3$, 怎么做？
分为两种情况：
$lowbit(a_i,a_j)==1$的情况
0集合和1集合，ij分别属于这两个集合才可行。 $lowbit(a_i,a_j)==10$的情况 分别处理两个集合：{10，00}，{11,01}
扩展到所有情况：
lowbit(x,y) 把x和y都分解成二进制 奇数（二进制末位是1），偶数（二进制末位是0）
lowbit(x^y)=1
把奇数放到左边，假设有x个， 把偶数放到右边，假设有y个， xy2 对 lowbit起来是等于1。
lowbit(x^y)=2 (10)
x和y全奇 或者 全偶
假如x和y全奇数
二进制倒数第二位一个是0一个是1
倒数第二位是0 倒数第二位是1
1 2 3 4 5 001 010 011 100 101
001 010 011 100 101
322 * 1 = 12
011 001 010 100 101
122 * 2 = 8 112 * 2=4
101 001 112 * 4 = 8
方法一：分治， 二元组一个在左边，另一个在右边，这样的贡献是很容易统计的 对于每一个数，它只在最多31层中被分治到，总时间复杂度是$o(n*31)$
方法二：找出后t-1位一样的分成一组，再把这组内第t位为1和0的个数都找出来。计算乘积。也可以用trie树，但注意用的时候要从低位开始建树，因为我们要从低位找相同前缀。
方法一参考代码：
#include<bits\/stdc++.h>
#define MOD 1000000007
#define MAXN 999999999
#define LL long long
using namespace std;
LL a[100005],b[100005],ans;
LL n;
void work(LL m,LL t) {
LL l,r,p,i;
if(m<=1||t>=30) return;
l=0;
for(i=1; i<=m; i++)
if(a[i]&(1<<t)) {
l++;
b[l]=a[i];
}
r=l;
for(i=1; i<=m; i++)
if(!(a[i]&(1<<t))) {
r++;
b[r]=a[i];
}
for(i=1; i<=m; i++) a[i]=b[i];
ans=(ans+(l*(m-l)%MOD)%MOD*(1<<t)%MOD)%MOD;\/\/l*r
work(l,t+1);
p=0;
for(i=l+1; i<=r; i++) {
p++;
a[p]=a[i];
}
work(p,t+1);
}
int main() {
int i;
scanf("%lld",&n);
for(i=1; i<=n; i++)
scanf("%lld",&a[i]);
work(n,0);
ans=(ans*2)%MOD;
printf("%lld",ans);
return 0;
}
方法二参考代码：
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include<bitset>
using namespace std;
typedef long long ll;
const int N=100009;
const ll mod=1e9+7;
int nex[N*31][2],m,n,cnt=0,flag;
ll num[N*31][2],ans=0;
int a[N],le[N],ri[N];
inline void insert(int x) {
int l,p,y=x;
int now=0;
for(int i=0; i<=30; i++) {
p=1&(x>>i);
if(!nex[now][p])
nex[now][p]=++cnt;
num[now][p]++;
now=nex[now][p];
}
}
void count(int u,ll t){
if(num[u][0]&&num[u][1])
ans=(ans+num[u][0]%mod*num[u][1]%mod*(1<<t))%mod;
if(nex[u][0]){
count(nex[u][0],t+1);
}
if(nex[u][1]){
count(nex[u][1],t+1);
}
}
int main() {
int x=0;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
insert(a[i]);
}
count(0,0);
ans=ans*2%mod;
printf("%d\n",ans);
return 0;
}
T4逆序对
题目分析
对于当前枚举的L,R若满足条件，则对于当前的L，当R取R~N时都满足条件。
对于当前的枚举的L,R若不满足条件，则对于当前的L，当R取L+1~R时都不能满足条件。
于是就转变成了一个滑动窗口问题，双指针维护，用树状数组算出左右指针移动对当前总值的贡献 双指针，随着l的左移，r不断左移，单调的。
两个树状数组， 一个是y:处理 r...n后缀的情况，r不断增大。 一个是x：处理 1..l,前缀的情况，l不断增大。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL "%lld"
#define lb(x) ((x)&(-(x)))
const int maxn=100010;
int n,z[maxn],y[maxn],x[maxn];
long long k;
bool cmp(int a,int b) {
return z[a]<z[b];
}
void insert(int *z,int p,int d) {
for (; p<=n; p+=lb(p))
z[p]+=d;
}
int query(int *z,int p) {
int ans=0;
for (; p; p-=lb(p))
ans+=z[p];
return ans;
}
int main() {
scanf("%d" LL,&n,&k);
for (int a=1; a<=n; a++)
scanf("%d",&z[a]),y[a]=a;
sort(y+1,y+n+1,cmp);
x[y[1]]=1;
for (int a=2; a<=n; a++)
if (z[y[a]]==z[y[a-1]]) x[y[a]]=x[y[a-1]];
else x[y[a]]=x[y[a-1]]+1;
for (int a=1; a<=n; a++)\/\/完成a离散化后的数据
z[a]=x[a];
memset(x,0,sizeof(x));
memset(y,0,sizeof(y));
long long nowans=0;
int p=n;
while (p>=1) {\/\/第一遍逆序对
nowans+=query(y,z[p]-1);\/\/逆序做，查询比他小的数。nowans是所有逆序对的个数。
insert(y,z[p],1);
p--;
}
p++;
\/\/存储当前到l的逆序对情况
long long ans=0;
int l,r=1;
for (l=1; l<=n; l++) {
if (r==l) {\/\/，不能有l==r，因此要删掉r，同时减去对应的逆序对数目。
nowans-=l-1-query(x,z[r])+query(y,z[r]-1);\/\/减去和1.r中 1..r-1和人构成的逆序对个数，减去和r点和后面数据构成的逆序对个数query(y,z[r]-1)
insert(y,z[r],-1);\/\/删掉r
r++;
}
nowans+=l-1-query(x,z[l])+query(y,z[l]-1);\/\/1..l,r..n构成的逆序对总数
insert(x,z[l],1);
while (nowans>k && r<=n) {\/\/个数太多，r要后移。
nowans-=l-query(x,z[r])+query(y,z[r]-1);
insert(y,z[r],-1);
r++;
}
if (nowans<=k) ans+=n-r+1;\/\/r 到n都符合条件。
}
printf(LL "\n",ans);
return 0;
}
鲁ICP备2025150228号