2021csp 赛前第一次集训 - 数学专题

• 进制、余数的理解
• 递归、栈

#include 
using namespace std;

int n, r;
string c = "0123456789ABCDEFGHIJ";

void f(int n) {
	if (n == 0) return;
	
	int t = n % r;
	if (t < 0) t -= r, n += r;
	
	f(n/r);
	cout << c[t];
}

int main() {
	scanf("%d%d", &n, &r);
	printf("%d=", n);
	f(n);
	printf("(base%d)n", r);

	return 0;
}

#include 
using namespace std;

int n, r;
string c = "0123456789ABCDEFGHIJ";
stack  stk;

int main() {
	scanf("%d%d", &n, &r);
	printf("%d=", n);
	
	while (n) {
		int t = n % r;
		if (t < 0) t -= r, n += r;
		
		n /= r;
		stk.push(c[t]);
	}
	
	while (stk.size()) printf("%c", stk.top()), stk.pop();
	
	printf("(base%d)n", r);

	return 0;
}

• 递归，二分

#include 
#define ull unsigned long long
using namespace std;

ull n, k;

void f(ull n, ull k) {
	if (n == 0) return;

	n --;
	ull t = (1ull << n);
	if (k < t) {    //左侧
		cout << 0;
		f(n, k);
	}
	else {          //右侧
		cout << 1;
		f(n, 2*(t-1) - (k-1));
	}
}

int main() {
	cin >> n >> k;
	f(n, k);

	return 0;
}

• 生成字符串，查找，50分

#include 
#define ull unsigned long long
using namespace std;

ull n, k;
string s = "01", t;
stack  stk;

int main() {
	cin >> n >> k;

	for (int i = 1; i <= n; i ++) {
		t = s;
		reverse(t.begin(), t.end());
		s += t;
	}

	for (int i = n - 1; i >= 0; i --) {
		int x = k >> i;
		cout << s[x];
	}
	
	return 0;
}

• 观察到规律，格雷码是“0110”这4个数字不断循环，100分

#include 
#define ull unsigned long long
using namespace std;

ull n, k;
string s = "0110";

int main() {
	cin >> n >> k;

	for (int i = n - 1; i >= 0; i --) {
		ull x = k >> i;
		cout << s[x%4];
	}
	
	return 0;
}

• 杨辉三角、组合数
• 强调长整型、结果取模
• 数组长度

#include 
#define LL long long
using namespace std;

const int MOD = 10007;
int f[1009][1009];
LL a, b, k, n, m;

int main() {
	cin >> a >> b >> k >> n >> m;
	f[0][0] = 1;
	for (int i = 1; i <= k + 1; i ++) {
		for (int j = 1; j <= i; j ++) {
			f[i][j] = (f[i-1][j-1] + f[i-1][j]) % MOD;
		}
	}
		
	int ans = f[k+1][m+1];
	for (int i = 1; i <= n; i ++) ans = ans * a % MOD;
	for (int i = 1; i <= m; i ++) ans = ans * b % MOD;	
	cout << ans << endl;
	
	return 0;
}

• 预处理所有组合数， O(n^2*t)

#include 
using namespace std;

const int N = 2009;
int t, n, m;
int a[N][N], k;

int main() {
	cin >> t >> k;

	a[0][0] = 1;
	for (int i = 1; i <= 2001; i ++) {
		for (int j = 1; j <= 2001; j ++) {
			a[i][j] = (a[i-1][j-1] + a[i-1][j]) % k;
		}
	}

	while (t --) {
		cin >> n >> m;
		int ans = 0;
		for (int i = 1; i <= n+1; i ++) {
			for (int j = 1; j <= min(i, m + 1); j ++) {
				if (a[i][j] == 0) {
					ans ++;
				}
			}
		}
		cout << ans << endl;
	}

	return 0;
}

• 利用前缀和数组进一步优化，O(n*t)

#include 
using namespace std;

const int N = 2009;
int t, n, m;
int a[N][N], cnt[N][N], k;

int main() {
	cin >> t >> k;

	a[0][0] = 1;
	for (int i = 1; i <= 2001; i ++) {
		for (int j = 1; j <= 2001; j ++) {
			a[i][j] = (a[i-1][j-1] + a[i-1][j]) % k;
			cnt[i][j] = cnt[i][j-1] + !a[i][j];
		}
	}
	
	while (t --) {
		cin >> n >> m;

		int ans = 0;
		for (int i = 1; i <= n+1; i ++) {
			ans += cnt[i][min(i, m+1)];
		}
		cout << ans << endl;
	}

	return 0;
}

• 整除性
• 长整形的输入输出

#include 
using namespace std;

int main() {
	long long a, b;
	
	scanf("%lld%lld", &a, &b);
	printf("%lldn", a * b - a - b);
	
	return 0;
}

• 拓扑排序
• 最大公约数
• 每个管道分流不超过5个，通分后分母可达到60，中间排水结点不超过10个，所以分母的最大值可达到60^11，约等于3.6e19，甚至超出了unsigned long long的范围(1.9e19)。这道题在通分的时候如果先乘后除，只能得到60分，改成先除后乘后可以得到90分。满分需要写高精度或者用long double 来实现
• 注意：用 printf 输出 unsigned long long 时，占位符是 %llu
• 90分代码：

#include 
#define ull unsigned long long
using namespace std;

const int N = 1e5 + 10, E = 1e6 + 10;
int n, m;
int h[N], to[E], ne[E], idx;
int in[N], out[N];
ull p[N], q[N];

void add(int u, int v) { to[++idx] = v; ne[idx] = h[u]; h[u] = idx; }

ull gcd(ull x, ull y) {
	if (y == 0) return x;
	return gcd(y, x % y);
}

void topsort() {
	queue  que;
	for (int i = 1; i <= n; i ++) {
		if (in[i] == 0) que.push(i), p[i] = 1;
	}

	while (que.size()) {
		int u = que.front(); que.pop();

		ull fz, fm, t;
		t = gcd(p[u], out[u]);          //先把分母和管道的分流数量约分
		p[u] /= t; out[u] /= t; q[u] *= out[u];
		
		for (int i = h[u]; i; i = ne[i]) {
			int v = to[i];
			
			t = gcd(q[u], q[v]);        //先求出分母的 gcd，尽量减小通分后的分母大小
			fz = q[v] / t * p[u] + q[u] / t * p[v];
			fm = q[u] / t * q[v];
				
			t = gcd(fz, fm);            //再约分一次
			p[v] = fz / t; q[v] = fm / t;
			
			in[v] --;
			if (!in[v] && out[v]) que.push(v);
		}
	}
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i ++) {
		q[i] = 1;                       //把分母都初始化为 1
		int d, a;
		scanf("%d", &d);
		for (int j = 1; j <= d; j ++) {
			scanf("%d", &a);
			add(i, a);
			in[a] ++; out[i] ++;
		}
	}

	topsort();

	for (int i = 1; i <= n; i ++) {
		if (out[i] == 0) {
			printf("%llu %llun", p[i], q[i]);
		}
	}

	return 0;
}

• 几何相关知识
• 邻接矩阵存储图
• 图的深搜遍历

#include 
using namespace std;

const int N = 1009;
int T, n;
int h, r, x[N], y[N], z[N];
bool e[N][N], vst[N], flag;

double dis(int u, int v) {
	double res = pow((x[u]-x[v]),2) + pow((y[u]-y[v]),2) + pow((z[u]-z[v]),2);
	return sqrt(res);
}

void dfs(int x) {
	//和上表面相交或相切
	if (z[x] >= h - r) {
		flag = true;
		return;
	}

	for (int i = 1; i <= n; i ++) {
		if (!vst[i] && e[x][i]) {
			vst[i] = true;
			dfs(i);
		}
	}
}

int main() {
	scanf("%d", &T);
	while (T --) {
		scanf("%d%d%d", &n, &h, &r);
		for (int i = 1; i <= n; i ++) scanf("%d%d%d", &x[i], &y[i], &z[i]);
		//多组数据，一定要初始化
		memset(e, 0, sizeof(e));
		memset(vst, 0, sizeof(vst));

		for (int i = 1; i <= n; i ++) {
			for (int j = i + 1; j <= n; j ++) {
				//如果两球相交或相切，则建立有向边
				if (dis(i, j) <= 2 * r) {
					e[i][j] = e[j][i] = 1;
				}
			}
		}

		flag = false;
		for (int i = 1; i <= n; i ++) {
			//和下表面相交或相切
			if (z[i] <= r) {
				vst[i] = true;
				dfs(i);
				if (flag) break;
			}
		}
		if (flag) puts("Yes");
		else puts("No");
	}

	return 0;
}