D. Strange Fractions
$\frac{a}{b}=x$
原式即
$x + \frac{1}{x} = \frac{p}{q}$ 解方程然后$\delta$为整数即可算出对应的$a$和$b$
#include <bits/stdc++.h>
using namespace std;
long long p,q;
int main(){
int T;
scanf("%d",&T);
while (T--){
cin>>p>>q;
if (p<2*q){
printf("0 0\n");
continue;
}
long long delta = sqrt(1ll*p*p-4ll*q*q);
if (delta*delta == 1ll*p*p-4ll*q*q){
long long b = p+delta;
long long a = 2*q;
long long r = __gcd(a,b);
printf("%lld %lld\n",a/r,b/r);
}
else{
printf("0 0\n");
}
}
return 0;
}
E. Strange Integers
萌萌签到题
排序后贪心，能取则取即可。
#include <bits/stdc++.h>
using namespace std;
int a[100005],N,K;
int main(){
scanf("%d%d",&N,&K);
for (int i = 1; i<= N ;i++)
scanf("%d",&a[i]);
sort(a+1,a+N+1);
int nw = 0,ans = 0;
for (int i=2;i<=N;i++){
//cout<<nw<<" ";
nw += a[i]-a[i-1];
//cout<<a[i]<<" "<<nw<<endl;
if (nw >= K){
ans ++;
nw = 0;
}
}
cout<<ans+1;
return 0;
}
G. Edge Groups
树形$dp$
$f[i]$表示$i$的子树能分尽量分的方案
如果子树的节点个数是奇数的话
说明子树内就可以自己分配完，不用这条接到父亲的边
否则一定要用掉这条接到父亲的边
然后发现，这些不用接到父亲的边可以称为"自由边"
可以随意配对
$g[n]$表示$n$个东西随意配对的方案数
$g[n] = g[n-2]*(n-1)$递推即可。
如果自由边数量为奇数，说明有一条自由边要向上配对
$cnt+1$即可
#include <bits/stdc++.h>
using namespace std;
vector<int> G[100005];
long long dp[100005],f[100005],Siz[100005];
const int fish = 998244353;
void jt(int u,int v){
G[u].push_back(v);
G[v].push_back(u);
}
void dfs(int Now,int fa){
dp[Now] = 1;
Siz[Now] = 1;
int cnt = 0;
for (auto v:G[Now]){
if (v == fa) continue;
dfs(v,Now);
(dp[Now] *= dp[v])%=fish;
Siz[Now] += Siz[v];
if (Siz[v]&1) cnt++;
} if (cnt & 1) cnt++;
(dp[Now] *= f[cnt])%=fish;
}
int main(){
int N;
scanf("%d",&N);
for (int i = 1 ; i < N; i++){
int u,v;
scanf("%d%d",&u,&v);
jt(u,v);
}
f[0] = 1;
for (int i = 2 ; i<= N;i+=2)
f[i] = 1ll*f[i-2]*1ll*(i-1)%fish;
dfs(1,1);
cout<<dp[1];
return 0;
}
H. Life is a Game
有点像那题归程。
发现因为走边没有消耗，所以其实走路的过程在最小生成树上一定是最优的。
但是有多个询问，不好处理
利用$krusual$重构树，建树出来
因为越接近根节点的边的值越大，所以其实只要不断地往上跳，能跳到一个点就说明能到这个点的所有子节点，更新一下当前的能量
这个跳的过程可以用倍增优化。
#include <bits/stdc++.h>
using namespace std;
int N,M,Q;
int a[200005];
long long Sum[200005],Cos[200005];
int fa[200005];
int f[200005][25];
vector<int>G[200005];
void AddEdge(int u,int v){
G[u].push_back(v);
}
struct Node{
int u,v,w;
}E[200005];
int temp(Node a,Node b){
if (a.w == b.w && a.u == b.v) return a.v<b.v;
if (a.w == b.w) return a.u<b.u;
return a.w<b.w;
}
int Getfa(int x){
if (x == fa[x]) return x;
else return fa[x] = Getfa(fa[x]);
}
int tot;
void Krusual(){
scanf("%d%d%d",&N,&M,&Q);
for (int i = 1 ; i <= N ; i++) fa[i] = i;
for (int i = 1;i<=N;i++) scanf("%d",&a[i]);
for (int i = 1;i<=M;i++) scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].w);
sort(E+1,E+M+1,temp);
tot = N;
for (int i = 1 ;i<= M ;i++){
if (Getfa(E[i].u) != Getfa(E[i].v)){
int fx = Getfa(E[i].u),fy=Getfa(E[i].v);
tot++;
Cos[tot] = E[i].w;
AddEdge(tot,fx);
AddEdge(tot,fy);
AddEdge(fx,tot);
AddEdge(fy,tot);
fa[fx] = fa[fy] = fa[tot] = tot;
}
}
}
void dfs(int Now,int fa){
f[Now][0] = fa;
Sum[Now] = a[Now];
for (int i = 1;i <= 20 ; i++) f[Now][i] = f[f[Now][i-1]][i-1];
for (auto x : G[Now]){
if (x == fa) continue;
dfs(x,Now);
Sum[Now] += Sum[x];
}
}
void Solve(int x,int K){
Cos[0] = 1e16;
long long Now = K + a[x];
int pos = x;
while (pos != tot){
bool flag = false;
for (int i = 20 ; i >= 0 ;i--)
if (Now >= Cos[f[pos][i]]){
pos = f[pos][i];
flag = true;
}
if (flag){
Now = K + Sum[pos];
}else break;
}
printf("%lld\n",Now);
}
int main(){
Krusual();
dfs(tot,tot);
while (Q--){
int x,K;
scanf("%d%d",&x,&K);
Solve(x,K);
}
return 0;
}
I. Steadily Growing Steam
首先理解清楚题意。
其实本质上是一个先选物品后分组的问题
容易想到一个朴素的$dp$
$dp[i][j][S][T]$表示考虑到$i$,翻倍次数为$j$,$S$集合的重量和为$S$,$T$集合重量和为$T$的最优解
但是会发现这样时间和空间都不能接受，需要压维
首先第一维可以滚动数组优化一下
然后考虑$S$和$T$，其实我们需要知道的信息有什么？
其实只有$S$和$T$是否相等，而不关心他们的具体取值、
于是其实后两维可以压成一维$S-T$(很常见的套路)
然后就根据每个物品放不放，翻倍不翻倍，放$S$还是$T$分类即可。
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
const long long NINF = 0x8888888888888888;
int n, k;
long long dp[2][N][N * 13 * 2]; // dp[i][j][S - T]
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k;
int o = 0;
memset(dp, NINF, sizeof dp);
dp[o ^ 1][0][0] = 0;
for (int i = 1; i <= n; i++, o ^= 1) {
long long v; int t;
cin >> v >> t;
for (int j = 0; j <= k; j++) {
for (int st = 0; st <= 100 * 13 * 2; st++) {
dp[o][j][st] = dp[o ^ 1][j][st];
if (dp[o ^ 1][j][abs(st - t)] != NINF) {
dp[o][j][st] = max(dp[o][j][st], dp[o ^ 1][j][abs(st - t)] + v);
}
if (dp[o ^ 1][j][st + t] != NINF) {
dp[o][j][st] = max(dp[o][j][st], dp[o ^ 1][j][st + t] + v);
}
if (j > 0 && dp[o ^ 1][j - 1][abs(st - t * 2)] != NINF) {
dp[o][j][st] = max(dp[o][j][st], dp[o ^ 1][j - 1][abs(st - t * 2)] + v);
}
if (j > 0 && dp[o ^ 1][j - 1][st + t * 2] != NINF) {
dp[o][j][st] = max(dp[o][j][st], dp[o ^ 1][j - 1][st + t * 2] + v);
}
}
}
// for (int j = 0; j <= k; j++) {
// for (int st = 0; st <= 4; st++) {
// cout << dp[o][j][st] << " ";
// }
// cout << endl;
// }
}
o ^= 1;
long long ans = NINF;
for (int j = 0; j <= k; j++) {
ans = max(ans, dp[o][j][0]);
}
cout << ans << endl;
return 0;
}
K. Circle of Life
训练赛最后一分钟压线通过，十分的刺激
很有趣的一个题
首先，考虑题目给的一个循环节，发现循环节可以循环，有一部分原因是因为两边是墙壁，会直接炸掉$1$
于是就会猜想，是否可以把这个字符串分解成一堆比较小的串，这些串形如$1xxxxxx1$，然后在若干次操作后回到$1xxxxx1$，此时首尾的两个$1$就充当原本题目中墙壁的位置。
然后稍微试一试就会发现$1001$是一个满足条件的串
但是至此我们只解决了长度模$4$为$0$的部分，还有模$4$为$1$,$2$,$3$的部分
显然，长度为$2$有唯一解$01$
将$01$和$1001$拼在一起，会发现这个串仍然有循环。
所以$2$的做法是，$01 1001 1001 1001$以此类推
然后到$3$，会发现长度为$3$是无解的(可以手动验证一下)
问题即转化为找一个长度为$7$的串，使得它合法，且最后一位为$1$
人类智慧或者打表可以发现，长度为$7$的串答案是$0101001$
$0101001 1001 1001$这样即可。
还有一个长度模$4$为$1$，显然这时候$1$是无解的
考虑长度为$5$的串，发现答案是$10001$
同样的构造即可。
#include <bits/stdc++.h>
using namespace std;
string ss[7]={"1001","10001","01","0101001"};
int main(){
int N;
cin>>N;
if (N<=7){
if (N==2) {
cout<<"01";
}
if (N==3){
cout<<"Unlucky";
}
if (N==4){
cout<<"1001";
}
if (N==5){
cout<<"10001";
}
if (N==6){
cout<<"011001";
}
if (N==7){
cout<<"0101001";
}
}
else{
int x = N%4;
cout<<ss[x];
N-=ss[x].length();
int cnt = N/4;
for (int i = 1;i<=cnt;i++){
cout<<"1001";
}
}
return 0;
}
尝试了但还没做出来的题：
J. Two Binary Strings Problem
只是记录一下训练赛时的想法。
首先，这个问题可以类似括号匹配的，$0$视为$-1$,$1$视为$+1$，区间和大于$0$意味着这个区间合法。
此时，假设我们已经通过某种手段快速求得了对于每个$A_i$，它长度为$1,2,3,$...$k$是否合法，存在一个$bitset$里
然后考虑怎么快速的获得$lucky number$
对于$b_i$为$1$的位置来说，显然，所有的数字在这一位都要是$1$，那么全部的$k$取个$&$，看是不是$1$即可。
同理，$b_i$为$0$的位置，其实此时$0$充当了$1$的位置，对这个串取个反即可。
这样做完之后直接把所有的位全部$&$起来就好了。
回到最开始的问题，如何快速求解当前位置对应的$1$区间
考虑问题的本质
1、位置在当前位置前面
2、前缀和小于当前位置
显然，这是一个二维偏序问题。
把$sum$排个序，顺序扫描，前缀位置做个$bitset$，每次扫到一个位置的时候，把前面的答案拿进来，去掉位置比当前靠后的，然后再把这个位置本身加入前缀的$bitset$里
但是注意一个细节，这里的是绝对位置关系，而上面的串存的是相对位置关系。
这个问题位移取反应该能解决？
训练赛中代码没弄完，细节挺多的，回头应该会补(咕咕？)