ACM-ICPC 2018 徐州赛区网络预赛 LeeRinji

队伍人不齐打这场真心累啊…

BE, GE or NE

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

const int maxn=1000+10;

int f[maxn][210];
int a[maxn],b[maxn],c[maxn];
int n,m,k,l;

int main()
{
    scanf("%d%d%d%d",&n,&m,&k,&l);
    for (int i=1;i<=n;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]);
    for (int i=0;i<=l+100;i++) f[n+1][i]=-1;
    for (int i=l+101;i<k+100;i++) f[n+1][i]=0;
    for (int i=k+100;i<=200;i++) f[n+1][i]=1;
    for (int i=n;i>=1;i--)
    {
    //  for (int w=90;w<110;w++) printf("%d",f[i+1][w]);
     // printf("\n");
     for (int j=0;j<=200;j++)
     {

        int x=-1,y=-1,z=-1;
        if (a[i])
        {
            x=j+a[i];
            if (x>200) x=200;
        }
        if (b[i])
        {
            y=j-b[i];
            if (y<0) y=0;
        }
        if (c[i]) z=200-j;
        if (i&1)
        {
            if ((x>=0)&&(f[i+1][x]==1)) {f[i][j]=1; continue;}
            if ((y>=0)&&(f[i+1][y]==1)) {f[i][j]=1; continue;}
            if ((z>=0)&&(f[i+1][z]==1)) {f[i][j]=1; continue;}
            if (((x<0)||((x>=0)&&(f[i+1][x]==-1)))
                 &&((y<0)||((y>=0)&&(f[i+1][y]==-1)))
                    &&((z<0)||((z>=0)&&(f[i+1][z]==-1))))
             {f[i][j]=-1; continue;}
            f[i][j]=0;
        }
        else
        {
            if ((x>=0)&&(f[i+1][x]==-1)) {f[i][j]=-1; continue;}
            if ((y>=0)&&(f[i+1][y]==-1)) {f[i][j]=-1; continue;}
            if ((z>=0)&&(f[i+1][z]==-1)) {f[i][j]=-1; continue;}
            if (((x<0)||((x>=0)&&(f[i+1][x]==1)))
                 &&((y<0)||((y>=0)&&(f[i+1][y]==1)))
                  &&((z<0)||((z>=0)&&(f[i+1][z]==1))))
             {f[i][j]=1; continue;}
            f[i][j]=0;
        }

     }
}
    if (f[1][m+100]==1) printf("Good Ending");
     else if (f[1][m+100]==0) printf("Normal Ending");
      else printf("Bad Ending");
}

Features Track

#include<cstdio>
#include<unordered_map>
using namespace std;
int t,n;
int main()
{
    for(scanf("%d",&t); t--;)
    {
        scanf("%d",&n);
        unordered_map<int,unordered_map<int,pair<int,int> > > mp;
        int ans=0;
        for(int i=1,k,x,y; i<=n; ++i)
            for(scanf("%d",&k); k--;)
            {
                scanf("%d%d",&x,&y);
                pair<int,int> &p=mp[x][y];
                if(p.first==i)continue;//坑
                if(p.first!=i-1)p.second=0;
                p.first=i,ans=max(ans,++p.second);
            }
        if(ans==1)ans=0;//坑
        printf("%d\n",ans);
    }
}

Trace

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

const int maxn=200000+10;

struct node
{
    int l,r,mx;
} t[maxn*4];

int n;
long long ans;
int x[maxn],y[maxn],tmp1[maxn],tmp2[maxn];

void build(int cur,int l,int r)
{
    t[cur].l=l;
    t[cur].r=r;
    t[cur].mx=0;
    if (l==r) return ;
    int mid=(l+r)/2;
    build(cur*2,l,mid);
    build(cur*2+1,mid+1,r);
}

void update(int cur,int l,int r,int v)
{
    if ((t[cur].l==l)&&(t[cur].r==r))
    {
        t[cur].mx=max(t[cur].mx,v);
        return ;
    }
    t[cur*2].mx=max(t[cur*2].mx,t[cur].mx);
    t[cur*2+1].mx=max(t[cur*2+1].mx,t[cur].mx);
    t[cur].mx=0;
    int mid=(t[cur].l+t[cur].r)/2;
    if (r<=mid) update(cur*2,l,r,v);
    else if (l>mid) update(cur*2+1,l,r,v);
    else update(cur*2,l,mid,v),update(cur*2+1,mid+1,r,v);
}

int query(int cur,int pos)
{
    if (t[cur].l==t[cur].r) return t[cur].mx;
    t[cur*2].mx=max(t[cur*2].mx,t[cur].mx);
    t[cur*2+1].mx=max(t[cur*2+1].mx,t[cur].mx);
    t[cur].mx=0;
    int mid=(t[cur].l+t[cur].r)/2;
    if (pos<=mid) return query(cur*2,pos);
    else return query(cur*2+1,pos);
}

int main()
{
    scanf("%d",&n);
    for (int i=1; i<=n; i++) scanf("%d%d",&x[i],&y[i]);
    for (int i=1; i<=n; i++) tmp1[i]=x[i];
    sort(tmp1+1,tmp1+n+1);
    for (int i=1; i<=n; i++) x[i]=lower_bound(tmp1+1,tmp1+n+1,x[i])-tmp1;
    for (int i=1; i<=n; i++) tmp2[i]=y[i];
    sort(tmp2+1,tmp2+n+1);
    for (int i=1; i<=n; i++) y[i]=lower_bound(tmp2+1,tmp2+n+1,y[i])-tmp2;
    ans=0;
    build(1,1,n);
    for (int i=n; i>=1; i--)
    {
        int k=query(1,y[i]);
        ans+=tmp1[x[i]]-tmp1[k];
        update(1,1,y[i],x[i]);
    }
    build(1,1,n);
    for (int i=n; i>=1; i--)
    {
        int k=query(1,x[i]);
        ans+=tmp2[y[i]]-tmp2[k];
        update(1,1,x[i],y[i]);
    }
    printf("%lld",ans);
    return 0;
}

Ryuji doesn’t want to study

#include<cstdio>
#include<vector>
using namespace std;
typedef long long ll;
const ll INF=1e18;
struct SegmentTree
{
    struct Node
    {
        ll set,sum,ans;
    };
    vector<Node> v;
    int LAST,L,R;
    SegmentTree(int n):LAST(n),v(2*n+1) {}
    void build(ll a[],int l,int r)
    {
        if(l<r)
        {
            int m=l+(r-l)/2;
            build(a,l,m),build(a,m+1,r);
            lv(l,r).set=INF;
        }
        else lv(l,r).set=a[l];
        maintain(l,r);
    }
    Node &lv(int l,int r)
    {
        return v[l+r|l!=r];
    }
    void push_down(Node &lc,Node &rc,Node &fa)
    {
        if(fa.set!=INF)
            lc.set=rc.set=fa.set,fa.set=INF;
    }
    void push_up(const Node &lc,const Node &rc,Node &fa,int l,int r,int m)
    {
        fa.sum=lc.sum+rc.sum;
        fa.ans=lc.ans+rc.ans+lc.sum*(r-m);
    }
    void maintain(int l,int r)
    {
        if(l<r)
        {
            int m=l+(r-l)/2;
            push_up(lv(l,m),lv(m+1,r),lv(l,r),l,r,m);
        }
        if(lv(l,r).set!=INF)
        {
            int len=r-l+1;
            lv(l,r).sum=len*lv(l,r).set;
            lv(l,r).ans=(1LL+len)*len/2*lv(l,r).set;
        }
    }
    Node ask(int l,int r,ll val=0,bool out=1)
    {
        if(out)return L=l,R=r,ask(1,LAST,val,0);
        if(lv(l,r).set!=INF)
        {
            int len=min(R,r)-max(l,L)+1;
            v[0].sum=len*lv(l,r).set;
            v[0].ans=(1LL+len)*len/2*lv(l,r).set;
        }
        else if(L<=l&&r<=R)v[0]=lv(l,r);
        else
        {
            int m=l+(r-l)/2;
            if(R<=m)return ask(l,m,val,0);
            if(L>m)return ask(m+1,r,val,0);
            push_up(ask(l,m,val,0),ask(m+1,r,val,0),v[0],max(L,l),min(R,r),m);
        }
        return v[0];
    }
    void set(int l,int r,ll val,bool out=1)
    {
        if(out)return L=l,R=r,set(1,LAST,val,0);
        if(L<=l&&r<=R)lv(l,r).set=val;
        else
        {
            int m=l+(r-l)/2;
            push_down(lv(l,m),lv(m+1,r),lv(l,r));
            if(L<=m)set(l,m,val,0);
            else maintain(l,m);
            if(R>m)set(m+1,r,val,0);
            else maintain(m+1,r);
        }
        maintain(l,r);
    }
};
ll n,q,a[100009];
int main()
{
    scanf("%lld%lld",&n,&q);
    for(ll i=1; i<=n; ++i)
        scanf("%lld",&a[i]);
    SegmentTree tree(n);
    tree.build(a,1,n);
    for(ll i=0,a,b,c; i<q; ++i)
    {
        scanf("%lld%lld%lld",&a,&b,&c);
        if(a==1)printf("%lld\n",tree.ask(b,c).ans);
        if(a==2)tree.set(b,b,c);
    }
}

Characters with Hash

#include<cstdio>
using namespace std;
char s[1000009],z[9];
int t,n,ans;
int main()
{
    for(scanf("%d",&t); t--;)
    {
        scanf("%d%s%s",&n,z,s);
        for(int i=ans=0,tmp,flag=0; i<n; ++i)
        {
            if(tmp=(int)z[0]-(int)s[i],tmp<0)tmp=-tmp;
            if(flag)ans+=2;
            else if(tmp)
                for(flag=1; tmp; tmp/=10)++ans;
        }
        if(ans==0)ans=1;//坑
        printf("%d\n",ans);
    }
}