2020牛客暑期多校训练营（第九场）
A. Groundhog and 2-Power Representation
题意
一个数可以由2x1+2x2+2x3+.....组成，例如1315=210+28+25+2+1=2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0).
现在给出一个由2的次幂组成的表达式，输出这个数是多少。
题解
不得不说py真的强，看到不到2分钟就有人a了，还以为是原题，赛后发现py三行。（暴风哭泣
我队用的c++高精度模拟写的，队友%%%
代码
py
n = input()
n = n.replace("(","**(")
print(eval(n)) c++
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 3e4+10;
vector<int> mult(vector<int>x,vector<int>y)//高精*高精
{
int xlen=(int)x.size(),ylen=(int)y.size(),zlen=xlen+ylen;
vector<int>z(zlen);
for(register int i=0;i<xlen;i++)
for(register int j=0;j<ylen;j++)
z[i+j]+=x[i]*y[j];
for(register int i=0;i<zlen;i++)
if(z[i]>9)
{
z[i+1]+=z[i]/10;
z[i]%=10;
}
while(zlen>1 && !z.back())
{
z.pop_back();
zlen--;
}
return z;
}
vector<int> chu(int x,vector<int> vv)
{
bool flag=false;
vector<int> ans;
int t=0;
int i;
for (i=vv.size()-1; i>=0; i-- )
{
t=t*10+vv[i];
if(flag)
{
ans.push_back(t/x);
}
else if(t/x>0)
{
flag=true;
ans.push_back(t/x);
}
t=t%x;
}
return vector<int> (ans.rbegin(),ans.rend());
}
vector<int> add(vector<int>x,vector<int>y)//高精+高精
{
int xlen=(int)x.size(),ylen=(int)y.size(),zlen=max(xlen,ylen)+1;
vector<int>z(zlen);
for(register int i=0;i<zlen;i++)
{
if(i<xlen)
z[i]+=x[i];
if(i<ylen)
z[i]+=y[i];
if(z[i]>9)
{
z[i+1]++;
z[i]-=10;
}
}
while(zlen>1 && !z.back())
{
zlen--;
z.pop_back();
}
return z;
}
void prin(vector<int> x)
{
int i;
if(x.size() == 0)
{
printf("0");
}
for (i=x.size()-1;i>=0;i--)
{
printf("%d",x[i]);
}
printf("\n");
}
std::vector<int> qup(std::vector<int> vv)
{
std::vector<int> ans;
ans.pb(1);
std::vector<int> v;
std::vector<int> f;
f.pb(0);
v.pb(2);
while(vv.size() > 0 && *(--vv.end()) != 0)
{
if(vv[0] & 1)
ans = mult(v,ans);
vv = chu(2,vv);
v = mult(v,v);
}
return ans;
}
char a[maxn];
vector<int> dg(int l,int r)
{
vector<int> ans;
if(l == r)
{
ans.pb(a[l] - '0');
return ans;
}
ans.pb(0);
std::vector<int> temp;
for (int i = l; i <= r; i ++ )
{
if(a[i] == '(')
{
int s= 0 ;
for(int j = i + 1; j <= r; j ++ )
{
if(a[j] == '(')
s ++ ;
if(a[j] == ')')
{
if(s == 0)
{
ans = add(ans,qup(dg(i + 1, j - 1)));
i = j;
break;
}
else
s -- ;
}
}
continue;
}
if(a[i] == '+')
{
ans = add(ans,dg(i + 1,r));
break;
}
else
{
if(a[i + 1] != '(')
{
temp.pb(a[i] - '0');
ans = add(ans,temp);
}
continue;
}
}
return ans;
}
int main()
{
scanf("%s",a + 1);
int n = strlen(a + 1);
vector<int> ans = dg(1,n);
prin(ans);
} E. Groundhog Chasing Death
题意
给出a,b,c,d,x,y，求)
modulo 998244353的结果
题解
第一想法肯定是暴力：枚举 i 和 j ，然后算出每一个 gcd(xi , yj)，然后乘起来。但是数据 i 和 j 的数据范围都在1e6，这样肯定会超时，i 和 j 的范围在1e9，这样肯定是要爆long long的。那么就要想想怎么优化。
因为这是一个乘性函数，那么肯定要想到分解质因子，所以先预处理 x 的质因子，并记录每个质因子出现的次数，这样 xi 就可以由每个质因子个数再 *i 得到。枚举 xi 中因子 m 出现的次数，可以发现当 yj 小的时候，gcd(xi , yj) 主要是被 yj 的 m 个数约束，此时是一个等差数列；当 yj 大的时候，就是由 xi 约束，此时 yj 中 m 的个数是一个常数，暴力求解就好了。
由于质因子的幂很大，会爆long long，所以要用欧拉降幂，欧拉降幂是对mod-1取模（队友对mod取模debug好久
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const ll md = 998244352;
vector<pair<ll,ll> > v;
void div(ll n)
{
v.clear();
ll k = sqrt(n);
for (ll i = 2; i <= k; ++ i) {
ll cnt = 0;
while (n % i == 0) {
n /= i;
cnt ++;
}
v.push_back({i, cnt});
}
if (n != 1) {
v.push_back({n, 1});
}
}
ll phi(ll n)
{
ll ans = n;
ll k = sqrt(n);
for (int i = 2; i <= k; ++i) {
if (n % i == 0) {
ans = ans / i * (i - 1);
while (n % i == 0) n /= i;
}
}
if (n > 1) {
ans = ans / n * (n - 1);
}
return ans;
}
ll pow(ll a, ll b, ll p) {
ll res = 1;
while (b) {
if (b & 1) res = (res * a) % p;
a = a * a % p;
b >>= 1;
}
return res%p;
}
int main()
{
ll a, b, c, d, x, y;
scanf("%lld%lld%lld%lld%lld%lld", &a, &b, &c, &d, &x, &y);
a = max(1LL, a);
c = max(1LL, c);
--c;
div(x);
ll ans = 1;
for (int i = 0; i < (int)v.size(); ++ i) {
ll cnt = 0;
while (y % v[i].first == 0) {
y /= v[i].first;
++ cnt;
}
ll sum = 0;
if (cnt == 0) continue;
for (ll j = a; j <= b; ++ j) {
ll e = v[i].second * (ll)j;
ll f = e/cnt;
while (cnt * f < e) {
++ f;
}
if (c >= f) {
sum -= ((f * (f-1) / 2)% md * (cnt % md)) % md;
sum = (sum % md + md) % md;
sum -= (ll)(((c-f+1) % md) * (e % md)) % md;
sum = (sum % md + md) % md;
}
else {
sum -= ((c * (c+1) / 2) % md * (cnt % md)) % md;
sum = (sum % md + md) % md;
}
sum = (sum % md + md) % md;
if (d >= f) {
sum += ((f * (f-1) / 2) % md) * (cnt % md) % md;
sum = (sum % md + md) % md;
sum += (ll)(((d-f+1) % md) * (e % md)) % md;
sum = (sum % md + md) % md;
}
else {
sum += (((d * (d+1) /2) % md) * (cnt) % md) % md;
sum = (sum % md + md) % md;
}
}
sum = (sum % md + md) % md;
ans *= pow(v[i].first, sum, mod);
ans = (ans % mod + mod) % mod;
}
ans = (ans % mod + mod) % mod;
printf("%lld\n", ans);
return 0;
}
F. Groundhog Looking Dowdy
题意
土拨鼠要和苹果约会，第 i 天它的第 j 件衣服的邋遢度为 aij ，它要在n天中选择m天和苹果约会，要求选出的m天衣服的邋遢度的最大值和最小值的差值最小。
题解
因为要最小化最大值和最小值的差值，所以用pair存每件衣服的邋遢度和第几天，然后对邋遢度从小到大排序。那么问题就转换成了求一个区间 [L,R] ，使得这个区间覆盖m个不同的天，并且R的邋遢度-L的邋遢度最小。这个问题就可以用尺取解决了。对于每一个L，求出最小的合法的R，每次更新差值最小值即可。
代码
#include<bits/stdc++.h>
#define st first
#define sd second
#define ll long long
#define pii pair<int,int>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 2e6+10;
pii pp[maxn];
int vis[maxn];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
int cnt = 0;
for (int i = 1; i <= n; i ++ ){
int p;
scanf("%d",&p);
for (int j = 1; j <= p; j ++ ){
int x;
scanf("%d",&x);
pp[++cnt].st = x;
pp[cnt].sd = i;
}
}
sort(pp + 1, pp + 1 + cnt);
int num = 0;
int l = 1, r = 1;
int minn = pp[1].st, maxx = 0;
int ans = inf;
while(1){
while(r <= cnt && num < m){
if(vis[pp[r].sd] == 0) num ++ ;
vis[pp[r].sd] ++ ;
maxx = pp[r].st;
r ++ ;
}
if(num < m)
break;
ans = min(ans, maxx - minn);
vis[pp[l].sd] -- ;
if(vis[pp[l].sd] == 0) num -- ;
minn = pp[l + 1].sd;
l ++ ;
}
printf("%d\n",ans);
} I. The Crime-solving Plan of Groundhog
题意
给出n个数(0<=a[i]<=9)，由这n个数组成2个数，使得这两个数的乘积最小。
题解
自己造几个例子就可以看出，选择0之外最小的数和剩下的数字组成的没有前导0的数相乘结果最小。剩下的数字怎样最小呢，当然是找到最小的非零的数做第一位，后边接上所有的0，再按照有小到大的顺序放剩下的数字。因为n的范围在1e5，所以要用高精度乘法。
推导：
把当前的数字拆成4个数 a, b, c, d (a ≤ b ≤ c ≤ d) ,那么我们有两种决策：两位数×两位数，或者三位数×一
位数。
(10a + d) * (10b + c) = 100ab + 10ac + 10bd + cd (100b+10c+d) * a = 100ab + 10ac +ad<(10a + d) * (10b + c)
同理，可以证明留一个最小的正整数作为第一个数，剩下的所有数字排成最小的数作为第二个数时，答案取到最小值。
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[100100];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n);
int k=0;
while(k<n&&a[k]==0) k++;
vector<int>q;
q.push_back(a[k+1]);
for(int i=0;i<k;i++) q.push_back(0);
for(int i=k+2;i<n;i++) q.push_back(a[i]);
vector<int>ans;
for(int i=q.size()-1;i>=0;i--){
int x=q[i]*a[k];
ans.push_back(x);
}
for(int i=0;i<10;i++) ans.push_back(0);
for(int i=0;i<ans.size();i++){
if(ans[i]>=10){
ans[i+1]+=ans[i]/10;
ans[i]%=10;
}
}
while(!ans.back()) ans.pop_back();
for(int i=ans.size()-1;i>=0;i--) cout<<ans[i];
cout<<endl;
}
return 0;
}
K. The Flee Plan of Groundhog
题意
土拨鼠在第1个宿舍，橙子在第n个宿舍。这n个宿舍间有n-1条路并且长度都为1，土拨鼠从第1个房间去第n个宿舍，速度为1m/s；橙子从第n个宿舍追赶土拨鼠，速度为2m/s。
题解
二分时间 t ，然后判断在 ts 内土拨鼠是否会被橙子追上。以橙子所在的寝室 n 为根建树，从 1 到 n 枚举所有土拨鼠能够到达的点，先找出t秒能走到哪个点，然后再找这个点能走到的离n最远的点，判断在走的过程中会不会被追上。
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
vector<int> vv[maxn];
int vis[maxn];
int f[maxn];
int dep[maxn];
void dfs(int x,int fa,int de)
{
f[x] = fa;
dep[x] = de;
for (int i =0 ; i< vv[x].size(); i ++ )
{
int v = vv[x][i];
if(v == fa)
continue;
dfs(v,x,de + 1);
vis[x] |= vis[v];
}
}
int ans =0 ;
void dfs2(int x,int fa,int de)
{
ans = max(ans,de);
for (int i =0 ; i<vv[x].size(); i ++ )
{
int v = vv[x][i];
if(v == fa)
continue;
dfs2(v,x,de + 1);
}
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for (int i = 1; i < n; i ++ )
{
int x,y;
scanf("%d%d",&x,&y);
vv[x].push_back(y);
vv[y].push_back(x);
}
vis[1] = 1;
dfs(n,0,1);
int k = -1;
int s = dep[1] - m;
for (int i = 1; i <= n; i ++ ){
if(vis[i] && dep[i] == s){
k = i;
break;
}
}
int num = dep[k] - 1;
dfs2(k,f[k],1);
ans -- ;
num += ans;
int r = (num + 1) / 2;
int l = 0;
while(l < r){
int mid = l + r>> 1;
int x = min(2 * mid,num);
int y = min(mid, ans);
if(x - dep[k] + 1>= y) r = mid;
else l = mid + 1;
}
printf("%d\n",l);
} 
