做了indeed秋招的第一场笔试，题目相比别家确实简单。其中前三道完全是水题，记录一下~
第一题：Tabereru
题意：给定一个字符串，遇到"ra"需要删除，但是删除之后如果又出现了"ra"那么不继续删除了。即如果输入是rrraaa，那么输出是rraa。
思路：字符串很短，随便搞就OK。
第二题：Matrix Product
题意：就是裸的矩阵乘法，复杂度不需要任何优化，O(n^3)即可。
第三题：Ancient Formula
题意：给定不超过6个数，其中有5个空位可以添加加号+或者乘号*，求值的时候不考虑优先级，即2+3*4=20。再给定一个整数k，问这6个数的某种排列以及某种加符号方式下，与k的差的绝对值的最小值(即与k的接近程度)。
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <iostream>
#define N 505
#define INF 0x7fffffff
using namespace std;
int n,k,res = INF;
vector<int> s;
void solve(vector<int> &s,int d,int now){
if(d == s.size()){
res = min(res,abs(now-k));
return;
}
solve(s, d+1, now+s[d]);
solve(s, d+1, now*s[d]);
}
void dfs(vector<int> &s,int d,vector<bool> &used,vector<int> &tmp){
if(d == s.size()){
solve(tmp, 1, tmp[0]);
return;
}
for(int i = 0;i<s.size();i++){
if(!used[i]){
tmp[d] = s[i];
used[i] = true;
dfs(s, d+1, used, tmp);
used[i] = false;
}
}
}
int main(){
scanf("%d %d",&n,&k);
for(int i = 0;i<n;i++){
int x;
scanf("%d",&x);
s.push_back(x);
}
if(n == 1){
printf("%d\n",abs(s[0]-k));
return 0;
}
vector<bool> used(s.size(),false);
vector<int> ans(s.size());
dfs(s,0,used,ans);
printf("%d\n",res);
return 0;
}
第四题：Painting
题意：输入n(n<=100000)，表示n个白球在一条线上。每次等概率在不与黑球相邻的白球中选择一个置为黑球，直到没有这样的白球。问最后剩下的黑球的期望。输出float，精度10e-8之内。
样例：n=1和2下显然期望为1。n=3的时候，第一次有2/3的概率选择两边的白球，此时必然会选择第二个白球（另一边的边上）；第一次还有1/3的概率选择中间的球，此时只会选择这一个球，最终的期望是5/3。
思路：dp咯。一个显然的dp如下：dp[x]表示初始有x个白球的期望。分类第一个白球选择的位置（1~n）：如果选在了最边上的1号球，那么剩下变成了在3~n中继续选球；如果选择了2号，那么接下来在4~n中选择；如果选择了3号，那么接下来在1号以及5~n号中选择；同理，如果选择的是i号球，那么接下来从1~i-2和i+2~n中分别选择。但是这个dp的复杂度是O(n^2)级别的，太高了。
如何降到O(n)？考虑上述dp的结果(为方便令dp[0]=0)，通过一个具体的例子解释吧：n=6的时候dp(x)=1/3(1 + dp(4)) + 1/3(1 + dp(0) + dp(3)) + 1/3(1 + dp(1) + dp(2)) = 1/3 * (3+dp(0)+...+dp(4))。推广到一般的偶数x,dp(x) = (2/x)*(x/2 + dp(0) + ... + dp(x-2))。同理可以推得n为奇数时候的公式，可知与前n项和有关，记录一下即可。这样的dp复杂度就降低为O(n)啦。
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <iostream>
#define N 100005
#define INF 0x7fffffff
using namespace std;
int n;
double dp[N];
int main(){
scanf("%d",&n);
for(int i = 2;i<=n;i++)
dp[i] = -1;
dp[0] = 0;
dp[1] = dp[2] = 1;
double sum = 1;
for(int i = 3;i<=n;i++){
if(i&1)
dp[i] = (sum-dp[(i-3)>>1]+i/2)*2/i + (1+2*dp[(i-3)>>1])/i;
else
dp[i] = (sum+(i>>1))/(i>>1);
sum += dp[i-1];
}
printf("%.10lf\n",dp[n]);
return 0;
}
实际上对于奇数情况，如果把式子乘出来再次化简，可以得到和偶数相同的形式，而且求dp[i]的时候只与前i-2项的和有关，从而连dp这个数组也可以省略：代码如下：
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <iostream>
#define N 100005
#define INF 0x7fffffff
using namespace std;
int n;
int main(){
scanf("%d",&n);
double res = 1, sum = 1;
for(int i = 3;i<=n;i++){
double tmp = res;
res = 2.*sum/i + 1;
sum += tmp;
}
printf("%.10lf\n",res);
return 0;
}