本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-29 20:24:02

过马路

假如一个人 $i$ 和一个车 $j$ 在 $T$ 相撞，有 $(T,a_i)=(b_j,T)$。

所以此时一定有 $a_i=b_j=T$，又由于 $a_i,b_j$ 两两不同，所以一个人仅可能和一辆车相撞，对于一组人与车，只要删去其中任何一个即可。

所以需要维护一个查询一个数是否在一个集合中出现的数据结构，使用 $\text{std::set}$ 即可。

时间复杂度 $O(n\log n)$。

参考代码：liuzixuan

#include <bits\/stdc++.h>
#define endl '\n'
using namespace std;
const int N=1e5+10;
unordered_map<int,int> mp;
int n,m,r,c;
int cnt;
int t;
int x;
signed main()
{
\/\/	freopen("cece3.in","r",stdin);
\/\/    freopen("cece.out","w",stdout);
    cin>>t;
    while(t--)
    {
        cin>>n>>m>>r>>c;
        mp.clear();
        cnt=0;
        for(int i=1;i<=n;i++)
        {
            cin>>x;
            mp[x]++;
        }
        for(int i=1;i<=m;i++)
        {
            cin>>x;
            mp[x]++;
        }
        for(auto y:mp)
        {
            if(y.second==2)
            {
                cnt++;
            }
        }
        cout<<cnt<<endl;
    }
    return 0;
}

子序列

算法一：$n\le12$，$q\le100$

我会状压！

预处理出每个长度不超过 $n$ 的 01 串的答案。具体来说，枚举一个子序列并判断是否合法，如果合法则把它加入答案集合。

时间复杂度 $\text O(2^n+q)$。

算法二：$n\le100$，$q\le100$

我会 DP！

对于每个询问，设 $f_{i,j}$ 表示区间匹配到 $i$，在原串上子序列匹配到 $j$ 是否可行，转移类似 LCS。

时间复杂度 $\text O(n^2q)$

算法三：$n\le1000$，$q\le1000$

我会优秀地枚举！

对于每个询问，考虑枚举一个子序列没选择的位置 $i$，预处理出区间 $[l,r]$ 在 $s_{1\dots i-1}$ 作为子序列出现的最长前缀长度 $pre_i$ 和在 $s_{i+1\dots n}$ 作为子序列出现的最长后缀长度 $suf_i$，那么有答案等价于 $pre_i+suf_i\ge r-l+1$ 且 $pre_i,suf_i>0$。

时间复杂度 $\text O(nq)$

算法四：$n\le1\times10^5$，$q\le1\times10^5$

我会找性质！

答案是 Yes 当且仅当下面两种情况至少满足一个：

1. $s_l$ 第一次出现不是在 $l$。

2. $s_r$ 最后一次出现不是在 $r$。

证明：

• 必要性：

以情况 1. 为例，选择 $s_l$ 第一次出现的位置和 $s_{l+1\dots r}$ 即可，情况 2. 类似。

• 充分性：考虑它的逆否命题。

假设 $s_l$ 第一次出现在 $l$ 且 $s_r$ 最后一次出现在 $r$。

仍然考虑算法三中的做法，枚举一个子序列没选择的位置 $i$。由于 $s_l$ 第一次出现在 $l$，所以 $p_1\ge l$，因此 $pre_i\le \max\{i-l,0\}$。同理可得 $suf_i\le\max\{r-i,0\}$。

因为要求 $pre_i,suf_i>0$，所以 $l<i<r$，此时 $pre_i+suf_i\le (i-l)+(r-i)=r-l<r-l+1$，因此无解，证毕。

本题时间复杂度 $\text O(n+q)$。

参考代码：guoweifeng

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<map>
#define int long long
using namespace std;
const int N=1e5+10;
const int M=20+10;
const int maxs=1e9;
const int mins=-1e9;
int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){ if(ch=='-') w=-1; ch=getchar();}
	while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar();}
	return s*w;
}
int T;
int n,q;
char s[N];
int st[2],e[2];
signed main()
{
	T=read();
	while(T--)
	{
		n=read();
		q=read();
		cin>>s+1;
		st[0]=maxs;\/\/0在串中第一次出现的位置 
		st[1]=maxs;
		e[0]=0;\/\/在串中最后一次出现的位置 
		e[1]=0;
		for(int i=1;i<=n;i++)
		{
			if(st[0]==maxs&&s[i]=='0')\/\/更新0出现的位置 
				st[0]=i;
			if(st[1]==maxs&&s[i]=='1')
				st[1]=i;
		}
		for(int i=n;i>=1;i--)
		{
			if(e[0]==0&&s[i]=='0')
				e[0]=i;
			if(e[1]==0&&s[i]=='1')
				e[1]=i;
		}
		while(q--)
		{
			int l,r;
			l=read();
			r=read();
			if(l>st[s[l]-'0']||r<e[s[r]-'0'])\/\/左端点之前或右端点之后。 
				cout<<"Yes"<<"\n";
			else
				cout<<"No"<<"\n";
		}
	}
	return 0;
}

烦恼

本题由于同时有两个变量，如果同时考虑，过于复杂。

1. 小Z本身在动，每秒可以走S步。

2. 狗仔每秒同时向4个方向在动

其实样例解释也是在提示我们，我们可以把停留若干秒后再去判定是否到家比较容易，所以，我们可以把计算问题转换为判定问题。

由于小Z和狗仔的步长不一样，同时处理不太方便。我们可以用BFS预处理出每一个格子被狗仔占领的最早时间$t_{i,j}$,那么我们只需要保证小Z到达每一个格子的时间严格小于被狗仔占领的最早时间$t_{i,j}$即可。

小Z的步长有 $S$ ,每一秒可以往外走 $S$ 步，其实我们也可以用BFS解决，BFS处理出小Z到达每一个格子的曼哈顿距离(最小步数),设为 $step$ ,那么就可以算出来小Z到达这个格子所需的时间为 $step/S$ ,设这个时间为 $t$。

• 其实，我们可以贪心的来看，小Z每一秒一定是走S步的，走得快一定比走得慢要好，除非离家已经不足S步。

那么,我们只需要保证小Z到达这个格子的时间t加上小Z在原地吃饭停留的时间x严格小于ti,j即可。我们只需要不断地扩展这个合法的格子直到回到家或者没有状态可以更新(只剩下私人住宅)。

计算时间复杂度

• 我们预处理狗仔队到达每一个格子的时间，只需要把狗仔队起点全部入队做一次BFS,为 $O(n^2)$

• 然后我们枚举小Z停留的时间 $x$,显然停留时间范围在 $[0,n]$ 中间

• 总时间复杂度为 $O(n^4)$,无法通过 $n≤800$ 的数据。

但是，我们很容易发现，该问题具有單调性，可以二分，如果停留 $x$ 秒可以到家，那么停留小于 $x$ 秒一样可以可以到家，如果 $x$ 秒不能到家，那么大于 $x$ 秒也不能到家。

参考代码

#include <bits\/stdc++.h>
#define mk make_pair
#define pii pair<int, int>
#define fr first
#define sc second
using namespace std;

int sx, sy, ex, ey, n, s;
int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };
char m[1001][1001];
int bk[1001][1001], vis[1001][1001];

bool checkbfs(int x, int y) {
    if (x < 1 || x > n || y < 1 || y > n)
        return false;
    if (m[x][y] == 'T' || m[x][y] == 'D')
        return false;
    if (bk[x][y] != -1)
        return false;
    return true;
}
bool check1(int x, int y, int step) {
    if (x < 1 || x > n || y < 1 || y > n)
        return false;
    if (step >= bk[x][y] * s && m[x][y] != 'D')
        return false;
    if (vis[x][y])
        return false;
    return true;
}

bool check(int t) {
    queue<pair<pii, int> > q;
    memset(vis, 0, sizeof(vis));
    q.push(mk(mk(sx, sy), t * s));
    vis[sx][sy] = 1;
    while (!q.empty()) {
        int x = q.front().fr.fr, y = q.front().fr.sc, st = q.front().sc;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (check1(nx, ny, st + 1)) {
                if (nx == ex && ny == ey)
                    return 1;
                vis[nx][ny] = 1;
                q.push(mk(mk(nx, ny), st + 1));
            }
        }
    }
    return false;
}
int i, j;
int main() {
    cin >> n >> s;
    memset(bk, -1, sizeof(bk));
    queue<pair<pii, int> > q;
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            cin >> m[i][j];
            if (m[i][j] == 'M')
                sx = i, sy = j;
            if (m[i][j] == 'D')
                ex = i, ey = j;
            if (m[i][j] == 'H')
                bk[i][j] = 0, q.push(mk(mk(i, j), 0));
        }
    }
    while (!q.empty()) {
        int x = q.front().fr.fr, y = q.front().fr.sc, st = q.front().sc;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (checkbfs(nx, ny))
                bk[nx][ny] = st + 1, q.push(mk(mk(nx, ny), st + 1));
        }
    }
    if (!check(0))
        return cout << -1, 0;
    int l = 0, r = bk[sx][sy], mid;
    while (l < r) {
        mid = (l + r) >> 1;
        if (check(mid))
            l = mid + 1;
        else
            r = mid;
    }
    cout << l - 1;
    return 0;
}

种树

因为我们只能将序列中的数增加，对于 $A_i<A_j$，$A_j$ 能移动到的位置 $A_i$ 一定能移到，所以我们将 $A$ 从大到小排序。

考虑如下贪心策略：排序后由大往小遍历，并将当前数移动到目前最小的未被占用的位置，这个可以使用一个栈进行维护，实现不难，具体可以参考 std（如果能拿到的话）。

证明：考虑两个数 $x,y\ (x<y)$，他们最终将移到 $p$ 和 $q\ (p<q)$，显然会将距离较大的一组匹配较小的 $b_i$，又由于无论是哪种匹配方式，移动的距离和不变，所以说两个的距离差越大越好，即 $x\to q$，$y\to p$ 是更好的方案，可以发现，这要求我们对更大的 $A_i$ 匹配尽量小的位置，即上述结论。

时间复杂度 $\text O(n\log n)$，瓶颈在于排序。

例如：1 3 3 3 4 4 4 9 最终：1 3 4 5 6 7 8 9

例如：1 3 3 3 4 4 4 9 最终：1 3 5 6 4 7 8 9

高度和最后是固定的，一样的。怎样最小呢？用的$$b_i$排序后中来数越小越好。 变化的数： 3 3 4 4 匹配到： 5 6 7 8 匹配的顺序 8 7 6 5 匹配的差值 5 4 2 1

#include<bits\/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pi pair<int,int>
#define ld long double
#define vi vector<int>
#define all(x) begin(x),end(x)
using namespace std;
const int N=3e6+10,p=998244853;
int a[N],b[N],val[N];
int main()
{
	
	int n;
	scanf("%d", &n);
	for(int i=1;i<=n;i++) scanf("%d", &a[i]);
	for(int i=1;i<=n;i++) scanf("%d", &b[i]);
	sort(a+1,a+n+1),sort(b+1,b+n+1);
	vector<pi>s;
	a[n+1]=2e9;
	for(int i=n;i;i--)
	{
	    if(a[i]!=a[i+1])s.push_back({a[i],a[i+1]-1});
	    int &l = s.back().first, &r = s.back().second;
	    val[i]=(l++)-a[i];
	    if(l>r)s.pop_back();
	}
	ll ans=0;
	
	sort(val+1,val+n+1);
	for(int i=1;i<=n;i++)ans=(ans+(ll)val[n-i+1]*b[i]%p)%p;
	cout<<ans<<endl;
}

\/*
8
1 3 3 3 4 4 7 15
1  3 4 10 20 30 40 50
*\/