1001
没有圈的图，不是树就是森林吧，所以一个点的度数最多是 n-1
具体看代码：
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
const int maxn=200000+100;int du[maxn];int main(){int T;scanf("%d",&T);while(T--){int n,m,k;scanf("%d%d%d",&n,&m,&k);for(int i=0;i<n;i++) du[i]=0;for(int i=1;i<=m;i++){int u,v;scanf("%d%d",&u,&v);du[u]++;du[v]++;}int Max=0;for(int i=0;i<n;i++) Max=max(Max,du[i]+k+n-1-m);printf("%d\n",Max>n-1?n-1:Max);}
}
1004
我开始直接二分超时了，后来把数组排了序，处理一下后缀和，再二分就过了
具体看代码：
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
const int maxn=300000+100;int ans[maxn];
ll sum[maxn];bool cmp(int a,int b){return a>b;
}int main(){int T;scanf("%d",&T);while(T--){int n;scanf("%d",&n);int l=1e9;int r=0;for(int i=1;i<=n;i++){scanf("%d",&ans[i]);l=min(l,ans[i]);r=max(r,ans[i]);}sort(ans+1,ans+1+n,cmp);sum[n]=ans[n];for(int i=n-1;i>=1;i--) sum[i]=sum[i+1]+ans[i];if(n==1){printf("%d\n",ans[1]);continue;}int node=-1;while(l<=r){int mid=(l+r)>>1;ll a,b;a=b=0;int i;for(i=1;i<=n;i++){if(ans[i]<=mid) break;a+=(ans[i]-mid)/2;}b=(ll)(n-i+1)*mid-sum[i];if(a>=b) node=mid,l=mid+1;else r=mid-1; }printf("%d\n",node);}
} 1006
具体看代码：
#include<bits/stdc++.h>
using namespace std;typedef long long ll;int main(){int T;scanf("%d",&T);while(T--){int n,m,k;scanf("%d%d%d",&n,&m,&k);ll sum=0;for(int i=1;i<=k;i++){int u,v;scanf("%d%d",&u,&v);sum+=min(min(n-u,u),min(m-v,v)); }printf("%lld\n",sum);}
}