第1题.n个数最多能分成多少个质数之和
ac:100 思路:分成n个2
#include <bits/stdc++.h> using namespace std; #define ll long long int main(){ ll sum=0,n,m; scanf("%lld",&n); for(int i=1;i<=n;i++){ scanf("%lld",&m); sum+=m/2; } printf("%lld\n",sum); }第2题:序列最小 ac100
思路:模拟当前位置的数
#include <bits/stdc++.h> using namespace std; #define ll long long const int N=1e5+5; int a[N],b[N],vis[N]; int main(){ int n,m; cin>>n>>m; for(int i=1;i<=m;i++){ cin>>a[i]; vis[a[i]]=1; } a[m+1]=1e9; int i=1,k=1,c=0; while(i<=n){ if(vis[i]==1) i++; else{ if(i>a[k]) b[++c]=a[k],k++; else b[++c]=i,i++; } } for(int i=1;i<n;i++) cout<<b[i]<<" "; cout<<b[n]<<endl; }第3题:将物品平均分给两个人,多余的丢弃,求最少丢弃的值?
ac:80 两重dfs爆栈了,应该dfs物品分给了哪个人。
#include <bits/stdc++.h> using namespace std; #define ll long long const int N=15; int a[N],b[N],vis[N]; int n; int maxx; void dfs(int pos,int sum,int pre,int cnt){ if(cnt==2&&sum>pre) return; if(sum==pre) maxx=max(maxx,sum); if(pos==n+1){ if(cnt==2){ return; } if(cnt==1){ dfs(1,0,sum,2); return; } } if(vis[pos]==0){ vis[pos]=1; dfs(pos+1,sum+a[pos],pre,cnt); vis[pos]=0; } dfs(pos+1,sum,pre,cnt); } int main(){ int T,m; cin>>T; while(T--){ cin>>n; int sum=0; maxx=0; for(int i=1;i<=n;i++) vis[i]=0; for(int i=1;i<=n;i++){ cin>>a[i]; sum+=a[i]; } sort(a+1,a+1+n); dfs(1,0,0,1); cout<<sum-2*maxx<<endl; } }
第4题:求构成的生成树最大边和最小边的差值最小
ac:100 思路:枚举边求最小生成树 复杂度m*n*o(并查集复杂度)
#include <bits/stdc++.h> using namespace std; #define ll long long const int N=1005; int p[N],n,m,minn=1e9; struct node{ int u,v,c; }a[N*3]; bool cmp(node a,node b){ if(a.c!=b.c) return a.c<b.c; return a.u<b.u; } int find(int x){ return x==p[x]?x:p[x]=find(p[x]); } bool fun(int s){ if(n==1){ minn=0; return true; } for(int i=1;i<=n;i++) p[i]=i; int cnt=0; for(int i=s;i<=m;i++){ int x=find(a[i].u),y=find(a[i].v); if(x!=y){ p[x]=y; cnt++; } if(cnt==n-1){ minn=min(minn,a[i].c-a[s].c); return true; } } return false; } int main(){ cin>>n>>m; for(int i=1,u,v,c;i<=m;i++) cin>>a[i].u>>a[i].v>>a[i].c; sort(a+1,a+1+m,cmp); for(int i=1;i<=m;i++){ bool c=fun(i); if(c==false) break; } cout<<minn<<endl; }
全部评论
(2) 回帖