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;
}