CodeForces 1482B Restore Modulo GCD，条件结构入门题（误）-白红宇的个人博客

CodeForces 1482B Restore Modulo GCD，条件结构入门题（误）

发布日期：2021-05-10 11:29:10 浏览次数：12 分类：精选文章

本文共 2428 字，大约阅读时间需要 8 分钟。

题目链接

题意

思路

通过推导式子，发现本题可以分为几种情况来处理：

等差递减或等差递增：在这种情况下，直接判断是否满足等差数列的特征。如果是等差递增或递减的，那么最大化的m就是数组的最大递增或递减的值。

其他情况：在其他情况下，我们需要计算所有相邻元素的差分以及这些差分的最大公约数gcd。

特殊情况处理：如果存在不止一个差分值，那么这种情况的m只能被返回-1。这是因为题目中对m的限制条件不满足。

教训与收获

在这个问题中，我们学到了以下几点教训：

边界条件的处理：在编写代码时，必须注意数组的长度以及元素的范围。例如，当数组的长度为2时，不需要进行多余计算，因为无法确定是否为等差数列。

逻辑清晰：在进行复杂的逻辑判断时，必须确保每一步的条件都被正确处理，避免逻辑错误。

多想反例：通过多次测试样例数据，可以帮助发现潜在的问题，并确保代码在各种情况下都能正常运行。

代码实现

#include 
   
    #include 
    
     #include 
     
      #include 
      #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);#define endl "\n"using namespace std;typedef long long ll;const int maxn = 200502;const int inf = 0x3f3f3f3f;// 定义gcd函数auto gcd = [](int a, int b) { return b ? gcd(b, a % b) : a;};// 函数返回m的最大值，返回-1表示不满足条件，返回0表示存在多个解int getMaxM(int n, int a[]) { if (n < 2) return -1; int diff = a[2] - a[1]; int m = diff; bool isStrictlyIncreasing = true; for (int i = 2; i < n; ++i) { int current_diff = a[i] - a[i - 1]; if (current_diff != diff) { if (isStrictlyIncreasing) { return (diff == 0) ? 0 : -1; } m = gcd(m, diff); } else { if (diff != 0 && current_diff == diff) { continue; } } // 更新差分 if (current_diff != diff) { diff = current_diff; isStrictlyIncreasing = (diff > 0); } } // 检查是否是非递增或非递减的等差数列 if (diff <= 0 || (n > 2 && !isStrictlyIncreasing)) { if (diff == 0) { // 所有a[i]相同，返回m=0 return 0; } else { // 检查是否全部差分都等于diff for (int i = 2; i < n; ++i) { if (a[i] - a[i - 1] != diff) return -1; } // 检查是否等差递增 for (int i = 1; i < n; ++i) { if (a[i + 1] - a[i] != diff) return -1; } // 能得到一个合适的m return diff; } } else { // 检查非递减 for (int i = 2; i < n; ++i) { if (a[i] - a[i - 1] != diff) return -1; } return m; }}int main() { IOS #ifndef ONLINE_JUDGE freopen("D:\\_ACM_code\\IO\\in.txt", "r", stdin); freopen("D:\\_ACM_code\\IO\\out.txt", "w", stdout); #endif int tn; cin >> tn; while (tn--) { int n; vector
               
                 a; for (int i = 0; i < n; ++i) { a.push_back(i); // 假设数组由连续的整数构成示例 } if (n == 2) { cout << -1 << endl; continue; } // 假设计算m的最大值 int res = getMaxM(n, a); if (res == -1) cout << -1 << endl; else if (res == 0) cout << 0 << endl; else cout << res << endl; }}

以上代码实现主要负责以下几个步骤：

计算初始差值：从a[2] - a[1]开始计算初始差值。

遍历差分：一旦差值发生变化，就更新差分值并计算差分值的最大公约数。

检查条件：对于非严格递增或递减的情况，返回-1。对于所有差分都相等但非交替的情况，返回最大公约数。

特殊情况处理：如果所有元素都相同，则返回m=0。

在实际运行中，代码还会处理边界条件，比如n=2的情况，直接返回-1，因为无法确定是否是等差数列。如果存在不止一个差值，那么返回-1，因为m无法同时满足所有条件。

上一篇：CodeForces 1484C Basic Diplomacy 网络流模板题

下一篇：2021年度训练联盟热身训练赛第二场 J-Lowest Common Ancestor 进制转换，LCA

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

题目链接

题意

思路

教训与收获

代码实现

发表评论

最新留言

关于作者

推荐文章