当前位置：首页 > news >正文

Code Jam 2020 Qualification Round

news 来源：原创 2024/5/19 19:01:12

比赛链接

Vestigium（签到）

在这里插入图片描述
简单模拟

#include <iostream>
#include <cstring>
using namespace std;
int a[105][105];
int vis[105];

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t,n,kase=0;
    cin>>t;
    while(t--){
        int r=0,c=0,sum=0;
        cin>>n;
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
            if(i==j) sum+=a[i][j];
        }

        for(int i=1;i<=n;i++){
            memset(vis,0,sizeof vis);
            for(int j=1;j<=n;j++){
                if(!vis[a[i][j]]) vis[a[i][j]]=1;
                else{
                    r++;
                    break;
                }
            }
        }
        for(int i=1;i<=n;i++){
            memset(vis,0,sizeof vis);
            for(int j=1;j<=n;j++){
                if(!vis[a[j][i]]) vis[a[j][i]]=1;
                else{
                    c++;
                    break;
                }
            }
        }
        cout<<"Case #"<<++kase<<": "<<sum<<" "<<r<<" "<<c<<endl;
    }
    return 0;
}

Nesting Depth（规律/分治）

在这里插入图片描述
1.题目大意：给出一个序列，现在让按要求每个数字都必须被当前数字数量的括号包含，除此之外还要使整体括号数量最少，输出答案

方法一(标答)

假设该序列全是"01"序列，我们可以在每组1前加一个开头的括号，在后面加一个结尾的括号。我们可以用下面的小窍门来简化实现：在S的前面加上并附加一个额外的0，那么实现时只需将01替换成0(1，10替换成1)0即可，在一些编程语言中，可以用一行代码来写。不要忘了把生成的字符串尾部多出的0去掉!

对于整个数据范围，为了方便起见，让我们再一次使用上面描述的技巧：在S前加上并附加额外的0，然后从左到右扫描S。假设我们看到一些数字A紧随其后的是一些较大的数字B，并且假设之前插入的所有小括号都将使A处于正确的嵌套深度–也就是说，在A前面正好有A的开头小括号不匹配，而没有未匹配的结尾小括号。要使B处于嵌套深度B，我们至少需要在B-A的开头括号中加上B-A的开头括号。我们可以只做这个，其他的都不用做，以保持最后的字符串长度最小。任何额外的开端括号都需要在B之前加上，这样会不必要地延长字符串的长度。同样的，如果我们看到一些数字A后面紧跟着一些小的数字B，我们可以在A-B的闭合括号中插入A-B。而在A等于B的情况下，我们不需要加任何东西。我们不需要在开头的临时0之前加上括号，也不需要在结尾的括号后面加上括号，所以我们可以在打印结果前把它们去掉。因为我们只在至少需要p个括号的时候才添加p个括号，所以得到的字符串长度是最小的

#include <cmath>
#include <cstring>
#include <iostream>
#include <string>
using namespace std;
const int N = 105;
string s;
int lnum[N], rnum[N];
int T;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >> T;
    for (int Case = 1; Case <= T; Case++) {
        s.clear();
        memset(lnum, 0, sizeof(lnum));
        memset(rnum, 0, sizeof(rnum));
        cin >> s;
        s = "0" + s + "0";
        int len = s.length();
        for (int i = 0; i < len - 1; i++) {
            if (s[i] < s[i + 1])
                lnum[i] += s[i + 1] - s[i];
            else if (s[i] > s[i + 1])
                rnum[i] += s[i] - s[i + 1];
        }
        cout << "Case #" << Case << ": ";
        while (lnum[0]--)
            cout << '(';
        for (int i = 1; i < len - 1; i++) {
            cout << s[i];
            while (lnum[i]--)
                cout << '(';
            while (rnum[i]--)
                cout << ')';
        }
        cout << endl;
    }
    return 0;
}

方法二(分治)

我一开始没找到规律。后来自己推，首先缩小长度，肯定是一段不含0的区间，而且该区间只能对区间内最小的数消括号，也就是添加在首尾，那么这时最小的数处相当于变成了0。上述区间又被分成若干个连续不为0的小区间，为了解决这个问题我们可以分而治之，使用dfs递归遍历所有操作的区间，时间复杂度O(n²)

主要思路是设置两个数组L和R记录每个位置左边右边的括号数量，处理时每次找到最小的数并将区间所有数减去该数，更新区间最左边的L和最右边的R，递归求解即可

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define INF 0x3f3f3f3f
char s[105];
int a[105],L[105],R[105];
void dfs(int,int);

void solve(int l,int r){
    if(l==r){
        L[l]+=a[l];
        R[l]+=a[l];
        return;
    }
    int m=INF;
    for(int i=l;i<=r;i++){
        m=min(a[i],m);
    }
    L[l]+=m; R[r]+=m;
    for(int i=l;i<=r;i++) a[i]-=m;
    dfs(l,r);
}

void dfs(int l,int r){
    if(l==r){
        L[l]+=a[l];
        R[l]+=a[l];
        return;
    }
    for(int i=l;i<=r;i++){
        if(!a[i]) continue;
        int j=i+1;
        while(j<=r && a[j]) j++;
        solve(i,j-1);
        i=j;
    }
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t,kase=0;
    cin>>t;
    while(t--){
        cin>>s;
        for(int i=0;i<strlen(s);i++)
            a[i+1]=s[i]-'0';
        memset(L,0,sizeof L);
        memset(R,0,sizeof R);
        dfs(1,strlen(s));
        cout<<"Case #"<<++kase<<": ";
        for(int i=0;i<strlen(s);i++){
            for(int j=1;j<=L[i+1];j++) cout<<'(';
            cout<<s[i];
            for(int j=1;j<=R[i+1];j++) cout<<')';
        }
        cout<<endl;
    }
    return 0;
}

Parenting Partnering Returns

在这里插入图片描述
1.题目大意：给出若干段时间区间，只有两个人，一个人在做某区间的事时不能分心，判断两人能否不冲突的情况下完成所有区间，注意到区间是左闭右开的，也就是区间右端点不计入区间

2.区间问题，明显是贪心。考虑到必须从开始较早的区间开始，那么就需要对左端点升序处理，相等时右端点升序，且记录ID。那么可以从任意一个人开始，记录他俩的结束时间，如果下一段区间的起点开始时两个至少有一个空闲，则分配即可，都空闲可以任意分配。否则就是IMPOSSIBLE

#include <iostream>
#include <set>
#include <cstring>
#include <algorithm>
using namespace std;
struct node{
    int l,r;
    int id;
}line[1005];

int ans[1005];

bool cmp(node &a,node &b){
    if(a.l==b.l) return a.r<b.r;
    return a.l<b.l;
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t,n,kase=0;
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>line[i].l>>line[i].r;
            line[i].id=i;
        }
        sort(line+1,line+n+1,cmp);
        int flag=0,end1=line[1].r,end2=0;
        ans[line[1].id]=1;
        for(int i=2;i<=n;i++){
            if(line[i].l>=end1) ans[line[i].id]=1,end1=line[i].r;
            else if(line[i].l>=end2) ans[line[i].id]=2,end2=line[i].r;
            else{
                flag=1;
                break;
            }
        }
        cout<<"Case #"<<++kase<<": ";
        if(flag){
            cout<<"IMPOSSIBLE\n";
            continue;
        }else{
            for(int i=1;i<=n;i++){
                if(ans[i]==1) cout<<"C";
                else cout<<"J";
            }
        }
        cout<<"\n";
    }

    return 0;
}