长乐 DAY2

今天做了两道题，一道贪心一道披着二分皮的dp

scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
    int l=1,r=500000000,mid,res,t,k;
    while(l>1;
        for(int i=1;imid && tm) break;
            k+=a[i];
        }
        if(t<=m) r=mid;
        else l=mid+1;
    } 
    printf("%d ",r);
    for(int i=1;ir) tot++;
        u[i]=tot;
    }
    for(int i=0;i<=n;i++) s[i]=1;
    for(int i=0;i<=m;i++)
    {
        for(int j=1;j<=n;j++) dp[j]=(s[j-1]-s[u[j]-1])%mod;
        s[0]=0;
        for(int j=1;j<=n;j++) s[j]=dp[j]+s[j-1];
        ans=(ans+dp[n])%mod;
    }
    printf("%d",ans);

#include<bits/stdc++.h>
using namespace std;
int n,m,k,a[100005],res,cnt,head[100005];
int h[100005],l[100005],q[100005],p[100005];
bool b[100005],c[100005];
int main()
{
    freopen("paint.in","r",stdin);
    freopen("paint.out","w",stdout);
    scanf("%d%d%d",&n,&m,&k);
    b[0]=1;
    for(int i=1;i<=k;i++) q[i]=m+1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[j+(i-1)*m]);
            if(a[j+(i-1)*m]==0) continue;
            if(!b[a[j+(i-1)*m]])
            {
                b[a[j+(i-1)*m]]=1;
                res++;
                head[res]=a[j+(i-1)*m];
            }
            if(!h[a[j+(i-1)*m]]) h[a[j+(i-1)*m]]=i;
            else l[a[j+(i-1)*m]]=i;
            q[a[j+(i-1)*m]]=min(q[a[j+(i-1)*m]],j);
            p[a[j+(i-1)*m]]=max(p[a[j+(i-1)*m]],j);
        }
    if(res==1) printf("%d",k-1);
    else
    {
        for(int i=1;i<=res;i++)
        {
            for(int j=h[head[i]];j<=l[head[i]];j++)
                for(int t=q[head[i]];t<=p[head[i]];t++)
                    if(a[(j-1)*m+t]!=head[i] && !c[a[(j-1)*m+t]]) c[a[(j-1)*m+t]]=1;
        }
        for(int i=1;i<=res;i++) if(c[head[i]]) cnt++;
        printf("%d",k-cnt);
    }
    return 0;
}