liyangxinpeng
UID: 46104, 注册于 2024-10-15 21:01:45, 最后登录于 2024-10-20 14:35:10, 最后活动于 2024-10-16 16:11:48.
解决了 4 道题目，RP: 34 (No. 96)
-
个人简介
/* ┌───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┐ 1 A ↓ │Esc│ │ F1│ F2│ F3│ F4│ │ F5│ F6│ F7│ F8│ │ F9│F10│F11│F12│ │P/S│S L│P/B│ ┌┐ ┌┐ ┌┐ └───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┘ └┘ └┘ └┘ ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───────┐ ┌───┬───┬───┐ ┌───┬───┬───┬───┐ │~ `│! I│@ A│# K│$ I│% O│^ I│& 7│* 8│( 9│) 0│_ -│+ =│ BacSp │ │Ins│Hom│PUp│ │N L│ / │ * │ - │ ├───┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─────┤ ├───┼───┼───┤ ├───┼───┼───┼───┤ │ Tab │ Q │ W │ E │ R │ T │ Y │ U │ I │ O │ P │{ [│} ]│ | \ │ │Del│End│PDn│ │ 7 │ 8 │ 9 │ │ ├─────┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴─────┤ └───┴───┴───┘ ├───┼───┼───┤ + │ │ Caps │ A │ S │ D │ F │ G │ H │ J │ K │ L │: ;│" '│ Enter │ │ 4 │ 5 │ 6 │ │ ├──────┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴────────┤ ┌───┐ ├───┼───┼───┼───┤ │ Shift │ Z │ X │ C │ V │ B │ N │ M │< ,│> .│? /│ Shift │ │ ↑ │ │ 1 │ 2 │ 3 │ │ ├─────┬──┴─┬─┴──┬┴───┴───┴───┴───┴───┴──┬┴───┼───┴┬────┬────┤ ┌───┼───┼───┐ ├───┴───┼───┤ E││ │ Ctrl│ Win│Alt │ Space │ Alt│ Fn │Win │Ctrl│ │ ← │ ↓ │ → │ │ 0 │ . │←─┘│ └─────┴────┴────┴───────────────────────┴────┴────┴────┴────┘ └───┴───┴───┘ └───────┴───┴───┘ */ `system("shutdown -s -t 1");//krustal算法 #include<bits/stdc++.h> using namespace std; const int maxn=10010; int n,m,f[maxn],tot; double a[maxn][2]; double ans; struct edge { int u,v;double w; }e[maxn*2]; int find(int a) { if(f[a]!=a) f[a]=find(f[a]); return f[a]; } void union_set(edge p) { int x=find(p.u); int y=find(p.v); if(x!=y){ ans+=p.w; f[y]=x; } } bool cmp(edge a,edge b){return a.w<b.w;} int main(){ while(cin>>n){ if(n==0)return 0; tot=0,ans=0; for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i][0],&a[i][1]); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) { e[++tot]={i,j,sqrt(pow(a[i][0]-a[j][0],2)+pow(a[i][1]-a[j][1],2))}; } sort(e+1,e+tot+1,cmp); for(int i=1;i<=n;i++) f[i]=i; for(int i=1;i<=tot;i++) union_set(e[i]); printf("%.2lf\n", ans); } return 0; }//prim算法 #include<bits/stdc++.h> using namespace std; int main() { int n; cin>>n; int nn=0; while(n!=0) { nn++; float minn[101]; //定义成float类型 bool u[101]; float x[101],y[101]; float g[101][101]; for(int i=1; i<=n; i++) //读入N个点的坐标 cin>>x[i]>>y[i]; for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) g[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])); memset(minn,0x7f,sizeof(minn)); //minn[x]代表x到已加入最小生成树中的点，最小的点距是多少 minn[1]=0; // memset(u,1,sizeof(u)); //代表某个点是否加入最小生成树 float tot=0; for(int i=1; i<=n; i++) //循环N次 { int k=0; for(int j=1; j<=n; j++) { if(u[j]&&minn[j]<minn[k]) //从没有找入最小生成树中的点中找 //找一个minn[j]是最小的 k=j; } u[k]=false; //将k点加入最小生成树 tot=tot+minn[k]; for(int j=1; j<=n; j++) //遍历所有还没有加入最小生成树中的点 { if(u[j]&&g[k][j]<minn[j]) //如果j点没有加入MST，并且k与j直接相连的边权，小于minn[j]的话 //就换过来 minn[j]=g[k][j]; } } printf("%.2f\n",tot); cin>>n; printf("\n"); } }//dijkstra #include <bits/stdc++.h> using namespace std; struct node{ int to,sum; }; bool operator<(node a,node b){ return a.sum>b.sum; } priority_queue<node> q; vector<node> g[300005]; int n,m,d[300005],ans[300005],top,anns,anss; void dij(){ while(top<n){ node hh=q.top(); q.pop(); if(d[hh.to]==0){ top++; d[hh.to]=1; ans[hh.to]=hh.sum; for(int i=0;i<g[hh.to].size();i++){ int v=g[hh.to][i].to; int w=g[hh.to][i].sum; if(hh.sum+w<ans[v]){ ans[v]=hh.sum+w; q.push({v,ans[v]}); } } } } } signed main(){ memset(ans,31,sizeof ans); cin>>n>>m; for(int i=1;i<=m;i++){ int u,v; cin>>u>>v; g[u].push_back({v,1}); g[v].push_back({u,1}); } q.push({1,0}); dij(); for(int i=1;i<=n;i++){ anns=max(ans[i],anns); } for(int i=1;i<=n;i++){ if(ans[i]==anns && anss==0){ cout<<i<<" "; } if(ans[i]==anns){ anss++; } } cout<<anns<<" "<<anss; return 0; }const int N=1e5+114; struct node { int x,y,z; }edge[N]; bool cmp(node x,node y) { return x.z<y.z; } sort(edge+1,edge+1+m,cmp); int sum=0,ans=0; for(int i=1;i<=m;i++) { int x=edge[i].x,y=edge[i].y; int xx=find(x),yy=find(y); if(xx==yy)continue; ans++; sum+=edge[i].z; fa[xx]=yy; if(ans==n-1)break; } 出现次数最多的数字 #include<bits/stdc++.h> using namespace std; const int N=5e5+114; int n,m,a[N]; int dp[55][N],g[55],num[N],l[N],r[N],tmp=-1e9,cnt; int main() { while(cin>>n && n!=0) { memset(dp,0,sizeof dp); memset(num,0,sizeof num); memset(l,0,sizeof l); memset(r,0,sizeof(r)); cnt=0; tmp=-1e9; cin>>m; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n+1;i++) { int x=a[i]; if(x!=tmp) { r[cnt]=i-1; l[++cnt]=i; tmp=x; } num[i]=cnt; } for(int i=1;i<=cnt;i++) { dp[0][i]=r[i]-l[i]+1; } // g[0]=-1; // for(int i=1;i<=n;i++)g[i]=g[i>>1]+1; for(int i=1;(1<<i)<=cnt;i++) { for(int j=1;j<=n-(1<<i)+1;j++) { dp[i][j]=max(dp[i-1][j],dp[i-1][j+(1<<(i-1))]); } } for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; if(x>y)swap(x,y); if(num[x]==num[y])cout<<y-x+1<<endl; else { int ans=0; if(num[x]+1<=num[y]-1) { int l=num[x]+1,r=num[y]-1; int k=0; while((1<<(k+1))<=r-l+1)k++; ans=max(dp[k][l],dp[k][r-(1<<k)+1]); } ans=max(ans,max(r[num[x]]-x+1,y-l[num[y]]+1)); cout<<ans<<endl; } } } return 0; } //tarjan #include<bits/stdc++.h> typedef long long ll; //#define int long long using namespace std; const int N=1e5+114; int n,m,dfn[N],low[N],tot,ans; vector<int> adj[N],what[N]; stack<int> st; int flag[N]; void tarjan(int u) { dfn[u]=low[u]=++tot; st.push(u); for(auto it : adj[u]) { if(!dfn[it]) { tarjan(it); low[u]=min(low[u],low[it]); } else if(!flag[it]) { low[u]=min(low[u],dfn[it]); } } if(dfn[u]==low[u]) { ans++; flag[u]=ans; what[ans].push_back(u); while(st.top()!=u) { flag[st.top()]=ans; what[ans].push_back(st.top()); st.pop(); } st.pop(); } } int main() { cin>>n>>m; for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; adj[x].push_back(y); } for(int i=1;i<=n;i++) { if(!dfn[i]) { tarjan(i); } } int ab=0; for(int i=1;i<=ans;i++) { if(what[i].size()>1)ab++; } cout<<ab; return 0; } //求割点 //tarjan #include<bits/stdc++.h> typedef long long ll; #define int long long using namespace std; const int N=1e5+114; int n,m,dfn[N],low[N],tot,ans,sbsb,hi; vector<int> adj[N],what[N]; set<int> anss; stack<int> st; int flag[N]; void tarjan(int u,int fa) { dfn[u]=low[u]=++tot; st.push(u);int son=0; for(auto it : adj[u]) { if(!dfn[it]) { son++; tarjan(it,u); low[u]=min(low[u],low[it]); if(low[it]>=dfn[u] && it!=fa && hi!=u && !(anss.count(u))) { sbsb++; anss.insert(u); } } else { low[u]=min(low[u],dfn[it]); } } if(hi==u && son>=2) { sbsb++; anss.insert(u); } } signed main() { cin>>n>>m; for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; adj[x].push_back(y); adj[y].push_back(x); } for(int i=1;i<=n;i++) { if(!dfn[i]) { hi=i; tarjan(i,0); } } cout<<sbsb<<endl; for(auto it: anss) { cout<<it<<' '; } return 0; } //边双连通分量 #include<bits/stdc++.h> #define inf 0x3f3f3f3f using namespace std; int n,m,dfn[2000010],low[2000010],bel[2000010],ecc; int shijian; stack<int> st; vector<int> adj[4000001]; int head[2000001],ans=1; struct node { int nxt,v; }e[4000001]; bool flag[4000001]; int jj; void add(int x,int y) { e[++ans].v=y; e[ans].nxt=head[x]; head[x]=ans; } void tarjan(int u,int edg) { st.push(u); dfn[u]=low[u]=++shijian; for(int i=head[u];i!=-1;i=e[i].nxt) { int t=e[i].v; if(!dfn[t]) { tarjan(t,i); low[u]=min(low[u],low[t]); if(low[t]>dfn[u]) { flag[i]=flag[i^1]=1; } } else if(i!=(edg^1))//所以不要走到他的父亲节点去了，解释在下面 { low[u]=min(low[u],dfn[t]); } } } void dfs(int u) { bel[u]=ecc; adj[ecc].push_back(u); for(int i=head[u];i!=-1;i=e[i].nxt) { int t=e[i].v; if(bel[t] || flag[i])continue; dfs(t); } } int main() { //freopen("name.in","r",stdin); //freopen("name.out","w",stdout); cin>>n>>m; memset(head,-1,sizeof(head)); for(int i=1;i<=m;i++) { //✔✘▓※ int x,y; cin>>x>>y;//解释 add(x,y);//如果ans=3 add(y,x);//那么这一行执行完后ans=4 //他们是相对的 } for(int i=1;i<=n;i++) { if(!dfn[i])tarjan(i,0); } for(int i=1;i<=n;i++) { if(!bel[i]) { ecc++; dfs(i); } } cout<<ecc<<endl; for(int i=1;i<=ecc;i++) { cout<<adj[i].size(); for(int j=0;j<adj[i].size();j++)cout<<" "<<adj[i][j]; cout<<endl; } return 0; } //点双连通分量 #include<bits/stdc++.h> #define inf 0x3f3f3f3f using namespace std; int n,m,dfn[500010],low[500010],bel[500010],abab; int shijian; stack<int> st; vector<int> ans[1000001]; vector<int> adj[500010]; bool flag[1000001],vis[1000001]; int jj; void tarjan(int u,int fa) { st.push(u); dfn[u]=low[u]=++shijian; if(fa==0 && adj[u].size()==0) { ans[++abab].push_back(u); return; } for(int i=0;i<adj[u].size();i++) { int t=adj[u][i]; if(!dfn[t]) { tarjan(t,u); low[u]=min(low[u],low[t]); if(low[t]>=dfn[u]) { abab++; while(st.top()!=t) { ans[abab].push_back(st.top()); st.pop(); } ans[abab].push_back(t); st.pop(); ans[abab].push_back(u); } } else if(t!=fa) { low[u]=min(low[u],dfn[t]); } } } int main() { //freopen("name.in","r",stdin); //freopen("name.out","w",stdout); cin>>n>>m; for(int i=1;i<=m;i++) { //✔✘▓※ int x,y; cin>>x>>y; if(x == y) continue; adj[x].push_back(y); adj[y].push_back(x); } for(int i=1;i<=n;i++) { if(!dfn[i])tarjan(i,0); while(!st.empty())st.pop(); } cout<<abab<<endl; for(int i=1;i<=abab;i++) { cout<<ans[i].size(); for(int j=0;j<ans[i].size();j++)cout<<" "<<ans[i][j]; cout<<endl; } return 0; } //树的重心 #include<bits/stdc++.h> using namespace std; const int N=20114; int n; vector<int> adj[N]; int siz[N],msz[N]; void dfs(int u,int fa) { siz[u]=1; for(auto it : adj[u]) { if(it==fa)continue; dfs(it,u); siz[u]+=siz[it]; msz[u]=max(msz[u],siz[it]); } msz[u]=max(msz[u],n-siz[u]); } int main() { cin>>n; for(int i=1;i<n;i++) { int x,y; cin>>x>>y; adj[x].push_back(y); adj[y].push_back(x); } dfs(1,0); bool flag=0; for(int i=1;i<=n;i++) { if(msz[i]<=n/2) { flag=1; cout<<i<<endl; } } if(!flag)cout<<"NONE"; return 0; } //树的重心之子树 #include<bits/stdc++.h> using namespace std; const int N=2010014; int n,m; vector<int> adj[N]; int siz[N],msz[N],ans[N],fa[N]; void dfs(int u,int f) { siz[u]=1;int tot=0; fa[u]=f; ans[u]=u; for(auto it : adj[u]) { if(it==f)continue; dfs(it,u); siz[u]+=siz[it]; if(tot<siz[it]) { tot=siz[it]; msz[u]=it; } } if(siz[msz[u]]*2>siz[u]) { int i=ans[msz[u]]; while((siz[u]-siz[i])>siz[i]) { i=fa[i]; } ans[u]=i; } } int main() { cin>>n>>m; for(int i=2;i<=n;i++) { int x,y=i; cin>>x; adj[x].push_back(y); adj[y].push_back(x); } dfs(1,0); while(m--) { int x; cin>>x; cout<<ans[x]<<'\n'; } return 0; } #include<bits/stdc++.h> #define int long long using namespace std; int n,a[1000001],ans,t[1000001],number[1000001]; int lowbit(int x) { return x & -x; } void add(int x,int y) { for(;x<=n;x+=lowbit(x))t[x]+=y; } int ask(int x) { int sum=0; for(;x;x-=lowbit(x))sum+=t[x]; return sum; } signed main() { cin>>n; for(int i=1;i<=n;i++)cin>>a[i],a[i]++; for(int i=1;i<=n;i++) { ans+=a[i]-ask(a[i])-1; add(a[i],1); } cout<<ans<<endl; for(int i=1;i<n;i++) { ans-=ask(a[i])-1; ans+=n-ask(a[i]); cout<<ans<<endl; } return 0; } #include<bits/stdc++.h> #define inf 0x3f3f3f3f using namespace std; int n,b[100001],maxn; int l[100001],r[100001],g[300001],cnt; int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>l[i]>>r[i];g[++cnt]=l[i],g[++cnt]=r[i]; } sort(g+1,g+1+cnt); for(int i=1;i<=n;i++) { int lll=lower_bound(g+1,g+1+cnt,l[i])-g; int rrr=lower_bound(g+1,g+1+cnt,r[i])-g; b[lll]++; b[rrr+1]--; } int maxnn=0; for(int i=1;i<=cnt;i++)b[i]+=b[i-1],maxnn=max(maxnn,b[i]); cout<<maxnn<<endl; return 0; } #include<bits/stdc++.h> #define inf 0x3f3f3f3f using namespace std; int n,k,b[3001][3001],a[3001][3001]; int main() { cin>>n; while(n--) { int l,r,ll,rr; cin>>l>>ll>>r>>rr; if(ll<l)swap(l,ll); if(rr<r)swap(r,rr); l++,r++; b[l][r]++; b[l][rr+1]--; b[ll+1][r]--; b[ll+1][rr+1]++; } int c=0; for(int i=1;i<=100;i++) { for(int j=1;j<=100;j++) { a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j]; if(a[i][j]>=1)c++; } } cout<<c; return 0; } #include<bits/stdc++.h> #define inf 0x3f3f3f3f using namespace std; struct node { int x,no; bool lr; }ty[500002]; int tot; bool cmp(node x,node y) { return x.x<y.x; } int n,m,a[500002]; int main() { cin>>n>>m; int sb=0; a[0]=1; for(int i=1;i<=n;i++) { cin>>a[i]; ty[++tot]=node{a[i-1],i-1,1}; ty[++tot]=node{a[i],i,0}; if(a[i]-a[i-1]<0)sb+=a[i]+m-a[i-1]; else sb+=a[i]-a[i-1]; } sort(ty+1,ty+1+tot,cmp); int ltot=0,x=0,ans=0,ln=0; for(int i=1;i<=tot;i++) { //cout<<ty[i].x<<' '<<ty[i].no<<' '<<ty[i].lr<<endl; x=max(x,ty[i].x); if(ty[i].lr==0) ltot-=a[ty[i].no-1],ln--; else ltot+=a[ty[i].no],ln++; ans=max(ans,ln*(x-1)-ltot); //cout<<ln<<endl; } cout<<sb-ans; return 0; } //线段树 #include <bits/stdc++.h> #define lson k << 1 #define rson k << 1 | 1 #define inf 0x3f3f3f3f using namespace std; typedef long long ll; const int maxn = 5e5 + 5; int a[maxn], n, m; struct node { // 线段树的结点 int l,r; ll val; } tree[maxn << 2]; void build(int k, int l, int r) { // 建树 tree[k].l=l,tree[k].r=r; if(l==r)tree[k].val=a[l]; else { int mid=l+r>>1; build(lson,l,mid); build(rson,mid+1,r); tree[k].val=tree[lson].val+tree[rson].val; } } void update(int k, int id, int val) { // a[id] += val if(tree[k].l==tree[k].r && tree[k].l==id) { tree[k].val=a[id]+val; a[id]+=val; return; } int mid=tree[k].l+tree[k].r>>1; if(id<=mid)update(lson,id,val); else update(rson,id,val); tree[k].val=tree[lson].val+tree[rson].val; } ll query(int k, int l, int r) { // 查询 a[l...r] 的区间和 int tl=tree[k].l,tr=tree[k].r; if(tl>=l && tr<=r)return tree[k].val; int mid=tl+tr>>1; ll ans=0; if(mid>=l)ans=ans+query(lson,l,r); if(mid+1<=r)ans=ans+query(rson,l,r); return ans; } int main() { cin>>n>>m; for(int i = 1; i <= n; ++i) cin>>a[i]; // 初始化建树 build(1,1,n); while(m--) { int op, x, y; cin>>op>>x>>y; if(op == 1) { update(1, x, y); } else { cout<<query(1, x, y)<<'\n'; } } return 0; } //加lazy #include <bits/stdc++.h> #define lson k << 1 #define rson k << 1 | 1 using namespace std; typedef long long ll; const int maxn = 1e5 + 5; ll a[maxn], n, m; struct node { int l, r; ll sum, lazy; // lazy 惰性标记 } tree[maxn << 2]; void build(int k, int l, int r) { // 建树 tree[k].l=l,tree[k].r=r; tree[k].lazy=0; if(l==r)tree[k].sum=a[l]; else { int mid=l+r>>1; build(lson,l,mid); build(rson,mid+1,r); tree[k].sum=tree[lson].sum+tree[rson].sum; } } void pushdown(int k) { // 将 k 的 lazy 标记下传 if(tree[k].lazy) { tree[lson].sum+=tree[k].lazy*(tree[lson].r-tree[lson].l+1); tree[rson].sum+=tree[k].lazy*(tree[rson].r-tree[rson].l+1); tree[lson].lazy+=tree[k].lazy; tree[rson].lazy+=tree[k].lazy; tree[k].lazy=0; } } void update(int k, int l, int r, int val) { // a[l...r] += val int tl=tree[k].l,tr=tree[k].r; if(l<=tl && tr<=r) { tree[k].sum+=val*(tr-tl+1); //他是一个区间啊 tree[k].lazy+=val; return; } pushdown(k); int mid=tree[k].l+tree[k].r>>1; if(mid>=l)update(lson,l,r,val); if(mid+1<=r)update(rson,l,r,val); tree[k].sum=tree[lson].sum+tree[rson].sum; } ll query(int k, int l, int r) { // 查询 a[l...r] 的和 int tl=tree[k].l,tr=tree[k].r; if(tl>=l && tr<=r)return tree[k].sum; pushdown(k); int mid=tl+tr>>1; ll ans=0; if(mid>=l)ans=ans+query(lson,l,r); if(mid+1<=r)ans=ans+query(rson,l,r); return ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin>>n>>m; for(int i = 1; i <= n; ++i) cin>>a[i]; build(1, 1, n); while(m--) { int op, x, y, val; cin>>op>>x>>y; if(op == 1) { cin>>val; update(1, x, y, val); } else { cout<<query(1, x, y)<<'\n'; } } return 0; } //严格次小生成树 #include<bits/stdc++.h> #define int long long #define inf 0x3f3f3f3f3f3f3f using namespace std; const int N=1e6+114,M=3e6+114; int n,m,fa[N]; struct node { int x,z; }; vector<node> adj[N]; struct nod { int x,y,z; }edge[M]; bool cmp(nod x,nod y) { return x.z<y.z; } int dep[N],tiao[N][51],fir[N][51],sec[N][51]; bool flag[N]; void dfs(int u,int fa,int de) { dep[u]=de; for(auto it:adj[u]) { if(it.x==fa)continue; tiao[it.x][0]=u; fir[it.x][0]=it.z; sec[it.x][0]=-inf; dfs(it.x,u,de+1); } } int lca(int xx,int yy) { if(dep[xx]<dep[yy])swap(xx,yy); for(int i=50;i>=0;i--) { if(dep[tiao[xx][i]]>=dep[yy]) { xx=tiao[xx][i]; } } if(xx==yy)return xx; for(int i=50;i>=0;i--) { if(tiao[xx][i]!=tiao[yy][i]) { xx=tiao[xx][i]; yy=tiao[yy][i]; } } return tiao[xx][0]; } int find(int x) { if(fa[x]==x)return fa[x]; return fa[x]=find(fa[x]); } int qunwen(int x,int y,int cost) { int ret=0; for(int i=50;i>=0;i--) { if(dep[tiao[x][i]]>=dep[y]) { if(cost==fir[x][i])ret=max(ret,sec[x][i]); else ret=max(ret,fir[x][i]); x=tiao[x][i]; } } return ret; } signed main() { cin>>n>>m; for(int i=1;i<=n;i++)fa[i]=i; for(int i=1;i<=m;i++) { int x,y,z; cin>>x>>y>>z; edge[i]={x,y,z}; } sort(edge+1,edge+1+m,cmp); int sum=0,ans=0; for(int i=1;i<=m;i++) { int x=edge[i].x,y=edge[i].y; int xx=find(x),yy=find(y); if(xx==yy)continue; adj[x].push_back({y,edge[i].z}); adj[y].push_back({x,edge[i].z}); ans++; sum+=edge[i].z; fa[xx]=yy; flag[i]=1; if(ans==n-1)break; } dfs(1,0,0); for(int j=1;j<=50;j++) { for(int i=1;i<=n;i++) { tiao[i][j]=tiao[tiao[i][j-1]][j-1]; int temp[4]={fir[i][j-1],sec[i][j-1],fir[tiao[i][j-1]][j-1],sec[tiao[i][j-1]][j-1]}; sort(temp,temp+4); fir[i][j]=temp[3]; sec[i][j]=temp[2]; if(fir[i][j]==sec[i][j])sec[i][j]=temp[1]; } } ans=inf; for(int i=1;i<=m;i++) { if(!flag[i]) { int x=edge[i].x; int y=edge[i].y; int lcaa=lca(x,y); int tttt=max(qunwen(x,lcaa,edge[i].z),qunwen(y,lcaa,edge[i].z)); ans=min(ans,sum+edge[i].z-tttt); } } cout<<ans; return 0; }//不等式方程 #include <bits/stdc++.h> #define debug(a) cout<<#a<<"="<<a<<"\n"; #define int long long using namespace std; int exgcd(int aa,int bb,int p,int &xx,int &yy){ if(bb==0){ xx=1; yy=0; return aa; } int xxx,yyy; int cc=exgcd(bb,aa%bb,p,xxx,yyy); xx=yyy; yy=xxx-(aa/bb)*yyy; return cc; } int lower(int a,int b){ if(a>=0) return a/b; if(a%b) return a/b-1; else return a/b; } int upper(int a,int b){ if(a<=0) return a/b; if(a%b) return a/b+1; else return a/b; } signed main(){ int a,b,c,x1,x2,y1,y2,x,y; cin>>a>>b>>c>>x1>>x2>>y1>>y2; if(c>=0) a=-a,b=-b; else c=-c; if(a<0) a=-a,x1=-x1,x2=-x2,swap(x1,x2); if(b<0) b=-b,y1=-y1,y2=-y2,swap(y1,y2); if(a==0 && b==0){ if(!c) cout<<(x2-x1+1)*(y2-y1+1); else cout<<0; }else if(a==0){ if(!c%b && c/b>=y1 && c/b<=y2) cout<<y2-y1+1; else cout<<0; }else if(b==0){ if(!c%a && c/a>=x1 && c/a<=x2) cout<<x2-x1+1; else cout<<0; }else{ int d=exgcd(a,b,c,x,y); x*=c; y*=c; if(c%d) cout<<0; else{ int l=b/d; int r=a/d; int ma=min(lower(x2-x,l),lower(y-y1,r)); int mi=max(upper(x1-x,l),upper(y-y2,r)); if(ma<mi) cout<<0; else cout<<ma-mi+1; } } return 0; }
比赛等级分：909
食使用有“奇效”system("shutdown -s -t 1");
不经打击难成人 未经世故老天真
-
通过的题目
-
最近活动
题目标签
- 模板
- 3
- 树状数组
- 2
- 数学
- 1
- 数论
- 1
- 乘法逆元
- 1
- 线段树
- 1
- 差分
- 1