CF631

2016.02.20 14:13 Sat | 37次阅读 | 旧日oi | 固定链接 | 源码

education round,就贴个后仨题代码吧

D Magic Numbers

题目大意

求[a,b]之间所有从高到低第2,4,6.....2x位都等于d,且是m的倍数的个数。

题解

数位dp,f[i][j][k]表示从高到低前i位,模m为j,前i为是否和上限的前k位相同。然后转移不说了……

我的程序

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long
char getc()
{   
    static char *S,*T,buf[65536];
    if(S==T){T=(S=buf)+fread(buf,1,65536,stdin);if(S==T) return EOF;}
    return *S++;
}
int read()
{
    static char ch;static int D,f;
    while(!isdigit(ch=getc())&&ch!='-');
    if(ch=='-') ch=getc(),f=1;else f=0;
    for(D=ch-'0';isdigit(ch=getc());) D=D*10+ch-'0';
    return f?D:-D;
}
ll dp[2005][2005][2];
char a[2005],b[2005];
int m,d;
ll work(char s[],int flag)
{
    int len=strlen(s+1);
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=s[1]-'0';i++) 
    if(i!=d) dp[1][i%m][i==s[1]-'0']++;
    for(int i=1;i<len;i++)
    for(int j=0;j<m;j++)
    {
        dp[i][j][0]%=mod;dp[i][j][1]%=mod;
        if(i&1)
        {
            dp[i+1][(j*10+d)%m][0]+=dp[i][j][0];
            if(d<=s[i+1]-'0') dp[i+1][(j*10+d)%m][d==s[i+1]-'0']+=dp[i][j][1];
        }
        else
        {
            for(int k=0;k<=9;k++)
            if(k!=d)
            {
                dp[i+1][(j*10+k)%m][0]+=dp[i][j][0];
                if(k<=s[i+1]-'0') dp[i+1][(j*10+k)%m][k==s[i+1]-'0']+=dp[i][j][1];
            }
        }
    }
    return dp[len][0][0]+dp[len][0][1]*flag;
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
    cin>>m>>d;
    scanf("%s%s",a+1,b+1);
    printf("%I64d\n",(work(b,1)-work(a,0)+mod)%mod);
}

E Zbazi in Zeydabad

题目大意

给出一个n*m的网格,上面有一些点,求由点构成的z字形的个数。
n,m<=3000

题解

斜着考虑,用一个树状数组和set维护一下就好了……没啥说的
复杂度nmlog(n+m)

我的程序

#include <bits/stdc++.h>
using namespace std;
#define N 3005
char getc()
{   
    static char *S,*T,buf[65536];
    if(S==T){T=(S=buf)+fread(buf,1,65536,stdin);if(S==T) return EOF;}
    return *S++;
}
int read()
{
    static char ch;static int D,f;
    while(!isdigit(ch=getc())&&ch!='-');
    if(ch=='-') ch=getc(),f=1;else f=0;
    for(D=ch-'0';isdigit(ch=getc());) D=D*10+ch-'0';
    return f?D:-D;
}
int n,m;
long long ans;
char s[N][N];
set< pair<int,int> > ss;
int c[N<<1],vis[N<<1],tim;
#define lowbit(x) (x&(-x))
void add(int x,int y)
{
    for(;x;x-=lowbit(x))
    {
        if(vis[x]!=tim) vis[x]=tim,c[x]=0; 
        c[x]+=y;
    }
}
int query(int x)
{
    int ret=0;
    for(x=max(1,x);x<=6000;x+=lowbit(x)) 
    if(vis[x]==tim) ret+=c[x];
    return ret;
}
int l[N][N],r[N][N];
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
    for(int i=1;i<=n;i++)
    {
        int last=0;
        for(int j=1;j<=m;j++)
        {
            if(s[i][j]=='.') last=j;
            else l[i][j]=last+1;
        }
    }
    for(int i=1;i<=n;i++)
    {
        int last=m+1;
        for(int j=m;j;j--)
        {
            if(s[i][j]=='.') last=j;
            else r[i][j]=last-1;
        }
    }
    for(int i=2;i<=n+m;i++)
    {
        ss.clear();tim++;
        for(int k,j=max(1,i-m);j<=min(n,i-1);j++)
        {
            k=i-j;
            if(s[j][k]=='.') tim++,ss.clear();
            else
            {
                while(!ss.empty()&&(*ss.begin()).first<j) 
                {
                    add((*ss.begin()).second,-1);
                    ss.erase(ss.begin());
                }
                add(j,1);
                ans+=query(j-(r[j][k]-k));
                ss.insert(make_pair(j+k-l[j][k],j));
            }
        }
    }
    cout<<ans<<endl;
}

F Bear and Fair Set

题目大意

不写了自己看……

题解

很简单的网络流,建图不说了……

我的程序

#include <bits/stdc++.h>
using namespace std;
#define N 10010
#define M 1000005
#define inf 0x3f3f3f3f
char getc()
{   
    static char *S,*T,buf[65536];
    if(S==T){T=(S=buf)+fread(buf,1,65536,stdin);if(S==T) return EOF;}
    return *S++;
}
int read()
{
    static char ch;static int D,f;
    while(!isdigit(ch=getc())&&ch!='-');
    if(ch=='-') ch=getc(),f=1;else f=0;
    for(D=ch-'0';isdigit(ch=getc());) D=D*10+ch-'0';
    return f?D:-D;
}
int h[N],tp=1;
struct edge{int to,next,val;}e[M];
void ae(int u,int v,int w=0){e[++tp].to=v;e[tp].next=h[u];e[tp].val=w;h[u]=tp;}
int n,b,q;
struct MAXFLOW
{
    int S,T,dis[N],q[N],f,t;
    void init(int s,int t){S=s;T=t;}    
    void add(int u,int v,int w){ae(u,v,w);ae(v,u,0);}
    int bfs(){
        memset(dis,0,sizeof(dis));dis[S]=1;q[f=t=1]=S;
        while(f<=t){
            int u=q[f++];
            for(int v,i=h[u];i;i=e[i].next) 
            if(e[i].val&&!dis[v=e[i].to]) dis[q[++t]=v]=dis[u]+1;
        }
        return dis[T];
    }
    int dfs(int u,int l)
    {
        if(u==T) return l;
        int c=0,t;
        for(int v,i=h[u];i;i=e[i].next)
        if(e[i].val&&dis[v=e[i].to]==dis[u]+1)
        {
            t=dfs(v,min(l-c,e[i].val));
            if(t){e[i].val-=t;e[i^1].val+=t;if((c+=t)==l) break;}
            else dis[v]=-1;
        }
        return c;
    }
    int dinic(){int ret=0;while(bfs()) ret+=dfs(S,inf);return ret;}
}g;
pair<int,int> a[N];
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
    cin>>n>>b>>q;
    for(int i=1;i<=q;i++)
        scanf("%d%d",&a[i].first,&a[i].second);
    sort(a+1,a+q+1);
    if(a[q].first!=b) a[++q]=make_pair(b,n);
    g.init(0,5+q+1);
    for(int i=1;i<=5;i++) g.add(i,g.T,n/5);
    for(int i=1;i<=q;i++)
    {
        if(a[i].second<a[i-1].second){puts("unfair");return 0;}
        g.add(g.S,i+5,a[i].second-a[i-1].second);
        for(int k=0;k<5;k++) 
        {
            if(!k) g.add(i+5,k+1,(a[i].first-k)/5-(a[i-1].first-k)/5);
            else g.add(i+5,k+1,(a[i].first-k)/5+1-(a[i-1].first-k)/5-(a[i-1].first>=k));
        }
    }
    puts(g.dinic()==n?"fair":"unfair");
}
  • 张丁天 2016-02-26 23:26:57

    %%%%%%%%%%%%%%%求友链OAQ