头像

Accepting

太原理工大学




在线 


活动打卡代码 AcWing 2816. 判断子序列

#include<iostream>

using namespace std;

const int N=1e5+10;

int a[N],b[N];

int n,m;

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    for(int i=0;i<m;i++) scanf("%d",&b[i]);
    int i,j;
    for(i=0,j=0;i<n;i++,j++)
    {
        if(j>=m) break;
        while(b[j]!=a[i] && j<m) j++;
    }
    if(i==n) puts("Yes");
    else puts("No");
    return 0;
}



鄙人不才,此中鄙陋甚多,望海涵!!!

首先简单分析一下题目:给出至多4个每个面都有颜色的正方体,我们可以任意翻转这些正方体且不消耗代价,但有的时候并不是翻转就能让这4个正方体完全一样(same指每个正方体的面颜色相同),我们还可以通过消耗代价的涂色来解决问题(重新涂色一个面消耗一代价),问最终最少消耗多少代价可以实现same!
/-------------------------------------------------------------------------------------------------------------------------------------------------/

看到这个题目我们的第一想法肯定是能旋转解决的肯定不会通过重涂来解决!当然这样的想法肯定没错,接下来我们就要想怎么让他实现旋转呢?

一·规定正方行摆放!

一共四个正方体,并不多,从某种意义上讲我们可以试试暴力枚举所有旋转的情况,接下来的关键就是何不重不漏不乱(注:不乱是非必要条件,但一乱很难做对)的枚举每一种情况,这里刘佬的做法非常精妙,我们将正方体的摆放分为2步!
1.首先是确定顶部的那个面是几(这里以及下面我们的面都定位0,1,2,3,4,5号面)
2.再确定前面的面的编号这样一共可以分为6(顶部那个面的情况)*4(前面的面情况)=24种情况!

二·得到所有旋转的情况!!!(极其重要的一步)

题目给出我们的6个颜色都是对应着的标准正方体的颜色!
即:前 右 顶 底 左 后(附图)
我们再想对于给定正方体我们可以用哪几个精简的操作就能实现所有的情况枚举:有了前面我们正方体摆放的规定,我们应该不难理解分为2步的操作,即左转和上转(附图),所有的操作都可以由这2步组合而成:下面附上从标准变为其他状态的6种操作组合:
* 0在顶面:上翻1,左0~3
* 1在顶面:左1,上1,左0~3
* 2在顶面:左0~3
* 3在顶面:上2,左0~3
* 4在顶面:左3,上1,左0~3
* 5在顶面:左2,上1,左0~3
因此我们只要实现左操作和上操作即可!
附上图解析与数表代码!
无标题.png

数表代码

#include<iostream>
#include<cstring>
#include<vector>

using namespace std;

int lef[6]={4,0,2,3,5,1};
int up[6]={2,1,5,0,4,3};

//将p进行t旋转
//这里的指针实现了引用的功能直接对原地址下的p进行修改(即实现转)
void rot(int* t,int* p)
{
    int q[6];//q为临时数组,用于存储之前的0,1,2,3,4,5这6个面对应所在的面
    memcpy(q,p,sizeof q);
    for(int i=0;i<6;i++) p[i]=t[q[i]];
}

void enum_order()
{
    int p0[6]={0,1,2,3,4,5};
    printf("int dice[24][6] = {\n");
    for(int i=0;i<6;i++)
    {
        int p[6];
        memcpy(p,p0,sizeof p0);
        //枚举6种情况
        //0在顶面:上翻1,左0~3
        if(i==0) rot(up,p);
        //1在顶面:左1,上1,左0~3
        else if(i==1) {rot(lef,p); rot(up,p);}
        //2在顶面:左0~3

        //3在顶面:上2,左0~3
        else if(i==3) {rot(up,p); rot(up,p);}
        //4在顶面:左3,上1,左0~3
        else if(i==4) {rot(lef,p);rot(lef,p);rot(lef,p); rot(up,p);}
        //5在顶面:左2,上1,左0~3
        else if(i==5) {rot(lef,p);;rot(lef,p); rot(up,p);}
        //枚举所有情况下的左0~3
        for(int j=0;j<4;j++)
        {
            printf("{%d, %d, %d, %d, %d, %d}, \n",p[0],p[1],p[2],p[3],p[4],p[5]);
            rot(lef,p);
        }
    }
    printf("};\n");
}

int main()
{
    enum_order();
    return 0;
}

三.找到一种合适的枚举方法来处理好旋转与重涂的结合!

这里我们让第一个正方体作为标准不动,枚举其余正方体的旋转来不断更新重涂的次数,以达到尽可能的少!(O(24^3)程序可行)下附上代码,我个人认为刘佬处理此题输入的方式太精美了,建议反复阅读!

最终代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

const int N=4;

int n,dice[N][6],ans;//dice用来存储颜色编号,后续再详细介绍
int r[N],color[N][6];//r表示每一个正方体的旋转方式
vector<string> names;//color表示每个正方体每个面对应的颜色

int ID(string name)//每一个ID对应着每一种颜色
{
    int n=names.size();
    for(int i=0;i<n;i++)    
        if(names[i]==name) return i;
    names.push_back(name);
    return n;
}

int dice24[24][6] = {{2, 1, 5, 0, 4, 3}, {2, 0, 1, 4, 5, 3}, 
{2, 4, 0, 5, 1, 3}, {2, 5, 4, 1, 0, 3}, {4, 2, 5, 0, 3, 1}, 
{5, 2, 1, 4, 3, 0}, {1, 2, 0, 5, 3, 4}, {0, 2, 4, 1, 3, 5}, 
{0, 1, 2, 3, 4, 5}, {4, 0, 2, 3, 5, 1}, {5, 4, 2, 3, 1, 0}, 
{1, 5, 2, 3, 0, 4}, {5, 1, 3, 2, 4, 0}, {1, 0, 3, 2, 5, 4}, 
{0, 4, 3, 2, 1, 5}, {4, 5, 3, 2, 0, 1}, {1, 3, 5, 0, 2, 4}, 
{0, 3, 1, 4, 2, 5}, {4, 3, 0, 5, 2, 1}, {5, 3, 4, 1, 2, 0}, 
{3, 4, 5, 0, 1, 2}, {3, 5, 1, 4, 0, 2}, {3, 1, 0, 5, 4, 2}, 
{3, 0, 4, 1, 5, 2}, };

void check()
{
    for(int i=0;i<n;i++)
        for(int j=0;j<6;j++)
    //让每个旋转后的面对应旋转前的颜色
            color[i][dice24[r[i]][j]]=dice[i][j];
    //上面这句话包含的一个隐藏信息,虽说我们强调第一个不旋转,但实际比
    //较时第一个的初态却是已经是经过一次向上翻转后的状态,我们所谓的不
    //旋转只是说不去枚举他旋转的情况罢了!不增加时间复杂度
    int tot=0;
    for(int i=0;i<6;i++)//枚举6个面
    {
        int cnt[N*6];//记录当前的面在每个正方体中的颜色出现次数
        memset(cnt,0,sizeof cnt);
        int maxv=0;//记录最大重复颜色
        for(int j=0;j<n;j++) maxv=max(maxv,++cnt[color[j][i]]);
        tot+=n-maxv;
    }
    ans=min(ans,tot);
}

void dfs(int u)
{
    if(u==n)
    {
        check();
        return;
    }
    for(int i=0;i<24;i++)
    {
        r[u]=i;
        dfs(u+1);
    }
}

int main()
{
    while(cin>>n,n)
    {
        names.clear();
        for(int i=0;i<n;i++)
            for(int j=0;j<6;j++)
            {
                char name[30];
                scanf("%s",name);
                dice[i][j]=ID(name);
            }
        ans=n*6;//上界
        r[0]=0;//第一个不旋转
        dfs(1);
        printf("%d\n",ans);
    }
    return 0;
}

创作不易,如果您觉得对您有帮助,就点个赞支持一下!您的赞就是我持续更新优质题解的动力!




Accepting
12天前

鄙人不才,此中鄙陋甚多,望海涵!!!

前记:这道题目还是比较恶心的,网上找了许多代码都看不懂(原谅我太菜了),可能太习惯了y总的码风,看别人的那些define一大堆的就感觉不是很想看,所以搞了好久!


大致思路:题目是让我们去找点集或者有k个点的团,若都没有则输出-1!
注意:此题关键就是找团,比较暴力的思路就是在图中,找到一个度等于k-1的点时,就将这点以及他的邻点都加入一个vector中(在我们这里这个vector就定义为tuan),再利用双重循环来遍历团中所有的点是否全都互通,若互通就输出!
这里有的朋友可能会问k是1e5级别的怎么能双重循环呢?但其实我们在题目一开始的时候不论找团或者集合都有一个大前提,那就是k*(k-1)/2>m,只有边够用我们才去寻找,不然就直接是-1了,了解了这个就不难知道双重循环是m级别的,但在找互通时我们又用了一个比较巧妙的方式,直接遍历邻边肯定会超时(三重循环),因此我们可以在加边时对于每一个点建一个vector,并进行排序,这样我们在查找时就可以二分查找了,保证程序可行性!详细见代码!
关于时间复杂度的分析:题目中说当多种答案出现时输出一种即可,也就是说当集合和团都存在时输出一个即可,而我们在寻找时之所以可行,是因为我们在找到一个团时就会退出循环,而找不到时又会标记没失败,下次不会将这个点再加入团中,这样就保证了加入团中的都是没试过的点,保证时间复杂度接近O(mlogn)!

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N=1e5+10,M=2*N;

int n,m,k;
int h[N],d[N],e[M],ne[M],idx;
bool st[N],vis[N];
vector<int> G[N];
vector<int> tuan;

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    d[b]++,G[a].push_back(b);
}

void init()
{
    idx=0;
    memset(h,-1,sizeof h);
    for(int i=0;i<=n+10;i++)
    {
        G[i].clear();
        st[i]=d[i]=vis[i]=0;
    }
}

void dfs(int now)
{
    queue<int> q;
    for(int i=1;i<=n;i++) if(d[i]<now) q.push(i),st[i]=true;
    bool ok=false;
    while(q.size())
    {
        int t=q.front();
        q.pop();
        if(d[t]==now-1)
        {
            tuan.clear();
            tuan.push_back(t);
            for(int i=h[t];~i;i=ne[i])
            {
                int j=e[i];
                if(vis[j]) continue;
                tuan.push_back(j);
            }
            bool mark=false;
            for(int i=0;i<tuan.size();i++)
                for(int j=i+1;j<tuan.size();j++)
                {
                    if(!binary_search(G[tuan[i]].begin(),G[tuan[i]].end(),tuan[j]))
                        mark=true;
                }
            if(!mark)
            {
                ok=true;
                break;
            }
        }
        vis[t]=true;
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            d[j]--;
            if(d[j]<now && !st[j]) q.push(j),st[j]=true;
        }
    }
    if(ok)
    {
        puts("2");
        for(int i=0;i<tuan.size();i++) printf("%d ",tuan[i]);
        puts("");
    }
    else
    {
        int tmp=0;
        for(int i=1;i<=n;i++) if(st[i]) tmp++;
        if(tmp<n)
        {
            printf("1 %d\n",n-tmp);
            for (int i=1;i<=n;i++)  if(!st[i])  printf("%d ",i);
            printf("\n");
        }
        else puts("-1");
    }
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        init();
        scanf("%d%d%d",&n,&m,&k);
        for(int i=1;i<=m;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            add(a,b);add(b,a);
        }
        if((LL)k*(k-1)/2>m)
        {
            printf("-1\n");
            continue;
        }
        for(int i=1;i<=n;i++) sort(G[i].begin(),G[i].end());
        dfs(k);
    }
    return 0;
}

创作不易,如果您觉得对您有帮助,就点个赞支持一下!您的赞就是我持续更新优质题解的动力!




Accepting
18天前

鄙人不才,此中鄙陋甚多,望海涵!!!

#include<iostream>
#include<cstring>

using namespace std;

const int N=110;

int f[N],f1[N],a[N];

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n,ans=0;
        cin>>n;
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
        {
            f[i]=f1[i]=1;
            for(int j=1;j<i;j++)
                if(a[i]<a[j]) f[i]=max(f[j]+1,f[i]);
                else if(a[i]>a[j]) f1[i]=max(f1[j]+1,f1[i]);
            ans=max(ans,max(f[i],f1[i]));
        }
        cout<< ans <<endl;
    }
    return 0;
}


活动打卡代码 AcWing 1243. 糖果

Accepting
21天前
#include<iostream>
#include<vector>

using namespace std;

const int N=25,M=1<<20;

int n,m,k;
vector<int> col[N];
int log2[M];

int lowbit(int x)
{
    return x&-x;
}

int h(int state)
{
    //当前还需要搜索的最少的层数
    int res=0;
    for(int i=(1<<m)-1-state;i;i-=lowbit(i))
    {
        int c=log2[lowbit(i)];
        for(auto row:col[c]) i&=~row;
        res++;
    }
    return res;
}

bool dfs(int depth,int state)
{
    if(!depth || h(state)>depth) return state==(1<<m)-1;
    //寻找分枝最少,优先搜索顺序
    int t=-1;
    for(int i=(1<<m)-1-state;i;i-=lowbit(i))
    {
        int c=log2[lowbit(i)];
        if(t==-1 || col[c].size()<col[t].size()) t=c;
    }
    for(auto row:col[t]) if(dfs(depth-1,state|row)) return true;
    return false;
}

int main()
{
    cin>>n>>m>>k;
    for(int i=0;i<m;i++) log2[1<<i]=i;
    for(int i=0;i<n;i++)
    {
        int state=0;
        for(int j=0;j<k;j++)
        {
            int x;
            scanf("%d",&x);
            state|=1<<x-1;
        }
        for(int j=0;j<m;j++)
            if(state>>j&1) col[j].push_back(state);
    }
    int depth=0;
    while(depth<=m && !dfs(depth,0)) depth++;
    if(depth>m) puts("-1");
    else printf("%d\n",depth);
    return 0;
}


活动打卡代码 AcWing 1243. 糖果

Accepting
21天前
#include<iostream>
#include<vector>

using namespace std;

const int N=25,M=1<<20;

int n,m,k;
vector<int> col[M];
int log2[M];

int lowbit(int x)
{
    return x&-x;
}

int h(int state)
{
    //当前还需要搜索的最少的层数
    int res=0;
    for(int i=(1<<m)-1-state;i;i-=lowbit(i))
    {
        int c=log2[lowbit(i)];
        for(auto row:col[c]) i&=~row;
        res++;
    }
    return res;
}

bool dfs(int depth,int state)
{
    if(!depth || h(state)>depth) return state==(1<<m)-1;
    //寻找分枝最少,优先搜索顺序
    int t=-1;
    for(int i=(1<<m)-1-state;i;i-=lowbit(i))
    {
        int c=log2[lowbit(i)];
        if(t==-1 || col[c].size()<col[t].size()) t=c;
    }
    for(auto row:col[t]) if(dfs(depth-1,state|row)) return true;
    return false;
}

int main()
{
    cin>>n>>m>>k;
    for(int i=0;i<m;i++) log2[1<<i]=i;
    for(int i=0;i<n;i++)
    {
        int state=0;
        for(int j=0;j<k;j++)
        {
            int x;
            scanf("%d",&x);
            state|=1<<x-1;
        }
        for(int j=0;j<m;j++)
            if(state>>j&1) col[j].push_back(state);
    }
    int depth=0;
    while(depth<=m && !dfs(depth,0)) depth++;
    if(depth>m) puts("-1");
    else printf("%d\n",depth);
    return 0;
}



Accepting
22天前
#include<iostream>
#include<cstring>

using namespace std;
typedef long long LL;

int n,m;

void mul(LL a[3][3],LL b[3][3],LL c[3][3])
{
    LL tmp[3][3]={0};
    for(int i=0;i<3;i++)    
        for(int j=0;j<3;j++)
            for(int k=0;k<3;k++)
                tmp[i][j]=(tmp[i][j]+b[i][k]*c[k][j])%m;
    memcpy(a,tmp,sizeof tmp);
}

void mul(LL a[3],LL b[3],LL c[3][3])
{
    LL tmp[3]={0};
    for(int i=0;i<3;i++)    
        for(int j=0;j<3;j++)
                tmp[i]=(tmp[i]+b[j]*c[j][i])%m;
    memcpy(a,tmp,sizeof tmp);
}

int main()
{
    cin>>n>>m;
    LL a[][3]={
        {0,1,0},
        {1,1,1},
        {0,0,1}
    };
    LL f[3]={1,1,1};
    n--;
    while(n)
    {
        if(n&1) mul(f,f,a);
        mul(a,a,a);
        n>>=1;
    }
    cout<< f[2] <<endl;
    return 0;
}



活动打卡代码 AcWing 1220. 生命之树

Accepting
23天前
#include<iostream>
#include<cstring>

using namespace std;
typedef long long LL;
const int N=1e5+10,M=2*N;

int h[N],e[M],ne[M],idx;
int w[N],n;
LL sum=-1e6,f[N];

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void dfs(int u,int fa)
{
    f[u]+=w[u];
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(j==fa) continue;
        dfs(j,u);
        f[u]+=max((LL)0,f[j]);
    }
}

int main()
{
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);
    for(int i=1;i<n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);
    }
    dfs(1,-1);
    for(int i=1;i<=n;i++) sum=max(sum,f[i]);
    cout<< sum <<endl;
    return 0;
} 


活动打卡代码 AcWing 1222. 密码脱落

Accepting
23天前

倒着做

#include<iostream>

using namespace std;

const int N=1010;

int f[N][N];
string s;

int main()
{
    cin>>s;
    int n=s.size();
    for(int len=1;len<=n;len++)
        for(int l=0;l+len-1<n;l++)
        {
            int r=l+len-1;
            if(len==1) f[l][r]=1;
            else
            {
                if(s[l]==s[r]) f[l][r]=f[l+1][r-1]+2;
                f[l][r]=max(f[l][r],max(f[l+1][r],f[l][r-1]));
            }
        }
    cout<< n-f[0][n-1] <<endl;
    return 0;
}

正做

#include<iostream>
#include<cstring>

using namespace std;

const int N=1010;

int f[N][N];
string s;

int main()
{
    cin>>s;
    int n=s.size();
    memset(f,0x3f,sizeof f);
    for(int len=1;len<=n;len++)
        for(int l=0;l+len-1<n;l++)
        {
            int r=l+len-1;
            if(len==1) f[l][r]=0;
            else
            {
                if(s[l]==s[r])
                {
                    if(len!=2) f[l][r]=f[l+1][r-1];
                    else f[l][r]=0;
                }
                else f[l][r]=min(f[l][r],min(f[l+1][r]+1,f[l][r-1]+1));
            }
        }
    cout<< f[0][n-1] <<endl;
    return 0;
}


活动打卡代码 AcWing 1047. 糖果

Accepting
24天前
#include<iostream>
#include<cstring>

using namespace std;

const int N=110;

int f[N][N];

int main()
{
    int n,k;
    cin>>n>>k;
    memset(f,-0x3f,sizeof f);
    f[0][0]=0;
    for(int i=1;i<=n;i++)
    {
        int w;
        scanf("%d",&w);
        for(int j=0;j<k;j++)
            f[i][j]=max(f[i-1][j],f[i-1][((j-w)%k+k)%k]+w);
    }
    cout<< f[n][0] <<endl;
    return 0;
}