首页 > 代码库 > 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 | 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（电子神大的老师发的）