头像

李乾


访客:7497

离线:9小时前


活动打卡代码 AcWing 181. 回转游戏

李乾
4天前

AcWing 181. 回转游戏

#include <iostream>
#include <algorithm>
using namespace std ;
const int N=24 ;
const int op[8][7]=
{
    {0,2,6,11,15,20,22},
    {1,3,8,12,17,21,23},
    {10,9,8,7,6,5,4},
    {19,18,17,16,15,14,13},
    {23,21,17,12,8,3,1},
    {22,20,15,11,6,2,0},
    {13,14,15,16,17,18,19},
    {4,5,6,7,8,9,10}
} ;
const int opp[8]={5,4,7,6,1,0,3,2} ;
const int center[8]={6,7,8,11,12,15,16,17} ;
int q[N] ;
int path[100] ;
int f()
{
    int sum[4]={0} ;
    for(int i=0;i<8;i++) sum[q[center[i]]]++ ;
    int maxv=0 ;
    for(int i=1;i<4;i++) maxv=max(maxv,sum[i]) ;
    return 8-maxv ;
}
void operate(int x)
{
    int t=q[op[x][0]] ;
    for(int i=0;i<6;i++) q[op[x][i]]=q[op[x][i+1]] ;
    q[op[x][6]]=t ;
}
bool dfs(int dep,int max_d,int last_move)
{
    if(dep+f()>max_d) return false ;
    if(!f()) return true ;
    for(int i=0;i<8;i++)
        if(opp[i]!=last_move)
        {
            operate(i) ;
            path[dep]=i ;
            if(dfs(dep+1,max_d,i)) return true ;
            operate(opp[i]) ;
        }
    return false ;
}
int main()
{
    while(~scanf("%d",&q[0]),q[0])
    {
        for(int i=1;i<N;i++)
            scanf("%d",&q[i]) ;
        int dep=0 ;
        while(!dfs(0,dep,-1)) dep++ ;
        if(!dep) puts("No moves needed") ;
        else 
        {
            for(int i=0;i<dep;i++) printf("%c",path[i]+'A') ;
            puts("") ;
        }
        printf("%d\n",q[6]) ;
    }
    return 0 ;
}


活动打卡代码 AcWing 180. 排书

李乾
4天前

AcWing 180. 排书

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std ;
int n ;
vector<int> q ;
vector<int> cache[5] ;
int f()
{
    int res=0 ;
    for(int i=0;i<n-1;i++)
        if(q[i]+1!=q[i+1]) res++ ;
    return (res+2)/3 ;
}
bool dfs(int dep,int max_d)
{
    if(dep+f()>max_d) return false ;
    if(!f()) return true ;
    for(int len=1;len<n;len++)
        for(int l=0;l+len-1<n;l++)
        {
            int r=l+len-1 ;
            for(int k=r+1;k<n;k++)
            {
                cache[dep].clear() ;
                for(int i=0;i<l;i++) 
                    cache[dep].push_back(q[i]) ;
                for(int i=r+1;i<=k;i++)  
                    cache[dep].push_back(q[i]) ;
                for(int i=l;i<=r;i++) 
                    cache[dep].push_back(q[i]) ;
                for(int i=k+1;i<n;i++) 
                    cache[dep].push_back(q[i]) ;
                swap(q,cache[dep]) ;
                if(dfs(dep+1,max_d)) return true ;
                swap(q,cache[dep]) ;
            }
        }
    return false ;
}
int main()
{
    int t ;
    scanf("%d",&t) ;
    while(t--)
    {
        scanf("%d",&n) ;
        q.assign(20,0) ;
        for(int i=0;i<n;i++)
            scanf("%d",&q[i]) ;
        int dep=0 ;
        while(dep<5&&!dfs(0,dep)) dep++ ;
        if(dep>=5) puts("5 or more") ;
        else printf("%d\n",dep) ;
    }
    return 0 ;
}


活动打卡代码 AcWing 171. 送礼物

李乾
5天前

AcWing 171. 送礼物

#include <iostream>
#include <algorithm>
using namespace std ;
typedef long long ll ;
const int N=50 ;
int n,w,k ;
int item[N] ;
vector<int> first_k ;
int ans ;
ll t(int i)
{
    return ((ll)1<<i)+((ll)i<<n-i) ;
}
void dfs1(int num,int sum)
{
    if(sum>w) return ;
    if(num==k)
    {
        first_k.push_back(sum) ;
        return ;
    }
    dfs1(num+1,sum) ;
    if((ll)sum+item[num]<=w) dfs1(num+1,sum+item[num]) ;
}
void dfs2(int num,int sum)
{
    if(num>=n)
    {
        ans=max(ans,sum+first_k[upper_bound(first_k.begin(),first_k.end(),w-sum)-first_k.begin()-1]) ;
        return ;
    }
    dfs2(num+1,sum) ;
    if((ll)sum+item[num]<=w) dfs2(num+1,sum+item[num]) ;
}
int main()
{
    scanf("%d%d",&w,&n) ;
    for(int i=0;i<n;i++)
        scanf("%d",&item[i]) ;
    sort(item,item+n,greater<int>()) ;
    k=1 ;
    ll res=2e18 ;
    for(int i=1;i<n;i++)
        if(t(i)<res) 
        {
            res=t(i) ;
            k=i ;
        }
    dfs1(0,0) ;
    sort(first_k.begin(),first_k.end()) ;
    unique(first_k.begin(),first_k.end()+1) ;
    dfs2(k,0) ;
    printf("%d",ans) ;
    return 0 ;
}



李乾
5天前

unique:去重函数

iterator unique(iterator iter1,iterator iter2)
// 在[iter1,iter2)中去重 ,是左闭右开区间!!!
//注:iter1,iter2,unique()的值均可用指针替代
//例如:
//int arr[100] ;
//cout << unique(arr,arr+99)-arr << endl ;//减去头指针即可取得数组长度
//sort好的数据才能unique!

示例代码:

#include <algorithm>
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std ;
int arr[100] ;
int main()
{
    srand(time(NULL)) ;
    for(int i=0;i<10;i++)
        arr[i]=rand()%10 ; 
    // 取随机值 rand()

    puts("original:") ;
    for(int i=0;i<10;i++)
        printf("%d ",arr[i]) ; 

    puts("\nsort:") ;
    sort(arr,arr+10) ;             
    for(int i=0;i<10;i++)
        printf("%d ",arr[i]) ; 
    //sort

    puts("\nunique:") ;
    int cnt=unique(arr,arr+10)-arr ;
    for(int i=0;i<cnt;i++)            //try:change cnt into 10
        printf("%d ",arr[i]) ;
    // unique
    return 0 ;
}


活动打卡代码 AcWing 170. 加成序列

李乾
5天前

AcWing 170.此题有巨坑

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std ;
const int N=110 ;
int path[N] ;
int n ;
bool dfs(int dep,int maxd)
{
    if(dep==maxd) return path[dep]==n ;
    bool st[N]={0} ;
    for(int i=dep;i;i--)
        for(int j=i;j;j--)
        {
            int sum=path[i]+path[j] ;
            if(sum>n||st[sum]||sum<=path[dep]) continue ;
            st[sum]=true ;
            path[dep+1]=sum ;
            if(dfs(dep+1,maxd)) return true ;
            //st[sum]=false ;                  不需要恢复现场
        }
        return false ;
}
int main()
{
    path[1]=1 ;
    while(~scanf("%d",&n),n)
    {
        int dep=1 ;
        while(!dfs(1,dep)) dep++ ;
        //printf("%d   ",dep) ;        格式坑啊!
        for(int i=1;i<=dep;i++)
            printf("%d ",path[i]) ;
        //printf("%d\n",path[dep]) ;
        puts("") ;
    }
    return 0 ;
}


活动打卡代码 AcWing 168. 生日蛋糕

李乾
14天前

AcWing 168. 生日蛋糕

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std ;
const int N=20,INF=1e9 ;
int n,m ;
int mins[N],minv[N] ;
int R[N],H[N] ;
int ans=INF ;
void dfs(int u,int v,int s)
{
    if(v+minv[u]>n) return ;
    if(s+mins[u]>=ans) return ;
    if(s+2*(n-v)/R[u+1]>=ans) return ;
    if(!u)
    {
        if(v==n) ans=s ;
        return ;
    }
    for(int r=min(R[u+1]-1,(int)sqrt(n-v));r>=u;r--)
        for(int h=min(H[u+1]-1,(n-v)/r/r);h>=u;h--)
        {
            int t=0 ;
            if(u==m) t=r*r ;
            R[u]=r,H[u]=h ;
            dfs(u-1,v+r*r*h,s+2*r*h+t) ;
        }
}
int main()
{
    scanf("%d%d",&n,&m) ;
    for(int i=1;i<=m;i++)
    {
        mins[i]=mins[i-1]+2*i*i ;
        minv[i]=minv[i-1]+i*i*i ;
    }
    R[m+1]=H[m+1]=INF ;
    dfs(m,0,0) ;
    if(ans==INF) puts("0") ;
    else printf("%d",ans) ;
    return 0 ;
}


活动打卡代码 AcWing 167. 木棒

李乾
14天前

AcWing 167. 木棒

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std ;
const int N=1<<6 ;
int w[N] ;
int len,sum ;
int n ;
bool st[N] ;
bool dfs(int group,int count,int start)
{
    if(group*len==sum) return true ;
    if(count==len) return dfs(group+1,0,0) ;
    //printf("%d %d %d\n",group,count,start) ;
    for(int i=start;i<n;i++)
    {
        if(st[i]) continue ;
        if(count+w[i]>len) continue ;
        st[i]=true ;
        if(dfs(group,count+w[i],i+1)) return true ;
        st[i]=false ;
        if(!count) return false ;
        if(count+w[i]==len) return false ;
        int j=i ;
        while(j<n&&w[j]==w[i]) j++ ;
        i=j-1 ;
    }
    return false ;
}
int main()
{
    while(~scanf("%d",&n),n)
    {
        sum=0,len=1 ;
        memset(st,false,sizeof st) ;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&w[i]) ;
            sum+=w[i] ;
        }
        sort(w,w+n,greater<int>()) ;
        while(len<=sum)
        {
            if(sum%len==0&&dfs(0,0,0))
            {
                printf("%d\n",len) ;
                break ;
            }
            len++ ;
        }
    }
    return 0 ;
}


活动打卡代码 AcWing 166. 数独

李乾
15天前

AcWing 166. 数独

#include <iostream>
#include <algorithm>
#include <string>
#define lowbit(x) (x&-x) 
using namespace std ;
const int N=9,M=1<<N ;
int row[N],col[N],cell[3][3] ;
string str ;
int ones[M],two[M] ;
void init_1()
{
    for(int i=0;i<N;i++) two[1<<i]=i ;
    for(int i=0;i<M;i++)
        for(int j=0;j<N;j++)
            ones[i]+=i>>j&1 ;
}
void init_2()
{
    for(int i=0;i<N;i++)
        row[i]=col[i]=M-1 ;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            cell[i][j]=M-1 ;
}
void mark(int x,int y,int t,bool flag)
{
    if(flag) str[x*N+y]=t+'1' ;
    else str[x*N+y]='.' ;
    int val=1<<t ;
    if(!flag) val=-val ;
    row[x]-=val ;
    col[y]-=val ;
    cell[x/3][y/3]-=val ;
}
int get(int x,int y)
{
    return row[x]&col[y]&cell[x/3][y/3] ;
}
bool dfs(int cnt)
{
    if(!cnt) return true ;
    int minv=10 ;
    int x,y ;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            if(str[i*N+j]=='.')
            {
                int st=get(i,j) ;
                if(ones[st]<minv)
                {
                    minv=ones[st] ;
                    x=i ;
                    y=j ;
                }
            }
    int st=get(x,y) ;
    for(int i=st;i;i-=lowbit(i))
    {
        int t=two[lowbit(i)] ;
        mark(x,y,t,true) ;
        if(dfs(cnt-1)) return true ;
        mark(x,y,t,false) ;
    }
    return false ;
}
int main()
{
    init_1() ;
    while(cin >> str&&str[0]!='e')
    {
        init_2() ;
        int cnt=0 ;
        for(int i=0,k=0;i<N;i++)
            for(int j=0;j<N;j++,k++)
                if(str[k]!='.')
                {
                    int t=str[k]-'1' ;
                    mark(i,j,t,true) ;
                }
                else cnt++ ;
        dfs(cnt) ;
        cout << str << endl ;
    }
    return 0 ;
}



李乾
15天前
#include <iostream>
#include <algorithm>
#include <string>
#define lowbit(x) (x&-x) 
using namespace std ;
const int N=9,M=1<<N ;
int row[N],col[N],cell[3][3] ;
string str ;
int ones[M],two[M] ;
void init_1()
{
    for(int i=0;i<N;i++) two[1<<i]=i ;
    for(int i=0;i<M;i++)
        for(int j=0;j<N;j++)
            ones[i]+=i>>j&1 ;
}
void init_2()
{
    for(int i=0;i<N;i++)
        row[i]=col[i]=M-1 ;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            cell[i][j]=M-1 ;
}
void mark(int x,int y,int t,bool flag)
{
    if(flag) str[x*N+y]=t+'1' ;
    else str[x*N+y]='.' ;
    int val=1<<t ;
    if(!flag) val=-val ;
    row[x]-=val ;
    col[y]-=val ;
    cell[x/3][y/3]-=val ;
}
int get(int x,int y)
{
    return row[x]&col[y]&cell[x/3][y/3] ;
}
bool dfs(int cnt)
{
    if(!cnt) return true ;
    int minv=10 ;
    int x,y ;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            if(str[i*N+j]=='.')
            {
                int st=get(i,j) ;
                if(ones[st]<minv)
                {
                    minv=ones[st] ;
                    x=i ;
                    y=j ;
                }
            }
    int st=get(x,y) ;
    for(int i=st;i;i-=lowbit(i))
    {
        int t=two[lowbit(i)] ;
        mark(x,y,t,true) ;
        if(dfs(cnt-1)) return true ;
        mark(x,y,t,false) ;
    }
    return false ;
}
int main()
{
    init_1() ;
    while(cin >> str&&str[0]!='e')
    {
        init_2() ;
        int cnt=0 ;
        for(int i=0,k=0;i<N;i++)
            for(int j=0;j<N;j++,k++)
                if(str[k]!='.')
                {
                    int t=str[k]-'1' ;
                    mark(i,j,t,true) ;
                }
                else cnt++ ;
        dfs(cnt) ;
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<N;j++)
                printf("%c ",str[i*N+j]) ;
            puts("") ;
            if(i%9==8) puts("") ;
        }
    }
    return 0 ;
}

Nice!



活动打卡代码 AcWing 165. 小猫爬山

李乾
15天前

AcWing 165. 小猫爬山

#include <iostream>
#include <algorithm>
using namespace std ;
const int N=20 ;
int ans=20 ;
int c[N] ;
int sum[N] ;
int n,w ;
void dfs(int cat,int cable)
{
    if(cable>=ans) return ;
    if(cat==n)
    {
        ans=cable ;
        return ;
    }
    for(int i=0;i<cable;i++)
        if(sum[i]+c[cat]<=w)
        {
            sum[i]+=c[cat] ;
            dfs(cat+1,cable) ;
            sum[i]-=c[cat] ;
            flag=false ;
        }
    sum[cable]=c[cat] ;
    dfs(cat+1,cable+1) ;
    sum[cable]=0 ;
}
int main()
{
    scanf("%d%d",&n,&w) ;
    for(int i=0;i<n;i++) 
        scanf("%d",&c[i]) ;
    sort(c,c+n,greater<int>()) ;
    dfs(0,0) ;
    printf("%d",ans) ;
    return 0 ;
}
//>_<