Dashboard - Codeforces Round 906 (Div. 2) - Codeforces

C. Qingshan Loves Strings 2

题意

给出一个n长的01串（$1 \le n \le 100$），每次操作向串中插入一个”01“（最多可以插入300次），问如何插入能够使得最终的串满足：对于任何$0\le i < len$ 都有$str[i] \not= str[len-1-i]$ 。 如果有合理的方案，则输出方案，否则输出-1。

思路

首先考虑特判，每次插入”01“ 不会改变0和1的数量关系， 而最终的串要求0和1的数量一样多。所以最初的0和1的数量也需要一样多。

然后考虑如下插入策略：由两边向中间靠拢，逐个检查每个字符。为了方便起见，我们使用$l$和$r$来代表待检查的左右字符的下标，

  1. 如果$str[l] \not= str[r]$ 则令 $l$++,$r$—,

  2. 如果$str[l] = str[r]$ ,则代表我们需要插入”01“串来干预。如果$str[l] = str[r] = ‘0’$ 那么就在第r+1位置插入”01“ ，这样新的r就是r+2，一定是1，满足$str[l] \not = str[r]$ , 相反，如果$str[l] = str[r] = ‘1’$,则在第l个位置前插入01。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define OI ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
void solve() { 
    int n;
    cin>> n;
    string str;
    cin>>str;
    if(n&1 || count(str.begin(),str.end(),'0') != count(str.begin(),str.end(),'1')) {cout<<-1<<endl;return ;} 
    int l = 0;
    int r = n - 1;
    vector<int> ans;
    while(l <= r){
        while(str[l] != str[r]) {l++;r--;}
        if(str[l] == '0'){
            str.insert(r+1,"01");
            ans.push_back(r + 1);
            r += 2;
        }
        if(str[l] == '1'){
            str.insert(l,"01");
            r += 2;
            ans.push_back(l);
        }
        l++;r--;
    }
    cout<<ans.size()<<endl;
    for(auto p : ans) cout<<p<<" ";
    cout << endl;
    return ;
}
signed main(){
    int T;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

D. Doremy’s Connecting Plan

题意

给出n个节点，需要你连接一些边使得整张图中任意两点之间是可达的。 当两个节点$(i,j)$满足如下条件时，这两个节点之间可以连边 ：
$\sum_{k \in S} a_k \ge c i j$ 。 其中S表示为此时从$i$ 或$j$ 可到达的节点集合。

如果可以通过某种连边顺序得到连通图就输出YES，否则输出NO

思路

贪心思想： 每次连边都令$i = 1$，这样我们只需要关注$j$的顺序就好 。 此时连边的条件变为$(\sum _{k \in S}a_k) + a_j \ge c j$ ,其中S为已经和$i$相连的节点。可以发现，我们何时将1与j相连，不等式右边不变，而左边则越晚相连越大。 因此我们将2~n号节点按照 $c j - a_j$ 从小到大排序，然后按顺序与1号节点相连，即为最优解法。最终只需要判断通过该解法能否全部相连即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define OI ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
typedef pair<int,int> PII;
int n,c;
bool cmp(PII p1,PII p2){
    return p1.first - p1.second * c > p2.first - p2.second * c;
}
void solve() { 
    cin>>n>> c;
    vector< pair<int,int> > vec(n+5);
    for(int i = 1;i<=n;i++){
        cin>>vec[i].first;
        vec[i].second = i;
    }
    sort(vec.begin()+2,vec.begin()+1+n,cmp);//按照cmp排序
    int sum = vec[1].first;
    for(int i = 2;i<=n;i++){
        if(sum + vec[i].first < vec[i].second * c){
            cout<<"No\n";
            return;
        }
        sum += vec[i].first;
    }
    cout<<"Yes\n";
    return ;
}
signed main(){
    int T;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}