2024杭电7

题意：
给定n个敌人的伤害值，自己的生命值，和烟雾弹的数量。
烟雾弹可以逃离一次战斗，必须按顺序依次战斗，问最多能活过几轮。

题解：
就枚举能活过$i$轮，取前$i$个伤害值的最大k个值用烟雾弹逃避伤害。
判断剩下的战斗能不能活下来就行。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+6;
const int mod=1e9+7;
int a[N];
priority_queue <int,vector<int>,greater<int> > q;
void solve()
{int n,k,x;cin>>n>>x>>k;for(int i=1;i<=n;i++){cin>>a[i];}while(!q.empty()){q.pop();}int ans=min(n,k);for(int i=1;i<=min(n,k);i++){q.push(a[i]);}int f=1;for(int i=min(n,k)+1;i<=n;i++){int y;if(q.empty()){x-=a[i];if(x<=0){ans=i-1;f=0;break;}continue;}else y=q.top();if(y<a[i]){x-=y;if(x<=0){ans=i-1;f=0;break;}q.pop();q.push(a[i]);}else {x-=a[i];if(x<=0){ans=i-1;f=0;break;}}}if(f){cout<<n<<'\n';}elsecout<<ans<<'\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int T = 1;cin >> T;while (T--){solve();}}

题意：
有蛋糕$y$个，草莓$x$个。
可以把蛋糕切为$2my$块，草莓切为$2nx$块。
现在要保证每块蛋糕都有草莓，并且草莓数量一样。
优先保证每个草莓大小最大，再保证每个蛋糕最大。
问最后蛋糕数量和每个蛋糕的草莓数量。

题解：
首先，假如草莓是蛋糕的倍数，不用切。
蛋糕是不用切的，如果切了，草莓要切更多才能是蛋糕的倍数。
有$2nx=cy$，要使$n$最小，那$c$就是$\frac{2x}{gcd(y,2x)}$。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef __int128 i128;
typedef long long ll;
typedef double db;const db PI = acos(-1);
typedef array<ll, 2> PII; // vector<PII> a(n + 1);
const ll inf = 2e18 + 10;
const int mod = 998244353;
const int maxn = 2e5 + 10;
bool multi = 1;void Solve() {ll x, y; cin >> x >> y;ll z = __gcd(x, y);if(x % y == 0) cout << y << " " << x / y << "\n";else {if((y / z) % 2 == 0) cout << y << " " << x / z << "\n";else cout << y << " " << x / z * 2 << "\n";}
}signed main() {// freopen("test.in","r",stdin);  // freopen("code.out","w",stdout);    ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);ll T = 1;if(multi) cin >> T;while(T -- ) {Solve();}return 0;
}

题意：
有$n$种物品，可能是原材料，也可能是合成产物。
给你所有合成产物的配方。首先一种原材料只能是一种合成产物的原料。
给定原材料采集需要的时间，合成不需要时间。
现在想要生产一件最终产物，可以选一种材料为无限的前提，问最短时间是多少，如果大于$10^9$就输出$Impossible$。

题解：
这就是一颗树，根为最终产物，可以选一个时间最大孩子为无限的，递归一下其他的孩子需要的时间。假如有一个孩子已经有$10^9$就选这个孩子，就选这个孩子，有两个就直接输出$Impossible$。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+6;
const int M=1e9;
int p[N],t[N];
vector<pair<int,int> > a[N];
int f=0;int dfs(int x,int b)
{if(x>M){return M+6;}if(p[b]==0){if(x*t[b]>M)return M+6;return x*t[b];}else {int w=0,y;for(int i=0;i<t[b];i++){if(x*(a[b][i].first)>M)return M+6; y=dfs(x*(a[b][i].first), a[b][i].second);w+=y;if(w>M){return M+6;}}return w;}
}
int xx[N];
void solve()
{int n,k,x,nd;cin>>n>>k;for(int i=1;i<=n;i++){a[i].clear();}for(int i=1;i<=n;i++){cin>>p[i];if(p[i]==1){cin>>t[i];for(int j=1;j<=t[i];j++){cin>>x>>nd;a[i].push_back({x,nd});}}else {cin>>t[i];}}if(p[k]==0){cout<<t[k]<<'\n';return ;}f=0;int ma=0,sub,w=0,tt=t[k];for(int i=0;i<t[k];i++){sub=dfs(a[k][i].first,a[k][i].second);xx[i]=sub;}sort(xx,xx+tt);for(int i=0;i<tt-1;i++){ma+=xx[i];if(ma>M){cout<<"Impossible\n";return ;}}int ans=ma;if(ans<=M){cout<<ans<<'\n';}else cout<<"Impossible\n";}signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int T = 1;cin >> T;while (T--){solve();}}

题意：
给你一颗树，两人博弈，一人A可以选一个点半径为r1的轰炸区，一人B移动距离为r2。
不限时间，问两人谁最后获胜。

解题：
如果$r2<=2\times r1$，轰炸区可以一直把B向一个方向逼近，最后没有出路。
还有一种情况，轰炸区可以包含整棵树，找到树的直径，判断直径与轰炸区的大小。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+6;
int h[N];
vector<int> a[N];
int c,ma;void dfs(int u, int fa, int dep)
{if (dep>ma){ma = dep;c = u;}for (auto i:a[u]) {if (i==fa) continue;dfs(i,u,dep + 1);}
}void solve() {int n,s,r1,r2;cin >>n>>s>>r1>>r2;for (int i=1;i<=n;i++) a[i].clear();for (int i=1;i<n;i++) {int u,v;cin>>u>>v;a[u].push_back(v);a[v].push_back(u);}ma=0;c=s;dfs(s,0,1);ma=0;dfs(c,0,1);if (r1 * 2 >= r2 || ma <= r1 * 2 + 1) {cout << "Kangaroo_Splay\n";} else {cout << "General_Kangaroo\n";}
}signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int T = 1;cin >> T;while (T--) {solve();}
}