c 做网站需要什么知识,长垣网站建设,做抛物线的网站,做外贸网站平台题目链接#xff1a;https://www.nowcoder.com/acm/contest/94/A 题意#xff1a;在一个二维平面上有 n 个炸弹#xff0c;每个炸弹有一个坐标和爆炸半径#xff0c;引爆它之后在其半径范围内的炸弹也会爆炸#xff0c;每个炸弹最多爆炸一次#xff0c;每次随机选一个未引…题目链接https://www.nowcoder.com/acm/contest/94/A 题意在一个二维平面上有 n 个炸弹每个炸弹有一个坐标和爆炸半径引爆它之后在其半径范围内的炸弹也会爆炸每个炸弹最多爆炸一次每次随机选一个未引爆的炸弹来引爆问引爆所有炸弹的期望操作次数。 题解先 dfs 把引爆每个炸弹之后会触发的所有炸弹的状态保存起来当作引爆该炸弹的下一个状态。然后可以巧妙的考虑从后往前进行状压 DP显然全部炸弹都引爆之后的操作次数为 0此状态则为初始状态接一下考虑每个状态引爆所有可能引爆的状态把其转移到的下一个状态的期望操作次数加起来最后除以该状态下可以引爆的炸弹数则为该状态的期望操作次数。 1 #include bits/stdc.h2 using namespace std;3 #define ll long long4 #define mst(a,b) memset((a),(b),sizeof(a))5 #define pi acos(-1)6 #define pii pairint,int7 const int INF 0x3f3f3f3f;8 const double eps 1e-3;9 const int MAXN 1e5 10;
10 const int MAXM 2e6 10;
11 const ll mod 1e9 9;
12
13 int n;
14 ll x[25],y[25],r[25];
15 ll inv[25],st[25];
16 ll dp[121];
17 bool vis[25];
18
19 ll pow_mod(ll a,ll m) {
20 ll res 1;
21 while(m) {
22 if(m 1) res res * a % mod;
23 a a * a % mod;
24 m / 2;
25 }
26 return res;
27 }
28
29 ll dis(int i,int j) {
30 return (x[i]-x[j])*(x[i]-x[j]) (y[i]-y[j])*(y[i]-y[j]);
31 }
32
33 ll num;
34
35 void dfs(int u) {
36 num | 1u;
37 vis[u] true;
38 for(int i0; in; i) {
39 if(vis[i] || dis(u,i)r[u]*r[u]) continue;
40 dfs(i);
41 }
42 }
43
44 int main()
45 {
46 #ifdef local
47 freopen(data.txt,r,stdin);
48 // freopen(data.txt,w,stdout);
49 #endif
50 inv[0] 1;
51 for(int i1; i20; i)
52 inv[i] pow_mod(i,mod-2);
53 while(~scanf(%d,n)) {
54 for(int i0; in; i)
55 scanf(%lld%lld%lld,x[i],y[i],r[i]);
56 for(int i0; in; i) {
57 mst(vis,false);
58 num 0;
59 dfs(i);
60 st[i] num;
61 }
62 dp[(1n)-1] 0;
63 for(ll i(1n)-2; i0; i--) {
64 dp[i] 0;
65 num 0;
66 for(ll j0; jn; j) {
67 if((1j)i) {
68 num;
69 continue;
70 }
71 dp[i] (dp[i] dp[i|st[j]]) % mod;
72 }
73 dp[i] (dp[i] n) % mod;
74 dp[i] (dp[i] * inv[n-num]) % mod;
75 }
76 printf(%lld\n,dp[0]);
77 }
78 return 0;
79 } 转载于:https://www.cnblogs.com/scaulok/p/9770569.html
