砝码称重

dp题

Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 7, mod = 1e9 + 7;
bitset<maxn>f;
int main() {
    int n;
    scanf("%d",&n);
    f[100000]=1;
    for(int i=1,x;i<=n;++i) {
        scanf("%d",&x);
        f|=(f<<x)|(f>>x);
    }
    int cnt(0);
    for(int i=100001;i<maxn;++i) if(f[i]) cnt+=1;
    printf("%d\n",cnt);
    return 0;
}

杨辉三角形

思路：
图片说明

由于杨辉三角的对称性，只需要考虑对称轴及其左边的元素。
注意到除了第一个斜行外，其它的斜行都是从对称轴开始递增的，对称轴上的元素等于，计算可知已经大于了，所以最早只会出现在前个斜行里，因为第个斜行中的元素都大于。
于是就可以想到从大到小枚举所在的斜行，然后二分在该斜行中的第几个。二分第个斜行时，二分的区间为，是该斜行的第一个元素，其次每个斜行的第个元素一定大于等于，是为了防止时导致程序出错。

求出在第几个斜行第几个位置后即可算出答案。

Code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 7, mod = 1e9 + 7;
int n;
ll C(int a, int b) {
    ll res = 1;
    for (int i = a, j = 1; j <= b; ++j, --i) {
        res = res * i / j;
        if (res > n) return res;
    }
    return res;
}
bool check(int k) {
    ll l=2*k,r=max(1LL*n,l);
    while(l<r) {
        int mid=(l+r)/2;
        if(C(mid,k)>=n) r=mid;
        else l=mid+1; 
    }
    if(C(r,k)==n) {
        printf("%lld\n",r*(r+1)/2+k+1);
        return true;
    }
    return false;
}
int main() {
    scanf("%d",&n);
    for(int k=16;;k--) {
        if(check(k)) return 0;
    } 
}

双向排序

图片说明

上面的黑线是原始序列，因为原始序列是升序的，所以第一个有效的操作一定是降序操作，可以证明的是最终有效的操作集合可以用上图表示，从左往右连的灰线是降序操作，从右往左的灰线是升序操作，红线包起来的灰线部分是每次操作实际需要排序的区间，且区间的左端点递增、右端点递减。
下面以升序操作为例证明：
1.相邻的操作取最大的那个。比如下面的四个操作其实等效于操作2
图片说明

2.有效区间的右端点一定是递减的，比如执行下图的操作1、2、3等效于只执行一个操作3
图片说明

Code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 7, mod = 1e9 + 7;
pair<int, bool> st[maxn];
int ans[maxn];
int main() {
    int n, m, p, q, tot(0);
    scanf("%d%d", &n, &m);
    while (m--) {
        scanf("%d%d", &p, &q);
        if (!p) {
            if (tot && !st[tot].second) q = max(q, st[tot--].first);
            while (tot > 1 && st[tot - 1].first <= q) tot -= 2;
            st[++tot] = {q, 0};
        } else if (tot) {
            if (tot && st[tot].second) q = min(q, st[tot--].first);
            while (tot > 1 && st[tot - 1].first >= q) tot -= 2;
            st[++tot] = {q, 1};
        }
    }
    int num=n,l=1,r=n;
    for(int i=1;i<=tot;++i) {
        if(st[i].second)
            while(l<st[i].first &&l<=r) ans[l++]=num--;
        else
            while(r>st[i].first&&l<=r) ans[r--]=num--;
        if(l>r) break;
    }
    if(tot&1) while(l<=r) ans[l++]=num--;
    else while(l<=r) ans[r--]=num--;
    for(int i=1;i<=n;++i) printf("%d ",ans[i]);
    return 0;
}

括号序列

图片说明
合法括号序列满足：1.左括号数等于右括号数。2.任一位置的左括号的数量不小于右括号的数量。

放左括号时一定是放在右括号前面，放右括号时同理，添加左右括号时可以插在同一个位置且互不干扰，且只有一种插入方式：，而不能是：，因为要添加尽可能少的括号。所以我们可以单独考虑放置左括号的方案数，然后相乘即可。

表示前个括号中左括号数比右括号数多个的集合数量。因为不知道最终左括号数会比右括号多多少，所以需要枚举从小到大枚举找到最小的使得。算右括号时只需要把原括号序列翻转并对每个括号取反，然后重新算新序列左括号的贡献。

状态转移：时，，因为左括号前面不能插入左括号。 时，，分别表示在前面插入个左括号。仔细观察发现，于是就有。

Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 7, mod = 1e9 + 7;
char s[5007];
int n;
ll f[5005][5005];
// when s[i]=')'：
// f[i][j]=f[i-1][j+1]+f[i][j-1]
// f[i][j-1]=f[i-1][j]+f[i-1][j-1]+...+f[i-1][0]   -->   f[i][0] = f[i - 1][1] + f[i - 1][0]
ll cal() {
    f[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        if (s[i] == '(') {
            for (int j = 0; j <= n; ++j) f[i][j] = f[i - 1][j - 1];
        } else {
            f[i][0] = (f[i - 1][1] + f[i - 1][0]) % mod;
            for (int j = 1; j <= n; ++j) {
                f[i][j] = (f[i - 1][j + 1] + f[i][j - 1]) % mod;
            }
        }
    }
    for (int i = 0; i <= n; ++i)
        if (f[n][i]) return f[n][i];
}
int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    ll l = cal();
    reverse(s + 1, s + 1 + n);
    for (int i = 1; i <= n; ++i) s[i] = '(' + ')' - s[i];
    memset(f, 0, sizeof f);
    ll r = cal();
    printf("%lld\n", l * r % mod);
    return 0;
}