头像

wkj

$\mathtt{O(1)}$




离线:9天前


最近来访(2)
用户头像
AcKing_HIT
用户头像
rhyyy


wkj
1个月前
#include<bits/stdc++.h>
using namespace std;
int a[105][105];
int n,m;
int main()
{
    scanf("%d%d",&n,&m);
    memset(a,0x3f,sizeof a);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        a[x][y]=a[y][x]=1;
    }
    for(int k=1;k<=n;k++)
      for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
          a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
    int ans=0;
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
        if(a[i][j]!=0x3f3f3f3f)ans=max(ans,a[i][j]);
    printf("%d\n",ans);
    return 0;
}


活动打卡代码 AcWing 322. 消木块

wkj
2个月前
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
int a[205],len[205];
int b[205];
int f[205][205][205];
int tot;
int T;
int dfs(int l,int r,int same)
{
    if(l>r)return 0;
    if(f[l][r][same])return f[l][r][same];
    f[l][r][same]=dfs(l,r-1,0)+(same+len[r])*(same+len[r]);
    for(int k=l;k<r;k++)if(b[r]==b[k])f[l][r][same]=max(f[l][r][same],dfs(l,k,same+len[r])+dfs(k+1,r-1,0));
    return f[l][r][same];
}
int main()
{
    scanf("%d",&T);
    for(int p=1;p<=T;p++)
    {
        memset(f,0,sizeof f);
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
          scanf("%d",&a[i]);
        tot=0;
        for(int i=1;i<=n;i++)
        {
            int j=i;
            int cnt=1;
            while(a[j]==a[j+1]&&j<=n)j++,cnt++;
            i=j;
            b[++tot]=a[j],len[tot]=cnt;
        }
        //for(int i=1;i<=tot;i++)printf("%d %d\n",b[i],len[i]);
        printf("Case %d: %d",p,dfs(1,tot,0));
        if(p!=T)puts("");
    }
    return 0;
}


活动打卡代码 AcWing 302. 任务安排3

wkj
2个月前
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,s;
int t[300005],c[300005];
double sumt[300003],sumc[300005],f[300005];
int q[300005];
int le=1,ri=0;
int pd(int i,int x,int y)
{
    return f[x]-f[y]<=(s+sumt[i])*(sumc[x]-sumc[y]);
}
int pd2(int i,int x,int y)
{
    return (f[x]-f[y])*(sumc[i]-sumc[x])>=(f[i]-f[x])*(sumc[x]-sumc[y]);
}
int search(int x)
{
    if(le==ri)return q[le];
    int l=le,r=ri;
    int ans=-1;
    while(l<=r)
    {
        int mid=l+r>>1;
        if(f[q[mid+1]]-f[q[mid]]<=x*(sumc[q[mid+1]]-sumc[q[mid]]))l=mid+1;
        else r=mid-1,ans=mid;
    }
    return q[ans];
}
int main()
{
    scanf("%d%d",&n,&s);
    for(int i=1;i<=n;i++)scanf("%d%d",&t[i],&c[i]);
    for(int i=1;i<=n;i++)sumt[i]=sumt[i-1]+t[i],sumc[i]=sumc[i-1]+c[i];
    memset(f,0x3f,sizeof f);
    f[0]=0;
    q[++ri]=0;
    for(int i=1;i<=n;i++)
    {
        int j=search(s+sumt[i]);
        f[i]=f[j]-(s+sumt[i])*sumc[j]+sumt[i]*sumc[i]+s*sumc[n];
        while(le<ri&&pd2(i,q[ri],q[ri-1]))ri--;
        q[++ri]=i;
    }
    printf("%.0lf\n",f[n]);
}


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

wkj
3个月前
#include<bits/stdc++.h>
using namespace std;
int n;
int a[105];
struct node{
    int l,r;
}b[205];
int f[205][205];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i].l=a[i],b[i-1].r=a[i];
    b[n].r=a[1];
    for(int i=n+1;i<=n*2;i++)b[i]=b[i-n];
    for(int len=2;len<=n;len++)
      for(int l=1;l<=n*2-len+1;l++){
         int r=l+len-1;
         for(int k=l;k<r;k++)
           f[l][r]=max(f[l][r],f[l][k]+f[k+1][r]+b[l].l*b[k].r*b[r].r);
      }
    int ans=0;
    for(int i=1;i<=n;i++)ans=max(ans,f[i][i+n-1]);
    printf("%d\n",ans);
    return 0;
}


活动打卡代码 AcWing 312. 乌龟棋

wkj
3个月前
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[400];
int card[5];
int f[45][45][45][45];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)
    {
        int x;
        scanf("%d",&x);
        card[x]++;
    }
    f[0][0][0][0]=a[1];
    for(int i=0;i<=card[1];i++)
      for(int j=0;j<=card[2];j++)
        for(int p=0;p<=card[3];p++)
          for(int k=0;k<=card[4];k++)
          {
            if(i==0&&j==0&&p==0&&k==0)continue;
            if(i!=0)f[i][j][p][k]=max(f[i][j][p][k],f[i-1][j][p][k]+a[i+j*2+p*3+k*4+1]);
            if(j!=0)f[i][j][p][k]=max(f[i][j][p][k],f[i][j-1][p][k]+a[i+j*2+p*3+k*4+1]);
            if(p!=0)f[i][j][p][k]=max(f[i][j][p][k],f[i][j][p-1][k]+a[i+j*2+p*3+k*4+1]);
            if(k!=0)f[i][j][p][k]=max(f[i][j][p][k],f[i][j][p][k-1]+a[i+j*2+p*3+k*4+1]);
          }
    printf("%d\n",f[card[1]][card[2]][card[3]][card[4]]);
    return 0;
}


活动打卡代码 AcWing 314. 低买

wkj
3个月前
#include<bits/stdc++.h>
using namespace std;
int n;
int a[5005];
int f[5005];
int cnt[5005];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        f[i]=1;
        for(int j=1;j<i;j++)
          if(a[j]>a[i])f[i]=max(f[i],f[j]+1);
        if(f[i]==1)cnt[i]=1;
        for(int j=1;j<i;j++)
        {
            if(a[j]==a[i]&&f[i]==f[j])cnt[j]=0;
            else if(a[j]>a[i]&&f[i]==f[j]+1)cnt[i]+=cnt[j];
        }
        //if(cnt[i]==0)cnt[i]=1;
    }
    int ans1=0;
    int ans2=0;
    for(int i=1;i<=n;i++)ans1=max(ans1,f[i]);
    for(int i=1;i<=n;i++)if(ans1==f[i])ans2+=cnt[i];
    printf("%d %d\n",ans1,ans2);
    return 0;
}


活动打卡代码 AcWing 286. 选课

wkj
3个月前
#include<bits/stdc++.h>
using namespace std;
int n,m;
int p[305];
int f[305][305];
vector<int> son[305];
void dp(int x)
{
    f[x][0]=0;
    for(int i=0;i<son[x].size();i++)
    {
        int y=son[x][i];
        dp(y);
        for(int t=m;t>=0;t--)
          for(int j=t;j>=0;j--)
            if(t-j>=0)f[x][t]=max(f[x][t],f[x][t-j]+f[y][j]);
    }
    if(x)for(int t=m;t;t--)f[x][t]=f[x][t-1]+p[x];
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d%d",&x,&p[i]);
        son[x].push_back(i);
    }
    dp(0);
    int ans=0;
    for(int i=1;i<=m;i++)ans=max(f[0][i],ans);
    printf("%d\n",ans);
    return 0;
} 



wkj
3个月前
#include<bits/stdc++.h>
using namespace std;
int n;
int h[6005],f[6005][2];
vector<int> son[10010];
int fa[6005];
void dp(int x)
{
    f[x][1]=h[x];
    for(int i=0;i<son[x].size();i++)
    {
        int y=son[x][i];
        dp(y);
        f[x][0]+=max(f[y][1],f[y][0]);
        f[x][1]+=f[y][0];
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&h[i]);
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        fa[x]=1;
        son[y].push_back(x);
    }
    int root;
    for(int i=1;i<=n;i++)if(fa[i]==0){
        root=i;
        break;
    }
    dp(root);
    printf("%d\n",max(f[root][1],f[root][0]));
    return 0;
} 


活动打卡代码 AcWing 251. 小Z的袜子

wkj
3个月前
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node{
    int l,r,id;
}b[50005];
bool cmp1(node x,node y)
{
    return x.l<y.l;
}
bool cmp2(node x,node y)
{
    return x.r<y.r;
}
ll gcd(ll x,ll y)
{
    if(y==0)return x;
    return gcd(y,x%y);
}
int n,m;
int a[50005];
int L[50005],R[50005];
ll ans1[50005],ans2[50005];
int num[50005];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)scanf("%d%d",&b[i].l,&b[i].r),b[i].id=i;
    sort(b+1,b+m+1,cmp1);
    int T=sqrt(m);
    int Lo=sqrt(m);
    for(int i=1;i<=T;i++){
        L[i]=(i-1)*Lo+1;
        R[i]=i*Lo;
    }
    if(R[T]<m)L[T+1]=R[T]+1,R[++T]=m;
    for(int i=1;i<=T;i++)
        sort(b+L[i],b+R[i]+1,cmp2);
    for(int i=1;i<=T;i++)
    {
        ll ans=0;
        memset(num,0,sizeof num);
        for(int j=b[L[i]].l;j<=b[L[i]].r;j++)
          num[a[j]]++;
        for(int j=1;j<=n;j++)ans+=(ll)num[j]*(num[j]-1);
        if(ans==0||b[L[i]].l==b[L[i]].r)ans1[b[L[i]].id]=0,ans2[b[L[i]].id]=1;
        else{
            ll p=(ll)(b[L[i]].r-b[L[i]].l+1)*(b[L[i]].r-b[L[i]].l);
            ans1[b[L[i]].id]=ans/gcd(ans,p);
            ans2[b[L[i]].id]=p/gcd(ans,p);
        }
        int l=b[L[i]].l,r=b[L[i]].r;
        for(int j=L[i]+1;j<=R[i];j++)
        {
            if(b[j].l<l)
              for(int q=b[j].l;q<l;q++)
                ans-=(ll)num[a[q]]*(num[a[q]]-1),num[a[q]]+=1,ans+=(ll)num[a[q]]*(num[a[q]]-1);
            else if(b[j].l>l)
              for(int q=l;q<b[j].l;q++)
                ans-=(ll)num[a[q]]*(num[a[q]]-1),num[a[q]]-=1,ans+=(ll)num[a[q]]*(num[a[q]]-1);
            if(b[j].r<r)
              for(int q=b[j].r+1;q<=r;q++)
                ans-=(ll)num[a[q]]*(num[a[q]]-1),num[a[q]]-=1,ans+=(ll)num[a[q]]*(num[a[q]]-1);
            else if(b[j].r>r)
              for(int q=r+1;q<=b[j].r;q++)
                ans-=(ll)num[a[q]]*(num[a[q]]-1),num[a[q]]+=1,ans+=(ll)num[a[q]]*(num[a[q]]-1);
            l=b[j].l,r=b[j].r;
            //if(l==3&&r==4)printf("%d %d\n",j,R[i]);
            if(ans==0||r==l)ans1[b[j].id]=0,ans2[b[j].id]=1;
            else{
                ll o=(ll)(r-l+1)*(r-l);
                //printf("%d %d\n",ans,o);
                ans1[b[j].id]=ans/gcd(ans,o);
                ans2[b[j].id]=o/gcd(ans,o);
            }
        }
    }
    for(int i=1;i<=m;i++)printf("%lld/%lld\n",ans1[i],ans2[i]);
    return 0;
}


活动打卡代码 AcWing 250. 磁力块

wkj
3个月前
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
struct node{
    int x,y,m,p,r;
}Fe[250005];
struct node2{
    int p,r;
};
node2 MKN(int p,int r)
{
    node2 q;
    q.p=p,q.r=r;
    return q;
}
bool cmp1(node x,node y)
{
    return x.m<y.m;
}
int xx,yy,pL,rL;
queue<node2> q;
int st[250005];
int L[250005],R[250005];
int pos[250005];
int vis[250005];
int maxn[250005];
bool cmp2(node x,node y)
{
    return (ll)(x.x-xx)*(x.x-xx)+(ll)(x.y-yy)*(x.y-yy)<(ll)(y.x-xx)*(y.x-xx)+(ll)(y.y-yy)*(y.y-yy);
}
int main()
{
    scanf("%d%d%d%d%d",&xx,&yy,&pL,&rL,&n);
    for(int i=1;i<=n;i++)scanf("%d%d%d%d%d",&Fe[i].x,&Fe[i].y,&Fe[i].m,&Fe[i].p,&Fe[i].r);
    sort(Fe+1,Fe+n+1,cmp1);
    int T=sqrt(n),LT=sqrt(n);
    for(int i=1;i<=n/T;i++)
      L[i]=(i-1)*LT+1,R[i]=i*LT;
    if(R[T]<n)T++,L[T]=R[T-1]+1,R[T]=n;
    for(int i=1;i<=T;i++)
    {
        maxn[i]=Fe[R[i]].m;
        sort(Fe+L[i],Fe+R[i]+1,cmp2);
        for(int j=L[i];j<=R[i];j++)pos[j]=i;
        st[i]=L[i];
    }
    q.push(MKN(pL,rL));
    int ans=0;
    while(q.size())
    {
        node2 x=q.front();
        q.pop();
        for(int i=1;i<=T;i++)
        {
            if(x.p<maxn[i])
            {
                for(int j=L[i];j<=R[i];j++)
                {
                    if(vis[j]==0&&x.p>=Fe[j].m&&(ll)x.r*x.r>=(ll)(Fe[j].x-xx)*(Fe[j].x-xx)+(ll)(Fe[j].y-yy)*(Fe[j].y-yy))q.push(MKN(Fe[j].p,Fe[j].r)),ans++,vis[j]=1;
                }
                break;
            }
            for(int j=st[i];j<=R[i];j++)
            {
                if(vis[j]==0&&(ll)x.r*x.r>=(ll)(Fe[j].x-xx)*(Fe[j].x-xx)+(ll)(Fe[j].y-yy)*(Fe[j].y-yy))q.push(MKN(Fe[j].p,Fe[j].r)),ans++,vis[j]=1;
                else if((ll)x.r*x.r<(ll)(Fe[j].x-xx)*(Fe[j].x-xx)+(ll)(Fe[j].y-yy)*(Fe[j].y-yy)){
                    st[i]=j;
                    break;
                }
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}