转载请注明出处:http://tokitsukaze.live/

题目链接:http://codeforces.com/problemset/problem/995/D


题意:给2^n个数,Allen和Bessie轮流操作,每次操作可以选一个数,sum加上或者不加这个数,每个数只能选一次。Allen想让sum最大,Bessie想让sum最小。让你求sum的期望值。然后有r轮,每轮会改变一个数,每次输出改变后sum的期望值。


题解:
观察案例猜了个结论就过了…

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define mem(a,b) memset((a),(b),sizeof(a))
#define MP make_pair
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
using namespace std;
#define _GLIBCXX_PERMIT_BACKWARD_HASH
#include <ext/hash_map>
using namespace __gnu_cxx;
struct str_hash{size_t operator()(const string& str)const{return __stl_hash_string(str.c_str());}};
typedef long long ll;
typedef unsigned long long ull;
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PDD pair<double,double>
#define VI vector<int>
#define VL vector<ll>
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-4;
const int MAX=5e5+10;
const ll mod=998244353;
int main()
{
int n,r,i,x,y;
double ans;
while(~scanf("%d%d",&n,&r))
{
n=1<<n;
VI a(n);
ans=0;
for(i=0;i<n;i++) scanf("%d",&a[i]),ans+=a[i];
printf("%.6f\n",ans/n);
for(i=0;i<r;i++)
{
scanf("%d%d",&x,&y);
ans-=a[x];
a[x]=y;
ans+=a[x];
printf("%.6f\n",ans/n);
}
}
return 0;
}