列表

详情

NC16855. [NOI1999]01串

描述

给定7个整数N,A0,B0,L0,A1,B1,L1，要求设计一个01串S=s1s2…si…sN，满足：

si=0或si=1，1<=i<=N；

对于S的任何连续的长度为L0的子串sjsj+1…sj+L0-1(1≤j≤N-L0+1)，0的个数大于等于A0且小于等于B0;

对于S的任何连续的长度为L1的子串sjsj+1…sj+L1-1(1≤j≤N-L1+1)，1的个数大于等于A1且小于等于B1;

例如，N=6,A0=1,B0=2,L0=3,A1=1,B1=1,L1=2，则存在一个满足上述所有条件的01串S=010101。


输入描述

仅一行，有7个整数，依次表示N,A0,B0,L0,A1,B1,L1（3 ≤ N ≤ 1000，1 ≤ A0 ≤ B0 ≤ L0 ≤ N，1 ≤ A1 ≤ B1 ≤ L1 ≤ N），相邻两个整数之间用一个空格分隔。

输出描述

仅一行，若不存在满足所有条件的01串，则输出一个整数-1，否则输出一个满足所有条件的01串。

示例1

输入: 

6 1 2 3 1 1 2

输出: 

101010

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 604K, 提交时间: 2019-01-07 18:12:34 

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=1001,MAXP=MAXN*10,INF=0x7FFFFFF;
using namespace std;
struct edge
{
    edge *next;
    int t,c;
}ES[MAXP];
struct vertex
{
    edge *f,*l;
    int sp;
}V[MAXN];
struct qlist
{
    qlist *next;
    int v;
};
int N,A[2],B[2],L[2],EC=-1,Q_Size;
bool Q_In[MAXN];
int RelaxCount[MAXN];
qlist *qf,*ql;
void Q_Insert_Tail(int v)
{
    if (Q_Size)
        ql=ql->next=new qlist;
    else
        qf=ql=new qlist;
    ql->next=0;
    ql->v=v;
    Q_Size++;
    Q_In[v]=true;
}
int Q_Pop()
{
    int r=qf->v;
    Q_In[r]=false;
    Q_Size--;
    qlist *t=qf;
    qf=qf->next;
    delete t;
    return r;
}
void init()
{
    scanf("%d%d%d%d%d%d%d",&N,&A[0],&B[0],&L[0],&A[1],&B[1],&L[1]);
}
inline void addedge(int a,int b,int c)
{
    if (V[a].l)
        V[a].l=V[a].l->next=&ES[++EC];
    else
        V[a].f=V[a].l=&ES[++EC];
    ES[EC].t=b; ES[EC].c=c;
}
void construct()
{
    int i;
    for (i=1;i<=N;i++)
    {
        addedge(0,i,N);
        if (i >= L[0])
        {
            addedge(i-L[0],i,L[0]-A[0]);
            addedge(i,i-L[0],B[0]-L[0]);
        }
        if (i >= L[1])
        {
            addedge(i,i-L[1],-A[1]);
            addedge(i-L[1],i, B[1]);
        }
        if (i < N)
        {
            addedge(i+1,i,0);
            addedge(i,i+1,1);
        }
    }
}
bool spfa()
{
    int u,v,c;
    for (u=1;u<=N;u++)
        V[u].sp=INF;
    V[0].sp=0;
    Q_Insert_Tail(0);
    while (Q_Size)
    {
        u=Q_Pop();
        for (edge *k=V[u].f;k;k=k->next)
        {
            v=k->t; c=k->c;
            if (V[u].sp + c < V[v].sp)
            {
                RelaxCount[v]++;
                if (RelaxCount[v]>=N)
                    return false;
                V[v].sp = V[u].sp + c;
                if (!Q_In[v])
                    Q_Insert_Tail(v);
            }
        }
    }
    return true;
}
void decode()
{
    int i,M=INF;
    for (i=1;i<=N;i++)
        if (V[i].sp<M)
            M=V[i].sp;
    for (i=1;i<=N;i++)
        V[i].sp-=M-1;
    for (i=1;i<=N;i++)
        printf("%d",V[i].sp-V[i-1].sp);
}
int main()
{
    init();
    construct();
    if (spfa())
        decode();
    else
        printf("-1");
    return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 672K, 提交时间: 2023-05-02 10:51:39 

#include<bits/stdc++.h>
using namespace std;
int n,a0,b0,l0,a1,b1,l1;
const int N=2e4+10;
int h[N],e[2*N],ne[2*N],w[2*N],idx;
int q[N],cnt[N];
int dist[N];
bool st[N];

void add(int a,int b,int c)
{
	e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;	
}

bool spfa()
{
	memset(dist,0x3f,sizeof dist);
	dist[0]=0;
	int hh=0,tt=0;
	q[++tt]=0;
	st[0]=true;
	
	while(hh != tt)
	{
		int t=q[tt--];
		st[t]=false;
		
		for(int i=h[t];i != -1;i=ne[i])
		{
			int j=e[i];
			
			if(dist[j] > dist[t]+w[i])
			{
				dist[j]=dist[t]+w[i];
				if(!st[j])
				{
					q[++tt]=j;
					st[j]=true;
				}
				
				cnt[j]++;
				if(cnt[j] >= n) return false;
			}
		}
	}
	
	return true;
}

int main()
{
	cin>>n>>a0>>b0>>l0>>a1>>b1>>l1;
	
	memset(h,-1,sizeof h);
	
	for(int i=1;i <= n;i++) add(i-1,i,1),add(i,i-1,0);
	for(int i=1;i+l0-1 <= n;i++) add(i+l0-1,i-1,b0-l0),add(i-1,i+l0-1,l0-a0);
	for(int i=1;i+l1-1 <= n;i++) add(i-1,i+l1-1,b1),add(i+l1-1,i-1,-a1);
	
	if(!spfa()) cout<<-1<<endl;
	else
	{
		for(int i=1;i <= n;i++)
		cout<<dist[i]-dist[i-1];
		cout<<endl;
	}
	
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 3ms, 内存消耗: 512K, 提交时间: 2023-05-01 17:24:55 

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int h[N],ne[2*N],e[2*N],w[2*N],idx,co[N],st[N],d[N],n;

void add(int a,int b,int c){
	e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}

bool spfa(){
	memset(d,0x3f,sizeof d);
	d[0]=0;
	queue<int> q;
	q.push(0);st[0]=1;
	while(q.size())
	{
		auto t=q.front();
		q.pop();
		st[t]=0;
		for(int i=h[t];i!=-1;i=ne[i]){
			int j=e[i];
			if(d[j]>d[t]+w[i]){
				d[j]=d[t]+w[i];
				co[j]++;
				if(co[j]>=n)	return false;
				if(!st[j]){
					st[j]=1;
					q.push(j);
				}
			}
		}
	}return true;
}

int main(){
	memset(h,-1,sizeof h);
	int	a0,b0,l0,a1,b1,l1;
	cin>>n>>a0>>b0>>l0>>a1>>b1>>l1;
	for(int i=1;i<=n;i++)	
		add(i-1,i,1),add(i,i-1,0);
	for(int l=1,r=l0;r<=n;l++,r++)
		add(r,l-1,b0-l0),add(l-1,r,l0-a0);
	for(int l=1,r=l1;r<=n;l++,r++)
		add(r,l-1,-a1),add(l-1,r,b1);
	if(spfa())	
		for(int i=1;i<=n;i++)	
			cout<<d[i]-d[i-1];
	else	cout<<-1<<endl;
	return 0;
}

上一题

© 2025 nowcoder.com