前言:L2部分我感觉更侧重于算法基础或者思维,L1部分偏语法。L2一些数据结构课本题我都不写了,没意思。
L2-001 紧急救援
题解:因为没有负边权,所以我使用的是最优化的优先队列dijkstra算法。设num[i]表示到达i点最短路的路径数量,sum[i]表示到达i点最短路的时候的最大权值和。当d[v]>d[u]+edge[i].w时,更新d[v]值,同时num[v]=num[u] . sum[v]=sum[u]+a[v]。如果d[v]=d[u]+edge[i].w时,需要更新的是num[v]的数量,即num[v]+=num[u],同时可以更新sum的情况,if(sum[v]<sum[u]+a[v]) sum[v]=sum[u]+a[v];具体看代码
#include<bits/stdc++.h> #pragma GCC optimize(2) #define ll long long #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,n,a) for(int i=n;i>=a;i--) #define endl ' ' #define white 0 #define grey 1 #define black 2 #define eps 0.000000001 #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) #define IO ios::sync_with_stdio(false);cin.tie(0); using namespace std; const int INF=0x3f3f3f3f; const ll inf=0x3f3f3f3f3f3f3f3f; const int mod=1e9+7; const int maxn=3e5+5; int tot,head[maxn]; struct E{ int to,next,w; }edge[maxn<<1]; void add(int u,int v,int w){ edge[tot].to=v; edge[tot].w=w; edge[tot].next=head[u]; head[u]=tot++; } int n,m,S,T; int a[maxn],d[maxn],color[maxn],pre[maxn]; int num[maxn],sum[maxn]; priority_queue<pair<int,int> >q; void dijkstra(int s){ for(int i=1;i<=n;i++) color[i]=white,d[i]=INF,pre[i]=s; q.push({0,s});d[s]=0;color[s]=grey; num[s]=1;sum[s]=a[s];pre[s]=0; while(!q.empty()){ pair<int,int> f=q.top();q.pop(); int u=f.second; color[u]=black; if(d[u]<(-1)*f.first) continue; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(color[v]==black) continue; if(d[v]>d[u]+edge[i].w){ d[v]=d[u]+edge[i].w; pre[v]=u; num[v]=num[u]; sum[v]=sum[u]+a[v]; color[v]=grey; q.push({(-1)*d[v],v}); } else if(d[v]==d[u]+edge[i].w){ num[v]+=num[u]; if(sum[v]<sum[u]+a[v]){ sum[v]=sum[u]+a[v]; pre[v]=u; } } } } } stack<int> s; void get_path(int t){ while(t){ s.push(t-1); t=pre[t]; } } int main(){ scanf("%d%d%d%d",&n,&m,&S,&T);mem(head,-1); ++S;++T; rep(i,1,n) scanf("%d",&a[i]); rep(i,1,m){ int u,v,w;scanf("%d%d%d",&u,&v,&w); ++u;++v; add(u,v,w);add(v,u,w); } dijkstra(S); cout<<num[T]<<" "<<sum[T]<<endl; get_path(T); while(!s.empty()){ int cur=s.top();s.pop(); if(s.size()) cout<<cur<<" "; else cout<<cur; } }
L2-002 链表去重
#include<bits/stdc++.h> #pragma GCC optimize(2) #define ll long long #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,n,a) for(int i=n;i>=a;i--) #define endl ' ' #define eps 0.000000001 #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) #define IO ios::sync_with_stdio(false);cin.tie(0); using namespace std; const int INF=0x3f3f3f3f; const ll inf=0x3f3f3f3f3f3f3f3f; const int mod=1e9+7; const int maxn=1e5+5; struct Node{ int address,key,next,num; }node[maxn]; bool vis[maxn]; bool cmp(Node a,Node b){ return a.num<b.num; } int main(){ int head,n;scanf("%d%d",&head,&n); for(int i=0;i<maxn;i++) node[i].num=INF; for(int i=0;i<n;i++){ int a;scanf("%d",&a); scanf("%d%d",&node[a].key,&node[a].next); node[a].address=a; } int k1=0,k2=0; for(int i=head;i!=-1;i=node[i].next){ if(!vis[abs(node[i].key)]){ vis[abs(node[i].key)]=true; node[i].num=k1++; }else{ node[i].num=maxn+k2; k2++; } } sort(node,node+maxn,cmp); int k=k1+k2; for(int i=0;i<k;i++){ if(i!=k1-1&&i!=k-1){ printf("%05d %d %05d ",node[i].address,node[i].key,node[i+1].address); }else{ printf("%05d %d -1 ",node[i].address,node[i].key); } } }
L2-003 月饼
坑点:注意正数与正整数的区别,用double输入比较安全
#include<bits/stdc++.h> #pragma GCC optimize(2) #define ll long long #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,n,a) for(int i=n;i>=a;i--) #define endl ' ' #define eps 0.000000001 #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) #define IO ios::sync_with_stdio(false);cin.tie(0); using namespace std; const int INF=0x3f3f3f3f; const ll inf=0x3f3f3f3f3f3f3f3f; const int mod=1e9+7; const int maxn=1e5+5; double w[maxn],p[maxn];double s[maxn]; struct Node{ double s,t; }node[maxn]; bool cmp(Node a,Node b){ return a.s>b.s; } int main(){ int n,weight;scanf("%d%d",&n,&weight); rep(i,1,n) scanf("%lf",&w[i]); rep(i,1,n) scanf("%lf",&p[i]); rep(i,1,n){ node[i].s=1.00*p[i]/w[i]; node[i].t=w[i]; } sort(node+1,node+n+1,cmp); double ans=0; rep(i,1,n){ if(weight>=node[i].t){ weight-=node[i].t; ans+=node[i].t*node[i].s; }else{ ans+=weight*node[i].s; weight=0; } if(!weight) break; } printf("%.2lf ",ans); }
L2-005 集合相似度
坑点:能尽量优化减少对于set的使用和遍历次数
#include<bits/stdc++.h> #pragma GCC optimize(2) #define ll long long #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,n,a) for(int i=n;i>=a;i--) #define endl ' ' #define eps 0.000000001 #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) #define IO ios::sync_with_stdio(false);cin.tie(0); using namespace std; const int INF=0x3f3f3f3f; const ll inf=0x3f3f3f3f3f3f3f3f; const int mod=1e9+7; const int maxn=1e5+5; set<int> s[maxn]; int main(){ int n;scanf("%d",&n); rep(i,1,n){ int t;scanf("%d",&t); while(t--){ int x;scanf("%d",&x); s[i].insert(x); } } int k;scanf("%d",&k); while(k--){ int a,b;scanf("%d%d",&a,&b); int cnt=0; for(auto it:s[b]){ if(s[a].count(it)) ++cnt; } double ans=1.00*cnt/(s[a].size()+s[b].size()-cnt); printf("%.2lf% ",ans*100); } }
L2-007家庭房产
题解:大模拟+bfs建边跑连通块维护连通块信息
#include<bits/stdc++.h> #pragma GCC optimize(2) #define ll long long #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,n,a) for(int i=n;i>=a;i--) #define endl ' ' #define eps 0.000000001 #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) #define IO ios::sync_with_stdio(false);cin.tie(0); using namespace std; const int INF=0x3f3f3f3f; const ll inf=0x3f3f3f3f3f3f3f3f; const int mod=1e9+7; const int maxn=1e5+5; int tot,head[maxn]; struct E{ int to,next; }edge[maxn<<2]; void add(int u,int v){ edge[tot].to=v; edge[tot].next=head[u]; head[u]=tot++; } int n,a[maxn],num[maxn],s[maxn]; bool vis[maxn]; struct node{ vector<int> vec; int num,s; int minn,t; double averT,averSIZ; }p[maxn]; void bfs(int x,int id){ queue<int> q;q.push(x); while(!q.empty()){ int now=q.front();q.pop(); p[id].vec.push_back(now); p[id].num+=num[now]; p[id].s+=s[now]; for(int i=head[now];i!=-1;i=edge[i].next){ int v=edge[i].to; if(vis[v]) continue; vis[v]=true; q.push(v); } } } bool cmp(node a,node b){ if(a.averSIZ!=b.averSIZ) return a.averSIZ>b.averSIZ; else return a.minn<b.minn; } int main(){ scanf("%d",&n);mem(head,-1); rep(i,1,n){ int id,L,R;scanf("%d%d%d",&id,&L,&R); a[id]=1; if(L!=-1) a[L]=1,add(id,L),add(L,id); if(R!=-1) a[R]=1,add(id,R),add(R,id); int k;scanf("%d",&k); while(k--){ int x;scanf("%d",&x); a[x]=1; add(id,x);add(x,id); } scanf("%d%d",&num[id],&s[id]); } int cnt=0; for(int i=0;i<=9999;i++){ if(a[i]&&!vis[i]){ vis[i]=true; bfs(i,++cnt); p[cnt].minn=i; } } for(int i=1;i<=cnt;i++){ p[i].minn=p[i].vec[0]; p[i].t=p[i].vec.size(); p[i].averT=1.000*p[i].num/p[i].t; p[i].averSIZ=1.000*p[i].s/p[i].t; } sort(p+1,p+cnt+1,cmp); cout<<cnt<<endl; rep(i,1,cnt){ printf("%04d %d %.3lf %.3lf ",p[i].minn,p[i].t,p[i].averT,p[i].averSIZ); } }
L2-008 最长对称子串
题解:马拉车算法模板裸题,输入用getline输入
#include <bits/stdc++.h> using namespace std; const int maxn=1e7+5; string s; char str[maxn<<1]; int p[maxn<<1]; int init(){ int len=s.length(); str[0]='@',str[1]='#'; int j=2; for(int i=0;i<len;i++) str[j++]=s[i],str[j++]='#'; str[j]='