A 约数之和
(count.pas/c/cpp)
TL:1S ML:128MB【Description】我们用 D(x)表示正整数 x 的约数的个数。给定一个正整数 N，求 D(1)+D(2)+…+D(N)。【Input】一行一个正整数 N。【Output】一行一个整数，表示答案【Sample Input】5【Sample Output】10【Hint】样例解释：D(1)=1 D(2)=2D(3)=2 D(4)=3 D(5)=2对于 20%的测试数据：N<=1000对于 50%的测试数据：N<=100000对于 100%的测试数据：N<=10000000
题解：枚举因数。含有因数i的数有几个
#include#include #include using namespace std;int n;long long ans;inline int read(){ char ch=getchar();int x=0,f=1; for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1; for(;isdigit(ch);ch=getchar())x=x*10+ch-'0'; return x*f;}int main(){ freopen("count.in","r",stdin); freopen("count.out","w",stdout); n=read(); ans=0; for(int i=1;i<=n;i++){ ans+=n/i; } cout< <
B 邮局选址
(post.pas/c/cpp)
TL:1S ML:128MB【Description】在 J 市的一条笔直的公路旁分布着 n 个村庄，每个村庄都有一个唯一的坐标 Xi，任意一对村庄的坐标不同。最近，J 市领导计划在村庄里新建 m 个邮局，而邮局在 n 个村庄里的分布情况会影响到居民的便利程度。设 m 个邮局分别建在 P1,P2,..,Pm 号村庄。每个村庄的村民都会找到与其距离最近的一个邮局， 若有多个距离最近的则会任选一个， 该村庄的便利度即为该村庄与其最近的邮局的距离，而所有村庄的便利度的和即为总便利度。现在，由你来安排邮局的建设位置。请计算最小的 C 是多少。【Input】第一行两个整数 n m第二行递增的 n 个整数，表示 X1..Xn【Output】一行一个整数，表示最小的 C【Sample Input】10 51 2 3 6 7 9 11 22 44 50【Sample Output】9【Hint】样例解释：建立在坐标为：2 7 22 44 50 的位置每个村庄的便利度分别为：1 0 1 1 0 2 4 0 0 0对于 30%的测试数据 n ≤ 10对于 60%的测试数据 n ≤ 50对于 100%的测试数据 1 ≤ n ≤ 300; 1 ≤ m ≤ 30; m ≤ n; 1 ≤ Xi ≤ 10000题解：
30分dfs 对于每个村庄建还是不建邮寄
#include#include #include using namespace std;int n,m,res,xi[320],a[32];inline int read(){ char ch=getchar();int x=0,f=1; for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1; for(;isdigit(ch);ch=getchar())x=x*10+ch-'0'; return x*f;}int zs(int x){ return x<0?-x:x; }void dfs(int x,int pos){ if(n-pos+1
正解：dp 对于区间[l,r]，把邮局放在(l+r)>>1最优，枚举最后一个邮局管辖的范围，预处理dis[l,r]之间建立邮局的最小值。
#include#include #include using namespace std;int n,m;int dis[302][302],f[302][33],x[302];int zs(int x){ return x<0?-x:x;} int main(){ scanf("%d%d",&n,&m);//n个村庄,m个邮局。 for(int i=1;i<=n;i++)scanf("%d",&x[i]); for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ int mid=(i+j)>>1; for(int k=i;k<=j;k++){ dis[i][j]+=zs(x[k]-x[mid]); } } } memset(f,0x3f,sizeof(f)); for(int i=1;i<=n;i++)f[i][1]=dis[1][i]; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(j>i)break; for(int k=1;k
C 分数(fraction.pas/c/cpp)
TL:2S ML:128MB
【Description】
在一门叫做计算机应用数学的神奇的课上，老师教给大家如何处理小数的进制转换：
例如十进制数在十进制下小数表示为0.33333…，在三进制下为0.1，在三十进制下为0.A。（这里A的含义与十六进制中A的含义相同，均表示10）。
下课后，老师要求kAc将N个十进制的分数写成k进制下的小数。然而kAc发现，很多十进制分数根本不可能写成有限的k进制小数！这令他十分不爽，不过他想知道，最小需要几进制才能使得这些十进制分数在该进制下均为有限的小数。
【Input】
第一行两个整数N
接下来N行，每行两个整数a, b，表示一个十进制小数
【Output】
一个整数，表示最小进制数。这里，请按照十六进制输出，所有字母全部大写。（例如，如果答案为十进制下26，则输出1A）。
【Sample Input】
2
3 99
1 99
1 11
【Sample Output】
21
【Hint】
样例解释：
在33进制下，可以表示为0.1，可以表示为0.0B，可以表示为0.3。
可以证明不存在更小的进制，使得他们均为有限小数。
对于20%的测试数据：n=1
对于50%的测试数据：n<=10，a, b <= 10000，保证最终答案在十进制下不超过10000。
对于70%的测试数据：n<=100，a, b<= 10000。
对于100%的测试数据：n<=1000，1 <= a,b <= 1000000000。
题解：
#include#include #include #include #define pz putchar('0');#include