b所有数模k，记录出现次数即可
#include<bits/stdc++.h> using namespace std; int main(){ int n,k,a[200005]; int cnt[200]={}; cin>>n>>k; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++) cnt[a[i]%k]++; int ans=cnt[0]/2; int l=1,r=k-1; while(l<r){ ans+=min(cnt[l],cnt[r]); l++,r--; } if(l==r) ans+=cnt[l]/2; cout<<ans*2<<endl; }
c尺取
#include<bits/stdc++.h> using namespace std; #define maxn 200005 int cmp(int a,int b){return a<b; } int main(){ int n,a[maxn]; scanf("%d",&n); for(int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+1+n); int l=1,r=0,ans=0; while(1){ r++; if(r>n)break; if(a[r]-a[l]<=5)ans=max(ans,r-l+1); if(a[r]-a[l]>5)l++; } cout<<ans; return 0; }
d，用map<pair<ll,ll>,int>来统计二元组<a[i]/gcd,b[i]/gcd>的最大出现次数即可，注意特判
#include<bits/stdc++.h> using namespace std; #define maxn 200005 #define ll long long ll n,a[maxn],b[maxn]; map<pair<ll,ll>,ll>mp; int main(){ cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; for(int j=1;j<=n;j++)cin>>b[j]; ll cnt=0,ans=0,x=0; for(int i=1;i<=n;i++){ if(a[i]==0 && b[i]==0)cnt++;//权是0 else if(a[i]==0 && b[i]!=0) continue;//无解 else if(b[i]==0)x++; //c必须是0 else { ll tmp=__gcd(a[i],b[i]); pair<ll,ll> p=make_pair(b[i]/tmp,a[i]/tmp); mp[p]++;ans=max((ll)ans,mp[p]); } } if(cnt==n)cout<<cnt; else cout<<max(x+cnt,ans+cnt); }
e，线性dp
/* l[i]表示选择以第i个为最大能力成员的团队中能力最小的成员的下标是什么 阶段k，状态j表示选择第j个成员作为第k组能力最大的成员 那么第k组的范围就是[l[j],j],dp[k][j]=len[j]+max(dp[k-1][l[j]-i]),i小于l[j]即可) */ #include<bits/stdc++.h> using namespace std; #define maxn 5005 int n,k,dp[maxn][maxn],a[maxn],l[maxn]; int main(){ cin>>n>>k; for(int i=1;i<=n;i++)cin>>a[i]; sort(a+1,a+1+n);a[0]=-1; for(int i=1;i<=n;i++) l[i]=lower_bound(a+1,a+1+n,a[i]-5)-a; int ans=0; for(int i=1;i<=k;i++){ int tmp[maxn]={}; for(int j=1;j<=n;j++) tmp[j]=max(tmp[j-1],dp[i-1][j]); for(int j=i;j<=n;j++){ dp[i][j]=(j-l[j]+1)+tmp[l[j]-1]; ans=max(dp[i][j],ans); } } cout<<ans<<endl; }
f1找最大点度数最大的生成树
#include<bits/stdc++.h> using namespace std; #define maxn 200005 struct Edge{int to,nxt;}edge[maxn<<1]; int head[maxn],tot; void init(){memset(head,-1,sizeof head);tot++;} void addedge(int u,int v){ edge[tot].to=v;edge[tot].nxt=head[u];head[u]=tot++; } int n,m,degree[maxn],vis[maxn]; void dfs(int u){ for(int i=head[u];i!=-1;i=edge[i].nxt){ int v=edge[i].to; if(vis[v])continue; else { vis[v]=1; cout<<u<<" "<<v<<endl; dfs(v); } } } int main(){ cin>>n>>m; init(); for(int i=1;i<=m;i++){ int u,v; cin>>u>>v; degree[u]++; degree[v]++; addedge(u,v); addedge(v,u); } int id,Max=0; for(int i=1;i<=n;i++) if(degree[i]>Max){ Max=degree[i]; id=i; } vis[id]=1; for(int i=head[id];i!=-1;i=edge[i].nxt) vis[edge[i].to]=1; for(int i=head[id];i!=-1;i=edge[i].nxt){ int v=edge[i].to; cout<<id<<" "<<v<<endl; dfs(v); } }
f2
/* 给定一个无向连接图，求出1的度为d的生成树 删掉结点1，对剩下结点染色 不成立的情况： 1的度小于d 联通块大于d 1能连上的联通块小于d */ #include<bits/stdc++.h> #include<vector> using namespace std; #define maxn 200005 struct Edge{int to,nxt;}edge[maxn<<1]; int head[maxn],c[maxn],cnt,d,totc,n,m; void init(){ memset(head,-1,sizeof head); totc=0; } void addedge(int u,int v){ edge[totc].to=v;edge[totc].nxt=head[u];head[u]=totc++; } void dfs(int u){ c[u]=cnt; for(int i=head[u];i!=-1;i=edge[i].nxt){ int v=edge[i].to; if(c[v]||v==1)continue; dfs(v); } } int vis[maxn]; struct A{int u,v; }ans[maxn]; void dfs1(int u){ for(int i=head[u];i!=-1;i=edge[i].nxt){ int v=edge[i].to; if(vis[v])continue; vis[v]=1; cout<<u<<" "<<v<<' '; dfs1(v); } } int main(){ cin>>n>>m>>d; init(); int tmp=0,flag[maxn]={}; for(int i=1;i<=m;i++){ int u,v; cin>>u>>v; if(v==1)swap(u,v); if(u==1)flag[v]=1,tmp++; addedge(u,v); addedge(v,u); } if(tmp<d){ puts("NO"); return 0; } for(int i=2;i<=n;i++) if(c[i]==0) ++cnt,dfs(i); if(cnt>d){ puts("NO"); return 0; } int tot=0,link[maxn]={}; for(int i=2;i<=n;i++){ if(flag[i] && link[c[i]]==0){ ans[++tot].u=1; //cout<<tot<<' '; ans[tot].v=i; link[c[i]]=1; vis[i]=1; } } //把剩下的度用完 for(int i=2;i<=n;i++){ if(tot==d)break; if(flag[i] && vis[i]==0){ //cout<<tot<<' '; ans[++tot].u=1; ans[tot].v=i; vis[i]=1; } } if(tot<d){ puts("NO"); return 0; } for(int i=1;i<=cnt;i++) if(link[i]==0){ puts("NO"); return 0; } puts("YES"); for(int i=1;i<=tot;i++) cout<<ans[i].u<<" "<<ans[i].v<<' '; vis[1]=1; for(int u=2;u<=n;u++) if(vis[u]){ dfs1(u); } }