前言
- 比赛链接。
终于不挂分了这次，但是 T2 写得太慢了导致 T4 没写完只能胡暴力。
但是赛时数据和样例出了好多问题给不少人造成了影响。
T1 abc猜想
\(ans=\lfloor\dfrac{a^b}{c}\rfloor \bmod c=\dfrac{a^b-a^b\bmod c}{c}\bmod c\)
不妨设 \(\dfrac{a^b-a^b\bmod c}{c}=kc+ans\)，有 \(a^b-a^b\bmod c=kc^2+ans·c\)。
所以有 \(ans=\dfrac{(a^b-a^b\bmod c)\bmod c^2}{c}\)。
T2 简单的排列最优化题
枚举 \(k\)，思考从 \(k\) 转移到 \(k+1\) 会有什么影响。
对于在目标左边的点，向右移贡献减一，反之已经在目标上或在其右边的贡献均加一，且距离目标的距离向右移一位，这个移位不好处理，不妨将 \(0\) 这个端点左移，达到向右移位的效果，\(a_{n-k}\) 特殊处理，从 \(n\) 移到 \(1\) 即可，开几个变量可以做到 \(O(1)\) 修改。
复杂度 \(O(n)\)。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=8e6+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
void wt(int x){if(x>9)wt(x/10);putchar((x%10)+'0');}
void write(int x){if(x<0)putchar('-'),x=~x+1;wt(x);}
int n,a[N],cnt[N],now,sum,ans,ans2,l,r;
signed main()
{
read(n); now=2*n;
for(int i=1;i<=n;i++)
{
read(a[i]);
cnt[i-a[i]+2*n]++;
sum+=abs(a[i]-i);
}
for(int i=n;i<=2*n-1;i++)
l+=cnt[i];
for(int i=2*n;i<=4*n;i++)
r+=cnt[i];
ans=sum,ans2=0;
for(int i=0;i<=n-2;i++)
{
sum=sum+r-1-l-n+2*a[n-i]-1;
r+=cnt[now-1];cnt[n-a[n-i]+now]--;r--;
l-=cnt[now-1];cnt[1-a[n-i]-1+now]++;
if(a[n-i]==1) r++;
else l++;
now--;
if(sum<ans) ans=sum,ans2=i+1;
}
cout<<ans2<<' '<<ans;
}
T3 简单的线性做法题
分治。
- 结论 \(1\)：若 \(x\) 为 \([l,r]\) 的绝对众数，则其一定是 \([l,k]\) 或 \([k+1,r]\) 的绝对众数。
- 结论 \(2\)：一个区间能成为绝对众数的个数不超过 \(log\)。
证明显然。
对于 \([l,r]\)，取 \(mid\) 为分割点，处理所有经过 \(mid\) 的合法的子区间，对 \([l,mid],[mid+1,r]\) 递归处理。
类似于处理中位数的做法，我们知道 \(x\) 为区间绝对众数当且仅当 \(cnt_x>\lfloor\dfrac{size}{2}\rfloor\)，转化有 \(2cnt_x-size>0\)，枚举众数 \(x\)，若 \(a_i=x\) 则 \(sum+1\)，否则 \(sum-1\)，\(sum\) 即表示 \(2cnt_x-size\)。
可以 \(O(size)\) 通过结论处理出可能成为众数的 \(a_i\)，对于区间 \([l,mid-1]\) 从左往右扫出 \(sum\) 进行前缀和处理，开桶统计每个 \(sum\) 的个数，继续向右扫，对于区间 \([mid+1,r]\)，则此时桶内值小于当前 \(sum\) 均可以产生贡献，即前缀和操作使对应区间 \(2cnt_x-size>0\)，使其合法。
对于 \(l=r\) 显然合法。
复杂度 \(O(n\log^2(n))\)。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=1e6+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
ll n,a[N],ans,cnt[N];
bool vis[N];
vector<ll>pos;
void solve(int l,int r)
{
if(l==r) {ans++; return ;}
ll mid=(l+r)>>1,sum,minn,maxx;
solve(l,mid),solve(mid+1,r);
for(int i=mid;i>=l;i--)
{
cnt[a[i]]++;
if(cnt[a[i]]>((mid-i+1)>>1)&&vis[a[i]]==0)
{
vis[a[i]]=1;
pos.push_back(a[i]);
}
}
for(int i=l;i<=mid;i++) cnt[a[i]]=0;
for(int i=mid+1;i<=r;i++)
{
cnt[a[i]]++;
if(cnt[a[i]]>((i-mid)>>1)&&vis[a[i]]==0)
{
vis[a[i]]=1;
pos.push_back(a[i]);
}
}
for(int i=l;i<=r;i++) cnt[a[i]]=vis[a[i]]=0;
for(int x:pos)
{
sum=minn=maxx=r-l+1;
cnt[sum]++;
for(int i=l;i<=mid-1;i++)
{
sum+=(a[i]==x)?1:-1;
minn=min(minn,sum);
maxx=max(maxx,sum);
cnt[sum]++;
}
sum+=(a[mid]==x)?1:-1;
for(int i=minn+1;i<=maxx;i++) cnt[i]+=cnt[i-1];
for(int i=mid+1;i<=r;i++)
{
sum+=(a[i]==x)?1:-1;
ans+=cnt[min(maxx,sum-1)];
}
for(int i=minn;i<=maxx;i++) cnt[i]=0;
}
pos.clear();
}
signed main()
{
read(n);
for(int i=1;i<=n;i++) read(a[i]);
solve(1,n);
write(ans);
}
T4 简单的线段树题
-
部分分 \(60pts\)：直接 \(n^2\) 暴力。
-
正解：
考虑 \(10^{11}\) 最多被开方 \(6\) 次，在势能线段树上对于每个区间处理出区间和与区间最大值，若最大值 \(=1\) 就不需要再递归下去了，修改直接单点暴力改，每个数最多改 \(6\) 遍，所以复杂度是正确的。
点击查看代码
#include<bits/stdc++.h> #define int long long #define endl '\n' #define sort stable_sort #define f t[p] #define ls p<<1 #define rs p<<1|1 using namespace std; const int N=1e6+10; template<typename Tp> inline void read(Tp&x) { x=0;register bool z=true; register char c=getchar(); for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0; for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48); x=(z?x:~x+1); } void wt(int x){if(x>9)wt(x/10);putchar((x%10)+'0');} void write(int x){if(x<0)putchar('-'),x=~x+1;wt(x);} int n,m,a[N],sum[N],pos[N]; struct aa {int l,r,val,add,flag;}t[N<<2]; void pushup(int p) { f.val=t[ls].val+t[rs].val; f.flag=max(t[ls].flag,t[rs].flag); } void build(int p,int l,int r) { f.l=l,f.r=r; if(l==r) { pos[l]=p; f.val=f.flag=a[l]; return ; } int mid=(l+r)>>1; build(ls,l,mid),build(rs,mid+1,r); pushup(p); } void change(int p,int l,int r) { if(f.l==f.r) { f.flag=floor(sqrt(f.flag)),f.val=f.flag; return ; } if(f.flag<=1) return ; int mid=(f.l+f.r)>>1; if(l<=mid) change(ls,l,r); if(r>mid) change(rs,l,r); pushup(p); } int ask(int p,int l,int r) { if(l<=f.l&&r>=f.r) return f.val; int mid=(f.l+f.r)>>1,ans=0; if(l<=mid) ans+=ask(ls,l,r); if(r>mid) ans+=ask(rs,l,r); return ans; } signed main() { read(n); for(int i=1;i<=n;i++) read(a[i]); build(1,1,n); read(m); for(int i=1,op,l,r;i<=m;i++) { read(op),read(l),read(r); if(l>r) swap(l,r); if(op==0) change(1,l,r); else write(ask(1,l,r)),puts(""); } }
总结
提高速度。
标签：10,int,void,mid,2024,暑假,ans,集训,define From： https://www.cnblogs.com/Charlieljk/p/18314959