Ticket Game

标签：思维

--------------------------------------------------------------------------------------------------------

Alice和Bob生活在Berland。Berland的每一张公交车票都包含n（n是偶数）位数。

在晚上散步时，Alice和Bob发现了一张有某些位被擦掉而空着（擦掉的位数也是偶数）的公交车票。

Alice讨厌“高兴”的车票，而Bob则喜欢并收集它们。我们称一张车票“高兴”是说前 n/2​ 位数之和和后 n/2 ​位数之和相等。

Alice和Bob轮流进行操作（Alice先手），每次操作，当前进行操作的玩家会在一个被空着的数位填上0到9。当所有数位都被填满，游戏结束。

如果这张车票在游戏结束后“高兴”，那么Bob胜利；否则Alice胜利。如果两人都足够聪明，请你确定谁会胜出。

---------------------------------------------------------------------------------------------------------

  考虑Bob在什么情况下会输。如果他在最后一次填数时两边的差距已经超过了9，Alice就赢了。所以Alice一定想让两端的差距越大越好，Bob一定想让两端平衡。显然，最优策略是Alice在大的那一半拼命加9，Bob在小的那一半拼命加9。

  考虑两边的初始值相等并且问号相等的情况，那肯定Bob赢。无论Alice填了什么内容，Bob都可以在相对应的位置填入相同的数字，这样，始终能够保证左右两半的数字之和都是一样的。

  如果两端和不相等时，Alice就在大的那一半拼命加9，Bob小的那一半拼命加9。这样一直操作，如果小的那一边没"?"了，Alice肯定赢。如果大的那一边没"?"了，Alice一定会在小的那一边填0，而Bob一定会填9。这样，我们只需要计算Bob在这一半内能填入多少个数字，假设Bob能填 x个数字，那么，如果恰好两边的差为9*x ,则Bob可以获胜，否则，都是Alice获胜。

  为什么呢？如果两边的差一开始就大于9*x，那不必说，一定是Alice赢。而如果数字和小的一半加上 9*x 大于了数字和大的一半，那么，Alice可以选择使劲的填入9，这样这一半就会超过想要的大小。但如果两边的差为9*x，无论Alice填什么，Bob都只用填9-Alice填的值即可满足情况

 #include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int n;
char s[maxn];
int main() {
  cin >> n;
  cin >> s;
  int l = 0, r = 0;
  int p = 0, q = 0;
  for (int i = 0; i < n / 2; i++) {
    if (s[i] != '?') {
      l += s[i] - '0';
   } else
      p++;
 }
  for (int i = n / 2; i < n; i++) {
    if (s[i] != '?') {
      r += s[i] - '0';
   } else
      q++;
 }
  int tt = min(p, q);
  p -= tt;
  q -= tt;
  if ((p - q) / 2 * 9 == r - l)
    cout << "Bob" << endl;
  else
    cout << "Alice" << endl;
  return 0;
}

最优贸易

标签：最短路

--------------------------------------------------------------------------------------------------------

C国有 n个大城市和 m 条道路，每条道路连接这 n个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 m 条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为 1 条。

C国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。

商人阿龙来到 C 国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息之后，便决定在旅游的同时，利用商品在不同城市中的差价赚回一点旅费。设 C 国 n 个城市的标号从 1~ n，阿龙决定从 1 号城市出发，并最终在 n 号城市结束自己的旅行。在旅游的过程中，任何城市可以重复经过多次，但不要求经过所有 n 个城市。阿龙通过这样的贸易方式赚取旅费：他会选择一个经过的城市买入他最喜欢的商品――水晶球，并在之后经过的另一个城市卖出这个水晶球，用赚取的差价当做旅费。由于阿龙主要是来 C 国旅游，他决定这个贸易只进行最多一次，当然，在赚不到差价的情况下他就无需进行贸易。

假设 =C国有 5个大城市，城市的编号和道路连接情况如下图，单向箭头表示这条道路为单向通行，双向箭头表示这条道路为双向通行。

假设 1~n号城市的水晶球价格分别为 4,3,5,6,1。

阿龙可以选择如下一条线路：1->2->3->5，并在 2号城市以 3 的价格买入水晶球，在 3号城市以 5的价格卖出水晶球，赚取的旅费数为 2。

阿龙也可以选择如下一条线路 1->4->5->4->5，并在第1次到达 5 号城市时以 1的价格买入水晶球，在第 2 次到达 4 号城市时以 6 的价格卖出水晶球，赚取的旅费数为 5。

现在给出 n个城市的水晶球价格，m 条道路的信息（每条道路所连接的两个城市的编号以及该条道路的通行情况）。请你告诉阿龙，他最多能赚取多少旅费。
--------------------------------------------------------------------------------------------------------

  考试的时候想的就是枚举买点和卖点，很显然会超时，只有20pts。

 #include<bits/stdc++.h>
using namespace std;
#define re register
int a[100005],vis[100005];
vector<int> G[500005];
int n,m;
inline bool check(int x,int y) { //判断两点是否联通
	queue<int> Q;
	while(!Q.empty()) Q.pop();
	Q.push(x);
	for(re int i=1;i<=n;i++) vis[i]=0;
	while(!Q.empty()) {
		re int v=Q.front();
		Q.pop();
		if(v==y) return true;
		if(vis[v]) continue;
		vis[v]=1;
		for(re int i=0;i<G[v].size();i++) {
			re int vv=G[v][i];
			Q.push(vv);
		}
	}
	return false;
}
int main() {
	//freopen("trade.in","r",stdin);
	//freopen("trade.out","w",stdout);
	n=read(),m=read();
	for(re int i=1;i<=n;i++) {
		a[i]=read();
	}
	while(m--) {
		re int x,y,z;
		x=read(),y=read(),z=read();
		if(z==1) {
			G[x].push_back(y);
		}
		else {
			G[y].push_back(x);
			G[x].push_back(y);
		}
	}
	re int ans=0;
	for(re int i=1;i<=n;i++) {
		for(re int j=1;j<=n;j++) {
			if(a[j]-a[i]<=0) continue;
			if(check(i,j)) {
				ans=max(ans,a[j]-a[i]);
			}
		}
	}
	printf("%d",ans);
	return 0;
}

  题目本质：在走过的路中，从起点到终点的这条路径上的最小的买入价值点和最大的卖出价值点。

  仔细观察可以发现，对于最终的答案而言，我们最终走不走这个点，取决于从1 到这个点i 时价值的最小值与从点i 到点n 路上价值的最大值的价值差。因此，我们可以跑两个SPFA，一个用来求从起点出发，到另外任意一个点的最小值，另一个用来求从终点出发，到其他任意一个点的最大值，最后取所有点最大值与最小值差最大的那个，就是我们的答案。

这道题是可以重复走点的，而Dijkstra的vis数组限制不能重复

SPFA：我和你不熟