2021_HUASACM_寒假周測_1 題解

我是比賽鏈接

A題(huas_sy)：清除內奸
思路：
略

#include <iostream>
using namespace std;

int n, x;

int main(){
    cin >> n >> x;
    int y;
    for(int i = 0; i < n; i ++){		//	每個數只用一次，不需要開辟額外的空間存盤
        cin >> y;
        if(x != y) cout << y << ' ';	//	不相等就輸出
    }
    return 0;
}

B題(the_xin)：棒球比賽
思路(the_xin)：
比較D在是不是小于v*s或者大于vt

#include<iostream>
using namespace std;
int main(){
    int n,s,t,d;
    cin>>n>>s>>t>>d;
    int sd=n*s;
    int td=n*t;
    if(d<sd||d>td)puts("Yes");
    else puts("No");
    return 0;
}

C題(the_xin)：壞了的鍵盤
思路1(the_xin)：
從左往右遍歷整個字符陣列（從1開始），累計相同字符的和若其連續相同字符個數為奇數則當前字符鍵盤必不可能是壞的，

#include<bits/stdc++.h> 			// 萬能頭檔案，包含絕大多數常用頭檔案
using namespace std;
string s;                           // C++提供的字串變數
int cnt[30];
int main()
{
	cin >> s;
	int ans = 26;
	int len = 1;
	char ch = s[0];
	for(int i = 1; i < s.length(); i ++) {
		if(ch == s[i]) len ++;
		else {
			if(len % 2 == 1 && !cnt[ch - 'a']) {
				ans --;
				cnt[ch - 'a'] = 1;
			}
			len = 1;
			ch = s[i];
		}
	}
	if(len % 2 == 1 && !cnt[ch - 'a']) ans --;
	cout << ans;
	return 0;
}

思路2(huas_sy)：
從左至右遍歷（從1開始），將每一位分成和前面字符相同與不相同去談論，若相同則累加，否則判斷累計和是否為奇數，奇數則說明當前字符必定為好的，在a陣列中標記，最后求a中有多少個沒被標記的數，

#include <iostream>
using namespace std;

int n, a[30];						// 全域變數定義后系統自動初始化其為0
string s;                           // C++提供的字串變數

int main(){
    cin >> s;
    n = s.length();
    int ans = 0, sum = 1, x = s[0] - 'a';
    for(int i = 1; i < n; i ++){
        if(s[i] == s[i-1]){
            sum ++;
        }else {
            if(sum & 1) a[x] = 1;	// ‘&’ 運算子為位運算子的一種，自行百度其用法，不懂可群里溝通
            sum = 1;
        }
        x = s[i] - 'a';
    }
    if(sum & 1) a[x] = 1;
    for(int i = 0; i < 26; i ++)
        if(a[i] == 0) ans ++;
    cout << ans;
    return 0;
}

D題(huas_sy)：干掉小團體
思路(huas_sy)：
發現對于每個人的愛好值，其范圍是比較小的，完全可以開辟一個陣列令其下標范圍大于愛好值的取值范圍，然后將愛好值對號入座（類似于“桶排序”的思路），最后將無愛好值相同的愛好值順序列印輸出即可，

#include <iostream>

using namespace std;

int n, a[200009], b[200009];
 
int main(){
    cin >> n;
    int x;
    for(int i = 0; i < n; i ++){
        cin >> a[i];
        b[a[i]] ++;
    }
    for(int i = 0; i < n; i ++){
        if(b[a[i]] < 2) cout << a[i] << ' ';
    }
    return 0;
}

E題(the_xin)：簡單的陣列
思路(huas_sy):
分別維護前綴最大值和前綴最小值最后答案即為最大值和最小值的差（想想前綴和差值的意義）

#include <iostream>

using namespace std;

int n;
 
int main(){
    cin >> n;
    int a, b, x, sum = 0;
    a = b = 0;     			  // 初始化最值為0
    for(int i = 0; i < n; i ++){
        cin >> x;
        sum += x;
        if(sum < a) a = sum;
        if(sum > b) b = sum;
    }
    cout << b - a;
    return 0;
}

F題(huas_sy)：排位次
思路1(the_xin)：
Node結構體中x存的是運動員得分 id表示是第幾個運動員
對nodes利用x進行排序后 id為原來詢問的順序
這時候nodes陣列存放的是按照得分排序后的結果
陣列下標就是他的排名 node[i].id存放第幾個運動員在i名
我們可以用陣列b來表示 其中第i個元素表示第i個運動員的排名
我們只需要遍歷nodes陣列 使得b[node[i].id]=i
最后按順序輸出即可

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
const int N=2e5+10;
struct Node{
    int x,id;
    bool operator<(const Node &a )const {           // C++提供的運算子多載,其關鍵字為: operator     
        return x>a.x;                               // 多載比較運算子之后 Node 之間的比較僅與 x 欄位有關,配合后文的 sort 函式使用           
    }
}nodes[N];
int b[N];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&nodes[i].x);                    // x 存盤運動員得分
        nodes[i].id=i;                              // id 存盤運動員的位置
    }
    sort(nodes+1,nodes+1+n);                        // 由 <algorithm> 頭檔案提供的一個排序函式 sort
    for(int i=1;i<=n;i++){
        b[nodes[i].id]=i;                           // 第 nodes[i].id 個運動員的名次是 i
    }
    for(int i=1;i<=n;i++)
        printf("%d ",b[i]);
    return 0;
}

思路2(huas_sy)：
將 b 陣列初值賦值為 a 陣列的下標（系結）
利用 a 陣列的值對 b 陣列進行遞減排序（排序方法：歸并排序；利用 c 陣列進行過渡；時間復雜度為O(nlogn) ）
通過排序后的 b 陣列還原 a 陣列中各個位置的名次（此時 b 陣列的下標為名次，b 陣列的值為該名次運動員被詢問的次序）（溯源）

#include <iostream>
 
using namespace std;
 
int n, a[200009], b[200009], c[200009];
 
void fu1(int l, int r, int m){					// 合并有序區間 [l, r-1] , [r, m]
    int i, j, coun = 0;
    for(i = l, j = r; i < r && j <= m; ){
        if(a[b[i]] > a[b[j]]){					// 比較時根據下標系結的 a 進行比較
            c[coun ++] = b[i];
            i ++;
        }else {
            c[coun ++] = b[j];
            j ++;
        }
    }
    while(i != r){
        c[coun ++] = b[i ++];
    }
    while(j != m + 1){
        c[coun ++] = b[j ++];
    }
    for(i = l, j = 0; j < coun; j ++, i ++){	// 將排序好的陣列賦值回 b 陣列
        b[i] = c[j];
    }
}
void fu(int l, int r){							// 對區間 l， r 排序
    if(l == r) return;
    int mid = (l + r) / 2;						// 二分中點
    fu(l, mid);
    fu(mid + 1, r);
    fu1(l, mid + 1, r);							// 對排序后的兩個區間，進行有序合并
}
int main(){
    cin >> n;
    int x;
    for(int i = 0; i < n; i ++){				// 初始化 a，b 陣列
        cin >> a[i];
        b[i] = i;
    }
    fu(0, n - 1);								// 對 b 陣列 0 到 n-1 的位置進行排序
    for(int i = 0; i < n; i ++){				// 溯源
        a[b[i]] = i;
    }
    for(int i = 0; i < n; i ++)
        cout << a[i] + 1 << ' ';
    return 0;
}

感謝觀看
對于后續的題目希望大家再接再厲，我們的水平是有限的，若有錯誤隨時聯系我們改正，
關于題目和解題思路，均已用小括號標識了提供者；一些初次提到的點也已做注釋說明，以后將不再贅述，
最后：網路是個好東西，它龐大的容量足以你在里面找到絕大多數知識，智者會利用它，愚人也會利用它，只是用它做的事情有所不同而已，