首页 > 其他分享 >gjoi 2024.10.9

gjoi 2024.10.9

时间：2024-10-10 15:34:45浏览次数：1  
标签：2024.10 return int GCC pragma gjoi optimize functions

当天在家里躺尸看 t1 过不了就去睡觉了，还好没写卡场 Round 哦 /cf

怎么有人吃错了一整盒退高烧药啊 /wq

T1 游戏升级

考虑有多少 \(x\in [1,n]\) 满足 \(b_1+\lfloor\frac{a_1}{x}\rfloor=b_2+\lfloor\frac{a_2}{x}\rfloor\)，直接对下取整做整除分块即可。gj oj 卡常所以开 long long 无法通过哦。

#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 up(i,l,r) for(register int i=l; i<=r; ++i)
#define dn(i,r,l) for(register int i=r; i>=l; --i)

using namespace std;

int t, a1, b1, a2, b2, n, Ans, ran;

void mian() {
	cin >> a1 >> b1 >> a2 >> b2 >> n, Ans=0;
	for(int l=1, r=n; l<=n; l=r+1, r=n) {
		if(a1/l) r=min(r,a1/(a1/l));
		if(a2/l) r=min(r,a2/(a2/l));
		if(b1+a1/l==b2+a2/l) Ans+=r-l+1; 
	}
	cout << Ans << '\n';
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> t;
	while(t--) mian();
	return 0;
}

T2 难题

手玩一下发现 \(x,y\) 系数是 \(fib\) 数列的数，稍微打一下系数表只有 \(44\) 组可能的系数，设其为 \(\{(L_i,R_i)\}\)。首先除了 \(X=0\) 的情况别的 \((x,y)\) 肯定至多在一组系数中成立，所以特判之后不用考虑去重哦。

那我们现在要知道用系数对 \(L,R\) 能有多少组合法的 \(Lx+Ry=X\) 呢，用 exgcd 求出一组 \(Lx_0+Ry_0=X(d\times\frac{X}{d})\) 之后通解可以表示为 \(L(x_0+\frac{R}{d}\times k)+R(y_0-\frac{L}{d}\times k)=X\)，怕超时要预处理所以写了点莫名其妙带 \(d\) 的东西。我们用 \(x\in[0,n],y\in[0,m]\) 的范围去约束 \(X\) 求出合法 \(k\) 的范围就能知道答案个数了。因为数据较大一些东西需要 i128 和自己手写哦。

#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 __int128
#define db long double
#define up(i,l,r) for(register int i=l; i<=r; ++i)
#define dn(i,r,l) for(register int i=r; i>=l; --i)

using namespace std;

inline int read() {
    int X=0; bool flag=1; char ch=getchar();
    while(ch<'0'||ch>'9') { if(ch=='-') flag=0; ch=getchar(); }
    while(ch>='0'&&ch<='9') { X=(X<<1)+(X<<3)+ch-'0'; ch=getchar(); }
    if(flag) return X;
    return ~(X-1);
}

void write(int X) {
    if(X<0) { X=~(X-1); putchar('-'); }
    if(X>9) write(X/10);
    putchar(X%10+'0');
}

const int N=1005;

int tot=45, t, ran, n, m, Ans;
int L[N], R[N], dd[N], xx[N], yy[N]; 

int exgcd(int a,int b,int &x,int &y) {
	if(b==0) { x=1, y=0; return a; }
	int d=exgcd(b,a%b,x,y);
	int t=x; x=y, y=t-a/b*y;
	return d;
}

inline int ceil(int i,int j), floor(int i,int j);

inline int ceil(int i,int j) {
	if(j<0) i*=-1, j*=-1;
	if(i>=0) return i/j+(i%j!=0);
	return -floor(-i,j);
}

inline int floor(int i,int j) {
	if(j<0) i*=-1, j*=-1;
	if(i>=0) return i/j;
	return -ceil(-i,j);
}

void mian() {
	ran=read(), n=read(), m=read(), Ans=0;
	if(ran==0) { puts("1"); return; }
	up(i,1,tot) {
		if(ran%dd[i]) break;
		int d=dd[i], x=xx[i]*(ran/dd[i]), y=yy[i]*(ran/dd[i]);	
		int l=max(ceil (-x*d,R[i]),ceil ((y-m)*d,L[i]));
		int r=min(floor( y*d,L[i]),floor((n-x)*d,R[i]));
		if(l<=r) Ans+=r-l+1;
	}
	write(Ans), puts("");
}

signed main() {
	L[1]=R[1]=1;
	up(i,1,tot) {
		if(i>1) L[i]=L[i-1]+R[i-1], R[i]=R[i-1]+L[i];
		dd[i]=exgcd(L[i],R[i],xx[i],yy[i]);
	}
	t=read();
	while(t--) mian();
	return 0;
}

T3 迷宫逃亡

好唐哦。

贪心的想想要尽量小的边效力，那答案应该可以在 mst 上面，预处理出 mst 之后在上面求路径最大权即可。

问题是怎么求 mst，暴力做什么的就是每一个特殊点为起点做一个 bfs 连一个 \(O(p^2)\) 的巨大图，绝对不可以呢，考虑到 mst 的特殊性，这里面一定有大量的无用边，起点的量级好像不是很有办法缩小，那想办法把起点一起做，发现会有重叠交错哦，然后不难发现这个东西要走重叠的边建出来是对的了，因为这个相当于枚举 \(s/t\) 往前走 \(\frac{\alpha}{2}\) 步拼在一起，跟 \(s\to t\) 长度为 \(\alpha\) 的路径是双射，整个过程恰好是从小到大枚举权值油滴拓展式的合并，再大的边是无用的了喵 >w<

#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 up(i,l,r) for(register int i=l; i<=r; ++i)
#define dn(i,r,l) for(register int i=r; i>=l; --i)
#define pii pair<int,int>
#define mp make_pair
#define pb push_back

using namespace std;

const int N=200005, M=2005, K=log2(N)+5;
const int dx[4]={1,-1,0,0}, dy[4]={0,0,1,-1};

int n, m, tot, t, ran, col[M][M], dis[M][M], dsu[N], cnt;
int fa[N][K], f[N][K], dep[N];
char init[M][M];
queue<pii> q;
vector<pii> to[N];

struct node {
	int u, v, w;
	bool operator<(const node &rhs) const { return w<rhs.w; }
} p[20000005];

bool check(int i,int j) {
	if(i<1||i>n||j<1||j>m) return 0;
	return init[i][j]=='.';
}

int get(int x) {
	if(x==dsu[x]) return x;
	return dsu[x]=get(dsu[x]);
}

void dfs(int x,int fad) {
	fa[x][0]=fad, dep[x]=dep[fad]+1;
	up(i,1,ran) fa[x][i]=fa[fa[x][i-1]][i-1], f[x][i]=max(f[x][i-1],f[fa[x][i-1]][i-1]);
	for(pii qwq:to[x]) {
		int y=qwq.first, w=qwq.second;
		if(y!=fad) f[y][0]=w, dfs(y,x);
	}
}

int lca(int x,int y) {
	if(dep[x]<dep[y]) swap(x,y);
	dn(i,ran,0) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
	if(x==y) return x;
	dn(i,ran,0) if(fa[x][i]!=fa[y][i]) x=fa[x][i], y=fa[y][i];
	return fa[x][0];
}

int upt(int x,int d) {
	int ret=0;
	dn(i,ran,0) if(dep[fa[x][i]]>=d) ret=max(f[x][i],ret), x=fa[x][i];
	return ret;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> tot >> t, ran=log2(tot);
	up(i,1,n) cin >> (init[i]+1);
	up(i,1,tot) {
		int x, y; cin >> x >> y;
		col[x][y]=i, dis[x][y]=1, q.push(mp(x,y));
	}
	while(q.size()) {
		int x=q.front().first, y=q.front().second;
		q.pop();
		up(o,0,3) {
			int xx=x+dx[o], yy=y+dy[o];
			if(!check(xx,yy)) continue;
			if(dis[xx][yy]) p[++cnt]=(node){col[x][y],col[xx][yy],dis[x][y]+dis[xx][yy]-2};
			else dis[xx][yy]=dis[x][y]+1, col[xx][yy]=col[x][y], q.push(mp(xx,yy));
		}
	}
	sort(p+1,p+1+cnt);
	up(i,1,tot) dsu[i]=i;
	up(i,1,cnt) {
		int x=get(p[i].u), y=get(p[i].v);
		if(x==y) continue;
		dsu[x]=y, to[p[i].u].pb(mp(p[i].v,p[i].w)), to[p[i].v].pb(mp(p[i].u,p[i].w));
	}
	up(i,1,tot) if(!dep[i]) dfs(i,0);
	while(t--) {
		int x, y;
		cin >> x >> y;
		if(get(x)!=get(y)) { cout << -1 << '\n'; continue; }
		int z=lca(x,y);
		cout << max(upt(x,dep[z]),upt(y,dep[z])) << '\n';
	}
	return 0;
}

标签：2024.10,return,int,GCC,pragma,gjoi,optimize,functions
From： https://www.cnblogs.com/chelsyqwq/p/18456476

相关文章

  • 2024.10.10 1514版
    起于《海奥华预言》的思考◆地球管理结构和参考持续更新中...... 英文地址：https://github.com/zhuyongzhe/Earth/tags中文地址：https://www.cnblogs.com/zhuyongzhe85作者：朱永哲 ---------------------------------------------------------------------------------......
  • 2024.10.10 总结
    A：赛时发了什么疯非要来冲这题。不妨计各种颜色的宝石为0/1。考虑记前缀和的最大值为\(S_\max\)，最小值为\(S_\min\)，于是总的限制为\(|S_\max-S_\min|\leqk\)。考虑反向维护这个限制，即枚举一个\(i\)，然后钦定\(i\leqS_\min\leqS_\max\leqi+k\)，计算对应的序列个数。然后......
  • 2024.10.9
    完善由合同来直接生成制令的代码publicvoidinsertOrdersByContract(Contractscontract){//查询刚刚插入的合同contract=contractsMapper.selectContractsList(contract).get(0);//1.根据合同生成唯一的总制令Ordersorders=newO......
  • 【笔记】杂题选讲 2024.10.5（DNF）
    十一杂题选讲-VirtualJudge(vjudge.net)/mnt/e/codes/contests/20241008/sol.md目录[AGC004F]Namori[1406E]DeletingNumbers[1081G]MergesortStrikesBack[1033E]HiddenBipartiteGraph[1254E]SendTreetoCharlie[1012E]Cyclesort[1284F]NewYearandSocialN......
  • 2024.10.9 LGJ Round
    B对于所有\(x\in[0,n],y\in[0,m]\)，求执行\(x\getsx+y,y\getsx+y\)若干次后满足\(x=k\)的双元组个数。这个题充分体现我的唐氏。具体地枚举\(x,y\)分别被算了多少次，系数是斐波那契数列，所以项数很少。然后转化为求\(k_1x+k_2y=k\)的方案数，这个我非常唐不会求。只需......
  • 2024.10.9训练记录
    下午提高组模拟省流：又被lyy吊打了晚上订正A神秘猜结论题，场上少猜了一点挂了\(18\)分，遗憾。结论：\(ans\in[0,3]\)\(0/1\)可以直接判。\(1\)的情况就是存在一个前缀\(a_{1,i}\)满足出现的数是\(1\)到\(i\)。\(3\)的情况仅当\(a_1=n\)且\(a_n=1\)。场上......
  • 2024.10.09 力扣刷题 盛水最多的容器
    题目：这边是参考了B站UP主的思路进行了解答，采用双下标访问的方式进行。如果要水最多的话，一定是高的那端找低的那端，然后算出面积。如果是低的那端找高的那端，那本身下限就在自己身上，所以不从低的端固定不变。附上代码：intmaxArea(std::vector<int>&height){ if(height.empty......
  • 2024.10.9 总结
    决定以后分开写，显的博客多。A：首先考虑对给定树计算权值，假设我们已经知道了一个权值最小的划分，那么可以通过调整得到新的划分使得权值不变，目的是简化虚树的形态。考虑该划分中任意一个集合形成的虚树，有两种情况：如果根节点\(r\)存在于任何一个最大独立集中，即\(f_{r,1}>f_{r,0}......
  • 【test】2024.10.8
    次大值思路发现性质，对于一个数\[a[i]\%a[j]\lea[i]\]当他取得最大值时\(a[i]<a[j]\)于是对于前&n-1&大的数，他的贡献值就是他本身，所以我们只需要保存第\(n-1\),\(n-2\)大的数就可以。但是此时要注意第\(n\)大的数的贡献值没有计算，由于\(a[n]\%a[n-2]<a[n-2]\),所以如果他要......
  • 2024.10.8 鲜花
    好题蜂鸟（难忘今宵）传说中人类在远早住于黑暗的地下之遥派出了娇小的蜂鸟找到通往光明的隧道飞过了一座一座岛好想有一个地方落脚把一个一个梦制造会不会有人能够听到寻找太阳的梦自不量力说自己也变成太阳的念头有时候寂寞几乎扛不动咽在喉咙里无人诉说我们到底在......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99