目录：
1：一道简单题【树形问题】(Bzoj 1827 奶牛大集会)
2：一道更简单题【矩阵乘法】【快速幂】
3：最简单题【技巧】
话说这些题目的名字也是够了。。。。
题目：
1、一道简单题
时间1s
题目描述
Bessie正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方便的地点来举办这次集会。每个奶牛居住在 N(1<=N<=100,000) 个农场中的一个，这些农场由N-1条道路连接，并且从任意一个农场都能够到达另外一个农场。道路i连接农场A_i和B_i(1 <= A_i <=N; 1 <= B_i <= N),长度为L_i(1 <= L_i <= 1,000)。集会可以在N个农场中的任意一个举行。另外，每个牛棚中居住着C_i(0 <= C_i <= 1,000)只奶牛。在选择集会的地点的时候，Bessie希望最大化方便的程度(也就是最小化不方便程度)。比如选择第X个农场作为集会地点，它的不方便程度是其它牛棚中每只奶牛去参加集会所走的路程之和，(比如，农场i到达农场X的距离是20，那么总路程就是C_i*20)。帮助Bessie找出最方便的地点来举行大集会。
输入
第一行：一个整数N
第二到N+1行：第i+1行有一个整数C_i
第N+2行到2*N行，第i+N+1行为3个整数：A_i,B_i和L_i。
输出
一个数字表示答案
样例
|
Input |
Output |
|
5 |
15 |
对于
20%数据n<20
50%数据 n<2000
100%数据n<100,000
2、一道更简单题
时间1s
描述
有n个数围成一圈，每次操作后每个数变成和他距离在d以内的数字之和，求k次操作后每个数字模1000000007分别是多少有n个数围成一圈，每次操作后每个数变成和他距离在d以内的数字之和，求k次操作后每个数字模1000000007分别是多少
输入
第一行三个数n, d, k (1 ≤ n ≤ 1000, 0 ≤ d < n / 2 , 1 ≤ k ≤ 100 000 000),
第二行有n个正数，每个的大小都在int范围内
输出
一行n个数，空格隔开，表示结果。
样例
|
Input |
Ouput |
5 1 1 1 2 10 3 6 |
9 13 15 19 10 |
10%数据满足n*k<10^6
30%数据满足 n<=100
50%数据满足 n<=500
100%数据满足n<=1000
3、最简单的题
时间1s
题目描述
给出正整数n和k，计算j(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值，其中k mod i表示k除以i的余数。
例如j(5, 3)=3 mod 1 + 3 mod 2 + 3 mod 3 + 3 mod 4 + 3 mod 5=0+1+0+3+3=7
输入
第一行2个数n,k。
输出
一个数 j(n,k)。
样例
|
Input |
Output |
|
5 3 |
7 |
50% 数据 满足 n<1e6
100%数据 满足 n<1e12 k<=n
解题报告：
第一题：参考Regina8023（****）的思路解释：
发现这些农场构成了一棵树。
所以首先以任意一个点为根建树，并把这个点当做目标点。
那么最终的答案就是每条树边乘有几头牛要走，一条边有几头牛要走其实就是这条边下面有几个子孙。
于是我们预处理出以1为根的树的答案，并求出每个节点有几个子孙，然后O(1)转移到他的儿子的答案，这个儿子又可以O(1)转移到他自己的儿子。。。
因此我们用O(n)时间就求出以每个点为目的地的路程和，输出最小即可。
转移方法是：
根变成儿子的时候，只有连接儿子的边要变化，根据预处理出的每个节点的儿子，即可转移。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#define LL long long
using namespace std;
const int maxn=;
LL n,ans=1e15,sum,c[maxn];
LL he[maxn],ne[maxn*],to[maxn*],w[maxn*],tot;
LL f[maxn],cost[maxn],num[maxn],len[maxn];
void add(LL a,LL b ,LL x)
{
tot++;
ne[tot]=he[a];
w[tot]=x;
to[tot]=b;
he[a]=tot;
}
void ready(LL x ,LL fa)//当前节点x，它的father fa
{
for (LL i=he[x];i;i=ne[i])
if (to[i]!=fa)//!!! 防止原路返回
{
len[to[i]]=len[x]+w[i];
ready(to[i],x);//从上到下
cost[x]+=cost[to[i]];//从x到根节点(包括它的所有儿子)的总路程
num[x]+=num[to[i]];//从x向下的所有奶牛数
}
cost[x]+=len[x]*c[x];//加上自己
num[x]+=c[x];
}
void dfs(LL x,LL fa)
{
for (LL i=he[x];i;i=ne[i])
if (to[i]!=fa)
{
f[to[i]]=f[x]+(sum-num[to[i]])*w[i]-num[to[i]]*w[i];
//将集合地点向下移，用O(1)算它的总路程
dfs(to[i],x);
}
}
int main()
{
freopen("A.in","r",stdin);
freopen("A.out","w",stdout);
cin>>n;
for (LL i=;i<=n;i++)
{
scanf("%I64d",&c[i]);
sum+=c[i];
}
for (LL i=;i<n;i++)// < n not <=n
{
LL a,b,x;
scanf("%I64d%I64d%I64d",&a,&b,&x);
add(a,b,x);
add(b,a,x);
}
ready(,);//预处理任意根节点的一棵树
f[]=cost[];
dfs(,);
for (LL i=;i<=n;i++)
{
if (f[i]<ans)
ans=f[i];
}
cout<<ans;
return ;
}
第二题：如果纯模拟的话，按理说可以得10分，但是我的纯模拟怎么一分都没有。这道题要用矩阵乘法+快速幂。具体的推导方法是这样的：
首先，我们从一个点的多次修改得到系数：
如 a0,a1,a2,a3,a4
第一次：a0=a0+a1+a4 第二次：a0=3*a0+2*a1+2*a4+a2+a3第三次：a0=7*a0+6*a1+6*a4+4*a2+4*a3
a1=a0+a1+a2 a1=3*a1+2*a0+2*a2+a3+a4 ......
a2=a1+a2+a3 a2=3*a2+2*a3+2*a1+a4+a0 ......
...... ......
按照a0~a4提取出它们的系数：1*a0 1*a1 0*a2 0*a3 1*a4
3*a0 2*a1 1*a2 1*a3 2*a4
7*a0 6*a1 4*a2 4*a3 6*a4
所以我们想到了矩阵相乘用 1 1 0 0 1 a0 a0+a1+a4
1 1 1 0 0 a1 a0+a1+a2
0 1 1 1 0 * a2 = a1+a2+a3
0 0 1 1 1 a3 a2+a3+a4
1 0 0 1 1 a4 a3+a4+a1
如果k>1的话，就要再用新的数列重复以上操作，所以，运用矩阵乘法的结合律，我们可以用快速幂求解。
又发现左边矩阵很有规律，所以可以简化为一维数组，具体的解释和注意在代码中了。
#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;
const LL INF=;
const LL maxn=;
LL n,d,k;
LL num[maxn],tmp[maxn];
void cheng(LL a[],LL b[])//a num ,b tmp
{
LL c[maxn];
memset(c,,sizeof(c));//局部变量 c 初值随机，需要重定为 0
for (LL i=;i<n;i++)//c[0]=a0*b0+a1*b1+a2*b2+a3*b3+a4*b4
for (LL j=;j<n;j++)//c[1]=a0*b4+a1*b0+a2*b1+a*b2+a4*b3
{
if (i>j) c[i]=(c[i]+a[j]*b[n+j-i])%INF;//发现当i>j时，b取b[n+j-i]
else
c[i]=(c[i]+a[j]*b[j-i])%INF;//当i<=j时，b取 b[j-i]
}
for (LL i=;i<n;i++)
a[i]=c[i]%INF;
}
int main()
{
freopen("B.in","r",stdin);
freopen("B.out","w",stdout);
cin>>n>>d>>k;
for (LL i=;i<n;i++)
scanf("%d",&num[i]);
tmp[]=;
for (LL i=;i<=d;i++)
tmp[i]=tmp[n-i]=;
while (k>)
{
if (k&) cheng(num,tmp);
k=k>>;
cheng(tmp,tmp);
}
for (LL i=;i<n;i++)
printf("%I64d ",num[i]);
return ;
}
第三题：主要是打表找规律，比如从n=100,k=100打表出100/(1~100)=x.....y 从中找到规律：
100/(51~100)=1....(0、1~48、49)
100/(34~50)=2......(0、2~30、32)
100/(26~33)=3......(1,4~19,22)
100/(21~25)=4......(0,4,~12,16)
100/(17~20)=5......(0,5,10,15)
100/(15,16)=6......(4,10)
.......
从100/12 开始余只有一个。所以从1~12就循环求解。另外，当n>k时，直接余数=k 加上去就可以了。
#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;
LL n,k;
LL ans;
int main()
{
freopen("C.in","r",stdin);
freopen("C.out","w",stdout);
cin>>n>>k;
if (n>k)
{
ans+=(n-k)*k;
n=k;
}
LL l,x,d,next,r;
for (LL i=n;i>=;i=next)
{
d=k/i;//等差值
l=k%i;//a(1)
next=k/(d+);//下一个区间的右边界
x=i-next;//区间个数 n
r=k%(next+);//a(n)
if (l==r) break;
else
//S(n)=n*a(1)+( n*(n-1)/2 )*d
ans+=x*l+(x*(x-)/)*d;
}
for (LL i=;i<=next+;i++)
ans+=k%i;
cout<<ans;
return ;
}