SCOI2019d1t1平台跳跃[高精]

分析

首先考虑相邻柱子之间没有浮台。

记前 \(m-1\) 个盘子为 x, 第 \(m\) 个盘子为 y，有如下过程：\(x\rightarrow C, y\rightarrow B, x\rightarrow A, y\rightarrow C, x \rightarrow C\) 。

写出递推式：\(f(m)=f(m-1)+1+f(m-1)+1+f(m-1)\) 。

将递推式展开，容易得到：\(f(m-1)=3^{m-1}-1\) 。

发现如果第 \(X\) 步要取 \(m\) 的话就只有两个位置，分别是 \(X=3^{m-1}\) 和 \(X=2\times 3^{m-1}\) 。

什么时候可以取到 \(m-1\) ？考虑将递推式中的 \(f(m-1)\) 展开一层，容易发现当且仅当 \(3^{m-2}|X\) 且 \(3^{m-1}\nmid X\) 时，答案是 \(m-1\) 。所以可以直接用 \(X\) 不断整除三直到有余数，答案就是合法整除的次数+1。

实际有浮台可以转化成没有浮台，令两段为 L, R, 因为我们操作的序列一定形如 LRLRLRLR ，所以可以根据给定的 \(X\) 对 \(n-1\) 作除法得到的商和余数得到没有浮台模型下的步数。

复杂度 \(O(q*len*30)\)，\(len\) 是大整数长度。

代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

#define go(u) for(int i = head[u], v = e[i].to; i; i=e[i].lst, v=e[i].to)

#define rep(i, a, b) for(int i = a; i <= b; ++i)

#define pb push_back

#define re(x) memset(x, 0, sizeof x)

inline int gi() {

    int x = 0,f = 1;

    char ch = getchar();

    while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar();}

    while(isdigit(ch)) { x = (x << 3) + (x << 1) + ch - 48; ch = getchar();}

    return x * f;

}

template <typename T> inline bool Max(T &a, T b){return a < b ? a = b, 1 : 0;}

template <typename T> inline bool Min(T &a, T b){return a > b ? a = b, 1 : 0;}

const int N = 1e3 + 7;

int n, m, k, q;

char s[N];

struct num {

	int x[N], l;

	num(){memset(x, 0, sizeof x); l = 0;}

	num(int a){x[0] = a, l = 1;}

	void read() {

		scanf("%s", s);

		l = strlen(s);

		for(int i = 0; i < l; ++i) x[i] = s[l - i - 1] - '0';

	}

	pair<num, LL> operator /(LL f) {

		num res;

		LL rest = 0;

		for(int i = l - 1; ~i; --i) {

			rest = rest * 10 + x[i];

			res.x[i] = rest / f;

			if(!res.l && res.x[i])

				res.l = i + 1;

			rest %= f;

		}

		if(!res.l) res.l = 1;

		return make_pair(res, rest);

	}

	num operator +(num rhs) {

		num res;

		for(int i = 0; i < min(rhs.l, l); ++i) res.x[i] = x[i] + rhs.x[i];

		for(int i = min(rhs.l, l); i < max(rhs.l, l); ++i) {

			if(l > i) res.x[i] += x[i];

			if(rhs.l > i) res.x[i] += rhs.x[i];

		}

		res.l = max(rhs.l, l);

		for(int i = 0; i < res.l; ++i) res.x[i + 1] += res.x[i] / 10, res.x[i] %= 10;

		for(; res.x[res.l]; ++res.l) {

			res.x[res.l + 1] += res.x[res.l] / 10;

			res.x[res.l] %= 10;

		}

		return res;

	}

}A, B;

int main() {

	n = gi(), m = gi(), k = gi(), q = gi();

	while(q--) {

		A.read();

		pair<num, LL> f = A / (n - 1);

		B = f.first;

		B = B + B;

		if(f.second == 0);

		else if(f.second < k) B = B + num(1);

		else B = B + num(2);

		int cnt = 1;

		while(1) {

			f = B / 3;

			if(f.second == 0) ++cnt;

			else break;

			B = f.first;

		}

		printf("%d\n", cnt);

	}

	return 0;

}

巴特西

SCOI2019d1t1平台跳跃[高精]

分析

代码

最新文章

热门文章