头像

舞曲


访客:473

离线:9小时前


新鲜事 原文

舞曲
2天前
未做题单: 1.能量石


活动打卡代码 AcWing 180. 排书

舞曲
4天前
 for(int len = 1; len <= n; len++) {
    //枚举连续区间的长度
        for(int l = 0; l + len - 1 < n; l++) {
        //连续区间的开始节点    
            int r = l + len - 1;
            //连续区间的右端点
            for(int j = r + 1; j < n; j++) {
            //枚举选择插入的位置
                memcpy(w[depth], q, sizeof q);
                int y = l;
               ** for(int x = r+1; x <= j; x++, y++) q[y] = w[depth][x];
                for(int x = l; x <= r; x++, y++) q[y] = w[depth][x];**
                //切换两段数据单元
                if(dfs(depth+1, max_depth)) return true;
                memcpy(q, w[depth], sizeof q);
            }
        }
    }


新鲜事 原文

舞曲
6天前
903昂贵的聘礼: 误用不合法的路径修改dis,导致答案变小,血一般的教训。



舞曲
7天前

RT
QAQ




舞曲
7天前
// common 
# include <iostream>
# include <cstdio>
# include <cmath>
using namespace std;
int n,ans;
int a[3010],b[3010];
int f[3010][3010];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
    //f[i][j]表示到i以j未结尾的最长LICS 
    //回想LIS LCS 
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if(a[i]!=b[j]) f[i][j]=f[i-1][j]; //继承 
            else{
                for(int k=0;k<j;k++)
                    if(b[k]<b[j])  
                        f[i][j]=max(f[i][j],f[i-1][k]+1);
            }
        }
    for(int i=1;i<=n;i++)
        ans=max(ans,f[n][i]);   //必须 
    printf("%d",ans);
    return 0;
}
// dynamic
# include <iostream>
# include <cstdio>
# include <cmath>
using namespace std;
int n,ans;
int a[3010],b[3010];
int f[3010][3010];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
    for(int i=1;i<=n;i++){
        int val=0;
        for(int j=1;j<=n;j++){
            if(a[i]!=b[j]) f[i][j]=f[i-1][j];  
            else f[i][j]=val+1; 
            if(b[j]<a[i]) val=max(val,f[i-1][j]);
            // 避免重复扫描 
        }
    }       
    for(int i=1;i<=n;i++)
        ans=max(ans,f[n][i]);   
    printf("%d",ans);
    return 0;
}


新鲜事 原文

舞曲
8天前
终于死在搜索


活动打卡代码 AcWing 186. 巴士

舞曲
15天前

最多有17条线路,自然而然想到迭代加深,一开始思路是dfs里枚举两个点,然后方差,首项就出来了,但是这种包含了许多不合法的情况,而且写得太麻烦,然后就GG++了。
看了一下大佬的代码,预处理出所有合法的线路(这个真的妙),然后问题就转化成了选择i条线路覆盖所有点,然后再加上些许剪枝即可(我的剪枝真是辣鸡QAQ)。
原:

# include <iostream> 
# include <cstdio>
using namespace std;
int n;
int a[310],num[65],num2[65];
void dfs(int x,int y,int lim){
    /*if(lim==1){
        printf("%d\n",y);
    }*/
    if(x>lim) return ;
    if(y>n){
        printf("%d",lim);
        exit(0);
    }
    bool p=0;
    for(int i=y;i<=n;i++)
        if(num[a[i]]>0){
            p=1;
            break;
        }           
    if(!p){
        printf("%d",lim);
        exit(0);
    }
    if(num[a[y]]<=0) dfs(x,y+1,lim);
    num[a[y]]--;
    for(int i=a[y]+1;i<=59;i++){
        int flag2=0;
        if(num[i]<=0) continue;
        int e=i-a[y];
        for(int j=i;j<=59;j+=e){
            if(num[j]<=0){
                flag2=j;
                break;
            }
            else
                num[j]--;
        }       
        if(flag2!=0){
            for(int j=i;j<flag2;j+=e)
                num[j]++;
            continue;
        } 
        dfs(x+1,y+1,lim);
        for(int j=i;j<=59;j+=e)
            num[j]++;
    }
    num[a[y]]++;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),num[a[i]]++,num2[a[i]]=num[a[i]];
    for(int i=1;i<=16;i++){
        cout<<i<<endl;
        dfs(0,1,i);
        for(int i=0;i<=59;i++)
            num[i]=num2[i];
    }
    cout<<17;
    return 0;
}

ans:

# include <iostream>
# include <cstdio>
# include <algorithm>
using namespace std;
struct node{
    int l,d,num;
}rode[2100];
int n,cnt;
int a[310],qua[60];
bool cmp(node a,node b){
    return a.num>b.num;
}
bool check(int x,int y){
    for(int i=x;i<=59;i+=y)
        if(!qua[i])
            return 0;
    return 1;
} 
void dfs(int x,int sum,int sta,int lim){
    //printf("%d\n",sta);
    if(sum==n){
        printf("%d",lim);
        exit(0);
    }
    if(x>=lim) return ;
    if(sum+rode[sta].num*(lim-x)<n) return ;
    for(int i=sta;i<=cnt;i++){
        if(rode[i].num>n-x) continue;
        if(!check(rode[i].l,rode[i].d)) continue;
        for(int j=rode[i].l;j<=59;j+=rode[i].d)
            qua[j]--;
        dfs(x+1,sum+rode[i].num,i,lim);
        for(int j=rode[i].l;j<=59;j+=rode[i].d)
            qua[j]++;
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),qua[a[i]]++;
    for(int i=0;i<=58;i++)
        for(int j=i+1;i+j<=59;j++){
            if(check(i,j))
               rode[++cnt].l=i,rode[cnt].d=j,rode[cnt].num=(59-i)/j+1;
        }       
    sort(rode+1,rode+cnt+1,cmp);
/*  for(int i=1;i<=cnt;i++)
        if(rode[i].l==0)
            printf("%d %d %d\n",rode[i].l,rode[i].d,rode[i].num);*/
    for(int i=1;i<=16;i++)
        dfs(0,0,1,i);
    printf("17");
    return 0;
}


活动打卡代码 AcWing 190. 字串变换

舞曲
15天前

要仔细考虑情况。
洛谷单队列过不了这题,然后要用双向bfs,减半,然后写了好久,调了更久,具体看代码注释。
然后要学一下string库,如果有人以后看到,记得提醒我QAQ

# include <iostream>
# include <cstring>
# include <cstdio>
# include <queue>
# include <map>
using namespace std;
struct node{
    string s; 
    int x;
};
queue<node> q1,q2;
map<string,int> m1,m2,M1,M2;
string s0,s1;
string s[11],S[11];
int cnt=1,num=0;
int main(){
    cin>>s0>>s1;
    while(cin>>s[cnt]>>S[cnt]){
        ++cnt;
        if(cnt>6) break;
    }   
    q1.push((node){s0,0});
    q2.push((node){s1,0});
    M2[s1]=M1[s0]=0;
    m1[s0]=m2[s1]=1;
    while(!q1.empty()&&!q2.empty()){  //此处可以用&,因为如果出现合法情况,是一半一半的情况,如果是||那么就爆炸了。。 
        /*num++;
        if(num>10000)
            break;*/
        //if(!q1.empty()){
            node t=q1.front();q1.pop();
            string ss=t.s;
            //cout<<ss<<" "<<endl;
            //cout<<t.x<<" ";
            int l=ss.length();
            if(t.x>10){
                printf("NO ANSWER!");
                return 0;
            }   
            for(int i=1;i<cnt;i++)
                for(int j=0;j<l;j++){  // 不一定是替换第一次出现的 
                    string SS=ss;
                    int e=SS.find(s[i],j);
                    if(e>=0&&e<l){
                        string sss=SS.replace(e,s[i].length(),S[i]);
                        if(m2[sss]==1){
                            printf("%d",t.x+M2[sss]+1);
                            return 0;
                        }
                        if(m1[sss]!=1)
                            q1.push((node){sss,t.x+1}),m1[sss]=1,M1[sss]=t.x+1;
                    }       
                }
       // }
        //if(!q2.empty()){
            t=q2.front();q2.pop();
            ss=t.s; 
            //cout<<t.x<<endl;
            l=ss.length();
            if(t.x>10){
                printf("NO ANSWER!");
                return 0;
            }   
            for(int i=1;i<cnt;i++)
                for(int j=0;j<l;j++){  // 不一定是替换第一次出现的 
                    string SS=ss;
                    int e=SS.find(S[i],j);
                    if(e>=0&&e<l){
                        string sss=SS.replace(e,S[i].length(),s[i]);
                        if(m1[sss]==1){
                            printf("%d",t.x+M1[sss]+1);
                            return 0;
                        }
                        if(m2[sss]!=1)
                            q2.push((node){sss,t.x+1}),m2[sss]=1,M2[sss]=t.x+1;
                    }       
                }
        //}
    }   
    printf("NO ANSWER!");// 有可能找到一般找不下去了,但步数不超过10 
    return 0;
}


活动打卡代码 AcWing 189. 乳草的入侵

舞曲
16天前
bfs即可


活动打卡代码 AcWing 188. 武士风度的牛

舞曲
16天前
bfs即可