B Boxes
Yes n n n boxes, each box contains black ball, and the probability of white ball is 1 2 \displaystyle \frac{1}{2} 21. Open page i i The cost of i boxes is w i w_i wi. Now there is an opportunity to use c c The cost of c knows the number of black balls in the remaining boxes, and asks the expected minimum cost of using the optimal strategy to open the box until all the boxes are filled with ball colors.
Solution: obviously, there are several black balls in the inquiry box. This strategy will only be used once: the answer used for the second time can be obtained from the result of the first inquiry and the new result in the middle. And the sooner you use it, the better ∑ w i < c \sum w_i<c Σ wi < C must be used first c c c. ask about the price.
Since the probability of black-and-white balls in each box is the same, the box with small weight must be opened first. Sort according to the weight and open the box from small to large. Next, consider section i i When will i open the box.
Remember that the initial query result is x x x. The termination condition for opening the box can be felt x x x black balls can also be touched n − x n-x n − x white balls - but one thing in common is that after the box, the remaining balls are all the same color, either all black or all white. Consider section i i i box. If you don't open to this box, it proves that the front has stopped. Just in the second i i The probability of i-bit stop is P ( i ) = 1 2 n − i − 1 , i < n P(i)=\displaystyle \frac{1}{2^{n-i-1}},i<n P(i)=2n − i − 11, i < n, obviously the last box will not open. Then open the second page i i The probability of i-bit box is 1 − ∑ j = 1 i − 1 P ( j ) = 1 − 1 2 n − i \displaystyle 1-\sum_{j=1}^{i-1}P(j)=1-\frac{1}{2^{n-i}} 1−j=1∑i−1P(j)=1−2n−i1. So the expected probability is ∑ i = 1 n − 1 w i ( 1 − 1 2 n − i ) \displaystyle \sum_{i=1}^{n-1} w_i (1-\frac{1}{2^{n-i}}) i=1∑n−1wi(1−2n−i1). Pay attention to the accuracy. You can use long double.
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
long double w[100005], sum[100005];
int main()
{
int n;
long double c;
scanf("%d%Lf", &n, &c);
for (int i = 1; i <= n; i++)
cin >> w[i];
sort(w + 1, w + n + 1);
for (int i = 1; i <= n; i++)
sum[i] = sum[i - 1] + w[i];
long double ans = 0, p = 1;
for (int i = n; i >= 1;i--)
{
ans += (1 - p) * w[i];
p /= 2;
}
printf("%.10Lf", min(ans + c, sum[n]));
return 0;
}
C Cheating and Stealing
Given n n The result of the table tennis match in n games, and the current match point is i ∈ [ 1 , n ] i \in [1,n] i ∈ [1,n]. n ≤ 1 × 1 0 5 n \leq 1\times 10^5 n≤1×105.
Solution: easy to find, when the match point is x x When x, the total number of stations is only O ( n x ) \displaystyle O(\frac{n}{x}) O(xn) local, according to the properties of harmonic series, ∑ i = 1 n O ( n x ) = O ( n log n ) \displaystyle \sum_{i=1}^{n} O(\frac{n}{x})=O(n \log n) i=1 Σ n O(xn) = O(nlogn), so as long as each bureau can be used O ( 1 ) O(1) O(1) time calculation is enough.
Consider how to quickly find the end of a game. Take the first inning as an example, the match point is x x x. For the score determination of the later Bureau, the prefix and the previous bureau score can be excavated.
First find two people to reach x x The position of x-share, whichever is smaller. Here, you can use the bucket for storage to quickly find how many points are in which game and how many points are accumulated in which game. Let PJ King get it first x x x points at y y y field. If PJ King is on page y y The score in field y is not enough x − 2 x-2 x − 2 points, the Council is over.
Obviously, at this time, they can't have the same score, and PJ King is ahead. If he wins the next game, the game is over. Otherwise, they have the same score at this time. Then there may be a tug of war - win alternately and draw all the time.
Introduce the second array—— T i e b r e a k \rm Tiebreak Tiebreak. This array represents the number of games that a person wins when he is ahead. Only one recursion is needed to find the array:
tiebreak[n] = tiebreak[n + 1] = n + 1;
for (int i = n - 1; i >= 1;i--)
tiebreak[i] = a[i] == a[i + 1] ? i + 1 : tiebreak[i + 2];
So now we can quickly find a place to end this draw—— y = T i e b r e a k [ y + 1 ] y= {\rm Tiebreak}[y+1] y=Tiebreak[y+1]. Because No y y y game is a draw, so we have to add one. At this time, the scores of the two have been set, the bureau is over, and the statistical results are.
Overall complexity O ( n log n ) O(n \log n) O(nlogn).
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const long long mod = 998244353;
int tiebreak[2000005], sumw[2000005], suml[2000005], posw[2000005], posl[2000005];
//posl is the number of fields corresponding to PJ King at x-minute, and posw is the same
char a[2000005];
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n * 2;i++)
posw[i] = posl[i] = n + 1;
scanf("%s", a + 1);
for (int i = 1; i <= n; i++)
{
sumw[i] = sumw[i - 1];
suml[i] = suml[i - 1];
if (a[i] == 'W')
{
sumw[i]++;
posw[sumw[i]] = i;
}
else
{
suml[i]++;
posl[suml[i]] = i;
}
}
tiebreak[n] = tiebreak[n + 1] = n + 1;
for (int i = n - 1; i >= 1;i--)
tiebreak[i] = a[i] == a[i + 1] ? i + 1 : tiebreak[i + 2];
long long ans = 0, x = 1;
for (int i = 1; i <= n;i++)
{
int res = 0;
int old = 0, place = 0;
while (old < n)
{
int Wwin = posw[sumw[old] + i];
int Lwin = posl[suml[old] + i];
place = min(Wwin, Lwin);
if(place>n)
break;
if (abs((sumw[place] - sumw[old]) - (suml[place] - suml[old])) >= 2)
{
if (sumw[place] - sumw[old] > suml[place] - suml[old])
res++;
old = place;
continue;
}
place++;
if (place > n)
break;
if (abs((sumw[place] - sumw[old]) - (suml[place] - suml[old])) >= 2)
{
if (sumw[place] - sumw[old] > suml[place] - suml[old])
res++;
old = place;
continue;
}
place = tiebreak[place + 1];
if(place>n)
break;
if (sumw[place] - sumw[old] > suml[place] - suml[old])
res++;
old = place;
}
ans = (ans + res * x % mod) % mod;
x = x * (n + 1) % mod;
}
printf("%lld", ans);
return 0;
}
D Double strings
The given length is n n n and m m Two strings of m S , T S,T S. T, ask from S , T S,T S. Select the substring with the same length from t a , b a,b a. B and meet a a The dictionary order of a is less than b b b number of programmes. n , m ≤ 5 × 1 0 3 n,m \leq 5\times 10^3 n,m≤5×103.
Solution: disassemble the problem into the following sub problems,
- Found a public prefix
- Find the first different place
- Find the following equal length substring of any length
Might as well make f i , j f_{i,j} fi,j + S S S string to No i i Bit i, T T T string to No j j The total number of public prefix fetches of j bits. This transfer is very easy to write:
f i , j = { f i − 1 , j + f i , j − 1 , a i ≠ b j f i − 1 , j + f i , j − 1 + f i − 1 , j − 1 , a i = b j f_{i,j} = \begin{cases} f_{i-1,j}+f_{i,j-1}, & a_i\neq b_j \\[2ex] f_{i-1,j}+f_{i,j-1}+f_{i-1,j-1}, & a_i=b_j \end{cases} fi,j=⎩⎨⎧fi−1,j+fi,j−1,fi−1,j+fi,j−1+fi−1,j−1,ai=bjai=bj
remember s u m f sumf sumf is f f The two-dimensional prefix sum of f, which represents S S Front of S String i i i-bit and T T Front of T j j The total number of schemes taking the common prefix in bit j. Then from the above formula and s u m f i , j = s u m f i − 1 , j + s u m f i − 1 , j − s u m f i − 1 , j − 1 sumf_{i,j}=sumf_{i-1,j}+sumf_{i-1,j}-sumf_{i-1,j-1} sumfi,j = sumfi − 1,j + sumfi − 1,j − sumfi − 1,j − 1,
s u m f i , j = { s u m f i − 1 , j + s u m f i , j − 1 − s u m f i − 1 , j − 1 , a i ≠ b j s u m f i − 1 , j + s u m f i , j − 1 a i = b j sumf_{i,j} = \begin{cases} sumf_{i-1,j}+sumf_{i,j-1}-sumf_{i-1,j-1}, & a_i\neq b_j \\[2ex] sumf_{i-1,j}+sumf_{i,j-1} & a_i=b_j \end{cases} sumfi,j=⎩⎨⎧sumfi−1,j+sumfi,j−1−sumfi−1,j−1,sumfi−1,j+sumfi,j−1ai=bjai=bj
We'll use it later s u m f sumf sumf carries out the statistics of answers.
Next comes the third question. remember g i , j g_{i,j} gi,j is S S S string from No i i i position back, T T T string from No j j Position j backward, satisfied a i < b j a_i<b_j ai < BJ, followed by the total number of schemes with equal length suffix. Its calculation formula is:
g i , j = { ( n + m − i − j n − i ) a i < b j 0 , a i ≥ b j g_{i,j} = \begin{cases} \dbinom{n+m-i-j}{n-i} & a_i< b_j \\[2ex] 0, & a_i \geq b_j \end{cases} gi,j=⎩⎪⎨⎪⎧(n−in+m−i−j)0,ai<bjai≥bj
About its formula: its essence is n n n and m m Select each item from m items k k The sum of k item schemes, i.e ∑ k = 1 min ( n , m ) ( n k ) ( m k ) = ( n + m n ) \displaystyle \sum_{k=1}^{\min(n,m)} \dbinom{n}{k} \dbinom{m}{k}=\dbinom{n+m}{n} k=1∑min(n,m)(kn)(km)=(nn+m). DP can be used to solve here, which is easy to find the law of Yang Hui triangle.
do g g Two dimensional suffix and of g s u m g sumg sumg, indicating from S S After S String i i i-bit and T T After the T string j j The sum of the legal schemes selected in bit j.
s u m g i , j = { s u m g i + 1 , j + s u m g i , j + 1 − s u m g i + 1 , j + 1 + ( n + m − i − j n − i ) a i < b j s u m g i + 1 , j + s u m g i , j + 1 − s u m g i + 1 , j + 1 , a i ≥ b j sumg_{i,j} = \begin{cases} sumg_{i+1,j}+sumg_{i,j+1}-sumg_{i+1,j+1}+\dbinom{n+m-i-j}{n-i} & a_i< b_j \\[2ex] sumg_{i+1,j}+sumg_{i,j+1}-sumg_{i+1,j+1}, & a_i \geq b_j \end{cases} sumgi,j=⎩⎪⎨⎪⎧sumgi+1,j+sumgi,j+1−sumgi+1,j+1+(n−in+m−i−j)sumgi+1,j+sumgi,j+1−sumgi+1,j+1,ai<bjai≥bj
Finally, consider the second step, just O ( n m ) O(nm) The enumeration of O(nm) is sufficient for such segmentation points. When a i = b j a_i=b_j When ai = bj ， the total number of schemes is exactly in the second i − 1 , j − 1 i-1,j-1 The number of schemes terminated by I − 1 and J − 1 bits multiplied by the number of schemes with suffix, i.e f i , j s u m g i + 1 , j + 1 f_{i,j} sumg_{i+1,j+1} fi,jsumgi+1,j+1.
Note that the space of this topic is strictly limited. You can't open long.
Overall complexity O ( n m ) O(nm) O(nm).
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int mod = 1000000007;
int power(int a,int x)
{
int ans = 1;
while(x)
{
if(x&1)
ans = 1ll * ans * a % mod;
a = 1ll * a * a % mod;
x >>= 1;
}
return ans;
}
int inv(int x)
{
return power(x, mod - 2);
}
int sumf[5005][5005], sumg[5005][5005];
int fac[10005], invfac[10005];
char a[5005], b[5005];
int C(int n,int m)
{
if(m<0 || n<m)
return 0;
return (long long)fac[n] * invfac[m] % mod * invfac[n - m] % mod;
}
int main()
{
fac[0] = 1;
for (int i = 1; i <= 10000;i++)
fac[i] = fac[i - 1] * (long long)i % mod;
invfac[10000] = inv(fac[10000]);
for (int i = 9999; i >= 1;i--)
invfac[i] = invfac[i + 1] * (long long)(i + 1) % mod;
invfac[0] = 1;
scanf("%s", a + 1);
scanf("%s", b + 1);
int n = strlen(a + 1);
int m = strlen(b + 1);
sumf[0][0] = 1;
for (int i = 1; i <= n;i++)
sumf[i][0] = 1;
for (int i = 1; i <= m;i++)
sumf[0][i] = 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (a[i] == b[j])
sumf[i][j] = (sumf[i - 1][j] + sumf[i][j - 1]) % mod;
else
sumf[i][j] = ((sumf[i - 1][j] + sumf[i][j - 1] - sumf[i - 1][j - 1]) % mod + mod) % mod;
for (int i = n; i >= 1;i--)
for (int j = m; j >= 1;j--)
{
sumg[i][j] = ((sumg[i][j + 1] + sumg[i + 1][j] - sumg[i + 1][j + 1]) % mod + mod) % mod;
if(a[i]<b[j])
sumg[i][j] = (sumg[i][j] + C(n + m - i - j, n - i)) % mod;
}
int ans = sumg[1][1];
for (int i = 1; i <= n;i++)
for (int j = 1; j <= m;j++)
if(a[i]==b[j])
{
long long temp = (((long long)sumf[i][j] - sumf[i][j - 1] - sumf[i - 1][j] + sumf[i - 1][j - 1]) % mod + mod) % mod;
ans = (ans + temp * sumg[i + 1][j + 1] % mod) % mod;
}
printf("%d", ans);
return 0;
}
E Eert Esiwtib
Given a tree, the second i i The weight of i points is w i w_i wi, there are operators and, or, XOR on the edge. q q q independent inquiries ( d , u ) (d,u) (d,u), the point weight is revised to w i + d i w_i +di wi + di, ask u u All nodes in the subtree of u node u u The and, or, XOR value of the weight on the u path calculated according to the symbol given on the edge. d ≤ 100 d \leq 100 d≤100， n , q ≤ 1 × 1 0 5 n,q \leq 1\times 10^5 n,q≤1×105.
Solution: Although there are many questions, but d d d is very small, that is, the number of weights with different essence is not much, so it is considered to divide d d d answer the inquiry, so as to execute the whole process 100 100 100 times.
Now the weight of the point is given. It is easy to find that this is a tree DP, f u , 0 / 1 / 2 f_{u,0/1/2} fu,0/1/2 + u u All nodes under the subtree of u u u The or, and, XOR value of the weight on the u path. Consider merging operations according to u u u to his son v v The symbol on the side of v can be divided into three cases.
-
( u , v ) (u,v) (u,v) the edge symbol is or.
Three more hours
A. Or value
consider v v v up f v , 0 f_{v,0} The composition of fv,0 ， can be written:
( w α 1 o p α 1 w α 2 o p α 2 ⋯ ) ∣ ( w β 1 o p β 1 w β 2 o p β 2 ⋯ ) ∣ ( w γ 1 o p γ 1 w γ 2 o p γ 2 ⋯ ) ∣ ⋯ (w_{\alpha_1} {\rm op_{\alpha_1} }w_{\alpha_2} {\rm op_{\alpha_2} } \cdots )|(w_{\beta_1} {\rm op_{\beta_1} }w_{\beta_2} {\rm op_{\beta_2} } \cdots )|(w_{\gamma_1} {\rm op_{\gamma_1} }w_{\gamma_2} {\rm op_{\gamma_2} } \cdots ) | \cdots (wα1opα1wα2opα2⋯)∣(wβ1opβ1wβ2opβ2⋯)∣(wγ1opγ1wγ2opγ2⋯)∣⋯
that f u , 0 f_{u,0} fu,0 # can write:
( w v ∣ w α 1 o p α 1 w α 2 o p α 2 ⋯ ) ∣ ( w v ∣ w β 1 o p β 1 w β 2 o p β 2 ⋯ ) ∣ ( w v ∣ w γ 1 o p γ 1 w γ 2 o p γ 2 ⋯ ) ∣ ⋯ (w_v|w_{\alpha_1} {\rm op_{\alpha_1} }w_{\alpha_2} {\rm op_{\alpha_2} } \cdots )|(w_v|w_{\beta_1} {\rm op_{\beta_1} }w_{\beta_2} {\rm op_{\beta_2} } \cdots )|(w_v|w_{\gamma_1} {\rm op_{\gamma_1} }w_{\gamma_2} {\rm op_{\gamma_2} } \cdots ) | \cdots (wv∣wα1opα1wα2opα2⋯)∣(wv∣wβ1opβ1wβ2opβ2⋯)∣(wv∣wγ1opγ1wγ2opγ2⋯)∣⋯
However, such analysis is troublesome. We can directly consider the results of each position, the same below. If w v w_v The binary bit on wv # is 1 1 1. No matter how many internal values or external values are, they must be now 1 1 1； If current w v w_v The binary bit of wv + 0 0 0, the original result will be directly viewed. thus f u , 0 = w v ∣ f v , 0 f_{u,0}=w_v|f_{v,0} fu,0=wv∣fv,0. Note: This is only the combined result of one subtree, so the final result should be or on each subtree, the same below.
B. And value
If w v w_v wv# current bit is 1 1 1, then all values in each descendant node (i.e. in the largest braces) are brushed into 1 1 1. The current and values must have w v w_v wv # all 1 1 Binary bit of 1; If yes 0 0 0, it depends on the previous results. thus f u , 1 = w v & f v , 1 f_{u,1}=w_v\& f_{v,1} fu,1=wv&fv,1.
C. XOR value
The XOR value is special and needs to be counted 1 1 1 number of occurrences. If the subtree size is odd, then w v w_v wv# was XORed an odd number of times. w v w_v wv ＾ above 0 0 The bit of 0 obviously doesn't matter, just consider 1 1 1. Obviously, whether this is 1 1 1. All presented in the operation of this step are 1 1 1, so the current one has 1 1 The condition of 1 is that the subtree size is odd—— f u , 2 = w v ∣ f v , 2 f_{u,2}=w_v | f_{v,2} fu,2=wv∣fv,2； If the subtree size is even, all the subtrees will be dug out—— f u , 2 = ( w v ∣ f v , 2 ) ⊕ w v f_{u,2}=(w_v | f_{v,2}) \oplus w_v fu,2=(wv∣fv,2)⊕wv. -
( u , v ) (u,v) (u,v) symbols are and
A. Or value
w v w_v wv ＾ above 0 0 The bit of 0 directly brushes all the corresponding bits in each bracket 0 0 0, so these bits or outputs are also 0 0 0 If w v w_v wv# upper binary is 1 1 1. It depends on the previous results. thus f u , 0 = w v & f v , 0 f_{u,0} = w_v\& f_{v,0} fu,0=wv&fv,0.
B. And value
Ibid., yes 1 1 Only in the position of 1 can you contribute, f u , 1 = w v & f v , 1 f_{u,1}=w_v \& f_{v,1} fu,1=wv&fv,1.
C. XOR value
w v w_v wv ＾ above 0 0 Bits of 0 directly exit the discussion, and there are 1 1 1, if 1 1 The number of times of 1 is even, so now and after last, it is still even; It used to be an odd number of times, but now it's still an odd number of times. thus f u , 2 = w v & f v , 2 f_{u,2} = w_v \& f_{v,2} fu,2=wv&fv,2. -
( u , v ) (u,v) (u,v) the symbol is exclusive or
A. Or value
w v w_v wv# binary is 0 0 0 is very simple, so you can directly undertake this part; If yes 1 1 1, then the last digit is 1 1 It depends on whether this person exists 0 0 Bit of 0 - only this can happen 1 1 1. So go and query f v , 1 f_{v,1} fv,1 + f u , 0 f_{u,0} Fu, the result of 0.
B. And value
Ditto, if current w v w_v wv# this one is 1 1 1. Then only this one was 0 0 0 is possible 1 1 1.
C. XOR value
Still the molecular tree size. Here, you can consider directly w v w_v wv# remove it from each bracket. If it is removed an odd number of times, it will be XOR, otherwise it will not move.
Overall complexity O ( n d ) O(nd) O(nd).
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const long long inf = 0xffffffffffffffffll;
struct line
{
int from;
int to;
int next;
int op;
};
struct line que[200005];
long long w[100005], oldw[100005];
int cnt, headers[100005], siz[100005];
long long f[100005][3], old[100005][3];
void add(int from,int to,int op)
{
cnt++;
que[cnt].from = from;
que[cnt].to = to;
que[cnt].op = op;
que[cnt].next = headers[from];
headers[from] = cnt;
}
//Consider the influence of bit by bit observation
void dfs(int place,int father)
{
siz[place] = 1;
f[place][0] = 0;
f[place][1] = inf;
f[place][2] = 0;
for (int i = headers[place]; i; i = que[i].next)
if(que[i].to!=father)
{
dfs(que[i].to, place);
siz[place] += siz[que[i].to];
switch(que[i].op)
{
case 0:
{
f[place][0] |= w[place] | f[que[i].to][0];
f[place][1] &= w[place] | f[que[i].to][1];
if (siz[que[i].to] & 1)
f[place][2] ^= w[place] | f[que[i].to][2];
else
f[place][2] ^= (w[place] | f[que[i].to][2]) ^ w[place];
break;
}
case 1:
{
f[place][0] |= w[place] & f[que[i].to][0];
f[place][1] &= w[place] & f[que[i].to][1];
f[place][2] ^= w[place] & f[que[i].to][2];
break;
}
case 2:
{
f[place][0] |= ((~w[place]) & f[que[i].to][0]) | (w[place] & (~f[que[i].to][1]));
f[place][1] &= ((~w[place]) & f[que[i].to][1]) | (w[place] & (~f[que[i].to][0]));
if (siz[que[i].to] & 1)
f[place][2] ^= w[place] ^ f[que[i].to][2];
else
f[place][2] ^= f[que[i].to][2];
break;
}
}
}
old[place][0] = f[place][0];
old[place][1] = f[place][1];
old[place][2] = f[place][2];
f[place][0] |= w[place];
f[place][1] &= w[place];
f[place][2] ^= w[place];
return;
}
struct node
{
int id;
int u;
};
vector<node> ask[100005];
long long ans[100005][3];
int main()
{
int n, q;
scanf("%d%d", &n, &q);
for (int i = 1; i <= n;i++)
{
scanf("%lld", &w[i]);
oldw[i] = w[i];
}
for (int i = 1; i < n;i++)
{
int a, b;
scanf("%d%d", &a, &b);
add(a, i + 1, b);
add(i + 1, a, b);
}
for (int i = 1; i <= q; i++)
{
int u, d;
scanf("%d%d", &d, &u);
ask[d].push_back((node){i, u});
}
for (int d = 0; d <= 100;d++)
{
for (int i = 1; i <= n; i++)
w[i] = oldw[i] + (long long)i * d;
dfs(1, 0);
for(auto i:ask[d])
for (int j = 0; j <= 2;j++)
ans[i.id][j] = old[i.u][j];
}
for (int i = 1; i <= q;i++)
{
for (int j = 0; j <= 2;j++)
printf("%lld ", ans[i][j]);
printf("\n");
}
return 0;
}
F Finding Points
According to the clockwise direction, given a convex polygon, find the maximum value of the minimum angle formed from a point to each side of the polygon.
Solution: the minimum of the maximum value or the maximum of the minimum value, all two answers. After dividing the angle, for each edge, the corresponding track circle can be obtained by using the relationship between the center angle and the circumference angle.
Given the circumferential angle and the corresponding chord, find the circle. First, the center of the circle must be on the vertical line of the string α \alpha α Becomes the center angle 2 α 2\alpha two α or 2 π − 2 α 2\pi -2\alpha 2π−2 α. In this way, any vertex of the circle center, chord midpoint and line segment forms a right triangle, which can be calculated by trigonometric function.
The rest is to find the intersection of circles - enumerate the intersection and center of each circle to see if it is in the remaining circles.
Find the intersection of two circles. First, put the circle with small ordinate of the center of the circle on the lower part and record it as ( x , y ) (x,y) (x,y), whose radius is r r r. Note the centreline of two circles and x x The included angle formed by the x-axis is α \alpha α， The center angle of the circle corresponding to the intersection chord at the lower part is β \beta β， Then the intersection can be expressed as ( x + r cos ( α + β ) , y + r sin ( α + β ) ) (x+r\cos (\alpha + \beta),y+r \sin (\alpha + \beta)) (x+rcos( α+β), y+rsin( α+β)) And ( x + r cos ( α − β ) , y + r sin ( α − β ) ) (x+r\cos (\alpha - \beta),y+r \sin (\alpha - \beta)) (x+rcos(α−β),y+rsin(α−β))
Overall complexity O ( n 3 ) O(n^3) O(n3).
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
const long double pi = acos(-1);
const long double eps = 1e-10;
struct node
{
long double x;
long double y;
};
long double distance(node a,node b)
{
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
struct vec
{
long double x;
long double y;
long double length()
{
return sqrt(x * x + y * y);
}
};
vec operator -(node a,node b)
{
return (vec){b.x - a.x, b.y - a.y};
}
node operator +(node a,vec b)
{
return (node){a.x + b.x, a.y + b.y};
}
vec operator *(long double len,vec a)
{
return (vec){len * a.x, len * a.y};
}
vec unit(vec a)
{
return (vec){a.x / a.length(), a.y / a.length()};
}
struct circle
{
node center;
long double r;
};
struct polygon
{
vector<node> vertex;
int n;
};
vector<circle> cal(polygon now,long double angle)
{
vector<circle> ans;
vector<node> temp;
for (int i = 0; i < now.n;i++)
temp.push_back(now.vertex[i]);
temp.push_back(now.vertex[0]);
for (int i = 0; i + 1 < temp.size(); i++)
{
node start = (node){(temp[i].x + temp[i + 1].x) / 2, (temp[i].y + temp[i + 1].y) / 2};
vec direction = unit((vec){temp[i].y - temp[i + 1].y, temp[i + 1].x - temp[i].x});
long double dis = distance(temp[i], temp[i + 1]);
long double len = dis / 2 / tanl(angle);
long double r = dis / 2 / sinl(angle);
ans.push_back((circle){start + (-len * direction), r});
}
return ans;
}
vector<node> get_intersection(circle a,circle b)
{
vector<node> ans;
long double dis = distance(a.center, b.center);
if(dis>a.r+b.r-eps || -eps+dis<fabs(a.r-b.r))
return ans;
if(a.center.y>b.center.y)
swap(a, b);
long double alpha = asin((b.center.y - a.center.y)/dis);
long double beta = (a.r * a.r + dis * dis - b.r * b.r) / (2 * a.r * dis);
ans.push_back((node){a.center.x + a.r * cosl(alpha + beta), a.center.y + a.r * sinl(alpha + beta)});
ans.push_back((node){a.center.x + a.r * cosl(alpha - beta), a.center.y + a.r * sinl(alpha - beta)});
return ans;
}
bool check(vector<circle> &cir)
{
int n = cir.size();
for(auto i:cir)
{
bool flag = 0;
for(auto j:cir)
if (distance(i.center, j.center) > j.r - eps)
{
flag = 1;
break;
}
if(!flag)
return 1;
}
for (int i = 0; i < n;i++)
for (int j = i + 1; j < n;j++)
{
long double dis = distance(cir[i].center, cir[j].center);
if(dis<fabs(cir[i].r-cir[j].r))
continue;
vector<node> intersection = get_intersection(cir[i], cir[j]);
if(intersection.empty())
return 0;
for(auto k:intersection)
{
bool flag = 0;
for(auto l:cir)
if(distance(k,l.center)>l.r+eps)
{
flag = 1;
break;
}
if(!flag)
return 1;
}
}
return 0;
}
int main()
{
polygon now;
scanf("%d", &now.n);
for (int i = 1; i <= now.n;i++)
{
double x, y;
scanf("%lf%lf", &x, &y);
now.vertex.push_back((node){x, y});
}
reverse(now.vertex.begin(), now.vertex.end());
long double left = 0.0, right = 2 * pi / now.n;
while(left+eps<right)
{
long double mid = (left + right) / 2;
vector<circle> temp = cal(now, mid);
if(check(temp))
left = mid;
else
right = mid;
}
printf("%.10Lf", left * 180 / pi);
return 0;
}
G Greater Integer, Better LCM
Given three numbers a , b , c a,b,c a. B, C, satisfy l c m ( a + x , b + y ) = c {\rm lcm}(a+x,b+y)=c lcm(a+x,b+y)=c ( x , y ) (x,y) (x,y) x + y x+y x+y min. satisfy c c c is made up of not more than 100 100 It is composed of 100 prime numbers, and all power numbers do not exceed 18 18 18. Use int128.
Solution: consider each component c c Prime number of c p p p. The second square is q q q. because l c m \rm lcm The nature of lcm, a + x a+x a+x and b + y b+y There must be a number in b+y that is reached at the last time of this prime factor q q q times. At this time, another number can not be reached.
Design DP status: f [ m a s k ] f[mask] f[mask] is a + x a+x a+x satisfies the condition of how many prime factors (represented by the binary state of the mask) and obtains a number y ≥ a y\geq a y ≥ a, record the minimum at this time y − a = x y-a=x y−a=x. We only need to enumerate the power of each prime number to complete the DP. Finally, we need 1 1 1. Less state acceptance 1 1 Answer to more than one state.
Note satisfaction a a a and satisfaction b b b the conditions are the same. We record the corresponding m a s k mask The product of the mask value and the resulting v v v. Enumerate all such states for b b b and its y y y. Use v − b v-b v − b is obtained; and a a a and x x The status of x has been recorded in the DP array. You only need to find it m a s k mask The status of the mask.
Overall complexity O ( n 2 n ) O(n 2^n) O(n2n)， n ≤ 18 n \leq 18 n≤18.
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const __int128_t inf = (__int128_t)1e36;
vector<pair<int, __int128_t>> dif;
int n;
void scan(__int128_t &now)
{
char num[45];
scanf("%s", num);
int len = strlen(num);
for (int i = 0; i < len;i++)
{
now *= 10;
now += num[i] - 48;
}
return;
}
void print(__int128_t value)
{
if(value==0)
{
printf("0");
return;
}
vector<int> num;
while(value)
{
num.push_back(value % 10);
value /= 10;
}
for (int i = num.size() - 1; i >= 0;i--)
printf("%d", num[i]);
return;
}
__int128_t f[1 << 18], a, b, prime[20];
int times[20];
void dfs(int step,__int128_t value,int mask)
{
if (step == n + 1)
{
dif.push_back(make_pair(mask, value));
if(value>=a)
f[mask] = min(f[mask], value - a);
return;
}
for (int i = 0; i <= times[step];i++)
{
if(i==times[step])
mask |= (1 << (step - 1));
dfs(step + 1, value, mask);
value *= prime[step];
}
return;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n;i++)
{
scan(prime[i]);
scanf("%d", ×[i]);
}
scan(a);
scan(b);
for (int i = 0; i < (1 << n);i++)
f[i] = inf;
dfs(1, 1, 0);
for (int i = 0; i < n;i++)
for (int j = 0; j < (1 << n);j++)
if ((j & (1 << i)) == 0)
f[j] = min(f[j], f[j | (1 << i)]);
__int128_t ans = inf;
for(auto i:dif)
if(i.second>=b)
{
int fora = (1 << n) - 1 - i.first;
ans = min(ans, i.second - b + f[fora]);
}
print(ans);
return 0;
}