第十二届

习题链接

砝码称重

首先想到的是直接爆搜，结果只过了样例，复杂度应该是 n ! n! n!，所以妥妥超时。

int a[N],vis[N],n;
int ok[100010];
int sum;
void dfs(int cur,int x,int sign){
    cur+=sign*a[x];
    if(cur>0)ok[cur]=1;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            vis[i]=1;
            dfs(cur,i,1);
            dfs(cur,i,-1);
            vis[i]=0;
        }
    }
}

其实这个题很像背包，即看某个重量可不可以被满足，考虑dp。 d p [ i ] [ j ] dp[i][j] dp[i][j]表示枚举到第 i i i个砝码，重量 j j j是否可以获得。这是最基本最容易想到的状态转移方法，在空间允许的情况下，用一个维度枚举个数，用一个维度枚举答案。因为只要不使用当前的砝码 i i i，当前可以表示的重量和 i − 1 i-1 i−1可以表示的是一样多的，因此需要先将之前的全部进行复制，然后再增加当前砝码的贡献即可。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1E5+10;
int a[110];
bool dp[110][N];
int vis[N];
int sum,cnt;
int main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];sum+=a[i];
        dp[i][a[i]]=1;
        if(!vis[a[i]]){
            vis[a[i]]=1;cnt++;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=sum;j++){
            if(!dp[i][j])//复制之前可表示重量
            dp[i][j]=dp[i-1][j];
            if(dp[i-1][j+a[i]]||dp[i-1][abs(j-a[i])]){
                //当前砝码的贡献
                if(!vis[j]){
                    vis[j]=1;cnt++;
                } dp[i][j]=1;
            }

        }
    }
    cout<<cnt<<endl;
    return 0;
}

杨辉三角

参考博客
暴力肯定是过不了的啦。
关于杨辉三角我只知道某个数等于其肩上两个数字之和…其他一概不知道，然后从百度学了以下性质：

1. 每个数等于它上方两数之和。
2. 每行数字左右对称，由1开始逐渐变大。
3. 第n行的数字有n项。
4. 前n行共[(1+n)n]/2 个数。
5. 第n行的m个数可表示为 C(n-1，m-1)，即为从n-1个不同元素中取m-1个元素的组合数。
6. 第n行的第m个数和第n-m+1个数相等 ，为组合数性质之一。
7. 每个数字等于上一行的左右两个数字之和。可用此性质写出整个杨辉三角。即第n+1行的第i个数等于第n行的第i-1个数和第i个数之和，这也是组合数的性质之一。即 C(n+1,i)=C(n,i)+C(n,i-1)。
8. (a+b)ⁿ的展开式中的各项系数依次对应杨辉三角的第(n+1)行中的每一项。
9. 斜线上数字的和等于其向左（从左上方到右下方的斜线）或向右拐弯（从右上方到左下方的斜线），拐角上的数字。1+1=2，1+1+1=3，1+1+1+1=4，1+2=3，1+2+3=6，1+2+3+4=10，1+3=4，1+3+6=10，1+4=5。
10. 将各行数字左对齐，其右上到左下对角线数字的和等于斐波那契数列的数字。1，1，1+1=2，2+1=3，1+3+1=5，3+4+1=8，1+6+5+1=13，4+10+6+1=21，1+10+15+7+1=34，5+20+21+8+1=55。

此题需要用到的性质是 2 , 4 , 5 2,4,5 2,4,5。

1. 因为左右对称，所以一个数只会在左边第一次出现，右边可以直接咔嚓掉不管了；因为每行左端都是递增的，查找的时候可采用二分。
2. 找到某个数字的行列位置就可以通过该式子知道它是第几个数字。
3. 是此题的关键性质：若某行的个数 n n n为偶数则第 n / 2 n/2 n/2个数字最大，为 C 2 × i i C_{2×i}^i C2×ii​。

知道这些性质之后就可以解题了：

1. 因为中间最大的数字都是第一次出现，因此枚举每行最大数时，若其为我们查找的数字可以直接输出其位置。
2. 从第 1 1 1行到第 33 行 33行 33行，分别对每行进行二分查找。

但是只有20分…

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n;
ll C(int a,int b){
    ll ans=1;
    for(int i=a,j=1;j<=b;i--,j++){
        ans=ans*i/j;
    }
    return ans;
}
int main(){
    cin>>n;
    if(n==1){
        cout<<1<<endl;
        return 0;
    }
    for(int i=1;i<=33;i++){//枚举每一行 i表示i+1行
        int l=1,r=(i+1)/2;//每一行二分答案
        int mid=(l+r)>>1;
        int ans=mid;
        while(l<=r){
            mid=(l+r)>>1;
            if(C(i,mid)==n){
                cout<<(1+i)*i/2+ans+1<<endl;
                return 0;
            }
            if(C(i,mid)<n){
                l=mid+1;
            else r=mid-1;
        }
    }
    return 0;
}