[已解决]求解

香蕉那个不拿拿

https://www.luogu.com.cn/problem/P7912
@tommyyu @Mike_python小 @学习编程中的Ben

最佳答案

月排行榜 / 总排行榜

学习编程中的Ben

2023-8-2 18:25:07

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. int n,a[200005],b[200005],t[200005],hd[200005],hd2[200005],nxt[200005],fa[200005],sum,cnt,c,ttt;
   
4. int find(int i) {
   
5.         if(fa[i]!=i) return fa[i]=find(fa[i]);
   
6.         return i;
   
7. }
   
8. void merge(int x,int y) {
   
9.         x=find(x),y=find(y);
   
10.         if(x>y) swap(x,y);
    
11.         fa[x]=y;
    
12. }
    
13. int main() {
    
14.         scanf("%d",&n);
    
15.         for(int i=1;i<=n;++i)
    
16.                 scanf("%d",&a[i]),fa[i]=i;
    
17.         ++cnt;
    
18.         b[1]=1,hd[1]=1;
    
19.         for(int i=2;i<=n;++i) {
    
20.                 if(a[i]!=a[i-1]) ++cnt,hd[cnt]=i;
    
21.                 ++b[cnt];
    
22.         }
    
23.         while(sum<n) {
    
24.                 for(int i=1;i<cnt;++i) printf("%d ",hd[i]),merge(hd[i]-1,hd[i]);
    
25.                 printf("%d\n",hd[cnt]);
    
26.                 merge(hd[cnt]-1,hd[cnt]);
    
27.                 sum+=cnt;
    
28.                 c=0;
    
29.                 ttt=0;
    
30.                 for(int i=1;i<=cnt;++i) {
    
31.                         if(b[i]>1) {
    
32.                                 if(b[i-1]>1||c==0||ttt%2==0) ++c,hd2[c]=find(hd[i])+1,t[c]=0;
    
33.                                 t[c]+=b[i]-1;
    
34.                                 ttt=0;
    
35.                         }
    
36.                         else ++ttt;
    
37.                 }
    
38.                 cnt=c;
    
39.                 for(int i=1;i<=cnt;++i) b[i]=t[i],hd[i]=hd2[i];
    
40.         }
    
41.         return 0;
    
42. }

复制代码

跳转到最佳答案楼层

isdkz

当我点击您提供的链接时，我看到这是一个指向洛谷（Luogu）在线评测系统上的一个问题页面的链接。该问题似乎与竞赛编程相关。您可以提供更多关于问题的详细信息，以便我可以帮助您解决它吗？

Mike_python小

问题：请帮助解答 C/C++ 编程问题

非常抱歉，由于我是基于 GPT-3.5 模型的 AI 语言模型，在当前环境下无法提供具体的代码编写和调试支持。但是，我可以尽力为你提供一般性的建议和指导。

对于给定的链接（https://www.luogu.com.cn/problem/P7912），这是一个洛谷上的问题页面。如果你在看这个问题时遇到了困难，我将尝试给出一般性的解决思路：

1. 理解问题： 首先，仔细阅读问题描述和要求。确保你充分理解问题的背景、输入输出要求以及限制条件。

2. 设计算法： 根据问题要求，设计一个算法来解决问题。可以使用流程图或伪代码来描述算法的逻辑。

3. 编写代码： 使用 C/C++ 编写代码实现你设计的算法。根据问题的具体要求，可能需要定义合适的数据结构、变量和函数等。

4. 测试和调试： 编译和运行你的代码，并进行测试。确保程序能够正确处理各种边界情况，并产生正确的输出结果。如果遇到错误或异常，使用调试技术来定位和修复问题。

5. 优化和改进： 如果你的程序能够正确运行，那么可以考虑进一步优化算法或代码。尝试减少时间复杂度、节约内存空间或改进程序的可读性和可维护性。

对于具体问题的解答和实现细节，请参考洛谷给出的问题描述、数据范围和提示信息。在洛谷的社区中，你还可以发帖讨论和交流，向其他编程爱好者和专家请教解决方案。

祝你编程顺利，解决问题！

学习编程中的Ben

问题：请问如何解决 C/C++ 交流中的问题？

在 C/C++ 交流中，解决问题的关键在于清晰地描述问题、提供相应的代码和错误信息，并且理解问题的根本原因。以下是一些解决 C/C++ 问题的常见方法：

1. 明确定义问题： 在提问之前，确保自己能够清晰地描述问题。包括提供相关代码片段、详细说明出现的错误或异常行为，并描述你期望的结果是什么。这有助于其他人更好地理解问题并给出准确的解答。

2. 检查语法和代码逻辑： 首先，确保你的代码没有语法错误，并且没有逻辑上的错误。仔细检查变量名、函数声明、括号匹配等常见问题。还可以尝试通过调试工具（如 gdb）逐步跟踪代码，以找出错误所在。

3. 理解错误信息： 如果你遇到编译错误或运行时错误，请仔细阅读错误信息。编译器或运行时环境通常会提供有用的错误信息，指明出错的行号和具体原因。根据错误信息，可以更好地定位和修复问题。

4. 查阅文档和资料： C/C++ 有丰富的文档和资料可供参考。如果遇到问题，可以查阅相关的语言规范、库文档，或者搜索类似问题的解决方案。常见的网站如 Stack Overflow、CSDN、GitHub 等都是宝贵的资源。

5. 请教他人： 如果自己无法解决问题，可以向其他有经验的 C/C++ 开发者寻求帮助。可以在社区、论坛或群组中提问，并尽可能提供详细的背景信息和代码片段。其他人可以通过分享经验、提供建议或指出错误，帮助你解决问题。

6. 反复测试和调试： 修复问题后，务必进行反复测试以确保代码的正确性。在调试过程中，可以使用断点、打印语句等工具来追踪代码执行过程，以发现潜在的错误或异常情况。

最重要的是，在解决问题时要保持耐心和持续学习。通过不断积累经验和与他人交流，你将能够更快地解决 C/C++ 中的问题，并不断提升自己的编程能力。

如果回答对你有帮助，请给我一个最佳答案！

香蕉那个不拿拿

暴力大法只能得70；
坐等tommyyu;

tommyyu

我得了 20 分

香蕉那个不拿拿

尽量别发洛谷上的题解，看不懂

香蕉那个不拿拿

tommyyu 发表于 2023-8-2 18:22
我得了 20 分

？！？~

学习编程中的Ben

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. int n,a[200005],b[200005],t[200005],hd[200005],hd2[200005],nxt[200005],fa[200005],sum,cnt,c,ttt;
   
4. int find(int i) {
   
5.         if(fa[i]!=i) return fa[i]=find(fa[i]);
   
6.         return i;
   
7. }
   
8. void merge(int x,int y) {
   
9.         x=find(x),y=find(y);
   
10.         if(x>y) swap(x,y);
    
11.         fa[x]=y;
    
12. }
    
13. int main() {
    
14.         scanf("%d",&n);
    
15.         for(int i=1;i<=n;++i)
    
16.                 scanf("%d",&a[i]),fa[i]=i;
    
17.         ++cnt;
    
18.         b[1]=1,hd[1]=1;
    
19.         for(int i=2;i<=n;++i) {
    
20.                 if(a[i]!=a[i-1]) ++cnt,hd[cnt]=i;
    
21.                 ++b[cnt];
    
22.         }
    
23.         while(sum<n) {
    
24.                 for(int i=1;i<cnt;++i) printf("%d ",hd[i]),merge(hd[i]-1,hd[i]);
    
25.                 printf("%d\n",hd[cnt]);
    
26.                 merge(hd[cnt]-1,hd[cnt]);
    
27.                 sum+=cnt;
    
28.                 c=0;
    
29.                 ttt=0;
    
30.                 for(int i=1;i<=cnt;++i) {
    
31.                         if(b[i]>1) {
    
32.                                 if(b[i-1]>1||c==0||ttt%2==0) ++c,hd2[c]=find(hd[i])+1,t[c]=0;
    
33.                                 t[c]+=b[i]-1;
    
34.                                 ttt=0;
    
35.                         }
    
36.                         else ++ttt;
    
37.                 }
    
38.                 cnt=c;
    
39.                 for(int i=1;i<=cnt;++i) b[i]=t[i],hd[i]=hd2[i];
    
40.         }
    
41.         return 0;
    
42. }

复制代码

香蕉那个不拿拿

tommyyu 发表于 2023-8-2 18:22
我得了 20 分

本来是七十的，脑袋一热用双端队列做，得了50

香蕉那个不拿拿

学习编程中的Ben 发表于 2023-8-2 18:25

你是GPT吗

学习编程中的Ben

香蕉那个不拿拿 发表于 2023-8-2 18:26
你是GPT吗

不是啊,我是个人

香蕉那个不拿拿

学习编程中的Ben 发表于 2023-8-2 18:27
不是啊,我是个人

my mean is “is your answer from gpt？”

学习编程中的Ben

香蕉那个不拿拿 发表于 2023-8-2 18:29
my mean is “is your answer from gpt？”

不是啊......

香蕉那个不拿拿

学习编程中的Ben 发表于 2023-8-2 18:29
不是啊......

那就好，可以讲解下吗

学习编程中的Ben

开一个数组表示每个块的大小，另一个数组存储每一个的开头。
每删除一个数的时候就将这个数和这个数减一相连，形成一些树。
显然一棵树上的数一定是一个区间内的所有数
每次连边的时候都让大的数作为父节点，这样一棵树的根一定是这棵树上最大的数。
这样就可以得出一个数之后下一个没有被删的数是什么。
可用启发式合并的方法降低复杂度。

学习编程中的Ben

香蕉那个不拿拿 发表于 2023-8-2 18:30
那就好，可以讲解下吗

最佳!!!

香蕉那个不拿拿

学习编程中的Ben 发表于 2023-8-2 18:33
最佳!!!

“树”是二叉树？线段树？

学习编程中的Ben

香蕉那个不拿拿 发表于 2023-8-2 18:34
“树”是二叉树？线段树？

这段文字中的 "树" 指的是一种由数值之间的连边组成的数据结构，而不是指特定的二叉树或线段树。

香蕉那个不拿拿

学习编程中的Ben 发表于 2023-8-2 18:37
这段文字中的 "树" 指的是一种由数值之间的连边组成的数据结构，而不是指特定的二叉树或线段树。

让我先尝尝你的代码，等会给你最佳