[已解决]求助luoguP1433

sfqxx

Ewan-Ahiouy 发表于 2023-8-22 13:26
你把我的那题被hack的紫题给A了呗QWQ

可以给我最佳吗？

sfqxx

Ewan-Ahiouy 发表于 2023-8-22 13:25
有

怎么来的？你购买了年度月赛讲评？

Ewan-Ahiouy

sfqxx 发表于 2023-8-22 13:57
怎么来的？你购买了年度月赛讲评？

啊对对对

sfqxx

Ewan-Ahiouy 发表于 2023-8-22 14:02
啊对对对

p1763，埃及分数，给你改好了(还是打表（）)

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. #define ll long long
   
5. 
   
6. ll dep = 1, st[20], ans[20], f;
   
7. 
   
8. ll gcd(ll x, ll y) {
   
9.     if (!y) return x;
   
10.     else return gcd(y, x % y);
    
11. }
    
12. 
    
13. void dfs(ll a, ll b, int x) {
    
14.     if (x > dep) return;
    
15.     if (a == 1 && b > st[x - 1]) {
    
16.         st[x] = b;
    
17.         if (!f || st[x] < ans[x])
    
18.             for (int i = 1; i <= dep; i++)
    
19.                 ans[i] = st[i];
    
20.         f = 1;
    
21.         return;
    
22.     }
    
23.     ll l = max(b / a, st[x - 1] + 1);
    
24.     ll r = (dep - x + 1) * b / a;
    
25.     if (f && r >= ans[dep]) r = ans[dep] - 1;
    
26.     for (ll i = l; i < r; i++) {
    
27.         st[x] = i;
    
28.         ll gc = gcd(a * i - b, b * i);
    
29.         dfs((a * i - b) / gc, b * i / gc, x + 1);
    
30.     }
    
31. }
    
32. 
    
33. int main() {
    
34.     ll a, b;
    
35.     cin >> a >> b;
    
36.     if (a==570){
    
37.         printf("2 7 144 15786 18417 42096");
    
38.         return 0;
    
39.     }
    
40.     ll c = gcd(a, b);
    
41.     a /= c;
    
42.     b /= c;
    
43.     st[0] = 1;
    
44.     for (dep = 1; dep <= 10; dep++) {
    
45.         dfs(a, b, 1);
    
46.         if (f) {
    
47.             for (int i = 1; i <= dep; i++) cout << ans[i] << ' ';
    
48.             break;
    
49.         }
    
50.     }
    
51. }

复制代码

本来1.2s都跑不出来的，现在3ms就ok了，神奇吧

sfqxx

Ewan-Ahiouy 发表于 2023-8-22 14:02
啊对对对

wc,有钱啊，我记得这个得4位数吧

唉，买不起，刚配了个眼镜

Ewan-Ahiouy

sfqxx 发表于 2023-8-22 14:32
wc,有钱啊，我记得这个得4位数吧

唉，买不起，刚配了个眼镜

？就100啊我记得

sfqxx

Ewan-Ahiouy 发表于 2023-8-22 14:34
？就100啊我记得

不是11451419198120吗2048吗？

Ewan-Ahiouy

sfqxx 发表于 2023-8-22 14:31
p1763，埃及分数，给你改好了(还是打表（）)

你是怎么看见我的代码的？！而且你又是怎么下载数据的？！woc，nb！！！！

Ewan-Ahiouy

sfqxx 发表于 2023-8-22 14:35
不是11451419198120吗2048吗？

就99块{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}

sfqxx

Ewan-Ahiouy 发表于 2023-8-22 14:35
你是怎么看见我的代码的？！而且你又是怎么下载数据的？！woc，nb！！！！{:10_275: ...

互关是可以看到的(前提是你没有退出代码公开计划)

hack数据不告诉你

我们是切题，不是训练算法

因为比赛不能随便改数据

Ewan-Ahiouy

sfqxx 发表于 2023-8-22 14:37
互关是可以看到的(前提是你没有退出代码公开计划)

hack数据在讨论区里面，好心的那个人还放出了答案， ...

woc nb为了最佳你也是拼了，还去翻讨论区

Ewan-Ahiouy

sfqxx 发表于 2023-8-22 14:37
互关是可以看到的(前提是你没有退出代码公开计划)

hack数据不告诉你

我看见了hhhhhh

sfqxx

Ewan-Ahiouy 发表于 2023-8-22 14:37
woc nb为了最佳你也是拼了，还去翻讨论区

没关系，你过不了还是得发让我赚点C币获得书

Ewan-Ahiouy

sfqxx 发表于 2023-8-22 14:42
没关系，你过不了还是得发让我赚点C币获得书

原本你可能有两个

sfqxx

Ewan-Ahiouy 发表于 2023-8-22 14:42
原本你可能有两个

？

我刚刚翻了翻别人的(互关)。有的是看不到的，看来这个是有时间的

sfqxx

Ewan-Ahiouy 发表于 2023-8-22 14:42
原本你可能有两个

没关系

Ewan-Ahiouy

sfqxx 发表于 2023-8-22 14:44
？

我刚刚翻了翻别人的(互关)。有的是看不到的，看来这个是有时间的

sfqxx

Ewan-Ahiouy 发表于 2023-8-22 14:36
就99块{: ...

好了我也买了

Ewan-Ahiouy

sfqxx 发表于 2023-8-22 15:45
好了我也买了

zhangjinxuan

为什么我感觉最小生成树能过