题意给我们一个长度为n4n2e5的数组a0a[i]2.5e6然后需要我们判断是否存在四个下标x,y,z,w,使得a[x]a[y]a[z]a[w],存在则输出yes否则no.题解简单数论其实这题就是两个for循环就可解决看似n的数据范围为2e5两个for循环一般来说肯定是超时的然而注意看a[i]的数据范围只有2.5e6那么对于2e5个数而言当n的数据量比较大的时候例如接近2e5时那么在考虑a[i]的范围这个时候就必然会出现接下来的一种会多种情况存在四个a[i]相同存在四个及以上个a[i]存在顺序关系例如1,2,3,4那么1423或者1,2,6,7这种1726那么其实就跑不满两个for复杂度也就其实达不到 O(n 2 n^{2}n2)这题的数据量给的十分巧妙。C. Going Home传送门#includebits/stdc.husingnamespacestd;constintMAXN200005;intn,a[MAXN];pairint,intb[30*MAXN];intmain(){ios::sync_with_stdio(false);cinn;for(inti1;in;i){cina[i];}for(inti1;in;i){for(intji1;jn;j){intsuma[i]a[j];if(!b[sum].first){b[sum]{i,j};continue;}elseif(ib[sum].first||jb[sum].first||ib[sum].second||jb[sum].second)continue;coutYES\n;couti j b[sum].first b[sum].second\n;return0;}}coutNO\n;return0;}
