a 问题描述数据范围解题法代码 b 问题描述数据范围解题法代码 c 题目描述数据范围解题法代码 总结（讲垃圾话）

a

问题描述

请构造一颗 n n 个节点的树，使得其价值最大。 f(d)f(d) 表示树上，度数为 d d 的一个点能够获取的价值。 这棵树的价值为∑ni=1f(di)∑i=1nf(di) di d i 表示第 i i 个点的度数

数据范围

对于20% 的数据, n⩽8n⩽8, 对于100% 的数据, 1⩽T⩽2015 1 ⩽ T ⩽ 2015 , 1⩽n⩽2015 1 ⩽ n ⩽ 2015 , 1⩽f(i)⩽10000 1 ⩽ f ( i ) ⩽ 10000 , 最多10 组数据 n>100 n > 100 。

解题法

20分：二维DP，搜索，大暴力。

前两个很好理解

大暴力其实就跟找碳链异构一样，枚举1~8每种树的构成。 看起来多，其实很简单。（化学不好没法做的）

附大暴力代码

#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #define FN "a" const int maxn=2015+1; int f[maxn]; int main() { freopen(FN".in","r",stdin); freopen(FN".out","w",stdout); int T; scanf("%d",&T); while(T--) { memset(f,0,sizeof(f)); int n; scanf("%d",&n); for(int i=1;i<n;i++) scanf("%d",f+i); if(n>8) printf("³ÔÄûÃÊ£¡\n"); int ans=0; switch (n) { case 1: break; case 2: ans=f[1]+f[1];break; case 3: ans=f[2]+f[1]+f[1];break; case 4: ans=std::max((f[2]<<1)+(f[1]<<1),f[3]+(f[1]<<1)+f[1]);break; case 5: ans=std::max(3*f[2]+2*f[1], std::max(f[3]+f[2]+3*f[1],f[4]+4*f[1]));break; case 6: ans=std::max((f[1]<<1)+(f[2]<<2), std::max(3*f[1]+(f[2]<<1)+f[3], std::max((f[1]<<2)+(f[3]<<1), std::max(f[4]+f[2]+(f[1]<<2),f[1]*5+f[5]))));break; case 7: ans=std::max((f[1]<<1)+5*f[2], std::max(3*f[1]+3*f[2]+f[3], std::max(4*f[1]+f[2]+2*f[3], std::max(4*f[1]+2*f[2]+f[4], std::max(5*f[1]+f[3]+f[4], std::max(5*f[1]+f[2]+f[5],6*f[1]+f[6]))))));break; case 8: ans=std::max(2*f[1]+6*f[2], std::max(3*f[1]+4*f[2]+f[3], std::max(4*f[1]+2*f[2]+2*f[3], std::max(5*f[1]+3*f[3], std::max(4*f[1]+3*f[2]+f[4], std::max(5*f[1]+f[2]+f[3]+f[4], std::max(6*f[1]+2*f[4], std::max(5*f[1]+2*f[2]+f[5], std::max(6*f[1]+f[3]+f[5], std::max(6*f[1]+f[2]+f[6],7*f[1]+f[7]))))))))));break; default:break; } printf("%d\n",ans); } return 0; }

（闲的蛋疼才会写这种程序吧！）

100分：看起来真的很简单的背包DP

每个节点至少一个度，所以就先把总度数（2*n-2）分配给大家，就还剩（n-2）个度。

问题变成把n-2个度分成若干块，求收益最大值。

背包无疑。

dp[i] d p [ i ] 表示选 i i 个点时的最大收益。

状态转移靠感性理解。

代码

#include<cstdio> #include<iostream> #include<cstring> #define FN "a" const int maxn=2015 1; int dp[maxn<<2],f[maxn]; int main() { freopen(FN".in","r",stdin); freopen(FN".out","w",stdout); int T; scanf("%d",&T); while(T--) { memset(dp,0,sizeof(dp)); int n; scanf("%d",&n); for(int i=1;i<n;i ) scanf("%d",f i); dp[0]=n*f[1]; for(int i=0;i<n;i ) for(int j=i;j>=0;j--) dp[i]=std::max(dp[i],dp[j] f[i-j 1]-f[1]); printf("%d\n",dp[n-2]); } return 0; }

b

问题描述

给出正整数nn 和 k k ，计算j(n,k)=∑nik mod ij(n,k)=∑ink mod i的值，其中 k mod i k   m o d   i 表示 k k 除以ii 的余数。例如 j(5,3)=3 mod 1+3 mod 2+3 mod 3+3 mod 4+3 mod 5=0+1+0+3+3=7 j ( 5 , 3 ) = 3   m o d   1 + 3   m o d   2 + 3   m o d   3 + 3   m o d   4 + 3   m o d   5 = 0 + 1 + 0 + 3 + 3 = 7

数据范围

对于 40% 40 % 的数据, n,k⩽1000 n , k ⩽ 1000 , 对于 100% 100 % 的数据, 1⩽n,k⩽1e9 1 ⩽ n , k ⩽ 1 e 9 。

解题法

暴力分在40~70不等

乱优化就是了。

j(n,k)=∑ink mod i j ( n , k ) = ∑ i n k   m o d   i

这个式子带了取模运算，就很烦。 于是变成这样：

j(n,k)=n∗k−∑in⌊ki⌋∗i j ( n , k ) = n ∗ k − ∑ i n ⌊ k i ⌋ ∗ i

当 i>k i > k 时，后边一半值为0。

故只考虑 i<k i < k 。

把 ⌊ki⌋∗i ⌊ k i ⌋ ∗ i 相同的放在一个块中，这样的块有 n−−√ n 个。

每个块内都是等差数列。

OVER！

代码

#include<bits/stdc++.h> #define FN "b" int main() { freopen(FN".in","r",stdin); freopen(FN".out","w",stdout); int n,k; scanf("%d%d",&n,&k); long long ans=0,now=1; while(now<=n) { long long l=now,r=n+1; while(l+1<r) { long long mid=(l+r)>>1; if((int) (k/mid) == (int) (k/now)) l=mid; else r=mid; } ans+=(l-now+1)*(k%now+k%l)/2; now=l+1; } printf("%I64d",ans); return 0; }

c

题目描述

n n 个霍比特人打算在佛罗多的家里过夜。佛罗多有 n n 张床位和mm 个枕头 (n⩽m) ( n ⩽ m ) 。 n n 张床位排成一列。每个霍比特人需要一张床和至少一个枕头睡觉，但是，每个人都想要尽可能多的 枕头。当然，并不总是可以平等地分享枕头，但如果霍比特人比他邻居少至少两个枕头，那么他会受伤。 佛罗多将睡在排在第kk 个的床上。他可以拥有多少枕头，以便每个霍比特人至少有一个枕头，每个枕头都被给予霍比特人，而且没有人受伤？

数据范围

对于 20% 20 % 的数据, m⩽1000 m ⩽ 1000 , 对于 100% 100 % 的数据, 1⩽k⩽n⩽m⩽1e9 1 ⩽ k ⩽ n ⩽ m ⩽ 1 e 9 。

解题法

本题的难点在于意识到佛罗多是一个霍比特人。

其他直接可以秒杀。

二分答案+贪心check

结束。

代码

#include<cstdio> #include<iostream> #define FN "c" int n,m,k; bool check(int x) { long long sum=0; //left if(k>=x) sum+=1LL*(k-x)+1LL*(x-1)*x/2; else sum+=1LL*(x+x-k)*(k-1)/2; //right if(x+k-n<=1) sum+=1LL*(n-k-x+1)+1LL*(x-1)*x/2; else sum+=1LL*(x+x-n+k-1)*(n-k)/2; return sum<=m-x; } int main() { freopen(FN".in","r",stdin); freopen(FN".out","w",stdout); int T; scanf("%d",&T); while(T--) { scanf("%d%d%d",&n,&m,&k); int l=1,r=m-n+1,ans=1; if(check(r)) ans=r; else while(l<r) { int mid=(l+r)>>1; if(check(mid)) { l=mid+1; ans=mid; } else r=mid; } printf("%d\n",ans); } return 0; }

总结（讲垃圾话）

Rank终于还行了。

T2 暴力没有进行任何优化是一个败笔。

今天好像还不错？