復旦大学コンピュータ2020年機試験問題の問題解

ACは前の3つの問題を行い、D問題は木を建てる方法を採用したので、半分の用例がタイムアウトした.E問題は何の考えもなく、時間もないので、できませんでした.
A ⽃⽜
0~9の範囲の5つの整数a 1,a 2,a 3,a 4,a 5が与えられる.5つの整数の中から3つを選択することができ、この3つの整数の和が10の倍数(0を含む)である場合、この5つの整数の重み値は、選択されていない2つの整数の和が10に対して余剰を取った結果であり、明らかに複数の3元群が10の倍数である場合、残りの2つの数の和が10に対して余剰を取った結果は同じである.このような3つの整数が選択されない場合、この5つの整数の重みは-1です.
ここで、T組のデータが与えられ、各組のデータは5個の0~9の範囲の整数を含み、それぞれこのT組のデータの中の5個の整数の重み値を求める.
【入力形式】
1番目の整数T(1<=T<=1000)は、テーブル⽰データ群数である.
次にT,0~9の整数を5個ずつ,表1組のデータを表す.
【出力形式】
Tを出力し、1個の整数ごとに、表⽰の各データの中の5個の整数の重み値を出力する.
【サンプル負け】
4
1 0 0 1 0
1 0 0 8 6
3 4 5 6 7
4 5 6 7 8
【サンプル出力】
2
【時空制限】
2500ms,256MB

//    ：        5，      
#include 
using namespace std;

int main() {
	int T, a[5];
	cin >> T;
	//T   
	while (T--) {
		int sum = 0, flag = 0, ans;
		for (int i = 0; i < 5; i++) {
			cin >> a[i];
			sum += a[i];
		}
		// 5     3     
		for (int i = 0; i < 5; i++) {
			for (int j = i + 1; j < 5; j++) {
				for (int k = j + 1; k < 5; k++) {
					int sumOfThree = a[i] + a[j] + a[k];
					if (sumOfThree % 10 == 0) {
						flag = 1;
						ans = (sum - sumOfThree) % 10;
						break;
					}
				}
			}
		}
		if (flag == 0) cout << -1 << endl;
		else cout << ans << endl;
	}
	return 0;
}

Bネズミを打つ
n個の整数a 1,a 2,...,anと1個のdを与えるには、これらの整数を⼲から大へ並べた後、任意の2つの隣接する数の差が所定のdに等しくないように、整数を選択する必要があります.最大何個の数を選ぶことができますか.
【入力形式】
2つ目の整数n,d(1<=n<=10^5,0<=d<=10^9)は,それぞれ整数個数と隣接整数差の下限を表す.
第2のn個の整数a 1,a 2,...,an(1<=ai<=10^9,1<=i<=n),表
【出力形式】
1つの整数だけで、答えを表します.
【サンプル負け】
6 2
1 4 2 8 5 7
【サンプル出力】
3
【時空制限】
2500ms,256MB

//    ：     +     
#include 
using namespace std;
const int MAXN = 100010;
int a[MAXN], dp[MAXN];

int main(){
	int n, d;
	cin >> n >> d;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n);
	dp[0] = 1;
	for (int i = 1; i < n; i++) {
		if (a[i] - a[i - 1] >= d) {
			dp[i] = dp[i - 1] + 1;
		} else {
			dp[i] = dp[i - 1];
			a[i] = a[i - 1];
		}
	}
	cout << dp[n - 1];
	return 0;
}

C列に並んで食事をする
授业が终わって、n人の学友は続々と学生一人一人の食事開始時間を聞いたり、早めにチームを離れたことを指摘したりします(そうすれば-1を出力します).【入力形式】
1番目の整数n(1<=n<=10^5)は、ご飯を食べに来る同級生の数を表す.
次にn,各整数ai,ti,bi(1<=ai,ti,bi<=10^9,1<=i<=n)を3つずつ表し,各学生の到着時間,食事時間,待ち時間の上限をそれぞれ表す.
保証a 1
【出力形式】
1つの整数で、各学生の食事開始時間または-1を表す(もしその学生が早めにチームを離れたら).
【サンプル負け】
4
1 3 3
2 2 2
3 9 1
4 3 2
【サンプル出力】
1 4 -1 6
【時空制限】
5000ms,256MB

//    ：      
#include 
#include 
#include 
#include 
using namespace std;

struct node{
	long long a;
	long long t;
	long long b;
};

int main() {
	int n;
	cin >> n;
	queue q;
	vector v;
	while (n--) {	//             
		node stu;
		cin >> stu.a >> stu.t >> stu.b;
		q.push(stu);
	}
	int current = 1;
	while (!q.empty()) {
		node temp = q.front();
		q.pop();
		int ans;
		if (temp.a + temp.b >= current) {	//         
			if (current > temp.a){
				ans = current;
				current += temp.t;
			} else {
				ans = temp.a;
				current = temp.a + temp.t;
			}
		} else {	//        
			ans = -1;
		}
		v.push_back(ans);
	}
	for (int i = 0; i < v.size(); i++) {
		if (i == 0) cout << v[i];
		else cout << " " << v[i];
	}
	return 0;
}

D二叉探索木
1個の1~nの配列P、すなわち、⻓度がnであり、1~nのすべての数字に1回のシーケンスが適切に現れる.次に,配列中の要素を最初は空の二重フォーク探索ツリー(左⼩右大)に順番に挿入し,最後に各ノードの親ノードの要素が何であるかを尋ねる.特に、ルートノードの親ノード要素は0と見なされる.
【入力形式】
1番目の整数n(1<=n<=10^5)は、P中の要素の個数を表す.
第2のn個の整数p 1,p 2,...,pn(1<=pi<=n,1<=i<=n),表
【出力形式】
i番目の整数aiテーブルiがノードの親ノードの要素に対応するn個の整数.特に、ルートノードの親ノード要素は0と見なされる.
【サンプル負け】
5
2 3 5 1 4
【サンプル出力】
2 0 2 5 3
【時空制限】
5000ms,256MB
私のやり方は木を建てることですが、一部の使用例はタイムアウトしました.

//  ：        ，      ，           。                         。
#include 
using namespace std;
int n, flag = 0;	//flag                 

//       
struct node{
	int data;
	int father;
	node* lchild;
	node* rchild;
};

//    
node* newNode(int x, int f){
	node* Node = new node;
	Node->data = x;
	Node->father = f;
	Node->lchild = NULL;
	Node->rchild = NULL;
	return Node;
}

//    
void insert(node* &root, int x, int f){
	if (root == NULL){
		root = newNode(x, f);
		return;
	}
	f = root->data;
	if (x < root->data){
		insert(root->lchild, x, f);
	} else {
		insert(root->rchild, x, f);
	}
}

//       
node* create(int data[], int n) {
	node* root = NULL;
	for (int i = 0; i < n; i++) {
		insert(root, data[i], 0);
	}
	return root;
}

//    
void inorder(node* root) {
	if (root == NULL) return;
	inorder(root->lchild);
	if(flag != n - 1) {
		cout << root->father << " ";
		flag++;
	} else {
		cout << root->father;
	}
	inorder(root->rchild);
}

int main() {
	cin >> n;
	int a[n];
	for (int i = 0; i < n; i++){
		cin >> a[i];
	}
	node *root = create(a, n);
	inorder(root);
	return 0;
}

タイムアウトしない方法は次のとおりです.

//            +       map                  
#include 
#include 

Eシーケンス
1つのnのシーケンスAが与えられ、シーケンス中の要素はいずれも0~9の間の整数であり、1つのnの整数シーケンスBについても、その重み値を|A_と定義するi-B_i|(1<=i<=n)の和に(B_j-B_j+1)^2(1<=j)を加える
【入力形式】
一次整数n(1<=n<=10^5)、表⽰シーケンスAの⻓度.
2番目のn個の整数a 1,a 2,...,an(0<=ai<=9,1<=i<=n),表
【出力形式】
1つの整数だけで、答えを表します.
【サンプル負け】
6
1 4 2 8 5 7
【サンプル出力】
11
【解釈】
A配列は[14 2 8 5]
B配列は[34 4 4 5 6]であってもよい.
重み値|A_i - B_i|(1<=i<=n)の和に(B_j-B_j+1)^2(1<=j)を加える
重み第一部分|A_i - B_i|(1<=i<=n)の和は、
|1 - 3| + |4 - 4| + |2 - 4| + |8 - 5| + |5 - 5| + |7 - 6| = 2 + 0 + 2 + 3 + 0 + 1 = 8
重み第2部(B_j-B_j+1)^2(1<=j
(3 - 4)^2 + (4 - 4)^2 + (4 - 5)^2 + (5 - 5)^2 + (5 - 6)^2 = 1 + 0 + 1 + 0 + 1 = 3
したがって、合計ウェイト値は8+3=11です.
【時空制限】
2500ms,256MB
以下の問題解を転載する.https://blog.csdn.net/hyacinthhome/article/details/105952974
分析:シーケンスAが与えられ、考えてみると、b配列の各値の選択に対する答えへの貢献は何ですか?実は前だけ
寄与は前の値との差を加えた二乗にすぎないため、A配列に対応する位置にある.
差の絶対値なので、now配列を維持します.now[i]は現在終了しているBのこれを表しています.
位置値がiであると,更新には前の位置の0−9の場合が最適となり,複雑度は
O(10*10*n)、n=1 e 5で、1秒以内の差はありません

#include 
#include 
#include 
using namespace std;
int tp1[10][10], tp2[10][10];
int now[10], now_temp[10];  //     i      ，   O(n*10*10)   1e7，     
const int INF=0x3f3f3f3f;

void init()
{
	for(int i = 0; i < 10; i++){
		for(int j = 0; j < 10; j++)
		{
			tp1[i][j] = i < j ? (j - i) : (i - j);
			tp2[i][j] = (i - j) * (i - j);
		}
	}
}

int main()
{
	int n, num;
	init();
	while(scanf("%d",&n) != EOF) {
		memset(now, 0, sizeof(now));
		for(int i = 0; i < n; i++) {
			scanf("%d", &num);
			for(int j = 0; j < 10; j++) {
				int temp = INF;
				for (int k = 0; k < 10; k++) {
					int tp;
					if (i) {
						tp = now[k] + tp1[j][num] + tp2[j][k];
					}
					else {
						tp = now[k] + tp1[j][num];
					}
					if(tp < temp) temp = tp;
				}
				now_temp[j] = temp;
			}
			for(int i = 0; i < 10; i++) 
				now[i] = now_temp[i];
		}
		int ans = INF;
		for(int i = 0; i < 10; i++)
			ans = min(ans, now[i]);
		printf("%d
", ans);
	}
	return 0;
}