当前位置:网站首页>Solution to the problem of the 10th Programming Competition (synchronized competition) of Harbin University of technology "Colin Minglun Cup"
Solution to the problem of the 10th Programming Competition (synchronized competition) of Harbin University of technology "Colin Minglun Cup"
2022-07-05 08:51:00 【Qizi K】
“ 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;
}
边栏推荐
- js异步错误处理
- Programming implementation of ROS learning 6 -service node
- Halcon snap, get the area and position of coins
- Use arm neon operation to improve memory copy speed
- Guess riddles (10)
- 696. 计数二进制子串
- 猜谜语啦(3)
- Programming implementation of ROS learning 5-client node
- [牛客网刷题 Day4] JZ55 二叉树的深度
- 容易混淆的基本概念 成员变量 局部变量 全局变量
猜你喜欢
随机推荐
多元线性回归(sklearn法)
Golang foundation - the time data inserted by golang into MySQL is inconsistent with the local time
MPSoC QSPI Flash 升级办法
Low code platform | apaas platform construction analysis
ORACLE进阶(三)数据字典详解
C#绘制带控制点的Bezier曲线,用于点阵图像及矢量图形
Business modeling | process of software model
C# LINQ源码分析之Count
Apaas platform of TOP10 abroad
猜谜语啦(7)
JS asynchronous error handling
深度学习模型与湿实验的结合,有望用于代谢通量分析
OpenFeign
Redis实现高性能的全文搜索引擎---RediSearch
整形的分类:short in long longlong
Halcon shape_ trans
Guess riddles (7)
Numpy 小坑:维度 (n, 1) 和 维度 (n, ) 数组相加运算后维度变为 (n, n)
[matlab] matlab reads and writes Excel
Business modeling of software model | object modeling