A-E题解

标签：Code int 题解 void cin solve View

A：对于任意一个满足条件的2*2矩阵，要么3个R和1个W，要么3个W和1个R。

我们以3个R和1个W举例，只有以下4中情况满足：

RR     RR     RW     WR
RW    WR    RR      RR

所以一种构造方法如下：

奇数行全部放R；偶数行奇数列放R，偶数列放W即可。

void solve() {
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i&1) cout<<'R';
            else{
                if(j&1) cout<<'R';
                else cout<<'W';
            }
        }
        cout << endl;
    }
}

View Code

 

 

B：一个很经典的贪心问题。给定一段时间和很多事件，每个事件都有开始时间和结束时间。

问你在这段事件内最多能完成多少个事件。

我们将事件按照结束时间从小到大排序，然后贪心的取即可。

struct node {
    int l,r;
    bool operator < (const node & a) const {
        return r < a.r;
    }
}k[N];
 
void solve() {
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=m;i++) cin >> k[i].l >> k[i].r;
    sort(k+1,k+m+1);
    int last=k[1].r , ans=1;
    for(int i=2;i<=m;i++) {
        int l = k[i].l , r = k[i].r;
        if(l>=last) last = r , ans++;
    }
    cout << ans << endl;
}

View Code

 

 

C：我们将每个故事按照故事大小排序，然后贪心的从小到大取即可。但是由于数据范围很大，直接暴力找会TLE。所以我们对故事按照从小到大求个前缀和，每次二分的去找可以一本书可以出多少个故事即可。

void solve() {
    int n,k;
    cin >> n >> k;
    vector<int> a(n+1) , b(n+10);
    for(int i=1;i<=n;i++) cin >> a[i];
    sort(a.begin()+1,a.end());
    for(int i=1;i<=n;i++) b[i] = b[i-1] + a[i];
    while(k--) {
        int x;
        cin >> x;
        int l=1 , r=n;
        while(l<=r){
            int mid = l+r >> 1;
            if(b[mid]>x) r = mid - 1;
            else l = mid + 1;
        }
        cout << r << ' ';
    }
}

View Code

 

 

D：给你一个只包含’ ( ’和’ ) ’的字符串，问该字符串是否是合法括号序列。（我记得C语言讲过课讲过）。

用栈维护一下即可，最后判一下栈是否非空。

void solve() {
    int n;
    string s;
    cin >> n >> s;
    stack<int> st;
    for(int i=0;i<s.size();i++) {
        if(s[i]=='(') st.push(i);
        else {
            if(st.empty()) {
                cout << "NO" << endl;
                return ;
            }
            else st.pop();
        }
    }
    if(st.size()) cout << "NO" << endl;
    else cout << "YES" << endl;
}

View Code

 

 

E：n支队伍，两两比赛。实力高的得3分，实力相同的双方都得一分。教练训练一次某支队伍，可以让该队伍实力加一。问：如果想让最后所有选手得分之和最高，教练最少训练几次。

很明显只要让所有队伍实力两两不相同即可。

将数组从小到大排序，每次若当前队伍实力小于等于上一支队伍，我们将该队伍实力变为上一支队伍实力加一，记录答案。

void solve() {
    int n;
    cin >> n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a.begin()+1,a.end());
    int ans=0;
    for(int i=2;i<=n;i++) {
        if(a[i]<=a[i-1]) ans+=a[i-1]+1-a[i] , a[i]=a[i-1]+1;
    }
    cout << ans << endl;
}

View Code

 

标签：Code,int,题解,void,cin,solve,View
From： https://www.cnblogs.com/lzywakaka/p/18039963