L1-7 拼接梯子

等比数列求前n项和公式图片说明 (公比为2，首项也为2)，如果图片说明 是可能凑出来的（就是个二进制啊。。），反之一定表示不出来，同时，因为没有 权为1的梯子，所以奇数也是一定表示不出来的。对那些可以表示的数，找出它二进制为1的位置。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ll k,n;cin>>k>>n;
    if((1ll<<(k+1))-2<n || n&1) cout<<"No";
    else{
        cout<<"Yes"<<endl;
        ll q=0;
        for(ll i=0;i<63;i++){
            if(n>>i&1) q=i;
        }
        cout<<(1ll<<q);
    }
    return 0;
}

L1-8 幻想乡炼金学

模拟题

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define dd(x) cout << #x << " = " << x << "    "
#define de(x) cout << #x << " = " << x << endl
const ll mod = 1e9 + 7;
const int N = 1e5 + 7;
const int inf = 0x3f3f3f3f;
ll gcd(ll a,ll b){return b ? gcd(b,a % b) : a;}
string s,ss,sss;
int main()
{
    getline(cin,s);
    for(int i = 0;i < s.size();++i){
        if(s[i] != ' '){
            ss += s[i];
        }
    }
    string tmp;
    int cnt = 0;
    for(int i = 0;i < ss.size();++i){
        if(ss[i] <= 'Z' && ss[i] >= 'A' && tmp.size()){
            sss += tmp;
            tmp = "";
            tmp += ss[i];
        }
        else if(ss[i] == '('){
            sss += tmp;
            tmp = "";
            while(ss[++i] != ')')
                tmp += ss[i];
            i++;
            cnt = 0;
            while(ss[i] != '}'){
                i++;
                if(ss[i] <= '9' && ss[i] >= '0'){
                    cnt = cnt * 10 + ss[i] - '0';
                }
            }
            string res = "";
            for(int j = 0;j < tmp.size();++j){
                if(tmp[j] >= 'A' && tmp[j] <= 'Z'){
                    res += tmp[j];j++;
                    while(j < tmp.size() && tmp[j] < 'A' || tmp[j] > 'Z'){
                        res += tmp[j];
                        ++j;
                    }
                    j--;
                }
                for(int k = 0;k < cnt;++k)
                    sss += res;
                res = "";
            }
            tmp = "";
        }
        else if(ss[i] == '{'){
            cnt = 0;
            while(ss[i] != '}'){
                i++;
                if(ss[i] <= '9' && ss[i] >= '0'){
                    cnt = cnt * 10 + ss[i] - '0';
                }
            }
            for(int j = 0;j < cnt;++j)
                sss += tmp;
            tmp = "";
        }
        else{
            tmp += ss[i];
        }
    }
    sss += tmp;
    cout << sss << endl;
    return 0;
}

L2-1 特殊的沉重球

dfs暴力搜，注意剪枝（也就是记得按体重降序排个序）

#include<bits/stdc++.h>
using namespace std;
int n,w;
int a[25],b[25];
int ans;
void dfs(int x,int num){
    if(num>=ans) return ;
    if(x>n) {
        ans=min(ans,num);return ;
    }
    for(int i=1;i<=num;i++){
        if(a[x]+b[i]<=w){
            b[i]+=a[x],dfs(x+1,num),b[i]-=a[x];
        }
    }
    b[num+1]+=a[x];
    dfs(x+1,num+1);
    b[num+1]-=a[x];
}
int main(){
    cin>>n>>w;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n,greater<int>());
    ans=n;
    dfs(1,0);
    cout<<ans;
    return 0;
}

L2-2 又见火车入栈

因为存在查询前y项记录用STL的stack肯定是不行的，只能手写一个栈，先记录进出栈的信息，然后用离线算法，对没次询问按处理信息的数量升序排序。接着模拟进出栈就可以了。

#include<bits/stdc++.h>
using namespace std;
struct node{
    int l,r;
    int id;
}a[1<<20];
int ans[1<<20];
int vis[1<<20];
int sta[1<<20],tot=1;
bool cmp(node x,node y){
    return x.l<y.l;
}
char s[15];
int main(){
   int n;scanf("%d",&n);
   for(int i=1;i<=n;i++){
    scanf("%s",s);
    if(s[0]=='i') vis[i]=1;
   }
   int q;scanf("%d",&q);
   for(int i=1;i<=q;i++){
        int x,y;scanf("%d%d",&x,&y);
        a[i]={x,y,i};
   }
   sort(a+1,a+1+q,cmp);
    int k=0,num=1;
    for(int i=1;i<=q;i++){
        while(a[i].l!=k){
            if(vis[++k]) sta[tot++]=num++;
            else tot--;
        }
        ans[a[i].id]=sta[a[i].r];
    }
    for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
    return 0;
}

L2-3 新旷野地带

n行m列，枚举k，n行、m列分别选出k个，有图片说明 ，然后组成k阶方阵，因为每行每列只能选一个，所以有图片说明 种方案，总方案就是图片说明 * 图片说明。预处理阶乘，然后根据逆元来求组合数。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f[1<<21];
const ll mod=1e9+7;
ll qpow(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1) ans=ans*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans;
}
int main(){
    int n,m,k;cin>>n>>m>>k;
    f[0]=1;
    for(int i=1;i<=1000000;i++) f[i]=f[i-1]*i%mod;
    ll ans=0;
    k=min(k,min(n,m));
    for(int i=1;i<=k;i++){
        ans+=(f[n]*qpow(f[n-i]*f[i]%mod,mod-2))%mod*(f[m]*qpow(f[m-i]*f[i]%mod,mod-2)%mod)%mod*f[i]%mod;
        ans%=mod;
    }
    cout<<ans;

    return 0;
}

L2-4 缘之空

LCA的板子题。
统计每个点的入度，入度为0的点就是根。两者是直系血缘关系说明有一个人是另一个人的祖先，两者的距离是图片说明 。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int head[N], nex[N<<1], to[N<<1], edge[N<<1], tot;
int n, m, s, f[N][30], h[N];
int TT;
int len[N];
void add(int x, int y, int z) {
    to[tot] = y;
    edge[tot] = z;
    nex[tot] = head[x];
    head[x] = tot++;
}
void dfs(int x, int fa) {
    h[x] = h[fa] + 1;
    f[x][0] = fa;
    for (int i = 1; i <= TT; i++) f[x][i] = f[f[x][i - 1]][i - 1];
    for (int i = head[x]; ~i; i = nex[i]) {
        if(to[i] != fa) {
            len[to[i]] = len[x] + edge[i];
            dfs(to[i], x);
        }
    }
}
int LCA(int x, int y) {
    if(h[x] > h[y]) swap(x, y);
    for (int i = TT; i >= 0; i--)
        if(h[f[y][i]] >= h[x]) y = f[y][i];
    if(x == y) return x;
    for (int i = TT; i >= 0; i--)
        if(f[y][i] != f[x][i])
            y = f[y][i], x = f[x][i];
    return f[x][0];
}
int d[N];
int main()
{
    int n, q; scanf("%d%d", &n, &q);
    memset(head, -1, sizeof(head));
    memset(len, 0, sizeof(len));
    for (int i = 1, u, v; i < n; i++) {
        scanf("%d %d", &u, &v);
        add(u, v, 1); add(v, u, 1);
        d[v]++;
    }
    int root = 0;
    for (int i = 1; i <= n; i++) {
        if(d[i] == 0) {
            root = i;
            break;
        }
    }
    TT = int(log(n) / log(2)) + 1;
    dfs(root, 0);
    while (q--) {
        int a, b;
        scanf("%d%d", &a, &b);
        int lca = LCA(a, b);
        int ans = len[a] + len[b] - 2 * len[LCA(a, b)];
        if(lca == a || lca == b) printf("NO\n");
        else {
            if(ans <= 4) printf("NO\n");
            else printf("YES\n");
        }
        printf("%d\n", ans);
    }
}