A 00:02
B 00:08
C 00:23
D --:--
E1 --:--
E2 --:--
F --:--
A. Tanya and Stairways
每段序列都是从1开始依次递增
就统计1的数量和1后面的最大值输出即可
int n = read();
for(int i = 1 ; i <= n ; i ++){
int x = read();
if(x == 1) a.push_back(1);
else a[Len(a) - 1] = x;
}
cout << Len(a) << endl;
for(auto x : a) cout << x << " ";
cout << endl;
B. Delete from the Left
计算两个字符串最长的公共后缀长度
string s,t; cin >> s >> t;
int r1 = Len(s) - 1, r2 = Len(t) - 1;
while(r1 >= 0&& r2 >= 0 && s[r1] == t[r2]) r1 --, r2 --;
cout << r1 + r2 + 2 << endl;
C. Summarize to the Power of Two
如果要删除一个数就需要这个数不存在和另一个数的和是2的幂
mi[0] = 1;
for(int i = 1 ; i <= 34 ; i ++) mi[i] = mi[i - 1] << 1;
int n = read();
for(int i = 1 ; i <= n ; i ++){
int x = read();
a.push_back(x);
m[x]++;
}
int ans = 0;
for(int i = 1 ; i <= n ; i ++){
int x = a[i - 1];
m[x] --;
bool flag = false;
for(int j = 1 ; j <= 33 ; j ++){
if(mi[j] <= x) continue;
if(m[mi[j] - x]){
flag = true;
break;
}
}
if(!flag){
ans ++;
}
m[x] ++;
}
cout << ans << endl;
D. Polycarp and Div 3
你有一个字符序列,你需要将这个序列分成若干段,使存在一段字符序列数字和为3的倍数的段数尽可能多
经分析对于一段序列如果可以继续分成一段可以被3整除的序列我一定会继续分下去的
因此只需统计序列中存在多少种模3 为'0', '111','222','12','21'的序列即可
学习知识:^的优先级小于
string s; cin >> s;
int ans = 0;
for(int i = 0 ; i < Len(s) ; i ++){
int x = idz(s[i]) % 3;
if(x == 0){
ans ++;
}else if(i + 1 < Len(s) && (x ^ 3) == (idz(s[i + 1]) % 3)){
ans ++;
i += 1;
}else if(i + 2 < Len(s) && (x == (idz(s[i + 1]) % 3)) && (x == (idz(s[i + 2]) % 3))){
ans ++;
i += 2;
}
}
cout << ans << endl;
E. Median on Segments
给你一段序列你需要找有多少种连续序列满足以m为中位数
直接求有多少序列是以m为中位数的很难求
因此可以转换一下,求有多少序列满足大于等于m的数为中位数-有多少序列满足大于m的数为中位数
求中位数序列大于等于m的操作很简单,只需要统计(1,i)中间大于等于m的个数减去小于m的个数就是当前是否满足,在找一个(1,j)中间大于等于m的个数减去小于m的个数,如果发现第一个数大于等于第二个数就表示(j,i)满足,显然这种情况可以用树状数组维护,但是我没有调出来,stO
因此就考虑贪心维护这个操作,维护一个区间和 和 区间和为p的区间和出现了多少次,当遇到一个大于等于m的就将当前区间和出现的次数的上一次维护上去,因为维护的时小于当前区间和的数量,若小于m则减去前一个维护的区间和数量,因为本身区间和本身就没有向上维护,
int get(int k){
memset(c, 0, sizeof c);
int res = 0;
int sum = 0;
int p = n + 1;
c[p] ++;
for(int i = 1 ; i <= n ; i ++){
if(a[i] >= k){
sum += c[p];
p ++;
}else{
p --;
sum -= c[p];
}
res += sum;
c[p] ++;
}
return res;
}
F. Berland and the Shortest Paths
学习ing