2020牛客暑期多校训练营（第九场）
A. Groundhog and 2-Power Representation
题意：给一个正则表达式，求正则表达式的值。
例子：
2(0)=2^0
2(2+2(0))=2^(2+2^0)
分析：队友写的py.
a = input()
a = a.replace('(', '**(')
print(eval(a))B. Groundhog and Apple Tree
题意：给定有n个节点一颗无根树，每个节点有点权,每条边有边权
.从起点1出发遍历所有点，并且保证每条边最多遍历1次，每次遍历一条边，体力减去该边权大小，遍历点时体力获得点权值，如果要保证行进时候当前体力不小于0，那么从1开始初始值最小是多少。
分析：贪心+树形dp。
维护每颗子树两个信息。
遍历以x为根节点的子树的所有节点，初始值最小是多少。
遍历以x为根节点的子树的所有节点，体力增加值。
显然dp方程的转移跟路径决策有关。那么当前行进x节点，如何决策选择那个子节点继续行进。
采用贪心策略：
对于的子节点(肯定是先遍历它们)，我们显然是先遍历体力增加值大的子节点，如果体力增加值相同那么先遍历所需要的体力初始值小的子节点。
对于
的节点，我们可以列一个方程：
对于x的两个子节点.
先
后，那么对于要
那我们按照为关键字进行从小到大排序，然后遍历选择即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
vector<pair<int,int>> g[maxn];
ll dp[maxn],siz[maxn];
int a[maxn];
void dfs( int x,int f )
{
dp[x]=0;
siz[x]=a[x];
vector< pair<ll,ll> > p1,p2;
for( pair<int,int> i:g[x] )
{
int v=i.first,w=i.second;
if( v==f ) continue;
dfs(v,x);
siz[v]-=2*w;
dp[v]=min(dp[v]-w,siz[v]);
if( siz[v]>=0 ) p1.push_back( make_pair( dp[v],siz[v] ) );
else p2.push_back( make_pair( dp[v],siz[v] ) );
}
sort(p1.begin(),p1.end(),[&]( pair<int,int> x,pair<int,int> y) {
return x.first>y.first || x.first==y.first && x.second>y.second;
});
sort(p2.begin(),p2.end(),[&]( pair<int,int> x,pair<int,int> y) {
return x.first+y.second<y.first+x.second;
});
for( pair<ll,ll> v: p1 )
{
dp[x]=min(dp[x],siz[x]+v.first);
siz[x]+=v.second;
}
for( pair<ll,ll> v:p2 )
{
dp[x]=min(dp[x],siz[x]+v.first);
siz[x]+=v.second;
}
}
int main()
{
int t;
scanf("%d",&t);
while( t-- )
{
int n;
scanf("%d",&n);
for( int i=1;i<=n;i++ ) scanf("%d",&a[i]),g[i].clear();
for( int i=1;i<n;i++ )
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
g[u].push_back( make_pair(v,w) );
g[v].push_back( make_pair(u,w) );
}
dfs(1,0);
printf("%lld\n",-dp[1]);
}
}
E.Groundhog Chasing Death
题意：求
分析：利用唯一分解定理将 分解成若干个质因子次方的乘积。那么式子只用记录两个共有质因子次方的gcd值。
根据数据范围，我们可以枚举 进行计算，首先我们预处理出两个树共有的质因子，然后问题就转化成了求每一个共有质因子的
,
表示
对应质因子的次方数，
表示
对应质因子的次方数。
然后细致讨论一下大小就可以过了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e6+10;
const ll mod=998244353;
const ll modd=998244352;
inline ll read()
{
ll x=0;char s=getchar();
for( ;isdigit(s);x=x*10+s-48,s=getchar());
return x;
}
void print( ll x )
{
if( x<0 ) x=-x,putchar('-');
if( x>9 ) print(x/10);
putchar( x%10+'0' );
}
ll prime[5000000];//保存素数
ll vis[maxn];//初始化
ll cnt;
void getprime( ll n )
{
cnt=0;
memset(vis,0,sizeof(vis));
for( ll i=2;i<n;i++ )
{
if( vis[i]==0 ) prime[cnt++]=i;
for( int j=0;j<cnt && i*prime[j]<n;j++ )
{
vis[i*prime[j]]=1;
// vis[i*prime[j]]=prime[j];
if( i%prime[j]==0 ) break;
}
}
}
vector<pair<ll,ll>> p1,p2;
ll cnt1,cnt2;
void solve( ll n ,vector<pair<ll,ll>> &p )
{
for( ll i=0; prime[i]<=n && i<cnt;i++ )
{
if( n%prime[i]==0 )
{
int tmp=0;
while( n%prime[i]==0 )
{
tmp++;
n/=prime[i];
}
p.push_back( make_pair(prime[i],tmp) );
if( n==1 ) break;
}
}
if( n>1 ) p.push_back( make_pair(n,1) );
}
ll poww( ll a,ll b ) // 快速幂
{
ll ans = 1;
while(b){
if(b&1)
ans=(ans*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return ans%mod;
}
vector< pair<ll,ll> > ans;
vector< pair<ll,ll> > id;
void get_ans( ll now,ll l,ll r )
{
for( int i=0;i<ans.size();i++ )
{
ll lef=p1[id[i].first].second,rig=p2[id[i].second].second;
//lef*=now;rig*=l;
ll mins=min(lef*now,rig*l);
if( mins==lef*now ) ans[i].second=(ans[i].second+(r-l+1)*mins)%modd;
else
{
if( rig*r<=lef*now )
{
ll all=(rig*l+rig*r)*(r-l+1)/2;
ans[i].second=(ans[i].second+all)%modd;
}
else
{
ll k=lef*now/rig;
ll all1=( l+k )*(k-l+1)/2;
all1=all1*rig%modd;
ll all2=(r-k)*lef*now;
ans[i].second=(ans[i].second+all1+all2)%modd;
}
}
}
}
int main()
{
// int sum=0,er=0;
// for( int i=1;i<=10;i++ )
// {
// er+=i-1;
// cout<<er+i*(10-i+1)<<endl;
// }
// cout<<sum<<endl;
getprime(1e6);
ll a=read(),b=read(),c=read(),d=read(),x=read(),y=read();
solve(x,p1);
solve(y,p2);
cnt1=p1.size(),cnt2=p2.size();
for( ll i=0;i<cnt1;i++ )
{
for( ll j=0;j<cnt2;j++ )
{
if( p1[i].first==p2[j].first )
{
ans.push_back( make_pair(p1[i].first,0) );
id.push_back( make_pair(i,j) );
}
}
}
for( ll i=a;i<=b;i++ )
{
get_ans(i,c,d);
}
ll res=1;
for( ll i=0;i<ans.size();i++ )
{
// pair<int,ll> tmp=ans[i];
res=(res*poww(ans[i].first,ans[i].second))%mod;
}
print(res);
}F.Groundhog Looking Dowdy
题意：n天每天有 衣服，每件衣服有个魅力值，你要从中选m件衣服，每件衣服必须是不同天的，求选择方案中衣服的最大美丽值和最小美丽值的差异最小是多少。
分析：将所有衣服按所属天数编号，然后根据每件衣服的美丽值从小到大排序。二分选择方案的差异值，然后用移动指针维护滑窗进行判断。
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+10;
vector<pair<int,int>> p;
int n,m;
int vis[maxn];
inline int read()
{
int x=0;char s=getchar();
for( ;isdigit(s);x=x*10+s-48,s=getchar());
return x;
}
bool check( int x )
{
int l=0;
int num=0;
for( int i=1;i<=n;i++ ) vis[i]=0;
for( int i=0;i<p.size();i++ )
{
// pair<int,int> tmp=p[i],tmp1=p[l];
if( p[i].first<=x+p[l].first )
{
vis[p[i].second]++;
if( vis[p[i].second]==1 ) num++;
if( num>=m ) return true;
}
else
{
while( p[i].first>x+p[l].first )
{
vis[p[l].second]--;
if( vis[p[l].second]==0 ) num--;
l++;
}
vis[p[i].second]++;
if( vis[p[i].second]==1 ) num++;
if( num>=m ) return true;
}
}
return false;
}
int main()
{
n=read(),m=read();
for( int i=1;i<=n;i++ )
{
int num=read();
int x;
for( int j=0;j<num;j++ )
{
x=read();
//g[i].push_back(x);
p.push_back( make_pair(x,i) );
}
}
sort(p.begin(),p.end());
p.erase( unique(p.begin(),p.end()),p.end());
int l=0,r=1e9,ans;
while( l<=r )
{
int mid=l+r>>1;
if( check(mid) )
{
ans=mid;
r=mid-1;
}
else l=mid+1;
}
printf("%d\n",ans);
}I.The Crime-solving Plan of Groundhog
题意：给定n个0-9的数，将它们组合成两个非前导零的正整数，求他们乘积最小的组合答案。输出乘积。
分析：将n个数从小到大排序。组合最优方案：一个是1位数，一个是n-1位数。1位数肯定选最小的非零数。n-1位数的最高位一定是次小非零数,其他位从小到大选取。
#include<bits/stdc++.h>
using namespace std;
// base and base_digits must be consistent
constexpr int base = 1000000000;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
constexpr int base_digits = 9;
struct bigint
{
// value == 0 is represented by empty z
vector<int> z; // digits
// sign == 1 <==> value >= 0
// sign == -1 <==> value < 0
int sign;
bigint() : sign(1) {}
bigint(long long v) { *this = v; }
bigint& operator=(long long v)
{
sign = v < 0 ? -1 : 1;
v *= sign;
z.clear();
for (; v > 0; v = v / base)
z.push_back((int)(v % base));
return *this;
}
bigint(const string& s) { read(s); }
bigint& operator+=(const bigint& other)
{
if (sign == other.sign)
{
for (int i = 0, carry = 0; i < other.z.size() || carry; ++i)
{
if (i == z.size())
z.push_back(0);
z[i] += carry + (i < other.z.size() ? other.z[i] : 0);
carry = z[i] >= base;
if (carry)
z[i] -= base;
}
}
else if (other != 0 /* prevent infinite loop */)
{
*this -= -other;
}
return *this;
}
friend bigint operator+(bigint a, const bigint& b)
{
return a += b;
}
bigint& operator-=(const bigint& other)
{
if (sign == other.sign)
{
if (sign == 1 && *this >= other || sign == -1 && *this <= other)
{
for (int i = 0, carry = 0; i < other.z.size() || carry; ++i)
{
z[i] -= carry + (i < other.z.size() ? other.z[i] : 0);
carry = z[i] < 0;
if (carry)
z[i] += base;
}
trim();
}
else
{
*this = other - *this;
this->sign = -this->sign;
}
}
else
{
*this += -other;
}
return *this;
}
friend bigint operator-(bigint a, const bigint& b)
{
return a -= b;
}
bigint& operator*=(int v)
{
if (v < 0)
sign = -sign, v = -v;
for (int i = 0, carry = 0; i < z.size() || carry; ++i)
{
if (i == z.size())
z.push_back(0);
long long cur = (long long)z[i] * v + carry;
carry = (int)(cur / base);
z[i] = (int)(cur % base);
}
trim();
return *this;
}
bigint operator*(int v) const
{
return bigint(*this) *= v;
}
friend pair<bigint, bigint> divmod(const bigint& a1, const bigint& b1)
{
int norm = base / (b1.z.back() + 1);
bigint a = a1.abs() * norm;
bigint b = b1.abs() * norm;
bigint q, r;
q.z.resize(a.z.size());
for (int i = (int)a.z.size() - 1; i >= 0; i--)
{
r *= base;
r += a.z[i];
int s1 = b.z.size() < r.z.size() ? r.z[b.z.size()] : 0;
int s2 = b.z.size() - 1 < r.z.size() ? r.z[b.z.size() - 1] : 0;
int d = (int)(((long long)s1 * base + s2) / b.z.back());
r -= b * d;
while (r < 0)
r += b, --d;
q.z[i] = d;
}
q.sign = a1.sign * b1.sign;
r.sign = a1.sign;
q.trim();
r.trim();
return {q, r / norm};
}
friend bigint sqrt(const bigint& a1)
{
bigint a = a1;
while (a.z.empty() || a.z.size() % 2 == 1)
a.z.push_back(0);
int n = a.z.size();
int firstDigit = (int)::sqrt((double)a.z[n - 1] * base + a.z[n - 2]);
int norm = base / (firstDigit + 1);
a *= norm;
a *= norm;
while (a.z.empty() || a.z.size() % 2 == 1)
a.z.push_back(0);
bigint r = (long long)a.z[n - 1] * base + a.z[n - 2];
firstDigit = (int)::sqrt((double)a.z[n - 1] * base + a.z[n - 2]);
int q = firstDigit;
bigint res;
for (int j = n / 2 - 1; j >= 0; j--)
{
for (;; --q)
{
bigint r1 = (r - (res * 2 * base + q) * q) * base * base + (j > 0 ? (long long)a.z[2 * j - 1] * base + a.z[2 * j - 2] : 0);
if (r1 >= 0)
{
r = r1;
break;
}
}
res *= base;
res += q;
if (j > 0)
{
int d1 = res.z.size() + 2 < r.z.size() ? r.z[res.z.size() + 2] : 0;
int d2 = res.z.size() + 1 < r.z.size() ? r.z[res.z.size() + 1] : 0;
int d3 = res.z.size() < r.z.size() ? r.z[res.z.size()] : 0;
q = (int)(((long long)d1 * base * base + (long long)d2 * base + d3) / (firstDigit * 2));
}
}
res.trim();
return res / norm;
}
bigint operator/(const bigint& v) const
{
return divmod(*this, v).first;
}
bigint operator%(const bigint& v) const
{
return divmod(*this, v).second;
}
bigint& operator/=(int v)
{
if (v < 0)
sign = -sign, v = -v;
for (int i = (int)z.size() - 1, rem = 0; i >= 0; --i)
{
long long cur = z[i] + rem * (long long)base;
z[i] = (int)(cur / v);
rem = (int)(cur % v);
}
trim();
return *this;
}
bigint operator/(int v) const
{
return bigint(*this) /= v;
}
int operator%(int v) const
{
if (v < 0)
v = -v;
int m = 0;
for (int i = (int)z.size() - 1; i >= 0; --i)
m = (int)((z[i] + m * (long long)base) % v);
return m * sign;
}
bigint& operator*=(const bigint& v)
{
*this = *this * v;
return *this;
}
bigint& operator/=(const bigint& v)
{
*this = *this / v;
return *this;
}
bool operator<(const bigint& v) const
{
if (sign != v.sign)
return sign < v.sign;
if (z.size() != v.z.size())
return z.size() * sign < v.z.size() * v.sign;
for (int i = (int)z.size() - 1; i >= 0; i--)
if (z[i] != v.z[i])
return z[i] * sign < v.z[i] * sign;
return false;
}
bool operator>(const bigint& v) const
{
return v < *this;
}
bool operator<=(const bigint& v) const
{
return !(v < *this);
}
bool operator>=(const bigint& v) const
{
return !(*this < v);
}
bool operator==(const bigint& v) const
{
return !(*this < v) && !(v < *this);
}
bool operator!=(const bigint& v) const
{
return *this < v || v < *this;
}
void trim()
{
while (!z.empty() && z.back() == 0)
z.pop_back();
if (z.empty())
sign = 1;
}
bool isZero() const
{
return z.empty();
}
friend bigint operator-(bigint v)
{
if (!v.z.empty())
v.sign = -v.sign;
return v;
}
bigint abs() const
{
return sign == 1 ? *this : -*this;
}
long long longValue() const
{
long long res = 0;
for (int i = (int)z.size() - 1; i >= 0; i--)
res = res * base + z[i];
return res * sign;
}
friend bigint gcd(const bigint& a, const bigint& b)
{
return b.isZero() ? a : gcd(b, a % b);
}
friend bigint lcm(const bigint& a, const bigint& b)
{
return a / gcd(a, b) * b;
}
void read(const string& s)
{
sign = 1;
z.clear();
int pos = 0;
while (pos < s.size() && (s[pos] == '-' || s[pos] == '+'))
{
if (s[pos] == '-')
sign = -sign;
++pos;
}
for (int i = (int)s.size() - 1; i >= pos; i -= base_digits)
{
int x = 0;
for (int j = max(pos, i - base_digits + 1); j <= i; j++)
x = x * 10 + s[j] - '0';
z.push_back(x);
}
trim();
}
friend istream& operator>>(istream& stream, bigint& v)
{
string s;
stream >> s;
v.read(s);
return stream;
}
friend ostream& operator<<(ostream& stream, const bigint& v)
{
if (v.sign == -1)
stream << '-';
stream << (v.z.empty() ? 0 : v.z.back());
for (int i = (int)v.z.size() - 2; i >= 0; --i)
stream << setw(base_digits) << setfill('0') << v.z[i];
return stream;
}
static vector<int> convert_base(const vector<int>& a, int old_digits, int new_digits)
{
vector<long long> p(max(old_digits, new_digits) + 1);
p[0] = 1;
for (int i = 1; i < p.size(); i++)
p[i] = p[i - 1] * 10;
vector<int> res;
long long cur = 0;
int cur_digits = 0;
for (int v : a)
{
cur += v * p[cur_digits];
cur_digits += old_digits;
while (cur_digits >= new_digits)
{
res.push_back(int(cur % p[new_digits]));
cur /= p[new_digits];
cur_digits -= new_digits;
}
}
res.push_back((int)cur);
while (!res.empty() && res.back() == 0)
res.pop_back();
return res;
}
typedef vector<long long> vll;
static vll karatsubaMultiply(const vll& a, const vll& b)
{
int n = a.size();
vll res(n + n);
if (n <= 32)
{
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
res[i + j] += a[i] * b[j];
return res;
}
int k = n >> 1;
vll a1(a.begin(), a.begin() + k);
vll a2(a.begin() + k, a.end());
vll b1(b.begin(), b.begin() + k);
vll b2(b.begin() + k, b.end());
vll a1b1 = karatsubaMultiply(a1, b1);
vll a2b2 = karatsubaMultiply(a2, b2);
for (int i = 0; i < k; i++)
a2[i] += a1[i];
for (int i = 0; i < k; i++)
b2[i] += b1[i];
vll r = karatsubaMultiply(a2, b2);
for (int i = 0; i < a1b1.size(); i++)
r[i] -= a1b1[i];
for (int i = 0; i < a2b2.size(); i++)
r[i] -= a2b2[i];
for (int i = 0; i < r.size(); i++)
res[i + k] += r[i];
for (int i = 0; i < a1b1.size(); i++)
res[i] += a1b1[i];
for (int i = 0; i < a2b2.size(); i++)
res[i + n] += a2b2[i];
return res;
}
bigint operator*(const bigint& v) const
{
vector<int> a6 = convert_base(this->z, base_digits, 6);
vector<int> b6 = convert_base(v.z, base_digits, 6);
vll a(a6.begin(), a6.end());
vll b(b6.begin(), b6.end());
while (a.size() < b.size())
a.push_back(0);
while (b.size() < a.size())
b.push_back(0);
while (a.size() & (a.size() - 1))
a.push_back(0), b.push_back(0);
vll c = karatsubaMultiply(a, b);
bigint res;
res.sign = sign * v.sign;
for (int i = 0, carry = 0; i < c.size(); i++)
{
long long cur = c[i] + carry;
res.z.push_back((int)(cur % 1000000));
carry = (int)(cur / 1000000);
}
res.z = convert_base(res.z, 6, base_digits);
res.trim();
return res;
}
};
char s[100000];
int a[100005];
int main()
{
IOS
int t;
scanf("%d",&t);
while( t-- )
{
int n;
scanf("%d",&n);
for( int i=1;i<=n;i++ ) scanf("%d",&a[i]);
sort(a+1,a+1+n);
bigint c=0,d=0;
int pos=-1;
for( int i=1;i<=n;i++ )
{
if( a[i]!=0 )
{
c=a[i],pos=i;
break;
}
}
string s;
s=(char)(a[pos+1]+'0');
d=a[pos+1];
for( int i=1;i<=n;i++ )
{
if( i==pos || i==pos+1 ) continue;
char c=a[i]+'0';
s+=c;
}
d.read(s);
// cout<<c<<" "<<d<<endl;
bigint ans=c*d;
cout<<ans<<"\n";
}
}
K.The Flee Plan of Groundhog
题意：给定一颗n个节点的无向树，土拨鼠在节点1的位置，橘子在节点n的位置，前t面土拨鼠往节点n移动，t秒之后土拨鼠开始逃跑，橘子开始追击土拨鼠，土拨鼠的速度是每秒走一条边，橘子的速度是每秒走两条边，求土拨鼠最远能逃多久。输出逃跑时间。
分析：我们以节点n为树根建树。
首先判断t秒内是否到了节点n，如果已经到了输出0，否则土拨鼠的初始位置是pos.
对于土拨鼠而言，肯定要尽可能跑最长链，两种走法，一种是一直远离树根跑下去，一种是先往树根跑一段距离，然后从某个节点开始往最长的叶子节点方向跑。我们将这些方案都枚举然后取个max。
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int n,m,t;
inline int read()
{
int x=0;char s=getchar();
for( ;isdigit(s);x=x*10+s-48,s=getchar());
return x;
}
int fa[maxn],siz[maxn],d[maxn];
vector<int> g[maxn];
void dfs( int x,int f )
{
fa[x]=f;
siz[x]=0;
d[x]=d[f]+1;
for( int v:g[x] )
{
if( v==f ) continue;
dfs(v,x);
siz[x]=max(siz[v]+1,siz[x]);
}
}
int ans;
void solve( int now,int c )
{
if( c<=0 ) return;
if( 2*c<=siz[now] )
{
ans=max(ans,c);
}
else
{
int len=(siz[now]+c+1)/2;
ans=max(ans,len);
// printf("%d\n",len);
}
}
int main()
{
n=read(),t=read();
for( int i=1;i<n;i++ )
{
int u,v;
u=read(),v=read();
g[u].push_back(v);
g[v].push_back(u);
}
dfs(n,0);
if( d[1]-d[n]<=t )
{
puts("0");
return 0;
}
else
{
int now=1;
while( t-- ) now=fa[now];
int c=d[now]-d[n];
int cnt=0;
while( now!=n )
{
solve(now,c-cnt*3);
cnt++;
now=fa[now];
}
printf("%d\n",ans);
}
}
/*
12 1
10 9
9 8
8 7
7 1
7 6
6 5
5 4
4 3
3 2
11 10
12 11
*/
2020牛客暑假多校赛补题 文章被收录于专栏
自闭补题
投递网易等公司10个岗位 >