在线判题系统如何传递输入数据？及Codeforces两数组合问题求解咨询

嘿，我来帮你解答这两个问题：

首先说下OJ是怎么给你的程序传输入的——其实核心就是标准输入（stdin），和你平时在本地用键盘输入完全是一个逻辑：

• OJ会把预先准备好的测试用例（按照题目要求的格式写成纯文本），通过标准输入流直接发送给你的程序。你不用关心数据来源，只要用scanf、cin（C++）或者input()（Python）这类常规读取输入的方法就行，程序会自动从stdin里拿到数据。
• 举个例子，比如这道题的测试用例是：

  3 5
  1 2 3
  2 3 4
  

  OJ就会把这段文本原封不动地通过stdin传给你的程序，你的程序读第一行得到n=3和x=5，第二行得到数组A，第三行得到数组B。
• 对应的，你的程序要把结果输出到标准输出（stdout），OJ会捕获这个输出，和正确答案对比来判分。所以千万别输出多余的调试信息，不然会导致答案不匹配哦。

接下来聊聊这道题的解法，核心就是判断是否存在A[i] + B[j] = X，也就是B[j] = X - A[i]，这里有几种不同的思路，适合不同的场景：

1. 暴力枚举（适合小数据量） #

最直接的思路就是双重循环，遍历A的每个元素，再遍历B的每个元素，检查相加是否等于X。代码写起来很简单，但时间复杂度是O(n²)，如果n很大（比如1e5）的话会超时，所以只适合小数据的情况。

Python示例代码：

n, x = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

result = 0
for num_a in A:
    for num_b in B:
        if num_a + num_b == x:
            result = 1
            break
    if result:
        break
print(result)

2. 哈希集合优化（高效解法，推荐） #

把其中一个数组（比如B）的元素存入哈希集合，然后遍历A的每个元素，计算target = X - num_a，检查target是否在集合里。这样时间复杂度降到O(n)，空间复杂度O(n)，能轻松处理大数据量的测试用例。

Python示例代码：

n, x = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

b_elements = set(B)
result = 0
for num_a in A:
    if (x - num_a) in b_elements:
        result = 1
        break
print(result)

C++示例代码：

#include <iostream>
#include <unordered_set>
#include <vector>

using namespace std;

int main() {
    int n, x;
    cin >> n >> x;
    vector<int> A(n), B(n);
    
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
    }
    
    unordered_set<int> b_set;
    for (int i = 0; i < n; ++i) {
        cin >> B[i];
        b_set.insert(B[i]);
    }
    
    int ans = 0;
    for (int num : A) {
        if (b_set.find(x - num) != b_set.end()) {
            ans = 1;
            break;
        }
    }
    
    cout << ans << endl;
    return 0;
}

3. 排序+双指针（空间优化） #

如果不想用额外的空间，可以用排序加双指针的方法：

1. 把数组A升序排序，数组B降序排序；
2. 初始化两个指针i（指向A的开头）和j（指向B的开头）；
3. 计算当前和sum = A[i] + B[j]：
   • 如果sum等于X，直接返回1；
   • 如果sum小于X，说明需要更大的数，把i右移（A是升序，下一个数更大）；
   • 如果sum大于X，说明需要更小的数，把j右移（B是降序，下一个数更小）；
4. 遍历完所有元素还没找到的话，返回0。

这个方法的时间复杂度是O(n log n)（主要来自排序），空间复杂度是O(1)（如果用原地排序的话），适合对空间要求较高的场景。

Python示例代码：

n, x = map(int, input().split())
A = sorted(map(int, input().split()))
B = sorted(map(int, input().split()), reverse=True)

i = j = 0
result = 0
while i < n and j < n:
    current_sum = A[i] + B[j]
    if current_sum == x:
        result = 1
        break
    elif current_sum < x:
        i += 1
    else:
        j += 1
print(result)

内容的提问来源于stack exchange，提问作者Andrei_Buslik