“科林明伦杯”哈尔滨理工大学第十届程序设计竞赛(同步赛)

A.点对最大值

这里有一棵树，每个点和每条边都存在一个价值。对于树上点对的价值，包括点对的起点和终点以及路径上边权值之和，不包括路径上其他点值。
求这颗树上最大的点对价值为多少。点对至少需要两个点。

输入描述:
输入t，代表有t组样例。每组样例第一行输入n，代表有n个点。接下来有n-1行，第i行有a[i]和b[i]，代表a[i]节点与i节点存在一条边，且边的值为b[i]，2<=i<=n。接下来一行有n个值c[j]，代表每个节点j的价值，1<=j<=n。
（t1，n<1e6，a[i]<i，-500<=b[i]<=500，-500<=c[j]<=500）
题解
考虑树形dp，我们发现如果维护带两个端点的链比较麻烦，所以我们我们考虑维护只有一个端点的链，那么带两个端点的最长链也就是子树中带一个端点的最长两条链相连，因此设表示以为根的子树里的最长单端点链，那么我们能得到转移方程

dp[u]=max(dp[v]+C[e],dp[u]);

同时每次更新时我们还要再记录一下次长链，最长链加次长链就子树中权值最大的双端点最长链的权值了

代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lowbit(x) x&(-x)

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int N = 1e6+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps =1e-9;
const double PI=acos(-1.0);
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const int exdir[4][2]={1,1,1,-1,-1,1,-1,-1};

vector<int> RG[N];
int U[N],V[N],C[N],W[N];

int n,dp[N],ans;
void dfs(int u,int fa){
    int a=W[u],b=-INF;
    for(int e : RG[u]){
        int v = U[e] ^ V[e] ^ u;//儿子节点
        if(v == fa) continue;
        dfs(v,u);
        b=max(dp[v]+C[e],b);
        if(a<b)swap(a,b);
    }
    ans=max(ans,a+b);
    dp[u]=a;
}

void solve(){
    memset(RG,0,sizeof(RG));
    cin >> n;
    for(int i = 1;i < n;++i){
        cin >> U[i] >> C[i]; V[i] =i+1;
        RG[U[i]].push_back(i);
        RG[V[i]].push_back(i);
    }
    for(int i=1;i<=n;i++)cin>>W[i];
    ans=0;
    dfs(1,0);
    cout<<ans;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--)solve(),cout<<'\n';
    //solve();
    return 0;
}

B.减成一

题意

存在n个数，每次操作可以任选一个区间使得区间内的所有数字减一。问最少多少次操作，可以让所有数都变成1。数据保证一定有解。
题解
差分处理，想要得到所有数都一样，也就是要使差分序列的 2~n 项全为 0。而第 1 项代表第一个数的大小，改变第1项只会让数列整体变大或变小，并不影响数列相同。计算差分序列，记录差分序列中正数和负数的个数，每次操作可以让差分序列中的两个数一个 +1 另一个 -1，因此，也就是差分后 Max( 正数和，负数和 ) 次。然后要全变1，答案就是（加上要么是头要么是尾接近1的数减）

max(p,q)+min(abs(a[1]),abs(a[n]))-1;

代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define lowbit(x) x&(-x)
#define pb push_back
#define iter set<int>::iterator

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int N = 1e6+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const int exdir[4][2]={1,1,1,-1,-1,1,-1,-1};

ll qpow(ll x,ll y){
    ll ans=1,t=x;
    while(y>0){
        if(y&1)ans*=t,ans%=mod;
        t*=t,t%=mod;
        y>>=1;
    }
    return ans%mod;
}
ll a[N];
void solve(){
    int n;cin>>n;
    int q=0,p=0;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=2;i<=n;i++){
        if(a[i]-a[i-1]>0)p+=a[i]-a[i -1];
        else q-=a[i]-a[i-1];
    }
    cout<<max(p,q)+min(abs(a[1]),abs(a[n]))-1;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--)solve(),cout<<'\n';
    //solve();
    return 0;
}

C.面积
思路：
签到题，直接输出
代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lowbit(x) x&(-x)

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int N = 1e5+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps =1e-9;
const double PI=acos(-1.0);
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const int exdir[4][2]={1,1,1,-1,-1,1,-1,-1};

ll qpow(ll x,ll y){
    ll ans=1,t=x;
    while(y>0){
        if(y&1)ans*=t,ans%=mod;
        t*=t,t%=mod;
        y>>=1;
    }
    return ans%mod;
}

void solve(){
    double x;cin>>x;
    printf("%.2f",x*x+x*x*3.14/2);
}

int main(){
    //ios::sync_with_stdio(0);
    //cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--)solve(),cout<<'\n';
    //solve();
    return 0;
}

D.扔硬币
有n枚硬币，每枚硬币扔出来是正面和反面的概率各占50%。小明同时扔下了n枚硬币后，已知至少有m枚硬币是反面。请问恰好有k枚硬币是正面的概率是多少。对于结果是p/q，输出分数取模1e9+7后的结果。
题解
条件概率，由于已知部分硬币的方向。因此，扔n个硬 币的情况要在2的n次幂的中去掉少于m个硬 币是反面的情况。对于k+m>n是不可能的，直接输出0， 其余情况：C(n,k)/[ 2^n - ∑(C(n,i)) ] (i<m)，预处理减少常数
代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lowbit(x) x&(-x)

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int N = 1e5+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps =1e-9;
const double PI=acos(-1.0);
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const int exdir[4][2]={1,1,1,-1,-1,1,-1,-1};

ll jc[N],ny[N];
ll qmi(ll a,ll k){
    ll res=1%mod;
    while(k>0){
        if(k&1)res=res*a%mod;
        a=a*a%mod;
        k>>=1;
    }
    return res%mod;
}
void start(){
    jc[0]=1;ny[0]=1;
    for(int i=1;i<=N-5;i++){
        jc[i]=jc[i-1]*i%mod;
        ny[i]=ny[i-1]*qmi(i,mod-2)%mod;
    }
}
ll C(int a,int b){return jc[a]*ny[b]%mod*ny[a-b]%mod;}
ll a[N];
void solve(){
    ll n,m,k;cin>>n>>m>>k;
    if(n-m<k)cout<<0;
    else{
        ll y=0;
        for(int i=0;i<m;i++)
            y=(y+C(n,i)*a[n])%mod;
        y=(mod+1-y)%mod;
        ll x=C(n,k)*a[n]%mod;
        cout<<x*qmi(y,mod-2)%mod;
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    start();
    a[0]=1;
    for(int i=1;i<=100000;i++)a[i]=a[i-1]*qmi(2,mod-2)%mod;
    int t;cin>>t;
    while(t--)solve(),cout<<'\n';
    //solve();
    return 0;
}

E.赛马

一天小明与他同学准备赛马，他们每人有n匹马，每匹马有一个固定的战力值，战力值高的马会战胜战力值低的马并赢得比赛。每匹马只能出场比赛一次。小明偷看到了他对手每匹马的出场顺序，小明在更改自己马出场顺序后最多能赢多少场比赛。
题解
排一下序，从小到大模拟一下即可
代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lowbit(x) x&(-x)

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int N = 1e5+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps =1e-9;
const double PI=acos(-1.0);
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const int exdir[4][2]={1,1,1,-1,-1,1,-1,-1};

ll qpow(ll x,ll y){
    ll ans=1,t=x;
    while(y>0){
        if(y&1)ans*=t,ans%=mod;
        t*=t,t%=mod;
        y>>=1;
    }
    return ans%mod;
}
int a[N],b[N];
void solve(){
    int n;cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++)cin>>b[i];
    sort(a,a+n),sort(b,b+n);
    int ans=0,t=0;
    for(int i=0;i<n;i++){
        while(t<n&&a[t]<=b[i])t++;
        if(a[t]>b[i])ans++,t++;
    }
    cout<<ans;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--)solve(),cout<<'\n';
    //solve();
    return 0;
}

F.三角形

小明有一根长度为a的木棒，现在小明想将木棒分为多段（每段木棒长度必须为整数），
使得分隔后的木棍中，取出的任意三段都不能构成三角形，小明想知道木棒最多被分成几段？
题解
构造斐波那契数列，找前缀和恰好大于a的那项
代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lowbit(x) x&(-x)

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int N = 1e5+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps =1e-9;
const double PI=acos(-1.0);
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const int exdir[4][2]={1,1,1,-1,-1,1,-1,-1};

ll qpow(ll x,ll y){
    ll ans=1,t=x;
    while(y>0){
        if(y&1)ans*=t,ans%=mod;
        t*=t,t%=mod;
        y>>=1;
    }
    return ans%mod;
}
unsigned long long a[100],n;
void solve(){
    cin>>n;
    for(int i=1;i<=93;i++){
        if(n<a[i]){cout<<i-1;return;}
        n-=a[i];
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    a[1]=1,a[2]=1;
    for(int i=3;i<=93;i++)a[i]=a[i-1]+a[i-2];
    int t;cin>>t;
    while(t--)solve(),cout<<'\n';
    //solve();
    return 0;
}

H.直线
平面上存在n条直线。请问n条直线在平面上最多存在多少交点。
题解
直接输出n(n-1)/2,大数乘法
代码
java的

import java.io.*;
import java.math.*;
import java.util.*;
import java.text.*;

public class Main {
    public static void main(String[] args)   {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        int n=cin.nextInt();
        for(int i=0;i<n;i++){
        BigInteger k=new BigInteger("1"),t= new BigInteger("2");
        BigInteger a,b,c;
        a=cin.nextBigInteger();
        c=a.subtract(k);
        b=c.multiply(a);
        System.out.println(b.divide(t));
        }

    }
}

J.最大值

有一个字符串s，对于字符串中一个非前缀子串恰好为字符串的前缀我们称之为ac串。
请问给出一个字符串他的ac串最大长度为多少
题解
当时直接kmp+二分，然后发现憨憨了，直接next数组最大值就好了
代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lowbit(x) x&(-x)

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int N = 1e5+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps =1e-9;
const double PI=acos(-1.0);
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const int exdir[4][2]={1,1,1,-1,-1,1,-1,-1};

ll qpow(ll x,ll y){
    ll ans=1,t=x;
    while(y>0){
        if(y&1)ans*=t,ans%=mod;
        t*=t,t%=mod;
        y>>=1;
    }
    return ans%mod;
}

int net[100005];
int getfail(string p,int plen){
    net[0]=0;net[1]=0;
    for(int i=1;i<plen;i++){
        int j=net[i];
        while(j&&p[i]!=p[j])j=net[j];
        net[i+1]=(p[i]==p[j])?j+1:0;
    }
}
int kmp(string s,string p){
    int last=-1;
    int slen=s.size(),plen=p.size();
    getfail(p,plen);
    int j=0,k=0;
    for(int i=0;i<slen;i++){
        while(j&&s[i]!=p[j])j=net[j];
        if(s[i]==p[j])j++;
        if(j==plen){
            k++;
        }
        if(k>1)return 1;
    }
    return 0;
}
void solve(){
    int n;
    string s;cin>>s;
    n=s.size();
    int l=0,r=n-1;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(kmp(s,s.substr(0,mid+1)))l=mid;
        else r=mid-1;
    }
    cout<<l+1;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--)solve(),cout<<'\n';
    //solve();
    return 0;
}