第四场题解

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;
}

 

上一篇:Codeforces Round #587 White Sheet(几何覆盖)


下一篇:UVA 10763 Foreign Exchange