6月11日 Educational Codeforces Round 45
题目链接:http://codeforces.com/contest/990

A – Commentary Boxes & B – Micro-World

过水,不多说。

C – Bracket Sequences Concatenation Problem

思路:
类似于模拟吧,不过思路一定要清晰(我弄错了很多次QWQ)。

可以用一个map记录有多少序列有x个左(右)括号未匹配,然后答案就可以通过这个计算得到。

代码:

#include <bits/stdc++.h>
#define LL long long 
#define MAXN 300005
#define INF 0x3f3f3f3f
using namespace std;

int n, l, r;
LL ans;
map<LL, LL> mp;
char s[MAXN];

int main()
{
    //freopen("a.in", "r", stdin);
    //freopen("a1.out", "w", stdout);
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        scanf("%s", s);
        int len=strlen(s), l=0, r=0;
        for(int j=0; j<len; j++)
        {
            if(r==0 && s[j]==')') l--;
            if(r!=0 && s[j]==')') r--;
            if(l==0 && s[j]=='(') r++;
            if(l!=0 && s[j]=='(') r++;
        }
        if(l==0 && r==0) mp[0]++;
        else
        {
            if(l==0) mp[r]++;
            if(r==0) mp[l]++;
        }
    }
    for(int i=0; i<=MAXN; i++)
    {
        ans+=mp[i]*mp[-i];
    }
    cout<<ans;
}

D – Graph And Its Complement

思路:
是一道结论题吧。可以考虑当n>3时如果a,b均不等于1,则该情况不存在。当n=1或n=2并且a=b=1时同样无解。

其余情况都是有解的,然后就考虑输出方案。这时a或b有一个为1,如果b为1就直接构造,否则构造后输出它的反图。

代码:

#include<bits/stdc++.h>
using namespace std;

int n, a, b, ans[1005][1005];
bool flag;

int main()
{
    scanf("%d%d%d", &n, &a, &b);
    if(a<b) swap(a, b), flag=1;
    if(b!=1 || ((n==2 || n==3) && (a==1 && b==1))) {printf("NO\n"); return 0;}
    printf("YES\n");
    for(int i=1; i<=n-a; i++)
    {
        ans[i][i+1]=1;
        ans[i+1][i]=1;
    }
    if(!flag)
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++) printf("%d", ans[i][j]);
            printf("\n");
        }
    }
    else
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                if(i==j) printf("0");
                else printf("%d", 1^ans[i][j]);
            }
            printf("\n");
        }
    }

} 

E – Post Lamps

思路:
也是一个比较简单的模拟+贪心。每一次放灯时尽量放右边,并且灯之间全要覆盖。要判一下能否符合要求,如果整个序列都符合要求,就更新一下答案。

代码:

#include <bits/stdc++.h>
#define INF 1e18
#define LL long long
#define lld I64d
#define MAXN 1000005
using namespace std;

LL n, m, k, temp, ans=INF, lef[MAXN], a[MAXN];
bool vis[MAXN];

LL solve(LL x)
{
    LL r=0, cnt=0, pos=-1;
    while(r<n)
    {
        if(pos>=lef[r]) return INF;
        pos=lef[r];
        r=pos+x;
        cnt++;
    }
    return cnt;
}

int main()
{
    scanf("%lld%lld%lld", &n, &m, &k);
    for(int i=1; i<=m; i++)
    {
        scanf("%lld", &temp);
        vis[temp]=true;
    }
    if(vis[0]) lef[0]=-1;
    for(int i=1; i<n; i++)
    {
        if(vis[i]) lef[i]=lef[i-1];
        else lef[i]=i;
    }
    for(int i=1; i<=k; i++) scanf("%lld", &a[i]);
    for(int i=1; i<=k; i++)
    {
        temp=solve(i);
        if(temp!=INF && ans>temp*a[i]) ans=temp*a[i];
    }
    if(ans==INF) printf("-1\n");
    else printf("%lld\n", ans);
}

发表评论

邮箱地址不会被公开。 必填项已用*标注