常数太大挂分绝美哈,感觉是 oj 不带 o2 但是我用了不少吸氧才快点的东西。
T1 困难卷积
\(O(n\sqrt n)\) 感觉跑的太不过了,注意到 \(\sum a_i,\sum b_i\leq 10^7\),我们不妨让大 \(a/b\) 的找小的 \(b/a\) 贡献,这样子复杂度是 \(O(\sum\sqrt{a_i}+\sum\sqrt{b_i})\) 的,轻松通过此题。
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
using namespace std;
const int N=3000005;
int n, a[N], b[N], limit, Ans, cnt[N];
void solve() {
up(i,0,limit) cnt[i]=0;
up(i,1,n) ++cnt[b[i]];
up(i,1,limit) cnt[i]+=cnt[i-1];
up(i,1,n) for(int x=1; x*x<=a[i]; ++x) Ans+=cnt[a[i]-x*x];
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
up(i,1,n) cin >> a[i], limit=max(limit,a[i]);
up(i,1,n) cin >> b[i], limit=max(limit,b[i]);
solve();
up(i,1,n) swap(a[i],b[i]);
solve();
cout << Ans;
return 0;
}
T2 点集直径
先计算全放 \(x/y\) 的贡献,剩下横纵轴都有的情况,此时贡献有 3 种产生方式,在 \(x/y\) 轴的极差,\(x\) 上绝对值最大的和 \(y\) 上绝对值最大的组成的斜线。考虑二分答案 \(dis\) 判断可行性,枚举贡献 \(x\) 绝对值最大的点 \(p\),设其坐标为 \((x_0,y_0)\)。
-
若 \(x_0\geq 0\),则 \(x\in[max(-x_0,x_0-dis),x_0]\) 的放到 \(x\) 轴,否则只能放到 \(y\) 轴。
-
若 \(x_0<0\),则 \(x\in[x_0,min(-x_0,x_0+dis)]\) 的放到 \(x\) 轴,否则只能放到 \(y\) 轴。
找合法区间可以使用两个双指针 / 二分+o2 优化,lower_bound 不吸氧会 100-> 50 /fad
然后判定还要预处理一个前/后缀最大/小值域,注意初始化,还有就是自带的 sqrt 掉精度严重要手写。
#define _CRT_SECURE_NO_WARNINGS
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
#define pb push_back
using namespace std;
const int N=200005, inf=1e18;
int n, Ans, x[N], y[N], fx[N], fy[N], gx[N], gy[N];
struct node {
int x, y;
bool operator<(const node &rhs) const { return x<rhs.x; }
} p[N];
inline int sq(int x) { return x*x; }
inline int sqrt(int x) {
if(x<1) return 0;
int l=0, r=x, ret;
while(l<=r) {
int mid=(l+r)/2;
if(mid<=x/mid) ret=mid, l=mid+1;
else r=mid-1;
}
return ret;
}
bool check(int dis) {
int qwq=sqrt(dis);
up(i,1,n) {
int L, R, U=-inf, D=inf;
if(p[i].x>=0) R=p[i].x, L=max(-R,R-qwq); else L=p[i].x, R=min(-L,L+qwq);
L=lower_bound(x+1,x+1+n,L)-x, R=upper_bound(x+1,x+1+n,R)-x-1;
if(L>1) U=max(fx[L-1],U), D=min(fy[L-1],D);
if(R<n) U=max(gx[R+1],U), D=min(gy[R+1],D);
if((L>1||R<n)&&sq(U-D)<=dis&&sq(max(abs(U),abs(D)))+sq(p[i].x)<=dis) return 1;
}
return 0;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
up(i,1,n) cin >> p[i].x >> p[i].y;
sort(p+1,p+1+n), fy[0]=gy[n+1]=inf, fx[0]=gx[n+1]=-inf;
up(i,1,n) x[i]=p[i].x, y[i]=p[i].y;
up(i,1,n) fx[i]=max(fx[i-1],y[i]), fy[i]=min(fy[i-1],y[i]);
dn(i,n,1) gx[i]=max(gx[i+1],y[i]), gy[i]=min(gy[i+1],y[i]);
Ans=min(sq(p[n].x-p[1].x),sq(fx[n]-fy[n]));
int l=0, r=Ans;
while(l<=r) {
int mid=(l+r)/2;
if(check(mid)) Ans=min(Ans,mid), r=mid-1;
else l=mid+1;
}
cout << Ans;
return 0;
}
T3 对称之美
看到之后稍微打表联想会发现这个应该形如费马小定义,然后会出现神奇 \(1/p-1\),联想到二次剩余,去查找二次剩余之后又觉得这个东西应该形如二次剩余,于是猜测形式枚举出系数即可,指数是可以猜到的,底数是可以打表的。
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
#define pb push_back
using namespace std;
int mul(int a,int b,int mod) {
int ret=0;
a=(a%mod+mod)%mod, b=(b%mod+mod)%mod;
for( ; b; b>>=1) {
if(b&1) ret=(ret+a)%mod;
a=(a+a)%mod;
}
return (ret%mod+mod)%mod;
}
int ksm(int a,int b,int mod) {
int ret=1%mod;
a=(a%mod+mod)%mod;
for( ; b; b>>=1) {
if(b&1) ret=mul(ret,a,mod);
a=mul(a,a,mod);
}
return (ret%mod+mod)%mod;
}
int t, m, p;
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> t;
while(t--) {
cin >> p >> m;
if(p<=2) { cout << 1 << '\n'; continue; }
int t=((1-mul(4,m,p))%p+p)%p;
cout << ksm(t,(p-1)/2,p) << '\n';
}
return 0;
}
T4 王道征途
不难发现时间倒流之后是模板线段树,注意常数,注意如果在没有被占领的洞里面出现宝物不会留存(这个题面真的很没有素质,而且大样例也没有 \(a_i=0\) 吧)。
#define _CRT_SECURE_NO_WARNINGS
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
using namespace std;
const int N=500005;
int n, m, q, opt[N], a[N], L[N], R[N], X[N], Ans[N];
int tag[N<<2], add[N<<2], val[N<<2];
inline void tup(int p) {
val[p]=val[ls(p)]+val[rs(p)];
}
inline void tdn(int p,int s,int e) {
if(tag[p]) {
tag[ls(p)]=1, val[ls(p)]=0, add[ls(p)]=0;
tag[rs(p)]=1, val[rs(p)]=0, add[rs(p)]=0;
tag[p]=0;
}
if(add[p]) {
int mid=(s+e)>>1;
val[ls(p)]+=add[p]*(mid-s+1), add[ls(p)]+=add[p];
val[rs(p)]+=add[p]*(e-mid), add[rs(p)]+=add[p];
add[p]=0;
}
}
void Add(int l,int r,int v,int p=1,int s=1,int e=n) {
if(l<=s&&e<=r) {
val[p]+=(e-s+1)*v, add[p]+=v;
return;
}
tdn(p,s,e);
int mid=(s+e)>>1;
if(l<=mid) Add(l,r,v,ls(p),s,mid);
if(r>mid) Add(l,r,v,rs(p),mid+1,e);
tup(p);
}
void Clear(int l,int r,int p=1,int s=1,int e=n) {
if(l<=s&&e<=r) {
val[p]=add[p]=0, tag[p]=1;
return;
}
tdn(p,s,e);
int mid=(s+e)>>1;
if(l<=mid) Clear(l,r,ls(p),s,mid);
if(r>mid) Clear(l,r,rs(p),mid+1,e);
tup(p);
}
int Ask(int l,int r,int p=1,int s=1,int e=n) {
if(l<=s&&e<=r) return val[p];
tdn(p,s,e);
int mid=(s+e)>>1, ret=0;
if(l<=mid) ret+=Ask(l,r,ls(p),s,mid);
if(r>mid) ret+=Ask(l,r,rs(p),mid+1,e);
return ret;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> q;
up(i,1,n) cin >> a[i];
up(i,1,q) cin >> opt[i] >> L[i] >> R[i] >> X[i];
dn(i,q,1) {
if(opt[i]==1) {
Ans[X[i]]+=Ask(L[i],R[i]);
Clear(L[i],R[i]);
}
else Add(L[i],R[i],X[i]);
}
up(i,1,n) if(a[i]) Ans[a[i]]+=Ask(i,i);
up(i,1,m) cout << Ans[i] << '\n';
return 0;
}
标签:GCC,9.19,int,up,pragma,gjoi,optimize,mod
From: https://www.cnblogs.com/chelsyqwq/p/18421826