当天在家里躺尸看 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