头像

Koan




离线:1小时前


最近来访(50)
用户头像
string-s
用户头像
結城友奈
用户头像
那天月下等你
用户头像
努力搞技术111222
用户头像
自律
用户头像
Peter_5
用户头像
VegeDog
用户头像
实干者
用户头像
一只奇怪的小魔女
用户头像
陈信长
用户头像
ZNbreeze
用户头像
白洲アズサ
用户头像
RyanMoriarty
用户头像
M_L_Q_F
用户头像
Feilong
用户头像
妮可_4
用户头像
BigJoker
用户头像
zzzzch
用户头像
L_H_R
用户头像
hlydxxz

活动打卡代码 AcWing 273. 分级

Koan
2小时前

$状态定义:f[i][j]:匹配到a[i]且以b[j]为结尾的所有方案的集合$

$属性:最小值$

$状态转移方程:f_{i,j} = min(f_{i,j},f_{i-1,k})+\lvert a_{i}-b_{j}\rvert ,k\in[1,j]$

一个重要的性质:b[1-n]出现的所有数字一定出现在a中

优化方式:类似最长公共上升子序列,用一个前缀和,但是这里是$[1,j]$的所以在每次当前层更新

而上升子序列那题是$[1,j-1]$ 所以在这层之前更新

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

const int N=2010;

int n;
int a[N],b[N];
int f[N][N];

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(b+1,b+1+n);

    int res=0x3f3f3f3f;
    for(int i=1;i<=n;i++){
        int minv=0x3f3f3f3f;
        for(int j=1;j<=n;j++){
            minv=min(minv,f[i-1][j]);
            f[i][j]=minv+abs(a[i]-b[j]);
        }
    }
    for(int i=1;i<=n;i++) res=min(res,f[n][i]);

    reverse(b+1,b+1+n);
    for(int i=1;i<=n;i++){
        int minv=0x3f3f3f3f;
        for(int j=1;j<=n;j++){
            minv=min(minv,f[i-1][j]);
            f[i][j]=minv+abs(a[i]-b[j]);
        }
    }
    for(int i=1;i<=n;i++) res=min(res,f[n][i]);
    cout<<res<<endl;
    return 0;
}



Koan
3小时前

参考提高课

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int N=3010;

int n;
int a[N],b[N];
int f[N][N];

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];

    for(int i=1;i<=n;i++){
        int maxv=1;
        for(int j=1;j<=n;j++){
            f[i][j]=f[i-1][j];
            if(a[i]==b[j]) f[i][j]=max(f[i][j],maxv);
            if(b[j]<a[i]) maxv=max(maxv,f[i-1][j]+1);
        }
    }
    int res=0;
    for(int i=1;i<=n;i++) res=max(res,f[n][i]);
    cout<<res<<endl;
    return 0;
}



Koan
3小时前
#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int N=31;
typedef long long ll;

int n;
int k[N];
ll f[N][N][N][N][N];

int main()
{
    while(cin>>n,n){
        memset(f,0,sizeof f);
        memset(k,0,sizeof k);
        for(int i=1;i<=n;i++) cin>>k[i];

        f[0][0][0][0][0]=1;
        for(int i1=0;i1<=k[1];i1++)
            for(int i2=0;i2<=k[2]&&i2<=i1;i2++)
                for(int i3=0;i3<=k[3]&&i3<=i2;i3++)
                    for(int i4=0;i4<=k[4]&&i4<=i3;i4++)
                        for(int i5=0;i5<=k[5]&&i5<=i4;i5++){
                            ll &x=f[i1][i2][i3][i4][i5];
                            if(i1) x+=f[i1-1][i2][i3][i4][i5];
                            if(i2) x+=f[i1][i2-1][i3][i4][i5];
                            if(i3) x+=f[i1][i2][i3-1][i4][i5];
                            if(i4) x+=f[i1][i2][i3][i4-1][i5];
                            if(i5) x+=f[i1][i2][i3][i4][i5-1];
                        }
        cout<<f[k[1]][k[2]][k[3]][k[4]][k[5]]<<endl;

    }
    return 0;
}


活动打卡代码 AcWing 1929. 镜子田地

Koan
8小时前
#include<iostream>
#include<cstdio>
#include<vector>

using namespace std;

const int N=1010;
//0从上来 1从下来 2从左来 3从右来
int n,m;
char h[N][N];

int dfs(int cnt,int x,int y,int v)
{
    if(x<0||x>=n||y<0||y>=m) return cnt;
    char c=h[x][y];
    if(c=='/'){
        if(v==0) return dfs(cnt+1,x,y-1,3);
        if(v==1) return dfs(cnt+1,x,y+1,2);
        if(v==2) return dfs(cnt+1,x-1,y,1);
        if(v==3) return dfs(cnt+1,x+1,y,0);
    }
    if(c=='\\'){
        if(v==0) return dfs(cnt+1,x,y+1,2);
        if(v==1) return dfs(cnt+1,x,y-1,3);
        if(v==2) return dfs(cnt+1,x+1,y,0);
        if(v==3) return dfs(cnt+1,x-1,y,1);
    }
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++) scanf("%s",h[i]);

    int ans=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            int res=0;
            if(i==0) res=max(res,dfs(0,i,j,0));
            if(j==0) res=max(res,dfs(0,i,j,2));
            if(j==m-1) res=max(res,dfs(0,i,j,3));
            if(i==n-1) res=max(res,dfs(0,i,j,1));
            ans=max(ans,res);
        }
    cout<<ans<<endl;
    return 0;
}


活动打卡代码 AcWing 1934. 贝茜放慢脚步

Koan
21小时前

还有这种题,长见识

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

typedef pair<int,char> pic;
const int N=10010;

int n;
vector<int> t,d;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        char a;int b;
        cin>>a>>b;
        if(a=='T') t.push_back(b);
        else d.push_back(b);
    }
    sort(t.begin(),t.end());
    sort(d.begin(),d.end());

    double time=0;
    double dist=0;
    double v=1;

    int l=0,r=0;
    while(l<d.size()&&r<t.size()){
        double t_dist=(t[r]-time)/v;
        double d_time=(d[l]-dist)*v;

        if(t_dist<(double)d[l]-dist){//时间点在距离点前
            time=t[r];
            v++;
            dist+=t_dist;
            r++;
        }else if(t_dist>(double)d[l]-dist){
            dist=d[l];
            v++;
            time+=d_time;
            l++;
        }else{
            time=t[r];
            dist=d[l];
            v+=2;
            l++,r++;
        }
    }
    while(l<d.size()){
        double a=d[l]-dist;
        time+=a*v;
        dist=d[l];
        v+=1;
        l++;
    }
    while(r<t.size()){
        double a=t[r]-time;
        time=t[r];
        dist+=a/v;
        v+=1;
        r++;
    }
    printf("%.0f\n",time+(1000.0-dist)*v);

    return 0;
}



Koan
2天前

复习的时候想了想这个题的状态划分是不是还是要考虑多一点,当时做的时候没想过为什么状态转移方程只对最后一个操作,现在想想应该这么划分

集合定义:$ f[i][j] $ : 使得 $ a[ 1-i]$和$b[1-j]$相同的操作

集合属性:操作数的最小值

1.png

所以最后发现就是对最后一个操作,对前面操作结果已经被覆盖在前面了,所以好像没啥卵用

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std; 

const int N=1010;

int n,m;
char a[N],b[N];
int f[N][N];

int main()
{
    cin>>n>>a+1;
    cin>>m>>b+1;

    for(int i=1;i<=m;i++) f[0][i]=i;
    for(int i=1;i<=n;i++) f[i][0]=i;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            f[i][j]=min(f[i-1][j],f[i][j-1])+1;
            if(a[i]==b[j]) f[i][j]=min(f[i][j],f[i-1][j-1]);
            else f[i][j]=min(f[i][j],f[i-1][j-1]+1);
        }
    cout<<f[n][m]<<endl;
    return 0;

}


活动打卡代码 AcWing 1945. 奶牛棒球

Koan
2天前

$ O(n^2log(n)) $

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

const int N=1010;

int n,a[N];

int findl(int x,int l,int r)
{
    while(l<r){
        int mid=l+r>>1;
        if(a[mid]>=x) r=mid;
        else l=mid+1;
    }
    return l;
}

int findr(int x,int l,int r)
{
    while(l<r){
        int mid=l+r+1>>1;
        if(a[mid]<=x) l=mid;
        else r=mid-1;
    }
    return l;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n);
    a[n+1]=0x3f3f3f3f;
    int res=0;
    for(int i=1;i<=n-2;i++)
        for(int j=i+1;j<=n-1;j++){
            int left=2*a[j]-a[i];
            int right=3*a[j]-2*a[i];

            int l=findl(left,j,n+1),r=findr(right,j,n+1);
            if(l==n+1||r==n+1) continue;
            res+=r-l+1;
        }
    cout<<res<<endl;
    return 0;
}



Koan
3天前
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

const int N=20010;
typedef pair<int,int> pii;

int n,x,y,z;
vector<int> place;
pii p[N];
int b[N*3];

int main()
{
    cin>>n>>x>>y>>z;
    for(int i=1;i<=n;i++){
        int l,r;scanf("%d%d",&l,&r);
        p[i]={l,r};
        place.push_back(l),place.push_back(r);
    }
    sort(place.begin(),place.end());
    place.erase(unique(place.begin(),place.end()),place.end());

    for(int i=1;i<=n;i++){
        int l=p[i].first,r=p[i].second;
        l=lower_bound(place.begin(),place.end(),l)-place.begin()+1;
        r=lower_bound(place.begin(),place.end(),r)-place.begin()+1;
        b[l]+=y,b[r+1]-=y;
        b[1]+=x,b[l]-=x;
        b[r+1]+=z;
    }
    int res=0;
    for(int i=1;i<=place.size();i++){
        b[i]+=b[i-1];
        res=max(res,b[i]);
    }
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 1960. 闪烁

Koan
4天前

一眼偷sjj

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<map>
using namespace std;

const int N=20;
typedef long long ll;

int n;
ll m;
vector<int> a;
map<vector<int>,ll> mp;

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        a.push_back(x);
    }

    for(ll i=1;i<=m;i++){
        vector<int> t=a;
        for(int j=0;j<n;j++)
            if(a[j]) t[(j+1)%n]=1-a[(j+1)%n];
        a=t;
        if(!mp.count(t)){
            mp[t]=i;
            continue;
        }
        ll dist=i-mp[t];
        ll k=(m-i)/dist*dist;
        i+=k;
    }
    for(auto i:a) cout<<i<<endl;
    return 0;
}


活动打卡代码 AcWing 1969. 品种邻近

Koan
6天前
#include<iostream>
#include<cstdio>

using namespace std;

const int N=50010,M=1e6+10;

int n,k,a[N];

int st[M];

int main()
{
    cin>>n>>k;
    k++;//区间长度
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);

    int res=0;

    for(int r=1;r<=n;r++){
        if(r>k) st[a[r-k]]--;
        st[a[r]]++;
        if(st[a[r]]>=2) res=max(res,a[r]);
    }
    cout<<res<<endl;
    return 0;
}