1. 火柴问题

【题目大意】

我们用火柴棒表示十进制下0~9

给定火柴数量$n$，问能摆出的最大、最小的数分别是多少

$n <= 100$

【题解】

很明显最大数一定是111…1或者711…1，只需要判断奇数偶数就行了

最小数的后缀一定是88…8，前面根据火柴的多少有不同的放法，而且只影响前三位（可以证明）

# include <stdio.h>
using namespace std;

int T, n, t, res;
int used[10]={6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
int rres[66]={-1, -1, -1, -1, -1, -1, -1, -1, 10, 18, 22, 20, 28, 68, -1, 108, 188, 200, 208, 288, 688};
int main() {
	freopen("match.in", "r", stdin);
	freopen("match.out", "w", stdout);
	scanf("%d", &T);
	while(T--) {
		t=0;
		scanf("%d", &n);
		if(n%7 == 0) {
			t = n/7;
			for (int i=1; i<=t; ++i)
				printf("8");
		} else {
			if(n<7) {
				if(n==2) printf("1");
				if(n==3) printf("7");
				if(n==4) printf("4");
				if(n==5) printf("2");
				if(n==6) printf("6");
			} else if (7<n && n<14) {
				printf("%d", rres[n]);
			} else {
				t = n/7 - 2;
				res = n - t*7;
				printf("%d", rres[res]);
				for (int i=1; i<=t; ++i) printf("8");
			}
		}
		printf(" ");
		if(n%2 == 0) {
			t = n/2;
			for (int i=1; i<=t; ++i) printf("1");
		} else {
			t = n/2 - 1;
			printf("7");
			for (int i=1; i<=t; ++i) printf("1");
		}
		printf("\n");
	}
	return 0;
}

2. 覆盖

【题目大意】

定义$(x, 0)$到$[L, R]$覆盖范围，若$x<L$或$x>R$，那么覆盖范围为0，否则，覆盖范围为$min(x-L, R-x)$

给定n条线段$[Li, Ri]$，q条询问，每条询问包含一个点$(xi, 0)$；求该点到所有线段的覆盖范围的最大值

$n, m <= 10^5 Li, Ri <= 10^9$

【题解】

用两个堆，类似于扫描线的方法处理，左边的堆 线段改为[l, mid]，右边改为[mid+1, r]

我们每次取出最大/最小就行啦！

multiset大法好！

# include <bits/stdc++.h>
using namespace std;

int T, n, m, l[100010], r[100010], x[100010];
struct point {
	int pos, lx, id, prev;
}f[666666], g[666666];
int fn, gn;
int ans[666666];
// lx: 0 in  2 out  1 question

inline int cmp1(point x, point y) {
	if(x.pos!=y.pos) return x.pos < y.pos;
	return x.lx < y.lx;
}
inline int cmp2(point x, point y) {
	if(x.pos!=y.pos) return x.pos > y.pos;
	return x.lx < y.lx;
}
multiset<int> s;
multiset<int,greater<int> > t;

int main() {
	freopen("cover.in", "r", stdin);
	freopen("cover.out", "w", stdout); 
	scanf("%d", &T);
	for (int Test = 1; Test <= T; ++Test) {
		fn = gn = 0;
		printf("Case %d:\n", Test);
		scanf("%d%d", &n, &m);
		for (int i=1; i<=n; ++i) {
			scanf("%d%d", &l[i], &r[i]);
			f[++fn].pos = l[i];
			f[fn].lx = 0;
			f[++fn].pos = (l[i]+r[i]) >> 1;
			f[fn].lx = 2;
			f[fn].prev=l[i];
			g[++gn].pos = r[i];
			g[gn].lx = 0;
			g[++gn].pos = (l[i]+r[i]+1) >> 1;
			g[gn].lx = 2;
			g[gn].prev=r[i];
		}
		for (int i=1; i<=m; ++i) {
			scanf("%d", &x[i]);
			f[++fn].pos = x[i];
			f[fn].lx = 1;
			g[++gn].pos = x[i];
			g[gn].lx = 1;
			g[gn].id = f[fn].id = i;
		}
		sort(f+1, f+fn+1, cmp1);
		sort(g+1, g+gn+1, cmp2);
		s.clear();
		for (int i=1; i<=fn; ++i) {
			if(f[i].lx == 0) {
				s.insert(f[i].pos);
			} else if(f[i].lx == 2) {
				s.erase(s.lower_bound(f[i].prev));
			} else if(f[i].lx == 1) {
				if(s.size() > 0)
					ans[f[i].id] = x[f[i].id] - *s.begin();
				else ans[f[i].id] = 0;
			}
		}
		t.clear();
		for (int i=1; i<=gn; ++i) {
			if(g[i].lx == 0) {
				t.insert(g[i].pos);
			} else if(g[i].lx == 2) {
				t.erase(t.lower_bound(g[i].prev));
			} else if(g[i].lx == 1) {
				if(t.size() > 0) 
					ans[g[i].id] = max(ans[g[i].id], *t.begin() - x[g[i].id]);
				else ans[g[i].id] = max(ans[g[i].id], 0);
			}
		}
		for (int i=1; i<=m; ++i) printf("%d\n", ans[i]);
	}	
	return 0;
}

3. 染色

【题目大意】

一行总长度为n的长龙由公共汽车组成，可能是长度为5或10的车。

长度为5的车有k种不同染色方法，长度为10的车有l种不同染色方法。

问总共有多少种染色方法。

$n <= 10^{15}$

【题解】

dp，f[i]表示前i*5有多少种染色方法，f[i] = f[i-1] * k +f[i-2] * l

那么我们只需要矩乘优化即可。复杂度O(logn)

# include <stdio.h>
# include <string.h>

using namespace std;

long long n, k, l, times;
const long long MOD = 1000000;
// f[i] 前i*5米方案数量

struct matrix {
	int n, m;
	long long a[101][101];
}zy, start;

inline struct matrix mul(struct matrix a, struct matrix b) {
	struct matrix c;
	memset(c.a, 0, sizeof(c.a));
	c.n = a.n, c.m = a.m;
	for (int i=1; i<=c.n; ++i)
		for (int j=1; j<=c.m; ++j)
			for (int k=1; k<=a.m; ++k)
				c.a[i][j] = (c.a[i][j] + a.a[i][k] * b.a[k][j] % MOD) % MOD;
	return c;
}

inline struct matrix power(struct matrix a, long long b) {
	struct matrix ans;
	ans.n = ans.m = 2;
	ans.a[1][1] = ans.a[2][2] = 1;
	ans.a[1][2] = ans.a[2][1] = 0;
	while(b > 0) {
		if(b&1) ans = mul(ans, a);
		a = mul(a, a);
		b /= 2;
	}
	return ans;
}

int main() {
	freopen("color.in", "r", stdin);
	freopen("color.out", "w", stdout);
	while(~scanf("%lld%lld%lld", &n, &k, &l)) {
		memset(zy.a, 0, sizeof(zy.a));
		memset(start.a, 0, sizeof(start.a));
		k = k % MOD; l = l % MOD;
		zy.n = 2, zy.m = 2;
		zy.a[1][1] = k, zy.a[1][2] = l;
		zy.a[2][1] = 1; zy.a[2][0] = 0;
		start.n = 2, start.m = 1;
		start.a[1][1] = l+k*k, start.a[2][1] = k;
		times = n/5-1;
		zy = power(zy, times);
		//printf("%lld %lld\n%lld %lld\n", zy.a[1][1], zy.a[1][2], zy.a[2][1], zy.a[2][2]);
		start = mul(zy, start);
		printf("%06lld\n", start.a[2][1]);
	}
	return 0;
}
					

upd: 知乎“如何评价Noi 2016 Day1的题目”抽屉的回答真是6啊！