2020 Multi-University Training Contest 4
2020 Multi-University Training Contest 4
7.30 怒骂出题人的杭电4
1002-Blow up the Enemy
题意
逆子张三和父亲打架，有 n 把武器，每把武器对敌人产生 a 点伤害，需要 b 时间冷却。父亲从 n 把武器中等概率选择一把，问张三获胜的最大概率是多少（平局则张三有一半的概率赢）
思路
贪心的思路，让张三选择获胜概率最大的一把武器，然后求一下该武器能赢过多少把武器，最后除一下就行了
坑点
场上因为第一轮不需要冷却时间被卡了 1e5 年QUQ
1004-Deliver the Cake
题意
给定 n 个点 m 条边的无向图，起点为 s ，终点为 t 。每个点有 L 、R 、M 三种状态，人物初始状态可以为 L 或者 M ，经过 L/R 时人物状态也需要为 L/R ，经过 M 时随意。切换状态需要时间 x 。问从 s 到 t 所花费的最短时间。
思路
这题很显然是个最短路，为处理换手时间的问题，可以采用拆点的方式，将一个点拆分为左手点和右手点（在该点的状态为左手/右手），把同一个点的左手点和右手点建立代价为 x 的双向边，然后对于读入的情况进行讨论
- (u, v) 为 MM 情况时，将两点的左手连左手，右手连右手即可
- (u, v) 为 MR 或 ML 情况时，v 为 L 时，将 u_左 和 v_左 相连；v 为 R 时，将 u_右 和 v_右 相连（双向）
- (u,v) 为 RM 或 LM 情况时，u 为 L 时，将 u_左 和 v_左 相连；u 为 R 时，将 u_右 和 v_右 相连（双向）
- (u,v) 为 RL 或 LR 情况时，u 为 L 时，将 u_右 和 v_右 相连，v_左 和 u_左 相连（单向）；u 为 R 时，将 u_左 和 v_左 相连，v_右 和 u_右相连（单向）；
然后对起点分类讨论，如果起点为 L 或 R 则直接跑一遍最短路就行，否则需要令起点为 L 和起点为 R 的情况分别做最短路，取时间更小的答案。
1005-Equal Sentences
题意
给定 n 个单词，问这些单词错排能有几种情况。错排指在单词集相同的情况下，每个单词第 i 次出现位置与原串相差不超过 1 。
思路
转换题意为：两两相邻且不相同的值才能交换。每个单词编号后记忆化搜索即可。
代码
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define rep(i,s,e) for(int i=(s); i<(e); ++i)
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
char s[15];
int a[maxn]; ll f[maxn];
map<string,int>aaa;
ll qaq(int n){
if(f[n]) return f[n];
if(n==1) return f[1]=1;
if(n==2) return f[2]=(a[1]==a[2]?1:2);
if(a[n]==a[n-1]) return f[n]=qaq(n-1);
return f[n]=(qaq(n-1)+qaq(n-2))%mod;
}
int solve(){
int n,cnt(0); sc(n); aaa.clear(); rep(i,1,n+1){
scs(s); if(!aaa.count(s)) aaa[s]=++cnt; a[i]=aaa[s]; f[i]=0;
} return pf("%lld\n",qaq(n));
}
int main(){
int _; sc(_); while(_--) solve();
}1012-Last Problem
题意
给定 n 种颜色，问按题意给的涂色方式涂色后包含 n 的方案。涂色方式是：涂 x 时，四周颜色需要是 (x−1, x−2, x−3, x−4) ，其中负数的情况不考虑。
思路
每次把所需涂色的点的周围所需颜色染上，由此想到递归求解。但是纯递归会步骤过多，所以用 map 存一下当前点是否已被涂上所需颜色。注意：为使操作序列尽量短，应将 n-1 和 n-4 相对，n-2 和 n-3 相对，可参考题解中的图。
代码
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=(s); i<(e); ++i)
#define dep(i,e,s) for(int i=(e); i>=(s); --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e4 + 5;
const int mod = 1e9 + 7;
map<pii,int>mp;
void dfs(int x,int y,int t){
if(t<=0) return;
if(mp[pii(x-1,y)]!=t-1) dfs(x-1,y,t-1);
if(mp[pii(x,y-1)]!=t-2) dfs(x,y-1,t-2);
if(mp[pii(x,y+1)]!=t-3) dfs(x,y+1,t-3);
if(mp[pii(x+1,y)]!=t-4) dfs(x+1,y,t-4);
mp[pii(x,y)]=t; pf("%d %d %d\n",x,y,t);
}
int main(){
/* int _; sc(_); while(_--) */ dfs(0,0,100);
}