Noip2016 六校模拟 AHSDFZ Round 2

tonyfang posted @ 2016年11月08日 10:50 in 随笔 with tags C++ OI , 369 阅读
A. 数数
小Star还不会数。有一天 他看到了一张奇怪的数表,上面每个数各自都由相同数字构成,比如“11111111”“66666”。于是他想自己从1慢数到这个数字。Star有个很不好的习惯, 每数到一定个就会从头开始数起。现在请你帮忙求出,他最后数出来的数是多少。
对于30%的数据,$Q \leq 100, p \leq 10^4, n \leq 10^4$;
对于60%的数据,$Q \leq 1000, p \leq 10^4, n \leq 10^9$;
对于额外20%的数据,$Q \leq 10^5, p \leq 10^8, n \leq 10^{18}$,$p$为质数;
对于100%的数据,$Q \leq 10^5, p \leq 10^8, n \leq 10^{18}, 1 \leq x \leq 9$。
【题解】可以发现一些奇怪的特性来构造这个数列
# 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;

int Q;
int x, p;
ll n;

ll pwr(ll x, ll y, ll mod) {
	ll ret = 1ll;
	while(y) {
		if(y&1) ret = ret * x % mod;
		x = x*x % mod;
		y >>= 1;
	}
	return ret;
}

int main() {
	freopen("count.in", "r", stdin);
	freopen("count.out", "w", stdout);
	scanf("%d", &Q);
	while(Q--) {
		scanf("%d%lld%d", &x, &n, &p);
		ll base = pwr(10ll, n, p*9);
		-- base;
		if(base < 0) base += p*9;
		base = base / 9 * x;
		base = base % p;
		printf("%lld\n", base);
	}
	return 0;
}
B.破解石碑
相传在上古时期留下了许多块神秘的石碑, 石碑的正面按顺序刻上$n$个数字,并且每个数字的下方都有一个字号较小的数相对应。研究人员把上面的数字称为$A$列,下面的数字称为$B$列。在查阅古书后人们得知,每块石碑其实都是一把锁 。如果人们在石碑上按合适的方法对数字进行操作 ,就会获得巨大的能量。 操作的规则如下:
若$A_i$和$A_{i+1}$不互 质,我们可以在原石碑中抹去第$i$和第$i + 1$个数(包括$A$中和$B$中),然后将两个序列重新按顺序编号。
假如最终$B$列中被抹去的数和达到可能的最大值,这把巨锁就解开了。由于对石碑上数字的抹去是不可逆,为了不浪费每块石碑,我们必须事先计算出每块石碑的操作方案并获得 $B$列被删去的可能最大和。
对于30%的数据,$n \leq 20$;
对于60%的数据,$n \leq 100$;
对于80%的数据,$n \leq 500$;
对于100%的数据,$n \leq 800, 1 \leq A_i, B_i \leq 10^9$。
【题解】直接区间dp即可。
# include <stdio.h>
# include <algorithm>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int M = 810;
ll f[M][M];
int a[M], b[M], n;
ll s[M];

int main() {
	freopen("stele.in", "r", stdin);
	freopen("stele.out", "w", stdout);
	scanf("%d", &n);
	for (int i=1; i<=n; ++i) scanf("%d", &a[i]);
	for (int i=1; i<=n; ++i) scanf("%d", &b[i]), s[i] = s[i-1] + b[i];
	for (int len=1; len<n; ++len)
		for (int i=1; i+len<=n; ++i) {
			int j=i+len;
			if(f[i+1][j-1] == s[j-1] - s[i] && __gcd(a[j], a[i]) > 1) f[i][j] = s[j] - s[i-1];
			else {
				for (int k=i; k<j; ++k)
					f[i][j] = max(f[i][j], f[i][k] + f[k+1][j]);
			}
		}
	printf("%lld\n", f[1][n]);
	return 0;
}
C.宏操作
在计算机程序设计中,定义宏是一种非常重要的简化代码的手段。一般说来,宏是一种规则或模式称语法替换用于说明某特定输入(通常字符串)如何根据预定义的规则转换成对应输出(通常也是字)。但是,过量的宏嵌套往使得代码逻辑复杂,难以理解。
某天,Star定义了一系列的宏来对数组$A$进行操作,这些宏具有这样的结构:
 1.    加法宏:给定$i,k$,执行$A[i] = A[i] + k$;
 2.    乘法宏:给定$k$,对任意$i$执行 $A[i] = A[i] \times k $;
 3.    复合宏:给定$i,j$,先执行第$i$个宏,再执行第$j$个宏。
最后Star发现,自己定义的宏在逻辑上恰好形成了一棵没有度为1的结点的二叉树,其中叶子结点为加法或乘的基本宏 。
Star的$A$数组大小为$n$,共有$m$个基本宏、$m-1$个复合宏 。程序中共 调 用了$q$次宏 。Star的编译器被绕晕了已经罢工,现在请你帮忙计算出程序运行之后数组中每个元素的结果(假定对数组元素的修改操作都会自动在模 998244353的同余系下进行。)
对于30%的数据 ,$n \leq 100,~m,q \leq 200$;
对于60%的数据 ,$n \leq 100,~m \leq 10000,~q \leq 20000$;
对于80%的数据 ,$m \leq 10000,~q \times n \leq 2000000$;
对于100%的数据 ,$n, m, q \leq 100000$,基本宏中的$k$均为不超过10000的正整数;
有50%的数据散落在所有数据中,满足基本宏均为加法。
【题解】(90分)对于50%线段树,其他暴力,待填坑
# 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;

/* ============ define "define" ============ */
int type[M], pos[M], del[M];
int lc[M], rc[M], rt[M], root;
int leaf[M], segpos[M], lnum, l[M], r[M];
// segpos[i]: 线段树中[i,i]区间表示实际的基本宏
// leaf[i]: 实际的基本宏代表的线段树区间 
int n, m, q;
int leafnum = 0;
ll tag[M], a[M];
const ll mod = 998244353;

inline void build(int x) {
	if(!lc[x] && !rc[x]) {
		leaf[x] = ++leafnum;
		segpos[leafnum] = x;
		l[x] = leafnum, r[x] = leafnum;
		return ;
	}
	if(lc[x]) build(lc[x]);
	if(rc[x]) build(rc[x]);
	l[x] = l[lc[x]];
	r[x] = r[rc[x]];
}

inline void add(int x, int L, int R) {
//	printf("%d left = %d, right = %d, L = %d, R = %d\n", x, l[x], r[x], L, R);
	if(L == l[x] && r[x] == R) {
		tag[x] ++;
		if(tag[x] >= mod) tag[x] -= mod;
		return ;
	}
	int mid = (l[x]+r[x])>>1;
	if(lc[x] != 0 && R <= r[lc[x]]) {
		add(lc[x], L, R);
	}
	if(lc[x] != 0 && L >= l[rc[x]]) {
		add(rc[x], L, R);
	} 
}

inline ll query(int x, int pos) {
	if(l[x] == r[x]) return tag[x];
	if(pos <= r[lc[x]]) return query(lc[x], pos) + tag[x];
	if(pos >= l[rc[x]]) return query(rc[x], pos) + tag[x];
}

inline void putforward(int x) {
//	printf("%d %d %d\n", x, lc[x], rc[x]);
//	system("pause");
	if(!lc[x] && !rc[x]) {
		if(type[x] == 1) a[pos[x]] += del[x], a[pos[x]] %= mod;
		else {
			for (int i=1; i<=n; ++i) a[i] *= del[x], a[i] %= mod;
		}
		return ;
	}
	if(lc[x]) putforward(lc[x]);
	if(rc[x]) putforward(rc[x]);
}

int main() {
	freopen("macro.in", "r", stdin);
	freopen("macro.out", "w", stdout);
	scanf("%d%d%d", &n, &m, &q);
	bool all = 1;
	for (int i=1; i<=m; ++i) {
		scanf("%d", &type[i]), all &= (type[i] == 1), rt[i] = 1;
		if(type[i] == 1) scanf("%d%d", &pos[i], &del[i]);
		else scanf("%d", &del[i]);
	}
	for (int i=1; i<m; ++i) 
		scanf("%d%d", &lc[i+m], &rc[i+m]), type[i+m] = 3, rt[lc[i+m]] = 1, rt[rc[i+m]] = 1;
	for (int i=1; i<=m+m-1; ++i)
		if(!rt[i]) {
			root = i;
			break;
		}
	if(all) {
//		printf("%d\n", root);
		build(root);
		while(q--) {
			int pos; scanf("%d", &pos);
//			printf("%d %d\n", l[pos], r[pos]);
			add(root, l[pos], r[pos]);
		}
		for (int i=1; i<=m; ++i) {
			ll act = query(root, leaf[i]);
//			printf("%lld\n", act); 
			a[pos[i]] += act * del[i] % mod;
			a[pos[i]] %= mod;
		}
		for (int i=1; i<=n; ++i) printf("%lld ", a[i]);
		puts("");
		return 0;
	}
	while(q--) {
		int pos;
		scanf("%d", &pos);
//		printf("%d %d %d\n", pos, lc[pos], rc[pos]);
		putforward(pos);
	}
	
	for (int i=1; i<=n; ++i) printf("%lld ", a[i]%mod);
	 
	return 0;
}

 


登录 *


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