# 1007 分配宝藏

1007 分配宝藏

题目描述：

船长拥有 $\infty$ 宝藏，要求分给士兵们，确定好分配方案后士兵们会投票，如果大于等于半数的人（包括船长）对分配认可，那么可按此分配；否则，船长被处死，第一继承人上位。问如何分配船长能在分出最少的情况下活下来。

解题思路：（ $n$ 表示士兵的个数）

n = 1 ：船长的 1 票已经过半，该士兵可给可不给，因为要求分出最少，所以给 0 。

n = 2 ：第一顺位一定投反对，因为如果 Ta 成为船长就可以拥有所有宝藏；因为赞同票需要过半，对于第二顺位，如果这一票 Ta 不投赞成，那么在下一轮 Ta 无法获得宝藏，所以只需给 Ta 1 个宝藏，Ta 就会获得比下一轮多的宝藏，Ta 就会投赞同。

n = 3 ：第一顺位一定投反对，因为如果 Ta 成为船长就可以拥有所有宝藏；第二顺位如果到下一轮将获得 0 宝藏，所以只需给 Ta 1 个宝藏，Ta 就会投赞同；因为包括船长自己票数过半，所以第三顺位可给可不给，因为要求给出最少，所以给 0。

n = 4 ：第一顺位一定投反对，因为如果 Ta 成为船长就可以拥有所有宝藏；第二顺位如果到下一轮将获得 0 宝藏，所以只需给 Ta 1 个宝藏，Ta 就会投赞同；第三顺位如果到下一轮将获得 1 宝藏，第四顺位如果到下一轮将获得 0 宝藏，显然拉拢第四顺位所需宝藏更少，所给第三顺位 0 宝藏，第四顺位 1 宝藏。

……

以此类推，可列出给出结果如下：

如此观察可知：奇数位分出 0 宝藏，偶数位分出 1 宝藏

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
int solve()
{
	int n;
	cin >> n;
	if(n == 1) return 0;
	return (2 + n / 2 * 2) * (n / 2) / 2 % mod;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t;
	cin >> t;
	while(t--)
	{
		cout << solve() << '\n';
	} 
	return 0;
}

# 1005 航线

1005 航线

解题思路 1：

对于每个格子，不仅有 “距离” 的消耗，还有转向的消耗，所以我们可以直接将每个格子拆成四个格子

那么图形的转换如下图：

其中灰色的线上标的数字是转向所需要的消耗，每一 “块” 中灰色线的消耗相同，即数组 $t[i][j]$ ；粉色的线是 “距离” 所需的消耗，即数组 $g[i][j]$

给每个节点一个编号，建图，套用 Dijkstral 即可

解题思路 2：

利用 $Dijkstral$ ，对于 priority 中存储的是

struct node 
{
    int time, x, y, dir;
};

分别表示到该节点消耗的时间，节点的 $x$ ， $y$ 坐标，以及该节点的方向

用 $dist[x][y][dir]$ 存储到 $(x, y)$ 方向为 $dir$ 的节点的最短时间

if(time != dist[x][y][dir]) continue 用来防止重复遍历节点

时间转移有两种方式：

方式 1：

先处理移动，再处理转向

即先判断，如果可以沿着当前方向走，且下个节点的 $dist[x2][y2][i]$ 大于当前节点的 $dist[x1][x1][i] + g[x1][y1]$ ，那么就将该方向的下一个节点 $dist$ 更新，并加入队列

if (dist[nx][ny][dir] > time + g[nx][ny]) 
{
    dist[nx][ny][dir] = time + g[nx][ny];
    q.push({dist[nx][ny][dir], nx, ny, dir});
}

再判断，在当前节点，如果方向 $i$ 和原方向 $dir$ 不同，且 $dist[x][y][i] > dist[x][y][dir] + t[x][y]$ 就更新为加上转向的消耗

if (dist[x][y][i] > time + t[x][y]) 
{
    dist[x][y][i] = time + t[x][y];
    q.push({dist[x][y][i], x, y, i});
}

结束时返回要求的节点和方向即可

完整实现代码如下：

#include <bits/stdc++.h>
#define int long long
using namespace std;
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
//右0, 下1, 左2, 上3 
struct node 
{
    int time, x, y, dir;
    // 重载 < 运算符
    bool operator<(const node& other) const 
	{
        return time > other.time; // 最小堆
    }
};

int solve()
{
	int n, m;
	cin >> n >> m;
	vector<vector<int>> g(n + 1, vector<int>(m + 1)), t(n + 1, vector<int>(m + 1));
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			cin >> g[i][j];
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			cin >> t[i][j];
	priority_queue<node> q;
	vector<vector<vector<int>>> dist(n + 1, vector<vector<int>>(m + 1, vector<int>(4, 1e18)));
	q.push({g[1][1], 1, 1, 0});
	dist[1][1][0] = g[1][1];
	while(q.size())
	{
		node tp = q.top();
		q.pop();
		int time = tp.time, x = tp.x, y = tp.y, dir = tp.dir;
		if(time != dist[x][y][dir]) continue;

	    // 沿着当前方向移动
	    int nx = x + dx[dir], ny = y + dy[dir];
	    if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) 
		{
	        if (dist[nx][ny][dir] > time + g[nx][ny]) 
			{
	            dist[nx][ny][dir] = time + g[nx][ny];
	            q.push({dist[nx][ny][dir], nx, ny, dir});
	        }
	    }
	
	    // 尝试转向
	    for (int i = 0; i < 4; i++) 
		{
	        if (i == dir) continue; // 不需要转向
	        if (dist[x][y][i] > time + t[x][y]) 
			{
	            dist[x][y][i] = time + t[x][y];
	            q.push({dist[x][y][i], x, y, i});
	        }
	    }
	} 
	if(dist[n][m][1] != 1e18) return dist[n][m][1];
	return -1;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t;
	cin >> t;
	while(t--)
	{
		cout << solve() << '\n';
	}
	return 0;
}

方式 2：

转向和移动一起处理

直接遍历某个节点的四个方向，如果可以走

如果新的节点的地理位置可以以原方向走到，那么就不需要加上转向的消耗
如果新的节点需要转向才能走到，那么请加上原节点的转向消耗

在判断更新之后的是否更小，更小就更新

if(newtime < dist[a][b][i])
{
    dist[a][b][i] = newtime;
    q.push({newtime, a, b, i});
}

在结束时，因为只有当能走到下一个节点时，上一个节点才有可能转向。所以对于最后一个节点 $(n, m)$ ，按照上面的逻辑它是无法判断是否转向更优的，需要单独判断

int ans = 1e18;
for(int i = 0; i < 4; i++)
{
    if(i != 1) ans = min(ans, dist[n][m][i] + t[n][m]);
    else ans = min(ans, dist[n][m][i]);
}

完整代码如下：

#include <bits/stdc++.h>
#define int long long
using namespace std;
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
//右0, 下1, 左2, 上3 
struct node 
{
    int time, x, y, dir;
    // 重载 < 运算符
    bool operator<(const node& other) const 
	{
        return time > other.time; // 最小堆
    }
};

int solve()
{
	int n, m;
	cin >> n >> m;
	vector<vector<int>> g(n + 1, vector<int>(m + 1)), t(n + 1, vector<int>(m + 1));
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			cin >> g[i][j];
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			cin >> t[i][j];
	priority_queue<node> q;
	vector<vector<vector<int>>> dist(n + 1, vector<vector<int>>(m + 1, vector<int>(4, 1e18)));
	q.push({g[1][1], 1, 1, 0});
	dist[1][1][0] = g[1][1];
	while(q.size())
	{
		node tp = q.top();
		q.pop();
		int time = tp.time, x = tp.x, y = tp.y, dir = tp.dir;
		if(time != dist[x][y][dir]) continue;
		for(int i = 0; i < 4; i++)
		{
			int a = x + dx[i], b = y + dy[i];
			if(a >= 1 && a <= n && b >= 1 && b <= m)
			{
				int turn = 0;
				if(dir != i) turn += t[x][y];
				int newtime = turn + g[a][b] + time;
				if(newtime < dist[a][b][i])
				{
					dist[a][b][i] = newtime;
					q.push({newtime, a, b, i});
				}
			}
		} 
	}

	int ans = 1e18;
	for(int i = 0; i < 4; i++)
	{
		if(i != 1) ans = min(ans, dist[n][m][i] + t[n][m]);
		else ans = min(ans, dist[n][m][i]);
	}
	if(ans != 1e18) return ans;
	return -1;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t;
	cin >> t;
	while(t--)
	{
		cout << solve() << '\n';
	}
	return 0;
}

# 1002 船长

1002 船长

题目描述：个人淘汰赛，钦定特定某个人是赢家，除此之外其他人获胜率均五五开，按编号从小到大两个两个打，多出来的直接晋级，求赢家不碰上另外特定 $k$ 个人的概率。

解题思路：

以钦定赢家 $w$ 不想碰到的 $k$ 个人为叶子节点建立二叉树，每往上走一层就是打了一轮。

为了方便给非叶子节点编号，我们将 $1\sim n$ 的编号都 $-1$ ，那么两个节点 $x, y$ 的父节点就直接是 $x / 2,y / 2$ ，并且两个打比赛的节点可以通过 x ^ 1 = y 得到。

叶子节点的概率 $f[i]$ 初始化为 1， $f[i]$ 表示 $w$ 不想碰到的人到达 $i$ 这个位置的概率。

对于向上比赛，概率的计算可以分成四种情况：

如果节点 $a[i]$ 和钦定赢家 $w$ 打比赛，那么就直接计算不会碰到该节点的概率 ans *= (1 - f[i])
如果节点 (a[i] >> 1) == (a[i + 1] >> 1) ，即跟 $a[i]$ 打比赛的节点也在 $a$ 中，二者都是 $w$ 不想碰到的人，那么 f[i >> 1] = (f[i] + f[i + 1]) / 2
如果节点 (a[i] ^ 1) != a[i + 1] && (a[i] ^ 1) < n ，即跟 $a[i]$ 打比赛的节点不在 $a$ 中，另一个节点是和 $w$ 打必输的节点，那么 f[i >> 1] = f[i] / 2
如果节点 (a[i] ^ 1) >= n ，即 $a[i]$ 是最后一个单出来的节点，不需要打就晋级，那么 f[i >> 1] = f[i]

小数取模：

注意：不能先用 $double$ 再取模，因为 $double$ 涉及精度不够的问题

因为最后的结果要求对 998244353 取模，而 ans 又是小数，所以需要利用乘法逆元

如果我们所有的除操作都用乘法逆元那么会 TLE，而我们发现所有的除法运算都是 / 2 所以只需要算 $2$ 的乘法逆元即可，一定要预处理 2 的乘法逆元

求 $2$ 的逆元有两种方式：

乘法逆元的定义:

$a \times a^{-1} \equiv 1\pmod m$

对于 $a = 2$ ，即找到 $x$ 使得

$2 \times x\equiv 1\pmod {998244353}$

等价于

$2x = 998244353k + 1$

经过尝试，因为 $x$ 为整数，所以 $k$ 取奇数，发现 $k = 1$ 时即可

得到结论：对于任意奇数模数 $m$ ，2 的乘法逆元可以通过以下公式计算：

$inv2 = \frac{m + 1}{2}$

直接利用求乘法逆元的公式，利用快速幂求逆元

$\frac{a}{b}\equiv a\times x\pmod m$

$\Rightarrow x = a ^ {m - 2}\mod m$

//快速幂 
int qmi(int a, int b, int p)
{
    int res = 1;
    while(b)
    {
        if(b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
//求逆元 
int inv(int x)
{
	return qmi(x, MOD - 2, MOD);
}
int inv2 = inv(2);

$\color{red}$

//dlink.host/wx2.sinaimg.cn/large/007CYURoly8hzkgkkpp4gj30nq0a60t8.jpg

请注意 ^ 的优先级比比较操作符 > >= < <= == != 低，一定要记得打括号！！！

完整代码如下：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 998244353;

//快速幂 
int qmi(int a, int b, int p)
{
    int res = 1;
    while(b)
    {
        if(b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
//求逆元 
int inv(int x)
{
	return qmi(x, MOD - 2, MOD);
}

void solve()
{
	int n, k, w;//n：比赛人数  k：w害怕遇到的人数  w：必胜的人 
	cin >> n >> k >> w; 
	w -= 1;
	
	vector<int> a(k), f(k, 1);//a 害怕遇到的人的编号  f害怕的人到i位置的概率
	for(int i = 0; i < k; i++) cin >> a[i], a[i] -= 1;//方便计算父节点
	sort(a.begin(), a.end());
	
	int ans = 1, inv2 = inv(2);
	while(a.size())
	{
		w >>= 1;//往上打一层
		vector<int> b, g;//b 临时存储下一轮的节点  g 临时存储下一轮的概率
		for(int i = 0; i < a.size();)
		{
			//如果和w打
			if((a[i] >> 1) == w) ans = ans * (MOD + 1 - f[i] ) % MOD, i += 1;
			else
			{
				b.push_back(a[i] >> 1);
				if(i + 1 < a.size() && (a[i] >> 1) == (a[i + 1] >> 1)) g.push_back((f[i] + f[i + 1]) * inv2 % MOD), i += 2;
				else if((a[i] ^ 1) < n) g.push_back(f[i] * inv2 % MOD), i += 1;
				else g.push_back(f[i]), i += 1;
			}
		}
		a = b;
		f = g;
		n = (n + 1) / 2;
	} 
	cout << ans << '\n';
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t;
	cin >> t;
	while(t--)
	{
		solve();
	}
	return 0;
}

# 1004 海浪

1004 海浪

题目表述：

题目给定一个长度为 $n$ 的数组 $a$ ，定义一段区间 $[l,r]$ 为 “波浪” 区间，当区间内存在一个 “波峰” 或 “波谷”，使得整个区间内的元素都围绕这个波峰或波谷波动。每次查询给出一个区间 $[l,r]$ ，要求在这个区间内找到最长的 “波浪” 子区间。

解题思路：

海浪一共只有两种形式

奇数位为 “波峰”，偶数位为” 波谷 “。即如果 $[l, r]$ 区间中的波面是海浪，那么 $[l, r]$ 中奇数位的最小值大于偶数位的最大值。
奇数位为 “波谷”，偶数位为 “波峰”。即如果 $[l, r]$ 区间中的波面是海浪，那么 $[l, r]$ 中奇数位的最大值小于偶数位的最小值。

显然我们只需要处理一种情况，对于另一种情况只需要对距离取反，再以相同的方式处理一遍即可。

实现过程：（以第一种情况为例）

初始化：既然要维护奇数位的最小值和偶数位的最大值，那么就可以利用 ST 表。

很明确，在我们要求奇数位的最小值的时候偶数位不能在里面，那么我们就需要把偶数位的最小值初始化为 $+\infty$ ；在我们要求偶数位的最大值的时候奇数位不能在里面，所以需要把奇数位的最大值初始化为 $-\infty$
判断一个区间是否是海浪：利用 ST 表，我们可以判断，如果一个区间奇数位的最小值大于偶数位的最大值，那么这个区间是海浪。

需要注意：对于只有一个节点的情况，假设该节点是奇数位，那么因为我们将该点的 $max$ 初始化为 $-\infty$ ， $min$ 初始化为 $+\infty$ ，所以只有一个点的时候这个点也是海浪
计算最长波浪距离和节点：利用双指针，我们可以得到以 $i$ 为左端点，波浪的最远距离 $len[i][0]$ ，距离最远时的右端点是 $pos[i] = j$
- $len[i][j]$ 表示从 $i$ 开始， $2 ^ j$ 距离的节点中任一节点，以该节点为左端点的波浪区间的长度最大值
- $pos[i]$ 表示以 $i$ 节点为左端点，最长波浪的右端点；很显然， $pos$ 是的单调递增的
处理询问：对于每一组给定的 $[l, r]$ ，我们可以将总区间分成三段：在 $pos$ 数组中左端点 $i$ 在 $l$ 左边，在 $l$ 和 $r$ 中间，以及在 $r$ 右边。具体如下图，其中黑色线段表示 $pos$ 数组，每个线段的左端点表示 $pos$ 数组中的左端点 $i$ ，右端点表示 $pos$ 数组中的值 $j$ ，即以 $i$ 为左端点的海浪距离最长时的右端点。
- 若左端点不在查询区间 $[l, r]$ $[l, r]$
  - 在 $1$ 区：因为 $pos$ 数组是递增的，所以这显然不如以 $l$ 为左端点，因为 $pos[l]$ 一定比 $pos[i](i<l)$ 的值靠右
  - 在 $3$ 区：显然和 $[l, r]$ 无交集，不可能
- 若左端点在查询区间 $[l, r]$ $[l, r]$
  - 右端点在查询区间 $j <= r$ ，利用 ST 表，利用 $len$ 找到最长的波浪
  - 右端点不在查询区间，利用二分找到最小的 $j$ ，使 $j >= r$ ，那么这种情况下的最长海浪就是 $r- i$ ，其中 $pos[i] = j$

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10, mod = 1e9 + 7, INF = (1 << 30) - 1;
int n, q, h[N], ql[N], qr[N], lg[N], maxx[N][20], minn[N][20], ans[N], pos[N], len[N][20];

void InitST()
{
	//初始化log2 
	lg[1] = 0;
	for(int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
	
	//初始化 奇数位是波谷 偶数位是波峰 
	for(int i = 1; i <= n; i++)
	{
		if(i & 1) maxx[i][0] = h[i], minn[i][0] = INF;
		else maxx[i][0] = -INF, minn[i][0] = h[i];
	}
	//处理每个区间的（奇数位）最大值和（偶数位）最小值 
	for(int j = 1; j < 19; j++)
	{
		for(int i = 1; i + (1 << j) - 1 <= n; i++)
		{
			maxx[i][j] = max(maxx[i][j - 1], maxx[i + (1 << j - 1)][j - 1]);
			minn[i][j] = min(minn[i][j - 1], minn[i + (1 << j - 1)][j - 1]);
		}
	}
}
//判断是否是海浪 
bool judge(int l, int r)
{
	int maxlog = lg[r - l + 1];
	int m = min(minn[l][maxlog], minn[r - (1 << maxlog) + 1][maxlog]);
	int M = max(maxx[l][maxlog], maxx[r - (1 << maxlog) + 1][maxlog]);
	return m > M;
}
//处理海浪长度 
void DealLen()
{
	for(int i = n, j = n; i >= 1; i--)
	{
		while(i <= j && !judge(i, j)) j--;
		pos[i] = j;
		len[i][0] = j - i + 1;
	}
	//处理每个区间的最长海浪
	for(int j = 1; j < 19; j++)
		for(int i = 1; i + (1 << j) - 1 <= n; i++)
			len[i][j] = max(len[i][j - 1], len[i + (1 << j - 1)][j - 1]);
}
//询问最长海浪 
int querylen(int l, int r)
{
	int maxlog = lg[r - l + 1];
	return max(len[l][maxlog], len[r - (1 << maxlog) + 1][maxlog]);	
}
//处理询问 
void DealQuery()
{
	for(int i = 1; i <= q; i++)
	{
		int l = ql[i], r = qr[i]; 
		int x = lower_bound(pos + l, pos + r + 1, r) - pos;
		ans[i] = max(ans[i], r - x + 1);
		if(x - 1 >= l) ans[i] = max(ans[i], querylen(l, x - 1)); 
	}
}
//反转 
void reverse()
{
	for(int i = 1; i <= n; i++) h[i] = -h[i];
}
void work()
{
	InitST();
	DealLen();
	DealQuery();
}
void solve()
{
	cin >> n >> q;
	for(int i = 1; i <= n; i++) cin >> h[i];
	for(int i = 1; i <= q; i++) cin >> ql[i] >> qr[i];
	work();
	reverse();
	work();
	int res = 0;
	for(int i = 1; i <= q; i++) res = (res + i * ans[i]) % mod;//是q!!!!!是q!!!!!是q!!!!!!!
	cout << res << '\n';
	memset(ans, 0, sizeof ans);
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t;
	cin >> t;
	while(t--)
	{
		solve();	
	} 
	return 0;
}

algorithm

# 1007 分配宝藏

# 1005 航线

# 1002 船长

# 1004 海浪

Atcoder396

Hust_ACM_Practice2