Educational Codeforces Round 160 (Rated for Div. 2)
题意:给定一个由数字字符组成的字符串,且无前导零,将其分割成ab两部分,b不能有前导零,拆分后的数字a是否可以严格小于数字b
思路:数据很小,可以暴力拆分,数字|字符串操作均可。这里是尽可能将数字靠前分割来判断分割后的两字符串。
AC code:
void solve(){
string s; cin >> s;
string cnt = "";
int pos;
cnt += s[0];
for(int i = 1; i < s.size(); i ++){
if(s[i] != '0'){
pos = i;
break;
}
cnt += s[i];
}
string tt = "";
for(int i = pos; i < s.size(); i ++)
tt += s[i];
if(tt == cnt || tt.size() < cnt.size() || tt.size() == cnt.size() && tt < cnt){
cout << "-1" << endl;
return;
}
cout << cnt << " "<< tt << endl;
}
题意:给定01二进制字符串s,现在有两种操作:
将操作后的字符串定为t,字符串t与原字符串s左对齐对每一位进行比较,若均不相等则t为好字符串,空字符串默认为好字符串;
求操作的最小成本。
思路:首先分别记录01字符的数量,然后遍历字符串s,遍历时需要记录走过的可以交换的0和1,若前方有可交换的字符时,就减去该字符,否则查看剩余01字符,选择交换然后同时减去两字符并将当前字符记录到交换字符中。
AC code:
void solve(){
string s; cin >> s;
n = s.size();
int zero = 0, one = 0;
for(int i = 0; i < n; i ++){
if(s[i] == '0') zero ++;
else one ++;
}
int cnt_0 = 0, cnt_1 = 0;
for(int i = 0; i < n; i ++){
if(s[i] == '0'){
if(cnt_1){
cnt_1 --;
}else if(one){
one --;
zero --;
cnt_0 ++;
}else{
cout << n - i << endl;
return;
}
}else{
if(cnt_0){
cnt_0 --;
}else if(zero){
one --;
zero --;
cnt_1 ++;
}else{
cout << n - i << endl;
return;
}
}
}
cout << 0 << endl;
}
题意:最初有一个空集,需要处理两种操作:
思路:位运算,每次添加的元素均为二进制的x位,记录二进制中存入的位,当查询时只需要从后往前遍历二进制数,看当前位存储的是否足够,不够就*2累加到下一位尝试减去。
AC code:
map<int, int> mp, cnt;
void solve(){
cin >> n;
for(int i = 0; i < n; i ++){
int t, v; cin >> t >> v;
if(t == 1){
mp[v] ++;
}else{
int now = 0;
for(int i = 30; i >= 0; i --){
int pos = v >> i & 1;
pos += now * 2;
if(mp[i] < pos) now = pos - mp[i];
else now = 0;
}
if(now) cout << "NO" << endl;
else cout << "YES" << endl;
}
}
}