头像

mozheng

大连海事大学




离线:18小时前



mozheng
1个月前

这咋做呀,通过的同学可以写下题解吗?




mozheng
2个月前

题目链接: https://www.jisuanke.com/course/6497/427111 (收费题目可能打不开)

题目描述

给你n个数的序列,让你求一个区间[l,r],使得区间元素的异或值最大。(n最大1e5)

输入

3
1 2 3

输出

3

思路

1.首先要知道,异或运算也是有类似前缀和的性质的。
2.所以这道题就转换为,给你n个数字,以及0,让你求其中两个数使其异或的值是最大的。
3.对于这个问题,使用字典树,把数字的二进制当成字符串,从高位到低位插入树中。把这n个数字和0都插入完之后,就枚举每个数字,在字典树中搜索一下,从高位尽量不一样的搜索,这样异或出来的结果是最大的,计算一下最大的异或值,更新答案,时间复杂度是O(32n).

代码(不用转字符串的,懒得改了)

#include<bits/stdc++.h>
using namespace std;
const int N=100000+5;
int n,a[N];
int tr[32*N][2],idx;

void ins(string s)
{
    int p=0;
    for(int i=0;i<s.size();i++)
    {
        int u=0;
        if(s[i]=='1') u=1;
        if(tr[p][u]==0) tr[p][u]=++idx;
        p=tr[p][u];
    }
}

string get(int x)
{
    string s;
        for(int j=0;j<=30;j++)
            if(x>>j&1) s+='1';
            else s+='0';
    reverse(s.begin(),s.end());
    return s;
}

int f(string s)
{
    int res=0,p=0;
    for(int i=0;i<s.size();i++)
    {
        int u=0;
        if(s[i]=='1') u=1;
        if(tr[p][u^1]==0) p=tr[p][u];
        else p=tr[p][u^1],res+=1<<(30-i);
    }

    return res;
}

int main()
{
    cin>>n;
    ins(string(31,'0'));
    int x=0;
    for(int i=1;i<=n;i++)
    {
        int y;cin>>y;
        x^=y;
        a[i]=x;
        string s=get(x);
        ins(s);
    }
    int ans=f(string(31,'0'));
    for(int i=1;i<=n;i++) 
    {
        ans=max(ans,f(get(a[i])));
    }
    cout<<ans<<endl;
    return 0;
}



mozheng
3个月前

题目:hdu2049
做法就是先从n本书中挑排错的m个,然后其他没有排错的都在原来的位置上,所以方案为1,然后求下这m本书的错排Dm就行了。
错排数的递推公式:Dn=(n-1)*(Dn-1+Dn-2),其中D1=0,D2=1.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n,f[21],fac[21],m,T;
int main()
{
    f[1]=0,f[2]=1;
    fac[0]=fac[1]=1,fac[2]=2;
    for(int i=3;i<=20;i++) 
    {
        f[i]=(i-1)*(f[i-1]+f[i-2]);
        fac[i]=fac[i-1]*i;
    }
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        ll x=fac[n]/fac[m]/fac[n-m];
        cout<<f[m]*x<<endl;
    }

    return 0;
}



mozheng
4个月前

先双指针,再RMQ,再二分,具体看注释

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,M=20;

int n,m,f[N][M],a[N],v[N],la[N]; //a数组为输入数组,f为RMQ数组
//v[i]为以下标i的元素为结尾的最长完美序列长度,la[i]是该序列的起始下标

void init() //RMQ的初始化
{
    for(int j=0;j<M;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
        {
            if(!j) f[i][j]=v[i];
            else f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
}

int get(int l,int r) //RMQ的查询,返回[l,r]之间的最大值
{
    int len=r-l+1;
    int k=log(len)/log(2);
    return max(f[l][k],f[r-(1<<k)+1][k]);
}

unordered_map<int,int> mp;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    //以下是双指针做法,把v[i]和la[i]求出来
    for(int i=1,j=1;i<=n;i++)
    {
        mp[a[i]]++;
        while(j<=i&&mp[a[i]]>1) mp[a[j++]]--;
        v[i]=i-j+1,la[i]=j;
    }

    init();
    while(m--)
    {
        int a,b,res=INT_MIN;
        scanf("%d%d",&a,&b);
        a++,b++;
        //二分,目的是把从左到右第一个起始位置没有超出a的完美序列找出来
        int l=a,r=b;
        while(l<r)
        {
            int mid=l+r>>1;
            if(la[mid]>=a) r=mid;
            else l=mid+1;
        }

        if(la[l]>=a)
        {
            printf("%d\n",max(l-a,get(l,b)));
        }else printf("%d\n",b-a+1);
    }

    return 0;
}



mozheng
4个月前

这题有两问,第一问用状压DP的思想解决,第二问用统计最短路条数的方法解决。毕竟dp是一种特殊的最短路问题嘛,具体看注释吧,写得还算详细

#include<bits/stdc++.h>
using namespace std;

const int N=15,M=1<<13;

int f[N][N][M]; //f[i][j][a]为走过的点的状态为a,现在停留在j,并且上次停留在i的所有方案的最大价值
int num[N][N][M]; //num[i][j][a]为走过的点的状态为a,现在停留在j,并且上次停留在i的所有方案中能达到最大价值的方案数目
int n,m,T,val[N]; //val[i]为的点权
bool g[N][N]; //g[i][j]为ture说明i到j有边
int tmp[N][N][N]; //tmp[i][j][k]为当前在j点,上次在i点,然后现在走到了k点,所增加的价值

int main()
{
    cin>>T;
    while(T--)
    {
        //清空数据,读入数据
        memset(num,0,sizeof num);
        memset(f,-0x3f,sizeof f);
        memset(g,0,sizeof g);
        memset(tmp,0,sizeof tmp);
        cin>>n>>m;
        for(int i=0;i<n;i++) cin>>val[i];
        while(m--)
        {
            int x,y;cin>>x>>y;
            x--,y--;
            g[x][y]=g[y][x]=true;
        }

        //初始化两个dp数组,因为初始状态只有当前的起点没有上一点,我这里人为设定把上一点等同于当前点了
        for(int i=0;i<n;i++)
            f[i][i][1<<i]=val[i],num[i][i][1<<i]=1;

        //预处理tmp,加速运算,不过不预处理应该也能过
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                for(int k=0;k<n;k++)
                {
                    int sum=val[k]+val[k]*val[j];
                    if(g[i][j]&&g[j][k]&&g[k][i]) sum+=val[i]*val[k]*val[j]; //若i,j,k三者能成环,则加上
                    tmp[i][j][k]=sum;
                }

        //DP过程,转移的方式是“我为人人”
        for(int a=0;a<(1<<n)-1;a++)
            for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                {
                    int v=f[i][j][a],cnt=num[i][j][a];

                    if(v<-100000000) continue; //非法状态,不必转移
                    for(int k=0;k<n;k++)
                    {
                        if(a>>k&1||!g[j][k]) continue; //如果已经走过了k或者j和k没有边,则continue

                        if(f[j][k][a|(1<<k)]<tmp[i][j][k]+v) //有更好的,则更新
                        {
                            f[j][k][a|(1<<k)]=tmp[i][j][k]+v;
                            num[j][k][a|(1<<k)]=cnt;
                        }else if(f[j][k][a|(1<<k)]==tmp[i][j][k]+v) //和之前的价值相等,则更新方案数目
                        {
                            num[j][k][a|(1<<k)]+=cnt;
                        }
                    }
                }

        //处理输出,别忘了sum得除2
        int ans=-0x3f3f3f3f,sum=0;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                {
                    if(ans<f[i][j][(1<<n)-1])
                    {
                        ans=f[i][j][(1<<n)-1];
                        sum=num[i][j][(1<<n)-1];
                    }else if(ans==f[i][j][(1<<n)-1]) sum+=num[i][j][(1<<n)-1];
                }
        if(ans<0) puts("0 0");
        else cout<<ans<<' '<<sum/2<<endl;
    }
    return 0;
}



mozheng
4个月前

三进制状态压模板题,具体思路请看注释吧

#include<bits/stdc++.h>
using namespace  std;
const int mo=1e6;

int c[100000],n,m,k; //c[i]=3的i次方
vector<int> v,g[310];//v中是所有的合法状态,g[i]中的是能和状态i相邻的状态
int state=0; //state为题目中所给的第k行的状态
int f[10005][300]; //f[i][j]为只涂了前i行,最后一行状态为j,并且第一行要能和state相邻的方案数目

int get(int x,int u) //此函数相当于二进制状压的x>>u&1
{
    return x%c[u+1]/c[u];
}

bool chk(int x) //判断行内状态x是否合法
{
    for(int i=1;i<m;i++)
    {
        if(get(x,i)==get(x,i-1)) return false;
    }
    return true;
}

bool chk2(int x,int y) //判断状态x和状态y是否可以挨着
{
    for(int i=0;i<m;i++)
        if(get(x,i)==get(y,i)) return false;
    return true;
}

int main()
{
    cin>>n>>m>>k;
    c[0]=1;
    for(int i=1;i<=m;i++) c[i]=3*c[i-1];
    for(int i=0;i<m;i++)
    {
        int x;cin>>x;
        state=state*3+x-1;
    }
    for(int i=0;i<c[m];i++)
        if(chk(i)) v.push_back(i);
    for(auto a:v)   
        for(auto b:v) if(chk2(a,b)) g[a].push_back(b);

    int x=max(k-1,n-k),y=min(k-1,n-k);

    f[0][state]=1;
    for(int i=1;i<=x;i++)
        for(auto a:v)
        {
            {
                for(auto b:g[a]) 
                    (f[i][a]+=f[i-1][b])%=mo;
            }
        }
    int ans1=0,ans2=0; //ans1为第k行上方的方案数,ans2是第k行下方的方案数目
    for(auto i:v) (ans1+=f[x][i])%=mo,(ans2+=f[y][i])%=mo;

    cout<<(long long )ans1*ans2%mo<<endl;
    return 0;
}



mozheng
4个月前

估算了一下,发现int128也是ok的

#pragma GCC optimize(2)
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <climits>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
typedef __int128 lll;
const int N=85;

int n,m,g[N][N];
lll f[N][N];

lll get(int a[],int n)
{
    for(int len=1;len<=n;len++)
        for(int i=1;i+len-1<=n;i++)
        {
            int j=i+len-1;
            lll k=n-len+1,ba=1;
            k=ba<<k;
            if(len==1) f[i][j]=k*a[i];
            else
            {
                f[i][j]=k*a[i]+f[i+1][j];
                f[i][j]=max(f[i][j],f[i][j-1]+k*a[j]);
            }
        }
    return f[1][n];
}

void print(lll x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) 
        print(x/10);
    putchar('0'+x%10);
}

int main()
{   
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>g[i][j];
    lll ans=0;
    for(int i=1;i<=n;i++)
    {
        ans+=get(g[i],m);
    }
    print(ans);
    return 0;
}



mozheng
4个月前

这道题如果不让输出方案的话,和普通的区间DP差不多。输出方案的话,我是直接把这颗树重建了,然后bfs一下输出的

#pragma GCC optimize(2)
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <climits>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;

int n,a[310];
int f[310][310];
int path[310][310];

int l[310],r[310];

int dfs(int i,int j)
{
    if(i>=j) return -1;

    int root=path[i][j];

    l[root]=dfs(i,root);
    r[root]=dfs(root+1,j);
    return root;
}

void bfs(int h){
    queue<int> q;
    q.push(h);
    vector<int> v;
    while(q.size())
    {
        int x=q.front();q.pop();
        v.push_back(x);

        if(~l[x]) q.push(l[x]);
        if(~r[x]) q.push(r[x]);
    }
    for(auto i:v) cout<<i<<' ';
}

int main()
{
    memset(f,-0x3f,sizeof f);
    memset(path,-1,sizeof path);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];

    for(int len=1;len<=n;len++)
        for(int i=1;i+len-1<=n;i++)
        {
            int j=i+len-1;
            if(len==1) f[i][j]=0;
            else
            {
                for(int k=i;k<j;k++)
                {
                    int x=f[i][k];
                    int y=f[k+1][j];
                    if(f[i][j]<(a[i]+a[j])*a[k]+x+y)
                    {
                        f[i][j]=(a[i]+a[j])*a[k]+x+y;
                        path[i][j]=k;
                    }
                }
            }
        }
    cout<<f[1][n]<<endl;
    int h=dfs(1,n);
    bfs(h);

    return 0;
}



mozheng
4个月前

对于无向图的最大流:
建边的时候,反向边的容量和正向边是一样的,而不是0;
对于无向图的最小费用流:
建边的时候,一条无向边对应4条边:
①正向边,容量为f,费用为c
②反向边,容量为0,费用为-c
③反向边,容量为f,费用为c
④正向边,容量为0,费用为-c
说白了,就是把无向图看作是有向图,然后像有向图那样一条有向边建两条边,也就变成了一条无向边建四条边
注意:开数组的时候一定要注意开2倍的M和4倍的M,还有spfa中的队列要用循坏队列。

无向图的最大流(hdu.4280)

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int N=100005,M=200005;

int n,m,Te,S,T;
int h[N],e[M],ne[M],flow[M],idx;

void add(int a,int b,int f)
{
    flow[idx]=f,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dist[N];
int q[N],hh,tt;
bool bfs()
{
    memset(dist,0x3f,sizeof dist);
    dist[S]=0;
    hh=0,tt=-1;
    q[++tt]=S;
    while(hh<=tt)
    {
        int x=q[hh++];
        for(int i=h[x];~i;i=ne[i])
        {
            int j=e[i];
            if(flow[i]&&dist[j]>dist[x]+1)
            {
                dist[j]=dist[x]+1;
                q[++tt]=j;
            }
        }
    }
    return dist[T]<0x3f3f3f3f;
}

int dfs(int u,int fl)
{
    if(u==T) return fl;
    int res=0;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(dist[j]==dist[u]+1&&flow[i])
        {
            int x=dfs(j,min(fl,flow[i]));
            fl-=x,res+=x,flow[i]-=x,flow[i^1]+=x;
            if(!fl) break;
        }
    }
    if(!res) dist[u]=1<<30;
    return res;
}

int maxflow()
{
    int res=0;
    while(bfs()) 
    {
        res+=dfs(S,INT_MAX);
    }
    return res;
}

int main()
{
    cin>>Te;
    while(Te--)
    {
        cin>>n>>m;
        memset(h,-1,sizeof h),idx=0;
        int minx=INT_MAX,maxx=INT_MIN;
        for(int i=1;i<=n;i++)    
        {
            int x,y;
            scanf("%d%d",&x,&y);
            if(x<minx) S=i,minx=x;
            if(x>maxx) T=i,maxx=x;
        }
        while(m--)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            add(x,y,z),add(y,x,z);
        }
        cout<<maxflow()<<endl;
    }

    return 0;
}

无向图的费用流(poj2135)

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <climits>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;

const int N=1010,M=4e4+50;

int n,m,S,T;
int h[N],e[M],ne[M],flow[M],co[M],idx;

void add(int a,int b,int f,int c)
{
    flow[idx]=f,co[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dist[N],pre[N];
bool st[N];
bool spfa()
{
    memset(dist,0x3f,sizeof dist);
    memset(pre,-1,sizeof pre);
    memset(st,0,sizeof st);
    dist[S]=0;
    queue<int>q;
    q.push(S);
    st[S]=true;
    while(q.size())
    {
        int x=q.front();q.pop();
        st[x]=false;
        for(int i=h[x];~i;i=ne[i])
        {
            int j=e[i];
            if(flow[i]&&dist[j]>dist[x]+co[i])
            {
                dist[j]=dist[x]+co[i];
                pre[j]=i;
                if(!st[j]) st[j]=true,q.push(j);
            }
        }
    }
    return dist[T]<0x3f3f3f3f;
}

void maxflow(int &ans)
{
    while(spfa())
    {
        int cur=pre[T];
        while(cur!=-1)
            flow[cur]-=1,flow[cur^1]+=1,cur=pre[e[cur^1]];
        ans+=dist[T];
    }
}

int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;S=0,T=n;
    while(m--)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,1,z),add(y,x,0,-z);
        add(y,x,1,z),add(x,y,0,-z);
    }
    add(S,1,2,0);add(1,S,0,0);
    int ans=0;
    maxflow(ans);
    cout<<ans<<endl;
    return 0;
}



mozheng
4个月前

1.一定存在一颗次小生成树(不论严格不严格)和最小生成树只差了一条边(这个定理用来求次小生成树的,而且要注意只是存在,不是所有的)
2.对于所有的最小生成树,它们的不同边权的边的个数是相同的(这个定理用来求最小生成树的个数)