BestCoder Round #71 (div.2)

比赛链接：click here

题解：

KK's Steel

问题描写叙述

我们可爱的KK遇到了一道数学难题:对于一条长为Nleft( 1leq Nleq {10}^{18}
ight)N(1≤N≤10​18​​)米的钢管，最多能够锯成几根小钢管，使得锯成的钢管互不相等且均不能围成三角形。

输入描写叙述

第一行一个数$T\left(1\le T\le 10\right)$，表示数据组数。
接着T行，每行一个整数Nleft( 1leq Nleq {10}^{18}
ight)N(1≤N≤10​18​​)，表示钢管的长度。

输出描写叙述

对于每个数据输出一个整数，表示能够锯成的钢管数。

输入例子

1
6

输出例子

3

Hint

1+2+3=6 1+2=3 他们都不同样且他们不能构成三角形。

题解：

已经忘记是哪一年的慈溪中学提前招生数学试卷里的题目了。

事实上我们不去考虑N，我们仅仅考虑最优分割策略：

首先肯定是尽量的小即1、2

既要不相等，又不能构成三角形。即每次为当前数列中最大的两项的和

那么，构成的数列为1,2,3,5,8,......

这样我们仅仅要求最接近且小于等于N的Fibonacci数的项数就可以。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef  unsigned long long LLU;
LLU a[1000]={1,1};
int main()
{
    for(int i=2; i<100; ++i) a[i]=a[i-1]+a[i-2];
    for(int i=2; i<100; ++i) a[i]+=a[i-1];
    int t;scanf("%d",&t);
    while(t--)
    {
        LLU n; scanf("%I64u",&n);
        for(LLU i=0; i<n; ++i)
        {
            if(a[i]>n)
            {
                printf("%I64u
",i-1);
                break;
            }
        }
    }
    return 0;
}

KK's Point

问题描写叙述

我们可爱的KK遇到了一道数学难题:他在一个圆上点下了互不重合的Nleft(2leq Nleq {10}^{5} 
ight)N(2≤N≤10​5​​)个点，如今他要将这$N$个点两两相连（圆内没有三条线交于一个点的情况），KK想知道图形中一共同拥有多少个交点（包含边界上的点）。

输入描写叙述

第一行一个数$T\left(1\le T\le 10\right)$，表示数据组数。
接着T行，每行一个整数Nleft(2leq Nleq {10}^{5} 
ight)N(2≤N≤10​5​​)。表示圆上的点数。

输出描写叙述

对于每个数据输出一个整数，表示交点数。

输入例子

2
3
4

输出例子

3
5

题解：

我们先撇开边界上的点无论。那么全部的点都是有两条线所构成的，手算得出N=4的时候，能形成一个点。那么。我们仅仅要知道N个点能够构成几个四边形就可以即求C(n,4),最后我们再把边界上的N个点加上， 最后的结果是C(n,4)+n;

代码：

#include <bits/stdc++.h>
using namespace std;
typedef  unsigned long long LLU;
int main()
{
    int t;scanf("%d",&t);
    while(t--)
    {
        LLU n; scanf("%I64u",&n);
        LLU ret=0;
        if(n>=4) ret=ret+n*(n-1)/2*(n-2)/3*(n-3)/4;
        ret+=n;
        printf("%I64u
",ret);
    }
    return 0;
}

KK's Chemical

问题描写叙述

我们可爱的KK有一道困难的化学题目：实验室有$N\left(1\le N\le 100\right)$瓶化学药品。编号为$0$到$N-1$，如今KK知道第i瓶当且仅当和第$c[i]$瓶放在一起时会发生爆炸。
KK得到任务要整理实验室，他须要将他们装进k个不同的盒子里。显然。为了KK的生命安全，你不能把两瓶会造成爆炸的药品放进同一个箱子。如今KK想知道有多少种不同的方案。因为答案可能会很很的大。全部将最后答案取{10}^{9}+710​9​​+7的模就可以。保证$c[i]\ne i$。

输入描写叙述

第一行一个数$T\left(1\le T\le 200\right)$，表示数据组数。
每组数据两行，第一行两个整数$N\left(1\le N\le 100\right)$和$K\left(1\le K\le 1000\right)$，表示化学药品的个数和须要放入的盒子数。
接下来第二行$N$个整数$c[i]\left(0\le c[i]\le N-1\right)$。

输出描写叙述

对于每个数据输出一个整数，表示方案数对{10}^{9}+710​9​​+7取模后的结果。

输入例子

3
3 3
1 2 0
4 3
1 2 0 0
3 2
1 2 0

输出例子

6
12
0

题解：

依据药品之间的相互关系。我们能够构建一张图。我们对相互会发生反应的药品连边

这个图的特征，是一个环加上一些“树”（可能有多个联通块）

一个环（1,2,3,4,5……。n）m染色的方案数：递推，设第一个点颜色为1

f[I,1]表示i点颜色为1的种数，f[I,0]为颜色不为1时(不考虑n与1颜色不同)

则F[I,0]=f[i-1,0]*(m-2)+f[i-1,1]*(m-1)，F[I,1]=f[i-1,0]

那么方案数为f[n,0]*m

一个根节点颜色固定且有k个孩子的树的m染色的方案数={(m-1)}^{k}(m−1)​k​​,由于每一个点的颜色仅仅要与他的父亲颜色不同，即m-1种

由于乘法原理。一个联通块的方案数=环方案数*以环上每一个点为根的树的积。多个联通块。再连乘就可以。

KK's Number

问题描写叙述

我们可爱的KK有一个有趣的数学游戏:这个游戏须要两个人，有Nleft(1leq Nleq 5*{10}^{4} 
ight)N(1≤N≤5∗10​4​​)个数。每次KK都会先拿数。每次能够拿随意多个数，直到$N$个数被拿完。
每次获得的得分为取的数中的最小值，KK和对手的策略都是尽可能使得自己的得分减去对手的得分更大。在这种情况下，终于KK的得分减去对手的得分会是多少？

输入描写叙述

第一行一个数$T\left(1\le T\le 10\right)$，表示数据组数。
对于每组数据包括两行，第一行一个整数Nleft(1leq Nleq 5*{10}^{4} 
ight)N(1≤N≤5∗10​4​​)，表示个数，第二行$N$个正整数（不超过{10}^{9}10​9​​）。

输出描写叙述

对于每个数据输出一个整数，表示终于KK的得分减去对手的得分。

输入例子

1
3
1 3 1

输出例子

2

Hint

首先KK取走3，然后对手取走两个1，那么终于分差为2。

题解：

显然。每一个人的策略就是都会拿剩下的数中最大的某几个数

假如我们用f[i]表示当剩下i个数的时候先手得分-后手得分的最小值

那么得到$f[i]=max\left(a[j+1]-f[j]\right)(1<j\le i)$

可是这样做。是要超时的

我们最好还是简单转换一下 f[i]=_max; _max=max(_max,a[i+1]-f[i]);

代码：

#include <bits/stdc++.h>
using namespace std;
typedef  unsigned long long LLU;
const int maxn = 1e5+10;
int a[maxn],b[maxn];
int main()
{
    int t;t=read();
    while(t--)
    {
        int n,maxx=0; n=read();
        for (int i=1; i<=n; i++)  a[i]=read();
        sort(a+1,a+n+1);
        for (int i=1; i<=n; i++)  maxx=max(maxx,a[i]-b[i-1]),b[i]=maxx;
        printf("%d
",b[n]);
    }
    return 0;
}