Twelfth

Exercise link

Weight weighing

The first thing I thought of was the direct explosion search. The result only passed the example, and the complexity should be n ! n! n!， So it's time-out.

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;
        }
    }
}

In fact, this question is very much like a backpack, that is, to see whether a certain weight can be satisfied, consider dp. d p [ i ] [ j ] dp[i][j] dp[i][j] indicates enumeration to i i i weights, weight j j j is available. This is the most basic and easy to think of state transition method. When space allows, use one dimension to enumerate numbers and one dimension to enumerate answers. Because as long as the current weight is not used i i i. Current weight and i − 1 i-1 i − 1 can represent the same number, so you need to copy all the previous ones first, and then increase the contribution of the current weight.

#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])//Weight can be represented before copying
            dp[i][j]=dp[i-1][j];
            if(dp[i-1][j+a[i]]||dp[i-1][abs(j-a[i])]){
                //Contribution of current weight
                if(!vis[j]){
                    vis[j]=1;cnt++;
                } dp[i][j]=1;
            }

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

Yang Hui triangle

Reference blog
Violence must be unbearable.
About Yang Hui triangle, I only know that a certain number is equal to the sum of the two numbers on his shoulder... I don't know anything else. Then I learned the following properties from Baidu:

1. Each number is equal to the sum of the two numbers above it.
2. The numbers in each line are symmetrical from left to right, and gradually increase from 1.
3. The number on line n has n items.
4. There are [(1+n)n]/2 in the first n lines.
5. The number of m in line n can be expressed as C(n-1, m-1), that is, the combined number of M-1 elements from n-1 different elements.
6. The m-th number in line n is equal to the n-m+1 number, which is one of the properties of combinatorial numbers.
7. Each number is equal to the sum of the left and right numbers in the previous line. This property can be used to write the whole Yang Hui triangle. That is, the i-th number in line n+1 is equal to the sum of the i-1st number and the i-th number in line n, which is also one of the properties of combinatorial numbers. That is, C(n+1,i)=C(n,i)+C(n,i-1).
8. The coefficients in the expansion of (a+b)n correspond to each term in row (n+1) of Yang Hui triangle in turn.
9. The sum of the numbers on the slash is equal to the number on the corner when it turns left (the slash from the top left to the bottom right) or right (the slash from the top right to the bottom left). 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. Align the numbers in each row to the left, and the sum of the diagonal numbers from the top right to the bottom left is equal to the number of Fibonacci series. 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.

The nature of this question is 2 , 4 , 5 2,4,5 2,4,5.

1. Because of the symmetry between the left and right, a number will only appear on the left for the first time, and can be directly clicked off on the right; Because the left end of each row is incremented, you can use dichotomy when searching.
2. If you find the row and column position of a number, you can know which number it is through this formula.
3. Is the key property of this question: if the number of a line n n If n is an even number, then the n / 2 n/2 n/2 digits, maximum, is C 2 × i i C_{2×i}^i C2×ii​.

Once you know these properties, you can solve the problem:

1. Because the largest number in the middle appears for the first time, when enumerating the maximum number of each line, if it is the number we find, we can directly output its position.
2. From the first 1 1 Lines 1 to 33 that 's ok Line 33 33 rows. Perform binary search on each row.

But only 20 points

#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++){//Enumerating each row i means i+1 row
        int l=1,r=(i+1)/2;//Two answers per line
        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;
}