1004

思路：

首先是迪克特斯拉算法。

网上的博客太杂了，这个还可以，有例子有真相。（链接：www.zhihu.com/tardis/sogou/art/40338107）

我按照他的思路写了个迪克特斯拉算法：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

typedef pair<int, int> pii;

vector<vector<int> > g;
vector<pii> S;
vector<int> D, S1;

const int INF = 0x3f3f3f3f;

int T, n, s, e;

inline void ini_g()
{
int from, to;
g.resize(n + 1);
for (int i = 1; i <= n; ++i)
{
g[i].resize(n + 1);
}
for (int i = 1; i <= n; ++i)
{
cin >> from >> to;
cin >> g[from][to];
}
}

inline int Find()
{
int tmp = s, tmp1;
S[1] = { s,0 };
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
if (g[tmp][j] != INF && find(S1.begin(), S1.end(), j) == S1.end())
{
if (g[tmp][j] + S[i].second < D[j])
{
tmp1 = D[j];
D[j] = g[tmp][j] + S[i].second;
if (min(D[j], tmp1) == D[j])
{
tmp = j;
tmp1 = D[j];
}
}
}
}
if (find(S1.begin(), S1.end(), e) != S1.end())
{
return D[e];
}
S[i] = { tmp,D[i] };
S1[i] = tmp;
}
}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> T;
while (T--)
{
cin >> n >> s >> e;
S.resize(n + 1);
S1.resize(n + 1);
D.resize(n + 1, INF);
ini_g();
cout << Find();
}
return 0;
}

但是，我看到《算法导论》和网上其它的一些实现方式似乎很不一样，等之后看到相关章节再处理这个问题吧(p.s.之后我看了下书，迪克特斯拉算法的总运行时间依赖于最小优先队列的实现方式)。

其次，这道题目有左手和右手的限制，所以不能直接用迪克特斯拉算法。

但是，我们可以通过一些方法来处理左右手的限制。

容易想到，从点A到点B，若A只为L、B只为R（或者反过来），那么A、B的距R离加上换手的额外消费即可。但是，如果A、B中有M，则需要额外的考虑。

实际上，如果A为L，B为M，C为R，那么在B点换不换手无所谓（我们选择不换手，因为不换手当前最佳，这符合贪心的策略）；若A、C为L，B为M，当然在B点也是不换手。

所以，我们在遇见M之前，记下当前已找到的最短路径中最后一个M前的点的手以及当前最短路径的总长度。因为我们有理由相信，碰到M前我们找到的都是最短的路径（见上述分析）。

代码：

 

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

typedef long long ll;

typedef pair<ll, ll> pll;

vector<vector<pll> > g;
//vector<pii> S;
vector<ll> D/*, S1*/;

//这个地方我的S对应的应该就是最小优先队列p_q

struct Node
{
ll first, second;
bool operator < (const Node& b) const
{
return second > b.second;
}
};

priority_queue<Node> p_q;

const ll INF = ~0LLU >> 1;

ll T, n_v, n_r, s, e, cost;
string str;
char prehand;

inline void ini_g()
{

ll from, to;
pll tmppll;
g.resize(n_v + 1);
for (ll i = 1; i <= n_r; ++i)
{
cin >> from >> to;
tmppll.first = to;
cin >> tmppll.second;
g[from].push_back(tmppll);//此处runtime_error
}
}

inline ll Find()
{
pll tmppll;
p_q.push({ s,0 });
D[1] = 0;
prehand = str[s - 1];
while (!p_q.empty())
{
ll tmp1 = p_q.top().first;
ll tmp2 = p_q.top().second;
p_q.pop();
if (tmp2 != D[tmp1]) continue;
for (ll i = 0; i < g[tmp1].size(); ++i)
{
tmppll = g[tmp1][i];
if ((str[g[tmp1][i].first - 1] == prehand || str[g[tmp1][i].first - 1] == 'M') && D[tmp1] + tmppll.second < D[tmppll.first])
{
D[tmppll.first] = D[tmp1] + tmppll.second;
p_q.push({ tmppll.first,D[tmppll.first] });
}
else if(str[g[tmp1][i].first - 1] != prehand && D[tmp1] + tmppll.second + cost < D[tmppll.first])
{
D[tmppll.first] = D[tmp1] + tmppll.second + cost;
p_q.push({ tmppll.first,D[tmppll.first] });
}
}
if (str[tmp1 - 1] != 'M')
{
prehand = str[tmp1 - 1];
}
}
return D[e];
}

//inline int my_find()
/*inline int Find()
{
int tmp = s, tmp1, tmp2 = tmp;
S[1] = { s,0 };
prehand = str[s - 1];
for (int i = 1; i <= n_v; ++i)
{
for (int j = 0; j < g[tmp].size(); ++j)
{
if (find(S1.begin(), S1.end(), g[tmp][j].first) == S1.end())
{
if ((str[g[tmp][j].first - 1] == prehand || str[g[tmp][j].first - 1] == 'M') && g[tmp][j].second + S[i].second < D[g[tmp][j].first])
{
tmp1 = D[g[tmp][j].first];
D[g[tmp][j].first] = g[tmp][j].second + S[tmp].second;
}
else if (str[g[tmp][j].first - 1] != prehand && g[tmp][j].second + S[i].second + cost < D[g[tmp][j].first])
{
tmp1 = D[g[tmp][j].first];
D[g[tmp][j].first] = g[tmp][j].second + S[tmp].second + cost;
}
if (min(D[j], tmp1) == D[j])
{
tmp2 = g[tmp][j].first;
tmp1 = D[g[tmp][j].first];
}
}
}
if (find(S1.begin(), S1.end(), e) != S1.end())
{//
return D[e];
}
S[i] = { tmp2,D[i] };
S1[i] = tmp2;
if(str[tmp2-1]!='M')
{
prehand = str[tmp2 - 1];
}
}
}*/

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> T;
while (T--)
{
cin >> n_v >> n_r >> s >> e >> cost;
cin >> str;
//S.resize(n_v + 1);
//S1.resize(n_v + 1);
D.resize(n_v + 1, INF);
ini_g();
cout << Find() << '\n';
}
return 0;
}

1011

思路：

通过代码：

#include<iostream>
using namespace std;

int main()
{
int T;
double a, b, d, t;
cin >> T;
while (T--)
{
cin >> a >> b >> d >> t;
cout << d << '\n';
}

}

1002

思路：

先算出每种武器的杀敌时间（（开枪次数-1）*每枪时间）；张三一定是选最厉害的武器，也就是说，他爸爸不选和他一样厉害的武器就一定会输。统计最厉害的武器数m，张三获胜的概率为（（n-m）/n   +    m/（2*n））。

通过代码：

#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;

struct Node
{
int k, a, b;
};

int T, n, m;//m为最厉害的武器总数
vector<Node> v;

bool cmp(Node a, Node b)
{
return a.k < b.k;
}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> T;
while (T--)
{
m = 0;
cin >> n;
v.resize(n + 1);
for (int i = 1; i <= n; ++i)
{
cin >> v[i].a >> v[i].b;
v[i].k = (ceil(100.0 / v[i].a) - 1) * v[i].b;//开局可攻击一次
}
sort(v.begin(), v.end(), cmp);
for (int i = 1; i <= n; ++i)
{
if (v[i].k == v[1].k) ++m;
else break;
}
cout << (double)(n - m) / n + (double)m / (2 * n) << '\n';
}
return 0;
}

1005

思路：

要求某字符串近似相等的个数。可以想象，一字符串中，交换任意相邻的两位，所得到的是与原字符串近似相等的字符串（但以下情况例外：1.交换的两字符相等；2.交换的两字符中有被交换过的字符）。基于此，我们可以说：假设有一字符串S，子串S[1…i]（1<=i<=n)的近似相等的字符串的个数ans[i]=ans[i]+ans[i-2](其中，ans[i]的初值为ans[i-1])。例如，对于S="abc",当i=1时，ans[1]=1；当i=2时，ans[2]=2("ab"、"ba")；当i=3时，ans[3]=ans[2]+ans[3-2]=3("abc"、"acb"、"bac")。

通过代码：

#include<iostream>
#include<string>
#include<vector>
using namespace std;

const int MOD = 1e9 + 7;

int T, n;
vector<int> ans;
vector<string> str;

int func()
{
for (int i = 1; i <= n; ++i)
{
ans[i] = ans[i - 1];
if (i >= 2 && str[i] != str[i - 1])
{
ans[i] = (ans[i] + ans[i - 2]) % MOD;
}
}
return ans[n];
}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> T;
while (T--)
{
cin >> n;
str.resize(n + 1);
ans.resize(n + 1, 1);
for (int i = 1; i <= n; ++i)
{
cin >> str[i];
}
cout << func() << '\n';
}
return 0;
}