T1

数据点1：枚举每一个位置并依次向两个对角线方向扩展即可 数据点2：注意到一条直线可以被描述为 x+y=p, 另一条直线可以被描述为 x-y=p。所以只用存下来 x+y 和 x-y 等于某一个值最大有多少点即可，最后将最大值相加。需要注意的是如果站立位置有气球的话，会重复算两边，用一个二维数组存一下当前节点是否有气球即可。

数据点3：不用二维数组判断当前位置是否有气球，改用map或者sort的方法

数据点4：用 map 存 x+y 和 x-y 的信息即可。

• #include<bits/stdc++.h>
  using namespace std;
  
  typedef unsigned long long ull;
  typedef long long ll;
  typedef long double db;
  typedef pair<int,int> pii;
  typedef pair<ll,ll> pll;
  #define fi first
  #define se second
  #define endl '\n'
  
  
  const int N = 2e5+5;
  
  int n,m;
  map<int,int> m1,m2;
  map<pii,int> m3;
  signed main(){
  freopen("cross.in","r",stdin);
  freopen("cross.out","w",stdout);
      ios::sync_with_stdio(false); cin.tie(0u); cout.tie(0u);
      cin >> n >> m;
      for (int i = 1; i <= n; i++){
          int x,y;
          cin >> x >> y;
          if (m1.count(x+y)) m1[x+y]++;
          else m1[x+y] = 1;
          if (m2.count(x-y)) m2[x-y]++;
          else m2[x-y] = 1;
          m3[{x,y}] = 1;
      }
      for (int i = 1; i <= m; i++){
          int x, y;
          cin >> x >> y;
          int ans = m1[x+y]+m2[x-y];
          if (m3.count({x,y})) ans--;
          cout << ans << endl;
      }
      return 0;
  }
  

T2

m 很大，最终购买并装修完所有房屋是最优秀的。 观察特殊性质 A：贪心，直接把所有购买和装修的花费时间拿出来排序，依次购买或装修即可 全部数据：依旧贪心，发现如果 $a_{i,0} > a_{i,1}$，那么肯定购买完这个房子立刻装修，所以拿平均数去排序即可

• #include<bits/stdc++.h>
  
  using namespace std;
  
  #define fi first
  #define se second
  typedef long long ll;
  typedef pair<int, int> pii;
  
  ll n, m;
  vector<pii> v;
  signed main() {
  	// freopen("a.in","r",stdin);
  	// freopen("a.out","w",stdout);
  	ios::sync_with_stdio(false);
  	cin.tie(0);
  	cout.tie(0);
  	cin >> n >> m;
  	for (int i = 1; i <= n; i++) {
  		int a, b;
  		cin >> a >> b;
  		if (a < b) {
  			v.push_back({a, -1});
  			v.push_back({b, -1});
  		} else {
  			v.push_back({a, b});
  		}
  	}
  	sort(v.begin(), v.end(), [&](pii a, pii b) {
  		int ta = a.fi + ((a.se == -1) ? a.fi : a.se);
  		int tb = b.fi + ((b.se == -1) ? b.fi : b.se);
  		return ta < tb;
  	});
  	ll ans = m * n * 2, sum = 0;
  	for (int i = 0; i < v.size(); i++) {
  		auto cal = [&](int t) {
  			sum += t;
  			ans -= sum;
  		};
  		if (v[i].se == -1) {
  			cal(v[i].fi);
  		} else {
  			cal(v[i].fi);
  			cal(v[i].se);
  		}
  	}
  	cout << ans << endl;
  
  	return 0;
  }
  

T3

n $\le$ 3分类讨论即可

观察任意两名同学的起点，称起点在左边的为A，右边的为B，发现其可以交友的充要条件是他们的终点B在A的左侧。

将其扩展至很多同学，发现一些同学可以组成朋友圈的充要条件是，将同学按起点从左向右排序，他们的终点从右向左。

于是就设计数组 $p[i]$，代表 $A[i]$ 在 $B$ 中的出现位置，原题转化为求 $p$ 的最长不上升子序列。

• #include<bits/stdc++.h>
  using namespace std;
  
  typedef unsigned long long ull;
  typedef long long ll;
  typedef long double db;
  typedef pair<int, int> pii;
  typedef pair<ll, ll> pll;
  #define fi first
  #define se second
  
  
  const int N = 1e5+5;
  
  int n, a[N], b[N], f[N], x;
  signed main() {
  	//freopen("dance.in", "r", stdin);
  	//freopen("dance.out", "w", stdout);
  	ios::sync_with_stdio(false);
  	cin.tie(0u);
  	cout.tie(0u);
  	cin >> n;
  	memset(f, 0x3f3f3f3f, sizeof(f));
  	for (int i = 1; i <= n; i++) {
  		cin >> x;
  		a[x] = i;
  	}
  	for (int i = 1; i <= n; i++) {
  		cin >> x;
  		b[n - i + 1] = a[x];
  	}
  	for (int i = 1; i <= n; i++) f[lower_bound(f + 1, f + n + 1, b[i]) - f] = b[i];
  	cout << lower_bound(f + 1, f + n + 1, f[0]) - f - 1 << endl;
  	return 0;
  }
  

T4

特殊性质：如果前 n 回合都是真话，即所有花色牌数已经固定了下来，那么可以推导出：当前话一定为假意味着当前花色牌数已经不够用；当前话一定为真意味着其他花色剩余的牌都不够这一次扣置的牌，而且当前花色牌数够用。

$n \le 30$ 如果前n回合出现假话，可以设计dp暴力模拟出当前牌数在四个花色的分布情况。设 $f[t][i][j][k][l]$ 为第 t 回合后，有没有可能四种花色牌数量分别为 $i,j,k,l$。通过这样的方法将所有花色牌数固定。

$n \le 80$ 可以发现第 $t$ 回合时，所扣置牌数总和是一定的，所以可以只用枚举三个花色的牌数即可

T5

本题考察了图论的相关知识。

30pts

直接爆搜每次的情况并进行去重，时间复杂度为 $O(n!)$，后续会给出具体证明。

+30pts

令初始的异或和为 $x$，拿在手中，相当于每次用手中的数把 $a$ 中的一个值顶掉，然后把原来的值拿在手里，这也间接说明了状态数是 $n!$ 量级的。

此档分会发现 $a_i$ 和所有 $a_i$ 异或后的权值两两不同，我们考虑一个过程，用 $x$ 替换了 $a_p$，然后用 $a_p$ 替换了 $a_q$，循环下去。

其实最终一定是要用 $b_i$ 替换 $a_i$ 的，而上面的过程又是从 $x$ 出发走了一条路，按如上方式建图找出环的个数即可统计答案。

100pts

我们从 $b_i$ 向 $a_i$ 连边（不同位置上相同的数值对应同一个点），然后尝试从 $x$ 出发遍历每条边。

注意如果图是一个包含 $x$ 的连通块，则一定可以找到一条欧拉路径（不一定是回路）覆盖所有边。

如果图不连通，或 $x$ 不在连通块内（$x$ 是孤立点），则答案就是边数再加上连通块数再减去 $1$（如果 $x$ 是孤立点就不用减 $1$）。

时间复杂度为 $O(n)$。

• #include<bits/stdc++.h>
  using namespace std;
  
  typedef unsigned long long ull;
  typedef long long ll;
  typedef long double db;
  typedef pair<int,int> pii;
  typedef pair<ll,ll> pll;
  #define fi first
  #define se second
  #define endl '\n'
  const int N = 81;
  
  int A,B,C,D,n,m;
  bool f[2][N][N][N][N];
  signed main(){
      // freopen("game2.in","r",stdin);
      // freopen("game10.out","w",stdout);
      ios::sync_with_stdio(false); cin.tie(0u); cout.tie(0u);
      cin >> A >> B >> C >> D;
      cin >> n;
      f[0][0][0][0][0] = 1;
      int tot = 0;
      for (int i = 1; i <= n; i++){
          char o,o2;
          int x;
          cin >> o >> x >> o2;
          tot += x;
          for (int d = 0; d <= A; d++){
              for (int c = 0; c <= B; c++){
                  for (int h = 0; h <= C; h++){
                      int s = tot-d-c-h;
                      f[i%2][d][c][h][s] = 0;
                  }
              }
          }
          for (int d = 0; d <= A; d++){
              for (int c = 0; c <= B; c++){
                  for (int h = 0; h <= C; h++){
                      int s = tot-d-c-h;
                      if (s < 0 || s > D) continue;
                      if ((o == 'D'&& o2 == 'T') || (o != 'D'&& o2 == 'F')) if (d >= x) f[i%2][d][c][h][s] |= f[(i&1)^1][d-x][c][h][s];
                      if ((o == 'C'&& o2 == 'T') || (o != 'C'&& o2 == 'F')) if (c >= x) f[i%2][d][c][h][s]  |= f[(i&1)^1][d][c-x][h][s];
                      if ((o == 'H'&& o2 == 'T') || (o != 'H'&& o2 == 'F')) if (h >= x) f[i%2][d][c][h][s] |=  f[(i&1)^1][d][c][h-x][s];
                      if ((o == 'S'&& o2 == 'T') || (o != 'S'&& o2 == 'F')) if (s >= x) f[i%2][d][c][h][s] |= f[(i&1)^1][d][c][h][s-x];
                  }
              }
          }
      }
      // cout << f[0][40][60][20][80] << endl;
      cin >> m;
      for (int i = 1; i <= m; i++){
          char o;
          int x;
          cin >> o >> x;
          int if0 = 1, if1 = 1;
          int noo = 1;
          for (int d = 0; d <= A; d++){
              for (int c = 0; c <= B; c++){
                  for (int h = 0; h <= C; h++){
                      int s = tot-d-c-h;
                      if (d > A-x && c > B-x && h > C-x && s > D-x) continue;
                      if (f[n%2][d][c][h][s]){
                          noo = 0;
                          if (o == 'D'){
                              if (d <= A-x) if0 = 0;
                              if (d <= A-x && c > B-x && h > C-x && s > D-x);
                              else if1 = 0;
                          }
                          if (o == 'C'){
                              if (c <= B-x) if0 = 0;
                              if (d > A-x && c <= B-x && h > C-x && s > D-x);
                              else if1 = 0;
                          }
                          if (o == 'H'){
                              if (h <= C-x) if0 = 0;
                              if (d > A-x && c > B-x && h <= C-x && s > D-x);
                              else if1 = 0;
                          }
                          if (o == 'S'){
                              if (s <= D-x) if0 = 0;
                              if (d > A-x && c > B-x && h > C-x && s <= D-x);
                              else if1 = 0;
                          }
                      }
                      
                  }
              }
          } 
          if (noo == 1) cout << "ERROR" << endl;
          else if (if0) cout << "F" << endl;
          else if (if1) cout << 'T' << endl;
          else cout << "NG" << endl;
      }
      return 0;
  }