第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（沈阳），签到题4题_witchwoodg.thewitchwoodc语言解法

补题链接：https://ac.nowcoder.com/acm/contest/18713
https://codeforces.com/gym/103202

G.The Witchwood

G. The Witchwood
time limit per test2 seconds
memory limit per test1024 megabytes
inputstandard input
outputstandard output
Shenyang’s night fair culture is developed very well. Every time Bob comes to Shenyang, he will definitely go to a night fair called The Witchwood. There are n snack stalls in The Witchwood, the ith of which gives him ai pleasure.

Bob’s stomach allows him to eat k snack stalls at most. So Bob wants to know the maximum pleasure he can get after visiting the night market.

Input
The first line of input contains two integers n (1≤n≤1000) and k (1≤k≤n), indicating the number of snack stalls and the capacity of Bob’s stomach.

The second line of input contains n integers a1,a2,…,an (1≤ai≤109), the ith of which indicates the pleasure of the ith snack stall.

Output
Print one integer denoting the maximum pleasure Bob can get.

Example
inputCopy
5 2
9 8 10 2 4
outputCopy
19

题意：

• 给你一个数列，求前k大的数之和。

思路：

• 排个序相加后输出即可。
• 不开longlong会WA2

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e6+10;
LL a[N];
void solve(){
    int n, k;   cin>>n>>k;
    for(int i = 1; i <= n; i++)cin>>a[i];
    sort(a+1,a+n+1, [&](int x, int y){
        return x>y;
    });
    LL res = 0;
    for(int i = 1; i <= k; i++){
        res += a[i];
    }
    cout<<res;
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T=1;  //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}


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

F.Kobolds and Catacombs

F. Kobolds and Catacombs
time limit per test2 seconds
memory limit per test1024 megabytes
inputstandard input
outputstandard output
Kobolds are rat-like, candle-loving cave folk, digging deep beneath the surface for millennia. Today, they gather together in a queue to explore yet another tunnel in their catacombs!

But just before the glorious movement initiates, they have to arrange themselves in non-descending heights. The shortest is always the leader digging small holes, and the followers swelling it.

The kobolds are hyperactive; they like to move here and there. To make the arrangement easier, they decide to group themselves into consecutive groups first, then reorder in each group.

What’s the maximum number of consecutive groups they can be partitioned into, such that after reordering the kobolds in each group in non-descending order, the entire queue is non-descending?

For example, given a queue of kobolds of heights [1, 3, 2, 7, 4], we can group them into three consecutive groups ([1] [3, 2] [7, 4]), such that after reordering each group, the entire queue can be non-descending.

Input
The first line of the input contains a single integer n (1≤n≤106), denoting the number of kobolds.

The second line contains n integers a1,a2,…,an (1≤ai≤109), representing the heights of the kobolds in the queue.

Output
Print a single integer, denoting the maximum number of groups.

Example
inputCopy
5
1 3 2 7 4
outputCopy
3

题意：

• 给出一个序列，将序列划分成尽可能多的连续子段，要求满足对各个子段进行独立排序后（升序），整个序列也是有序（升序）的。
• 输出最多能划分成多少段。

思路：

• 直观的想法是将序列与排好序的序列进行比较，一个元素本来在i，排序后到了j，那么i-j这段区间肯定都是必须属于同一个子区间的，即没办法被划分开来的。但是写起来可能比较麻烦。
• 实现的时候，考虑用前缀和优化，即排序后的序列的前缀和和原序列的前缀和，对于一段能划分的位置的分界线的地方，应该是相等的（因为对应区间的元素是相同的）。
  那么只要扫一遍前缀和，遇到相等的地方就+1，最后就是答案。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e6+10;
LL a[N], s[N], ss[N];
void solve(){
    int n;  cin>>n;
    for(int i = 1; i <= n; i++){
        cin>>a[i];  s[i] = s[i-1]+a[i];
    }
    sort(a+1,a+n+1);
    for(int i = 1; i <= n; i++){
        ss[i] = ss[i-1]+a[i];
    }
    LL res = 0;
    for(int i = 1; i <= n; i++){
        if(s[i]==ss[i])res++;
    }
    cout<<res;
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T=1;  //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
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

K.Scholomance Academy

Scholomance Academy
Input file: standard input
Output file: standard output
Time limit: 4 seconds
Memory limit: 1024 megabytes
As a student of the Scholomance Academy, you are studying a course called Machine Learning. You are
currently working on your course project: training a binary classifier.
A binary classifier is an algorithm that predicts the classes of instances, which may be positive (+) or
negative (-). A typical binary classifier consists of a scoring function S that gives a score for every instance
and a threshold θ that determines the category. Specifically, if the score of an instance S(x) ≥ θ, then
the instance x is classified as positive; otherwise, it is classified as negative. Clearly, choosing different
thresholds may yield different classifiers.
Of course, a binary classifier may have misclassification: it could either classify a positive instance as
negative (false negative) or classify a negative instance as positive (false positive).
Predicted class
Actual class Positive Negative
Positive True positive (TP) False negative (FN )
Negative False positive (FP) True negative (TN )
Таблица 1: Predicted classes and actual classes.
Given a dataset and a classifier, we may define the true positive rate (TPR) and the false positive rate
(FPR) as follows:
TPR = #TP
#TP + #FN
, FPR = #FP
#TN + #FP
where #TP is the number of true positives in the dataset; #FP, #TN , #FN are defined likewise.
Now you have trained a scoring function, and you want to evaluate the performance of your classifier.
The classifier may exhibit different TPR and FPR if we change the threshold θ. Let TPR(θ), FPR(θ) be
the TPR, FPR when the threshold is θ, define the area under curve (AUC) as
AUC = Z 1
0
max
θ∈R
{TPR(θ)|FPR(θ) ≤ r}dr
where the integrand, called receiver operating characteristic (ROC), means the maximum possible of TPR
given that FPR ≤ r.
Given the actual classes and predicted scores of the instances in a dataset, can you compute the AUC of
your classifier?
For example, consider the third test data. If we set threshold θ = 30, there are 3 true positives, 2 false
positives, 2 true negatives, and 1 false negative; hence, TPR(30) = 0.75 and FPR(30) = 0.5. Also, as θ
varies, we may plot the ROC curve and compute the AUC accordingly, as shown in Figure 1.
Input
The first line contains a single integer n (2 ≤ n ≤ 106
), the number of instances in the dataset. Then
follow n lines, each line containing a character c ∈ {+, -} and an integer s (1 ≤ s ≤ 109
), denoting the
actual class and the predicted score of an instance.
It is guaranteed that there is at least one instance of either class.
Output
Print the AUC of your classifier within an absolute error of no more than 10−9
.
Page 1 of 2

Рис. 1: ROC and AUC of the third sample data.
Examples
standard input standard output
3

• 2

• 3
• 1
  0.5
  6

• 7

• 2
• 5

• 4

• 2

• 6
  0.888888888888889
  8
• 34
• 33
• 26

• 34
• 38

• 39

• 7

题意：

• 讲的是一个机器学习的问题，FTP和TPR的计算规则，然后得到一个ROC曲线和AUC面积。
  具体可以参考这个：https://gwj1314.blog.csdn.net/article/details/127676843
• 大致就是给出样本，然后按照规则算一下面积输出，读懂题意就是模拟题，阅读理解题。

思路：

• 按照题意模拟计算即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e6+10;
void solve(){
    int n;  cin>>n;
    vector<double>v1, v2;
    for(int i = 1; i <= n; i++){
        string op; int x;  cin>>op>>x;
        if(op=="+")v1.push_back(x);
        else v2.push_back(x);
    }
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    double res = 0;
    for(int i = 0; i < v1.size(); i++){
        res += lower_bound(v2.begin(), v2.end(), v1[i])-v2.begin();
    }
    res = res/(double)v1.size()/(double)v2.size();
    printf("%.10lf\n", res);
}

int main(){
    // ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T=1;  //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
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

D.Journey to Un’Goro

D. Journey to Un’Goro
time limit per test2 seconds
memory limit per test1024 megabytes
inputstandard input
outputstandard output
Recently, you’ve taken a trip to Un’Goro.

A small road in Un’Goro has attracted your eyes. The road consists of n steps, each colored either red or blue.

When you go from the ith step to the jth, you count the number of red steps you’ve stepped. You will be satisfied if the number is odd.

“What is the maximum number of pairs (i,j) (1≤i≤j≤n), such that I’ll be satisfied if I walk from the ith step to the jth?” you wonder. Also, how to construct all colorings such that the number of pairs is maximized?

Input
The only line contains an integer n (1≤n≤105), indicating the number of steps of the road.

Output
Output an integer in the first line, denoting the maximum number of pairs that make you satisfied.

Each of the following several lines contains a string with length n that represents a coloring scheme, in lexicographically ascending order. The ith character is the color of the ith step, where r is for red and b for blue.

If there are more than 100 different colorings, just find the lexicographically smallest 100 colorings.

Note that in lexicographical order, b is ordered before r.

Examples
inputCopy
1
outputCopy
1
r
inputCopy
2
outputCopy
2
br
rb
rr
inputCopy
3
outputCopy
4
brb
rbr
rrr

题意：

• 给定一个长度n，你需要构造一个只有 r 和 b 字符的字符串。
• 在字符串的子串中，如果有奇数个r，这就是个好区间。
• 问一个这样长度的字符串最多有多少个好区间，并构造出最多的情况。
  最多的情况不唯一的话，按字典序输出，如果超过100个则输出前100个。

思路：

• 首先如何判断一个给定的区间是不是好区间，肯定不能每次O(n^2)跑一遍数数有多少个r。
  我们把r记为1，b记为0，对序列做前缀和， 那么好区间就是前缀和作差为奇数的区间。

• 然后考虑这个前缀和数组的性质， 因为前缀和要么是偶数要么是奇数，我们最后要的是作差为奇数。
  而只有偶数减奇数或者奇数减偶数才有可能得到奇数，所以我们不难算出最终整个序列好区间的个数为前缀和数组的奇数个数odd乘上偶数个数even。

• 我们最后要的是好区间个数尽可能大，同时因为奇数个数+偶数个数=n是固定的，所以根据f(x) = (n-x)*x ，显然x取到n/2附近， 奇数个数和偶数个数相等时，乘积能取到最大值。

• 所以我们构造的时候， dfs分别维护当前奇数个数和偶数个数，如果>n/2，就剪枝减掉，输出前100个为止。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e6+10;
LL n, mx, cnt = 0; string s;

void dfs(int cur, int n1, int n2, int st){ //奇数,偶数个数,前缀和奇偶性
    if(n1 > mx || n2 > mx || cnt==100)return ;
    if(cur == n){
        cnt++;
        cout<<s<<"\n";
        return ;
    }
    s[cur] = 'b';
    dfs(cur+1, n1+(st^1), n2+st, st);
    st ^= 1;
    s[cur] = 'r';
    dfs(cur+1, n1+(st^1), n2+st, st);
}

void solve(){
    cin>>n;
    s = string(n,'r');
    mx = (n+2)/2;
    cout<<((n+1)/2)*((n+2)/2)<<"\n";
    dfs(0, 1, 0, 0);
}  

int main(){
    // ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T=1;  //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
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