第一题
题目：
找x^{y}=target，数字特别大，可能会溢出
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
struct node {
double val;
int x, y;
bool operator<(const node& a) const {
return val < a.val;
}
};
LL w[507];
vector<node> num;
int n, m;
int binary_search(LL x) {
double key = log(x);
int l = 0, r = num.size() - 1;
while(l<=r) {
int mid = (l+r) / 2;
if(abs(num[mid].val - key) <= 1e-9) return mid;
else if(num[mid].val > key) r = mid - 1;
else l = mid + 1;
}
return -1;
}
int main()
{
cin >> n >> m;
for(int i=0; i<n; i++) cin >> w[i];
for(int i=0; i<n; i++)
for(int j=i+1; j<n; j++) {
double val = log(w[i]) * w[j];
node tmp = {val, i, j};
num.push_back(tmp);
val = log(w[j]) * w[i];
node ttmp = {val, j, i};
num.push_back(ttmp);
}
sort(num.begin(), num.end());
for(int i=0; i<m; i++) {
LL x; cin >> x;
int pos = binary_search(x);
if(pos == -1) cout << "-1 -1\n";
else cout << w[num[pos].x] << " " << w[num[pos].y] << endl;
}
return 0;
}
思路：
首先将他们的所有可能的幂以log方式保存起来，然后二分法查找log(target)和这些保存的数；如果可以找到(差距小于1e-9)，那么返回找到的x和y，否则返回-1，-1；注意target可能是long long；注意数字的范围，避免溢出问题；
第二题
题目：
x^k = y
x + y = b
(k>0, b>0) 求两条曲线在第一象限的相交面积
代码：
#include <bits/stdc++.h>
using namespace std;
int k, b;
double binary_search(int k, int b) {
double l = 0, r = b;
while(l<=r) {
double mid = (l+r) * 0.5;
if(k * log(mid) > log(1e6)) {
r = mid;
continue;
}
if(abs(mid + pow(mid, k) - b) < 1e-9) return mid;
else if(mid + pow(mid, k) > b) r = mid;
else l = mid;
}
return l;
}
int main()
{
cin >> k >> b;
double x = binary_search(k, b);
// printf("%lf %lf\n", x, x + pow(x, k));
double area = pow(x, k+1) / (k+1) + pow(x, k) * pow(x, k) * 0.5;
printf("%.6lf\n", area);
return 0;
}
思路：
首先使用二分法确定交点，然后将公式代入方程进行计算；
第三题
题目：
跳马问题，有一个起始点；给定一个矩形场地，场地中的元素要么是r，要么是b，跳马的时候只能跳日字，只能从r跳到b或者从b跳到r；求所有可以访问到的地毯数目；
代码：
int main(){
int n=3,m=3;
cin>>n>>m;
vector<vector<char>> v(n, vector<char>(m,0));
//vector<vector<char>> v={{'b','b','b'},{'b','r','b'},{'b','b','b'}};
vector<vector<int>> steps={{1,-2},{1,2},{-1,-2},{-1,2},{2,1},{2,-1},{-2,-1},{-2,1}};
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>v[i][j];
}
}
int startx=2,starty=2;
cin>>startx>>starty;
vector<vector<int>> mark(n,vector<int>(m,0));
queue<pair<int,int>> q;
q.push({startx-1,starty-1});
mark[startx-1][starty-1]=1;
int count=1;
while(!q.empty()){
pair<int,int> tmp=q.front();q.pop();
for(int i=0;i<steps.size();i++){
int newi=tmp.first+steps[i][0];
int newj=tmp.second+steps[i][1];
if(newi<0||newi>=n||newj<0||newj>=m)continue;
if(mark[newi][newj]!=0)continue;
if(v[newi][newj]!=v[tmp.first][tmp.second]){
mark[newi][newj]=1;
count+=1;
q.push({newi,newj});
}
}
}
cout<<count<<endl;
return 0;
}
思路：使用bfs，进行剪枝，遍历；
第四题
题目：
给定字符串，求STAR数目，两两字符之间不能相邻；
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 7;
LL dp[N][4];
int n;
int main()
{
cin >> n;
string str;
cin >> str;
for(int i=1; i<=n; i++) {
for(int j=0; j<4; j++) dp[i][j] = dp[i-1][j];
if(str[i-1] == 'S') dp[i][0] += 1;
else if(str[i-1] == 'T') {
if(i>=2) dp[i][1] += dp[i-2][0];
}
else if(str[i-1] == 'A') {
if(i>=2) dp[i][2] += dp[i-2][1];
}
else if(str[i-1] == 'R') {
if(i>=2) dp[i][3] += dp[i-2][2];
}
}
cout << dp[n][3] << endl;
return 0;
}
思路：使用动态规划，有四种不同的子串：分别以S, T, A, R结尾；动态规划递推式:
d[i][j]+=d[i-2][j-1]，将邻接的隔离关系表示的很好; i表示字符的位置，j表示式S,T,A,R中的哪一个；主要在于动态规划的活学活用；
第五题
题目：
小A在玩一个网络游戏，有一个抽装备环节。装备池总共有n+m件装备， 分别为n件普通装备和m件ssr装备。每次抽中一件ssr级装备，花费2元， 不放回。每次抽中一件普通装备，花费1元， 放回。所有装备抽中的概率相等。问：小A若想抽走所有ssr级装备，所有花费的期望是多少元？
代码：
#include <iostream>
using namespace std;
double ans;
int main()
{
int n, m; cin >> n >> m;
for(int i=1; i<=m; i++)
ans += 2.0 + double(n) / double(i);
printf("%.2lf\n", ans);
return 0;
}
想法：
换一种方式求解概率论；如果有n张普通卡，m张ssr卡，假设平均随机抽取N次，从期望来讲，抽到一张m卡，对应抽到n/m张普通卡；所以第m-i次抽到ssr卡的期望金币是：
2*1+1*n/i；最后结果累加，就是图中所示的结果；
