CSP

sscanf()
sprintf()
stringstream
substr(i,k) 返回从i开始的k个字符的子串
substr(i) 返回从i开始到末尾的子串
strstr()
string s; s.find("山西") 找不到返回-1，
stoi(s):  string转换到int
stoll(s): string转换到long long
stof(s):  string转换到float
char s[N] -> 变为int 用:atoi(s)
isdigit('1') :判断一个字符是不是数字
tolower('A') :将一个大写字母变成小写字母
toupper('a') :将一个小写字母变成大写字母
inline: 函数优化
register: 变量优化

犯过的错误

1. 数据范围：int long
2. 输出： 输出位数, 输出顺序
3. 如果可以证明自己的做法是正确的

3300. 食材运输

在 T 市有很多个酒店，这些酒店对于不同种类的食材有不同的需求情况，莱莱公司负责每天给这些酒店运输食材。
由于酒店众多，如何规划运输路线成为了一个非常重要的问题。你作为莱莱公司的顾问，请帮他们解决这个棘手的问题。
T 市有 N 个酒店，这些酒店由 N−1 条双向道路连接，所有酒店和道路构成一颗树。
不同的道路可能有不同的长度，运输车通过该道路所需要的时间受道路的长度影响。
在 T 市，一共有 K 种主流食材。
莱莱公司有 K 辆车，每辆车负责一种食材的配送，不存在多辆车配送相同的食材。
由于不同酒店的特点不同，因此不同酒店对食材的需求情况也不同，比如可能 1 号酒店只需要第 1,5 种食材， 2 号酒店需要全部的 K 种食材。
莱莱公司每天给这些公司运输食材。
对于运输第 i 种食材的车辆，这辆车可以从任意酒店出发，然后将食材运输到所有需要第 i 种食材的酒店。
假设运输过程中食材的装卸不花时间，运输车足够大使得其能够在出发时就装满全部所需食材，并且食材的重量不影响运输车的速度。
为了提高配送效率，这 K 辆车可以从不同的酒店出发。
但是由于 T 市对于食品安全特别重视，因此每辆车在配送之前需要进行食品安全检查。
鉴于进行食品安全检查的人手不足，最多可以设置 M 个检查点。
现在莱莱公司需要你制定一个运输方案：选定不超过 M 个酒店设立食品安全检查点，确定每辆运输车从哪个检查点出发，规划每辆运输车的路线。
假设所有的食材运输车在进行了食品安全检查之后同时出发，请制定一个运输方案，使得所有酒店的等待时间的最大值最小。
酒店的等待时间从运输车辆出发时开始计算，到该酒店所有需要的食材都运输完毕截至。
如果一个酒店不需要任何食材，那么它的等待时间为 0。
输入格式
第一行包含 3 个正整数 N,M,K，含义见题目描述。
接下来 N 行，每行包含 K 个整数。每行输入描述对应酒店对每种食材的需求情况，1 表示需要对应的食材， 0 表示不需要。
接下来 N−1 行，每行包含 3 个整数 u,v,w，表示存在一条通行时间为 w 的双向道路连接 u 号酒店和 v 号酒店。
保证输入数据是一颗树，酒店从 1 编号到 N。
输出格式
输出一个整数，表示在你的方案中，所有酒店的等待时间的最大值。

#include <iostream>
#include <cstring>
#include <algorithm>
#define x first
#define y second
#include <vector>
using namespace std;
typedef pair<int, int> PII;
const int N = 110,M = 1<<10,K=11;
bool need[N][K];   // need[i][j]第i家店对j种食材的需求情况
int dist[N][K];    // dist[i][j]从第i家店出发，运送j种食材的最短时间
int state[N];      // 用于状态压缩dp
int f[M];
int n,m,k;
vector<PII>h[N];  
PII dfs(int u,int fa,int k){  // 预处理dist数组
    PII res={0,-1};
    if(need[u][k]){
        res.y=0;
    }
    for (int i = 0; i < h[u].size(); i ++ ){
        int j = h[u][i].x;
        int w = h[u][i].y;
        if(j==fa){
            continue;
        }
        auto t = dfs(j,u,k);
        if(t.y!=-1){
            res.x += t.x + 2*w;
            res.y = max(res.y, t.y + w);
        }
    }
    return res;
}
bool check(int mid){    // 在时间为mid的情况下，选择最多选择k个起始点，能否送完所有食材
    memset(state, 0, sizeof state);
    memset(f, 0x3f, sizeof f);
    for (int i = 1; i <= n; i ++ ){
        for (int j = 0; j < k; j ++ ){
            if(dist[i][j]<=mid){
                state[i]|=1<<j;
            }
        }
    }
    f[0]=0;
    for (int i = 0; i < 1<<k; i ++ ){
        for (int j = 1; j <= n; j ++ ){
            f[i|state[j]] = min(f[i|state[j]],f[i]+1);
        }
    }
    return f[(1<<k)-1]<=m;
}
int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i<= n; i ++ ){
        for (int j = 0; j < k; j ++ ){
            cin >> need[i][j];
        }
    }
    for (int i = 0; i < n-1; i ++ ){
        int a,b,c;
        cin >> a >> b >> c;
        h[a].push_back({b,c});
        h[b].push_back({a,c});
    }
    for (int i = 1; i <= n; i ++ ){
        for (int j = 0; j < k; j ++ ){
            auto t = dfs(i,-1,j);
            if(t.y!=-1){
                dist[i][j] = t.x - t.y;
            }
        }
    }
    int l = 0,r = 2e8;
    while(l<r){
        int mid = l + r >> 1;
        if(check(mid)){
            r = mid;
        }else{
            l = mid+1;
        }
    }
    cout << l;
}

4009. 收集卡牌

小林在玩一个抽卡游戏，其中有 n 种不同的卡牌，编号为 1 到 n。
每一次抽卡，她获得第 i 种卡牌的概率为 pi。
如果这张卡牌之前已经获得过了，就会转化为一枚硬币。
可以用 k 枚硬币交换一张没有获得过的卡。
小林会一直抽卡，直至集齐了所有种类的卡牌为止，求她的期望抽卡次数。
如果你给出的答案与标准答案的绝对误差不超过 10−4，则视为正确。
提示：聪明的小林会把硬币攒在手里，等到通过兑换就可以获得剩余所有卡牌时，一次性兑换并停止抽卡。
输入格式
输入共两行。
第一包含两个用空格分隔的正整数 n,k，第二行给出 p1,p2,…,pn，用空格分隔。
输出格式
输出共一行，一个实数，即期望抽卡次数。
数据范围
对于 20% 的数据，保证 1≤n,k≤5。
对于另外 20% 的数据，保证所有 pi 是相等的。
对于 100% 的数据，保证 1≤n≤16,1≤k≤5，所有的 pi 满足 pi≥110000，且 ∑ni=1pi=1。
注意，本题在官网必须保留 10 位小数才能通过（可能是没加SPJ），在本网站无此问题，只要满足你给出的答案与标准答案的绝对误差不超过 10−4，则视为正确。
输入样例1：
2 2
0.4 0.6
输出样例1：
2.52
样例1解释
共有 2 种卡牌，不妨记为 A 和 B，获得概率分别为 0.4 和 0.6，2 枚硬币可以换一张卡牌。下面给出各种可能出现的情况：
第一次抽卡获得 A，第二次抽卡获得 B，抽卡结束，概率为 0.4×0.6=0.24，抽卡次数为 2。
第一次抽卡获得 A，第二次抽卡获得 A，第三次抽卡获得 B，抽卡结束，概率为 0.4×0.4×0.6=0.096，抽卡次数为 3。
第一次抽卡获得 A，第二次抽卡获得 A，第三次抽卡获得 A，用硬币兑换 B，抽卡结束，概率为 0.4×0.4×0.4=0.064，抽卡次数为 3。
第一次抽卡获得 B，第二次抽卡获得 A，抽卡结束，概率为 0.6×0.4=0.24，抽卡次数为 2。
第一次抽卡获得 B，第二次抽卡获得 B，第三次抽卡获得 A，抽卡结束，概率为 0.6×0.6×0.4=0.144，抽卡次数为 3。
第一次抽卡获得 B，第二次抽卡获得 B，第三次抽卡获得 B，用硬币兑换 A，抽卡结束，概率为 0.6×0.6×0.6=0.216，抽卡次数为 3。
因此答案是 0.24×2+0.096×3+0.064×3+0.24×2+0.144×3+0.216×3=2.52。
输入样例2：
4 3
0.006 0.1 0.2 0.694
输出样例2：
7.3229920752

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef double LL;
const int N = 1<<16,M = 6;
int n,k;
LL p[16];
LL f[N][16*6];  //记忆化搜索,期望,   状态和钱
bool g[N][16*6];
LL dfs(int state,int money,int len){ //表示手中还没有的牌的数量
    if(g[state][money]){  //说明这种情况已经计算过
        return f[state][money];
    }
    if(state==(1<<n)-1){     //到叶子节点了
        return 0;
    }
    // 手里钱够兑换全部
    if(len*k<=money){
        return 0;
    }
    LL res=0;
    for (int i = 0; i < n; i ++ ){
        int c = (state>>i)&1;
        if(!c){ //找手中还没有的牌
            LL t = dfs(state|(1<<i),money,len-1);
            res += (t+1)*p[i];
        }else{
            LL t = dfs(state,money+1,len);
            res += (t+1)*p[i];
        }
    }
    g[state][money] = true;
    f[state][money] = res;
    return res;
}
int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i ++ ){
        cin >>p[i];
    }
    memset(g, 0, sizeof g);
    LL t = dfs(0,0,n);
    printf("%.10lf",t);
}