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 ;
}
}
}
标签:map,Cup,int,cin,++,Dytechlab,mp,2022,cp
From: https://www.cnblogs.com/zwh-zzz/p/16770001.html