今天的题目还是老样子。。250p的简单，500p的依旧难想，直到晚上参考了一下下一大神的代码才豁然开朗，哎，什么时候才能在有限的一个小时内A出500p！加油！
250p：
题意：
有一副扑克牌，没有大小王，2到9的值分别是各自的数字，10、J、Q、K值为10，A值为11，给你一些扑克牌，让你从剩下的扑克牌中选新的牌放进去，一旦所有已有的牌的总值大于20，就不能再取了，问你取的次数的期望值。
解题思路：
简单的dfs，用vis数组来记录下每种牌还剩多少张，直接搜起~
500p：
题意：
这个题的题意说起来还真是有点复杂。。。刚开始你有一个卡片组，从顶部到底部编号1~n，把这个最初的卡片称成为主卡片组，另外还有三个卡片组，分别为左卡片组、右卡片组、结果卡片组，刚开始这三个都是空的。接下来要对这些卡片组重复进行以下操作直到主卡片组的卡片数少于两个：
1. 把主卡片组的最顶部的卡片移到左卡片组的顶部，再把主卡片组的最顶部的卡片移到有卡片组的顶部，重复这两个操作直到主卡片组为空了。
2.对左卡片组重复进行left(题目条件)次操作：把左卡片组最顶部的卡片移到最底部
3.对右卡片组重复进行right(题目条件)次操作：把右卡片组最顶部的卡片移到最底部
4.把左卡片组最顶部的卡片移到结果卡片组的最顶部
5.把右卡片组最顶部的卡片移到结果卡片组的最顶部
6.把左卡片组最顶部的卡片移到主卡片组的顶部，重复操作直到左卡片组为空
7.把右卡片组最顶部的卡片移到主卡片组的顶部，重复操作直到右卡片组为空
如果主卡片组最终剩了一张卡片，把这个卡片移到结果卡片组的顶部。
返回结果卡片组最顶部的卡片的编号。
解题思路：
我拿到这个题，一直在想怎么把每一次移到结果卡片组的两张卡片找出来。。。每次移了两个卡片，这个的确是一个非常重要的性质，但是我却一直忽略了最根本的性质，所以一直在歪路了，怎么也想不出。。。
其实这样来看，假设我们已经求得了ans[5] (表示5张卡片的时候的答案)，然后要求n = 7的答案，这个一次大操作后少了两张，而主卡片组里还剩下5张卡片，这样回到了5张卡片的情况，我们把它看成新的5张卡片。而我们已经求得了ans[5]，也就是说ans[7]就是新的5张卡片对应着ans[5]的位置的编号，这样其实很好找了。初始的ans[1]
= 1， ans[2] = 2，ans[n] 就可以由ans[n-2]递推出。需要注意ans[i-2]在左卡片组和右卡片组的情况不一样，具体见以下代码。
250p code:
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <sstream>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
template <class T> void checkmax(T &t, T x) { if (x > t) t = x; }
template <class T> void checkmin(T &t, T x) { if (x < t) t = x; }
template <class T> void _checkmax(T &t, T x) { if (t == -1 || x > t) t = x; }
template <class T> void _checkmin(T &t, T x) { if (t == -1 || x < t) t = x; }
typedef long long ll;
class TheBlackJackDivOne {
public:
double expected(vector <string> cards) ;
};
int vis[22];
double ans;
void dfs(double cal, int cnt, int now, int got) {
int i;
for(i = 2;i <= 11; i++) {
if(cnt + i < 21 && vis[i]) {
vis[i]--;
dfs(cal*(vis[i]+1)/now, cnt+i, now-1, got+1);
vis[i]++;
}
}
int sum = 0;
for(i = 2;i <= 11; i++) {
if(cnt+i >= 21) sum += vis[i];
}
ans += cal*sum/now*(got+1);
}
double TheBlackJackDivOne::expected(vector <string> cards) {
int i;
memset(vis, 0, sizeof(vis));
for(i = 2;i <= 9; i++) vis[i] = 4;
vis[10] = 16;
vis[11] = 4;
int n = cards.size();
int cnt = 0, cur;
for(i = 0;i < n; i++) {
if(cards[i][0] >= '2' && cards[i][0] <= '9') cur = cards[i][0] - '0';
else if(cards[i][0] == 'A') cur = 11;
else cur = 10;
vis[cur] --;
cnt += cur;
}
ans = 0;
if(cnt >= 21) return ans;
dfs(1.0, cnt, 52-n, 0);
return ans;
}
500p code:
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <sstream>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
template <class T> void checkmax(T &t, T x) { if (x > t) t = x; }
template <class T> void checkmin(T &t, T x) { if (x < t) t = x; }
template <class T> void _checkmax(T &t, T x) { if (t == -1 || x > t) t = x; }
template <class T> void _checkmin(T &t, T x) { if (t == -1 || x < t) t = x; }
typedef long long ll;
class TheCardShufflingDivOne {
public:
int shuffle(int n, int left, int right) ;
};
int ans[1000005];
int TheCardShufflingDivOne::shuffle(int n, int left, int right) {
ans[1] = 1;
ans[2] = 2;
int i;
for(i = 3;i <= n; i++) {
if(ans[i-2] > (i-2)/2) { // ans[i-2] 在左卡片组的情况
int cnt = (i+1)/2; // 分到左边的个数
int id = ans[i-2] - (i-2)/2;
id = (id + cnt - left%cnt)%cnt;
if(id == 0) id = cnt;
ans[i] = id*2-1;
}
else { // 在右卡片组的情况
int cnt = i/2;
int id = ans[i-2];
id = (id + cnt - right%cnt)%cnt;
if(id == 0) id = cnt;
ans[i] = id*2;
}
}
return ans[n];
}