L暴击率

题意：给出n个物品和m个硬币，每个物品有概率p,暴击率v,花费w。你可以用m个硬币买物品（每个不超过一个），在在所有可能情况中，当多个装备同时触发暴击时，只有最高的暴击倍率生效。求可能得到的最大期望。

本题为概率DP（01背包变式）

        考虑01背包可以求取当花费j个硬币时期望的最优解（1 <= j <= m）本题要求最大期望，可以遍历所有j个硬币的期望取最大值来求解
（这题和01背包不同的地方就是01背包当花费越大时，能够获得的价值是递增的，但是这道题中当花费越大时，期望不一定是全局最大的，只能说是该花费时的最优解，因此要遍历求最大值）
           为什么说这题是概率dp呢？其实就是在求解最优解时我们需要对暴击率从小到大排序，这样去枚举每个物品时，只会出现俩种情况：假设该物品为i,且暴击率为pr，一种是该物品暴击了，那么它对总期望的贡献就是pr*v;另外一种情况是该物品没暴击，那么它对期望的贡献是前一个期望最优解 dp[i-1]*(1-pr)，因此，dp转移式为：
            

其中j为硬币数，完整代码如下：
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct pi{
    double p,v,cst;
};
bool cmp(pi a,pi b){
    return a.v<b.v;
}
void solve(){
    int n,w;
    cin>>n>>w;
    vector<pi> a;
    for(int i=1;i<=n;i++){
        double p,v,cst;
        cin>>p>>v>>cst;
        a.push_back({p,v,cst});
    }
    sort(a.begin(),a.end(),cmp);
    vector<double> dp(w+10,0.0);
    for(int i=0;i<n;i++){
        double pr=1.0*a[i].p/100.0;
        for(int j=w;j>=a[i].cst;j--){
            dp[j]=max(dp[j],dp[j-a[i].cst]*(1.0-pr)+a[i].v*pr);
        }
    }
    double ans=-1e18;
    for(int i=0;i<=w;i++)ans=max(ans,dp[i]);
    cout<<fixed<<setprecision(12)<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int _=1;
    cin>>_;
    while(_--){
        solve();
    }
}

G贪吃蛇吃苹果

题意：（本题为交互题）给出n*m的网格，贪吃蛇初始长度为1，可以用UDLR来表示头向上下左右4个方向移动，给出起点坐标，之后每次给出一个苹果坐标，一个给出n*m-1次，要求蛇不能越界并且不能碰到自己的身体，每给出一个苹果打出一个字符串表示蛇的移动过程，要求吃掉所有苹果。

本题为构造

相信大家很容易想到，在存在一边长度大小为偶数的情况下，可以构造出哈密顿回路：
只要蛇一直沿着该哈密顿回路走总是能吃掉苹果，之后就是本题最难的点：如何处理奇数*奇数的情况：
首先，交互题有一个特点，你可以自适应它给出的数据，那就意味着你可以根据它给出的坐标修改你的实现方式。然后我们就开始思考能否在奇数*奇数网格中构造出类似的哈密顿回路并能够根据坐标位置进行调整。相信聪明的你这时候会想到这种情况：（构造题的特性：灵光一闪！！）

我们可以在一个拐角预留出一个格子，其余格子构成一个哈密顿回路，此时就可以充分利用交互题的特性：交互！！
具体代码就是先打表，然后奇数*奇数的时候根据苹果坐标特判即可。完整代码如下：
#include<bits/stdc++.h>
using namespace std;
int n,m,stx,sty;
vector<vector<char>> e(105,vector<char>(105));
struct pi{
    int x,y;
};
pi query(int sx,int sy,bool isji){
    int curx=sx,cury=sy;
    int x,y;
    cin>>x>>y;
    if(isji){
        if(e[1][2]=='D'){
            if(x==1 && y==1)e[1][2]='L';
        }else{
            if(x==2 && y==2)e[1][2]='D';
        }
    }
    while(!(curx==x && cury==y)){
        cout<<e[curx][cury];
        if(e[curx][cury]=='L'){
            cury--;
        }else if(e[curx][cury]=='R'){
            cury++;
        }else if(e[curx][cury]=='U'){
            curx--;
        }else{
            curx++;
        }
    }
    cout<<endl;
    return {x,y};
    
}
void solve(){
    cin>>n>>m>>stx>>sty;
    pi point={stx,sty};
    if(n%2==0 || m%2==0){
        if(n%2==0){
            for(int i=1;i<=n;i++)e[i][1]='D';
            for(int i=1;i<=n;i++){
                for(int j=2;j<=m;j++){
                    if(i==1)e[i][j]='L';
                    else if(i%2==0){
                        if(j!=m)e[i][j]='R';
                        else e[i][j]='U';
                    }else{
                        if(j!=2)e[i][j]='L';
                        else e[i][j]='U';
                    }
                }
            }
            e[n][1]='R';
        }else{
            for(int j=1;j<=m;j++)e[n][j]='R';
            for(int j=1;j<=m;j++){
                for(int i=1;i<=n-1;i++){
                    if(j==1)e[i][j]='D';
                    else if(j%2==0){
                        if(i!=1)e[i][j]='U';
                        else e[i][j]='L';
                    }else{
                        if(i!=n-1)e[i][j]='D';
                        else e[i][j]='L';
                    }
                }
            }
            e[n][m]='U';
        }
        for(int i=1;i<=n*m-1;i++){
            int curx=point.x,cury=point.y;
            point=query(curx,cury,false);
        }
    }else{
        for(int j=1;j<m;j++)e[n][j]='R';
        e[n][m]='U';
        for(int j=3;j<=m;j++){
            for(int i=1;i<=n-1;i++){
                if(j%2==1){
                    if(i!=1)e[i][j]='U';
                    else e[i][j]='L';
                }else{
                    if(i!=n-1)e[i][j]='D';
                    else e[i][j]='L';
                }
            }
        }
        e[1][1]='D';e[1][2]='D';
        for(int i=2;i<=n-1;i++){
            if(i%2==0){
                e[i][1]='D';e[i][2]='L';
            }else{
                e[i][1]='R';e[i][2]='D';
            }
        }
        for(int i=1;i<=n*m-1;i++){
            int curx=point.x,cury=point.y;
            point=query(curx,cury,true);
        }
    }
    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=m;j++)cout<<e[i][j]<<' ';
    //     cout<<'\n';
    // }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int _=1;
    cin>>_;
    while(_--){
        solve();
    }
}

D工厂管理

题意：给出n天，每天可以开一家工场，且告诉你工场一天可以生产的价值v或者招进一名工人。对于建工程的那一天你可以把闲置工人放到该工场（一个工场只能有一名工人），不可改变原先已经有工作的工人。对于一名新进的工人，你可以在这一天调配所有的工人，来使最终的产值最大化（可以预留工人），输出n天后最大的产值

本题为数据结构+反悔贪心（具体可以是线段树，对顶堆，树状数组）