7.30

King

索引

刷题表

P1010 幂次方【打表】
南蛮图腾【分治】
连续自然数的和【数学】
末日的传说【数学】
八皇后【回溯】
加分二叉树【DP,前序遍历】
P1030 求先序排列【前序中序后序遍历】

noip原题过手

积木大赛【过水】
乘积最大【DP】
进制转换【模拟，注意负进制的特点】

P1010 幂次方

/*
translation:
    
solution:

trigger:
    
note:
    *
date:
    2019.07.30
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,b) for(ll i=a;i<=b;++i)
#define dwn(i,a,b) for(ll i=a;i>=b;--i) 
template <typename T> inline void rd(T &x){x=0;char c=getchar();int f=0;while(!isdigit(c)){f|=c=='-';c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x=f?-x:x;} 
#define mem(a,b) memset(a,b,sizeof(a))

#define N 

int n,m;

void dfs(int x){
    if(x==0){
        printf("2(0)");
        return ;
    }
    if(x==1){
        printf("2");
        return ;
    }
    if(x==2){
        printf("2(2)");
        return ;
    }
    if(x==3){
        printf("2(2+2(0))");
        return ;
    }
    if(x==4){
        printf("2(2(2))");
        return ;
    }
    if(x==5){
        printf("2(2(2)+2(0))");
        return ;
    }
    if(x==6){
        printf("2(2(2)+2)");
        return ;
    }
    if(x==7){
        printf("2(2(2)+2+2(0))");
        return ;
    }
    if(x==8){
        printf("2(2(2+2(0)))");
        return ;
    }
    if(x==9){
        printf("2(2(2+2(0))+2(0)))");
        return ;
    }
    if(x==10){
        printf("2(2(2+2(0))+2)");
        return ;
    }
    if(x==11){
        printf("2(2(2+2(0))+2+2(0))");
        return ;
    }
    if(x==12){
        printf("2(2(2+2(0))+2(2)");
        return ;
    }
    if(x==13){
        printf("2(2(2+2(0))+2(2)+2(0))");
        return ;
    }
    if(x==14){
        printf("2(2(2+2(0))+2(2)+2)");
        return ;
    }
    dwn(i,14,0)
        if(x-pow(2,i)>=0){
            x-=pow(2,i);
            if(x!=0){
                dfs(i);
                printf("+");
            }
            else if(x==0){
                dfs(i);
                return ;
            }
        }
}

int main(){
    #ifdef WIN32
    freopen("mi.txt","r",stdin);
    #endif
    rd(n);
    dfs(n);
    return 0;
}

知识兔

乘积最大

/*
translation:
    
solution:
    
trigger:
    
note:
    *DP
    *字符串默认从0开始存,长度为0~n-1 
date:
    2019.07.29
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,b) for(ll i=a;i<=b;++i)
#define dwn(i,a,b) for(ll i=a;i>=b;--i) 
template <typename T> inline void rd(T &x){x=0;char c=getchar();int f=0;while(!isdigit(c)){f|=c=='-';c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x=f?-x:x;} 
#define mem(a,b) memset(a,b,sizeof(a))

string s;
ll n,num;
ll f[410][410];
//f[i][j]表示前i位添加了j个乘号时的最优解
ll zhi(int l,int r){
    ll sum=0,base=1;
    dwn(i,r,l){
        sum+=(s[i]-'0')*base;
        base*=10;
    }
    return sum;
}

int main(){
    rd(n),rd(num);
    cin>>s;
    rep(i,0,n-1)
        f[i][0]=zhi(0,i);
    rep(i,1,n)
        rep(j,0,num)
            dwn(k,i,j)
                f[i][j]=max(f[i][j],f[k-1][j-1]*zhi(k,i));
    printf("%lld",f[n-1][num]);
    return 0;
}

知识兔

P1498 南蛮图腾

/*
translation:
    
solution:

trigger:
    
note:
    *
date:
    2019.07.30
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,b) for(ll i=a;i<=b;++i)
#define dwn(i,a,b) for(ll i=a;i>=b;--i) 
template <typename T> inline void rd(T &x){x=0;char c=getchar();int f=0;while(!isdigit(c)){f|=c=='-';c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x=f?-x:x;} 
#define mem(a,b) memset(a,b,sizeof(a))

#define N 3010
int n,x,y;
char a[N][N];

void copy(int &u,int &v){
    rep(i,1,u)
        rep(j,1,v)  
            a[i][v+j]=a[u+i][(v/2)+j]=a[i][j];
    u*=2;
    v*=2;
}

int main(){
    mem(a,' ');
    a[1][1]=a[2][2]='\\';
    a[1][2]=a[1][3]='_';
    a[1][4]=a[2][3]='/';
    x=2,y=4;
    rd(n);
    rep(i,1,n-1)copy(x, y);//递推n-1次
    dwn(i,x,1){
        dwn(j,y,1)
            printf("%c",a[i][j]);
        puts("");
    }
    return 0;
}

知识兔

连续自然数和

/*
    设首项为L，末项为R，那么sum(L,R)=(L+R)(R-L+1)/2=M
    即(L+R)(R-L+1)=2M
    可以把2M分解成两个数之积，假设分成了两个数K1,K2，且K1<K2时，
    可以列一个二元一次方程组
    R-L+1=K1
    L+R=K2 解得L=(K2-K1+1)/2, R=(K1+K2-1)/2
    当K1,K2一奇一偶时，L,R才有自然数解.
    不过有一种特殊情况，就是L=R的情况，这种情况是不允许的
    即(K2-K1+1)/2≠(K1+K2-1)/2,解得K1≠1
*/
#include<bits/stdc++.h>
using namespace std;

int M;

int main(){
    scanf("%d",&M);
    for(int k1=sqrt(2*M);k1>1;k1--)
        if(2*M%k1==0 && (k1+2*M/k1)%2==1){
            int k2=2*M/k1;
            printf("%d %d\n",(k2-k1+1)/2,(k1+k2-1)/2);
        }
    return 0;
}

知识兔

末日的传说

/*
translation:
    
solution:

trigger:
    
note:
    *
date:
    2019.07.30
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,b) for(ll i=a;i<=b;++i)
#define dwn(i,a,b) for(ll i=a;i>=b;--i) 
template <typename T> inline void rd(T &x){x=0;char c=getchar();int f=0;while(!isdigit(c)){f|=c=='-';c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x=f?-x:x;} 
#define mem(a,b) memset(a,b,sizeof(a))

#define N 50010

ll n,m,a[N];

int main(){
    #ifdef WIN32
    freopen("mori.txt","r",stdin);
    #endif
    rd(n),rd(m);
    ll h=1,t=n;
    rep(i,1,n){
        ll k=(n-i)*(n-i-1)/2;
        if(k>=m)
            a[h++]=i;//放头上
        else{
            a[t--]=i;//放最后
            m-=(t-h+1);//m-(i的贡献) 
        }
    }
    rep(i,1,n)
        printf("%lld ",a[i]);
    return 0;
}

知识兔

八皇后

/*
translation:
    
solution:

trigger:
    
note:
    *
date:
    2019.07.30
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,b) for(ll i=a;i<=b;++i)
#define dwn(i,a,b) for(ll i=a;i>=b;--i) 
template <typename T> inline void rd(T &x){x=0;char c=getchar();int f=0;while(!isdigit(c)){f|=c=='-';c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x=f?-x:x;} 
#define mem(a,b) memset(a,b,sizeof(a))

#define N 

int n,sum;
int ans[15],check[5][30];


void dfs(int line){
    if(line==n+1){
        sum++;
        if(sum>3)return;
        else{
            rep(i,1,n)
                printf("%d ",ans[i]);
            puts("");
            return ;
        }
    }
    rep(i,1,n){
        if((!check[0][i]) && (!check[1][line+i]) && (!check[2][line-i+n])){
            ans[line]=i;
            check[0][i]=1;
            check[1][line+i]=1;
            check[2][line-i+n]=1;
            dfs(line+1);
            check[0][i]=0;
            check[1][line+i]=0;
            check[2][line-i+n]=0;
        }
    }
}

int main(){
    #ifdef WIN32
    freopen("","r",stdin);
    #endif
    rd(n);
    dfs(1);
    printf("%d",sum);
    return 0;
}

知识兔

加分二叉树

/*
translation:
    
solution:

trigger:
    
note:
    *dwn(i,n,1) 的原因：算f[i][...]时要知道f[i][k]和f[k][...]，而k在i后面，所以f[k][...]还没有算出，因此要从后往前算
    *f[i][i-1]=1的原因：k会等于i，f[i][k-1]为f[i][i-1]为空，题目中规定空子树的加分为1
date:
    2019.07.30
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,b) for(ll i=a;i<=b;++i)
#define dwn(i,a,b) for(ll i=a;i>=b;--i) 
template <typename T> inline void rd(T &x){x=0;char c=getchar();int f=0;while(!isdigit(c)){f|=c=='-';c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x=f?-x:x;} 
#define mem(a,b) memset(a,b,sizeof(a))

#define N 50

int n;
int w[N];
int f[N][N],root[N][N];

void print(int l,int r){
    if(l>r)return ;
    if(l==r){
        printf("%d ",l);
        return;
    }
    printf("%d ",root[l][r]);
    print(l,root[l][r]-1);
    print(root[l][r]+1,r);
}


int main(){
    #ifdef WIN32
    freopen("","r",stdin);
    #endif
    rd(n);
    rep(i,1,n){
        rd(w[i]);
        f[i][i]=w[i];
        f[i][i-1]=1;//2
    }
    dwn(i,n,1)//1
        rep(j,i+1,n)
            rep(k,i,j)
                if(f[i][j]<f[i][k-1]*f[k+1][j]+f[k][k]){
                    f[i][j]=f[i][k-1]*f[k+1][j]+f[k][k];
                    root[i][j]=k;
                }
    printf("%d\n",f[1][n]);
    print(1,n);
    return 0;
}

知识兔

P1030 求先序排列

/*
translation:
    
solution:

trigger:
    
note:
    *
date:
    2019.07.30
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,b) for(ll i=a;i<=b;++i)
#define dwn(i,a,b) for(ll i=a;i>=b;--i) 
template <typename T> inline void rd(T &x){x=0;char c=getchar();int f=0;while(!isdigit(c)){f|=c=='-';c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x=f?-x:x;} 
#define mem(a,b) memset(a,b,sizeof(a))

string a,b;

int calc(int l1,int r1,int l2,int r2){
    int m=a.find(b[r2]);
    cout<<b[r2];
    if(m>l1)
        calc(l1,m-1,l2,l2+m-1-l1);
    if(m<r1)
        calc(m+1,r1,l2+m-l1,r2-1);
}

int main(){
    cin>>a>>b;
    calc(0,a.size()-1,0,b.size()-1);
    return 0;
}

知识兔

进制转换

/*
translation:
    
solution:

trigger:
    
note:
    *
date:
    2019.07.30
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,b) for(ll i=a;i<=b;++i)
#define dwn(i,a,b) for(ll i=a;i>=b;--i) 
template <typename T> inline void rd(T &x){x=0;char c=getchar();int f=0;while(!isdigit(c)){f|=c=='-';c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x=f?-x:x;} 
#define mem(a,b) memset(a,b,sizeof(a))

int base,num_10,n;

void change(int q){
    int r;
    r=q%base;
    q=q/base;
    if(r<0){
        r-=base;
        q++;
    }
    if(q!=0)//注意不能是大于0，因为负进制的关系，q可能为负。 
        change(q);
    if(r>9)printf("%c",r-10+'A');
    else printf("%d",r);
}

int  main(){
    rd(num_10),rd(base);
    printf("%d=",num_10);
    change(num_10);  
    printf("(base%d)",base); 
    return 0;    
}

知识兔

计算机

2022年1月21日

7.30

索引

刷题表

南蛮图腾【分治】

末日的传说【数学】

加分二叉树【DP,前序遍历】

P1030 求先序排列【前序中序后序遍历】

noip原题过手

乘积最大【DP】

进制转换【模拟，注意负进制的特点】

P1010 幂次方

乘积最大

P1498 南蛮图腾

连续自然数和

末日的传说

八皇后

加分二叉树

P1030 求先序排列

进制转换

热门标签

最新文章