微软2017年预科生计划在线编程笔试1
问题1
地址
http://hihocoder.com/contest/mstest2017march/problem/1
思路
其实每次获得legendary item都是独立的（获取之后，概率会被重置为原来的一半），所以每次计算取得一个legendary item需要的平均操作次数即可。
代码
#include <iostream>
#include <cstdio>
#include <iostream>
#include <string>
#include <iterator>
#include <algorithm>
#include <vector>
#include <cstring>
#include <array>
#include <queue>
#include <set>
#include <cmath>
#include <unordered_set>
#include <map>
using namespace std;
int P, Q, N;
double solve(double p, double q) {
p = p / 100.;
q = q / 100.;
// cout<<p<<" "<<q<<endl;
double step = p;
double res = p;
double pre = 1.;
int depth = 1;
while(true) {
pre *= (1 - step);
step += q;
depth++;
res += pre * depth * min(step, 1.);
if(step >= 1.) {
break;
}
}
return res;
}
int main()
{
scanf("%d %d %d", &P, &Q, &N);
double res = 0.;
for(int i=1;i<=N;i++) {
res += solve((double)P, (double)Q);
P /= 2;
}
printf("%.2f\n", res);
return 0;
}
问题2
地址
http://hihocoder.com/contest/mstest2017march/problem/2
思路
自底向上。首先，确认下几个规律：
- 一层最左边的结点的父节点一定是上层第一个非叶子结点；
- 相邻结点之间距离为2时，两个结点的父节点相同；
- 相邻结点之间距离大于2时，两个结点的父节点不同，但是两个结点的父节点一定相邻。
根据上面的规律，我们进行如下步骤：
- 从左到右遍历一层结点。对于一个结点，首先找到其父节点（根据上面规则）；
- 将该结点和其父结点关联；
- 对其父结点进行更新，计算该父结点与其他所有结点的距离。
注意两个问题：
- 建立的关系表是N*N的，而不是K*K的；
- 相邻两个结点的距离必须是已知的或者已经计算出来了（因为要根据这两个结点的距离来判定是否属于同一个父结点）。
代码
#include <iostream>
#include <cstdio>
#include <iostream>
#include <string>
#include <iterator>
#include <algorithm>
#include <vector>
#include <cstring>
#include <array>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
using namespace std;
int dis[110][110] = {0};
int rt[110] = {0};
int N, M, K;
void solve(vector<vector<int> >& level, unordered_set<int>& leaves) {
for(int i=level.size()-1;i>=1;i--) {
int upper = 0;
while(upper < level[i-1].size() && leaves.count(level[i-1][upper]) > 0)upper++;
for(int n=1;n<=N;n++) {
if(dis[level[i][0]][n] > 0)
dis[level[i-1][upper]][n] = dis[n][level[i-1][upper]] = dis[level[i][0]][n] - 1;
}
for(int j=0;j<level[i].size();j++) {
if(j == 0) {
rt[level[i][j]] = level[i-1][upper];
continue;
}
if(dis[level[i][j-1]][level[i][j]] != 2) {
upper++;
while(upper < level[i-1].size() && leaves.count(level[i-1][upper]) > 0) {
upper++;
}
for(int n=1;n<=N;n++) {
if(dis[level[i][j]][n] > 0)
dis[level[i-1][upper]][n] = dis[n][level[i-1][upper]] = dis[level[i][j]][n] - 1;
}
}
rt[level[i][j]] = level[i-1][upper];
}
}
}
int main()
{
scanf("%d %d %d", &N, &M, &K);
vector<int> depth(M, 0);
for(int i=0;i<M;i++)
cin>>depth[i];
vector<vector<int> > level;
for(int i=0;i<M;i++) {
vector<int> tmp;
int val;
for(int j=0;j<depth[i];j++) {
cin>>val;
tmp.push_back(val);
}
level.push_back(tmp);
}
unordered_set<int> leaves;
vector<int> l(K, 0);
for(int i=0;i<K;i++) {
int tmp;
cin>>tmp;
leaves.insert(tmp);
l[i] = tmp;
}
for(int i=0;i<K;i++) {
for(int j=0;j<K;j++) {
cin>>dis[l[i]][l[j]];
}
}
solve(level, leaves);
for(int i=1;i<=N-1;i++) {
cout<<rt[i]<<" ";
}
cout<<rt[N]<<endl;
return 0;
}
问题4
地址
http://hihocoder.com/problemset/problem/1492
思路
这个问题需要拆解成两个过程：
- 先把字符串拆成两个部分，使得字符串左边的部分的”)”多于”(“，并使得字符串右边的部分的”(“多于”)”，这样就可以分别计算。左边的只需要考虑如何添加左括号，右边的只需要考虑如何添加右括号。
- 对于左（或者右，右边其实可以反转，然后将左括号和右括号互换，就变成了右括号多于左括号的情况了）字符串部分，’)’比’(‘多，且补充的’(‘可以插入到每个’)’前面，使用
dp[i][j]表示第i个’)’前补充j个’(‘多少种方案。比如i=2, j=3，表示在第2个右括号之前的串插入3个左括号，总共有几种方案。
注意：对于插入的位置，需要考虑一个下限，比如")(()))"，第一个右括号的前面至少要插入1个左括号，所以该位置可以插入[1, max]个左括号（max为右括号比左括号多出的个数）。
代码
#include <iostream>
#include <cstdio>
#include <iostream>
#include <string>
#include <iterator>
#include <algorithm>
#include <vector>
#include <cstring>
#include <array>
#include <queue>
#include <set>
#include <unordered_set>
#include <utility>
#include <map>
using namespace std;
typedef long long ll;
pair<int, ll> calc(string& s) {
if(s == "")
return make_pair(0, 1);
int len = s.size();
int p = 0, q = 0;
int maxx = 1;
vector<int> least;
for(char c : s) {
if(c == '(') {
p++;
}
else {
q++;
least.push_back(max(0, q-p));
maxx = max(maxx, q-p);
}
}
ll dp[q + 1][maxx + 1];
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for(int i=1;i<=maxx;i++) {
dp[0][i] += dp[0][i-1];
}
for(int i=1;i<=q;i++) {
int lower = least[i-1];
for(int j=0;j<=maxx;j++) {
if(j >= lower)
dp[i][j] = dp[i-1][j];
if(j > 0) {
dp[i][j] += dp[i][j-1];
dp[i][j] %= 1000000007;
}
}
}
return make_pair(maxx, dp[q][maxx]);
}
void solve(string& s) {
int cl = 0, cr = 0;
int cr_max = 0;
int cr_max_ind = -1;
for(int i=0;i<s.size();i++) {
char c = s[i];
if(c == '(') {
cl++;
}
else{
if(cl == 0)
cr++;
else
cl--;
if(cr > cr_max) {
cr_max = cr;
cr_max_ind = i;
}
}
}
if(cl == 0 && cr == 0) {
cout<<0<<" "<<1<<endl;
return;
}
// cout<<cr_max_ind<<endl;
string sl = s.substr(0, cr_max_ind + 1);
string sr = s.substr(cr_max_ind + 1);
reverse(sr.begin(), sr.end());
for(char& c : sr)
c = c == '(' ? ')' : '(';
// cout<<sl<<" "<<sr<<endl;
pair<int, ll> l = calc(sl);
pair<int, ll> r = calc(sr);
// cout<<l.first<<l.second<<endl;
// cout<<r.first<<r.second<<endl;
cout<<l.first + r.first<<" "<<l.second * r.second % 1000000007<<endl;
}
int main()
{
// string s = "())(()))";
string s;
cin>>s;
solve(s);
return 0;
}