题解：CF988C Equal Sums

· · 题解

终于发布了第一篇题解

CF988C 题解

题目传送门

题目要求删除一个数，那么，我们可以在每次输入新序列时删除一个数进行求和，再查询以前有没有这个数值，如果有，直接输出结果并结束程序。

考虑“查询”，可以维护一个 map ：

map<int,pair<int,int> > mp;

代表：

map<得到的值,pair<第几个数列，删除的第几个数> >

那么求和怎么办呢？

可以先算出总和，再减去要删除的数。

代码：

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
long long a[200010];//貌似可以用int
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    map<int,pair<int,int> > mp;
    int k;
    cin >> k;
    for(int i=1;i<=k;i++){
        int n;
        cin >> n;
        long long sum=0;
        for(int j=1;j<=n;j++){
            cin >> a[j];
            sum+=a[j];//求总和
        }
        //cout << sum << " ";
        for(int j=1;j<=n;j++){
            long long presum=sum-a[j];//求删除数后的总和

            //cout << presum << " ";
            if(mp.count(presum)&&mp[presum].first!=i){//如果已经保存过这个和且不是同一个数列
                cout << "YES" << endl;
                cout << mp[presum].first << " " << mp[presum].second << endl;
                cout << i << " " << j;
                return 0;//直接结束程序
            }
            else{//向map中添加新的结果
                mp[presum]={i,j};
            }
        }
        //cout << endl;
    }
    cout << "NO";//如果一直没有判断到，就不会结束程序，无解
    return 0;
}

通过记录