1024赛后总结

## 1.成绩
100+60+0+40=200  
最后一场了啊啊啊啊啊啊啊啊：(
## 2.做题过程
### T1
因为$n-1$很大，所以想到真正产生贡献的截面应该会很少。考虑枚举$z$（也就是枚举截面）。如果当前的截面跟上一个一样，就可以答案直接加上一个的贡献，用一个零时变量记录一下上一个的就可以了；否则如果当前截面的长方体数$<n-1$就可以直接$continue$了；否则（这种情况应该非常非常非常少）相当于把长方体变成了二维的矩形。  
考虑怎么算一个截面的贡献。如果截面上的矩形数$=n-1$就可以用$O(n)$的时间复杂度算每个矩形都覆盖到的那个矩形的面积$=(min_{i=1}^{n}(x1_i)-max_{i=1}^{n}(x0_i)+1)×(min_{i=1}^{n}(y1_i)-max_{i=1}^{n}(y0_i)+1)$；否则再利用前面的想法枚举$y$。  
因为坐标可能是负的，所以输入的时候偏移一下，加上$1e6$就可以了  
其实不用那么麻烦，枚举删哪个矩形，累加一下贡献再容斥一下，减掉$n-1$个$n$个矩形的交就可以了。。赛时都想到了，以为是错的就写了上面那个90多行的。。。（关键还调了30分钟）wssb啊啊啊啊我sm了！！：(
```cpp
#include <bits/stdc++.h>
#define LL long long

using namespace std;

LL n, f[2000010][2], ans, ff[2000010];
int mxz, mxyy, mxxx;
vector <int> v[2000010];
struct cube {
  int x0, y0, z0, x1, y1, z1;
} a[100010];

int main () {
  freopen("cube.in", "r", stdin);
  freopen("cube.out", "w", stdout);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i].x0 >> a[i].y0 >> a[i].z0 >> a[i].x1 >> a[i].y1 >> a[i].z1;
    a[i].x0 += 1e6;
    a[i].y0 += 1e6;
    a[i].z0 += 1e6;
    a[i].x1 += 1e6;
    a[i].y1 += 1e6;
    a[i].z1 += 1e6;
    f[a[i].z0][0]++;
    f[a[i].z1 + 1][1]++;
    v[a[i].y0].emplace_back(i);
    v[a[i].y1 + 1].emplace_back(-i);
    mxz = max(mxz, a[i].z1);
    mxyy = max(mxyy, a[i].y1);
    mxxx = max(mxxx, a[i].x1);
  }
  LL tmp = 0, sum = 0;
  for (int i = 0; i <= mxz; i++) {
    sum += f[i][0];
    sum -= f[i][1];
    if (sum < n - 1) {
      tmp = 0;
      continue;
    }
    if (f[i][0] == 0 && f[i][1] == 0) {
      ans += tmp;
//      cout << ans << "\n";
      continue;
    }
    if (sum == n - 1) {
      int mxx = 0, mxy = 0, mnx = 1e9, mny = 1e9;
      for (int j = 1; j <= n; j++) {
        if (a[j].z0 > i || a[j].z1 < i) continue;
        mxx = max(mxx, a[j].x0);
        mxy = max(mxy, a[j].y0);
        mnx = min(mnx, a[j].x1);
        mny = min(mny, a[j].y1); 
      }
      tmp = max(0ll, 1ll * (mnx - mxx + 1) * (mny - mxy + 1));
      ans += tmp;
      continue;
    }
    tmp = 0;
    int s = 0, tt = 0;
    for (int j = 1; j <= mxyy; j++) {
      for (auto k : v[j]) {
        if (k < 0) {
          s--;
        } else {
          s++;
        }
        ff[a[abs(k)].x0] += (k > 0 ? 1 : -1);
        ff[a[abs(k)].x1 + 1] += (k > 0 ? -1 : 1);
      }
      if (v[j].size() == 0) {
        tmp += tt;
        continue;
      }
      if (s < n - 1) {
        tt = 0;
        continue;
      }
      int fuck = 0;
      tt = 0;
      for (int k = 1; k <= mxxx; k++) {
        fuck += ff[k];
        if (fuck >= n - 1) {
          tt++;
        }
      }
      tmp += tt;
    }
    ans += tmp;
//    cout << ans << "\n";
  }
  cout << ans;
  return 0;
}
```
### T2
因为三条边$a$、$b$、$c$（$a\le b\le c$）能构成三角形的条件是$a+b>c$。所以就可以：暴力，启动！对查询的区间排个序，再枚举$c$，喜提60分的好成绩：）
```cpp
#include <bits/stdc++.h>

using namespace std;

int n, q, a[100010], b[100010];

int main () {
  freopen("triangle.in", "r", stdin);
  freopen("triangle.out", "w", stdout);
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  while (q--) {
    int l, r;
    cin >> l >> r;
    for (int i = l; i <= r; i++) {
      b[1 + i - l] = a[i];
    }
    sort(b + 1, b + r - l + 2);
    int f = 0;
    for (int j = 3; j <= r - l + 1 && !f; j++) {
      if (b[j] < b[j - 1] + b[j - 2]) {
        f = 1;
      }
    }
    if (f) {
      cout << "Yes\n";
    } else {
      cout << "No\n";
    }
  }
  return 0;
}
```
### T3
纯暴力就不讲了
### T4
写了一个错的贪心，因为$n\le1000$所以暴力建图，然后把权值从大到小排序，大的尽量多拉点进来，拿了40分
```cpp
#include <bits/stdc++.h>

using namespace std;

int n, a[1010], ans, mxa, vis[1010];
vector <int> v[1010];

bool cmp (int x, int y) {
  return x > y;
}

int main () {
  freopen("graph.in", "r", stdin);
  freopen("graph.out", "w", stdout);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  sort(a + 1, a + n + 1, cmp);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j < i; j++) {
      if ((a[i] & a[j]) == 0) {
        v[i].emplace_back(j);
        v[j].emplace_back(i);
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    if (!vis[i]) {
      vis[i] = 1;
      int mx = 0;
      for (auto j : v[i]) {
        if (vis[j]) {
          mx = max(mx, a[j]);
        } else {
          vis[j] = 1;
          ans += a[i];
        }
      }
      ans += mx;
    }
  }
  cout << ans;
  return 0;
}
```
## 3.总结
### 1.心态
一直都很崩，老师说是信心赛要ak，但我写不出题
### 2.做题
T1想复杂了
### 3.时间规划
T1时间太多了