====== 2020牛客暑期多校训练营（第九场） ====== ===== 比赛情况 ===== ^题号 ^A ^B ^C ^D ^E ^F ^G ^H ^I ^J ^K ^L | ^状态 |O |- |- |- |O |O |- |- |O |- |O |- | //O 在比赛中通过 Ø 赛后通过 ! 尝试了但是失败了 - 没有尝试// **比赛时间** 2020-08-08 12:00-17:00 ===== 题解 ===== ==== A - Groundhog and 2-Power Representation ==== 用栈模拟一下，并且用 $\text{py}$ 水一下高精度


s = input().strip()

stack = []

ans = 0

for ch in s:
	if ch == ')':
		now = 0
		while 1:
			r = stack[-1]
			stack.pop()
			if r == '(':
				break
			if r != '+':
				now += int(r)
		stack.pop()
		stack.append(2**now)

	else:
		stack.append(ch)
for each in stack:
	if each != '+':
		ans += int(each)
print(ans)

\\ ==== F - Groundhog Looking Dowdy ==== 我们考虑把所有衣服放到一起，然后把衣服按照邋遢值排序，然后做一个类似滑动窗口的东西，每次滑动保证窗口内有m天及以上可以穿的衣服，然后用当前的最大值和最小值相减一下更新答案即可。


#include 
using namespace std;
const int N = 1e6+5;
struct Node {
	int val,bel;
}clo[N<<1];
bool cmp(const Node &x,const Node &y) { return x.val < y.val; }
int buk[N],cnt,n,m;
int main()
{
	scanf("%d%d",&n,&m);
	int ki;
	for (int i = 1;i<= n;i++) {
		scanf("%d",&ki);
		for (int j = 1;j<= ki;j++) {
			cnt++;
			scanf("%d",&clo[cnt].val);
			clo[cnt].bel = i;
		}
	}
	sort(clo+1,clo+cnt+1,cmp);
	for (int i = 1;i<= n;i++)buk[i] = 0;
	int tail = 0;
	int ans = 1e9+5;
	int cntbel = 0;
	for (int i = 1;i<= cnt;i++) {
		while (tail+1<=cnt) {
			tail++;
			buk[clo[tail].bel]++;
			if (buk[clo[tail].bel] == 1)cntbel++;
			if (cntbel >= m) {ans = min(ans,clo[tail].val-clo[i].val);break;}
		}
		buk[clo[i].bel]--;
		if (buk[clo[i].bel]==0)cntbel--;
	}
	printf("%d\n",ans);
	return 0;
}

\\ ==== G - Groundhog Chasing Death ==== 求 $\prod_{i=a}^b \prod_{j=c}^d gcd(x^i,y^j)$。只有 $x,y$ 的公共质因子会有贡献，枚举这些质因子，然后枚举 $i$，可以用等差数列求出 $j$ 的贡献。


#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include
#define ALL(x) (x).begin(),(x).end()
#define ll long long
#define db double
#define ull unsigned long long
#define pii_ pair
#define mp_ make_pair
#define pb push_back
#define fi first
#define se second
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define show1(a) cout<<#a<<" = "< t)
		x = fa[x];
	int ans = 0;
	dis1[x] = 0;
	dfs1(x,x);
	dis2[n] = 0;
	dfs2(n,n);
	for (int i = 1;i<= n;i++)
		if (2*dis1[i] <= dis2[i])
			ans = max(ans,((dis2[i]+1)>>1));
	printf("%d\n",ans);
	return 0;
}