这场感觉需要记录的东西貌似不是很多，所以写个总的。
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（？），之后再考虑学（抄）习（袭）其他的代码找找更好的解***再更新（大概？）
京公网安备 11010502036488号