danihao123's Blog

我zzs就算掉光rating，R2爆炸，也不会做你们半道构造题！

啊构造题真好玩（一转）。

不妨钦定\(A\)中所有元素的和不大于\(B\)的。然后把两个集合按照任意顺序搞成一个序列，然后求出两者的前缀和\(SA\)和\(SB\)。

考虑对于0...n的\(SA_i\)，找出\(SB\)中不大于他的数中最大的一个（不妨设为\(SB_j\)），可以发现有\(0\leq SA_i - SB_j\leq n - 1\)（不然\(j\)还能再大）。然后发现：我们处理的\(i\)和\(j\)的数对有\(n + 1\)组，但是\(SA_i - SB_j\)的取值却只有N种！也就是说一定存在\(i\neq i'\)且\(j\neq j'\)满足\(SA_i - SB_j = SA_{i'} - SB_{j'}\)。

我们找出两对这样的数对，移一下项就可以构造一组解了。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <vector>
using ll = long long;
using pii = std::pair<int, int>;
int n;
void gen_S(int *arr, ll *S) {
  S[0] = 0LL;
  for(int i = 1; i <= n; i ++) {
    S[i] = (S[i - 1] + (ll(arr[i])));
  }
}

const int maxn = 1000005;
std::vector<pii> cs[maxn];
int main() {
  scanf("%d", &n);
  int *A = (int*)calloc(n + 1, sizeof(int));
  int *B = (int*)calloc(n + 1, sizeof(int));
  ll sum_A = 0LL, sum_B = 0LL;
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &A[i]); sum_A += A[i];
  }
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &B[i]); sum_B += B[i];
  }
  bool flip = false;
  if(sum_A > sum_B) {
    flip = true;
    std::swap(A, B);
    std::swap(sum_A, sum_B);
  }
  ll *SA = (ll*)calloc(n + 1, sizeof(ll));;
  ll *SB = (ll*)calloc(n + 1, sizeof(ll));;
  gen_S(A, SA); gen_S(B, SB);
  for(int i = 0; i <= n; i ++) {
    int j = std::upper_bound(SB, SB + n + 1, SA[i]) - SB - 1;
    ll val = SA[i] - SB[j];
    cs[val].push_back(std::make_pair(i, j));
  }
  int l1, r1, l2, r2;
  for(int i = 0; i < n; i ++) {
    if(cs[i].size() > 1) {
      int i1 = cs[i][0].first;
      int j1 = cs[i][0].second;
      int i2 = cs[i][1].first;
      int j2 = cs[i][1].second;
      if(i1 > i2) {
        std::swap(i1, i2);
        std::swap(j1, j2);
      }
      l1 = i1; r1 = i2;
      l2 = j1; r2 = j2;
      break;
    }
  }
  if(flip) {
    std::swap(l1, l2);
    std::swap(r1, r2);
  }
  printf("%d\n", r1 - l1);
  for(int i = l1 + 1; i <= r1; i ++) {
    if(i > l1 + 1) putchar(' ');
    printf("%d", i);
  }
  putchar('\n');
  printf("%d\n", r2 - l2);
  for(int i = l2 + 1; i <= r2; i ++) {
    if(i > l2 + 1) putchar(' ');
    printf("%d", i);
  }
  putchar('\n');
  free(A); free(B);
  free(SA); free(SB);
  return 0;
}

很好的数学题啊……

一看就应该想起来构造，对于[tex]n[/tex]为奇数的情况，我们可以假设[tex]n[/tex]为最小数。由此，可以构造出来[tex](n,(n^{2}-1)/2,(n^{2}-1)/2+1)[/tex]一组勾股数（具体证明自己证去）。

[tex]n[/tex]为偶数时呢？化成奇数做？不好，因为这样会出现对于[tex]n^{a} (a>1)[/tex]一类数会无能为力。偶数也可构造：[tex](n,(n/2)^{2}-1,(n/2)^{2}+1)[/tex]。

然后做就行了……

#include <iostream>
using namespace std;
int main(){
    long long n,temp;
    cin>>n;
    if(n<=2){
        cout<<-1<<endl;
        return 0;
    }
    if(1&n){
        temp=n*n-1;
        temp/=2;
        cout<<temp<<' '<<(temp+1)<<endl;
    }else{
        temp=n/2;
        cout<<temp*temp+1<<' '<<temp*temp-1<<endl;
    }
    return 0;
}

现在才明白，我数论其实不好……

这题也不怎么难，需要一点灵感构造

代码：