L3-001 凑零钱
题解：感觉很不错的01满背包问题，dp[i]表示重i时的最多硬币数，先排序，根据题意，字典序最小那么意思就是满载的情况下硬币越多越好。那么只要01背包标记路程就可以了，最后dfs回溯。(个人感觉比别的题解乱七八糟降序排序好理解的多)。
#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 a[maxn],pre[maxn],ans[maxn],dp[maxn]; void dfs(int x){ if(!pre[x]){ cout<<ans[x];return; }else{ dfs(pre[x]); cout<<" "<<ans[x]; } } int main(){ int n,m;cin>>n>>m; rep(i,1,n) cin>>a[i]; sort(a+1,a+n+1); mem(pre,-1);mem(dp,-INF); dp[0]=0; for(int i=1;i<=n;i++){ for(int j=m;j>=a[i];j--){ if(dp[j]<=dp[j-a[i]]+1){ dp[j]=dp[j-a[i]]+1; ans[j]=a[i]; pre[j]=j-a[i]; } } } if(dp[m]>0){ dfs(m); }else{ puts("No Solution"); } }
L3-002 特殊堆栈
题解：很好的STL题，弥补了我在STL上的漏洞。我们可以在vector中二分找到对应≥x 的位置地址 it，然后v.insert(it,x)，就能保证vector的单调性啦。很不错
#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 main(){ int T;cin>>T; vector<int> vec,v; while(T--){ string s;cin>>s; if(s=="Push"){ int x;cin>>x; auto it=lower_bound(v.begin(),v.end(),x); v.insert(it,x); vec.push_back(x); } else if(s=="Pop"){ if(vec.size()==0) puts("Invalid"); else{ auto it=lower_bound(v.begin(),v.end(),vec[vec.size()-1]); v.erase(it); cout<<vec[vec.size()-1]<<endl; vec.pop_back(); } }else{ if(vec.size()==0) puts("Invalid"); else{ if(v.size()%2==0) cout<<v[v.size()/2-1]<<endl; else cout<<v[v.size()/2]<<endl; } } } }
L3-003 社交集群
题解：并查集，因为每一行肯定是属于一类的，所以我们先把那些兴趣用并查集找到各自的祖先。最后从1-n遍历，一共有几个一样的祖先以及不同的祖先数，排序就行。这个题并查集时间复杂度会比用图论做法做快的多。L2我记得有一道题可以用图论写法水过去，这次n给的限制比较大，得用并查集
#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 a[maxn],fa[maxn]; bool vis[maxn]; int find(int x){ while(x!=fa[x]) x=fa[x]=fa[fa[x]]; return x; } int main(){ int n;scanf("%d",&n); for(int i=1;i<=1000;i++) fa[i]=i; for(int i=1;i<=n;i++){ int k;scanf("%d:%d",&k,&a[i]); vis[a[i]]=true; for(int j=1;j<k;j++){ int x;scanf("%d",&x);vis[x]=true; int eu=find(a[i]),ev=find(x); if(eu!=ev) fa[ev]=eu; } } map<int,int> mp; vector<int> vec,v; for(int i=1;i<=n;i++){ int x=find(a[i]); if(!mp.count(x)) mp[x]=1,vec.pb(x); else mp[x]+=1; } cout<<vec.size()<<endl; for(auto it:vec){ v.pb(mp[it]); } sort(v.rbegin(),v.rend()); for(int i=0;i<v.size();i++){ if(i<v.size()-1) cout<<v[i]<<" "; else cout<<v[i]<<endl; } }
L3-004 肿瘤诊断
题解：这个题看一眼就知道是3维bfs，但是算一下吧，空间大概需要1e7这样就不太敢写，不过后来想想应该也不会卡这个
#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 a[62][1290][130]; int vis[62][1290][130]; struct node{ int x,y,z; }p; int dx[6]={1,0,0,0,0,-1}; int dy[6]={0,1,-1,0,0,0}; int dz[6]={0,0,0,-1,1,0}; int n,m,l,t;ll ans; void bfs(int xx,int yy,int zz){ ll cnt=0;vis[xx][yy][zz]=1; queue<node> q;q.push({xx,yy,zz}); while(!q.empty()){ node now=q.front();q.pop();++cnt; for(int i=0;i<6;i++){ int x=now.x+dx[i],y=now.y+dy[i],z=now.z+dz[i]; if(x>=1&&x<=l&&y>=1&&y<=n&&z>=1&&z<=m&&a[x][y][z]==1&&!vis[x][y][z]){ q.push({x,y,z});vis[x][y][z]=1; } } } if(cnt>=t) ans+=cnt; } int main(){ scanf("%d%d%d%d",&n,&m,&l,&t);ans=0; rep(k,1,l) rep(i,1,n) rep(j,1,m) scanf("%d",&a[k][i][j]); rep(k,1,l) rep(i,1,n) rep(j,1,m) if(a[k][i][j]==1&&!vis[k][i][j]){ bfs(k,i,j); } cout<<ans<<endl; }
L3-005 垃圾箱分布
题解：对每个垃圾桶跑dijkstra，然后维护最远距离，以及到所有点距离之和，写起来有点烦，懒得写了
L3-006 秋风一刀斩
题解：计算几何，略，丢给队友
L3-007 天梯地图
题解：2次dijkstra就行，一次存路程，一次存时间，记录每次的pre，和可到达最短路径的数目，和L2-001类似
L3-008 喊山
题解：因为询问的点k只有10，而且n≤1e4，所以你每次询问的时候直接暴力bfs跑标记层数就行。