?本题比赛的时候对算法的测试不够深刻,导致wa的次数过多,我果然还是充满着新手的气息。本题意为给定点数量n,边数量m,dis(i,j)意为从i至j最少需要经历边的数量,如果两边没有边相连则dis(i,j) = n求所有的dis(i,j)之和最小为多少。
?直接考虑完全图,而n个点完全图所需的边的数量为n*(n - 1)/ 2如果m>=n*(n - 1)则所求边数直接为每个点和剩下所有点分别相连数量,知共有n个点则为n * (n - 1)。
?当m不满足上述情况时需要分两种情况。看边的数量是否可以连接所有点。
?如果边的数量可以到达所有点,则直接建立菊花图此图所需的边数为n - 1而此时需要n - 1条边,而每两非源点点间距离都为2和源点距离都为1,并且m每多1则答案都减少2.
?如果所有点不能满足关系则将能相连的点先建立标准菊花图相连,再与不能相连的点分别相连,注意没有边的点也要互相相连!
#includeusing namespace std; typedef long long ll; int main() { int t; scanf("%d",&t); while(t--) { ll n,m,ans; scanf("%lld%lld",&n,&m); if(n==1) printf("0\n"); else if(m>=(n*(n-1)/2)) { ans=n*(n-1); printf("%lld\n",ans); } else if(m>=1&&m<=n-1) { ll rst=n-(m+1); //不光是无边和有边的点相连,没边之点之间亦要相连! //代价wa*6 ans=n*rst*(m+1)*2 + n * rst * (rst - 1); m++; ans+=2*(m-1)*(m-1); printf("%lld\n",ans); } else { ans=2*(n-1)*(n-1); ans=ans-2*(m-(n-1)); printf("%lld\n",ans); } } }
?本题意思为给定集合元素个数n以及所有元素相加之和m,同时告诉你子集相加和为0~m的个数分别有几个(空集当作0),求原集合元素。
?本题想到用类似背包的思想,用小的去更新大的。类似01背包,大的必然由小的相加一个数而来,所以dp[n + i] += dp[n]更新可以由小到达大的数量。当更新到当前值时与题目所给的值做差就是当前值所有的个数。
#includeusing namespace std; typedef long long ll; int a[10010]; int dp[10010]; int main() { int t; scanf("%d",&t); while(t--) { int n,m,x; scanf("%d%d",&n,&m); memset(a,0,sizeof(a)); memset(dp,0,sizeof(dp)); scanf("%d",&x); int maxn=0,minx=0; for(int i=1;i<=m;i++) { scanf("%d",&x); x-=dp[i]; dp[0]=1; if(x>0) { a[i]=x; for(int k=1;k<=x;k++) { for(int now=maxn;now>=0;now--) dp[now+i]+=dp[now]; maxn=maxn+i; } } } int cnt=0; for(int i=1;i<=m;i++) { if(a[i]!=0) for(int j=1;j<=a[i];j++) { cnt++; printf("%d",i); if(cnt!=n) printf(" "); } } printf("\n"); } return 0; }
?本题为全场比赛之水题。意为给定n个数字当两数差的绝对值大于k时大者获胜,当两书绝对值小于等于k时两者皆有胜利之机。两两比较下,有多少个数字有最终获胜的可能性。
?可以看出只要和相邻最大的数之差小于等于k就有机会获胜;而一旦距离相邻最大的数之差大于k,比当前的数小的数和此数就再无获胜可能。
?由此可知只要由大到小排序,只要距离前一个的距离小于等于k最终答案就加1,而最大之数定获选故最终答案初始化为1。遂得代码。
#includeusing namespace std; int a[100004]; int main() { int t; scanf("%d", &t); while(t--) { int n, k; memset(a, 0, sizeof(a)); scanf("%d%d", &n, &k); for(int i = 1;i <= n;i++) { scanf("%d", &a[i]); } sort(a + 1, a + 1 + n); int ans = 1; for(int i = n;i >= 2;i--) { if(a[i] - a[i - 1] <= k) ans++; else break; } printf("%d\n", ans); } return 0; }