A.Groundhog and 2-Power Representation
题意
给一个表达式，转为一个10进制数。例如：(2(2)+2+2(0))+2(2+2(0))+2(0) = 137
思路
直接上python
代码
s = input()
ans = ''
for i in s:
if i == '(':
ans += '**('
else:
ans += i;
print(eval(ans));
B. Groundhog and Apple Tree
题意
有一颗数，从根节点1开始走，经过所有的点且每条边只能走两次，再回到根节点1.每条边都有一个边权$ w_i $，每一次经过这条边都会消耗$w_i$的HP.每个节点都有一个果子，吃掉这个果子会获得$a_i$的HP，但每个节点的果子只能吃一次.在每个节点，每休息一个单位时间就会恢复1HP.
求在任何时候的HP都为非负数的最少休息时间.
$ 1 \leq T \leq 1000, 1 \leq n \leq 10^{5}, \sum n \leq 10 ^{6}, 0 \leq a_i, w_i \leq 2^{31}$
思路
场上一顿乱贪，事实证明瞎搞还是A不了题的
如何求子结点的遍历顺序？
仔细一想，可以发现，A->B->A包含两种情况
1. $ 消耗值cost \leq 获得值gain$
2. $ 消耗值cost > 获得值gain$
贪心策略
对于只含第1种情况，我们肯定直接按 消耗值cost小 的思路贪心即可
对于只含第2种情况，利用johnson法则，让消耗值的最大值尽量小，即
$$max(a.cost, a.cost - a.gain + b.cost) < max(b.cost, b.cost - b.gain + a.cost)$$
也可化简公式，转化为$ a.gain > b.gain $
对于两种同时包含的情况，肯定优先选择第一种
这题写的时候细节也挺多
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<long, long> PLL;
const int N = 1e5 + 10;
int t, n, x, y;
ll w, a[N];
struct Tree{
int v, ne;
ll w;
}edge[N << 1];
int head[N], tot;
void add(int x, int y, ll w)
{
edge[++tot].v = y;
edge[tot].w = w;
edge[tot].ne = head[x];
head[x] = tot;
}
struct node{
int id;
ll cost, gain;
}d[N];
bool cmp(const node &a, const node &b)
{
if (a.gain >= a.cost)
{
if (b.gain >= b.cost) return a.cost < b.cost;
else return true;
}
else
{
if (b.gain >= b.cost) return false;
else
{
ll val1 = max(a.cost, a.cost - a.gain + b.cost);
ll val2 = max(b.cost, b.cost - b.gain + a.cost);
return val1 < val2;
}
//else return a.gain > b.gain;
}
}
ll ans = 0;
void dfs(int son, int fa)
{
vector<node>p;
for (int i = head[son]; i; i = edge[i].ne)
{
int v = edge[i].v;
if (v == fa) continue;
dfs(v, son);
d[v].id = v;
d[v].cost += edge[i].w;
d[v].gain -= edge[i].w;
if (d[v].gain < 0) d[v].cost -= d[v].gain, d[v].gain = 0;
p.push_back(d[v]);
}
sort(p.begin(), p.end(), cmp);
d[son].cost = d[son].gain = 0;
ll tmp = a[son];
for (auto x: p)
{
tmp -= x.cost;
if (tmp < 0)
{
d[son].cost -= tmp;
tmp = 0;
}
tmp += x.gain;
}
d[son].gain = tmp;
}
void init(int n)
{
for (int i = 0; i <= n; i++) head[i] = 0;
for (int i = 0; i <= n; i++) d[i].id = d[i].cost = d[i].gain = 0;
tot = 0;
}
int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
init(n);
for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
for (int i = 1; i < n; i++)
{
scanf("%d %d %lld", &x, &y, &w);
add(x, y, w);
add(y, x, w);
}
dfs(1, 0);
printf("%lld\n", d[1].cost);
}
return 0;
}
E.Groundhog Chasing Death
题意
$ \prod_{i=a}^b \prod_{j=c}^d gcd(x^i, y^j) $ $ mod $ $ 998244353$
$0 \leq a,b,c,d \leq 3 * 10^{6}, 0 < x,y \leq 10^{9}, a \leq b,c \leq d$
思路
直接枚举质因子，暴力求解即可
场中脑子混乱，假代码满天飞
代码
#include<bits/stdc++.h>
using namespace std;
const int P=998244353;
int qpow(int a,long long b){
int res=1;
for(;b;b>>=1){
if(b&1){
res=1ll*res*a%P;
}
a=1ll*a*a%P;
}
return res;
}
int main(){
int a,b,c,d,x,y;
cin>>a>>b>>c>>d>>x>>y;
vector<int>p;
int D=__gcd(x,y);
for(int i=2;i<=D/i;i++){
if(D%i==0){
p.push_back(i);
while(D%i==0)D/=i;
}
}
if(D!=1){
p.push_back(D);
}
if(D==P){
cout<<"0\n";
return 0;
}
vector<int>c1,c2;
for(auto& i:p){
int c=0;
while(x%i==0)x/=i,c++;
c1.push_back(c);
c=0;
while(y%i==0)y/=i,c++;
c2.push_back(c);
}
int ans=1;
const int N=3e6;
for(int j=0;j<p.size();j++){
long long cc=0;
for(int i=a;i<=b;i++){
int lim=c1[j]*i;
int cut=lim/c2[j];
cut=max(cut,c-1);
cut=min(cut,d);
long long x=(cut+c)*(cut-c+1ll)>>1;
cc+=x*c2[j]%(P-1);
long long up=1ll*i*(d-cut);
cc+=up*c1[j]%(P-1);
}
ans=1ll*ans*qpow(p[j], cc)%P;
}
cout<<ans;
}
I.The Crime-solving Plan of Groundhog
题意
给n个$0 - 9$的数字，将n个数字分成2组，每组生成1个正整数，且不含前导零.求两个数的最小乘积.
$1 \leq T \leq 1000, 2 \leq n \leq 100000, 1 \leq \sum n \leq 1000000$
思路
将最小的非负数划分到一组中；其余数字划分到另一组中，组成一个最小合法正整数.将两数相乘即为答案
注意：高精度乘法
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<int> mul(vector<int> &A, int b)
{
vector<int> C;
int t = 0;
for (int i = 0; i < A.size() || t; i ++ )
{
if (i < A.size()) t += A[i] * b;
C.push_back(t % 10);
t /= 10;
}
return C;
}
int t, n, a[N];
int num[10];
int main()
{
scanf("%d", &t);
while (t--)
{
int mi = 10;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 0; i < 10; i++) num[i] = 0;
for (int i = 1; i <= n; i++) num[a[i]]++;
for (int i = 1; i < 10; i++)
if (num[i]) mi = min(mi, i);
int lval = mi; num[lval]--;
vector<int>v;
int flag = 0;
for (int i = 1; i < 10 && !flag; i++)
for (int j = 1; j <= num[i] && !flag; j++)
{
v.push_back(i);
num[i]--;
flag = 1;
}
for (int i = 0; i < 10; i++)
for (int j = 1; j <= num[i]; j++)
v.push_back(i);
reverse(v.begin(), v.end());
vector<int> ans = mul(v, lval);
reverse(ans.begin(), ans.end());
for (auto x: ans)
{
printf("%d",x);
}
printf("\n");
}
return 0;
}
J.The Escape Plan of Groundhog
题意
给一个$n*m$的01矩阵，求满足以下条件的子矩阵个数.
1. 宽度和高度必须大于1
2. 四条边界上的值必须为1
3. 内部（不含边界）的0和1的数量差值（绝对值）小于等于1
$1 \leq n,m \leq 500$
思路
前期把题读错了，把绝对值漏了，导致卡题
从数据范围可得，可支持$O(N^3)$的时间复杂度
将01矩阵中的0记为-1，求一遍二维前缀和，即可得到前缀矩阵1和0的数量差值
由于题中只需求绝对值小于等于1 $~$且$~$n和m的范围很小，那么直接在数组中找对应合法个数即可
首先枚举上下边界，然后用双指针(l,r)的思想将列扫一遍.
r指针遍历到合法的情况就将’前缀’压入数组中，l指针遍历到合法的情况先从数组中删除’前缀’,再求对应合法解。
注意：前缀和可能出现负数，因此需要扩大一倍数组;宽度和高度必须大于1
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 510;
int n, m;
int mp[N][N], down[N][N], cnt[600010], pre[N][N];
int main()
{
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%d", &mp[i][j]);
for (int i = n; i >= 1; i--)
for (int j = m; j >= 1; j--)
if (mp[i][j] == 1) down[i][j] = down[i + 1][j] + 1;
else down[i][j] = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (mp[i][j] == 1) pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + 1;
else pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] - 1;
ll ans = 0;
for (int i = 1; i <= n; i++)
{
for (int j = i + 1; j <= n; j++)
{
int l = 1, r = 1;
while (r <= m)
{
if (mp[i][r] + mp[j][r] < 2)
{
l++; r++;
continue;
}
while (r <= m && mp[i][r] && mp[j][r])
{
if (down[i][r] >= j - i + 1)
{
cnt[pre[j - 1][r] - pre[i][r] + 300000]++;
// if (j == 4) cout << i << " " << j << " " << r << " " << pre[j - 1][r] - pre[i][r] << endl;
}
r++;
}
while (l < r)
{
if (down[i][l] >= j - i + 1) cnt[pre[j - 1][l] - pre[i][l] + 300000]--;
else
{
l++;
continue;
}
int val = pre[j - 1][l] - pre[i][l] + (j - i - 1);
// if (j == 4) cout << "query:" << val << endl;
val += 300000;
ans += cnt[val - 1] + cnt[val] + cnt[val + 1];
l++;
}
// cout << "l:" << l << endl;
}
// cout << i << " " << j << " " << ans << endl;
}
}
printf("%lld\n", ans);
return 0;
}
K.The Flee Plan of Groundhog
题意
有一棵树,树边为1m，Groundhog在节点1，Orange在节点n.前t时刻，Groundhog向n走（沿最短路径），速度1m/s，Orange不动.从t时刻开始，Orange开始抓Groundhog,Groundhog速度仍为1m/s,Groundhog也可以选择原地不动,而Orange速度为2m/s.问最长多少秒Orange能抓到Groundhog.
$1 \leq n \leq 10^{5}, 1 \leq t \leq n-1, 1 \leq x,y \leq n$
思路
首先，由题意可得Groundhog在t时刻的位置.
t时刻后，Orange肯定要尽量把Groundhog逼到角落上去，那么不妨把Orange所在的节点n设为根节点.
对于Groundhog而言，若此时刻有多条路可走，尽量要走到一条远离Orange的最长链上去.
那么，我们可以枚举t时刻后，若Groundhog继续沿原路径（最短路径）走所在的节点，如果Groundhog此时还未被Orange抓住，则挑一条最长链跑，求最长被抓到的时间.最后将枚举所求得的所有时间取最大值即可.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int head[N],cnt,n,t,dep[N],root,dep1[N],maxx;
bool ok[N];
struct edge{
int next,to;
}e[N<<1];
void add(int u,int v){
e[++cnt].next=head[u];
e[cnt].to=v;
head[u]=cnt;
}
void dfs(int u,int f){
dep[u]=dep[f]+1;
if(u==n)return;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(v==f)continue;
dfs(v,u);
ok[u]=ok[u]|ok[v];
}
}
void dfs1(int u,int f)
{
dep1[u]=dep1[f]+1;
maxx=max(maxx,dep1[u]);
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(v==f||ok[v])continue;
dfs1(v,u);
}
}
int main()
{
scanf("%d %d",&n,&t);
ok[n]=1;
for(int i=1;i<n;i++){
int a,b;scanf("%d %d",&a,&b);
add(a,b);add(b,a);
}
dfs(1,0);
if(dep[n]-dep[1]<=t){
puts("0");
return 0;
}
for(int i=1;i<=n;i++){
if(ok[i]&&dep[i]-dep[1]<t)ok[i]=0;
if(ok[i]&&dep[i]-dep[1]==t)root=i;
}
int ans=0;
int z=dep[n]-dep[1]-t;
for(int i=1;i<=n;i++){
if(i==n)continue;
if(ok[i]){
maxx=0;
dfs1(i,0);
int x=maxx-dep1[i];
int y=z-3*(dep[i]-dep[root]);
if(y<=0)continue;
if(x<=y)ans=max(ans,(x+y+1)/2);
else ans=max(ans,y+dep[i]-dep[root]);
}
}
printf("%d\n",ans);
}
