首页 > 代码库 > 【模拟题(电子科大MaxKU)】解题报告

【模拟题(电子科大MaxKU)】解题报告

目录:

   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
1
1
0
0
2
1 3 1
2 3 2
3 4 3
4 5 3

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(CSDN)的思路解释:

  发现这些农场构成了一棵

  所以首先以任意一个点为根建树,并把这个点当做目标点。

  那么最终的答案就是每条树边乘有几头牛要走,一条边有几头牛要走其实就是这条边下面有几个子孙。

  于是我们预处理出以1为根的树的答案,并求出每个节点有几个子孙,然后O(1)转移到他的儿子的答案,这个儿子又可以O(1)转移到他自己的儿子。。。

  因此我们用O(n)时间就求出以每个点为目的地的路程和,输出最小即可。

  转移方法是:

  根变成儿子的时候,只有连接儿子的边要变化,根据预处理出的每个节点的儿子,即可转移。

技术分享
 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #define LL long long 6 using namespace std; 7 const int maxn=100005; 8 LL n,ans=1e15,sum,c[maxn]; 9 LL he[maxn],ne[maxn*2],to[maxn*2],w[maxn*2],tot;10 LL f[maxn],cost[maxn],num[maxn],len[maxn];11 void add(LL a,LL b ,LL x)12 {13     tot++;14     ne[tot]=he[a];15     w[tot]=x;16     to[tot]=b;17     he[a]=tot;18 }19 void ready(LL x ,LL fa)//当前节点x,它的father fa 20 {21     for (LL  i=he[x];i;i=ne[i])22       if (to[i]!=fa)//!!! 防止原路返回 23       {24           len[to[i]]=len[x]+w[i];25           ready(to[i],x);//从上到下 26           cost[x]+=cost[to[i]];//从x到根节点(包括它的所有儿子)的总路程 27           num[x]+=num[to[i]];//从x向下的所有奶牛数 28       }29     cost[x]+=len[x]*c[x];//加上自己 30     num[x]+=c[x];31 }32 void dfs(LL x,LL fa)33 {34     for (LL i=he[x];i;i=ne[i])35     if (to[i]!=fa)36     {37         f[to[i]]=f[x]+(sum-num[to[i]])*w[i]-num[to[i]]*w[i];38         //将集合地点向下移,用O(1)算它的总路程 39         dfs(to[i],x);    40     }41 }42 int main()43 {44     freopen("A.in","r",stdin);45     freopen("A.out","w",stdout);46     cin>>n;47     for (LL i=1;i<=n;i++)48     {49         scanf("%I64d",&c[i]);50         sum+=c[i];51     }52     for (LL i=1;i<n;i++)// < n  not <=n 53     {54         LL a,b,x;55         scanf("%I64d%I64d%I64d",&a,&b,&x);56         add(a,b,x);57         add(b,a,x);58     }59     ready(1,0);//预处理任意根节点的一棵树 60     f[1]=cost[1];61     dfs(1,0);62     for (LL i=1;i<=n;i++)63     {64         if (f[i]<ans)65           ans=f[i];66     } 67     cout<<ans;68     return 0;69 }
View Code

  第二题:如果纯模拟的话,按理说可以得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的话,就要再用新的数列重复以上操作,所以,运用矩阵乘法的结合律,我们可以用快速幂求解。

  又发现左边矩阵很有规律,所以可以简化为一维数组,具体的解释和注意在代码中了。

技术分享
 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define LL long long 5 using namespace std; 6 const LL INF=1000000007; 7 const LL maxn=1005; 8 LL n,d,k; 9 LL num[maxn],tmp[maxn];10 void cheng(LL a[],LL b[])//a num ,b tmp11 {12     LL c[maxn];13     memset(c,0,sizeof(c));//局部变量 c 初值随机,需要重定为 0 14     for (LL i=0;i<n;i++)//c[0]=a0*b0+a1*b1+a2*b2+a3*b3+a4*b415       for (LL j=0;j<n;j++)//c[1]=a0*b4+a1*b0+a2*b1+a*b2+a4*b316       {17           if (i>j) c[i]=(c[i]+a[j]*b[n+j-i])%INF;//发现当i>j时,b取b[n+j-i] 18           else19               c[i]=(c[i]+a[j]*b[j-i])%INF;//当i<=j时,b取 b[j-i]20       }21     for (LL i=0;i<n;i++)22       a[i]=c[i]%INF;23 }24 int main()25 {26     freopen("B.in","r",stdin);27     freopen("B.out","w",stdout);28     cin>>n>>d>>k;29     for (LL i=0;i<n;i++)30       scanf("%d",&num[i]);31     tmp[0]=1;32     for (LL i=1;i<=d;i++)33         tmp[i]=tmp[n-i]=1;34     while (k>0)35     {36         if (k&1) cheng(num,tmp);37         k=k>>1;38         cheng(tmp,tmp);39     }40     for (LL i=0;i<n;i++)41       printf("%I64d ",num[i]);42     return 0;43 }
View Code

 

   第三题:主要是打表找规律,比如从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 加上去就可以了。

技术分享
 1 #include<iostream> 2 #include<cstdio> 3 #define LL long long 4 using namespace std; 5 LL n,k; 6 LL ans; 7 int main() 8 { 9     freopen("C.in","r",stdin);10     freopen("C.out","w",stdout);11     cin>>n>>k;12     if (n>k)13     {14         ans+=(n-k)*k;15         n=k;16     }17     LL l,x,d,next,r;18     for (LL i=n;i>=1;i=next)19     {20         d=k/i;//等差值 21         l=k%i;//a(1) 22         next=k/(d+1);//下一个区间的右边界 23         x=i-next;//区间个数 n24         r=k%(next+1);//a(n) 25         if (l==r) break;26         else27         //S(n)=n*a(1)+( n*(n-1)/2 )*d28             ans+=x*l+(x*(x-1)/2)*d;29     }30     for (LL i=1;i<=next+1;i++)31       ans+=k%i;32     cout<<ans;33     return 0;34 }
View Code

 

【模拟题(电子科大MaxKU)】解题报告