Solution to the problem of the 10th Programming Competition (synchronized competition) of Harbin University of technology "Colin Minglun Cup"

“ Colin minlon cup ” The 10th programming competition of Harbin University of Technology ( Synchronized competition ) Answer key

Mengxin has come to write a solution
Original link

B Reduce to one

The question ： There is n Number , Each operation can choose an interval to make all the numbers in the interval minus one . Ask at least how many operations , Can make all numbers become 1.

tips: Original topic of Luogu “ Building blocks competition ”. A similar idea , You don't even need an array , As long as a last Variable record “ The last data operation was performed several times ”. Note that if the input data is 1,last To set as 0, Express “ The last data does not need to be operated ”.
The answer is to use a differential array , Obviously more troublesome ~
But we can learn from ideas ！
“ By calculating Difference array , The operation can be changed to select first Take a number minus and choose a number plus one again （ Left end point of interval -1, One after the right endpoint +1）. The differential array of targets becomes The first number is 1, Others are 0 Array of （1,1,1 The difference between 1,0,0）.
• The fastest operation is to reduce the first number of the difference array to 1, The rest is reduced to 0. That is, the operand is The sum of the positive numbers of the difference array -1.”

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int t,n;
ll num,ans,last,tmp;

void solve(){
    
	scanf("%d",&n);
	ans = last = 0;
	for(int i = 1; i <= n; ++i){
    
		scanf("%lld",&num);
		if(num == 1){
    
			last = 0; 
			continue;
		}
		tmp = num - 1;
		if(tmp > last)	
			ans += tmp - last;
		last = tmp;
	}
	printf("%lld\n",ans);
}
int main(){
    
	scanf("%d",&t);
	while(t--){
    
		solve();
	}
	return 0;
}

C area

tips: Sign in problem . Be careful PI take 3.14. Calculate the area directly .

#include<bits/stdc++.h>
using namespace std;
const double PI = 3.14;
int t;
double x,ans;

int main(){
    
	scanf("%d",&t);
	while(t--){
    
		scanf("%lf",&x);
		ans = x * x + x * x * PI / 2.0;
		printf("%.2lf\n",ans);
	}
	return 0;
}

D Toss a coin

The question ： Left behind n After a coin , At least... Are known m This coin is the reverse . I happen to have k What is the probability that a coin is positive .

tips: Conditional probability . There are two situations ：
A. about k+m>n It's impossible , Direct output 0.
B. Other cases ：C(n,k)/[ 2^n - ∑(C(n,i)) ] (i<m)
Apply the conditional probability formula .A The event is “ throw n Coin , There happens to be k Coins face up ”（ molecular ）.B The event is “ throw n Coin , There are at least m The reverse side of the coin is up . Convert at least to at most , That is to say 0,1,2……（m-1) The probability of a coin reversing , use 1 Subtract is what you want .

After processing the expression , Use the inverse element directly + Fermat's theorem can deal with data . Be careful n 1e5 The amount of data , When finding factorial Do not use (a * b ) % mod, And you want to use (a % mod) * (b % mod) % mod Prevent overflow .

#include<bits/stdc++.h>
#define ll long long 
const ll mod = 1e9 + 7;

int n,m,k,t,fac[100005];
ll ksm(ll x ,ll n){
    
    ll rec = 1;
    while(n){
    
        if (n & 1)
            rec = (rec % mod * x % mod) % mod;
        x = (x % mod * x % mod )% mod;
        n >>= 1;
    }
    return rec;
}

void makefac(int x){
    
	fac[0] = 1;
	for(int i = 1; i <= x; ++i)
		fac[i] = (fac[i - 1] % mod * i % mod) % mod;
}

ll getC(int n, int m){
    
	return fac[n] * ksm(fac[m], mod - 2) % mod * ksm(fac[n - m], mod - 2) % mod; 
}

void solve(){
    
	scanf("%d%d%d",&n,&m,&k);
	if(m + k > n)	printf("0\n");
	else{
    
		makefac(n + 5);
		ll tmp1 = getC(n,k);
		ll tmp2 = ksm(2,n);
		ll tmp3 = 0;
		for(int i = 0; i < m; ++i)
			tmp3 = (tmp3 % mod + getC(n,i) % mod) % mod;
		ll tmp4 = (tmp2 % mod - tmp3 % mod + mod) % mod;
		printf("%lld\n",(tmp1 % mod * ksm(tmp4,mod - 2) % mod) % mod);
	}
}
int main(){
    
	scanf("%d",&t);
	while(t--){
    
		solve();
	}
	return 0;
}

E horse racing

The question ： One day Xiao Ming and his classmates were preparing for the horse race , Each of them has n horse , Each horse has a fixed combat power value , The horse with high combat power will defeat the horse with low combat power and win the race . Each horse can only race once . Xiao Ming spied on the order of each horse of his opponent , How many matches can Xiao Ming win at most after changing his horse's appearance order .

tips: It has nothing to do with sequence ~ Sort the two arrays directly , Then monotonously go through your horse .

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1005;
int t,n,ans,now,bookmy[1005],book[1005];
void solve(){
    
	scanf("%d",&n);
	ans = 0, now = 1;
	for(int i = 1; i <= n; ++i)
		scanf("%d",&bookmy[i]);
	for(int i = 1; i <= n; ++i)
		scanf("%d",&book[i]);
	sort(bookmy + 1, bookmy + 1 + n);
	sort(book + 1, book + 1 + n);
	for(int i = 1; i <= n; ++i){
    
		while(bookmy[now] <= book[i] && now <= n)
			now++;
		if(now > n)	break; 
		if(bookmy[now] > book[i])	ans++,now++;
	}
	printf("%d\n",ans);
}

int main(){
    
	scanf("%d",&t);
	while(t--){
    
		solve();
	}
	return 0;
}

F. triangle

The question ： Xiao Ming has one with a length of a My stick , Now Xiao Ming wants to divide the stick into several sections （ The length of each stick must be an integer ）, Make the separated wooden sticks , Any three segments taken out cannot form a triangle , Xiao Ming wants to know how many sections the stick is divided into at most ？

tips: To get the most appropriate solution , Triangular Side length must be fib The sequence .（ Any two adjacent terms correspond to two short sides , The sum is exactly equal to the third side ）. Such as 20, Can be divided into 1 1 2 3 5 8 , common 6 paragraph . If the remaining length is insufficient , The answer remains the same .（ It is equivalent to adding the remaining length to the longest side . Such as 22, Can be divided into 1 1 2 3 5 10, At most, it can only be divided into 6 paragraph ）.

it is to be noted that a The scope of the 2^64 - 1, open ll It will explode （2 ^ 63), So want to use unsigned long long , Use when reading %llu Place holder ！

#include<bits/stdc++.h>
#define ll unsigned long long
using namespace std;
 
ll a,ans,now,last,rec;
int t;
 
void solve(){
    
    scanf("%llu",&a);
    now = 2, last = 1, ans = 2;
    if(a == 1){
    
        printf("1\n");
        return ;
    }  
    if(a == 2 || a == 3)    printf("2\n");
    else{
    
        a -= 2;
        while(a >= now){
    
            a -= now;
            ans++;
            rec = now;
            now += last;
            last = rec;
        }
        printf("%llu\n",ans);
    }
}
 
int main(){
    
    scanf("%d",&t);
    while(t--){
    
        solve();
    }
    return 0;
}

H. A straight line

The question ： On the plane n A straight line . Excuse me, n How many intersections does a straight line have on the plane at most .

tips:n Two lines intersect , At most n(n-1) / 2 A point of intersection . n To reach the scope of 1e15, Use large numbers .

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    

	public static void main(String[] args) {
    
		Scanner cin = new Scanner(System.in);
		int t = cin.nextInt();
		while(t-- > 0) {
    
			BigInteger n = cin.nextBigInteger();
			BigInteger tmp = n.multiply(n.subtract(BigInteger.valueOf(1)));
			System.out.println(tmp.divide(BigInteger.valueOf(2)));
		}
	}
}

J Maximum

The question ： There's a string s, For a non prefix substring in a string that happens to be the prefix of the string, we call it ac strand . Please give a string of his ac What is the maximum length of the string .

tips:AC String is actually kmp in next The meaning of array , So find the string next Array to get the answer .( What I ask here is D Array , Traverse D Array , The maximum value is the answer .）

#include<bits/stdc++.h>
using namespace std;

int t,ans;
char str[100005];  
int d[100005];
void Getd(const char *p,int d[] ){
    
    int i = 1, j = 0, np = strlen(p);
    while(i < np){
    
        if(p[j] == p[i])
            d[i++] = ++j;
        else{
    
            if(j > 0)   j = d[j-1];
            else        i++;
        }
    }
}

int main(){
    
	scanf("%d",&t);
	while(t--){
    
		memset(d,0,sizeof(d));
		getchar();
		scanf("%s",str);
		Getd(str, d);
		int len = strlen(str);
		ans = 0;
		for(int i = 0; i < len; ++i){
    
			int tmp = d[i];
			ans = max(ans,tmp);
		}
		printf("%d\n",ans);
	} 
	return 0;
}