头像

山海皆可平

!ZAFU--




离线:8小时前


最近来访(178)
用户头像
沄逸
用户头像
Snowandraw.
用户头像
chqi
用户头像
zeng9999jian
用户头像
Rain丶bow
用户头像
共清欢
用户头像
AKA-Yi
用户头像
yxc
用户头像
BT7274
用户头像
一只小丑人
用户头像
OceanCjx
用户头像
Q_83
用户头像
KkkkkkkkkKK
用户头像
行人_6
用户头像
尒猫不秀
用户头像
AsincrdE
用户头像
青墨如许素淡如初
用户头像
clin123
用户头像
Eger
用户头像
Traveler03

活动打卡代码 AcWing 282. 石子合并

#include<bits/stdc++.h>
using namespace std;
const int N=310;
int f[N][N];
int a[N],s[N];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    } 
    for(int len=1;len<=n;len++){
        for(int i=1;i+len<=n;i++){
            int j=i+len;
            f[i][j]=1e8;
            for(int k=i;k+1<=j;k++){
                f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
            }
        }
    }
    cout<<f[1][n];
}



去题目中感悟吧

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int f[N][N];
int main(){
    int n,m;
    cin>>n>>m;
    string a,b;
    cin>>a>>b;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            f[i][j]=max(f[i-1][j],f[i][j-1]);
            if(a[i-1]==b[j-1]) f[i][j]=max(f[i][j],f[i-1][j-1]+1);       
        }
    }
    cout<<f[n][m];
}



#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int a[N],dp[N],res;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++){
        dp[i]=1;
        int m=0;
        for(int j=1;j<i;j++){
            if(a[i]>a[j])
                m=max(m,dp[j]);
        }
        dp[i]+=m;
    }
    for(int i=1;i<=n;i++) res=max(res,dp[i]);
    cout<<res<<endl;
}


活动打卡代码 AcWing 898. 数字三角形

注意边界问题

#include<bits/stdc++.h>
using namespace std;
const int N=510;
int a[N][N],f[N][N];
int res=-1e9;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            cin>>a[i][j];
    for(int i=1;i<=n;i++)
        for(int j=0;j<=n;j++)
            f[i][j]=-1e9;
    f[1][1]=a[1][1];
    for(int i=2;i<=n;i++)
        for(int j=1;j<=i;j++)
            f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j];
    for(int i=1;i<=n;i++)
        res=max(f[n][i],res);
    cout<<res;
}


分享 acwing周赛

谢谢周赛让我体验到了AK的快乐

虽然罚时爆炸



活动打卡代码 AcWing 1960. 闪烁

终于过了,这个循环节不一定是刚开始给你的那个值,所以要用map比较好

#include<bits/stdc++.h>
using namespace std;
long long mm;
long long q[30];
long long now,star,nn;
unordered_map<long long,int> qq;
void ans(long long x){
    long long j=0;
        while(x){
            cout<<(x&1)<<endl;
            x>>=1;
            j++;
        }
        while(j<nn){
            cout<<0<<endl;
            j++;
        }
}
int main(){
    long long n,t;bool stt=false;
    cin>>n>>t;
    nn=n;
    int p=1;
    while(n--){
        int x;
        cin>>x;
        if(x==1) now+=p;
        q[mm++]=p;
        p*=2;
    }
    mm=1;qq[now]=1;
    bool st;
    n=0;
    for(long long m=0;m<t;m++){
        long long x=now,i=1,kk=now;
        while(x){
            if(x&1) st=true;
            else st=false;
            x>>=1;
            if(st)
            if(x){
                if(x&1) now-=q[i];
                else now+=q[i]; 
            }else if(i==nn){
                if(kk&1) now--;
                else now++;
            }else now+=q[i];
            i++;
        }
        // cout<<now<<' '<<star<<endl;
        if(qq[now]){ t-=m+1;stt=true;
        break;}
        qq[now]=1;
        mm++;

        // ans(now);cout<<endl;
    }   
    if(stt){
        t%=mm;n=0;
        // cout<<mm<<endl;
        for(int j=1;j<=t;j++){
            int x=now,i=1;
            while(x){
                if(x&1) st=true;
                else st=false;
                x>>=1;
                if(st)
                if(x){
                    if(x&1) now-=q[i];
                    else now+=q[i]; 
                }else if(i==nn){
                    if(now&1) now--;
                    else now++;
                }else now+=q[i];
                i++;
            }
        }
    }
    // cout<<now<<endl;
     ans(now);
}


活动打卡代码 AcWing 1987. 粉刷栅栏

写的时候发现会因为一些边界问题被同一方向的多次输入给卡掉,所以我改了一下输入。也算是顺利的过掉了。
这里也是用的差分。(这里还是比较明显的)

#include<bits/stdc++.h>
using namespace std;
const long long N=1e9;
const int M=1e5+10;
long long now,sum,res;
map<long long,int> q;
int x[M];
string s[M];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>s[i];
    }
    for(int i=1;i<=n;i++){
        if(s[i][0]=='R'){
            int xx=0;
            int j=i;
            while(j<=n&&s[j][0]=='R'){
                xx+=x[j];
                j++;
            }
            if(j!=i) i=j-1;
            q[now+N]+=1;
            now+=xx;
            q[now+1+N]-=1;
        }else{
            int xx=0;
            int j=i;
            while(j<=n&&s[j][0]=='L'){
                xx+=x[j];
                j++;
            }
            if(j!=i) i=j-1;
            q[now+1+N]-=1;
            now-=xx;
            q[now+N]+=1;
        }
    }
    long long k;
    bool st=false;
    int i=0;
    for(auto t:q){
        sum+=t.second;
        if(sum>=2&&!st){
            st=true;
            k=t.first;
        }else if(sum<2&&st){
            st=false;
            res+=t.first-1-k;
        }
    }
    cout<<res;
}


分享 i&j

if(i&j) continue;

如果i和j的二进制位上有一个已经被被用过了就不能再用了,比较适合数据小的枚举

利用二进制的特殊性来代替dfs枚举




这个和那个岛是一样的想法和用法,这一种方法还是要学习一下的

#include<bits/stdc++.h>
using namespace std;
map<int,int> q;
int res,sum;
int main(){
    int n,x,y,z;
    cin>>n>>x>>y>>z;
    while(n--){
        int a,b;
        cin>>a>>b;
        q[0]+=x;q[a]-=x;q[a]+=y;q[b+1]-=y;q[b+1]+=z;
    }
    for(auto item:q){
        sum+=item.second;
        res=max(res,sum);
    }
    cout<<res<<endl;
}


活动打卡代码 AcWing 2005. 马蹄铁

小小dfs

#include<bits/stdc++.h>
using namespace std;
char f[10][10];
bool st[10][10];
int n,res;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
void dfs(int x,int y,int u,int k,int kk){
    if(u==0&&k==1){
        res=max(res,kk);
        return;
    }
    for(int i=0;i<4;i++){
        int a=x+dx[i],b=y+dy[i];
        if(st[a][b]||a<1||b<1||a>n||b>n) continue;
        if(!k){
            if(f[a][b]=='('){
                st[a][b]=true;
                dfs(a,b,u+1,0,kk);
                st[a][b]=false;
            }else if(f[a][b]==')'){
                st[a][b]=true;
                dfs(a,b,u-1,1,2*u);
                st[a][b]=false;
            }
        }else{
            if(f[a][b]==')'){
                st[a][b]=true;
                dfs(a,b,u-1,1,kk);
                st[a][b]=false;
            }
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>f[i][j];
    if(f[1][1]=='('){
        st[1][1]=true;
        dfs(1,1,1,0,0);
    }
    cout<<res<<endl;
}