2021牛客暑期多校训练营5（B.期望 G.暴力）

这场感觉需要记录的东西貌似不是很多，所以写个总的。

B.Boxes

根据贪心原则，其实我们可以注意到两点：
1、是否要提示是开始前决定的。要么，你一开始不要提示，全部盒子都开一次。要么，先要提示，根据提示的数量开盒子。因为假若你中途再要提示，可能要到后发现盒子开多了，还不如一开始就要，花费只多不少。
2、要了提示后，你一定是按照盒子价值从小到大开的。因为你开一个盒子都是的概率白或黑，因此从总体来说，从小往大开的话，期望的花费会比较少（可以往下看看期望的计算自己思考下）。
显然，如果不要提示，则期望为。
若要提示，则就要分情况了。
因为有了提示，你就知道有几个白几个黑，这时候，你会在中途因为开够数量而停下来。我们将研究对象转为每个盒子，则，假设有x个白/黑盒子，我们可以想到第i个盒子被开到的概率其实相当于最后一个白/黑盒子的位置>=i。
现在考虑如何计算这个概率。假设从正面进行计算，我貌似没想出来，有知道的大佬麻烦说下Orz，这里采用对立事件，我们算下开不到这个箱子的概率。

若开不到，则说明箱子全部在前面的i-1个位置上。这个好算：

(注意下要算黑白两种，要*2)

所以，第i个箱子被开到的概率是：

根据定义算即可。

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);
#define rep(i, a, n) for (int i = a; i <= n; ++i)
#define per(i, a, n) for (int i = n; i >= a; --i)
//#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
int mod = 1e9 + 7;
template<typename T>void write(T x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
    {
        write(x/10);
    }
    putchar(x%10+'0');
}

template<typename T> void read(T &x)
{
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}
int lcm(int a, int b) { return a / gcd(a, b) * b; };
ll ksm(ll a, ll n)
{
    ll ans = 1;
    while (n)
    {
        if (n & 1)
            ans = (ans * a) % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return ans % mod;
}
//==============================================================
const int maxn=1e5+10;
int n;
double c,w[maxn];
double Pow[maxn];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    //clock_t c1 = clock();
    //===========================================================
    read(n);cin>>c;  
    Pow[0]=1;
    for(int i=1;i<maxn;++i)Pow[i]=Pow[i-1]/2;
    double ans1=0;
    for(int i=1;i<=n;++i)cin>>w[i],ans1+=w[i];
    double ans2=c;
    sort(w+1,w+1+n);
    for(int i=1;i<n;++i){
       // cerr<<(1-2*Pow[n-i+1])<<" "<<w[i]<<endl;
        ans2+=(1-Pow[n-i])*w[i];
    }
    //cerr<<ans2<<endl;
    printf("%.10lf\n",min(ans1,ans2));;
    //===========================================================
    //std::cerr << "Time:" << clock() - c1 << "ms" << std::endl;
    return 0;
}

G.Greater Integer, Better LCM

这题其实主体思路不难想。他给出的是两个数的lcm，我们都知道，lcm是两个数的质因子分解的次数求max，因此，我们可以考虑枚举让（a+x）和（b+y）哪个数在该质因子上的次数是max。例如，对于样例中所给的，我们可以考虑是（a+x）的因子，或者是（b+y）的因此，同理。由于这题给的数很小，我们就可以冲了。然后T了。。。
但是，数这么小，所以还是考虑剪枝。这里参考了rank5的代码，三处剪枝，这里不多说，我写在注释里。
这题我认为关键是掌握好利用lcm是两个数质因子次数取max的性质。

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);
#define rep(i, a, n) for (int i = a; i <= n; ++i)
#define per(i, a, n) for (int i = n; i >= a; --i)
//#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
int mod = 1e9 + 7;
template<typename T>void write(T x) {
    if(x<0) { putchar('-'); x=-x; }
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
namespace FastIO {
    const int SIZE = 1 << 16;
    char buf[SIZE], str[64];
    int l = SIZE, r = SIZE;
    int read(char *s) {
        while (r) {
            for (; l < r && buf[l] <= ' '; l++);
            if (l < r) break;
            l = 0, r = int(fread(buf, 1, SIZE, stdin));
        }
        int cur = 0;
        while (r) {
            for (; l < r && buf[l] > ' '; l++) s[cur++] = buf[l];
            if (l < r) break;
            l = 0, r = int(fread(buf, 1, SIZE, stdin));
        }
        s[cur] = '\0';
        return cur;
    }
    template<typename type>
    bool read(type &x, int len = 0, int cur = 0, bool flag = false) {
        if (!(len = read(str))) return false;
        if (str[cur] == '-') flag = true, cur++;
        for (x = 0; cur < len; cur++) x = x * 10 + str[cur] - '0';
        if (flag) x = -x;
        return true;
    }
    template <typename type>
    type read(int len = 0, int cur = 0, bool flag = false, type x = 0) {
        if (!(len = read(str))) return false;
        if (str[cur] == '-') flag = true, cur++;
        for (x = 0; cur < len; cur++) x = x * 10 + str[cur] - '0';
        return flag ? -x : x;
    }
} using FastIO::read;
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}
int lcm(int a, int b) { return a / gcd(a, b) * b; };
ll ksm(ll a, ll n)
{
    ll ans = 1;
    while (n)
    {
        if (n & 1)
            ans = (ans * a) % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return ans % mod;
}
//==============================================================
const int maxn=25+10;
using i128=__int128_t;
i128 ans;
i128 p[maxn],q[maxn];
i128 pre[maxn][maxn];
i128 suf[maxn];
int n;
i128 a,b,c;

void dfs(int pos,i128 A,i128 B){
    if(A*suf[pos]<a||B*suf[pos]<b)return ;//剪枝1：不可能满足条件，剪掉。
    if(A-a+B-b>ans)return;//剪枝1：不可能比现有答案优，剪掉。
    if(pos>n){
        if(A<a||B<b)return ;
        ans=min(ans,A-a+B-b);
        return ;
    }
    i128 now=1;
    for(int i=1;i<=q[pos];++i){
        dfs(pos+1,A*now,B*pre[pos][q[pos]]);
        dfs(pos+1,A*pre[pos][q[pos]],B*now);
        now*=p[pos];
    }
    dfs(pos+1,A*pre[pos][q[pos]],B*pre[pos][q[pos]]);//剪枝3：这个就有点那个啥了，，减少了一次重复的搜索，但不加就会T
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    //clock_t c1 = clock();
    //===========================================================
    read(n);
    for(int i=1;i<=n;++i)read(p[i]),read(q[i]);
    read(a),read(b);
    for(int i=1;i<=n;++i){
        pre[i][0]=1;
        for(int j=1;j<=q[i];++j){
            pre[i][j]=pre[i][j-1]*p[i];
        }
    }
    suf[n+1]=1;
    for(int i=n;i>=1;--i){
        suf[i]=suf[i+1]*pre[i][q[i]];
    }
    //init();
    c=1;
    for(int i=1;i<=n;++i)c*=pre[i][q[i]];
    ans=2*c;
    dfs(1,1,1);
    write(ans);
    //===========================================================
    //std::cerr << "Time:" << clock() - c1 << "ms" << std::endl;
    return 0;
}

但这个做法我认为还不算完美Orz（？），之后再考虑学（抄）习（袭）其他的代码找找更好的解***再更新（大概？）