2020牛客暑期多校训练营（第九场）

比赛链接

A Groundhog and 2-Power Representation

讨厌的模拟，递归+高精度。

然而 $\text{python}$ 表示一行解决问题。。。

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

struct BigNum{
	vector<int> a; // a[n-1]...a[1]a[0]
	int neg;

	BigNum(){ a.clear(); neg = 1; }
	explicit BigNum(const string &s){
		a.clear();
		int len = s.length();
		for(int i = 0; i < len; i++)
			a.pb(s[len-i-1] - '0');
	}
	explicit BigNum(LL num){
		a.clear();
		do{
			a.pb(num % 10);
			num /= 10;
		}while(num);
	}

	BigNum operator = (const string &s){ return *this = BigNum(s); }
	BigNum operator = (LL num){ return *this = BigNum(num); }

	bool operator < (const BigNum &b) const{
		if(a.size() != b.a.size())	return a.size() < b.a.size();
		for(int i = a.size() - 1; i >= 0; i--)
			if(a[i] != b.a[i])
				return a[i] < b.a[i];
		return false;
	}
	bool operator > (const BigNum &b) const{ return b < *this; }
	bool operator <= (const BigNum &b) const{ return !(*this > b); }
	bool operator >= (const BigNum &b) const{ return !(*this < b); }
	bool operator != (const BigNum &b) const{ return (*this > b) || (*this < b); }
	bool operator == (const BigNum &b) const{ return !(*this < b) && !(*this > b); }

	BigNum operator + (const BigNum &b) const{
		BigNum C;
		int x = 0;
		for(int i = 0, g = 0; ; i++){
			if(g == 0 && i >= a.size() && i >= b.a.size())	break;
			x = g;
			if(i < a.size())	x += a[i];
			if(i < b.a.size())	x += b.a[i];
			C.a.pb(x % 10);
			g = x / 10;
		}
		return C;
	}
	BigNum operator - (const BigNum &b) const{
		BigNum C;
		BigNum A = *this;
		BigNum B = b;
		if(A < B)	C.neg = -1, swap(A, B);
		C.a.resize(A.a.size());
		for(int i = 0; ; i++){
			if(i >= A.a.size() && i >= B.a.size())	break;
			if(i >= B.a.size())	C.a[i] = A.a[i];
			else	C.a[i] = A.a[i] - B.a[i];
		}
		for(int i = 0; ; i++){
			if(i >= C.a.size())	break;
			if(C.a[i] < 0){
				C.a[i] += 10;
				C.a[i+1]--;
			}
		}
		while(C.a.size() > 1 && C.a.back() == 0)	C.a.pop_back();
		return C;
	}
	BigNum operator * (const BigNum &b) const{
		BigNum C;
		C.a.resize(a.size() + b.a.size());
		for(int i = 0; i < a.size(); i++){
			int g = 0;
			for(int j = 0; j < b.a.size(); j++){
				C.a[i+j] += a[i] * b.a[j] + g;
				g = C.a[i+j] / 10;
				C.a[i+j] %= 10;
			}
			C.a[i+b.a.size()] = g;
		}
		while(C.a.size() > 1 && C.a.back() == 0)	C.a.pop_back();
		return C;
	}
	BigNum operator / (const LL &b) const{
		BigNum C;
		C = *this;
		for(int i = C.a.size() - 1; i >= 0; i--){
			if(i)	C.a[i-1] += C.a[i] % b * 10;
			C.a[i] /= b;
		}
		while(C.a.size() > 1 && C.a.back() == 0)
			C.a.pop_back();
		return C;
	}
	BigNum operator / (const BigNum &b) const{
		BigNum L, R, ans, t;
		L = 0ll;
		R = *this;
		ans = 0ll;
		t = 1ll;
		while(L <= R){
			BigNum mid = (L + R) / 2;
			if((mid * b) > (*this))
				R = mid - t;
			else
				L = mid + t, ans = mid;
		}
		return ans;
	}
	BigNum operator % (const LL &b) const{
		BigNum B; B = b;
		return (*this) - (*this) / b * B;
	}
	BigNum operator % (const BigNum &b) const{
		return (*this) - (*this) / b * b;
	}
	BigNum operator += (const BigNum &b){ *this = *this + b; return *this; }
	BigNum operator -= (const BigNum &b){ *this = *this - b; return *this; }
	BigNum operator *= (const BigNum &b){ *this = *this * b; return *this; }
	BigNum operator /= (const LL &b){ *this = *this / b; return *this; }
	BigNum operator /= (const BigNum &b){ *this = *this / b; return *this; }

};

ostream& operator << (ostream &out, const BigNum &b){
	string res;
	if(b.neg == -1)	res += '-';
	for(int i = b.a.size() - 1; i >= 0; i--)
		res += b.a[i] + '0';
	return out << res;
}
istream& operator >> (istream &in, BigNum &b){
	string str;
	if(in >> str)   b = str;
	return in;
}

const int N = 30005;

int ans[N], p[N];
char s[N], t[N];

LL get(int l, int r){
	if(l == r)	return s[l] - '0';
	LL res = 0;
	for(int i = l; i <= r; i++){
		if(s[i] == '('){
			res += pow(2, get(i+1, p[i]-1));
			i = p[i];
		}
	}
	return res;
}

int main(){
	scanf("%s", t+1);
	int tlen = strlen(t+1);
	int len = 0;
	for(int i = 1; i <= tlen; i++){
		if(t[i] == '2' && t[i+1] != '(')
			s[++len] = '2', s[++len] = '(', s[++len] = '1', s[++len] = ')';
		else	s[++len] = t[i];
	}
	stack<int> stk;
	for(int i = 1; i <= len; i++){
		if(s[i] == '(')	stk.push(i);
		else if(s[i] == ')')	p[stk.top()] = i, stk.pop();
	}
	for(int i = 1; i <= len; i++){
		if(s[i] == '('){
			ans[get(i+1, p[i]-1)]++;
			i = p[i];
		}
	}
	BigNum res(0);
	BigNum base(1);
	for(int i = 0; i <= 600; i++, base = base * BigNum(2))
		res = res + BigNum(ans[i]) * base;
	cout << res << endl;
	return 0;
}

print(eval(input().replace('(', '**(')))

---

E Groundhog Chasing Death

把 $x,y$ 分解质因数，考虑每一个质因子对答案的贡献。

设枚举的质因子为 $p$，$x$ 中含有 $\alpha$ 个 $p$，$y$ 中含有 $\beta$ 个 $p$，那么 $p$ 对答案的贡献是 $p$ 的 $\sum\limits_{i=a}^b\sum\limits_{j=c}^d\min(i\alpha,j\beta)$ 次方。枚举 $i\alpha$ 和 $j\beta$ 作为最小值，可以 $O(1)$ 地计算贡献，记得不要重复计算 $i\alpha=j\beta$ 的情况。

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const LL MOD = 998244353;

LL a, b, c, d, x, y;
map<int, int> xx, yy;

inline LL fpow(LL bs, LL idx){
	bs %= MOD;
	LL res = 1;
	while(idx){
		if(idx & 1)	(res *= bs) %= MOD;
		(bs *= bs) %= MOD;
		idx >>= 1;
	}
	return res;
}

int main(){
	read(a, b, c, d, x, y);
	vector<int> factors;
	for(int i = 2; i * i <= x; i++){
		if(x % i == 0)	factors.pb(i);
		while(x % i == 0)	x /= i, xx[i]++;
	} if(x > 1) factors.pb(x), xx[x]++;
	for(int i = 2; i * i <= y; i++){
		if(y % i == 0)	factors.pb(i);
		while(y % i == 0)	y /= i, yy[i]++;
	} if(y > 1) factors.pb(y), yy[y]++;
	sort(factors.begin(), factors.end());
	factors.erase(unique(factors.begin(), factors.end()), factors.end());
	LL ans = 1;
	for(auto &p : factors){
		LL res = 0;
		LL alpha = xx[p], beta = yy[p];
		if(alpha == 0 || beta == 0)	continue;
		for(LL i = a; i <= b; i++){
			LL j = i * alpha / beta; while(j * beta < i * alpha) j++; j = max(j, c);
			if(d - j + 1 > 0)	(res += (d - j + 1) * alpha % (MOD - 1) * i) %= (MOD - 1);
		}
		for(LL j = c; j <= d; j++){
			LL i = j * beta / alpha + 1; i = max(i, a);
			if(b - i + 1 > 0)	(res += (b - i + 1) * beta % (MOD - 1) * j) %= (MOD - 1);
		}
		(ans *= fpow(p, res)) %= MOD;
	}
	printf("%lld\n", ans);
	return 0;
}

---

F Groundhog Looking Dowdy

把所有衣服拿出来按 dowdiness 排序，因为求的是最小极差，所以选取衣服是连续的一段，因此尺取即可。

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 2000005;

int n, m, cnt[N], k, tot;

struct Node{
	int val, day;
	bool operator < (const Node &A) const{
		return val < A.val;
	}
}a[N];

int main(){
	read(n, m);
	for(int i = 1; i <= n; i++){
		int ki; for(read(ki); ki; ki--){
			int val; read(val); a[++tot] = (Node){val, i};
		}
	}
	sort(a+1, a+tot+1);
	int ans = 1e9;
	for(int l = 1, r = 0; l <= tot; l++){
		while(r < tot && k < m){
			r++;
			if(cnt[a[r].day] == 0)	k++;
			cnt[a[r].day]++;
			if(k >= m)	ans = min(ans, a[r].val - a[l].val);
		}
		cnt[a[l].day]--;
		if(cnt[a[l].day] == 0)	k--;
		if(k >= m)	ans = min(ans, a[r].val - a[l].val);
	}
	printf("%d\n", ans);
	return 0;
}

---

G Groundhog Playing Scissors

思路明明和题解一模一样，结果比赛的时候总是 WA。

旋转多边形换成旋转直线，那么直线其实是一个圆的所有切线。设圆与多边形相交于两点，可以想象，在一定范围内这两点始终在特定的两条边上移动——这些范围就是用所有多边形的顶点做圆的切线之后划分出来的范围。每一个范围内，切出来的线段长度是下凸的，三分找到最小值，然后左右两边二分找距离等于 $L$ 的角度，即可得到这个范围内哪些角度满足线段长度 $\leqslant L$。如何得到两个交点移动的特定两条边呢？注意直线再旋转的过程中，这两条边也在逆时针旋转，所以两个指针移动即可；判定是否需要更换边用范围正中的那条线判断。

然而现在只过了 $75\%$ 的数据。。。

---

I The Crime-solving Plan of Groundhog

可以证明，答案就是取最小的正整数，乘上其他数从小到大排列起来（当然第一个数不能是 $0$）。

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 400005;

int T, n, a[N];
int ans[N];

int main(){
	for(read(T); T; T--){
		read(n);
		vector<int> b(10);
		for(int i = 1; i <= n; i++){
			read(a[i]);
			b[a[i]]++;
		}
		int now = 0;
		for(int i = 1; i <= n; i++){
			while(!b[now])	now++;
			a[i] = now, b[now]--;
		}

		int pos = 0;
		for(pos = 2; pos <= n; pos++)
			if(a[pos] != 0 && a[pos-1] != 0)
				break;
		a[1] = a[pos-1], a[2] = a[pos];
		for(int i = 3; i <= pos; i++)	a[i] = 0;

		for(int i = 2; i <= n; i++)	ans[i-1] = a[i];
		int x = 0;
		for(int i = n-1; i >= 1; i--){
			ans[i] = ans[i] * a[1] + x;
			x = ans[i] / 10;
			ans[i] %= 10;
		}
		ans[0] = x;
		pos = 0;
		while(!ans[pos])	pos++;
		for(int i = pos; i <= n-1; i++)	printf("%d", ans[i]);
		puts("");
	}
	return 0;
}

---

J The Escape Plan of Groundhog

这种题都是枚举上下边界，然后枚举右边界，统计合法左边界数目。

这道题也是这样，我们把 $0$ 换成 $-1$，做二维前缀和（那么和数就代表了桌子比空位多了多少）。在我们扫右边界的过程中，如果这一列全是 $1$，也就是说它可以作为右边界，那么把它的前缀和和加到桶里，而它作为右边界对答案的贡献可以在这之前在桶里面查询。当然注意，合法矩形的上下边界必须是连续的 $1$，所以一旦不满足该条件就把桶清空。

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 1005;

int n, m, a[N][N], sum[N][N];
int buc[N*N];
vi v;
LL ans;

inline int get(int u, int d, int l, int r){
	if(u > d || l > r)	return 0;
	return sum[d][r] - sum[u-1][r] - sum[d][l-1] + sum[u-1][l-1];
}

int main(){
	read(n, m);
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			read(a[i][j]);
			if(a[i][j] == 0)	a[i][j] = -1;
			sum[i][j] = a[i][j] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
		}
	}
	for(int u = 1; u <= n; u++){
		for(int d = u + 1; d <= n; d++){
			for(auto &k : v)	buc[k] = 0;
			v.clear();
			for(int p = 1; p <= m; p++){
				if(a[u][p] == -1 || a[d][p] == -1){
					for(auto &k : v)	buc[k] = 0;
					v.clear();
				}
				else if(get(u, d, p, p) == d - u + 1){
					int s = get(u+1, d-1, 1, p-1);
					ans += buc[s-1+500000] + buc[s+500000] + buc[s+1+500000];
					buc[get(u+1, d-1, 1, p)+500000]++;
					v.pb(get(u+1, d-1, 1, p)+500000);
				}
			}
		}
	}
	printf("%lld\n", ans);
	return 0;
}

---

K The Flee Plan of Groundhog

以 $n$ 为根，我们很容易得到 Groundhog 在 $t$ 时刻的位置，接下来他有两种走法，要么直接往现在的子树里找最深的一条路跑，要么往上走一些边，再往子树里最深的一条路跑，枚举往上走的边数，每次 $O(1)$ 计算即可。

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 100005;

int n, t;
vi edge[N];

int fa[N], dep[N], mxlen[N];
void dfs(int x, int f, int depth){
	fa[x] = f, dep[x] = depth, mxlen[x] = 0;
	for(auto &to : edge[x]){
		if(to == f)	continue;
		dfs(to, x, depth+1);
		mxlen[x] = max(mxlen[x], mxlen[to] + 1);
	}
}

inline int calc(int x, int dis){
	if(mxlen[x] >= dis)	return dis;
	else	return (dis - mxlen[x] + 1) / 2 + mxlen[x];
}

int main(){
	read(n, t);
	for(int i = 1; i < n; i++){
		int u, v; read(u, v);
		edge[u].pb(v), edge[v].pb(u);
	}
	dfs(n, 0, 0);
	int now = 1;
	while(now != n && t--)	now = fa[now];
	int pos = now;
	int ans = (dep[pos] + 1) / 2;
	for(int d = 0; now; now = fa[now], d++){
		if(dep[pos] <= d * 3)	break;
		ans = max(ans, calc(now, dep[pos] - d * 3));
	}
	printf("%d\n", ans);
	return 0;
}