7.30 怒骂出题人的杭电4
题意
逆子张三和父亲打架,有 n 把武器,每把武器对敌人产生 a 点伤害,需要 b 时间冷却。父亲从 n 把武器中等概率选择一把,问张三获胜的最大概率是多少(平局则张三有一半的概率赢)
思路
贪心的思路,让张三选择获胜概率最大的一把武器,然后求一下该武器能赢过多少把武器,最后除一下就行了
坑点
场上因为第一轮不需要冷却时间被卡了 1e5 年QUQ
题意
给定 n 个点 m 条边的无向图,起点为 s ,终点为 t 。每个点有 L 、R 、M 三种状态,人物初始状态可以为 L 或者 M ,经过 L/R 时人物状态也需要为 L/R ,经过 M 时随意。切换状态需要时间 x 。问从 s 到 t 所花费的最短时间。
思路
这题很显然是个最短路,为处理换手时间的问题,可以采用拆点的方式,将一个点拆分为左手点和右手点(在该点的状态为左手/右手),把同一个点的左手点和右手点建立代价为 x 的双向边,然后对于读入的情况进行讨论
然后对起点分类讨论,如果起点为 L 或 R 则直接跑一遍最短路就行,否则需要令起点为 L 和起点为 R 的情况分别做最短路,取时间更小的答案。
题意
给定 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();
}
题意
给定 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);
}