首页 > 其他分享 >gjoi 9.19

gjoi 9.19

时间：2024-09-20 09:25:31浏览次数：11  
标签：GCC 9.19 int up pragma gjoi optimize mod

常数太大挂分绝美哈，感觉是 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

相关文章

  • 9.19
    abc371F：两种做法。等差数列线段树和ODT。两种做法实现难度相同，不过后者似乎要快很多。花1个小时复习了ODT怎么打，他复杂度正确的原因是因为每次query(l,r)过后马上进行了assign。然后就是基础的split和getpos操作，记得给边界插入set。线段树也是维护三元组【l,r,......
  • 吉比特9.19笔试
    第一题给出n,d,m,分别代表多项式个数、维度和修改次数。接下来n行以t开头，接下来t+1个数分别代表0次1次--的项系数接下来m行以p,l,r开头分别代表修改第l个到第r个多项式的前p+1项系数。最后输出n个多项式f(233)的结果，要求结果对1e7+9取模。最后计算结果的次数上限设置为500......
  • 2024.9.19
    双向链表插入：即在单链表插入的基础上增加对前指针的修改循环链表：即将尾部结点的next从NULL改为指向头指针线性表的应用：1.线性表的合并（LB合并到LA中）：将LB中元素逐个取出，在LA中进行逐个查访，不存在就插入。2.有序表的合并(LA,LB合并到LC)：对LA,LB中元素依次比大小后插入。链式......
  • java学习9.19
    结合前端，在本地运行实现登陆操作。将在输入框的数据传给服务器，服务器再通过调用数据库的数据进行对比，实现简单的判断逻辑到这里的我就感觉内容多了起来，在之前连接数据库，数据库操作的时候，跟着教程走，只是知道简单的用法也能在之后自行配置这里的话数据库等操作变成了一个环节，还有......
  • 2024.09.19短时训练赛总结
    $T1$感觉没有蓝，只有中绿左右。赛时写了正解，漏了个$+$号，寄了，然后逆元处理了$inv$，但是不知道为什么写的是快速幂，于是就T了。考虑枚举两端改变，中间随便的区间$[i,j]$，然后乱搞即可。$\color{black}{zzzcr}$有一个$O(n)$的做法是考虑双指针，然后对于有交的区......
  • 【2024潇湘夜雨】WIN11_Pro_21H2.22000.3197软件选装纯净特别版9.19
    【系统简介】=============================================================1.本次更新母盘来自WIN11_Pro_21H2.22000.3197.2.全程离线精简、无人值守调用优化处理制作。部分优化适配系统可能要重启几次，即使显示适配失败也不要在意，可能部分优化不适用。3.OS版本号为22000.3197。......
  • gjoi 2024.9.12
    T1星天花雨首先考虑分解\(k=l\timesr\)，然后考虑\(a/b\)的前缀和中差分为\(l/r\)的对数是多少累加进去就行了，这个是好求的。#include<bits/stdc++.h>#defineup(i,l,r)for(inti=l;i<=r;++i)#definedn(i,r,l)for(inti=r;i>=l;--i)#definepbpush_backusing......
  • C语言试题汇编 答案 9.192&9.193
    9.192有4名学生，每个学生考4门课程，要求在用户输入学生序号以后能输出该学生的全部成绩，用指针型函数实现。#include<stdio.h>float*search(float(*pointer)[4],intn);intmain(){ staticfloatscore[][4]={{60,70,80,90},{50,89,67,88},{34,78,67,88},{80,90,100,70}}; ......
  • Java学习日历(String,StringBuilder,Stringjoiner)
     金额转换packageme.JavaStudy;importjava.util.Scanner;//币值转换publicclassCaptial{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);System.out.println("请输入一个数字");intnumber=sc.ne......
  • GJOI 2024.7.15 总结
    T1CF1607E简单题，直接模拟即可。T2CF1614C容易发现一种可行的构造方案就是对于每个\(a_i\)以及包含它的操作\(C_{i_1,i_2...i_t}\)，令\(a_i=V_{i_1}\&V_{i_2}\&...V_{i_t}\)即可。直接硬上线段树即可。考虑到位运算位之间互不影响的性质，接着我们从分别考虑每一......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99