难度:省选左右

Problem A: fibonacci

题目描述:

题解:

矩阵满足结合律和分配率

然后线段树维护矩阵

每次更改乘一个矩阵就完事了

代码:

#include <bits/stdc++.h>
#define Max 200005
#define ll long long
#define int ll
#define il inline
#define ls(x) x<<1
#define rs(x) x<<1|1
#define dg puts("qwq")
#define Mod 1000000007
using namespace std;
#define getchar() (tt==ss&&(tt=(ss=In)+fread(In,1,Max,stdin),tt==ss)?EOF:*ss++)
char In[Max],*ss=In,*tt=In;
il int read()
{
    char c=getchar();
    int x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct mat
{
    ll m[3][3];
}o,t[Max<<1],tg[Max<<1],b,c;
il mat operator * (mat x,mat y)
{
    mat z;
    for(int i=1;i<=2;i++) 
        for(int j=1;j<=2;j++)
            z.m[i][j]=0;
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            for(int k=1;k<=2;k++)
                z.m[i][j]=(z.m[i][j]+x.m[i][k]*y.m[k][j]%Mod)%Mod;
    return z;
}
il mat operator + (mat x,mat y)
{
    mat z;
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            z.m[i][j]=(x.m[i][j]+y.m[i][j])%Mod;
    return z;
}
il mat qpw(mat a,ll b)
{
    mat res=o;
    //cout<<b<<endl;
    while(b)
    {
        if(b&1) res=res*a;
        a=a*a;
        b>>=1;
    }
    return res;
}
il int calc(int x)
{
    if(x==1||x==2) return 1ll;
    mat a;
    a.m[1][1]=1,a.m[1][2]=1;
    a.m[2][1]=0,a.m[2][2]=0;
    a=a*qpw(b,x-2);
    return a.m[1][2];
}
int n,m,a[Max];
il void pushup(int x)
{
    t[x]=t[ls(x)]+t[rs(x)];
}
il void pushdown(int x)
{
    tg[ls(x)]=tg[ls(x)]*tg[x];
    t[ls(x)]=t[ls(x)]*tg[x];
    tg[rs(x)]=tg[rs(x)]*tg[x];
    t[rs(x)]=t[rs(x)]*tg[x];
    tg[x]=o;
}
il void build(int x,int l,int r)
{
    //cout<<l<<' '<<r<<endl;
    tg[x]=o;
    if(l==r)
    {
        t[x].m[1][1]=calc(a[l]);
        t[x].m[1][2]=calc(a[l]+1);
        t[x].m[2][1]=0;
        t[x].m[2][2]=0;
        return;
    }
    int mid=(l+r)>>1;
    build(ls(x),l,mid);
    build(rs(x),mid+1,r);
    pushup(x);
}
il void mdf(int x,int l,int r,int ql,int qr,mat k)
{
    if(ql<=l&&r<=qr)
    {
        t[x]=t[x]*k;
        tg[x]=tg[x]*k;
        return;
    }
    int mid=(l+r)>>1;
    pushdown(x);
    if(ql<=mid) mdf(ls(x),l,mid,ql,qr,k);
    if(qr>mid) mdf(rs(x),mid+1,r,ql,qr,k);
    pushup(x);
}
il mat qry(int x,int l,int r,int ql,int qr)
{
    if(ql<=l&&r<=qr)
    {
        //cout<<l<<' '<<r<<' '<<t[x].m[1][1]<<endl;
        return t[x];
    }
    pushdown(x);
    int mid=(l+r)>>1;
    mat res=c;
    if(ql<=mid) res=res+qry(ls(x),l,mid,ql,qr);
    if(qr>mid) res=res+qry(rs(x),mid+1,r,ql,qr);
    return res;
}
signed main()
{
    n=read(),m=read();
    b.m[1][1]=0,b.m[1][2]=1;
    b.m[2][1]=1,b.m[2][2]=1;
    for(int i=0;i<=2;i++)
        for(int j=0;j<=2;j++)
            c.m[i][j]=0;
    for(int i=0;i<=2;i++) o.m[i][i]=1;
    //cout<<calc(5)<<endl;
    for(int i=1;i<=n;i++) a[i]=read();
    //dg;
    build(1,1,n);
    //dg;
    while(m--)
    {
        int opt=read(),l=read(),r=read();
        if(opt==1)
        {
            int x=read();
            mdf(1,1,n,l,r,qpw(b,x));
        }
        if(opt==2)
        {
            printf("%lld\n",qry(1,1,n,l,r).m[1][1]);
        }
    }
}

Problem B: game

题意:

题解:

毒瘤玩意,我只会50pts O(n^2)做法。

代码:

50pts:

#include <bits/stdc++.h>
#define il inline
#define ll long long
#define int long long
#define Max 1000005
using namespace std;
il ll read()
{
    ll x=0,f=1;
    char c=getchar();
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int n,c[Max],sz[Max],head[Max],tot,f[Max],g[Max],sg[Max],t[3005],ans[Max];
struct node
{
    int t,nt;
}e[Max<<1];
il void add(int u,int v)
{
    e[++tot].t=v;
    e[tot].nt=head[u];
    head[u]=tot;
}
il void dfs2(int u,int fa,int x)
{
    int res=0;
    for(int i=head[u];i;i=e[i].nt)
    {
        int v=e[i].t;
        if(v==fa) continue;
        res^=sg[v];
    }
    for(int i=head[u];i;i=e[i].nt)
    {
        int v=e[i].t;
        if(v==fa) continue;
        dfs2(v,u,x^res^sg[v]);
    }
    if(c[u]) t[x^res]=1;
}
il int getmex()
{
    for(int i=0;;i++) if(!t[i]) return i;
}
il void dfs(int u,int fa)
{
    for(int i=head[u];i;i=e[i].nt)
    {
        int v=e[i].t;
        if(v==fa) continue;
        dfs(v,u);
    }
    dfs2(u,fa,0);
    sg[u]=getmex();
    memset(t,0,sizeof(t));
}
il void dfs3(int u,int fa,int x)
{
    int res=0;
    for(int i=head[u];i;i=e[i].nt)
    {
        int v=e[i].t;
        if(v==fa) continue;
        res^=sg[v];
    }
    for(int i=head[u];i;i=e[i].nt)
    {
        int v=e[i].t;
        if(v==fa) continue;
        dfs3(v,u,x^res^sg[v]);
    }
    if(c[u]&&(res^x)==0) ans[u]=1;
}
signed main()
{
    n=read();
    for(int i=1;i<=n;i++) c[i]=read()^1;
    for(int i=1;i<n;i++)
    {
        int u=read(),v=read();
        add(u,v),add(v,u);
    }
    //check();
    //if(!flg) cout<<ans<<endl;
    dfs(1,0);
    if(sg[1]==0) puts("-1"),exit(0);
    dfs3(1,0,0);
    for(int i=1;i<=n;i++) if(ans[i]) printf("%lld\n",i);
}

100pts by Owen

#include<bits/stdc++.h>
using namespace std;
inline char nchar() {
    static const int bufl=1<<20;
    static char buf[bufl],*a,*b;
    return a==b && (b=(a=buf)+fread(buf,1,bufl,stdin),a==b)?EOF:*a++;
}
inline int read() {
    int x=0,f=1;
    char c=nchar();
    for (;!isdigit(c);c=nchar()) if (c=='-') f=-1;
    for (;isdigit(c);c=nchar()) x=x*10+c-'0';
    return x*f;
}
const int maxn=1e5+1;
const int maxj=17;
const int maxp=maxn*maxj;
bool white[maxn];
vector<int> ans;
int n;
namespace trie {
    struct node {
        node *ch[2];
        int tag;
        bool ful;
    };
    inline void tick(node *&x,int d) {
        if (!x) return;
        x->tag^=d;
    }
    inline void pushdown(node *&x,int w) {
        if (!x->tag) return;
        if ((x->tag>>w)&1) swap(x->ch[0],x->ch[1]);
        tick(x->ch[0],x->tag);
        tick(x->ch[1],x->tag);
        x->tag=0;
    }
    void insert(node *&x,int d,int w) {
        if (!x) x=new node();
        if (w<0) {
            x->ful=true;
            return;
        }
        pushdown(x,w);
        insert(x->ch[(d>>w)&1],d,w-1);
        x->ful=(x->ch[0] && x->ch[0]->ful) && (x->ch[1] && x->ch[1]->ful);
    }
    node* merge(node *x,node *y,int w) {
        if (!y) return x;
        if (!x) return y;
        pushdown(x,w),pushdown(y,w);
        x->ch[0]=merge(x->ch[0],y->ch[0],w-1);
        x->ch[1]=merge(x->ch[1],y->ch[1],w-1);
        x->ful=(w==-1 || (x->ch[0] && x->ch[0]->ful) && (x->ch[1] && x->ch[1]->ful));
        delete y;
        return x;
    }
    int mex(node *x,int w) {
        if (!x) return 0;
        if (!x->ch[0] || !x->ch[0]->ful) return mex(x->ch[0],w-1);
        return (1<<w)+mex(x->ch[1],w-1);
    }
}
using trie::node;
void getrie(node *x,int w,int d) {
    if (!x) return;
    if (w<0) {
        printf("%d ",d);
        return;
    }
    trie::pushdown(x,w);
    getrie(x->ch[0],w-1,d);
    getrie(x->ch[1],w-1,d|(1<<w));
}
void getrie(node *x) {
    getrie(x,maxj-1,0);
    puts("");
}
namespace tree {
    vector<int> t[maxn];
    int f[maxn],sum[maxn];
    node *g[maxn];
    inline void add(int x,int y) {t[x].push_back(y);}
    int dfs(int x,int fa) {
        int &fx=f[x]=0,&sm=sum[x]=0;
        node *&gx=g[x]=NULL;
        for (const int &v:t[x]) if (v!=fa) 
            sm^=dfs(v,x);
        for (const int &v:t[x]) if (v!=fa) {
            trie::tick(g[v],sm^f[v]);
            gx=trie::merge(gx,g[v],maxj-1);
            g[v]=NULL;
        }
        if (white[x]) trie::insert(gx,sm,maxj-1);
        fx=trie::mex(gx,maxj-1);
        return fx;
    }
    void getans(int x,int fa,int d) {
        if (white[x] && !(d^sum[x])) ans.push_back(x);
        for (const int &v:t[x]) if (v!=fa) getans(v,x,d^sum[x]^f[v]);
    }
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in","r",stdin);
#endif
    n=read();
    for (int i=1;i<=n;++i) white[i]=(!read());
    for (int i=2;i<=n;++i) {
        int x=read(),y=read();
        tree::add(x,y),tree::add(y,x);
    }
    if (!tree::dfs(1,1)) {
        puts("-1");
        return 0;
    }
    ans.clear();
    tree::getans(1,1,0);
    sort(ans.begin(),ans.end());
    for_each(ans.begin(),ans.end(),[](int x)->void{printf("%d\n",x);});
    return 0;
}

Problem C: graph

题意:

给定一张n个点m条边的无向图, 问删去每个点后, 原图是不是二分图。

题解:

代码:

#include <bits/stdc++.h>
#define il inline
#define ll long long
#define int long long
#define Max 100005
#define dg puts("qwq")
using namespace std;
#define getchar() (tt==ss&&(tt=(ss=In)+fread(In,1,Max,stdin),tt==ss)?EOF:*ss++)
char In[Max],*ss=In,*tt=In;
il ll read()
{
    ll x=0,f=1;
    char c=getchar();
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node
{
    int t,nt;
}e[Max<<1];
int head[Max],tot;
il void add(int u,int v)
{
    e[++tot].t=v;
    e[tot].nt=head[u];
    head[u]=tot;
}
int f[Max],d[Max],n,s[Max],m;
il int getf(int x)
{
    //cout<<x<<' '<<f[x]<<endl;
    return f[x]==x?x:getf(f[x]);
}
il int getd(int x)
{
    return f[x]==x?0:getd(f[x])^d[x];
}
int ans[Max],q1[Max],q2[Max],tp;
il int merge(int x,int y)
{
    //dg;
    int dis=getd(x)^getd(y)^1;
    x=getf(x),y=getf(y);
    if(x==y) return dis;
    if(s[x]<=s[y])
    {
        q1[++tp]=x;
        q2[tp]=y;
        d[x]=dis;
        s[y]+=s[x];
        f[x]=y;
    }
    else
    {
        q1[++tp]=y;
        q2[tp]=x;
        d[y]=dis;
        s[x]+=s[y];
        f[y]=x;
    }
    return 0;
}
il void calc(int l,int r)
{
    //puts("qwq");
    //cout<<"l:"<<l<<" r:"<<r<<endl;
    if(l==r)
    {
        ans[l]=1;
        return;
    }
    int mid=(l+r)>>1;
    int nw=tp,flg=1;
    for(int u=l;u<=mid&&flg;u++)
    {
        for(int i=head[u];i&&flg;i=e[i].nt)
        {
            //dg;
            int v=e[i].t;
            if(v<u||v>r) flg^=merge(u,v);
        }
    }
    //dg;
    if(flg) calc(mid+1,r);
    else
        for(int i=mid+1;i<=r;i++) ans[i]=0;
    while(tp>nw)
    {
        f[q1[tp]]=q1[tp];
        s[q2[tp]]-=s[q1[tp]];
        tp--;
    }
    nw=tp;
    flg=1;
    for(int u=mid+1;u<=r&&flg;u++)
    {
        for(int i=head[u];i&&flg;i=e[i].nt)
        {
            //dg;
            int v=e[i].t;
            if(v<l||v>u) flg^=merge(u,v);
        }
    }
    if(flg) calc(l,mid);
    else for(int i=l;i<=mid;i++) ans[i]=0;
    while(tp>nw)
    {
        f[q1[tp]]=q1[tp];
        s[q2[tp]]-=s[q1[tp]];
        tp--;
    }
}
signed main()
{
    srand(19260817);
    int T=read();
    while(T--)
    {
        tp=tot=0;
        n=read(),m=read();
        for(int i=1;i<=n;i++) head[i]=0;
        for(int i=1;i<=m;i++)
        {
            int u=read(),v=read();
            add(u,v),add(v,u);
        }
        for(int i=1;i<=n;i++)
        {
            f[i]=i;
            s[i]=1;
            d[i]=0;
        }
        //dg;
        calc(1,n);
        //dg;
        //cout<<n<<endl;
        for(int i=1;i<=n;i++) putchar(ans[i]+'0');
        puts("");
    }
}