[已解决]洛谷小题目求助

额外减小

rt.

题目链接
https://www.luogu.com.cn/problem/P9698

问题
https://www.luogu.com.cn/discuss/700009

求hack/求调，都行，我比赛时候看了半个小时愣是看不出问题。是WA了。

Code:

1. #include <iostream>
   
2. #include <set>
   
3. #include <algorithm>
   
4. using namespace std;
   
5. 
   
6. struct pt{
   
7.         int v,l;//l 指所在斜线的编号
   
8. };
   
9. 
   
10. inline bool cmp(pt x,pt y)
    
11. {
    
12.         return x.v<y.v;
    
13. }
    
14. 
    
15. int main()
    
16. {
    
17.         ios::sync_with_stdio(false);
    
18.         cin.tie(0);
    
19.         int t,n,m,tmp,cnt;
    
20.         pt arr[2114514];
    
21.         // 共走 n+m step 故只需考虑前 n+m 个自然数即可。
    
22.         cin>>t;
    
23.         while(t--)
    
24.         {
    
25.                 cin>>n>>m;
    
26.                 cnt=0;
    
27.                 for(int i=0;i<n;i++)
    
28.                 {
    
29.                         for(int j=0;j<m;j++)
    
30.                         {
    
31.                                 cin>>tmp;
    
32.                                 if(tmp<n+m-1)//走 n+m-1 步，则只有 <n+m-1 的自然数才可能被加入
    
33.                                 {
    
34.                                         arr[cnt].l=i+j;
    
35.                                         arr[cnt].v=tmp;//tmp min=0 max=n+m-1
    
36.                                         cnt++;
    
37.                                 }
    
38.                         }
    
39.                 }
    
40.                 sort(arr,arr+cnt,cmp);
    
41.                 set<int> st;
    
42.                 bool flag=true;
    
43.                 for(int i=0;i<cnt;i++)
    
44.                 {
    
45.             //cout<<'='<<arr[i].v<<' '<<arr[i].l<<'='<<endl;
    
46.                         if(st.find(arr[i].l)==st.end())
    
47.                         {
    
48.                                 st.insert(arr[i].l);
    
49.                         }
    
50.                         else//该线已被占
    
51.                         {
    
52.                                 cout<<i<<endl;
    
53.                                 flag=false;
    
54.                                 break;
    
55.                         }
    
56.                 }
    
57.                 if(flag)
    
58.                 {
    
59.                         cout<<cnt<<endl;
    
60.                 }
    
61.         }
    
62. }

复制代码

最佳答案

月排行榜 / 总排行榜

sfqxx

2023-10-3 22:37:31

对拍代码:

1. t = int(input())
   
2. for _ in range(t):
   
3.     n, m = map(int, input().split())
   
4.     a = [list(map(int, input().split())) for _ in range(n)]
   
5. 
   
6.     l = 0
   
7.     r = n * m
   
8.     ans = 0
   
9. 
   
10.     while l <= r:
    
11.         k = (l + r) // 2
    
12.         p = -1
    
13.         flag = True
    
14. 
    
15.         for i in range(n):
    
16.             for j in range(m):
    
17.                 if a[i][j] < k:
    
18.                     if p > j:
    
19.                         flag = False
    
20.                         break
    
21.                     p = j
    
22. 
    
23.             if not flag:
    
24.                 break
    
25. 
    
26.         if flag:
    
27.             l = k + 1
    
28.             ans = k
    
29.         else:
    
30.             r = k - 1
    
31. 
    
32.     print(ans)

复制代码

l和r说明2分

但是可能有点慢

跳转到最佳答案楼层

isdkz

这道题目是一个简单的模拟题，但是需要注意的是，每一条斜线的编号是由它所在的位置的横纵坐标之和决定的，而不是直接从0开始编号。所以在存储每个数的时候，需要同时存储它所在的斜线编号和它的值，并按照值进行排序。然后，使用一个set来存储已经占用的斜线编号，如果一个数所在的斜线已经被占用，则输出该数的位置并结束程序。如果所有数都没有问题，则输出总数。以下是AC代码：

陶远航

首先，让我们分析一下代码的逻辑。这个代码试图解决洛谷的 P9698 问题。题目的大致描述如下：

给定一个 n×m 的矩阵，每个元素是一个非负整数。你需要从左上角 (1, 1) 走到右下角 (n, m)，每次只能向右或向下移动。你需要找到一条路径，使得路径上的整数之和最小。如果有多条这样的路径，输出字典序最小的一条。

代码的主要思路是：

1. 读取测试用例的数量 t。
2. 对于每个测试用例，读取矩阵的大小 n 和 m。
3. 读取矩阵中的元素，并将满足条件的元素（小于 n+m-1）存储在一个结构体数组 arr 中，同时记录它们所在的斜线编号。
4. 对 arr 数组按照元素值进行排序。
5. 使用一个 set st 来存储已经被占据的斜线编号。
6. 遍历排序后的 arr 数组，检查每个元素所在的斜线编号是否已经在 set st 中。如果不在，则将该斜线编号插入 set st；如果已经在 set st 中，输出当前遍历到的元素的索引并跳出循环。
7. 如果遍历完整个 arr 数组，输出 arr 数组的长度。

在这个代码中，我发现了一个可能的问题。在遍历排序后的 arr 数组时，你应该检查当前元素的斜线编号是否已经在 set st 中，而不是检查当前元素的索引。为了解决这个问题，你可以将以下代码段：

1. if(st.find(arr[ i].l)==st.end())
   
2. {
   
3.     st.insert(arr[ i].l);
   
4. }
   
5. else//该线已被占
   
6. {
   
7.     cout<<i<<endl;
   
8.     flag=false;
   
9.     break;
   
10. }
    

复制代码

修改为：

1. if(st.find(arr[ i].l)==st.end())
   
2. {
   
3.     st.insert(arr[ i].l);
   
4. }
   
5. else//该线已被占
   
6. {
   
7.     cout<<arr[ i].l<<endl;
   
8.     flag=false;
   
9.     break;
   
10. }
    

复制代码

这样，你将输出当前元素的斜线编号而不是索引。希望这个修改能帮助你解决问题。
如果问题已经解决，请设置最佳答案

Mike_python小

问题分析

根据题目链接和代码，这个问题是关于在一个给定的矩阵中找到满足特定条件的斜线的数量。具体来说，矩阵中的每个元素表示一个点，点的值为其所在斜线的编号。我们需要找到满足以下条件的斜线数量：在同一斜线上的所有点的值都小于 n+m-1。

代码审查

首先，我们来审查一下你的代码。在大致了解代码结构后，我发现了一个可能的问题。在检查斜线是否已被占用的部分，你使用了 set<int> 数据结构。然而，这可能导致错误的结果，因为 set 会自动排序并去除重复元素。这意味着，当你试图检查某个斜线是否已被占用时，你实际上可能在检查一个错误的斜线编号。

代码修改建议

为了解决这个问题，我建议你使用 unordered_set<int> 而不是 set<int>。unordered_set 是一个无序的集合，它不会自动排序元素。这样，你就可以正确地检查斜线编号了。以下是修改后的代码：

2. #include <iostream>
3. #include <unordered_set>
4. #include <algorithm>
5. using namespace std;
7. struct pt {
8.     int v, l; // l 指所在斜线的编号
9. };
11. inline bool cmp(pt x, pt y) {
12.     return x.v < y.v;
13. }
15. int main() {
16.     ios::sync_with_stdio(false);
17.     cin.tie(0);
18.     int t, n, m, tmp, cnt;
19.     pt arr[2114514];
21.     cin >> t;
22.     while (t--) {
23.         cin >> n >> m;
24.         cnt = 0;
25.         for (int i = 0; i < n; i++) {
26.             for (int j = 0; j < m; j++) {
27.                 cin >> tmp;
28.                 if (tmp < n + m - 1) {
29.                     arr[cnt].l = i + j;
30.                     arr[cnt].v = tmp;
31.                     cnt++;
32.                 }
33.             }
34.         }
35.         sort(arr, arr + cnt, cmp);
36.         unordered_set<int> st;
37.         bool flag = true;
38.         for (int i = 0; i < cnt; i++) {
39.             if (st.find(arr[i].l) == st.end()) {
40.                 st.insert(arr[i].l);
41.             } else {
42.                 cout << i << endl;
43.                 flag = false;
44.                 break;
45.             }
46.         }
47.         if (flag) {
48.             cout << cnt << endl;
49.         }
50.     }
51. }

复制代码

请尝试使用这个修改后的代码，并检查是否解决了你的问题。如果仍然存在问题，请随时提问，我会尽力帮助你。

球一个最佳答案谢谢啦！这对我非常重要！
本段回答来自Chat GPT-4，如有错误，多多包涵！

额外减小

isdkz 发表于 2023-10-3 22:19
这道题目是一个简单的模拟题，但是需要注意的是，每一条斜线的编号是由它所在的位置的横纵坐标之和决定的， ...

好好好

忘记的@人：

@元豪 @Mike_python小 @sfqxx @zhangjinxuan @Ewan-Ahiouy

sfqxx

对拍代码:

1. t = int(input())
   
2. for _ in range(t):
   
3.     n, m = map(int, input().split())
   
4.     a = [list(map(int, input().split())) for _ in range(n)]
   
5. 
   
6.     l = 0
   
7.     r = n * m
   
8.     ans = 0
   
9. 
   
10.     while l <= r:
    
11.         k = (l + r) // 2
    
12.         p = -1
    
13.         flag = True
    
14. 
    
15.         for i in range(n):
    
16.             for j in range(m):
    
17.                 if a[i][j] < k:
    
18.                     if p > j:
    
19.                         flag = False
    
20.                         break
    
21.                     p = j
    
22. 
    
23.             if not flag:
    
24.                 break
    
25. 
    
26.         if flag:
    
27.             l = k + 1
    
28.             ans = k
    
29.         else:
    
30.             r = k - 1
    
31. 
    
32.     print(ans)

复制代码

l和r说明2分

但是可能有点慢

sfqxx

@额外减小

人呢？？？

额外减小

sfqxx 发表于 2023-10-3 22:51
@额外减小

人呢？？？

来了

额外减小

sfqxx 发表于 2023-10-3 22:37
对拍代码:

发现没法对拍

我的程序占了亿点点内存（10Mib)就会强制退出

sfqxx

额外减小 发表于 2023-10-3 23:26
发现没法对拍

我的程序占了亿点点内存（10Mib)就会强制退出

唉