对一些题目的思考

洛谷 P3203 [HNOI2010]弹飞绵羊

这道题我用的是分块，但一开始 WA 了，改了几遍都还是只有 50pts，后来看题解，发现题解说的是在更新的时候要整个块全部重构，而我只重构了块内在被更新位置之前的那些位置的值，直接用 $i+a_i$ 是否等于 $x$ 来判断要不要更新这个值，然而在同一块中，绵羊可能从一个位置跳很多次都跳不出这个块，也就是说，有可能它无法一次性跳到从 $i$ 跳到 $x$ ，而要经过几次跳跃才行，所以不能这样判断，但如果直接根据弹力系数一个一个暴力跳来判断能否到达 $x$ ，那单次修改复杂度最坏可能会达到接近 $O(n)$ ，还不如直接整个块重构，这样复杂度是 $O(\sqrt n)$ 的。同时，在一开始初始化和重构时，不必每个位置都暴力跳一遍，可以从后往前循环，用后面的位置来更新前面的位置，也就是说，对于每个位置，判断是否能一次性跳出这个块，如果可以，直接给这个位置赋值就行了，如果不行，那它必定是跳到了后面的某个位置，由于它后面的值已经全部更新过了，所以直接在跳到的那个位置的基础上加一就可以了。

#include<bits/stdc++.h>
#define N 200010
#define pii pair<int,int>
#define mp make_pair
using namespace std;
int n,m,len,num,a[N],l[1010],r[1010],belong[N];
pii g[N];
void update(int x,int k)
{
	a[x]=k;
	for(int i=r[belong[x]];i>=l[belong[x]];i--)
	{
		g[i].first=i+a[i];
		g[i].second=1;
		if(g[i].first<=r[belong[x]])
		{
			g[i].second=g[g[i].first].second+1;
			g[i].first=g[g[i].first].first;
		}
	}
}
int query(int x)
{
	int j=x,sum=0;
	while(j<=n)
	{
		sum+=g[j].second;
		j=g[j].first;
	}
	return sum;
}
int main()
{
	scanf("%d",&n);
	len=sqrt(n);
	num=(n-1)/len+1;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		belong[i]=(i-1)/len+1;
	}
	for(int i=1;i<=num;i++)
	{
		l[i]=r[i-1]+1;
		r[i]=min(i*len,n);
	}
	for(int i=n;i>=1;i--)
	{
		g[i].first=i+a[i];
		g[i].second=1;
		if(g[i].first<=r[belong[i]])
		{
			g[i].second=g[g[i].first].second+1;
			g[i].first=g[g[i].first].first;
		}
	}
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		int op,x,k;
		scanf("%d%d",&op,&x);
		if(op==1)
			printf("%d\n",query(x+1));
		else
		{
			scanf("%d",&k);
			update(x+1,k);
		}
	}
	return 0;
}

另外，CF13E 跟这道题几乎一模一样，但有一个坑点在于它还要求最后一次落在哪个洞里，一开始我是直接用一个变量来存储 $j$ 上一次到达的位置，但在第三个测试点里 WA 了，后来才发现这里的 $j$ 是直接从块中跳出去的，所以可能会从当前位置跳多次才能跳出这个块，但上面这个方法就只统计了当前位置，没有管后面是否中转，所以会出错。解决方法是再把最后的答案进行暴力跳转，直到找到一个能把球弹出的位置，这个位置才是答案。

int query(int x)
{
	int j=x,b,sum=0;
	while(j<=n)
	{
		sum+=g[j].second;
		b=j;
		j=g[j].first;
	}
	while(b+a[b]<=n)
		b+=a[b];
	printf("%d %d\n",b,sum);
}

洛谷 P1171 售货员的难题

这道题算是状压的一道经典题型，一开始我是 WA 了，只得了 $10$ 分，调了一会不知道哪里出问题了，看了一下题解才发现自己在算 $dp$ 数组的时候，是把起点放在最外层循环，到过的城镇的状态放在中间循环，终点放在内层循环。

for(int i=1;i<=n;i++)
{
    for(int j=1;j<=(1<<n)-1;j++)
    {
        if(!(j&(1<<(i-1))))
            continue;
        for(int k=1;k<=n;k++)
        {
            if(j&(1<<(k-1)))
                continue;
            dp[k][j|(1<<(k-1))]=min(dp[k][j|(1<<(k-1))],dp[i][j]+dis[i][k]);
        }
    }
}

这样就相当于我是人为地把这个顺序给固定下来了，必须是从编号小的点走到大的点，因为如果最佳顺序是 $1\to 5 \to 2\to 3$ 这样一个序列的话，那我虽然可以用 $5$ 去更新 $2$ 的距离，但从 $2$ 到 $3$ 的距离已经定了，不能改变了，所以最后求出来的答案就是错误的，解决方法是把到过城镇的状态放在第一层循环，然后去枚举起点和终点（事实上，据旁边的 xfy 巨佬说，状压 DP 都应该是把状态放在最外层，这样才能保证你用来更新其他点的这个值是已经被计算完的）。

for(register int j=1;j<=(1<<n)-1;j++)
    for(register int i=1;i<=n;i++)
    {
        if(!(j&(1<<(i-1))))
            continue;
        for(register int k=1;k<=n;k++)
        {
            if(!(j&(1<<(k-1))))
                continue;
            dp[j][k]=min(dp[j][k],dp[j^(1<<(k-1))][i]+dis[i][k]);
        }
    }

另外，这道题有一点点卡常，亲测不加 register 的话第 $10$ 个点会 T 掉（~~也有可能是我人傻常数大~~），把表示状态的较大的一维放在最外层，也可以少个几毫秒的样子（~~其实更有可能是评测机波动~~）。

CodeForces 316D3 PE Lesson

今天校内模拟赛的 T3，洛谷题解区里第一篇的思路挺好懂的，这里主要对它做一些补充。

关于 $b=0$ 时的式子的解释

这个式子分成两部分理解，第一部分是 $f_{i-1}$ ，这个很容易理解，相当于是这个 $1$ 跟自己交换，所以是 $f_{i-1}\times 1$ ，另外一部分也类似地理解，由于是当前这个 $1$ 选定另外一个 $1$ 与之交换，另外一个 $1$ 有 $i-1$ 种选法，剩下 $i-2$ 个数，所以是 $f_{i-2}\times (i-1)$ ，然后将这两者相加即可。
关于 $b$ 个 $2$ 的可以选择与之交换的数的数量

首先是第一个 $2$ 之所以可以从 $n$ 个中选一个，是因为我们可以将多出来的那一个理解为它和自己交换，其次是为什么后面的 $2$ 可选的数的数量逐一递减，是因为这篇题解理解两次交换的思路是将其理解为一次主动交换，即它自己选一个数与之交换，一次被动交换，即它被另外一个数选中与之交换，假设这一次我们选的是一个 $1$ ，那么下一次这个 $1$ 就不能被选了，因为它的剩余次数已经变成 $0$ 了，而如果这一次选的是一个 $2$ ，那么它被选的次数也变成 $0$ 了，所以无论如何，我们都不能选之前已经被选过的数与之交换，因此要逐一递减。
关于剩余 $a$ 个 $1$

这个其实比较显然，首先可以发现，由于所有的 $2$ 都至少有了一次主动交换，所以 $b$ 次交换后就不可能会有 $2$ 了，其次，由于一开始总次数为 $a+2\times b$ ， $b$ 次交换每次会消耗 $2$ 次交换，所以最后剩下的总数为 $a$ ，又由于没有 $2$ ，只有 $0$ 或 $1$ ，所以一定会有 $a$ 个 $1$ 。

AUOJ 156D 项链

这道题其实我考场上就想出正解了的，然而由于一个 sb 错误导致挂了 10pts，这里记录一下我的玄学做法，顺便理一下思路。

首先根据题面可以看出所给的图是一个 DAG，提到 DAG 第一时间应该想到拓扑排序，众所周知，拓扑排序有两种实现方法，BFS 和 DFS，由于 BFS 是从上往下计算，个人感觉不太方便，于是这里选用不太常用的 DFS。

对于第一个答案，我们可以用一个 $dp_u$ 记录以 $u$ 为起点价值之和最大的一条链，这个很简单，直接在回溯的时候判断一下就行了，方法类似于最大子段和，不再赘述。

关键在于第二个答案，即求一个和最大子段和在同一条链上的次大子段和，众所周知，在一条链上，次大子段和只会出现在最大子段和的两端（废话），大概是这个意思

我们先考虑和次大的子段在和最大的子段的右边的情况，对应到图上也就是和最大的子段的儿子那一块，由于最大的字段不能和次大的子段交错，所以我们再记录一下以 $u$ 为起点的和最大的子段的终点，那么次大子段应该就是在这个终点的所有儿子里，我们把这个值记录下来，具体来说，对于每一个点，我们记录它所有儿子中和最大的一条链，这时，对于点 $u$ ，它下面的次大子段就应该是它最大子段的终点的儿子中和最大的一条链。

算了，我语文不太好，直接看一下代码

int n,m,vis[N],in[N];
ll w[N],dp[N][4];
/*
dp[u][0]: 以 u 为起点的最大子段和
dp[u][1]: 以 u 为起点的和最大的子段的终点
dp[u][2]: 以 u 为起点的和最大的子段下面的次大子段和，即图片中右边那段蓝色中的最大子段和
dp[u][3]: u 的儿子中和最大的一条链
*/
vector<int> edge[N];
void dfs(int u)
{
	if(vis[u])
		return;
	vis[u]=1;
	dp[u][0]=w[u];
	dp[u][1]=u;
	for(int i=0;i<edge[u].size();i++)
	{
		int v=edge[u][i];
		dfs(v);
		if(dp[v][0]+w[u]>dp[u][0]||(dp[v][0]+w[u]==dp[u][0]&&dp[u][2]<dp[dp[v][1]][3]))
		{
			dp[u][0]=dp[v][0]+w[u];
			dp[u][1]=dp[v][1];
			dp[u][2]=dp[dp[v][1]][3];
		}
		dp[u][3]=max(dp[u][3],max(dp[v][3],dp[v][0]));//这里考试时犯了一个 sb 错误，没有把 v 的两个值得较大值和 dp[u][3] 取较大值。。。
	}
}

我们并不需要考虑如果次大子段和比最大子段和大的情况，因为我们最后在计算答案时是遍历每一个点，如果次大子段和比最大子段和大，那么以这个点为起点的和最大的子段就不是最优答案，就会被覆盖掉。

接下来是第二种情况，和次大的子段在和最大的子段的左边，如果你把上面那一部分看懂了，那么这种情况也会很简单，我们可以直接建一个反图，然后完全相同地跑一遍拓扑，不过这时的儿子对应的就是原来那张图的爸爸，对于一个点 $u$ ，以它为起点的和最大的子段所在的链中的次大子段和就是 $\max\{dp1_{u,3},dp_{u,2}\}$ 。

完整代码

#include<bits/stdc++.h>
using namespace std;
namespace IO
{
	char buf[1<<23],*p1=buf,*p2=buf;
	#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
	#define isdigit(c) (c>=48&&c<=57)
	#define isalpha(c) (c>=65&&c<=90)
	template<typename T> inline void read(T &x)
	{
		x=0;
		register int f=1;
		register char ch=getchar();
		while(!isdigit(ch))
		{
			if(ch==45)
				f=-1;
			ch=getchar();
		}
		while(isdigit(ch))
		{
			x=(x<<1)+(x<<3)+(ch^48);
			ch=getchar();
		}
		x*=f;
	}
	template <typename T,typename... Args> inline void read(T& t, Args&... args)
	{
		read(t);read(args...);
	}
}
using namespace IO;
typedef long long ll;
const int N=1e5+10;
int n,m,vis[N],vis1[N],in[N],in1[N];
ll w[N],ans[2],dp[N][4],dp1[N][4];//后缀为 1 的都是建反图和跑反图时用的数组
vector<int> edge[N],edge1[N];
void dfs(int u)
{
	if(vis[u])
		return;
	vis[u]=1;
	dp[u][0]=w[u];
	dp[u][1]=u;
	for(int i=0;i<edge[u].size();i++)
	{
		int v=edge[u][i];
		dfs(v);
		if(dp[v][0]+w[u]>dp[u][0]||(dp[v][0]+w[u]==dp[u][0]&&dp[u][2]<dp[dp[v][1]][3]))
		{
			dp[u][0]=dp[v][0]+w[u];
			dp[u][1]=dp[v][1];
			dp[u][2]=dp[dp[v][1]][3];
		}
		dp[u][3]=max(dp[u][3],max(dp[v][3],dp[v][0]));
	}
}
void dfs1(int u)
{
	if(vis1[u])
		return;
	vis1[u]=1;
	dp1[u][0]=w[u];
	dp1[u][1]=u;
	for(int i=0;i<edge1[u].size();i++)
	{
		int v=edge1[u][i];
		dfs1(v);
		if(dp1[v][0]+w[u]>dp1[u][0]||(dp1[v][0]+w[u]==dp1[u][0]&&dp1[u][2]<dp1[dp1[v][1]][3]))
		{
			dp1[u][0]=dp1[v][0]+w[u];
			dp1[u][1]=dp1[v][1];
			dp1[u][2]=dp1[dp1[v][1]][3];
		}
		dp1[u][3]=max(dp1[u][3],max(dp1[v][3],dp1[v][0]));
	}
}
signed main()
{
	read(n,m);
	for(int i=1;i<=n;i++)
		read(w[i]);
	for(int i=1;i<=m;i++)
	{
		int u,v;
		read(u,v);
		edge[u].push_back(v);
		edge1[v].push_back(u);
		in[v]++;
		in1[u]++;
	}
	for(int i=1;i<=n;i++)
	{
		sort(edge[i].begin(),edge[i].end());
		edge[i].erase(unique(edge[i].begin(),edge[i].end()),edge[i].end());
		sort(edge1[i].begin(),edge1[i].end());
		edge1[i].erase(unique(edge1[i].begin(),edge1[i].end()),edge1[i].end());
	}
	for(int i=1;i<=n;i++)
		if(!in[i])
			dfs(i);
	for(int i=1;i<=n;i++)
		if(!in1[i])
			dfs1(i);
	for(int i=1;i<=n;i++)
		if(dp[i][0]>ans[0]||(dp[i][0]==ans[0]&&ans[1]<max(dp1[i][3],dp[i][2])))
		{
			ans[0]=dp[i][0];
			ans[1]=max(dp[i][2],dp1[i][3]);
		}
	printf("%lld %lld",ans[0],ans[1]);
	return 0;
}

CodeForces 76F Tourist

这道题比较容易想到的方法是按时间排个序，然后用 $dp_i$ 表示在必须看第 $i$ 个事件的前提下前 $i$ 个事件中最多能看到多少事件，然而显然这样是 $O(n^2)$ 的，而且不太好用数据结构优化，所以我们考虑转化这个式子。

对于所有 $t_j$ 小于 $t_i$ 的 $j$ ，显然它还要满足这样的条件才合法。

$|x_i-x_j|\le v\times(t_i-t_j)$

我们分两种情况讨论，即 $x_i\le x_j$ 和 $x_i>x_j$ 。

对于第一种情况，我们将上面这个式子化简，可以得到这个式子。

$x_j+v\times t_j\le x_i+v\times t_i$

对于第二种情况，可以得到这个式子。

$x_i-v\times t_i\le x_j-v\times t_j\\ v\times t_j-x_j \le v\times t_i-x_i$

然后你会发现，根据不等式的基本性质，这两个式子是可以互相转化的，也就是说，凡是合法的 $j$ ，都应该同时满足上述两个式子。

然后这就变成了一个二位偏序问题。

对于每一个事件，我们设 $p_i=v\times t_i-x_i$ ， $q_i=x_i+v\times t_i$ ，按 $p$ 排序后，直接求 $q$ 的最长上升子序列就行了。

这里还有一个很有意思的地方，由于第一个问题要求在 $0$ 时刻从原点出发，而最长上升子序列只能求出以某一点结束，所以我们可以把上面这个东西反一下，然后直接从终点开始求，而不是从起点开始求。

#include <bits/stdc++.h>
#define lowbit(x) (x&(-x))
#define rep(i, l, r) for(int i = (l), i##end = (r); i <= i##end; i++)
#define per(i, r, l) for(int i = (r), i##end = (l); i >= i##end; i--)
#define debug(x) cerr<<#x<<" = "<<x
using namespace std;
namespace IO
{
	char buf[1<<23], *p1 = buf, *p2 = buf;
	#define getchar() (p1 == p2 && (p2 = (p1 = buf)+fread(buf, 1, 1<<21, stdin), p1 == p2) ? EOF : *p1++)
	#define isdigit(c) (c >= 48 && c <= 57)
	#define isalpha(c) ((c >= 65 && c <= 90) || (c >= 97 && c <= 122))
	template<typename T> inline void read(T &x)
	{
		x = 0;
		register int f = 1;
		register char ch = getchar();
		while(!isdigit(ch))
		{
			if(ch == 45)
				f = -1;
			ch = getchar();
		}
		while(isdigit(ch))
		{
			x = (x<<1)+(x<<3)+(ch^48);
			ch = getchar();
		}
		x *= f;
	}
	template <typename T,typename... Args> inline void read(T& t, Args&... args)
	{
		read(t);read(args...);
	}
}
using namespace IO;
typedef long long ll;
const int N = 1e5+10, inf = 0x3f3f3f3f;
struct Event
{
	int p;
	int q;
	int id;
	bool operator < (const Event &x) const
	{
		return p == x.p ? q < x.q : p < x.p;
	}
};
Event a[N], b[N];
int n, v, qwq, ans, c[N], tree[N], dp[N];
void update(int x, int k)
{
	for(; x <= qwq; x += lowbit(x))
		tree[x] = max(tree[x], k);
}
int query(int x)
{
	int ans = 0;
	for(; x >= 1; x -= lowbit(x))
		ans = max(ans, tree[x]);
	return ans;
}
int main()
{
	read(n);
	rep(i, 1, n)
		read(a[i].p, a[i].q);
	read(v);
	rep(i, 1, n)
	{
		b[i] = (Event){-v*a[i].q+a[i].p, -v*a[i].q-a[i].p, i};
		c[i] = b[i].q;
	}
	sort(c+1, c+2+n);
	qwq = unique(c+1, c+2+n)-c-1;
	rep(i, 1, n+1)
		b[i].q = lower_bound(c+1, c+1+qwq, b[i].q)-c;
	sort(b+1, b+2+n);
	rep(i, 1, n+1)
	{
		dp[i] = query(b[i].q)+1;
		update(b[i].q, dp[i]);
		if(a[b[i].id].q == 0)
			printf("%d ",dp[i]-1);
		else
			ans = max(ans, dp[i]);
	}
	printf("%d", ans);
	return 0;
}

洛谷 P2894 [USACO08FEB]Hotel G

交了好多遍都只有 8pts，心态都快炸了，最后发现是 query 写错了。。。

int query(int p, int k)
{
	if(tree[p].lz < k && tree[p].data < k && tree[p].rz < k)
		return 0;
	if(tree[p].l == tree[p].r)
		return tree[p].l;
	push_down(p);
	if(tree[p<<1].data >= k || tree[p<<1].lz >= k || tree[p<<1].rz >= k)
		return query(p<<1, k);
	if(tree[p<<1].rz+tree[p<<1|1].lz >= k && tree[p<<1].rz)
		return query(p<<1, tree[p<<1].rz);
    	//就是这里，我本来想的是让线段树返回左儿子的右边连续的 0 的左端点
    	//但这样会有一个问题，就是这玩意可能认为本来让你找的就是这么长一段区间
    	//然后就可能会跑到其他地方去。。。
	if(tree[p<<1|1].data >= k || tree[p<<1|1].lz >= k || tree[p<<1|1].rz >= k)
		return query(p<<1|1, k);
	return 0;
}

稍微改了一下，加了个特判就过了。

int query(int p, int k, int flag)
{
	if(tree[p].lz < k && tree[p].data < k && tree[p].rz < k)
		return 0;
	if(tree[p].l == tree[p].r)
		return tree[p].l;
	push_down(p);
	if(flag)
	{
		if(k > tree[p<<1|1].rz)
			return query(p<<1, tree[p<<1].rz, flag);
		else
			return query(p<<1|1, k, flag);
	}
	if(tree[p<<1].data >= k || tree[p<<1].lz >= k || tree[p<<1].rz >= k)
		return query(p<<1, k, 0);
	if(tree[p<<1].rz+tree[p<<1|1].lz >= k && tree[p<<1].rz)
		return query(p<<1, tree[p<<1].rz, 1);
	if(tree[p<<1|1].data >= k || tree[p<<1|1].lz >= k || tree[p<<1|1].rz >= k)
		return query(p<<1|1, k, 0);
	return 0;
}

洛谷 P2891 [USACO07OPEN]Dining G

一开始的时候搞不明白这道题为什么要把牛拆成两个点，感觉好像并没有什么区别，然而如果不拆就只有 20pts，逛了一波题解区终于理解了。。。

其实很简单，因为题目要求一头牛只能享受一种食物和一种饮料，如果不拆点，就有可能让一头牛享受多种食物和饮料，从而让程序误以为满足了更多牛的需求。

比如说这张图。

显然最大流为 $2$ ，但实际上答案应该为 $1$ 。

解决方法就是把牛拆成两个点，并建一条边，容量为 $1$ ，这样就能保证一头牛只能吃一种食物，喝一种饮料了。

P5048 [Ynoi2019 模拟赛] Yuno loves sqrt technology III

这道题的做法大同小异，都是用一个数组 $d_i$ 表示 $i$ 在 $pos_{a_i}$ 这个 vector 中的下标，然后判断一下 $d_i+res$ 是否小于等于 $r$ ，如果是，就说明当前这个数更优，于是更新答案，代码大致如下。

预处理部分。

rep(i, 1, n)
{
    a[i] = lower_bound(c+1, c+1+qwq, a[i])-c;
    pos[a[i]].pb(i);
    d[i] = pos[a[i]].size()-1;
    belong[i] = (i-1)/len+1;
}

查询部分。

res = p[belong[x]+1][belong[y]-1];
rep(i, x, r[belong[x]])
    for(int j = d[i]+res; j < pos[a[i]].size() && pos[a[i]][j] <= y; j++)
        res++;
rep(i, l[belong[y]], y)
    for(int j = d[i]-res; j >= 0 && pos[a[i]][j] >= x; j--)
        res++;

说一下为什么这样复杂度是对的，首先可以很容易看出 $res$ 的值只增不减，所以我们可以近似的把 $res$ 增加的次数看成复杂度。

由于一开始 $res$ 被初始化为 $[belong_x+1,belong_y-1]$ 这些块中的众数的出现次数，显然，其他数在这些块中的出现次数都不可能比这个值更大，所以，对于任意 $d_i+res$ ，我们可以近似地看成是直接跳到了 $belong_y$ 这一块的起始位置，当然实际情况很有可能并不是这样，但其实也差不了多少，感性理解一下就行了。