q234rty's Blog

请移步http://q234rty.github.io

看起来像个裸矩乘。。

但是题目中有这样一句话：

但是同时HH又是个喜欢变化的人，所以他不会立刻沿着刚刚走来的路走回。

以点作为状态的算法很难处理这个条件，我们考虑以边作为状态。

只要在建矩阵的时候判断一下，不要从一条边直接走到它的反向边就可以了。

#include <iostream>
#include <cstring>
#include <cassert>
using namespace std;
typedef long long ll;
const int mod=45989;
struct matrix{
    int r,c;
    ll a[121][121];
    matrix(int r,int c){
        this->r=r;
        this->c=c;
        memset(a,0,sizeof(a));
    }
    ll * operator[](int p){
        return a[p];
    }
    matrix operator =(const matrix& rhs){
        //puts("WTF");
        assert(r==rhs.r && c==rhs.c);
        memcpy(a,rhs.a,sizeof(a));
        return *this;
    }
    matrix operator *(matrix& rhs){
        assert(c==rhs.r);
        //puts("WTF");
        matrix res(r,rhs.c);
        //puts("WTF");
        for(int i=0;i<r;i++)
            for(int j=0;j<rhs.c;j++)
                for(int k=0;k<c;k++)
                    (res[i][j]+=((a[i][k]*rhs[k][j])%mod))%=mod;
        //puts("WTF");
        return res;
    }
    matrix operator *=(matrix& rhs){
        return *this=(*this)*rhs;
    }
};
matrix power(const matrix& mat,ll b){
    //puts("WTF");
    matrix ret(mat.r,mat.c);
    matrix t(mat.r,mat.c);
    t=mat;
    //puts("line 48");
    for(int i=0;i<mat.r;i++)
        ret[i][i]=1;
    while(b){
        //puts("WTF");
        if (b%2)
            ret=ret*t;
        t=t*t;
        b/=2;
    }
    return ret;
}
struct edge{
    int from,to;
};
edge e[121];
int main(){
    int n,m,t,a,b;
    cin >> n >> m >> t >> a >> b;
    a++,b++;
    int cur=0;
    for(int i=1;i<=m;i++){
        int x,y;
        cin >> x >> y;
        x++,y++;
        e[cur++]=(edge){x,y};
        e[cur++]=(edge){y,x};
    }
    matrix mt(cur,cur);
    for(int i=0;i<cur;i++){
        for(int j=0;j<cur;j++){
            if (e[i].to==e[j].from && i!=(j^1))
                mt[i][j]++;
        }
    }
    mt=power(mt,t-1);
    int ans=0;
    for(int i=0;i<cur;i++)
        for(int j=0;j<cur;j++)
            if (e[i].from==a && e[j].to==b)
                (ans+=mt[i][j])%=mod;
    cout << ans;
}

三天写了一道NOIP题。。

题目在这里：http://uoj.ac/problem/17

暴力dp的方程是显然的：对于每一个i,j,更新dp[i+1][j-y[i]],dp[i+1][min(j+x[i]*k,m)](1<=k<=m)

然后发现min的部分是可以递推的。。

然后用dp[i][j][0]表示可以下降不能高度不变，dp[i][j][1]表示可以高度不变不能下降。。

转移看代码吧。。

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
const int MAXSIZE=10000020;
int bufpos;
char buf[MAXSIZE];
void init(){
    buf[fread(buf,1,MAXSIZE,stdin)]='\0';
    bufpos=0;
}
int readint(){
    bool isneg;
    int val=0;
    for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
    bufpos+=(isneg=(buf[bufpos]=='-'))?1:0;
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return isneg?-val:val;
}
int dp[10001][1001][2];
int l[10001],h[10001],x[10001],y[10001];
int main(){
    init();
    int n=readint(),m=readint(),k=readint();
    for(int i=0;i<n;i++){
        x[i]=readint(),y[i]=readint();
    }
    fill(l,l+n+1,0);
    fill(h,h+n+1,m+1);
    for(int i=1;i<=k;i++){
        int p=readint();
        l[p]=readint();
        h[p]=readint();
    }
    memset(dp,0x3f,sizeof(dp));
    memset(dp[0],0,sizeof(dp[0]));
    for(int j=0;j<=m;j++)
        dp[0][j][1]=INF;
    int maxr=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<=m;j++){
            if (j<=l[i] || j>=h[i]){
                dp[i][j][0]=INF;
                //printf("dp[%d][%d][1] is %d\n",i,j,dp[i][j][1]);
                //printf("dp[%d][%d][0] is %d\n",i,j,dp[i][j][0]);
            }
            dp[i+1][min(j+x[i],m)][0]=min(dp[i+1][min(j+x[i],m)][0],dp[i][j][0]+1);
            if (j>y[i])
                dp[i+1][j-y[i]][0]=min(dp[i+1][j-y[i]][0],dp[i][j][0]);
            dp[i+1][j][0]=min(dp[i+1][j][0],dp[i][j][1]);
            dp[i][min(j+x[i],m)][1]=min(dp[i][min(j+x[i],m)][1],dp[i][j][1]+1);
            dp[i][min(j+x[i],m)][1]=min(dp[i][min(j+x[i],m)][1],dp[i][j][0]+1);
            if (dp[i][j][0]<INF){
                maxr=i;
            }
            //printf("dp[%d][%d][1] is %d\n",i,j,dp[i][j][1]);
            //printf("dp[%d][%d][0] is %d\n",i,j,dp[i][j][0]);
        }
    int ans=INF;
    for(int i=0;i<=m;i++)
        ans=min(ans,dp[n][i][0]);
    if (ans>=INF){
        printf("0\n");
        int cnt=0;
        for(int i=0;i<=maxr;i++)
            if (h[i]<m+1)
                cnt++;
        printf("%d\n",cnt);
    }
    else printf("1\n%d\n",ans);

}

一些奇怪的模板

#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXSIZE=30000020;
int bufpos;
char buf[MAXSIZE];
void init(){
    buf[fread(buf,1,MAXSIZE,stdin)]='\0';
    bufpos=0;
}
int readint(){
    bool isneg;
    int val=0;
    for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
    bufpos+=(isneg=(buf[bufpos]=='-'))?1:0;
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return isneg?-val:val;
}
char readchar(){
    for(;isspace(buf[bufpos]);bufpos++);
    return buf[bufpos++];
}

struct segtree{
    ll minv[maxn*8];
    int n,p;
    ll v;
    segtree(){
        memset(minv,0,sizeof(minv));
    }
    void _update_(int o,int l,int r){
        if (l==r){
            minv[o]=v;
            assert(l==p);
            return;
        }
        ll m=l+(r-l)/2;
        //puts("line 35");
        if (p<=m)
            _update_(o*2,l,m);
        else _update_(o*2+1,m+1,r);
        minv[o]=min(minv[o*2],minv[o*2+1]);
    }
    void update(int p,ll v){
        this->p=p;
        this->v=v;
        _update_(1,1,n);
        //puts("updated once");
    }
    int ql,qr;
    ll _query_(int o,int l,int r){
        if (ql<=l && r<=qr)
            return minv[o];
        ll ans=INF;
        int m=l+(r-l)/2;
        if (ql<=m)
            ans=min(ans,_query_(o*2,l,m));
        if (qr>=m+1)
            ans=min(ans,_query_(o*2+1,m+1,r));
        return ans;
    }
    ll query(int l,int r){
        if (l>r)
            return INF;
        ql=l;
        qr=r;
        return _query_(1,1,n);
    }
};

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
struct acatm{
    int ch[201][26];
    int val[201];
    int f[201];
    int last[201];
    bool match[1000001][21];
    int sz,cnt;
    acatm(){
        sz=1;
        cnt=0;
        memset(ch[0],0,sizeof(ch[0]));
        memset(val,0,sizeof(val));
    }
    inline int idx(char c){
        return c-'a';
    }
    void ins(char* s){
        int len=strlen(s),u=0;
        for(int i=0;i<len;i++){
            int c=idx(s[i]);
            int v=ch[u][c];
            if (!v){
                ch[u][c]=v=sz++;
                memset(ch[v],0,sizeof(ch[v]));
                val[v]=0;
            }
            u=v;
        }
        val[u]=++cnt;
    }
    void getfail(){
        queue<int> q;
        f[0]=0;
        last[0]=0;
        for(int i=0;i<26;i++){
            int u=ch[0][i];
            if (u){
                q.push(u);
                f[u]=0;
                last[u]=0;
            }
        }
        while(!q.empty()){
            int r=q.front();q.pop();
            for(int i=0;i<26;i++){
                int u=ch[r][i];
                if (!u){
                    ch[r][i]=ch[f[r]][i];
                    continue;
                }
                int v=f[r];
                while(v && !ch[v][i])
                    v=f[v];
                f[u]=ch[v][i];
                //printf("f[%d]=%d\n",u,f[u]);
                last[u]=val[f[u]]?f[u]:last[f[u]];
                q.push(u);
            }
        }
    }
    void print(int i,int u){
        if (u){
            match[i][val[u]]=true;
            print(i,last[u]);
        }
    }
    void fi(char* s){
        memset(match,0,sizeof(match));
        int len=strlen(s),u=0;
        for(int i=0;i<len;i++){
            int c=idx(s[i]);
            u=ch[u][c];
            //printf("i=%d,u=%d\n",i,u);
            if (val[u])
                print(i,u);
            else if (last[u]) print(i,last[u]);
        }
    }
};

struct edge{
    int from,to,next;
};
struct graph{
    int n,m;
    edge e[400001];
    bool iscut[100001];
    bool isbri[400001];
    int low[100001];
    int pre[100001];
    int first[100001];
    int cnt;
    graph(){
        m=0;
        cnt=0;
        memset(first,-1,sizeof(first));
        memset(pre,0,sizeof(pre));
        memset(iscut,0,sizeof(iscut));
        memset(isbri,0,sizeof(isbri));
    }
    void addedge(int from,int to){
        e[++m]=(edge){from,to,first[from]};
        first[from]=m;
    }
    int dfs(int u,int fa){
        int& lowu=low[u];
        lowu=pre[u]=++cnt;
        int child=0;
        for(int i=first[u];i!=-1;i=e[i].next){
            int v=e[i].to;
            if (!pre[v]){
                child++;
                int lowv=dfs(v,u);
                lowu=min(lowu,lowv);
                if (lowv>=pre[u])
                    iscut[u]=true;
                if (lowv>pre[u])
                    isbri[i]=true;   //Only one of (u,v) and (v,u) will be labeled,be careful!
            }
            else if (pre[v]<pre[u] && v!=fa)
                lowu=min(lowu,pre[v]);
        }
        if (fa<0 && child==1)
            iscut[u]=false;
        return lowu;
    }
};

struct edge{
    int from,to,next;
};
struct graph{
    int n,m;
    edge e[100001];
    int first[10001];
    int lowlink[10001];
    int sccno[10001];
    int pre[10001];
    int num[10001];
    int out0[10001];
    int cnt,dfsc;
    stack<int> s;
    graph(){
        m=0;
        memset(first,-1,sizeof(first));
    }
    void addedge(int from,int to){
        e[++m]=(edge){from,to,first[from]};
        first[from]=m;
    }
    void dfs(int u){
        pre[u]=lowlink[u]=++dfsc;
        s.push(u);
        for(int i=first[u];i!=-1;i=e[i].next){
            int v=e[i].to;
            if (!pre[v]){
                dfs(v);
                lowlink[u]=min(lowlink[u],lowlink[v]);
            } else if (!sccno[v]){
                lowlink[u]=min(lowlink[u],pre[v]);
            }
        }
        if (lowlink[u]==pre[u]){
            cnt++;
            for(;;){
                int x=s.top();
                s.pop();
                sccno[x]=cnt;
                num[cnt]++;
                if (x==u)
                    break;
            }
        }
    }
    void getscc(){
        dfsc=cnt=0;
        memset(pre,0,sizeof(pre));
        memset(sccno,0,sizeof(sccno));
        memset(num,0,sizeof(num));
        for(int i=1;i<=n;i++)
            if (!pre[i])
                dfs(i);
    }
    void rebuild(){
        memset(out0,1,sizeof(out0));
        for(int i=1;i<=n;i++){
            for(int j=first[i];j!=-1;j=e[j].next)
                if (sccno[i]!=sccno[e[j].to])
                    out0[sccno[i]]=false;
        }
    }
};

#include <cstdio>
#include <cstring>
using namespace std;
struct edge{
    int from,to,next;
};
struct twosat{
    int n,m;
    edge e[2001];
    bool mark[201];
    int first[201];
    int s[201],c;
    inline int other(int x){
        return x%2?x+1:x-1;
    }
    twosat(){
        m=0;
        memset(mark,0,sizeof(mark));
        memset(first,-1,sizeof(first));
    }
    void clear(){
        m=0;
        memset(mark,0,sizeof(mark));
        memset(first,-1,sizeof(first));
    }
    void addedge(int from,int to){
        e[++m]=(edge){from,to,first[from]};
        first[from]=m;
    }
    void addclue(int x,int xval,int y,int yval){
        x=x*2+xval-1;
        y=y*2+yval-1;
        addedge(other(x),y);
        addedge(other(y),x);
    }
    bool dfs(int x){
        if (mark[x])
            return true;
        if (mark[other(x)])
            return false;
        mark[x]=true;
        s[++c]=x;
        for(int i=first[x];i!=-1;i=e[i].next){
            if (!dfs(e[i].to))
                return false;
        }
        return true;
    }
    bool solve(){
        /*for(int i=1;i<=2*n;i++){
            printf("edges from %d:",i);
            for(int j=first[i];j!=-1;j=e[j].next)
                printf("%d ",e[j].to);
            putchar('\n');
        }*/
        for(int i=1;i<=2*n;i+=2){
            if (!mark[i] && !mark[i+1]){
                c=0;
                if (!dfs(i)){
                    for(int j=1;j<=c;j++)
                        mark[s[j]]=false;
                    c=0;
                    if (!dfs(i+1))
                        return false;
                }
            }
        }
        return true;
    }
};

typedef long long ll;
struct edge{
    int from,to;
    int dist;
    int next;
};
struct graph{
    int n,m;
    ll d[1002];
    edge e[200001];
    int first[1002];
    bool inq[1002];
    int cnt[1002];
    int q[2000002];
    void init(int n){
        this->n=n;
        memset(first,-1,sizeof(int)*1002);
        m=0;
    }
    void addedge(int from,int to,int dist){
        e[++m]=(edge){from,to,dist,first[from]};
        first[from]=m;
    }
    bool spfa(int s){
        //int q[100004];
        int f=1,r=1;
        memset(d,0x3f,sizeof(ll)*1002);
        memset(inq,0,sizeof(int)*1002);
        memset(cnt,0,sizeof(int)*1002);
        d[s]=0;
        q[r]=s;
        r++;
        inq[s]=true;
        cnt[s]=1;
        while (f<r){
            register int u=q[f];
            f++;
            inq[u]=false;
            register int i=first[u];
            while(i!=-1){
                register ll t=d[u]+e[i].dist;
                register int v=e[i].to;
                if(d[u]<INF && d[v]>t){
                    d[v]=t;
                    if (!inq[v]){
                        q[r]=v;
                        r++;
                        inq[v]=true;
                        if (++cnt[v]>n){
                            return false;
                        }
                    }
                }
                i=e[i].next;
            }
        }
        return true;
    }
};

typedef long long ll;
struct edge{
    ll from,to,dist,next;
};
struct heapnode{
    ll d,u;
    bool operator < (const heapnode& rhs) const{
        return d>rhs.d;
    }
};
struct graph{
    ll n,m;
    edge* e=new edge[200003];
    ll* first=new ll[200003];
    ll* d=new ll[200003];
    ll* p=new ll[200003];
    bool* done=new bool[200003];
    void init(ll n){
        this->n=n;
        m=0;
        memset(first,-1,200003*sizeof(ll));
    }
    void addedge(ll from,ll to,ll dist){
        e[++m]=(edge){from,to,dist,first[from]};
        first[from]=m;
    }
    void dijkstra(ll s){
        priority_queue<heapnode> q;
        memset(d,0x3f,200003*sizeof(ll));
        d[s]=0;
        memset(done,0,200003*sizeof(bool));
        memset(p,0,200003*sizeof(ll));
        q.push((heapnode){0,s});
        while(!q.empty()){
            ll u=q.top().u;
            q.pop();
            if (done[u])
                continue;
            done[u]=true;
            //prllf("u=%d\n",u);
            ll i=first[u];
            while (i!=-1){
                if (d[u]+e[i].dist<d[e[i].to]){
                    d[e[i].to]=d[u]+e[i].dist;
                    p[e[i].to]=u;
                    q.push((heapnode){d[e[i].to],e[i].to});
                }
                i=e[i].next;
            }
        }
    }
};

typedef int ll;
int mod;
struct matrix{
    int r,c;
    ll a[51][51];
    matrix(int r,int c){
        this->r=r;
        this->c=c;
        memset(a,0,sizeof(a));
    }
    ll * operator[](int p){
        return a[p];
    }
    matrix operator =(const matrix& rhs){
        //puts("WTF");
        assert(r==rhs.r && c==rhs.c);
        memcpy(a,rhs.a,sizeof(a));
        return *this;
    }
    matrix operator *(matrix& rhs){
        assert(c==rhs.r);
        //puts("WTF");
        matrix res(r,rhs.c);
        //puts("WTF");
        for(int i=1;i<=r;i++)
            for(int j=1;j<=rhs.c;j++)
                for(int k=1;k<=c;k++)
                    (res[i][j]+=((a[i][k]*rhs[k][j])%mod))%=mod;
        //puts("WTF");
        return res;
    }
    matrix operator *=(matrix& rhs){
        return *this=(*this)*rhs;
    }
};
matrix power(const matrix& mat,ll b){
    //puts("WTF");
    matrix ret(mat.r,mat.c);
    matrix t(mat.r,mat.c);
    t=mat;
    //puts("line 48");
    for(int i=1;i<=mat.r;i++)
        ret[i][i]=1;
    while(b){
        //puts("WTF");
        if (b%2)
            ret=ret*t;
        t=t*t;
        b/=2;
    }
    return ret;
}

struct edge{
    int from,to,next;
};
struct graph{
    int nl,m;
    edge e[maxm];
    int first[maxn];
    int match[maxn];
    bool vis[maxn];
    void init(int nl){
        this->nl=nl;
        m=0;
        memset(first,-1,sizeof(first));
    }
    void addedge(int from,int to){
        e[++m]=(edge){from,to,first[from]};
        first[from]=m;
    }
    bool dfs(int u){
        for(int i=first[u];i!=-1;i=e[i].next){
            int v=e[i].to;
            if (!vis[v]){
                vis[v]=true;
                if (match[v]==-1 || dfs(match[v])){
                    match[u]=v;
                    match[v]=u;
                    return true;
                }
            }
        }
        return false;
    }
    int work(){
        int ans=0;
        memset(match,-1,sizeof(match));
        for(int i=1;i<=nl;i++)
            if (match[i]==-1){
                memset(vis,0,sizeof(vis));
                if (dfs(i))
                    ++ans;
            }
        return ans;
    }
};

struct bit{
    int t[32003];
    int n;
    bit(){
        memset(t,0,sizeof(t));
    }
    inline int lowbit(int x){
        return (x&(-x));
    }
    int sum(int x){
        int ret=0;
        for(int i=x;i>0;i-=lowbit(i))
            ret+=t[i];
        return ret;
    }
    void add(int p,int v){
        for(int i=p;i<=n;i+=lowbit(i))
            t[i]+=v;
        /*for(int i=1;i<=n;i++)
            printf("%d ",t[i]);*/
    }
};

第一篇博客\w/

这里是一名普及组蒟蒻，请大家多多指教\w/