A. Local Extrema

求一个序列的局部极值的数量

For循环判断+计数

B. Buggy Robot

给定一个机器人序列,问最终机器人停在原点,最多可以执行多少步骤。

C. K-Dominant Character

求能保证某字符串的每个长度为的子串中,都包含至少一个相同字母的最小是多少。

二分长度 + 线性判断

D. Almost Identity Permutations

问长度为的排列,至多有个位置保证的方案数。

枚举 + 错排列

E. Maximum Subsequence

问长度为的序列,取出若干个数字求和模的最大值。

Meet in the middle + 二分判断取余点

#include <cstdio>
#include <algorithm>
using namespace std;

const int Maxn=1e6;

int num[2][Maxn+5],tot[2];
int val[Maxn+5],n,m;

void dfs(int now,int lim,int sum,int idx){
    if (now>lim){
        num[idx][++tot[idx]]=sum;
    }else{
        dfs(now+1,lim,sum,idx);
        dfs(now+1,lim,(sum+val[now])%m,idx);
    }
}

int main(){
    //freopen("in.txt","r",stdin);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d",&val[i]);
    for (int i=1;i<=n;i++) val[i]%=m;

    tot[0]=tot[1]=0;
    dfs(1,n/2,0,0); dfs(n/2+1,n,0,1);

    int ans=0;
    for (int i=0;i<2;i++) sort(num[i]+1,num[i]+tot[i]+1);
    for (int i=0;i<2;i++) for (int j=1;j<=tot[i];j++) ans=max(ans,num[i][j]);
    for (int i=1;i<=tot[0];i++){
        int lim=lower_bound(num[1]+1,num[1]+tot[1]+1,m-num[0][i])-num[1]-1;
        if (lim>0) ans=max(ans,(num[0][i]+num[1][lim])%m);
        ans=max(ans,(num[0][i]+num[1][tot[1]])%m);
    }
    printf("%d\n",ans);

    return 0;
}

F. Connecting Vertices

问一个圆形顺时针包含个点的图,在给定的边集中选择条连接,保证边不交叉的方案数。

区间DP,状态表示:dpEdge[L,R],dpLink[L,R]
dpEdge[L,R]:区间[L,R]最外面使用一条L连接R的边的方案数
dpLink[L,R]:区间[L,R]由若干dpEdge拼成的方案数

#include <iostream>
#include <algorithm>
#define LL long long
using namespace std;
#define MOD 1000000007

const int Maxn=500+50;

int N;
int A[Maxn][Maxn];

LL dpEdge[Maxn][Maxn];
LL dpLink[Maxn][Maxn];

int main(){
    freopen("in.txt","r",stdin);
    scanf("%d",&N);
    for(int i=0;i<N;i++) for(int j=0;j<N;j++) scanf("%d",&A[i][j]);
    for(int i=0;i<N;i++){
        dpEdge[i][(i+1)%N]=dpLink[i][(i+1)%N]=A[i][(i+1)%N];
        dpLink[i][i]=1;
    }
    for(int d=2;d<N;d++){
        for(int i=0;i<N;i++){
            int j=(i+d)%N;
            if(A[i][j]){
                for(int k=i;k!=j;k=(k+1)%N)
                    dpEdge[i][j]=(dpEdge[i][j]+dpLink[i][k]*dpLink[(k+1)%N][j])%MOD;
            }
            for(int k=i;k!=j;k=(k+1)%N) dpLink[i][j]=(dpLink[i][j]+dpEdge[k][j]*dpLink[i][k])%MOD;
        }
    }
    printf("%lld\n",dpLink[1][0]);
    return 0;
}

G. Xor-MST

求一个个点的树的最小生成树,边权为边两端点点权异或。

字典树查询最小异或值 + Prim最小生成树

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <queue>
#include <cstring>
#define LL long long
#define PLI pair<LL,int>
#define mp(x,y) make_pair(x,y)
using namespace std;

const int Maxn=200000;

int n;
LL val[Maxn+5];
bool vis[Maxn+5];

struct BTree{
    int ch[2];
    int siz;
}tree[Maxn*20];
int Root,nume;

inline int initNode(int x){
    tree[x].siz=0;
    tree[x].ch[0]=tree[x].ch[1]=0;
    return x;
}

void modify(int &x,int now,LL num,int val){
    if (!x) x=initNode(++nume);
    tree[x].siz+=val;
    if (now>=0) modify(tree[x].ch[(num>>now)&1LL],now-1,num,val);
}

LL query(int x,int now,LL num){
    if (!x) return 0;
    if (now<0) return 0;
    int l=(num>>now)&1,r=((num>>now)&1)^1;
    if (tree[x].ch[l] && tree[tree[x].ch[l]].siz>0){
        return query(tree[x].ch[l],now-1,num);
    }else return 0LL+(1LL<<now)+query(tree[x].ch[r],now-1,num);
}

priority_queue<PLI> que;

inline void update(int x){
    LL mx=query(Root,30,val[x]);
    int idx=lower_bound(val+1,val+n+1,mx^val[x])-val;
    que.push(mp(-mx,idx));
    //printf("InQue %d %d %lld\n",x,idx,mx);
}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%lld",&val[i]);
    sort(val+1,val+n+1); n=unique(val+1,val+n+1)-val-1;
    memset(vis,false,sizeof(vis)); vis[1]=true;
    while(!que.empty()) que.pop();

    nume=Root=0; initNode(0);
    for (int i=2;i<=n;i++) modify(Root,30,val[i],1);
    update(1);

    LL ans=0;
    for (int rt=2;rt<=n;rt++){
        while(true){
            LL mx=que.top().first; int idx=que.top().second; que.pop();
            int src=lower_bound(val+1,val+n+1,(-mx)^val[idx])-val;
            if (vis[idx]){
                //printf("Die %d %d\n",src,idx);
                update(src);
            }else{
                ans-=mx; vis[idx]=true;
                modify(Root,30,val[idx],-1);
                ////printf("ADD %d %d\n",src,idx);
                update(src); update(idx);
                break;
            }
        }
    }
    printf("%lld\n",ans);

    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注