学习笔记--构造Divisible subsetHack itA Problem Concerning LCSBags and CoinsStack Machine Programmer

72 阅读 0 评论 48 点赞

我是靠谱客的博主洁净钢笔，最近开发中收集的这篇文章主要介绍学习笔记--构造Divisible subsetHack itA Problem Concerning LCSBags and CoinsStack Machine Programmer，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

%%% FSYo Orz orz orz

Divisible subset

题目大意：给定一个长度为 $n$ 的 multiset，找到一个非空子集，满足子集中的元素的和能被 $n$ 整除，或者判断这样的集合不存在。

首先，对这个数组做一个模 $n$ 的前缀和，如果我们找到了前缀和中有不同的两个位置相等，即 $S_l = S_r$ ，那么我们就找到了一个区间 $[l, r]$ ，这个区间内的所有数的和模 $n$ 得 0。即这个区间内的所有数的和是 $n$ 的倍数。那么我们就找到了这个子集。现在就要判定能不能找到 $S_l = S_r$ ，因为我们对所有的 $S_i$ 都对 $n$ 取模，所以 $S_i in [0, n-1]$ ，总共有 $n$ 种取值，而我们的前缀和数组一共有 $n + 1$ 个值（因为我们把 $S_0 = 0$ 也放在前缀和里面，不然的话 $n = 5 ， a = {3, 3, 3, 3, 3}$ ，这组数据就会被 hack 掉）。根据抽屉原理，必定有两个数值是相同的。

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100100
#define MAXA 100100

int n = 0;
int a[MAXN] = { 0 };
int s[MAXN] = { 0 };

struct Tnode{
	int idx[10];
	int cnt1, cnt2;
};
Tnode tong[MAXN] = { 0 };

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for(int i = 0; i <= n; i++){
		s[i] = (s[i-1] + a[i]) % n;
		tong[s[i]].cnt1++; tong[s[i]].idx[++tong[s[i]].cnt2] = i; 
	}
	for(int i = 0; i <= n; i++)
		if(tong[s[i]].cnt1 > 1){
			cout << tong[s[i]].idx[1] + 1 << ' ' << tong[s[i]].idx[2] << endl;
			return 0;
		}
	return 0;
}

Hack it

题目大意：令 $f (x)$ 表示 $x$ 在十进制下各位数字的和。给定一个整数 $a$ ，让你构造一个整数 $a$ 使得：
$sum_{i = l}^r f(i) equiv 0 pmod a qquad ain[1, 10^{18}]， l, rin[1, 10^{200}]$

我们发现如果找到一个 $k$ ，使得 $10^k >> x$ ，那么 $f(x + 10^k) = f(x) + 1$ 。现在我们考虑一个区间： $1, 10^k]$ ，我们把这个区间的第一个数字 $1$ 加上一个 $10^k$ ，这个区间就变成了： $2, 10^k + 1]$ ，而这个区间的 $T$ 加了 1。我们再把操作之后的区间的第一个数字加上 $10^k$ ，这个区间就变成了： $3, 10^k+2]$ ，这个区间的 $T$ 又在原来的基础上加了 1。所以如果我们想让这个区间的 $T$ 加上 $x$ ，那么我们就让 $1, 10^k]$ ，变成 $1+x, 10^k + x]$ 就好了。

知道了这个，我们就可以考虑先用数位 DP（不会数位 DP 也可以手推 qwq），把 $10^k]$ 的 $T$ 算出来，再把区间整体向右平移 $a - T$ 就好了，也就是把区间变成 $1+a-T, 10^k+a-T]$ 。

现在来讲一下如何手推 $1, 10^k]$ 的 $T$ 。我们首先可以算出 $1, 10^k-1]$ 的 $T$ ，然后再加上 1 就好了。那么首先可以手算出 $T ([1, 9]) = 45$ 。然后看 $T ([1, 99])$ ，我们考虑算每一位的贡献，个位数的贡献每轮都从 1 到 9，然后一共有 10 轮，所以是 45 * 10，然后是十位数的贡献，十位数从 1 到 9 每个数出现 10 次，所以也是 45 * 10，总共为 45 * 20 = 900。然后是 $T ([0, 999])$ ，同理，先算百位数的贡献，是 100 * 45.。然后是个位和十位的贡献，因为我们已经算出来了 $T ([0, 99])$ ，所以我们可以考虑把十位个个位放在一起考虑，每次都是从 0 到 99，总共轮了 10 次，所以就是 10 * $T ([1, 99])$ ，加起来就是 300 * 45 = 13500。

好了，现在我们找到了规律，也就是：
$10^k]) = 45k times 10^{k-1} + 1$

然后我们就可以解决这道题了。

#include<bits/stdc++.h>
typedef long long ll;
#define Pow18 (ll)1e18

ll a = 0;
ll l = 0; ll r = 0;

int main(){
    scanf("%lld", &a);
    l = a - Pow18 % a * 9 % a * 9 % a;
    r = l + Pow18 - 1;
    printf("%lld %lldn",l,r);
}

A Problem Concerning LCS

题目大意：给定一个仅有 “A”，“T”，“C”，“G” 构成的长度为 $10^6$ 的字符串 $a$ 。要求构造一个长度同为 $n$ 字符串 $b$ ，使得 $a ， b$ 的 LCS 最短。

你多写几个字符串出来你就会发现，满足条件的 $b$ 显然就是全部都是 “ATCG” 中的其中一个字母，然后这个字母就是 $a$ 串中出现次数最小的，我们可以证明这个结论。假设 $a$ 中出现次数最少的是 “A”，那么显然 “A” 的出现次数（我们设为 $x$ ）小于等于 $n 4 frac n4$ 。如果全用 “A” 来构造 $b$ 串，那么 LCS 的长度就是 $x$ 。假设存在 $b^{'}$ 使得它与 $a$ 的 LCS 小于长度 $x$ ，那么 $b^{'}$ 中所有字母的出现次数都要小于 $n 4 frac n4$ 。所以 $b^{'}$ 的长度小于 $n$ ，但是 $b^{'}$ 的长度又等于 $n$ ，矛盾了，所以不存在这样的 $b^{'}$ 。

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

char a[MAXN];

int main(){
	scanf("%s", a + 1); int n = strlen(a + 1);
	int A = 0; int T = 0; int C = 0; int G = 0;
	for(int i = 1; i <= n; i++)
		if(a[i] == 'A') A++;
		else if(a[i] == 'T') T++;
		else if(a[i] == 'C') C++;
		else G++;
	int x = min(min(A, T), min(C, G));
	if(x == A) for(int i = 1; i <= n; i++) cout << 'A';
	else if(x == T) for(int i = 1; i <= n; i++) cout << 'T';
	else if(x == C) for(int i = 1; i <= n; i++) cout << 'C';
	else for(int i = 1; i <= n; i++) cout << 'G';
	puts("");
	return 0;
}

Bags and Coins

题目大意：有 $s$ 个硬币，有 $n$ 个包。一个包可以放在其他包里面，可以多层嵌套。如果拿出一个硬币必须打开第 $i$ 个包，那我们就说第这个硬币在第 $i$ 个包里。现在已知第 $i$ 个包里有 $a_i$ 个硬币，构造一种满足上述条件的方案。 $a_i leq 70000$

可以把一个包a 里面的包b 看成是包a 是包b 的父节点。于是我们可以把整个嵌套结构看成一颗树。于是我们想到一颗最特别的树，也就是一条链。但是我们发现一个问题 $maxlimits_{i=1}^n a_i$ 可能小于 $s$ ，也就是说如果只有一条链的话，有些硬币可能就没有被放进包里。于是我们试着构造多条链，使得这些链的根节点所包含的硬币数的和等于总硬币数 $s$ 就好了。

Stack Machine Programmer

题目大意：有一个计算机，它只能存储整数，它只有一个栈作为存储器，它支持一下好几种操作：

NUM X：将一个非负整数数 $X$ 压入栈。
POP：弹出栈顶的数。
INV：将栈顶的数取相反数。
DUP：将栈顶的数复制一份再压入栈中。
SWP：交换栈顶的两个数。
ADD：将栈顶的两个数弹出，并将它们俩的和压入栈。
SUB：将栈顶的两个数弹出，并将它们俩的差压入栈。
MUL：将栈顶的两个数弹出，并将它们俩的积压入栈。
DIV：将栈顶的两个数弹出，并将它们俩的商的整数部分压入栈。
MOD：将栈顶的两个数弹出，并将它们俩相除的余数压入栈。

一个程序会按照顺序执行所有命令，给定在这个 Stack Machine 上一个程序的 $n, (n \leq 5)$ 组输入和输出（每组输入输出为两个整数），要求你构造一个程序能够使得给定的输入经过这个程序的处理能输出给定的输出（程序中只能使用上面给出的所有操作）。对于每个输入输出 $(I, O)$ ， $0 \leq I \leq 100 \leq O \leq 20$ ，要求你构造的程序的长度不得超过 $10^5$ 。