T1：

　　《论语文素养限制OI水平》：考场没读懂题意于是暴力都没打

考虑首先O(n^2)Bfs是显然的，考虑问题在于对于每个点会被多次转移，

于是考虑如何使每个点只被转移一次，一个直接的思路为记录当前已经转移过的点

又考虑到对于每个点只能转移到一段区间内的点，于是需要快速求解距离当前点距离在一定范围内的点

于是采用set进行维护，在记录可转移点的同时可以通过lower_bound查找合法点

接下来是具体实现细节，发现对于给定的k，每个点只会转移到一类奇偶性点上，于是两个set分别维护即可

需要注意的是，使用STL迭代器时一定需要注意边界问题，即在for循环位置，先用一个迭代器记录当前迭代器位置

在当前迭代器位置自增或自减后再进行删除，直接删除存在显然的逻辑错误，会造成段错误

一种错误方式为直接在当前点分别向左右存在距离小于等于k的合法位置，可以发现最劣复杂度为O(nklogn)

错误点在于判断也需要遍历到该点，为保证复杂度，必须保证每个点仅被操作一次，因此需要直接确定可行区间，在可行区间内进行遍历

这样保证每个点实际操作次数为1

代码总时间复杂度为O(nlogn)

代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define I int
 4 #define C char
 5 #define B bool
 6 const I N = 1e5 + 3;
 7 I n,k,m,s,ans[N];
 8 B ban[N];
 9 queue <I> q;
10 set <I> t[2];
11 set <I> :: iterator p;
12 inline I read() {
13     I x(0),y(1); C z(getchar());
14     while (!isdigit(z)) { if (z == '-') y = -1; z = getchar(); }
15     while ( isdigit(z))  x = x * 10 + (z ^ 48), z = getchar();
16     return x * y;
17 }
18 signed main () {
19     n = read(), k = read(), m = read(), s = read(); for (I i(1);i <= m; ++ i) ban[read()] = 1;
20     for (I i(1);i <= n; ++ i) if (!ban[i]) t[i & 1].insert (i);
21     memset (ans,-1,sizeof ans); ans[s] = 0, q.push (s), t[s & 1].erase (t[s & 1].find (s)); 
22     while (!q.empty ()) {
23         I x(q.front ()),typ(x & 1),MI(max (k + 1 - x,x - k)),MA (min (n * 2 - x - k + 1,x + k)); q.pop (); if (!(k & 1)) typ ^= 1;
24         for (set <I> :: iterator i(t[typ].lower_bound (MI));i != t[typ].end () && *i <= MA;p = i, i ++ ,t[typ].erase (p)) 
25             ans[*i] = ans[x] + 1, q.push (*i);
26     }
27     for (I i(1);i <= n; ++ i) printf ("%d ",ans[i]);
28 }

View Code

存在时间复杂度为O(n)的链表优化做法

T2：

　　一个很显然的容斥然而没有设计出来，

首先直接思路为发现每个位置所能填放的最大的数为min (x[i],y[j])

那么直接将所有位置相乘即可，然而发现题目的一个限制为每行每列至少存在一个位置满足条件

那么显然需要容斥出不合法的情况，

考虑一个很显然的性质为将x，y数组交换顺序（即排序）不会影响问题的答案，

考虑将x，y排序进行处理（目的是有序便于处理），

考虑发现在排序后，每种值的控制范围为矩形或L形（根据定义在排序后的方阵上模拟即可）

并且发现，大值的方案显然不受小值的方案影响

于是考虑将问题分块进行，由大到小逐渐计算方案数，最终相乘即可

于是考虑如何计算矩形和L形的实际贡献

考虑L形实际上可以由矩形相减得到，于是设对于a*b矩形减去(a-c)*(b-d)矩形的贡献

显然的容斥设f[i]为在c*d的矩阵中至少存在i行不满足条件（每一列都满足情况）的情况

（考场上由于直接设计i行j列不满足情况而复杂度爆炸，考虑题解状态压缩的做法显然更优）

有发现对于每一列方案数相同，于是在容斥时只需要考虑每一行方案幂上列数即可

简单的组合数学，注意减去所有行都不合法的方案数即可。

代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define I long long
 4 #define C char
 5 #define B bool
 6 const I N = 1e5 + 3;
 7 const I mod = 1e9 + 7;
 8 I n,a[N],b[N],J[N],Y[N],ans(1);
 9 inline I read() {
10     I x(0),y(1); C z(getchar());
11     while (!isdigit(z)) { if (z == '-') y = -1; z = getchar(); }
12     while ( isdigit(z))  x = x * 10 + (z ^ 48), z = getchar();
13     return x * y;
14 }
15 inline B com (I a,I b) { return a > b; }
16 inline I fp (I a,I b) { I ans(1);
17     for (; b ;b >>= 1, a = a * a % mod)
18         if (b & 1) ans = ans * a % mod;
19     return ans;
20 }   
21 inline I O (I n,I m) {
22     return J[n] * Y[m] % mod * Y[n - m] % mod;
23 }
24 inline I Figure (I a,I b,I c,I d,I s) { I sum(0);
25     for (I i(0);i <= c; ++ i) (sum += (i & 1 ? -1 : 1) * O(c,i) * fp(s,b * i) % mod * fp(fp(s + 1,a - i) - fp(s,a - i),d) % mod * fp(fp(s + 1,c - i),b - d) % mod) %= mod;
26     return sum;
27 }
28 signed main () {
29     n = read(); J[0] = Y[0] = 1; I p1(1),p2(1);
30     for (I i(1);i <= n; ++ i) a[i] = read();
31     for (I i(1);i <= n; ++ i) b[i] = read();
32     sort (a + 1,a + n + 1,com), sort (b + 1,b + n + 1,com);
33     for (I i(1);i <= n; ++ i) J[i] = J[i - 1] * i % mod; Y[n] = fp (J[n],mod - 2);
34     for (I i(n - 1); i; -- i) Y[i] = Y[i + 1] * (i + 1) % mod;
35     while (p1 <= n || p2 <= n) {
36         I num(max (a[p1],b[p2])),cnt1(0),cnt2(0);
37         while (p1 <= n && a[p1] == num) p1 ++ , cnt1 ++ ;
38         while (p2 <= n && b[p2] == num) p2 ++ , cnt2 ++ ;
39         ans = ans * Figure (p1 - 1,p2 - 1,cnt1,cnt2,num) % mod;
40     }
41     printf ("%lld\n",(ans + mod) % mod);
42 }

View Code