14. using std::max; 15. using std::swap; int main(int argc, char const *argv[]) 18. { 1 #ifndef ONLINE_JUDGE 20. freopen("rect.in", "r", stdin

Size: px

Start display at page:

Download "14. using std::max; 15. using std::swap; int main(int argc, char const *argv[]) 18. { 1 #ifndef ONLINE_JUDGE 20. freopen("rect.in", "r", stdin"

说昧苏
5 years ago
Views:

1 Notes HTML Display PDF English New words and expressions OI SSR's Ascii Art NOIP2016 Simulation Nr. 49 Problem A NOIP2016 Simulation Nr. 49 Problem B (Fibonacci Sequence, Minus Modulo, Fast Matrix Exponentiation) NOIP2016 Simulation Nr. 49 Problem C NOIP2016 Simulation Nr. 50 Problem A NOIP2016 Simulation Nr. 50 Problem B Cmd Markdown Slash Matrix M3. Inline-code Table Notes HTML Display PDF This is very useful in blogs. 1. <iframe src = "...pdf" width=768 height=1024></iframe> English New words and expressions Literary Meaning Literary adj. about writing Taking into account that... Mentioned that... OI SSR's Ascii Art 1. /\_/\ /\_/\ /\_/\ /\_/\ * *.\/. 3. w) w) w) w) W--W-----W--W----W--W-----W--W NOIP2016 Simulation Nr. 49 Problem A 小 W 摆石子问题描述小 W 得到了一堆石子, 要放在 N 条水平线与 M 条竖直线构成的网格的交点上因为小 M 最喜欢矩形了, 小 W 希望知道用 K 个石子最多能找到多少四边平行于坐标轴的长方形, 它的四个角上都恰好放着一枚石子输入格式第一行三个整数 N,M,K 输出格式一个非负整数, 即最多的满足条件的长方形数量输入输出样例 rectangle.in rectangle.out 5 rectangle.in rectangle.out 1398 数据规模对于 50% 的数据 :N<=30 对于 100% 的数据 :N<=30000, 保证任意两点不重合,K<=N*M 2. Problem: User: yanhuihang 6. Time:1 ms 7. Memory:1084 kb 11. #include <algorithm> 12. #include <cstdio> 13.

2 14. using std::max; 15. using std::swap; int main(int argc, char const *argv[]) 18. { 1 #ifndef ONLINE_JUDGE 20. freopen("rect.in", "r", stdin); 21. #endif long long int n, m, k; 24. scanf("%lld%lld%lld", &n, &m, &k); if (k == n*m) { 27. printf("%lld", n*(n-1)*m*(m-1)/4); } 28. else { 2 if (n > m) swap(n, m); long long s = 0; for (long long x = 1; x <= n; ++x) { 34. long long y = k / x; 35. long long r = k - x*y; 36. if (y > m (y == m && r!= 0)) continue; 37. s = max(s, x*(x-1)*y*(y-1)/4+r*y*(r-1)/2); } printf("%lld", s); } return 0; 42. } 考虑对于一个布满点的网格 (x 行,Y 列 ), 所有的矩形总数为组合数 C(2,x)*C(2,y) 但 k 不一定刚好就能布满整个网格, 所以我们先找到在网格中最大能形成的长方形矩阵的长 y 和宽 x, 剩余石子为 r, 则有 k = x * y + r, 最大能形成的长方形矩阵最多有 C(x,2)*C(y,2) 个矩形, 剩余石子 r 以一排或一列的形式, 靠在大矩形短的一边 ( 要注意是否到达边界 ), 则多增加的矩形数为 C(2,r)*y (y 为长边的点数 ) 枚举 x 与 y, 计算出 C(x,2)*C(y,2)+ C(r,2)*y 的最大值 1. #include <iostream> 2. #include <cmath> 3. #include <algorithm> 4. using namespace std; long long Func(long long n) 7. { 8. return n*(n-1)/2; } int main() 11. { 12. int T; 13. cin >> T; 14. for(int cnt = 1; cnt <= T; ++cnt) 15. { 16. int n, m, k; 17. cin >> n >> m >> k; 18. if(n > m) swap(n,m); //n 为短边,m 为长边 ( 个人习惯 ~0~) 1 long long ans = 0; 20. for(int x = 2; x <= n; ++x) // 对 x 进行枚举 ( 短边 ) 21. { 22. int y = k / x; // 可能的最大长边 y 23. int r = k % x; // 剩余的石子数 r 24. if( y > m ( y == m && r) ) // 超边界 25. continue; 26. ans = max(ans, Func(x)*Func(y) + y*func(r)); 27. } 28. cout << "Case #" << cnt << ": " << ans << endl; 2 } 30. return 0; 31. } NOIP2016 Simulation Nr. 49 Problem B (Fibonacci Sequence, Minus Modulo, Fast Matrix Exponentiation) Fibonacci Sequence is defined by: Given, calculate We have answer is required to be printed modulo Let be, we have so we just need to calculate. Obviously, Use the matrix exponentiation. I don't know how to do or how it works:

3 And the code (also I really don't know) : 1. #include<iostream> 2. #include<cstdlib> 3. #include<cstdio> 4. #include<cmath> 5. #include<cstring> 6. #include<algorithm> 7. #include<queue> 8. #define mod using namespace std; struct hh 11. { 12. int a[5][5],n,m; 13. }; 14. hh a,b,c; int t,l,r,suma,sumb,ans; 17. int f[50005]; hh mul(hh,hh); 20. hh ff(hh,int); 21. int main() 22. { 23. int i,j; 24. freopen("fibonacci.in","r",stdin); 25. freopen("fibonacci.out","w",stdout); 26. scanf("%d",&t); 27. a.m=a.n=b.n=3; 28. b.m=1; 2 for(j=1;j<=3;j++) a.a[1][j]=1; 30. a.a[2][2]=a.a[2][3]=1; 31. a.a[3][2]=1; 32. b.a[1][1]=2; 33. b.a[2][1]=b.a[3][1]=1; 34. while(t--) 35. { 36. scanf("%d%d",&l,&r); 37. if(l<=3) suma=l-1; 38. else{c=mul(ff(a,l-3),b);suma=c.a[1][1];} 3 if(r<=2) sumb=r; 40. else{c=mul(ff(a,r-2),b);sumb=c.a[1][1];} 41. ans=(sumb-suma+mod)%mod; 42. printf("%d\n",ans); 43. } 44. fclose(stdin); 45. fclose(stdout); 46. return 0; 47. } hh mul(hh a,hh b) 50. { 51. int i,j,k; 52. hh c; 53. c.n=a.n; 54. c.m=b.m; 55. memset(c.a,0,sizeof(c.a)); 56. for(i=1;i<=c.n;i++) 57. for(j=1;j<=c.m;j++) 58. for(k=1;k<=c.n;k++) 5 c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j])%mod; 60. return c; 61. } hh ff(hh a,int k) 64. { 65. int i,j; 66. hh c; 67. c.m=a.m; 68. c.n=a.n; 6 for(i=1;i<=min(c.n,c.m);i++) c.a[i][i]=1; 70. for(i=1;i<=c.n;i++) 71. for(j=1;j<=c.m;j++) 72. if(i!=j) c.a[i][j]=0; 73. while(k) 74. { 75. if(k&1) c=mul(a,c); 76. a=mul(a,a); 77. k>>=1; 78. } 7 return c; 80. } Another Code (I really don't know): 2. Problem: User: noip Time:7 ms 7. Memory:1084 kb 11. #include<cstdio> 12. #include<cstring> 13. const int maxn=3,mod=10000,sz=2; 14. int t,x,y,l,r; 15. struct Matrix 16. { 17. int num[maxn][maxn]; 18. Matrix operator*(matrix b) 1 { 20. Matrix res;memset(res.num,0,sizeof res.num); 21. for(register int i=1;i<=sz;++i)for(register int j=1;j<=sz;++j)for(register int k=1;k<=sz;++k)(res.num[i][j]+=num[i][k]*b.num[k][j])%=mo 22. return res; 23. } 24. void reset(){num[1][1]=num[1][2]=num[2][1]=1,num[2][2]=0;} 25. }ele; 26. Matrix operator^(matrix a,int n) 27. { 28. Matrix res;res.num[1][1]=res.num[2][2]=1,res.num[2][1]=res.num[1][2]=0; 2 for(;n;n>>=1,a=a*a)if(n&1)res=res*a; 30. return res; 31. } 32. int main() 33. { 34. for(scanf("%d",&t);t--;) 35. {

4 scanf("%d%d",&x,&y); ele.reset(); 38. ele=ele^(x-1);l=(ele.num[1][1]+ele.num[1][2])%mod; 3 ele.reset(); 40. ele=ele^y;r=(ele.num[1][1]+ele.num[1][2])%mod; 41. printf("%d\n",(r-l+mod)%mod); 42. } 43. return 0; 44. } Yet another code (I really don't know): 2. Problem: User: Owen 6. Time:8 ms 7. Memory:1084 kb 11. #include<cstdio> 12. #include<cstring> 13. using namespace std; 14. const int q=1e4; 15. struct matrix { 16. int a[3][3]; 17. void eye() { 18. a[1][2]=a[2][1]=0; 1 a[1][1]=a[2][2]=1; 20. } 21. void base() { 22. a[1][1]=a[1][2]=a[2][1]=1; 23. a[2][2]=0; 24. } 25. int first() { 26. return a[1][1]; 27. } 28. void clear() { 2 memset(a,0,sizeof a); 30. } 31. } bas,m,ret; 32. matrix mul(matrix b,matrix c) { 33. ret.clear(); 34. for (int i=1;i<=2;++i) for (int j=1;j<=2;++j) { 35. for (int k=1;k<=2;++k) (ret.a[i][j]+=b.a[i][k]*c.a[k][j])%=q; 36. } 37. return ret; 38. } 3 int get(int x) { 40. m.eye(); 41. bas.base(); 42. while (x) { 43. if (x&1) m=mul(m,bas); 44. x>>=1; 45. bas=mul(bas,bas); 46. } 47. return m.first(); 48. } 4 int main() { 50. #ifndef ONLINE_JUDGE 51. freopen("test.in","r",stdin); 52. #endif 53. int T; 54. scanf("%d",&t); 55. while (T--) { 56. int x,y; 57. scanf("%d%d",&x,&y); 58. int a=get(y+1),b=get(x); 5 int ans=(a-b+q)%q; 60. printf("%d\n",ans); 61. } 62. } Yet yet another code (I really don't know): 2. Problem: User: Time:9 ms 7. Memory:1084 kb 11. #include <cstdio> 12. #include <cstdlib> 13. #include <cstring> 14. const int Q=10000; 15. int tcas; inline int plus(int x,int y){return (x+y)%q;} 18. inline int mul(int x,int y){return (x*y)%q;} struct G{ 21. int a[2][2]; 22. G(){memset(a,0,sizeof(a));} 23. }fir,pr; 24. G operator *(G x,g y) 25. { 26. G res; 27. for(int k=0;k<2;k++) 28. for(int i=0;i<2;i++) 2 for(int j=0;j<2;j++) res.a[i][j]=plus(res.a[i][j],mul(x.a[i][k],y.a[k][j])); 30. return res; 31. } int get(int t) 34. { 35. G res=fir; 36. G x=pr; 37. for(;t>0;t>>=1) 38. { 3 if(t&1) res=x*res; 40. x=x*x; 41. } 42. return res.a[0][0]; 43. } int main() 46. { 47. #ifndef ONLINE_JUDGE 48. freopen("fibonacci.in","r",stdin); 4 freopen("fibonacci.out","w",stdout); 50. #endif

5 fir.a[0][0]=1;fir.a[1][0]=1; pr.a[0][1]=pr.a[1][0]=pr.a[1][1]=1; 53. int i,x,y; 54. scanf("%d",&tcas); 55. while(tcas--) 56. { 57. scanf("%d%d",&x,&y); 58. y++; 5 x=get(x),y=get(y); 60. printf("%d\n",(y-x% )%10000); 61. } 62. return 0; 63. } We have a simpler and faster way. Just brute-force. Taking into account that the answer should be moduloed. We can guess that is cyclical and we can find the cyclical is with the in this problem. So we can initialize the sequence and the sum like this: 1. MOD := CYCLE := fib := EMPTY SET 4. sum := EMPTY SET fib[1] = fib[2] = 1 7. sum[1] = 1 8. sum[2] = 2 for i in 3..CYCLE 11. fib[i] = (fib[i-1] + fib[i-2])%mod 12. sum[i] = (sum[i-1] + fib[i]) %MOD sum[cycle % CYCLE] = sum[cycle] The last line is that, we get by sum[i % CYCLE], so when i = CYCLE we get sum[0]. Then: 1. read n, m 2. output (sum[m%cycle] - sum[(n-1)%cycle] + MOD)%MOD What is the + MOD for? Imagine a situation when m > n-1 however m%cycle < (n-1)%cycle, we will get a negative number by evaluating sum[m%cycle] - sum[(n-1)%cycle]. So we should append a + MOD. But how it works? I don't know. I thought another way but failed. Here is it: We know where so we can calculate out the general term formula of. But includes, is something. And we can not modulo double like. But if we do not modulo in the halfway, we must deal with high precision big float number. So failed. NOIP2016 Simulation Nr. 49 Problem C 小 W 计树问题描述小 W 千辛万苦做出了数列题, 突然发现小 M 被困进了迷宫里迷宫是一个有 N(2 N 1000) 个顶点 M(N?1 M N?(N? 1)/2 ) 条边的无向连通图设 dist1[i] 表示在这个无向连通图中, 顶点 i 到顶点 1 的最短距离为了解开迷宫, 现在要求小 W 在这个图中删除 M? (N? 1) 条边, 使得这个迷宫变成一棵树设 dist2[i] 表示在这棵树中, 顶点 i 到顶点 1 的距离小 W 的任务是求出有多少种删除方案, 使得对于任意的 i, 满足 dist1[i]=dist2[i] 快点帮助小 W 救出小 M 吧! 输入格式第一行, 两个整数, N, M, 表示有 N 个顶点和 M 条边接下来有 M 行, 每行有 3 个整数 x, y, len(1 x, y n, 1 len 100), 表示顶点 x 和顶点 y 有一条长度为 len 的边数据保证不出现自环重边输出格式一行两个整数, 表示满足条件的方案数 mod 的答案输入输出样例 treecount.in treecount.in 2 样例解释删除第一条边或第三条边都能满足条件, 所以方案数是 2 数据规模

6 对于 30% 的数据 :2 N 5,M 10 对于 50% 的数据 : 满足条件的方案数不超过对于 100% 的数据 :2 N 1000 题解首先考虑离 1 点最近的那个点, 一定和 1 点只连着一条边, 则这条边是必选的 ; 然后考察第二近的点, 一种可能是和 1 点直接连的边比较近, 一种可能是经过刚才最近的那个点再到 1 点的路比较近, 不管是哪一种, 选择都是唯一的, 而剩下第三种可能是两者距离相同, 这样的话两者选且只能选一个以此类推, 假设现在已经构造好了前 k 个点的一棵子树, 看剩余点中到 1 点最近的点, 这个点到 1 点有 k 种方法 ( 分别是和那 k 个点连边 ), 其中有 m 个是可以保持最短距离的, 则这一步可选的边数就是 m 一直构造, 把方法数累乘, 就能得到最后的结果整个过程可以很好的符合 dijkstra 的过程, 而生成树的步骤和 prim 如出一辙 1. #include<cstdlib> 2. #include<cstdio> 3. #include<cmath> 4. #include<cstring> 5. #include<algorithm> 6. #include<queue> 7. #define mod using namespace std; int n,m; 11. bool v[1005]; 12. int we[1010][1010], dis[1010]; 13. int last[1010]; 14. int tot=0; 15. struct hh 16. { 17. int next,to,w; 18. }e[ ]; long long ans=1; 21. struct node 22. { 23. int id,d; 24. }; 25. node a[1005]; 26. queue<int> q; bool cmp(node a, node b) 2 { 30. return a.d < b.d; 31. } void add(int a,int b,int c) 34. { 35. tot++; 36. e[tot].to=b; 37. e[tot].w=c; 38. we[a][b]=c; 3 e[tot].next=last[a]; 40. last[a]=tot; 41. } void spfa() 44. { 45. int i,now; 46. for(i=2;i<=n;i++) dis[i]= ; 47. q.push(1); 48. dis[1]=0; 4 while(!q.empty()) 50. { 51. now=q.front(); 52. q.pop(); 53. v[now]=false; 54. for(i=last[now];i;i=e[i].next) 55. if(dis[e[i].to]>dis[now]+e[i].w) 56. { 57. dis[e[i].to]=dis[now]+e[i].w; 58. if(!v[e[i].to]) 5 { 60. v[e[i].to]=true; 61. q.push(e[i].to); 62. } 63. } 64. } 65. } int main() 68. { 6 int i,j,x,y,z,now; 70. freopen("treecount.in","r",stdin); 71. freopen("treecount.out","w",stdout); 72. scanf("%d%d",&n,&m); 73. for(i=1;i<=n;i++) 74. for(j=1;j<=n;j++) 75. we[i][j]= ; 76. for(i=1;i<=m;i++) 77. { 78. scanf("%d%d%d",&x,&y,&z); 7 add(x,y,z); 80. add(y,x,z); 81. } 82. spfa(); 83. for (i=1;i<=n;i++) 84. { 85. a[i].id=i; 86. a[i].d=dis[i]; 87. } 88. sort(a+1,a+n+1,cmp); 8 for(i=2;i<=n;i++) 90. { 91. now=0; 92. for(j=1;j<=i-1;j++) 93. if(a[i].d==a[j].d+we[a[i].id][a[j].id]) now++; 94. ans=ans*(long long)now%mod; 95. } 96. printf("%lld",ans); 97. fclose(stdin); 98. fclose(stdout); 9 return 0; 100. } 首先考虑离 1 点最近的那个点, 一定和 1 点只连着一条边, 则这条边是必选的 ; 然后考察第二近的点, 一种可能是和 1 点直接连的边比较近, 一种可能是经过刚才最近的那个点再到 1 点的路比较近, 不管是哪一种, 选择都是唯一的, 而剩下第三种可能是两者距离相同, 这样的话两者选且只能选一个以此类推, 假设现在已经构造好了前 k 个点的一棵子树, 看剩余点中到 1 点最近的点, 这个点到 1 点有 k 种方法 ( 分别是和那 k 个点连边 ), 其中有 m 个是可以保持最短距离的, 则这一步可选的边数就是 m 一直构造, 把方法数累乘, 就能得到最后的结果整个过程可以很好的符合 dijkstra 的过程, 而生成树的步骤和 prim 如出一辙

7 2. Problem: User: GEOTCBRL 6. Time:141 ms 7. Memory:5664 kb 11. /* 12. I will chase the meteor for you, a thousand times over. 13. Please wait for me, until I fade forever. 14. Just 'coz GEOTCBRL. 15. */ 16. #include <bits/stdc++.h> 17. using namespace std; 18. #define fore(i,u) for (int i = head[u] ; i ; i = nxt[i]) 1 #define rep(i,a,b) for (int i = a, _ = b ; i <= _ ; i ++) 20. #define per(i,a,b) for (int i = a, _ = b ; i >= _ ; i --) 21. #define For(i,a,b) for (int i = a, _ = b ; i < _ ; i ++) 22. #define Dwn(i,a,b) for (int i = ((int) a) - 1, _ = (b) ; i >= _ ; i --) 23. #define fors(s0,s) for (int s0 = (s), _S = s ; s0 ; s0 = (s0-1) & _S) 24. #define foreach(it,s) for ( typeof(s.begin()) it = s.begin(); it!= s.end(); it ++) #define mp make_pair 27. #define pb push_back 28. #define pii pair<int, int> 2 #define fir first 30. #define sec second 31. #define MS(x,a) memset(x, (a), sizeof (x)) #define gprintf(...) fprintf(stderr, VA_ARGS ) 34. #define gout(x) std::cerr << #x << "=" << x << std::endl 35. #define gout1(a,i) std::cerr << #a << '[' << i << "]=" << a[i] << std::endl 36. #define gout2(a,i,j) std::cerr << #a << '[' << i << "][" << j << "]=" << a[i][j] << std::endl 37. #define garr(a,l,r,tp) rep ( it, l, r) gprintf(tp"%c", a[ it], " \n"[ it == _]) template <class T> inline void upmax(t&a, T b) { if (a < b) a = b ; } 40. template <class T> inline void upmin(t&a, T b) { if (a > b) a = b ; } typedef long long ll; const int maxn = 1007; 45. const int maxm = ; 46. const int mod = ; 47. const int inf = 0x7fffffff; 48. const double eps = 1e-7; typedef int arr[maxn]; 51. typedef int adj[maxm]; inline int fcmp(double a, double b) { 54. if (fabs(a - b) <= eps) return 0; 55. if (a < b - eps) return -1; 56. return 1; 57. } inline int add(int a, int b) { return ((ll) a + b) % mod ; } 60. inline int mul(int a, int b) { return ((ll) a * b) % mod ; } 61. inline int dec(int a, int b) { return add(a, mod - b % mod) ; } 62. inline int Pow(int a, int b) { 63. int t = 1; 64. while (b) { 65. if (b & 1) t = mul(t, a); 66. a = mul(a, a), b >>= 1; 67. } 68. return t; 6 } #define gc getchar 72. #define idg isdigit 73. #define rd RD<int> 74. #define rdll RD<long long> 75. template <typename Type> 76. inline Type RD() { 77. char c = getchar(); Type x = 0, flag = 1; 78. while (!idg(c) && c!= '-') c = getchar(); 7 if (c == '-') flag = -1; else x = c - '0'; 80. while (idg(c = gc()))x = x * 10 + c - '0'; 81. return x * flag; 82. } 83. inline char rdch() { 84. char c = gc(); 85. while (!isalpha(c)) c = gc(); 86. return c; 87. } 88. #undef idg 8 #undef gc // beginning int n, m; 94. arr G[maxn], dis, vis, pre; void input() { 97. n = rd(), m = rd(); 98. rep (i, 1, n) rep (j, 1, n) G[i][j] = n * 200; 9 rep (i, 1, m) { 100. int u = rd(), v = rd(), w = rd(); 101. G[u][v] = G[v][u] = w; 102. } 103. } inline void dijk() { 106. rep (i, 1, n) dis[i] = inf; 107. dis[1] = 0; 108. rep (x, 1, n) { 10 int u = 0; 1 rep (i, 1, n) if (!vis[i] && (!u dis[i] < dis[u])) u = i; 111. if (!u) break; 112. vis[u] = 1; 113. rep (v, 1, n) if (!vis[v] && G[u][v] <= 100) { 114. if (dis[v] > dis[u] + G[u][v]) { 115. dis[v] = dis[u] + G[u][v]; 116. pre[v] = 1; 117. } else if (dis[v] == dis[u] + G[u][v]) 118. pre[v] ++; 11 } 120. } 121. } void solve() { 124. dijk(); 125. // garr(pre, 1, n, "%d"); 126. int ans = 1; 127. rep (i, 2, n) ans = 1ll * ans * pre[i] % ; 128. printf("%d\n", ans); 12 }

8 int main() { 132. #ifndef ONLINE_JUDGE 133. freopen("data.txt", "r", stdin); 134. #endif 135. input(); 136. solve(); 137. return 0; 138. } 2. Problem: User: noip Time:470 ms 7. Memory:18672 kb 11. #include<cstdio> 12. #include<cstring> 13. typedef long long ll; 14. const int maxn=1005,maxe= ,maxe=500005,inf=1<<30; 15. ll mod= ll; 16. int head[maxn],to[maxe],next[maxe],len[maxe],dis[maxn],st[maxe],en[maxe],l[maxe],n,m,cnt; 17. bool inq[maxn]; 18. ll ans=1; 1 struct Queue 20. { 21. int num[maxn],s,t; 22. bool empty(){return s==t;} 23. int nxt(int x){return x==n-1?0:x+1;} 24. void pop(){s=nxt(s);} 25. void push(int x){num[t]=x;t=nxt(t);} 26. int front(){return num[s];} 27. void reset(){s=t=0;} 28. }q; 2 void insert(int a,int b,int c){to[cnt]=b,len[cnt]=c,next[cnt]=head[a];head[a]=cnt++;} 30. void spfa() 31. { 32. q.reset();q.push(1);memset(inq,0,sizeof inq);inq[1]=1; 33. for(register int i=1;i<=n;++i)dis[i]=inf;dis[1]=0; 34. int u; 35. while(!q.empty()) 36. { 37. inq[u=q.front()]=0;q.pop(); 38. for(register int i=head[u],v=to[i];~i;v=to[i=next[i]])if(dis[v]>dis[u]+len[i]) 3 { 40. dis[v]=dis[u]+len[i]; 41. if(!inq[v])q.push(v),inq[v]=1; 42. } 43. } 44. } 45. int main() 46. { 47. memset(head,-1,sizeof head); 48. scanf("%d%d",&n,&m);for(register int i=1;i<=m;++i)scanf("%d%d%d",st+i,en+i,l+i),insert(st[i],en[i],l[i]),insert(en[i],st[i],l[i]); 4 spfa(); 50. for(register int s=2;s<=n;++s) 51. { 52. cnt=0; 53. for(register int i=head[s],v=to[i];~i;v=to[i=next[i]])if(dis[v]+len[i]==dis[s])++cnt; 54. (ans*=cnt)%=mod; 55. } 56. printf("%lld\n",ans); 57. return 0; 58. } 2. Problem: User: ez_myh 6. Time:192 ms 7. Memory:5044 kb 11. #include <cstdio> 12. #include <cstring> 13. #include <algorithm> 14. #include <utility> 15. #define FR first 16. #define SE second using namespace std; typedef long long ll; 21. typedef pair<int,int> pr; int e[1005][1005]; int dis[1005]; 26. bool check[1005]; pr a[1005]; void dijkstra(int n) { 31. memset(dis,0x7f,sizeof(dis)); 32. dis[1]=0; 33. for(int i=1;i<n;i++) { 34. int p=0; 35. for(int j=1;j<=n;j++) 36. if (!check[j]&&dis[j]<dis[p]) p=j; 37. check[p]=true; 38. for(int j=1;j<=n;j++) 3 if (!check[j]&&e[p][j]) dis[j]=min(dis[j],dis[p]+e[p][j]); 40. } 41. } int main() { 44. int n,m; 45. scanf("%d%d",&n,&m); 46. for(int i=1;i<=m;i++) { 47. int x,y,z; 48. scanf("%d%d%d",&x,&y,&z); 4 e[x][y]=z; 50. e[y][x]=z; 51. } 52. dijkstra(n); 53. for(int i=1;i<=n;i++) a[i]=pr(dis[i],i); 54. sort(a+1,a+n+1); 55. int ans=1; 56. for(int i=2;i<=n;i++) { 57. int p=a[i].se,s=0; 58. for(int j=1;j<i;j++) { 5 int q=a[j].se; 60. if (e[q][p]&&dis[q]+e[q][p]==dis[p]) s++;

9 } ans=(ll)ans*s%0x7fffffff; 63. } 64. printf("%d\n",ans); 65. return 0; 66. } NOIP2016 Simulation Nr. 50 Problem A NOIP2016 Simulation Nr. 50 Problem B Cmd Markdown Slash We can't type some special symbol like $#\ in formula, just append slash \backslash in the head. We can't get slash by this way because slash slash \\ means line-break. We can use \backslash. Matrix We have 3 types of matrix. We use & to separate columns, \\ to separate lines in all types. Syntax: 1. \begin{matrix type} 2. 1 & pi^2 \\ 3. x & e 4. \end{matrix type} matrix for pmatrix for bmatrix} for M3. Inline-code Use `code` for code. You can type some special symbols without slash here. Table for 1. 项目价格数量 : :----: 3. 计算机 \$ 手机 \$ 管线 \$1 234 项目价格数量计算机 $ 手机 $12 12 管线 $1 234

新版明解C++入門編

新版明解C++入門編 511!... 43, 85!=... 42 "... 118 " "... 337 " "... 8, 290 #... 71 #... 413 #define... 128, 236, 413 #endif... 412 #ifndef... 412 #if... 412 #include... 6, 337 #undef... 413 %... 23, 27 %=... 97 &... 243,