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$ 。

思路

转换题意为:两两相邻且不相同的值才能交换。每个单词编号后记忆化搜索即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#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$ 相对,可参考题解中的图。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#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);
}