头像

李商隐

心中有进阶 万物皆指南 正在刷《算法竞赛进阶指南》这本书 努力成为一名ACMer


访客:152

离线:21小时前



闫式dp分析法思维导图

前几天看了y总的闫式dp分析法视频,激动不已,于是根据视频写了一张思维导图,仅是一些y总话语转述而已。

当时发了一条动态,因为忘记上传原图了,有很多小伙伴想看原图,所以分享一下~~,有需要的小伙伴就拿去吧,还是有很多不足,忘批评改正。

1459A404DAE855121300FB83C926B56E.jpg



活动打卡代码 AcWing 95. 费解的开关

#include <iostream>
using namespace std;

int n;
int order[20];
bool chosen[20];

void calc(int k)
{
    if(k==n+1)
    {
        for(int i=1;i<=n;i++)
        {
            printf("%d ",order[i]);
        }
        puts("");
        return ;
    }
    for(int i=1;i<=n;i++)
    {
        if(chosen[i])
        continue;
        order[k]=i;
        chosen[i]=1;
        calc(k+1);
        chosen[i]=0;
        order[k]=0;
    }

}

int main()
{

    cin>>n;
    calc(1);

}


活动打卡代码 AcWing 101. 最高的牛

#include <iostream>
#include <map>
using namespace std;

map<pair<int ,int>,bool> existed;
int c[10010],d[10010];

int main()
{
    int n,p,h,m;
    cin>>n>>p>>h>>m;
    for(int i=1;i<=n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if(a>b)
            swap(a,b);
        if(existed[make_pair(a,b)])
            continue;
        d[a+1]--;
        d[b]++;
        existed[make_pair(a,b)]=true;
    }
    for(int i=1;i<=n;i++)
    {
        c[i]=c[i-1]+d[i];
        printf("%d",h+c[i]);
        if(i<n)
        printf("\n");
    }

    cout<<endl;

}



题目描述

曾经有一个国王,他有 N 个儿子。

王国中有着 N 个漂亮的姑娘,每个王子也都有自己喜欢的对象。

每个王子喜欢的对象可能不止一个。

因为王子们都到了结婚的年纪,所以国王想让王子们娶了这 N 个姑娘,当然每个姑娘只能嫁给一名王子。

国王请巫师为他做一个统计,他想看看儿子们都有哪些喜欢的姑娘。

就这样,巫师制作了一个清单,上面具体列出了每一个王子喜欢哪些姑娘,并给出了一套初步的配对方案。

国王看了看巫师给他列出的清单,说道:“你总结的不错,但是我并不完全满意。我希望你列出每个王子可以婚配的女子清单,可以满足每个王子对应的清单上都是他喜欢的姑娘,并且任何一个王子从自己的清单上任意选择一名姑娘作为自己的结婚对象之后,剩下的王子仍然能够从自己的清单中选择的到自己喜欢的对象,使得所有的王子都能完成和自己喜欢的姑娘配对。”

请你帮助巫师列出国王满意的清单。

输入格式
第一行包含整数 N。

接下来 N 行,每行包含多个整数,描述了一个王子喜欢的姑娘的清单,每行的第一个整数 K ,表示王子喜欢的姑娘的数量,接下来的 K 个整数,为这 K 个姑娘的编号。

最后一行,包含 N 个整数,表示初步的配对方案,第 i 个整数表示与第 i 个王子进行配对的姑娘编号。

输出格式
输出共 N 行。

每行包含多个整数,描述一个王子可以婚配的女子清单,第一个整数 L ,表示王子可以婚配的姑娘的数量,接下来 L 个整数,为这 L 个姑娘的编号(请按升序排列)。

数据范围
1≤N≤2000,
所有 K 加起来的和不超过200000。

样例

输入样例:
4
2 1 2
2 1 2
2 2 3
2 3 4
1 2 3 4
输出样例:
2 1 2
2 1 2
1 3
1 4

C++ 代码

#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 4e3 + 6;
int n, b[N], c[N], cnt, p[N][N];
vector<int> a[N], e[N], ans[N];
int dfn[N], low[N], num;
int st[N], top, ins[N];

void tarjan(int x) 
{
    dfn[x] = low[x] = ++num;
    st[++top] = x;
    ins[x] = 1;
    for (unsigned int i = 0; i < e[x].size(); i++) {
        int y = e[x][i];
        if (!dfn[y]) {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        } else if (ins[y])
            low[x] = min(low[x], dfn[y]);
    }
    if (dfn[x] == low[x]) {
        ++cnt;
        int y;
        do {
            y = st[top--];
            ins[y] = 0;
            c[y] = cnt;
        } while (x != y);
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int k;
        scanf("%d", &k);
        while (k--) {
            int x;
            scanf("%d", &x);
            a[i].push_back(x);
            p[i][x] = 1;
        }
    }
    for (int i = 1; i <= n; i++)  scanf("%d", &b[i]);
    for (int x = 1; x <= n; x++)
        for (unsigned int i = 0; i < a[x].size(); i++) 
        {
            int y = a[x][i];
            if (y == b[x]) e[y+n].push_back(x);
            else e[x].push_back(y + n);
        }
    for (int i = 1; i <= n << 1; i++)
        if (!dfn[i]) tarjan(i);
    for (int i = 1; i <= n; i++) 
    {
        for (int j = 1; j <= n; j++)
            if (b[i] == j || (p[i][j] && c[i] == c[j+n]))
                ans[i].push_back(j);
        printf("%d", (int)ans[i].size());
        for (unsigned int j = 0; j < ans[i].size(); j++)
            printf(" %d", ans[i][j]);
        puts("");
    }
    return 0;
}

作者:李商隐
链接:https://www.acwing.com/activity/content/code/content/368143/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。



活动打卡代码 AcWing 411. 国王的任务


#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 4e3 + 6;
int n, b[N], c[N], cnt, p[N][N];
vector<int> a[N], e[N], ans[N];
int dfn[N], low[N], num;
int st[N], top, ins[N];

void tarjan(int x) 
{
    dfn[x] = low[x] = ++num;
    st[++top] = x;
    ins[x] = 1;
    for (unsigned int i = 0; i < e[x].size(); i++) {
        int y = e[x][i];
        if (!dfn[y]) {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        } else if (ins[y])
            low[x] = min(low[x], dfn[y]);
    }
    if (dfn[x] == low[x]) {
        ++cnt;
        int y;
        do {
            y = st[top--];
            ins[y] = 0;
            c[y] = cnt;
        } while (x != y);
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int k;
        scanf("%d", &k);
        while (k--) {
            int x;
            scanf("%d", &x);
            a[i].push_back(x);
            p[i][x] = 1;
        }
    }
    for (int i = 1; i <= n; i++)  scanf("%d", &b[i]);
    for (int x = 1; x <= n; x++)
        for (unsigned int i = 0; i < a[x].size(); i++) 
        {
            int y = a[x][i];
            if (y == b[x]) e[y+n].push_back(x);
            else e[x].push_back(y + n);
        }
    for (int i = 1; i <= n << 1; i++)
        if (!dfn[i]) tarjan(i);
    for (int i = 1; i <= n; i++) 
    {
        for (int j = 1; j <= n; j++)
            if (b[i] == j || (p[i][j] && c[i] == c[j+n]))
                ans[i].push_back(j);
        printf("%d", (int)ans[i].size());
        for (unsigned int j = 0; j < ans[i].size(); j++)
            printf(" %d", ans[i][j]);
        puts("");
    }
    return 0;
}



#include <iostream>
#include <vector>

using namespace std;

int n;

vector <int >chosen;
void calc(int x)
{
    if(x==n+1)
    {
        for(int i=0;i<chosen.size();i++)
        {
            printf("%d ",chosen[i]);
        }
        puts("");
        return ;
    }

    calc(x+1);

    chosen.push_back(x);
    calc(x+1);
    chosen.pop_back();

}


int main()
{

    cin>>n;

    calc(1);

}



C++ 代码

#include <iostream>
using namespace std;

int n,m;
pair<string,int> a[100005];
int calc(int bit,int now)
{
    for(int i=1;i<=n;i++)
    {
        int x=a[i].second>>bit&1;
        if(a[i].first=="AND")
        now&=x;
        else if(a[i].first=="OR")
        now|=x;
        else
        now^=x;

    }
    return now;

}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        char str[5];
        int x;
        scanf("%s%d",str,&x);
        a[i]=make_pair(str,x);

    }
    int val=0,ans=0;
    for(int bit=29;bit>=0;bit--)
    {
        int res0=calc(bit,0);
        int res1=calc(bit,1);
        if(val+(1<<bit)<=m&&res0<res1)
            val+=1<<bit,ans+=res1<<bit;
        else
            ans+=res0<<bit;
    }
    cout<<ans<<endl;

}




#include <iostream>
using namespace std;

int n,m;
pair<string,int> a[100005];
int calc(int bit,int now)
{
    for(int i=1;i<=n;i++)
    {
        int x=a[i].second>>bit&1;
        if(a[i].first=="AND")
        now&=x;
        else if(a[i].first=="OR")
        now|=x;
        else
        now^=x;

    }
    return now;

}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        char str[5];
        int x;
        scanf("%s%d",str,&x);
        a[i]=make_pair(str,x);

    }
    int val=0,ans=0;
    for(int bit=29;bit>=0;bit--)
    {
        int res0=calc(bit,0);
        int res1=calc(bit,1);
        if(val+(1<<bit)<=m&&res0<res1)
            val+=1<<bit,ans+=res1<<bit;
        else
            ans+=res0<<bit;
    }
    cout<<ans<<endl;

}


活动打卡代码 AcWing 91. 最短Hamilton路径

#include <iostream>
#include <cstring>
using namespace std;

int f[1<<20][20];
int weight[20][20];

int hamilton(int n,int weight[20][20])
{
    memset(f,0x3f,sizeof(f));
    f[1][0]=0;
    for(int i=1;i<1<<n;i++)
        for(int j=0;j<n;j++)
        if(i>>j&1)
            for(int k=0;k<n;k++)
            if((i^1<<j)>>k&1)
                f[i][j]=min(f[i][j],f[i^1<<j][k]+weight[k][j]);
    return f[(1<<n)-1][n-1];
}

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>weight[i][j];
    printf("%d",hamilton(n,weight));



}


活动打卡代码 AcWing 90. 64位整数乘法

//方法一:
#include <iostream>
#include <stdio.h>
using namespace std;

typedef long long LL;

LL mul(LL a,LL b,LL p)
{
    LL ans=0;
    for( ; b ; b >>=1)
    {
        if(b&1) ans=(ans+a)%p;
        a=a*2%p;
    }

    return ans;

}

int main()
{
    LL a,b,p;
    cin>>a>>b>>p;
    printf("%lld",mul(a,b,p));
    return 0;
}

//方法二:
#include <iostream>
#include <stdio.h>
using namespace std;

typedef long long LL;

LL mul(LL a,LL b,LL p)
{
    a%=p;
    b%=p;

    LL c=(long double)a*b/p;
    LL ans=a*b-c*p;
    if(ans<0) ans+=p;
    else if(ans>=p) ans-=p;

    return ans;
}

int main()
{
    LL a,b,p;
    cin>>a>>b>>p;
    printf("%lld",mul(a,b,p));
    return 0;
}