头像

棉花糖SR




离线:4天前


最近来访(15)
用户头像
flzj_kl
用户头像
Pipipapi
用户头像
lyktes
用户头像
狗头人挖土豆
用户头像
不care
用户头像
HimenoSena
用户头像
这个显卡不太冷
用户头像
ADMlN
用户头像
灰之魔女
用户头像
夏男人


题目链接 CodeForces E. Game with Stones

自己看了一下官方的标准题解,看懂了题目转化成了一个什么新问题,但是对于这个c数组的计数操作不会实现,看了一些标程好像和题解不太一样,完全不会了555.

有没有哪位路过的大佬好心讲讲实现思路和做法,谢谢~



活动打卡代码 AcWing 1072. 树的最长路径

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010,M = N << 1;
int e[M],h[N],w[M],idx=1,n,ans,ne[M];
void add(int a,int b,int c)
{
    e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}
int dfs(int x,int fa)
{
    int dis=0;
    int d0=0,d1=0;
    for(int i=h[x];i;i=ne[i])
    {
        int y=e[i],z=w[i];
        if(y==fa)continue;
        int t=dfs(y,x)+z;
        dis=max(dis,t);
        if(t>=d0)d1=d0,d0=t;
        else if(t>d1)d1=t;
    }
    ans=max(d0+d1,ans);
    return dis;
}
int main()
{
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);add(b,a,c);
    }
    dfs(1,-1);
    cout<<ans;
    return 0;
}


活动打卡代码 AcWing 321. 棋盘分割

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 9,M = 16;
const double INF=1e9;
double X;
int s[N][N],a[N][N];
double f[M][N][N][N][N];
double get(int x1,int y1,int x2,int y2)
{
    double sum=s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]-X;
    return sum*sum;
}
double dp(int n,int x1,int y1,int x2,int y2)
{
    double &t=f[n][x1][y1][x2][y2];
    if(t>=0)return t;
    if(n==1)return get(x1,y1,x2,y2);
    t=INF;
    for(int i=x1;i<x2;i++)
    {
        t=min(t,dp(n-1,x1,y1,i,y2)+get(i+1,y1,x2,y2));
        t=min(t,dp(n-1,i+1,y1,x2,y2)+get(x1,y1,i,y2));
    }
    for(int i=y1;i<y2;i++)
    {
        t=min(t,dp(n-1,x1,y1,x2,i)+get(x1,i+1,x2,y2));
        t=min(t,dp(n-1,x1,i+1,x2,y2)+get(x1,y1,x2,i));
    }
    return t;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=8;i++)
    for(int j=1;j<=8;j++)
    {
        cin>>a[i][j];
        s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
    }
    X=(double)s[8][8]/n;
    memset(f,-1,sizeof(f));
    printf("%.3lf\n",sqrt(dp(n,1,1,8,8)/n));
    return 0;
}


活动打卡代码 AcWing 479. 加分二叉树

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 40;
int n,w[N],f[N][N],pre[N][N];
void print(int x,int y)
{
    if(pre[x][y])
    cout<<pre[x][y]<<" ",print(x,pre[x][y]-1),print(pre[x][y]+1,y);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>w[i];
    for(int len=1;len<=n;len++)
    {
        for(int l=1;l+len-1<=n;l++)
        {
            int r=l+len-1;
            if(len==1)
            {
                f[l][r]=w[l];
                pre[l][r]=l;
                continue;
            }
            if(f[l+1][r]+w[l]>f[l][r])
            {
                pre[l][r]=l;
                f[l][r]=f[l+1][r]+w[l];
            }
            for(int k=l+1;k<r;k++)
            {
                if(f[l][k-1]*f[k+1][r]+w[k]>f[l][r])
                {
                    pre[l][r]=k;
                    f[l][r]=f[l][k-1]*f[k+1][r]+w[k];
                }
            }
            if(f[l][r-1]+w[r]>f[l][r])
            {
                pre[l][r]=r;
                f[l][r]=f[l][r-1]+w[r];
            }
        }
    }
    cout<<f[1][n]<<endl;
    print(1,n);
    return 0;
}



传统数组写法

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define ll long long
#define pb push_back
using namespace std;
const int N = 60,M = 35,INF = 0x3f3f3f3f;
ll f[N][N][M],w[N];
int n;

void add(ll a[],ll b[])
{
    static ll c[M];
    memset(c,0,sizeof(c));
    int t=0;
    for(int i=0;i<M;i++)
    {
        t+=a[i]+b[i];
        c[i]=t%10;
        t/=10;
    }
    memcpy(a,c,sizeof(c));
}
void mul(ll a[],ll b)
{
    static ll c[M];
    memset(c,0,sizeof(c));
    ll t=0;
    for(int i=0;i<M;i++)
    {
        t+=a[i]*b;
        c[i]=t%10;
        t/=10;
    }
    memcpy(a,c,sizeof(c));
}
int cmp(ll a[],ll b[])
{
    for(int i=M-1;i>=0;i--)
    if(a[i]>b[i])return 1;
    else if(a[i]<b[i])return -1;
    return 0;
}
void print(ll a[])
{
    int k=M-1;
    while((a[k]==0)&&k)k--;
    while(~k)cout<<a[k--];
    cout<<endl;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
    }
    for(int len=3;len<=n;len++)
    {
        ll temp[M];
        for(int l=1;l+len-1<=n;l++)
        {
            int r=l+len-1;
            f[l][r][M-1]=1;
            for(int k=l+1;k<r;k++)
            {
                memset(temp,0,sizeof(temp));
                temp[0]=w[l];
                mul(temp,w[r]);
                mul(temp,w[k]);
                add(temp,f[l][k]);
                add(temp,f[k][r]);
                if(cmp(f[l][r],temp)>0)
                memcpy(f[l][r],temp,sizeof(temp));             
            }
        }
    }
    print(f[1][n]);
    return 0;
}

vector写法(开了$O_2$优化还是废拉不堪)

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define ll long long 
#define pb push_back
using namespace std;
const int N=60;
vector<ll> f[N][N];
ll w[N];
int n;
vector<ll> add(vector<ll> &a,vector<ll> &b)
{
    vector<ll> c;
    ll t=0;
    for(int i=0;i<a.size()||i<b.size();i++)
    {
        if(i<a.size())t+=a[i];
        if(i<b.size())t+=b[i];
        c.pb(t%10);
        t/=10;
    }
    if(t)c.pb(t);
    return c;
}
vector<ll> mul(vector<ll> &a,ll b)
{
    vector<ll> c;
    ll t=0;
    for(int i=0;i<a.size()||t;i++)
    {
        if(i<a.size())t+=a[i]*b;
        c.pb(t%10);
        t/=10;
    }
    return c;
}
int cmp(vector<ll> &a,vector<ll> &b)
{
    if(a.size()>b.size())return 1;
    else if(a.size()<b.size())return -1;
    else
    {
        for(int i=a.size()-1;i>=0;i--)
        if(a[i]>b[i])return 1;
        else if(a[i]<b[i])return -1;
    }
    return 0;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
    }
    for(int len=3;len<=n;len++)
    {
        for(int l=1;l+len-1<=n;l++)
        {
            int r=l+len-1;
            for(int i=0;i<35;i++)f[l][r].pb(9);
            for(int k=l+1;k<r;k++)
            {
                vector<ll> temp;
                temp.pb(w[l]);
                temp=mul(temp,w[k]);
                temp=mul(temp,w[r]);
                temp=add(temp,f[l][k]);
                temp=add(temp,f[k][r]);
                if(cmp(f[l][r],temp)>0)f[l][r]=temp;
            }
        }
    }
    auto v=f[1][n];
    for(int i=v.size()-1;i>=0;i--)
    cout<<v[i];
    return 0;
}


活动打卡代码 AcWing 320. 能量项链

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 210;
int w[N],n,f[N][N];

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
        w[i+n]=w[i];
    }
    memset(f,-0x3f,sizeof(f));
    for(int len=1;len<=n;len++)
    {
        for(int l=1;l+len-1<=n*2;l++)
        {
            int r=l+len-1;
            if(len==1)f[l][r]=0;
            for(int k=l;k<=r;k++)
            f[l][r]=max(f[l][r],f[l][k]+f[k+1][r]+w[l]*w[k+1]*w[r+1]);
        }
    }
    int ans=-0x3f3f3f3f;
    for(int i=1;i+n-1<=n*2;i++)
    ans=max(ans,f[i][i+n-1]);
    cout<<ans<<endl;
}


活动打卡代码 AcWing 1068. 环形石子合并

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 410,INF = 0x3f3f3f3f;
int w[N],g[N][N],f[N][N],n;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>w[i],w[i+n]=w[i];
    for(int i=1;i<=(n<<1);i++)w[i]+=w[i-1];
    memset(f,0x3f,sizeof(f));
    memset(g,-0x3f,sizeof(g));
    for(int len=1;len<=n;len++)
    {
        for(int l=1;l+len-1<=2*n;l++)
        {
            int r=l+len-1;
            if(l==r)f[l][r]=g[l][r]=0;
            for(int k=l;k<=r;k++)
            {
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+w[r]-w[l-1]);
                g[l][r]=max(g[l][r],g[l][k]+g[k+1][r]+w[r]-w[l-1]);             
            }
        }
    }
    int maxn=-INF,minn= INF;
    for(int i=1;i+n-1<=n*2;i++)
    {
        maxn=max(maxn,g[i][i+n-1]);
        minn=min(minn,f[i][i+n-1]);
    }
    cout<<minn<<endl<<maxn<<endl;
}


活动打卡代码 AcWing 529. 宝藏

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define pb push_back
#pragma GCC optimize(2)
using namespace std;
const int N=13,M=1<<N,INF=0x3f3f3f3f;
int n,m;
int a[N][N],f[N][M];
int expand[M],road[M][N];
vector<int> cost[M],valid[M],sub[M];
void dfs(int st,int nst,int pos)
{
    if(pos==n)
    {
        sub[st].pb(nst);
        return;
    }
    dfs(st,nst,pos+1);
    if(st>>pos&1)
    dfs(st,nst|(1<<pos),pos+1);
}
void init()
{
    memset(road,0x3f,sizeof(road));
    for(int i=0;i<(1<<n);i++)
    {
        dfs(i,0,0);
        expand[i]=i;
        for(int j=1;j<=n;j++)
        {
            if(i>>(j-1)&1)
            {
                road[i][j]=0;
                for(int k=1;k<=n;k++)
                {
                    if(((i>>(k-1))&1)||a[j][k]==INF)continue;
                    expand[i]|=1<<(k-1);
                    road[i][k]=min(road[i][k],a[j][k]);
                }
            }
        }
    }
    for(int j=0;j<(1<<n);j++)
    {
        for(int k:sub[j])
        {
            if((j&k)==k&&(j&expand[k])==j)
            {
                valid[j].pb(k);
                int sum=0;
                for(int i=1;i<=n;i++)
                if((j>>(i-1)&1)&&!(k>>(i-1)&1))sum+=road[k][i];
                cost[j].pb(sum);
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    if(n==1)
    {
        cout<<0;
        return 0;
    }
    memset(a,0x3f,sizeof(a));
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        a[x][y]=a[y][x]=min(a[x][y],z);
    }
    init();
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;i++)f[1][1<<(i-1)]=0;
    int ans=INF;
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<(1<<n);j++)
        {
            for(int p=0;p<valid[j].size();p++)
            {
                int k=valid[j][p];
                f[i][j]=min(f[i][j],f[i-1][k]+(i-1)*cost[j][p]);
            }
        }
        ans=min(ans,f[i][(1<<n)-1]);
    }
    cout<<ans<<endl;
}


活动打卡代码 AcWing 524. 愤怒的小鸟

稍微注意一下精度问题(第42行)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#define x first
#define y second
#define pb push_back
#define pdd pair<double,double>
using namespace std;
const int N = 19,M=1<<N;
const double eps=1e-8;
int n,m,path[N][N],f[M];
pdd p[N];

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        for(int i=0;i<n;i++)
        {
            double x,y;
            cin>>x>>y;
            p[i]={x,y};
        }
        memset(path,0,sizeof(path));
        for(int i=0;i<n;i++)
        {
            path[i][i]=1<<i;
            for(int j=0;j<n;j++)
            {
                double x1=p[i].x,y1=p[i].y;
                double x2=p[j].x,y2=p[j].y;
                if(abs(x1-x2)<eps)continue;
                double a=(y1/x1-y2/x2)/(x1-x2);
                double b=y1/x1-a*x1;
                if(a>-eps)continue;
                for(int k=0;k<n;k++)
                {
                    double x3=p[k].x,y3=p[k].y;
                    if(abs(y3-x3*x3*a-b*x3)<eps)path[i][j]|=1<<k;
                }
            }
        }
        memset(f,0x3f,sizeof(f));
        f[0]=0;
        for(int i=0;i+1<(1<<n);i++)
        {
            int x;
            for(int j=0;j<n;j++)
            if(!(i>>j&1))
            {
                x=j;
                break;
            }
            for(int y=0;y<n;y++)
            f[i|path[x][y]]=min(f[i]+1,f[i|path[x][y]]);
        }
        cout<<f[(1<<n)-1]<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 292. 炮兵阵地

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define pb push_back
using namespace std;
const int N = 110,M = 1<<10;
int cnt[M],f[2][M][M],n,m,g[N];
vector<int> state;
bool check(int x)
{
    for(int i=0;i<m;i++)
    if((x>>i&1)&&((x>>i+1&1)||(x>>i+2&1)))return 0;
    return 1;
}
int count(int x)
{
    int ans=0;
    for(int i=0;i<m;i++)ans+=(x>>i&1);
    return ans;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        char c;
        cin>>c;
        g[i]=(g[i]<<1)|(c=='H');
    }
    for(int i=0;i<(1<<m);i++)
    {
        if(check(i))state.pb(i),cnt[i]=count(i);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<state.size();j++)
        for(int l=0;l<state.size();l++)
        for(int w=0;w<state.size();w++)
        {
            int c1=state[j],c2=state[w],c3=state[l];
            if((!(c1&c2))&&(!(c1&c3))&&(!(c2&c3)))
            if((!(g[i]&c1))&&(!(g[i-1]&c3)))
            f[i&1][j][l]=max(f[i&1][j][l],f[i-1&1][l][w]+cnt[c1]);
        }
    }
    int ans=0;
    for(int i=0;i<state.size();i++)
    for(int j=0;j<state.size();j++)
    ans=max(ans,f[n&1][i][j]);
    cout<<ans<<endl;
    return 0;
}