1.A. Kevin and Combination Lock
知识点:模拟
题目意思:现有一个正整数x,我们能否通过两个操作让x为0,可以就输出YES,不行就输出NO。
操作一:如果x中存在33,并且x不等于33的情况下可以删除x中的33。比如13323 -> 123。
操作二:如果x >= 33,可以让x = x - 33。
思路:
操作一去除某个位置的33,相当于减去33 * 10 ^ n。
操作二相当于减去33 * 1
如果能够通过两操作来实现让x == 0,说明x本身是33的倍数
void solve(){
cin>>n;
if(n % 33 == 0)cout<<"YES\n";
else cout<<"NO\n";
}
知识点:构造
题目意思:要求构造一个长度为n的排列p,并要求p的n - k + 1个连续的子数组的最小值相加的和最小。
思路:想要最小,就得让小的数被尽量多的子数组包含其中。
因此构造p[k] = 1, p[2k] = 2 ,…, p[kn] * k = [n / k]
void solve(){
cin>>n>>k;
vi a(n + 1);
int l = 1, r = n;
for(int i = 1; i <= n; i++){
if(i % k == 0)a[i] = l ++;
else a[i] = r --;
}
for(int i = 1; i <= n; i++){
cout<<a[i]<<" \n"[i == n];
}
}
知识点:构造
题目意思:
思路:
一:为了最大化两个串的异或和,肯定想要最大化异或和的二进制位数,为了最大化这个位数,[1, n] 必然被选择。假设我们选择的另一个串的首位为 1,若不为 1 可以把前导零全部删去。
二:找到整个串从前往后的第一个 0 的位置,我们必然想让这个位置变为 1,设第一个 0 的位置为 pos,选取n - pos + 1长度的子串对原串进行异或,更新记录能让结果最大的子串的左右端位置。
void solve(){
cin>>s;
int n = s.size(), pos = 0;
for(int i = 0; i < n; i++){
if(s[i] == '0'){
pos = (n - i - 1);
break;
}
}
int x = 0, y = 0;
string s1 = "";
for(int i = 0; i < n - pos; i++){
string s2 = "";
for(int j = i; j <= i + pos; j++){
if(s[j] != s[(n - pos - 1) + (j - i)])s2 += '1';
else s2 += '0';
}
if(s1 < s2){
x = i + 1;
y = i + pos + 1;
s1 = s2;
}
}
cout<<x<<" "<<y<<" "<<1<<" "<<n<<"\n";
}
4.D. Kevin and Competition Memories
知识点:贪心 + 排序 + 二分
题目意思:有n个参赛者(Kevin是第一位),m道题目,数组a记录着n个参赛者评分(能做出题目的最大难度),数组b记录着m道题目的难度。现有一个k(1 <= k <= m),表示一场比赛由k道题目组成,一共[m / k]场(向下取整),在每场比赛中,Kevin 的排名是 1 加上解决问题数量超过他的参与者数量,求每个k的排名和。
思路:
一、如果一个人评分小于等于Kevin,那么他就不可能排在Kevin前面(不影响答案),所有可以将他评分修改为和Kevin一样的值(相当于删除)。
二、经过上一步操作,Kevin的评分目前是最低的,也就是说一道题要是Kevin能做出了,其他人也都可以做出了,全部人都可以做出来不就可以当成全部人都没做出来,可以将b[i]的值设置为无穷大,这样我们就可以得到每道题有多少人能做出来(不包括全部人都能做出来的题)。
三、枚举k,我们只需要关注每场比赛中的最简单的问题。
void solve(){
cin>>n>>m;
vi a(n), b(m);
for(int i = 0; i < n; i++){
cin>>a[i];
a[i] = max(a[i], a[0]);
}
for(int i = 0; i < m; i++){
cin>>b[i];
if(b[i] <= a[0])b[i] = inf;
}
sort(a.begin(), a.end());
sort(b.begin(), b.end(), greater<int>());
for(int i = 0; i < m; i++){
b[i] = a.end() - lower_bound(a.begin(), a.end(), b[i]);
}
for(int k = 1; k <= m; k++){
int ans = 0;
for(int i = k - 1; i < m; i += k){
ans += b[i] + 1;
}
cout<<ans<<" \n"[k == m];
}
}
标签:int,++,Global,28,Codeforces,cin,33,pos,Kevin
From: https://blog.csdn.net/hsjwhe/article/details/144618357