Contents

# P2822 Combinatorial number problem

## Title Description

Combinatorial number$_{_{The general formula:}}$

$Cnm =m!(n−m)!n! $

Among them$1 。$

Shallots want to know if they are given.$_{k The multiple of the number.}$

## Input-output format

Input format:

The first line has two integers$k The meaning of the problem is described.$

Next$m The meaning of the problem is described.$

Output format:

Collective$_{k The multiple of the number.}$

## Input and output sample

1 2 3 3

1

2 5 4 5 6 7

0 7

## Explain

【Example 1 illustrates]

In all possible circumstances, only$_{2 It’s a multiple of 2.}$

【Sub task]

Solve the problem: the Yang Hui triangle is the combination number, the middle group of data is ignored M< N is WA, not preprocessing; the sum of two dimensional tree array can be better pretreated by DP;

#include <bits/stdc++.h> #define ll long long using namespace std; int n,m,k,t,N; int k1, k2; const int M = 2010; ll c1[M][M],c2[M][M],a1[M][M],a2[M][M]; void add(int x, int y, int k){ x++,y++; if(k == 1){ for( ; x <= N; x += x&(-x)) for(int j = y ; j <= N; j += j&(-j)) a1[x][j]++; } if(k == 2){ for( ; x <= N; x += x&(-x)) for(int j = y ; j <= N; j += j&(-j)) a2[x][j]++; } } ll sum(int x, int y, int k){ ll ans = 0; x++,y++; if(k == k1){ for( ; x > 0; x -= x&(-x)) for(int j = y ; j > 0; j -= j&(-j)) ans += a1[x][j]; } if(k == k2){ for( ; x > 0; x -= x&(-x)) for(int j = y ; j > 0; j -= j&(-j)) ans += a2[x][j]; } return ans; } void init(int a, int b, int n){ k1 = a, k2 = b, N = n; c1[0][0] = c2[0][0] = 1; for(int i = 1; i <= n; i++) for(int j = 0; j <= i; j++){ if(!j)c1[i][j] = c2[i][j] = 1; else c1[i][j] = (c1[i - 1][j-1] + c1[i - 1][j]) % k1, c2[i][j] = (c2[i - 1][j-1] + c2[i - 1][j]) % k2; if(!c1[i][j])add(i, j, 1); if(!c2[i][j])add(i, j, 2); } } int main() { // freopen("problem.in","r",stdin); // freopen("problem.out","w",stdout); scanf("%d%d",&t,&k); switch(k){ case 2: case 3: init(2, 3, 5);break; case 4: case 5: init(4, 5, 10);break; case 6: case 7: init(6, 7, 12);break; case 8: case 9: init(8, 9, 105);break; case 10: case 11: init(10, 11, 2005);break; case 12: case 13: init(12, 13, 75);break; case 14: case 15: init(14, 15, 105);break; case 16: case 17: init(16, 17, 105);break; case 18: case 19: init(18, 19, 2005);break; case 20: case 21: init(20, 21, 2005);break; } while(t--){ scanf("%d%d",&n,&m); printf("%lld\n",sum(n, m, k)); } return 0; }

View Code

# P2827 Earthworm

## Title Description

In this problem, we will use symbols$3 。$

The recent earthworm in crickets has become a disaster! The fleas of the flea country next door also had no way to take the earthworms. The king of crickets had to ask the magic knife to help them destroy the earthworms.

The crickets are now shared by the crickets$_{0 Earthworms).}$

Every second, the magic knife will accurately find the longest one among all the earthworms (if there are multiple ones), and cut them into two halves. The location of the earthworm by a knife is a constant.$q （It is a non negative integer constant).$

King cricket knows that this is not a permanent solution, because earthworms will not only grow more and more, but will also grow longer. The king of crickets decided to turn to a mysterious figure with a great shortage of power, but he needed help for the rescue.$m For non negative integers)$

The cricket king wants to know this$m The war in the second. Specifically, he wants to know:$

- $m Numbers);$
- $m A number).$

The cricket king knows how to do it, of course. But he wants to test you…

## Input-output format

Input format:

The first line contains six integers$t It is the output parameter, and its meaning will be explained in the output format.$

Second lines include$_{_{_{n The length of only earthworms.}}}$

The two adjacent numbers in the same line are separated by one space.

Guarantee$_{_{_{_{_{8 。}}}}}$

Output format:

First line output$t Second,… The length of an earthworm (before being cut).$

Second lines output$t，……The length of it.$

The two adjacent numbers in the same line are separated by one space. Even if a row needs no output, you should output a blank line.

Please read the sample to better understand the format.

## Input and output sample

3 7 1 1 3 1 3 3 2

3 4 4 4 5 5 6 6 6 6 5 5 4 4 3 2 2

3 7 1 1 3 2 3 3 2

4 4 5 6 5 4 3 2

3 7 1 1 3 9 3 3 2

//Empty lineTwo

## Explain

【Example interpretation 1]

Before the arrival of the sword hand, the length of the 3 earthworms was 3,3,2.

1After 3 seconds, a worm with a length of about 1 was cut into two earthworms with a length of 1 and 2. The length of the earthworms increased by 1. The length of the final 4 earthworms were (1,2) and 4,3 respectively. Brackets indicate that an earthworm has been cut off in this position.

2Seconds later: an earthworm with a length of 4 was cut into 1 and 3. The length of 5 earthworms were as follows: 2,3, (1,3), and 4.

3Second: an earthworm with a length of 4 is cut off. The length of the 6 earthworms were: 3,4,2,4, (1,3).

4Second: an earthworm with a length of 4 is cut off. The length of the 7 earthworms were 4, (1,3), and 3,5,2,4 respectively.

5Second: an earthworm with a length of 5 is cut off. The length of 8 earthworms was 5,2,4,4, (1,4), 3,5 respectively.

6Second: an earthworm with a length of 5 is cut off. The length of 9 earthworms was: (1,4), 3,5,5,2,5,4,6.

7Second: an earthworm with a length of 6 is cut off. The length of 10 earthworms was 2,5,4,6,6,3,6,5, (2,4). Therefore, the length of earthworms cut in 7 seconds is 3,4,4,4,5,5,6 in sequence. After 7 seconds, the length of all earthworms from large to small is 66,6,5,5,4,4,3,2,2

【Example interpretation 2]

Only t=2 in this data is different from the previous data. You only need to output one number per two rows.

Although the last row of the first line has 6 output, the second row will still have to start again from the second number.

【Example interpretation 3]

Only t=9 in this data is different from the previous data.

Note that the first row has no output, but it also exports a blank line.

【Data range]

Answer: open three queues, 1 stored in the original, 2 storage first, 3 storage second, each time to find the largest of the 3 queues, can ensure that the queue is monotonically decreasing, proved as follows:

if La > Lb, After M seconds, La1 = P * La + m*q, La2 = (1-P) * L a + m* Q;

At this time, B is cut, Lb1 = p* (Lb +m*q), Lb2 = (1-p) * (Lb + m*q); (P < 1)

La1 > Lb1 , La2 > Lb2;

This problem often happens when you merge 3 queues. Do not open another array.

#include <bits/stdc++.h> using namespace std; #define ll long long ll w[4][8000005], a[8000005]; int h[4],tt[4]; const ll inf = 1e15; bool cmp(ll a, ll b){return a>b;} void read(ll &x){ ll f=1;x=0;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} x*=f; } int main() { //freopen("earthworm.in","r",stdin); //freopen("earthworm.out","w",stdout); double p = 0; int cnt = 0, n, m, q, u, v, t; scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t); p = u*1.0 / v; for(int i = 1; i <= n; i++)read(w[1][i]); sort(w[1]+1,w[1]+1+n,cmp); h[1] = h[2] = h[3] = 1; tt[1] = n; tt[2] = tt[3] = 0; int tot = n; for(int i = 1; i <= m; i++){ ll b, c, mx = -inf; tot++; int mh; for(int j = 1; j <= 3; j++) if(w[j][h[j]] > mx && h[j] <= tt[j]) mx = w[j][h[j]], mh = j; h[mh]++; //printf("%I64d %d ",mx+cnt,mh); mx += cnt; if(i % t == 0)printf("%lld ",mx); b = floor(p*mx); c = mx- b; cnt += q; w[2][++tt[2]] = b-cnt; w[3][++tt[3]] = c-cnt; } printf("\n"); int qq = 0; for(int i = 1; i <= tot; i++){ ll mx = -inf; int mh; for(int j = 1; j <= 3; j++) if(w[j][h[j]] > mx && h[j] <= tt[j]) mx = w[j][h[j]], mh = j; h[mh]++; if(i%t == 0)printf("%lld ",mx+cnt); } return 0; }

View Code

# P2831 Angry Birds

## Title Description

Kiana Recently indulged in a magical game can not extricate themselves.

In short, this game is done on a flat surface.

A slingshot is located$_{b All are real numbers.}$

When the bird falls back to the ground$x When the axis is, it will disappear instantly.$

In a certain level of the game, the first quadrant of the plane has$_{_{) 。}}$

If a bird’s flight path passes through$_{_{i A small pig will be destroyed and the bird will continue to fly along its original trajectory.}}$

If a bird’s flight path does not pass through$_{_{i Only piglets have any effect.}}$

For example, if two piglets are located respectively$_{x The birds will be destroyed by the little bird.}$

The purpose of this game is to destroy all piglets by launching small birds.

Every level of the magic game is hard for Kiana, so Kiana has also entered some mysterious instructions so that it can finish the game more easily. These instructions will be detailed in the input format.

Suppose there’s a total of this game$T Now, Kiana wants to know how many birds need to be fired at every level to destroy all the pigs. Because she can’t count, I hope you can tell her.$

## Input-output format

Input format:

The first line contains a positive integer.$T ，Represents the total number of games.$

This is the following.$_{_{_{_{) 。Data ensure that there is no identical pig in the same level.}}}}$

If$0 ，Indicates that Kiana has entered an instruction without any action.$

If$⌉ Only a little bird can kill all the pigs.$

If$⌋ A little pig.$

Guarantee$_{_{0 ，The real number in the input is kept to the two place after the decimal point.}}$

In the preceding article$3 。$

Output format:

Output one line in order for each pass.

Each row of the output contains a positive integer, which represents the minimum number of birds required for all pigs in the corresponding checkpoints.

## Input and output sample

2 2 0 1.00 3.00 3.00 3.00 5 2 1.00 5.00 2.00 8.00 3.00 9.00 4.00 8.00 5.00 5.00

1 1

3 2 0 1.41 2.00 1.73 3.00 3 0 1.11 1.41 2.34 1.79 2.98 1.49 5 0 2.72 2.72 2.72 3.14 3.14 2.72 3.14 3.14 5.00 5.00

2 2 3

1 10 0 7.16 6.28 2.02 0.38 8.33 7.78 7.68 2.09 7.46 7.86 5.77 7.44 8.24 6.72 4.42 5.11 5.42 7.79 8.15 4.99

6

## Explain

【Example interpretation 1]

There are two levels in this set of data.

The first card is the same as the case in the problem description. 2 small pigs are located (1.00,3.00) and (3.00,3.00), and only a bird that will launch a flight path of y = -x^2 + 4x can eliminate them.

There are 5 piglets in the second checkpoints, but after observation we can find that their coordinates are on the parabola y = -x^2 + 6x, so the Kiana only needs to launch a bird to kill all the pigs.

【Data range]

Answer: the original problem is also wrong, should reflect;

Each pig has two states: hitting and not hitting, so the shape is DP;

O(N*N*2^N) + O(N*N*N) Preconditioning

dp[s | g[i][j] ] = min(dp[s] +1), dp[0] = 0;

dp[s] How many birds are required for s state? G[i][j] is a parabola of pretreated birds that can hit those pigs; if the g[i][j] is useless, it will kick off or T.

#include <bits/stdc++.h> using namespace std; const int M = 20; double x[M], y[M], a[M][M], b[M][M]; int g[M][M], dp[1<<20]; const double eps = 1e-6; bool build(int i, int j){ a[i][j] = (y[i]/x[i] - y[j]/x[j]) / (x[i] - x[j]); if(a[i][j] >= 0)return false; b[i][j] = (y[i] - a[i][j]*x[i]*x[i]) / x[i]; return 1; } bool check(int i, int j, int k){ double tmp = a[i][j]*x[k]*x[k] + b[i][j] * x[k]; if(fabs(tmp - y[k]) < eps) return 1; return 0; } int main() { //freopen("angrybirds.in","r",stdin); //freopen("angrybirds.out","w",stdout); int T, n, m; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); for(int i = 1; i <= n; i++)scanf("%lf%lf",&x[i],&y[i]); memset(g, 0, sizeof(g)); memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); for(int i = 0; i <= n; i++){ for(int j = i+1; j <= n; j++){ if(!i)g[i][j] = 1<<(j-1); else if(build(i, j)){ g[i][j] |= 1<<(i-1); g[i][j] |= 1<<(j-1); for(int k = 1; k <= n; k++) if(check(i, j, k))g[i][j] |= (1<<(k-1)); } } } memset(dp, 127, sizeof(dp)); dp[0] = 0; for(int s = 0; s < (1<<n); s++) for(int i = 0; i <= n; i++) for(int j = i; j <= n; j++) dp[s|g[i][j]] = min(dp[s|g[i][j]], dp[s]+1); printf("%d\n",dp[(1<<n)-1]); } return 0; }

View Code

O（N*2^N)，

#include <bits/stdc++.h> using namespace std; const int M = 20; double x[M], y[M], a[M][M], b[M][M]; int g[M][M], dp[1<<20]; const double eps = 1e-6; inline bool build(int i, int j){ a[i][j] = (y[i]/x[i] - y[j]/x[j]) / (x[i] - x[j]); if(a[i][j] >= 0)return false; b[i][j] = (y[i] - a[i][j]*x[i]*x[i]) / x[i]; return 1; } inline bool check(int i, int j, int k){ double tmp = a[i][j]*x[k]*x[k] + b[i][j] * x[k]; if(fabs(tmp - y[k]) < eps) return 1; return 0; } inline int min(int a, int b){ return a < b ? a : b; } int down(int s){ int i = 0; while(!(s&(1<<i)))i++; return i+1; } int main() { // freopen("angrybirds.in","r",stdin); // freopen("angrybirds.out","w",stdout); int T, n, m, cnt = 0; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); for(int i = 1; i <= n; i++)scanf("%lf%lf",&x[i],&y[i]); memset(g, 0, sizeof(g)); for(int i = 1; i <= n; i++){ for(int j = i+1; j <= n; j++){ if(build(i, j)){ for(int k = 1; k <= n; k++) if(check(i, j, k))g[i][j] |= (1<<(k-1)); } } } for(int i = 1; i <= (1<<n); i++)dp[i] = 28; dp[0] = 0; for(int s = 1; s < (1<<n); s++){ int i = down(s); dp[s] = min(dp[s], dp[s-(1<<(i-1))]+1); for(int j = i+1; j<= n; j++){ int ss = (s&g[i][j]); dp[s] = min(dp[s], dp[s^ss]+1); } } printf("%d\n",dp[(1<<n)-1]); } return 0; }

View Code