首页 > 代码库 > 2016.8.26.模拟题problems(电子神大的老师发的)

2016.8.26.模拟题problems(电子神大的老师发的)

题目描述

         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

解析:

这道题是很典型的树形动规,一般都是dfs解决。该题需要先贪心出一个根节点,确定目标牧场。然后再搜出疲劳值。

然而,我这么机制,当然用了种傻逼办法,选择了bfs。最后A了,只是过程艰辛...

先是TLE,因为我从下往上直接走,由于双向存边,必定需要去除儿子。如果找一个儿子删一个,相当于1e10那么多了,因为每个点都判断了,而直接从父亲通过一个bool use[100005]来判断的话,就不会每个点都找一遍父亲的儿子。这样就不会TLE了。然后接着就发现有一个地方写错了,没有跟着改过来,导致全W。后来改了过后,int的数据都过了,但是ll的数据没有过。原因一是windows系统需要I64d输出,而Linux系统需要lld,我习惯性用了lld;二是因为双向存边,数组范围翻倍,而卧并没有...搞忘了......

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 #define ll long long 6 using namespace std; 7 queue<int>q; 8 int tot,tov[2000005],next[2000005],head[2000005]; 9 int n,a,b,l,c[1000005],num[1000005];10 ll sum,f[1000005],w[1000005],ac;11 bool use[1000005];12 void add(int x,int y,ll wea)13 {14     tot++;15     tov[tot]=y;16     next[tot]=head[x];17     head[x]=tot;18     w[tot]=wea;19 }20 void bfs()21 {22     while(!q.empty())23     {24         int v=q.front();25         use[v]=true;26         q.pop();27         if(f[v]*2>ac) continue ;28         29         int q1=head[v];30         while(use[tov[q1]]==true) 31             q1=next[q1];32         33         int u=tov[q1];34         35         num[u]--;36         f[u]+=f[v];37         38         if(num[u]==1&&f[u]*2<=ac) 39         q.push(u);40         sum=(sum+f[v]*w[q1]);41         if(f[u]==ac) break;42     }43 }44 int main()45 {46     freopen("A.in","r",stdin);47     freopen("A.out","w",stdout);48     scanf("%d",&n);49     for(int i=1;i<=n;i++) {scanf("%d",&c[i]); ac+=c[i];f[i]=c[i];}50     for(int i=1;i<n;i++) 51     {52         scanf("%d %d %d",&a,&b,&l);53         add(a,b,l);54         add(b,a,l);55         num[a]++;56         num[b]++;57     }58     for(int i=1;i<=n;i++)59     if(num[i]==1)60     {61         q.push(i);62     }63     bfs();64     printf("%I64d",sum);65     return 0;66 }

一道更简单题

时间1s

描述

有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

解析:

这种重复相同数据运算,一般用快速幂或者矩阵乘法。

该题使用快速幂,用了矩阵乘法的思想,只说把二维压成了一维,然后去改变每次调用的开始位置就搞定。

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define ll long long 5 #define p 1000000007 6 using namespace std; 7 int n,d,k; 8 ll a[1005],cheng[1005]; 9 void mul(ll q1[1005],ll q2[1005])10 {11     ll c[1005];12     int j;13     for(int i=0;i<n;i++)14         for(c[i]=j=0;j<n;j++)15         c[i]+=q1[j]*q2[(i-j+n)%n]%p;16     for(int i=0;i<n;q2[i]=c[i++]%p);17 }18 int main()19 {20     freopen("B.in","r",stdin);21     freopen("B.out","w",stdout);22     scanf("%d %d %d",&n,&d,&k);23     for(int i=0;i<n;i++) scanf("%lld",&a[i]);24     cheng[0]=1;25     for(int i=1;i<=d;i++) cheng[i]=cheng[n-i]=1;26     while(k)27     {28         if(k&1) mul(cheng,a);29         mul(cheng,cheng);30         k=k>>1;31     }32     for(int i=0;i<n;i++)33     printf("%lld ",a[i]);34     return 0;35 }

最简单的题

时间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

解析:

说白了,找规律,然而一开始我还智障的去用暴力除质数,发现并不行。

还是老老实实找规律,找其商和余数以及k-余数的规律,然后发现时等差数列,最后用一个公式就算出来了。

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define ll long long 5 using namespace std; 6 ll n,k,ans; 7 ll j,l,r; 8 int main() 9 {10     freopen("C.in","r",stdin);11     freopen("C.out","w",stdout);12     cin>>n>>k;13     if(k==0) {cout<<0<<endl; return 0;}14     ans=n*k;15     for(ll i=1;i<=k;i=r+1)16     {17         j=k/i,l=k/(j+1)+1,r=k/j;18         if(r>n) r=n;19         ans-=(r-l+1)*(r+l)*j/2;20     }21     22     cout<<ans<<endl;23     return 0;24 }

 

2016.8.26.模拟题problems(电子神大的老师发的)