十月最后一场训练赛,成功花了两个小时做出来我校去参赛队伍五个小时的罚时。
参赛人数 2 参赛时间 3 小时(其实过了 4 题之后就在摆了),大概参赛的话能混个 Cu ,有希望 Ag 吧
October 大神狂切题大显神威,scmmm 大菜鸡尽显菜鸡本色。
本菜鸡就做了两道题,神仙怒d:”我有你这个时间可以做两百道题“
E Draw a triangle
上帝视角来看, A 得第四多的题,可以算铜牌题?
题目是给你三角形得两个点 (a1,b1),(a2,b2),求你找出来第三个点,使得三角形面积最小,并且这个点一定得是整数点。
我们先考虑平行或者垂直于 x 轴的情况,显然这个时候最小面积是当前两点长度乘以二分之一 ,答案点是(a1+1,b1) 或者 (a1,b1+1)
否则,我们记两个点组成的线段斜率为k ,如果 k 是个整数,答案依然是(a1+1,b1) 或者 (a1,b1+1) ,考虑这个三角形以这个线段为底,高最小就是 k1
不然的话,假设当前斜率为 k=dc ,如果面积最小的话,我们肯定需要 t∗k=d1+ϕ ,ϕ 是一个整数
欸,这个写法好熟悉
t∗c≡1(modd)
用一个 exgcd 即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
| #include <bits/stdc++.h> using namespace std; using LL = long long;
int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int T; cin >> T; while(T -- ) { LL x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; if(x1 > x2) { swap(x1, x2); swap(y1, y2); } if(x1 == x2) { cout << x1 + 1 << " " << y1 << "\n"; continue; } if(y1 == y2) { cout << x1 << " " << y1 + 1 << "\n"; continue; } function<LL(LL, LL)> gcd = [&](LL a, LL b) -> LL { return b ? gcd(b, a % b) : a; }; function<LL(LL, LL, LL&, LL&)> Exgcd = [&](LL a, LL b, LL &x, LL &y) -> LL { if (!b) { x = 1; y = 0; return a; } LL d = Exgcd(b, a % b, x, y); LL t = x; x = y; y = t - (a / b) * y; return d; }; LL dx = abs(x1 - x2); LL dy = abs(y1 - y2); LL g = gcd(dx, dy); dx /= g; dy /= g; if(dx == 1) { cout << x1 << " " << y1 + 1 << "\n"; continue; } int rev = 0; if(y2 < y1) { x1 = x2 + x2 - x1; rev = 1; } LL ddy=dy%dx; LL xx,yy; Exgcd(ddy,dx,xx,yy); xx=((xx%dx)+dx)%dx; LL anx = (xx) + min(x1, x2); if(rev) anx -= 2 * (anx - x2); LL any = (xx) * dy / dx + min(y1, y2) ; cout << anx << " " << any << "\n"; } return 0; }
|
J Permutation Puzzle
神曰:“圣哉pui<pvi”
神再曰:“ 0 者,菜鸡写乎 ”
换句话说,对于我这个菜鸡,我需要在一个残缺的排列中(指有些数字是0 ,需要你填上数,满足上面的关系)
我们对于未知的两个数 x,y , 如果他们满足第一个条件 px<py ,那我们记两个数最小的可能值为 Lx,Ly ,最大值为 Rx,Ry
可以得到这两个东西:
Ly>=Lx+1,Rx<=Ry−1
我们可以利用一个拓扑排序,来得到所有数字的 Li,Ri 特别的,当 pi 已知,Li=Ri=a[i] 如果Li>Ri 那就说明无解。
问题就转化成了给你 n 个区间,每个数字满足 ax∈[Li,Ri] 询问是否有合法解。
那么我们先按照 Li 排序,考虑将 pos 赋值给 i ,那么 i 需要满足 $L_i \leq pos $
那么贪心地给当前 R 最小的 pos 是否最优呢?
我想很显然,所以我咕了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115
| #include<iostream> #include<cmath> #include<cstdio> #include<cstring> #include<queue> #include<stack> #include<vector> #include<set> #include<map> #include<algorithm>
using namespace std;
const int maxn=2e5+20;
vector <int> G1[maxn],G2[maxn]; int ind[maxn],dni[maxn]; int L[maxn],R[maxn],a[maxn]; int n,m,T,usd[maxn];
struct que{ int l,r,x; bool operator <(const que &b) const { if(l==b.l) return r<b.r; return l<b.l; } }qm[maxn];
int toposort() { queue <int> q; int tot=0; for(int i=1;i<=n;i++) if(!ind[i]) q.push(i); while(!q.empty()) { tot++; int t=q.front(); q.pop(); if(a[t]&&L[t]!=a[t] ){cout<<-1<<endl; return 0;} int sz=G1[t].size(); for(int i=0;i<sz;i++) { int j=G1[t][i]; ind[j]--; L[j]=max(L[t]+1,L[j]); if(!ind[j]) q.push(j); } } if(tot!=n) {cout<<-1<<endl; return 0;} tot=0; for(int i=1;i<=n;i++) if(!dni[i]) q.push(i); while(!q.empty()) { tot++; int t=q.front(); q.pop(); int sz=G2[t].size(); if(a[t]&&R[t]!=a[t]) {cout<<-1<<endl; return 0;} for(int i=0;i<sz;i++) { int j=G2[t][i]; dni[j]--; R[j]=min(R[t]-1,R[j]); if(!dni[j]) q.push(j); } } if(tot!=n) {cout<<-1<<endl; return 0;} priority_queue <que> qq; int cnt=0; for(int i=1;i<=n;i++) if(!a[i]) qm[++cnt]=que{L[i],R[i],i}; for(int i=1;i<=n;i++) if(a[i]) usd[a[i]]=1; sort(qm+1,qm+cnt+1); int pos=1; for(int i=1;i<=n;i++) if(!usd[i]){ while(qm[pos].l<=i&&pos<=cnt) qq.push(que{-qm[pos].r,-qm[pos].l,qm[pos].x}),pos++; if(qq.empty()) {cout<<"-1\n"; return 0;} int t=qq.top().x; if(R[t]<i||(L[t]>R[t])) {cout<<-1<<endl;return 0;} a[t]=i; qq.pop(); } for(int i=1;i<=n;i++) cout<<a[i]<<" "; cout<<endl; }
int main() { ios::sync_with_stdio(false); cin>>T; while(T--) { cin>>n>>m; int t1,t2; for(int i=1;i<=n;i++) { usd[i]=0; L[i]=1,R[i]=n; ind[i]=dni[i]=0; G1[i].clear(); G2[i].clear(); } for(int i=1;i<=n;i++) { cin>>a[i]; if(a[i]) L[i]=R[i]=a[i]; } for(int i=1;i<=m;i++) { cin>>t1>>t2; G1[t1].push_back(t2); G2[t2].push_back(t1); ind[t2]++,dni[t1]++; } toposort(); } }
|