前言
过题数 |
排名 |
A |
B |
C |
D |
E |
F |
G |
H |
I |
J |
K |
L |
M |
3 |
491 |
|
|
|
√ |
|
|
|
B |
|
√ |
√ |
|
B |
1 2 3 4 5 6
| |过题数|排名|A|B|C|D|E|F|G|H|I|J|K|L|M| |-----|----|-|-|-|-|-|-|-|-|-|-|-|-|-| | | | | | | | | | | | | | | | | √ 赛时过了 B 补题过了
|
A
B
C
D
E
F
G
H
给你两个数组 a,b 只能交换一次或者0次 ai,aj,询问最小化 d=i−1∑n∣ai−bi∣
考虑把 ai,bi 放在数轴上,就变成了一个区间覆盖的问题。我们定义 ai>bi 是向左的区间,反之为向右的区间。这个时候,桐乡的区间 a 交换对答案不会有任何印象,但是反向的区间交换有影响,具体而言,如果 ai≤bj≤bi≤aj 答案会减少 2∗(bi−bj)
这个时候我们从右向左扫一次,找到最大的 bi−bj 即可。
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
| #include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1000200;
int n,a[maxn],b[maxn],c1,c2; int ans=0,target;
struct mmm{ int l,r,lk; mmm(){} mmm(int L,int R,int LK): l(L),r(R),lk(LK){} bool operator <(const mmm &b) const { if(r==b.r) return l>b.l; return r>b.r; } }q[maxn];
signed main() { ios::sync_with_stdio(false); cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) cin>>b[i]; for(int i=1;i<=n;i++) { if(a[i]<b[i]) q[i]=mmm(a[i],b[i],1); else q[i]=mmm(b[i],a[i],0); ans+=abs(a[i]-b[i]); } int lmmn[2]={1000000000,1000000000}; sort(q+1,q+n+1); for(int i=1;i<=n;i++) { int lk=q[i].lk; target=max(target,max(0ll,q[i].r-max(q[i].l,lmmn[lk^1]))); lmmn[lk]=min(lmmn[lk],q[i].l); } cout<<ans-target*2<<endl; }
|
I
J
K
给你一张图,你可以把一条边改成一个新的顶点连原来边的两点,可以无限次操作,问最多有多少个点距离 1 号点距离小于 k
直接考虑 bfs 建树,然后对于每个非树边 (u,v) ,显然这上面还可以添加 2∗k−dis[u]−dis[v] 个点。然后考虑叶子节点,也可以在这上面添加点,具体而言,是添加 k−dis[u] 个点。
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
| #include<bits/stdc++.h>
#define int long long
const int maxn=500500;
using namespace std;
int f[maxn],n,m,k,vis[maxn]; int ans=0,pd[maxn];
struct mmm{ int x,y,looker; }q[maxn];
int getf(int x) { if(x==f[x]) return x; return f[x]=getf(f[x]); }
struct graph{ int head[maxn],s1ze; int dis[maxn],isleaf[maxn]; int fa[maxn]; struct edge { int next,to,lk; }e[maxn]; void addedge(int next,int to,int lk) { e[++s1ze].next=head[next]; head[next]=s1ze; e[s1ze].to=to; e[s1ze].lk=lk; }
void bfs() { queue <int> q; q.push(1); ans=1; while(!q.empty()) { int t=q.front(); q.pop(); int lk=1; for(int i=head[t];i;i=e[i].next) { int j=e[i].to; if(dis[t]+1<dis[j]) { dis[j]=dis[t]+1; if(dis[j]<=k) ans++; pd[e[i].lk]=1; q.push(j); lk=0; } } if(lk) isleaf[t]=1; } } }G;
signed main() { ios::sync_with_stdio(false); cin>>n>>m>>k; for(int i=1;i<=n;i++) f[i]=i,G.dis[i]=0x3f3f3f3f; for(int i=1;i<=m;i++) { cin>>q[i].x>>q[i].y; G.addedge(q[i].x,q[i].y,i); G.addedge(q[i].y,q[i].x,i); } G.dis[1]=0; G.bfs(); for(int i=1;i<=m;i++) { if(!pd[i]) { int tx,ty; tx=q[i].x; ty=q[i].y; if(G.dis[tx]<=k&&G.dis[ty]<=k) { ans+=2*k-G.dis[tx]-G.dis[ty]; } vis[tx]=1; vis[ty]=1; } } for(int i=1;i<=n;i++) { if(G.isleaf[i]&&G.dis[i]<=k&&!vis[i]&&G.head[i]) { ans+=k-G.dis[i]; } } cout<<ans<<endl; }
|
L
M
给你两种杯子容量分别为 a,b ,你可以接满水,倒水到另一个杯子或者倒掉,喝水,询问最少多少次操作你可以得到刚好 k 单位的水。
换句话说,考虑 k=ax+by ,当 x,y>=0 显然直接接了喝就可以了。
假定 a<b ,那么裴蜀定理,(a,b)∣k 才有解,