2017北京国庆刷题Day7 afternoon

期望得分：100+30+100=230

实际得分：60+30+100=190

排序去重

固定右端点，左端点单调不减

考场上用了二分，没去重，60

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 100001
void read(int &x)
{
    x=0;char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
}
struct node
{
    int a,b;
    bool operator < (node q) const
    {
        if(a!=q.a) return a<q.a; return b<q.b;
    }
    bool operator == (node p) const
    {
        return a==p.a && b==p.b;
    }
}e[N];
int main()
{
    freopen("card.in","r",stdin);
    freopen("card.out","w",stdout);
    int n;
    read(n);
    for(int i=1;i<=n;i++) read(e[i].a),read(e[i].b);
    sort(e+1,e+n+1);
    int tot=unique(e+1,e+n+1)-e-1;
    int l,last,mx=0;
    for(l=1;l<=tot;l++)
    {
        if(e[l].a!=e[l-1].a) last=l;
        while(e[l].b-e[last].b+1>n) last++;
        mx=max(mx,l-last+1);
    }
    printf("%d
",n-mx);
}

View Code

因为对于n个二进制位，要么属于s不属于i，要么属于s属于i，要么不属于s

#include<cstdio> #include<iostream> #define N 100001 using namespace std; void read(int &x) { x=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } } int pos[N]; int main() { freopen("test.in","r",stdin); freopen("test.out","w",stdout); int n,a,b,ans; read(n); for(int i=1;i<=n;i++) { ans=0; read(a); read(b); for(int j=a;j;j=(j-1)&a) { if(pos[j]<i-b) ans++; pos[j]=i; } printf("%d ",ans); } }

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define N 500001 using namespace std; int n,m,S; int val[N]; int front[N],to[N],nxt[N],tot,from[N]; int dfn[N],low[N],st[N],top; bool ins[N]; int id[N],cnt,sum[N]; int nxt2[N],front2[N],to2[N],tot2; int q[N]; int in[N],dp[N]; void read(int &x) { x=0;char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } } void add(int u,int v) { if(u==v) return; for(int i=front[u];i;i=nxt[i]) if(to[i]==v) continue; to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; from[tot]=u; } void init() { read(n);read(m); int u,v; for(int i=1;i<=m;i++) { read(u); read(v); add(u,v); } for(int i=1;i<=n;i++) read(val[i]); read(S); } void tarjan(int x) { dfn[x]=low[x]=++tot; st[++top]=x; ins[x]=true; for(int i=front[x];i;i=nxt[i]) if(!dfn[to[i]]) tarjan(to[i]),low[x]=min(low[x],low[to[i]]); else if(ins[to[i]]) low[x]=min(low[x],dfn[to[i]]); if(low[x]==dfn[x]) { id[x]=++cnt; sum[cnt]+=val[x]; while(top && st[top]!=x) { id[st[top]]=cnt; sum[cnt]+=val[st[top]]; ins[st[top--]]=false; } ins[st[top--]]=false; } } void add2(int u,int v) { to2[++tot2]=v; nxt2[tot2]=front2[u]; front2[u]=tot2; in[v]++; } void rebuild() { for(int i=1;i<=m;i++) if(id[from[i]]!=id[to[i]]) add2(id[from[i]],id[to[i]]); } void pre() { memset(ins,false,sizeof(ins)); int h=0,t=1; q[++h]=id[S]; ins[id[S]]=true; int now; while(h<=t) { now=q[h++]; for(int i=front2[now];i;i=nxt2[i]) if(!ins[to2[i]]) ins[to2[i]]=true,q[++t]=to2[i]; } for(int i=1;i<=cnt;i++) if(!ins[i]) for(int j=front2[i];j;j=nxt2[j]) in[to2[j]]--; } void topsort() { st[top=1]=id[S]; dp[id[S]]=sum[id[S]]; int now; while(top) { now=st[top--]; for(int i=front2[now];i;i=nxt2[i]) { dp[to2[i]]=max(dp[to2[i]],dp[now]+sum[to2[i]]); in[to2[i]]--; if(!in[to2[i]]) st[++top]=to2[i]; } } } void answer() { int ans=0,k,x; read(k); for(int i=1;i<=k;i++) { read(x); ans=max(ans,dp[id[x]]); } printf("%d ",ans); } int main() { freopen("save.in","r",stdin); freopen("save.out","w",stdout); init(); tot=0; for(int i=1;i<=n;i++) if(!dfn[i]) top=0,tarjan(i); rebuild(); pre(); topsort(); answer(); }

2017北京国庆刷题Day7 afternoon

相关推荐