「贪心 / 构造」AHSOFNU 新生训练 by hzwer

2016年6月11日5,6483

简单题系列

比赛地址http://acm.hust.edu.cn/vjudge/contest/view.action?cid=119385#overview

其实codeforces的题完全不需要题解吧

「cf432A」Choosing Teams 组队

总共有n个人，每个人最多参加5场比赛，现在给出每个人已经参加过的比赛次数，现在要组尽量多的队伍去继续参加比赛，每支队伍三个人，要求组成的队伍至少再参加k场比赛。

一眼题

#include<iostream>
#include<cstdio>
using namespace std;
int n,k,x,tot;
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        if(x+k<=5)tot++;
    }
    printf("%d",tot/3);
    return 0;
}

#include<iostream>

#include<cstdio>

using namespace std;

int n,k,x,tot;

int main()

{

scanf("%d%d",&n,&k);

for(int i=1;i<=n;i++)

{

scanf("%d",&x);

if(x+k<=5)tot++;

}

printf("%d",tot/3);

return 0;

}

「cf508B」Anton and currency you all know 最大偶数

交换n的某俩个数位，求其能成为的最大偶数

选择一个在最前面、比最后一个数字小的偶数交换若不存在，选择最后一个偶数，将其与最后一个数字交换

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#define eps 1e-8
#define inf 1000000000
#define pa pair<int,int>
#define ll long long 
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,t;
char a[100005];
int b[100005];
void print()
{
    for(int i=1;i<=n;i++)
        printf("%d",b[i]);
}
int main()
{
    scanf("%s",a+1);
    n=strlen(a+1);
    for(int i=1;i<=n;i++)b[i]=a[i]-'0';
    t=b[n];
    for(int i=1;i<=n;i++)
        if(b[i]%2==0&&b[i]<t)
        {
            swap(b[i],b[n]);
            print();return 0;
        }
    for(int i=n;i;i--)
        if(b[i]%2==0)
        {
            swap(b[i],b[n]);
            print();return 0;
        }
    puts("-1");
    return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<vector>

#include<queue>

#include<algorithm>

#include<map>

#include<cmath>

#define eps 1e-8

#define inf 1000000000

#define pa pair<int,int>

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,t;

char a[100005];

int b[100005];

void print()

{

for(int i=1;i<=n;i++)

printf("%d",b[i]);

}

int main()

{

scanf("%s",a+1);

n=strlen(a+1);

for(int i=1;i<=n;i++)b[i]=a[i]-'0';

t=b[n];

for(int i=1;i<=n;i++)

if(b[i]%2==0&&b[i]<t)

{

swap(b[i],b[n]);

print();return 0;

}

for(int i=n;i;i--)

if(b[i]%2==0)

{

swap(b[i],b[n]);

print();return 0;

}

puts("-1");

return 0;

}

「cf401C」Team 01序列

构造一个01序列，包含n个0，m个1

要求不存在连续2个0，或3个1

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m;
int main()
{
    scanf("%d%d",&n,&m);
    if(double(m)/(n+1)>2||n>m+1){printf("-1");return 0;}
    if(n>m){printf("0");n--;}
    int t=m-n-2;
    for(int i=1;i<=t;i++){printf("110");n--;m-=2;}
    t=min(n,m);
    for(int i=1;i<=t;i++){printf("10");n--;m--;}
    while(m--)printf("1");
    return 0;
}

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

int n,m;

int main()

{

scanf("%d%d",&n,&m);

if(double(m)/(n+1)>2||n>m+1){printf("-1");return 0;}

if(n>m){printf("0");n--;}

int t=m-n-2;

for(int i=1;i<=t;i++){printf("110");n--;m-=2;}

t=min(n,m);

for(int i=1;i<=t;i++){printf("10");n--;m--;}

while(m--)printf("1");

return 0;

}

「cf500C」New Year Book Reading 栈

一个人m天要读n本书每本书重量wi，每天读1本，他每天把要看的书x从栈里拿出来（拿起x上面的，拿出x，再把上面的书放回去），看完x后放到栈顶，问根据他的阅读顺序怎样初始化书的排列顺序能使他搬书的总重量最小，输出总重量

结论：初始把先看的书放在最上方

第一本书放栈顶显然没问题，考虑要阅读的第二本不同的书，显然放在第一本下面。

假设已经放了要看的前i-1本书，考虑第i本，如果插在前i-1本之中，把它拿出来显然更优，于是就能归纳出结论。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#define eps 1e-6
#define inf 1000000000
#define pa pair<int,int>
#define ll long long 
using namespace std;
ll read()
{
    ll x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
int n,m,ans,top;
int a[1005],b[1005],q[1005];
bool mark[1005];
void Lift(int x)
{
	int tmp=x;
	for(int i=1;i<=top;i++)
	{
		if(q[i]==tmp){x=i;break;}
	}
	for(int i=x-1;i>=1;i--)
	{
		ans+=a[q[i]];
		q[i+1]=q[i];
	}
	q[1]=tmp;
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=m;i++)b[i]=read();
    for(int i=1;i<=m;i++)
	{
		if(!mark[b[i]])q[++top]=b[i];
		mark[b[i]]=1;
	}
	for(int i=1;i<=m;i++)Lift(b[i]);
    printf("%d\n",ans);
    return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<vector>

#include<queue>

#include<algorithm>

#include<map>

#include<cmath>

#define eps 1e-6

#define inf 1000000000

#define pa pair<int,int>

#define ll long long

using namespace std;

ll read()

{

ll x=0;char ch=getchar();

while(ch<'0'||ch>'9')ch=getchar();

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x;

}

int n,m,ans,top;

int a[1005],b[1005],q[1005];

bool mark[1005];

void Lift(int x)

{

int tmp=x;

for(int i=1;i<=top;i++)

{

if(q[i]==tmp){x=i;break;}

}

for(int i=x-1;i>=1;i--)

{

ans+=a[q[i]];

q[i+1]=q[i];

}

q[1]=tmp;

}

int main()

{

n=read();m=read();

for(int i=1;i<=n;i++)a[i]=read();

for(int i=1;i<=m;i++)b[i]=read();

for(int i=1;i<=m;i++)

{

if(!mark[b[i]])q[++top]=b[i];

mark[b[i]]=1;

}

for(int i=1;i<=m;i++)Lift(b[i]);

printf("%d\n",ans);

return 0;

}

「cf482A」Diverse Permutation 全排列

求n的一个全排列，使其两两之间存在K种差值

1-n最多凑出n-1种差值所以让前k+1项差值为1到k，后面的差值全为1

形如1 7 2 6 3 5 4这样差值是6 5 4 3 2 1

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define mod 1000000007
#define ll long long 
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int t1,t2;
int n,k,now;
int a[100005];
int main()
{
    n=read();k=read();
    for(int i=1;i<=n;i++)a[i]=i;
    k++;
    now=0;
    if(k&1)
    {
		t1=t2=a[++now]=(k+1)/2;
		t1--;t2++;
    }
    else t1=k/2,t2=t1+1;
    for(int i=1;i<=k/2;i++)
		a[++now]=t1,a[++now]=t2,t1--,t2++;
    for(int i=1;i<=n;i++)printf("%d ",a[i]);
    return 0;
}

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#define mod 1000000007

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int t1,t2;

int n,k,now;

int a[100005];

int main()

{

n=read();k=read();

for(int i=1;i<=n;i++)a[i]=i;

k++;

now=0;

if(k&1)

{

t1=t2=a[++now]=(k+1)/2;

t1--;t2++;

}

else t1=k/2,t2=t1+1;

for(int i=1;i<=k/2;i++)

a[++now]=t1,a[++now]=t2,t1--,t2++;

for(int i=1;i<=n;i++)printf("%d ",a[i]);

return 0;

}

「cf235A」LCM Challenge 最大公约数

求三个不同的小于n的数字，使它们的lcm最大

显然是在接近n数内找三个两两互质的，由于懒得推公式所以可以小范围暴力一下

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define mod 1000000007
#define inf 1000000000
#define ll long long
using namespace std;
ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int n;
ll ans;
ll gcd(ll a,ll b)
{
    return b==0?a:gcd(b,a%b);
}
int main()
{
    n=read();
    int m=max(1,n-100);
    ans=n;
    for(int i=m;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            if(gcd(i,j)==1)
            for(int k=j+1;k<=n;k++)
                if(gcd(k,i)==1&&gcd(k,j)==1)
                    ans=max(ans,(ll)i*j*k);
    cout<<ans<<endl;
    return 0;
}

#include<map>

#include<set>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define mod 1000000007

#define inf 1000000000

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char c=getchar();

while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}

return x*f;

}

int n;

ll ans;

ll gcd(ll a,ll b)

{

return b==0?a:gcd(b,a%b);

}

int main()

{

n=read();

int m=max(1,n-100);

ans=n;

for(int i=m;i<=n;i++)

for(int j=i+1;j<=n;j++)

if(gcd(i,j)==1)

for(int k=j+1;k<=n;k++)

if(gcd(k,i)==1&&gcd(k,j)==1)

ans=max(ans,(ll)i*j*k);

cout<<ans<<endl;

return 0;

}

「cf468A」24 Game 24点

用1-n得出24点

思路就是用1-4得出24，剩下的互相抵消

发现每4个可以a+1,a+2,a+3,a+4可以消掉，加上中间俩个，减去两边两个，所以我讨论了模4后的4种情况

事实上可以分奇偶讨论。。a+1,a+2可以通过 *（a+2-(a+1)）消去。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define inf 1000000000
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n;
void print(int x)
{
    int now=24;
    for(int i=1;i<=(n-x)/2;i++)
        {
            if(i&1)
            {   
                printf("%d + %d = %d\n",now,i+x,now+i+x);now+=i+x;
                printf("%d + %d = %d\n",now,n-i+1,now+n-i+1);now+=n-i+1;
            }
            else 
            {
                printf("%d - %d = %d\n",now,i+x,now-(i+x));now-=i+x;
                printf("%d - %d = %d\n",now,n-i+1,now-(n-i+1));now-=n-i+1;
            }
        }
}
int main()
{
    n=read();
    if(n<=3){puts("NO");return 0;}
    else puts("YES");
    if(n%4==0)
    {
        puts("1 + 2 = 3");
        puts("3 + 3 = 6");
        puts("4 * 6 = 24");
        print(4);
    }
    else if(n%4==1)
    {
        puts("5 - 2 = 3");
        puts("3 - 1 = 2");
        puts("3 * 4 = 12");
        puts("12 * 2 = 24");
        print(5);
    }
    else if(n%4==2)
    {
        puts("1 + 5 = 6");
        puts("6 - 6 = 0");
        puts("2 * 3 = 6");
        puts("4 * 6 = 24");
        puts("24 + 0 = 24");
        print(6);
    }
    else 
    {
        puts("4 * 6 = 24");
        puts("2 * 5 = 10");
        puts("10 - 7 = 3");
        puts("3 - 3 = 0");
        puts("24 + 0 = 24");
        puts("24 * 1 = 24");
        print(7);
    }
    return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#define inf 1000000000

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n;

void print(int x)

{

int now=24;

for(int i=1;i<=(n-x)/2;i++)

{

if(i&1)

{

printf("%d + %d = %d\n",now,i+x,now+i+x);now+=i+x;

printf("%d + %d = %d\n",now,n-i+1,now+n-i+1);now+=n-i+1;

}

else

{

printf("%d - %d = %d\n",now,i+x,now-(i+x));now-=i+x;

printf("%d - %d = %d\n",now,n-i+1,now-(n-i+1));now-=n-i+1;

}

int main()

{

n=read();

if(n<=3){puts("NO");return 0;}

else puts("YES");

if(n%4==0)

{

puts("1 + 2 = 3");

puts("3 + 3 = 6");

puts("4 * 6 = 24");

print(4);

}

else if(n%4==1)

{

puts("5 - 2 = 3");

puts("3 - 1 = 2");

puts("3 * 4 = 12");

puts("12 * 2 = 24");

print(5);

}

else if(n%4==2)

{

puts("1 + 5 = 6");

puts("6 - 6 = 0");

puts("2 * 3 = 6");

puts("4 * 6 = 24");

puts("24 + 0 = 24");

print(6);

}

else

{

puts("4 * 6 = 24");

puts("2 * 5 = 10");

puts("10 - 7 = 3");

puts("3 - 3 = 0");

puts("24 + 0 = 24");

puts("24 * 1 = 24");

print(7);

}

return 0;

}

「cf639C」Bear and Polynomials 多项式

在差的绝对值为K范围内修改一个多项式Q的某一系数，使得Q(2)=0

先全部进位一下，然后找出最低位的1，不可能改动比它高位的系数

比它低位的系数依次枚举一下

注意超过2K就直接退出

#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define pi acos(-1)
#define eps 1e-13
#define mod 10000007
#define inf 1000000000
#define ll long long
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,K;
int a[200005],b[200005],ans;
int main()
{
    n=read();K=read();
    for(int i=0;i<=n;i++)a[i]=read();
    b[0]=a[0];
    for(int i=1;i<=n;i++)
    {
        b[i]=a[i]+b[i-1]/2;
        b[i-1]%=2;
    }
    int fir=0;
    ll res=0;
    for(int i=0;i<=n;i++)
        if(b[i])
        {
            fir=i;break;
        }
    for(int i=n;i>=fir;i--)
    {
        res*=2;
        res+=b[i];
        if(abs(res)>2*K){puts("0");return 0;}
    }
    if(fir==n&&a[n]==res)ans--;
    for(int i=fir;i>=0;i--)
    {
        if(abs(a[i]-res)<=K)ans++;
        res*=2;
        if(abs(res)>2*K)break;
    }
    printf("%d\n",ans);
    return 0;
}

#include<map>

#include<set>

#include<cmath>

#include<stack>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define pi acos(-1)

#define eps 1e-13

#define mod 10000007

#define inf 1000000000

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,K;

int a[200005],b[200005],ans;

int main()

{

n=read();K=read();

for(int i=0;i<=n;i++)a[i]=read();

b[0]=a[0];

for(int i=1;i<=n;i++)

{

b[i]=a[i]+b[i-1]/2;

b[i-1]%=2;

}

int fir=0;

ll res=0;

for(int i=0;i<=n;i++)

if(b[i])

{

fir=i;break;

}

for(int i=n;i>=fir;i--)

{

res*=2;

res+=b[i];

if(abs(res)>2*K){puts("0");return 0;}

}

if(fir==n&&a[n]==res)ans--;

for(int i=fir;i>=0;i--)

{

if(abs(a[i]-res)<=K)ans++;

res*=2;

if(abs(res)>2*K)break;

}

printf("%d\n",ans);

return 0;

}

「cf508E」Arthur and Brackets

给出一些括号，这个括号左括号的先后顺序确定，左右括号的距离的范围确定，构造一种合法的方案。

经过尝试构造后发现。。。

将括号的dis设小不会更劣

如（（））变成（）（）更有利于加入其它的括号

于是从后往前依次考虑每个括号，使得它尽量包含少的括号

复杂度n^2

其实知道上面的结论以后，用个栈贪心即可，具体看下面第二个代码。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#define eps 1e-8
#define inf 1000000000
#define pa pair<int,int>
#define ll long long 
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n;
vector<int> st;
int ans[605],q[1205];
int l[605],r[605];
bool mark[605];
void print()
{
	int now=1;
	for(int i=1;i<=n;i++)
	{
		while(q[now])now++;
		q[now]=1;q[now+ans[i]]=-1;
	}
	for(int i=1;i<=2*n;i++)
		if(q[i]==1)printf("(");
		else printf(")");
}
bool solve(int t)
{
	st.clear();
	int tot=0;
	if(l[t]==1){ans[t]=1;return 1;}
	if(ans[t])return 1;
	for(int j=t+1;j<=n&&tot+1<l[t];j++)
		if(ans[j])
		{
			if(!mark[j]){tot+=ans[j]+1;st.push_back(j);}
		}
		else return 1;
	tot++;
	if(tot<l[t]||tot>r[t])return 0;
	for(int i=0;i<st.size();i++)
		mark[st[i]]=1;
	ans[t]=tot;
	return 1;
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)
	{
		l[i]=read(),r[i]=read();
		if(l[i]%2==0)l[i]++;
	}
	for(int x=n;x;x--)
		if(!solve(x)){puts("IMPOSSIBLE");return 0;}
	print();
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<vector>

#include<queue>

#include<algorithm>

#include<map>

#include<cmath>

#define eps 1e-8

#define inf 1000000000

#define pa pair<int,int>

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n;

vector<int> st;

int ans[605],q[1205];

int l[605],r[605];

bool mark[605];

void print()

{

int now=1;

for(int i=1;i<=n;i++)

{

while(q[now])now++;

q[now]=1;q[now+ans[i]]=-1;

}

for(int i=1;i<=2*n;i++)

if(q[i]==1)printf("(");

else printf(")");

}

bool solve(int t)

{

st.clear();

int tot=0;

if(l[t]==1){ans[t]=1;return 1;}

if(ans[t])return 1;

for(int j=t+1;j<=n&&tot+1<l[t];j++)

if(ans[j])

{

if(!mark[j]){tot+=ans[j]+1;st.push_back(j);}

}

else return 1;

tot++;

if(tot<l[t]||tot>r[t])return 0;

for(int i=0;i<st.size();i++)

mark[st[i]]=1;

ans[t]=tot;

return 1;

}

int main()

{

n=read();

for(int i=1;i<=n;i++)

{

l[i]=read(),r[i]=read();

if(l[i]%2==0)l[i]++;

}

for(int x=n;x;x--)

if(!solve(x)){puts("IMPOSSIBLE");return 0;}

print();

return 0;

}

栈

#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define pi acos(-1)
#define mod 10000007
#define inf 1000000000
#define ll long long
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,top;
struct data{
    int l,r,pos;
}a[605];
int q[605];
char ch[1205];int l;
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        a[i].l=read();a[i].r=read();
        q[++top]=i;
        a[i].pos=l;
        ch[++l]='(';
        while(top&&a[q[top]].pos+a[q[top]].l<=l)
        {
            if(a[q[top]].pos+a[q[top]].r<l)
            {
                puts("IMPOSSIBLE");
                return 0;
            }
            ch[++l]=')';
            top--;
        }
    }
    if(top)puts("IMPOSSIBLE");
    else printf("%s",ch+1);
    return 0;
}

#include<map>

#include<set>

#include<cmath>

#include<stack>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define pi acos(-1)

#define mod 10000007

#define inf 1000000000

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,top;

struct data{

int l,r,pos;

}a[605];

int q[605];

char ch[1205];int l;

int main()

{

n=read();

for(int i=1;i<=n;i++)

{

a[i].l=read();a[i].r=read();

q[++top]=i;

a[i].pos=l;

ch[++l]='(';

while(top&&a[q[top]].pos+a[q[top]].l<=l)

{

if(a[q[top]].pos+a[q[top]].r<l)

{

puts("IMPOSSIBLE");

return 0;

}

ch[++l]=')';

top--;

}

if(top)puts("IMPOSSIBLE");

else printf("%s",ch+1);

return 0;

}

« 「CF639X」VK Cup 2016 – Round 1 2013PKU计算概论入学测试 »

某弱

orz，黄学长今年高考如何？

hzwer

血崩

江户川柯南

Orz黄学长

hzwer.com _ Home | http://hzwer.com

「贪心 / 构造」AHSOFNU 新生训练 by hzwer

分类目录

热门文章

Myfriends

近期评论