T1 分糖果

题目传送门

思路

分类讨论

当 $L=R$

每个小朋友拿 $\lfloor \frac{L}{N} \rfloor$ 个，那么一共就是 $N* \lfloor \frac{L}{N} \rfloor$ ，所以输出 L - L / N * N

当 $L \not= R$

记 $l = \lfloor \frac{L}{N} \rfloor$ , $r = \lfloor \frac{R}{N} \rfloor$

当 $l < r$

那么肯定可以拿到最多，即为输出 N - 1

当 $l = r$

能拿多少拿多少，即为输出 R - a * N

当 $l > r$

肯定不可能，输出 Fuck CCF

参考程序

#include <bits/stdc++.h>
using namespace std;

int N , L , R;

int main() {
	ios::sync_with_stdio(false);
	cin >> N >> L >> R;
	if(L == R) {
		cout << L - L / N * N << endl;
	}
	else {
		int a = L / N , b = R / N;
		if(a < b) {
			cout << N - 1 << endl;
		}
		else if(a == b){
			cout << R - a * N << endl;
		}
	}
}

T2 冒泡排序

题目传送门

思路

考场上看到的第一反应——平衡树，然后懒得写

我们考虑写一个 $O(n)$ 查找 $O(1)$ 查询

由于要记录编号，考虑使用结构体来维护

我们需要查询排名，新建一个数组 Rank 保存第 $i$ 个编号的排名

对于每次更新，只需要正向做一遍冒泡，反向再做一遍冒泡，更新 Rank 即可,总复杂度为 $O(n)$

对于查找，只需输出 Rank[x] 即可,总复杂度为 $O(1)$

参考程序

#include <bits/stdc++.h>
using namespace std;

int N , Rank[8010] , T;

struct num{
	int Num , Id;
}Num[8010];

bool Cmp(num X, num Y) {
	return X.Num == Y.Num ? X.Id < Y.Id : X.Num < Y.Num;
} 

int main() {
	ios::sync_with_stdio(false);
	cin >> N >> T;
	
	for(int i = 1; i <= N; i++) {
		cin >> Num[i].Num;
		Num[i].Id = i;
	}
	
	sort(Num + 1 , Num + 1 + N , Cmp);
	
	for(int i = 1; i <= N; i++)
		Rank[Num[i].Id] = i;
		
	for(int i = 1 , op , x , v; i <= T; i++) {
		cin >> op;
		if(op == 1) {
			cin >> x >> v;
			Num[Rank[x]].Num = v;
			for(int j = N; j >= 2; j--) {
				if(Cmp(Num[j] , Num[j - 1])) {
					swap(Num[j] , Num[j - 1]);
				}
			}
			for(int j = 2; j <= N; j++) {
				if(Cmp(Num[j] , Num[j - 1])) {
					swap(Num[j] , Num[j - 1]);
				}
			}
			for(int j = 1; j <= N; j++) {
				Rank[Num[j].Id] = j;
			}
		}
		else {
			cin >> x;
			cout << Rank[x] << endl;
		}
	} 
	return 0;
}

T3 网络连接

题目传送门

思路

本题难点在于 check() 函数

先考虑不合法的情况

$a$ 前面有前导字符
$e$ 后面有后缀字符
$a$ 与 $b$ 之间的符号(其余之间同理)

该字符不为 .

不止一个字符或没有

a > 255 || b > 255 || c > 255 || d > 255 || e > 65535

本题由于数据范围比较小，所以不需要用 map ，直接暴力即可

参考程序

#include <bits/stdc++.h>
using namespace std;

int N; 

string S[1010] , Op[1010];

long long ToString(string S) {
	long long res = 0;
	for (int i = 0; i < S.size(); i++) res = res * 10 + (S[i] - '0');
	return res;	
}

bool Check(string s){
	int i, x;
	long long num;
	for (i = 0, x = 0; ; ){
		if (i >= s.size()) return 0;
		string nums;
		bool read = 0;
		while ('0' <= s[i] && s[i] <= '9'){
			read = 1;
			nums += s[i ++];
			if (i >= s.size()) return 0;
		}
		num = ToString(nums);
		if (((nums[0] == '0' && num > 0) || (num == 0 && nums.size() > 1)) || !read) return 0;
		x++;
		if (num > 255 || num < 0) return 0;
		if (x == 4) break;
		if (s[i++] != '.') return 0;
	}
	if (s[i++] != ':') return 0;
	if (i >= s.size()) return 0; 
	string nums;
	bool read = 0;
	while ('0' <= s[i] && s[i] <= '9'){
		read = 1;
		nums += s[i++];
		if (i >= s.size()) break;
	}
	num = ToString(nums);
	if (((nums[0] == '0' && num > 0) || (num == 0 && nums.size() > 1)) || !read) return 0;
	if (num > 65535 || num < 0) return 0;
	return 1;
}

int main() {
	cin >> N;
	
	for(int i = 1; i <= N; i++) {
		cin >> Op[i] >> S[i];
		if(!Check(S[i])) {
			puts("ERR");
			continue;
		}
		
		if(Op[i] == "Server") {
			bool Serch = true;
			for(int j = 1; j < i; j++) {
				if(Op[j] == "Server" && S[j] == S[i]) {
					Serch = false;
					puts("FAIL");
					break;
				}
			}
			if(Serch) {
				puts("OK");
			}
		}
		
		else {
			bool Serch = true;
			for(int j = 1; j < i; j++) {
				if(Op[j] == "Server" && S[j] == S[i]) {
					Serch = false;
					cout << j << endl;
					break;
				}
			}
			if(Serch) {
				puts("FAIL");
			}
		}
	}
		
	return 0;
}

T4 小熊的果篮

思路

首先对输入序列建双向链表，共维护两个链表。

然后进行简单模拟即可

每个水果被遍历一次，每个块被删除一次，时间复杂度 $O(n)$ 。

参考程序

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 10;

int Cnt;

struct List {
	int Pre , Next;
	int Val;
}list1[MAXN] , list2[MAXN];

int Num[MAXN];

void Delete(int Pos) {
	int P = list1[Pos].Pre;
	int N = list1[Pos].Next;
	list1[P].Next = N;
	list1[N].Pre = P;
}

void EatOne(int Pos) {
	int P = list2[Pos].Pre;
	int N = list2[Pos].Next;
	list2[P].Next = N;
	list2[N].Pre = P;
	cout << Pos << " ";
}

void Chi() {
	int Head = list1[0].Next;
	int Color = Num[list1[Head].Val];
	while(Head != Cnt + 1) {
		if(Num[list1[Head].Val] != Color) {
			Delete(Head);
			Head = list1[Head].Next;
			goto end;
		}
		EatOne(list1[Head].Val);
		list1[Head].Val = list2[list1[Head].Val].Next;
		if(Num[list1[Head].Val] != Color) 
			Delete(Head);
		Head = list1[Head].Next;
		Color ^= 1;
		end:
			continue;
	}
	cout << endl;
}

int N;

int main() {
	ios::sync_with_stdio(false);
	
	cin >> N;
	
	list2[0].Next = 1;
	
	for(int i = 1; i <= N; i++) {
		cin >> Num[i];
		list2[i].Pre = i - 1;
		list2[i].Next = i + 1;
	}
	
	Num[0] = 2;
	
	Num[N + 1] = 2;
	
	list1[0].Next = 1;
	
	for(int i = 1; i <= N; i++) {
		if(Num[i] != Num[i - 1]) {
			++Cnt;
			list1[Cnt].Pre = Cnt - 1;
			list1[Cnt].Next = Cnt + 1;
			list1[Cnt].Val = i;
		}
	}
	
	while(list2[0].Next != N + 1)
		Chi();
	
	return 0;
}