Dytechlab Cup 2022 (A - C)

A - Ela Sorting Books

分析：贪心，将字符串每一位都存在map里，从前往后尽量让每一个\(n / k\)的段\(mex\)值尽量大，模拟mex即可。

void solve(){
	int n,k;
	cin >> n >> k;
	string s;
	cin >> s;
	map<char,int> mp;
	int d =  n / k; 
	set<char> st;
	for (int i =0;i < n;i++) {
		mp[s[i]]++;
	}
	while(k--){
		bool  f = false;
		for (int j = 0; j < d;j ++) {
			if(mp['a' + j] > 0) {
				mp['a' + j]--;
			}
			else {
				f =  true;
				cout << char ('a' + j);
				break;
			}
		}
		if(!f) cout << char('a' + d);
	}	
	cout << endl;
}

B - Ela's Fitness and the Luxury Number

分析:我自己也不太会证qwq，大概思路就是，因为这题数据量很大，可以肯定是\(O(1)\)计算无疑了，打表猜公式即可。

int rcl(int x) {
	int d = sqrt(x);
	int res = (int)(sqrt(x) - 1);
	res *= 3;
	int now = d * d;
	while(now <= x){
		now += d;
		res++;
	}
	return res;
}
void solve(){
	int l,r;
	cin >> l >> r;
	int ans1 = rcl(r);
	int ans2 = rcl(l);
	int q = 0;
	if(l % (int)(sqrt(l)) == 0)q++;
	cout << ans1 - ans2 + q<< endl;
 
}

C - Ela and Crickets

分析：画图模拟，很容易可以看出，以开始的点画十字，是可以跳到的位子，如何判断是否在十字内呢，只要目标点和出发的中心 \(x\)或\(y\)满足有一个绝对差是偶数倍即可。
还需要考虑边界情况，如果出发的中心在棋盘的四个角，那只能是一条横着的直线和竖着的直线了。

void solve(){
	int n;
	cin >> n;
	PII cp[5];
	for (int i = 1;i <= 3;i++) {
		cin >> cp[i].first >> cp[i].second;
	}
	int ax,ay;
	cin >> ax >> ay;
	sort(cp+1,cp+3);
	map<int,int> mp1;
	map<int,int> mp2;
	int tagx;
	int tagy;
	for (int i = 1;i <= 3;i ++) {
		mp1[cp[i].first]++;
		mp2[cp[i].second]++;
		if(mp1[cp[i].first] == 2) tagx = cp[i].first;
		if(mp2[cp[i].second] == 2) tagy = cp[i].second; 
	}
	if((tagx == 1 && tagy == 1) || (tagx == n && tagy == 1) || (tagx == 1 && tagy == n) || (tagx == n && tagy == n)) {
		if(tagx == ax || tagy == ay) {
			cout << "YES" << endl;
			return ;
		}
		else {
			cout << "NO" << endl;
			return ;
		}
	}
	else {
		if(abs(ax - tagx) % 2 == 0 || abs(tagy - ay) % 2 == 0 ) {
			cout <<"YES" << endl;
			return ;
		}
		else {
			cout <<"NO" << endl;
			return ;
		}
	}
 
}