Bakser's Blog

我是逗比。

NOI2014题解(待补)

| Comments

同步赛打的跟翔一样。。。。暴力写错不能多说
Day1:
T1:按位贪心,看一看这一位取1或0会有什么后果,在限制内从高位到低位贪心。
T2:按a排序然后按a从小到大加边,发现对b来说就是求MST,LCT维护动态MST即可。
T3:提答不多说。
Day2:
T1:next指针反向会构成一颗树,在这颗树上向上跳一步就是最长的公共前后缀的长度,两步就是次长的...所以问题就是询问从这个点到根有多少个比它的二分之一小的。我写的是vfk(Orz)教的做法,就是倒着枚举每个点,并查集维护以每个点做答案的点集,然后当这个点不能做答案时就将它与它父亲点集合并,以它父亲做答案。
PS:搞了半天发现递归的并查集带路径压缩也会爆栈,感觉整个人都萌萌哒了~~~~
T2:从小到大枚举1~n*m,如果在能选的范围内就选,否则跳过。所以怎么判可行成为了亮点。事实告诉我们,暴力维护每一行能取的左右边界就可以。。。。
T3:就是这道题待补啦0w0,真相是那一坨技能都遗忘了。。。。

代码

d1T1
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAX(a,b) (((a)>(b))?(a):(b))
const int N (1e5+10);
template<class T>
inline void read(T &x)
{
    char c(0);bool flag(0);
    for(;c<'0'||c>'9';c=getchar())flag|=(c=='-');
    for(x=0;c>='0'&&c<='9';c=getchar())(x*=10)+=(c-'0');
    if(flag)x*=-1;
}
int n,m,tmp1,tmp2,b,a[2][40];
struct hh
{
    int k,t;
}d[N];
int main()
{
    read(n);read(m);
    char s[20];
    int maxx(m);
    for(int i(0);i<n;i++)
    {
        scanf("%s",s);read(d[i].t);
        maxx=MAX(maxx,d[i].t);
        if(s[0]=='A')d[i].k=1;
        if(s[0]=='O')d[i].k=2;
        if(s[0]=='X')d[i].k=3;
    }   
    int t(maxx);
    for(b=0;t;t>>=1,b++);
    tmp1=((1<<(b+1))-1);
    tmp2=0;
    for(int i(0);i<n;i++)
    {
        if(d[i].k==1)tmp1&=d[i].t,tmp2&=d[i].t;
        if(d[i].k==2)tmp1|=d[i].t,tmp2|=d[i].t;
        if(d[i].k==3)tmp1^=d[i].t,tmp2^=d[i].t;
    }
    for(int i(0);i<=b;i++)
    {
        a[0][i]=tmp2&(1<<i);
        a[1][i]=tmp1&(1<<i);
    }
    int now=0;
    int ans(0);
    for(int i(b);i>=0;i--)
    {
        if(a[0][i])ans|=a[0][i];
        else if((now|(1<<i))<=m&&a[1][i])now|=(1<<i),ans|=(1<<i);
    }
    printf("%d\n",MAX(ans,tmp2));
    return 0;
}
d1T2
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N(50100);
const int M(100100);
#define id(x) (lct+x)
#define MIN(a,b) (((a)<(b))?(a):(b))
inline void read(int &x)
{
    char c(0);bool flag(0);
    for(;c<'0'||c>'9';c=getchar())flag|=(c=='-');
    for(x=0;c>='0'&&c<='9';c=getchar())(x*=10)+=(c-'0');
    if(flag)x*=-1;
}
struct db
{
    int u,v,a,b;
}edges[M];
inline bool operator<(const db &x,const db &y)
{
    return x.a<y.a;
}
class hh
{
    public:
        int val;
        bool rev;
        hh *son[2],*pre,*great;
        hh();
        void push_up();
        void push_down();
        bool is_root()
        {
            return (this!=pre->son[0]&&this!=pre->son[1]);
        }
        inline bool f()
        {
            return this==pre->son[1];
        }
        inline void sets(hh *x,int f)
        {
            push_down();
            (son[f]=x)->pre=this;
            push_up();
        }
}lct[N+M];
hh::hh(){val=rev=0;great=this;son[0]=son[1]=pre=lct;}
void hh::push_down()
{
    if(this==lct)return;
    if(rev)
    {
        swap(son[0],son[1]);
        son[0]->rev^=1;son[1]->rev^=1;
        rev=0;
    }
}
void hh::push_up()
{
    if(this==lct)return;
    great=this;
    if(son[0]->great->val>great->val)great=son[0]->great;
    if(son[1]->great->val>great->val)great=son[1]->great;
}
inline void rotate(hh *x)
{
    hh* const y(x->pre);
    if(!y->is_root())y->pre->push_down();
    y->push_down();
    x->push_down();
    int f(x->f());
    y->sets(x->son[!f],f);
    if(y->is_root())x->pre=y->pre;
    else y->pre->sets(x,y->f());
    x->sets(y,!f);
}
inline hh* splay(hh* x)
{
    for(;!x->is_root();rotate(x))
        if(x->pre->is_root());
        else if(x->f()==x->pre->f())rotate(x->pre);
        else rotate(x);
    return x;
}
inline hh* access(hh *x)
{
    hh *y(lct);
    for(;x!=lct;x=x->pre)
    {
        splay(x)->sets(y,1);
        y=x;
    }
    return y;
}
inline hh* evert(hh *x)
{
    access(x)->rev^=1;
    return splay(x);
}
inline hh* get_root(hh *x)
{
    for(x=access(x);x->push_down(),x->son[0]!=lct;x=x->son[0]);
    return x;
}
inline void link(hh* const x,hh* const y)
{
    evert(x)->pre=y;
    access(x);
}
inline void cut(hh* const x)
{
    splay(x)->son[0]->pre=x->pre;
    x->son[1]->pre=lct;
    x->son[0]=x->son[1]=x->pre=lct;
    x->great=x;
    x->val=0;
}
inline hh* query(hh *x,hh *y)
{
    evert(x);
    access(y);
    return splay(y)->great;
}
inline void add(hh *u,hh *v,hh *w)
{
    if(get_root(u)==get_root(v))
    {
        hh *x(query(u,v));
        if(x->great->val<w->val)return;
        cut(x);
        v->push_up();
    }
    link(v,w);
    link(w,u);
}
int n,m,fa[N],ls[M],tot;
inline int find(int x)
{
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
int main()
{
    read(n);read(m);
    for(int i(1);i<=n;i++)fa[i]=i;
    for(int i(1);i<=m;i++)
    {
        read(edges[i].u),read(edges[i].v),read(edges[i].a),read(edges[i].b);
        ls[tot++]=edges[i].a;
        int p(find(edges[i].u)),q(find(edges[i].v));
        if(p!=q)
            fa[p]=q;
    }
    if(find(1)!=find(n))
    {
        puts("-1");
        return 0;
    }
    sort(edges+1,edges+m+1);
    sort(ls,ls+tot);
    tot=unique(ls,ls+tot)-ls;
    long long ans(0x7fffffff);
    int last(1);
    for(int i(0);i<tot;i++)
    {
        for(;edges[last].a<=ls[i]&&last<=m;last++)
        {
            id(n+last)->val=edges[last].b;
            add(id(edges[last].u),id(edges[last].v),id(n+last));
            if(get_root(id(1))==get_root(id(n)))
                ans=MIN(ans,ls[i]+query(id(1),id(n))->val);
        }
    }
    printf("%lld\n",ans);
    return 0;
}
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD(1000000007);
const int L(1001000);
struct hh
{
    int next,v;
}edges[L];
int n,len,next[L],fa[L],dis[L],en,point[L];
char s[L];
inline void get_fail()
{
    next[1]=0;
    for(int i(2),j=0;i<=len;i++)
    {
        while(j>0&&s[j+1]!=s[i])j=next[j];
        if(s[j+1]==s[i])j++;
        next[i]=j;
    }
}
inline int find(int x)
{
    int t(fa[x]);
    for(;fa[t]!=t;t=fa[t]);
    for(;fa[x]!=x;)
    {
        int y(fa[x]);
        fa[x]=t;
        x=y;
    }
    return t;
}
inline void addedge(int u,int v)
{
    edges[++en].next=point[u];
    point[u]=en;edges[en].v=v;
}
inline void bfs()
{
    static queue<int> q;
    dis[0]=0;
    for(q.push(0);!q.empty();q.pop())
    {
        int u(q.front());
        for(int i(point[u]);i;i=edges[i].next)
            dis[edges[i].v]=dis[u]+1,q.push(edges[i].v);
    }
}
int main()
{
    for(scanf("%d",&n);n--;)
    {
        scanf("%s",s+1);
        len=strlen(s+1);
        get_fail();
        en=0;
        memset(point,0,sizeof(point));
        char lst=s[0];
        bool flag(1);
        for(int i(1);i<len;i++)
        {
            if(flag&&s[i]!=lst)flag=0;
        }
        LL ans(1);
        if(flag)
        {
            for(int i(1);i<len;i++)
            {
                ans*=((i+1)>>1)+1;
                if(ans>=MOD)ans%=MOD;
            }
            printf("%lld\n",ans);
        }
        for(int i(1);i<=len;i++)
            fa[i]=i;
        for(int i(1);i<=len;i++)
            addedge(next[i],i);
        bfs();
        int last(len);
        for(int i(len);i>=1;i--)
        {
            int now(i>>1);
            for(int j(now+1);j<=last;j++)
                {
                    int p(find(j)),q(find(next[j]));
                    if(p!=q)
                        fa[p]=q;
                }
            int p(find(i));
            if(p<=(i>>1))
                ans=(ans*LL(dis[p]+1))%MOD;
            last=now;
        }
        printf("%lld\n",ans);
    }
    return 0;
}
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N(25000100);
#define MIN(a,b) (((a)<(b))?(a):(b))
#define MAX(a,b) (((a)>(b))?(a):(b))
typedef long long LL;
template<class T>
inline void read(T &x)
{
    char c(0);
    for(;c<'0'||c>'9';c=getchar());
    for(x=0;c>='0'&&c<='9';c=getchar())(x*=10)+=(c-'0');
}
LL a,b,c,d,x;
int n,m,Q,tot,map[N],pos[N],l[5010],r[5010];
inline void putint(int x)
{
    if(!x)return;
    if(x<10)putchar(x+'0');
    else putint(x/10),putchar(x%10+'0');
}
int main()
{
    read(x);read(a);read(b);read(c);read(d);
    read(n);read(m);
    tot=n*m;
    for(int i(0);i<tot;i++)map[i]=i+1;
    for(int i(1);i<=tot;i++)
    {
        x=(x*x*a+b*x+c)%d;
        swap(map[i-1],map[x%i]);
    }
    for(read(Q);Q--;)
    {
        int u,v;
        read(u);read(v);
        swap(map[u-1],map[v-1]);
    }
    for(int i(0);i<tot;i++)
        pos[map[i]]=i;
    for(int i(1);i<=n;i++)
        l[i]=1,r[i]=m;
    tot=0;
    for(int i(1);i<=n*m;i++)
    {
        int hh(pos[i]/m+1),cc(pos[i]%m+1);
        if(!(cc>=l[hh]&&cc<=r[hh]))continue;
        else
        {
            tot++;
            putint(i);
            if(tot==n+m-1)puts("");
            else putchar(' ');
        }
        for(int i(1);i<hh;i++)
            r[i]=MIN(r[i],cc);
        for(int i(hh+1);i<=n;i++)
            l[i]=MAX(l[i],cc);
    }
    return 0;
}

Comments

comments powered by Disqus