20160725 训练记录

tonyfang posted @ 2016年7月30日 08:01 in 随笔 with tags c++ OI , 657 阅读

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的长龙由公共汽车组成,可能是长度为510的车。

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

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

$n <= 10^{15}$

【题解】

dpf[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啊!

ekhan.net 说:
2023年6月18日 15:57

Registration for Indian Overseas Bank (IOB) Mobile Banking, How to Update/Register Your Cell Number with Indian Overseas Bank, The recommendations of the Reserve Bank of India are followed by the national bank Indian Overseas Bank. ekhan.net The bank has been offering a variety of handy services and amenities to its public banking clients. Registration for Indian Overseas Bank (IOB) Mobile Banking, How to Update/Register Your Cell Number with Indian Overseas Bank, The recommendations of the Reserve Bank of India are followed by the national bank Indian Overseas Bank. The bank has been offering a variety of handy services and amenities to its public banking clients.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter