Noip2016 四校联考 FJSDFZ Round 2
1. rope
有$n$个球排成一列挂在空中,第i个球与第i+1个球用绳子或者弹簧相连,第$n$个球与天花板相连,现在剪断第i个球与第$i+1$个球之间的绳子或弹簧(或是第$n$个球与天花板之间的绳子或弹簧),你的任务是计算剪断后每个球的加速度/当地重力加速度的值。
$n \leq 100$
【题解】受力分析发现只影响cut的上面的第一个弹簧到下面的第一个弹簧这之间的部分。
然后讨论下就行了。
# include <stdio.h> // # include <bits/stdc++.h> using namespace std; int n, t[110], cut; double w[110]; double a[110]; int main() { freopen("rope.in", "r", stdin); freopen("rope.out", "w", stdout); scanf("%d", &n); for (int i=1; i<=n; ++i) scanf("%lf%d", &w[i], &t[i]); scanf("%d", &cut); int upf = 0; // actually down double upall = 0.0, ups = 0.0; for (int i=cut-1; i>=1; --i) { if(t[i] == 1) { upf = i; break; } ups += w[i]; } upall = ups; for (int i=upf; i>=1; --i) upall += w[i]; int downf = n; // actually up double downs = 0.0; for (int i=cut+1; i<=n; ++i) { downs += w[i]; if(t[i] == 1) { downf = i; break; } } // printf("%d %d %.3lf %.3lf %.3lf\n", upf, downf, ups, downs, upall); for (int i=upf; i>=1; --i) a[i] = 0; for (int i=downf+1; i<=n; ++i) a[i] = 0; for (int i=upf+1; i<=cut; ++i) a[i] = (double)(upall+w[cut])/(ups+w[cut]); if(downf != n) { for (int i=cut+1; i<=downf; ++i) a[i] = (double)(upall+w[cut])/downs, a[i] = -a[i]; } else { for (int i=cut+1; i<=n; ++i) a[i] = 0; } for (int i=1; i<=n; ++i) printf("%.2lf\n", a[i]); return 0; }
2. triangle
在一个圆周上分布着n个节点,每2个节点之间用红色线或蓝色线连接,你的任务是统计三条边同色的三角形数目。
$n \leq 1000, T \leq 5$。
【题解】
统计异色三角形数目,然后用总数$\frac{n(n-1)(n-2)}{6}$减去即可。
考虑如何统计异色三角形:一定有一对异色边连在同一个点上,统计这种边的对数后除以2即可。
# include <stdio.h> // # include <bits/stdc++.h> using namespace std; const int M = 1010; int T, n, a[M][M]; typedef long long ll; ll ans = 0; int main() { freopen("triangle.in", "r", stdin); freopen("triangle.out", "w", stdout); scanf("%d", &T); while(T--) { ans = 0; scanf("%d", &n); for (int i=1; i<=n; ++i) { a[i][i] = 0; for (int j=i+1; j<=n; ++j) scanf("%d", &a[i][j]); } for (int i=1; i<=n; ++i) for (int j=1; j<i; ++j) a[i][j] = a[j][i]; for (int i=1; i<=n; ++i) { int A=0, B=0; for (int j=1; j<=n; ++j) { if(i == j) continue; A += (a[i][j] == 1); B += (a[i][j] == 0); } ans += (ll)A*B; } ll all = (ll)n * (n-1) * (n-2) / 6; ans = all - ans/2; printf("%lld\n", ans); } return 0; }
3. code
给出一段代码,求对于给定的数据,输出“Find”的概率对于$10^9+7$取模。
#include<cstdio> #include<iostream> #include<cstdlib> #include<ctime> #include<set> using namespace std; set<int>st; int main() { srand(time(NULL)); int n,m; cin>>n>>m; while (n>0) { n=rand()%n; st.insert(n); } for (int i=1;i<=m;i++) { int check; cin>>check; if (st.count(check)==0) { cout<<"Not find"<<endl; return 0; } } cout<<"Find"<<endl; return 0; }
$m \leq n \leq 1000, -1000 \leq check \leq 1000$
【题解】
可以证明,答案就是把所有不同的$(check+1)$乘起来取个逆元即可。
# include <stdio.h> # include <algorithm> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 500010, mod = 1e9+7; int n, m, a[110]; bool cnt[110]; inline int pwr(int x, int y) { int ret = 1; while(y) { if(y&1) ret = 1ll * ret * x % mod; x = 1ll * x * x % mod; y >>= 1; } return ret; } int main() { freopen("code.in", "r", stdin); freopen("code.out", "w", stdout); scanf("%d%d", &n, &m); for (int i=1; i<=m; ++i) { scanf("%d", &a[i]); if(a[i]<0 || a[i]>=n) { puts("0"); return 0; } cnt[a[i]]=1; } int ans = 1; for (int i=0; i<n; ++i) if(cnt[i]) ans = 1ll * ans * (i+1) % mod; printf("%d\n", pwr(ans, mod-2)); return 0; }