Article From:https://www.cnblogs.com/EdSheeran/p/9061037.html

P2822 Combinatorial number problem

Title Description

Combinatorial numberC_n^mCnm It means thatnn Choose one of the items.mm The number of items. For example, from the point of view(1,2,3)(1,2,3) Two of the three items can be selected(1,2),(1,3),(2,3)(1,2),(1,3),(2,3) These three options. According to the definition of combination number, we can give the combinatorial number.C_n^mCnm The general formula:

C_n^m=\frac{n!}{m!(n-m)!}Cnm=m!(nm)!n!

Among themn!=1\times2\times\cdots\times nn!=1×2××n ;In particular, definition0!=10!=1 。

Shallots want to know if they are given.n,mn,m Andkk ,For all of them0\leq i\leq n,0\leq j\leq \min \left ( i, m \right )0in,0jmin(i,m) How many pairs are(i,j)(i,j) SatisfiedC_i^jCij It iskk The multiple of the number.

Input-output format

Input format:

 

The first line has two integerst,kt,k ,Among themtt Representing the total number of test data of the test point.kk The meaning of the problem is described.

Nexttt Row two integersn,mn,m ,Among themn,mn,m The meaning of the problem is described.

 


Output format:

 

Collectivett Line, an integer per line represents all of them0\leq i\leq n,0\leq j\leq \min \left ( i, m \right )0in,0jmin(i,m) How many of them are there(i,j)(i,j) SatisfiedC_i^jCij It iskk The multiple of the number.

 

Input and output sample

Input sample #1: replication

1 2
3 3
Output sample #1: replication

1
Input sample #2: replication

2 5
4 5
6 7
Output sample #2: replication

0
7

Explain

【Example 1 illustrates]

In all possible circumstances, onlyC_2^1 = 2C21=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\lfloor c \rfloorc⌋ Expresscc Get down, for example.\lfloor 3.0 \rfloor = \lfloor 3.1 \rfloor = \lfloor 3.9 \rfloor = 33.0=3.1=3.9=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 cricketsnn Earthwormsnn It is a positive integer). Each earthworm has a length, and we set up an earthworm.ii The length of earthwormsa_iai ( i=1,2,\dots,ni=1,2,,n),And ensure that all lengths are nonnegative integers (i.e., there may be a length of 0.00 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.pp (It is a satisfaction.0 < p < 10<p<1 The rational number of the earthworm is decided by the length of the earthworm.xx ,The God knife hand will cut it into two lengths.\lfloor px \rfloorpx⌋ Andx – \lfloor px \rfloorxpx⌋ Earthworms. In particular, if one of these two numbers is equal to00 ,This is the length.00 The earthworms are also preserved. Besides, besides the two new earthworms that have just been produced, the length of other earthworms will increase.qq (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.mm Seconds can come… Itmm For non negative integers)

The cricket king wants to know thismm The war in the second. Specifically, he wants to know:

  • mm The length of the earthworm before being cut off every second.mm Numbers);
  • mm After a second, the length of all earthwormsn + mn+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 integersn,m,q,u,v,tn,m,q,u,v,t ,Among themn,m,qn,m,q To see the meaning of the problem;u,v,tu,v,t It’s a positive integer; you need to do it yourself.p=u / vp=u/v (Guarantee0 < u < v0<u<v ); tt It is the output parameter, and its meaning will be explained in the output format.

Second lines includenn A non negative integer.a_1, a_2, \dots, a_na1,a2,,an ,Initial timenn The length of only earthworms.

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

Guarantee1 \leq n \leq 10^51n105 , 0 \leq m \leq 7 \times 10^60m7×106 , 0 < u < v \leq 10^90<u<v109 , 0 \leq q \leq 2000q200 , 1 \leq t \leq 711t71 , 0 \leq a_i \leq 10^80ai108 。

 


Output format:

 

First line output\left \lfloor \frac{m}{t} \right \rfloortm⌋ A number of integers, according to the order of time, in turntt Seconds2t2t Seconds3t3t Second,… The length of an earthworm (before being cut).

Second lines output\left \lfloor \frac{n+m}{t} \right \rfloortn+m⌋ Integer, outputmm The length of earthworms after a second; the order of output from top to bottom.tt ,Tertiary2t2t ,Tertiary3t3t,……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

Input sample #1: replication

3 7 1 1 3 1
3 3 2
Output sample #1: replication

3 4 4 4 5 5 6
6 6 6 5 5 4 4 3 2 2
Input sample #2: replication

3 7 1 1 3 2
3 3 2
Output sample #2: replication

4 4 5
6 5 4 3 2
Input sample #3: replication

3 7 1 1 3 9
3 3 2
Output sample #3: replication

//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(0,0)(0,0) Every time, Kiana can use it to launch a red bird to the first quadrant.y=ax^2+bxy=ax2+bx The curvea,ba,b It is the parameter specified by Kiana and must be satisfied.a < 0a<0 , a,ba,b All are real numbers.

When the bird falls back to the groundxx When the axis is, it will disappear instantly.

In a certain level of the game, the first quadrant of the plane hasnn Green piglets, among themii The pig is located in the coordinates.\left(x_i,y_i \right)(xi,yi) 。

If a bird’s flight path passes through\left( x_i, y_i \right)(xi,yi) ,So thenii 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\left( x_i, y_i \right)(xi,yi) ,So the whole process of this little bird’s flight will not be the case.ii Only piglets have any effect.

For example, if two piglets are located respectively(1,3)(1,3) And(3,3)(3,3) ,Kiana You can choose to launch a flight path.y=-x^2+4xy=x2+4x 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 gameTT 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.TT ,Represents the total number of games.

This is the following.TT A message for a checkpoint. The first line of each level contains two non negative integer valuesn,mn,m ,They represent the number of pigs in the checkpoint and the mysterious type of Kiana input. The nextnn In lineii Row contains two positive real numbersx_i,y_ixi,yi ,To represent the thirdii Only piglet coordinates(x_i,y_i)(xi,yi) 。Data ensure that there is no identical pig in the same level.

Ifm=0m=0 ,Indicates that Kiana has entered an instruction without any action.

Ifm=1m=1 ,The card will be satisfied: at most\lceil n/3 + 1 \rceiln/3+1⌉ Only a little bird can kill all the pigs.

Ifm=2m=2 ,Then the threshold will be satisfied: there must be an optimal solution, one of which has eliminated at least one bird.\lfloor n/3 \rfloorn/3⌋ A little pig.

Guarantee1\leq n \leq 181n18 , 0\leq m \leq 20m2 , 0 < x_i,y_i < 100<xi,yi<10 ,The real number in the input is kept to the two place after the decimal point.

In the preceding article\lceil c \rceilc⌉ And\lfloor c \rfloorc⌋ Respectively.cc To draw upwards and downwards, for example:\lceil 2.1 \rceil = \lceil 2.9 \rceil = \lceil 3.0 \rceil = \lfloor 3.0 \rfloor = \lfloor 3.1 \rfloor = \lfloor 3.9 \rfloor = 32.1=2.9=3.0=3.0=3.1=3.9=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

Input sample #1: replication

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
Output sample #1: replication

1
1
Input sample #2: replication

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
Output sample #2: replication

2
2
3
Input sample #3: replication

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
Output sample #3: replication

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

 

Link of this Article: Noip2016day2

Leave a Reply

Your email address will not be published. Required fields are marked *