The 2018 ACM-ICPC Asia Qingdao Regional Contest, Online

The 2018 ACM-ICPC Asia Qingdao Regional Contest, Online(青岛网络赛)

B.Red Black Tree

题意

题解

ac代码

J.Press the Button

题意

题解

ac代码

H Traveling on the Axis

题意

BOB走在$[1,n]$的路上,每两个点中间都有一个红绿灯,每一秒钟,

  • BOB先观察红绿灯是否绿,绿就走,红就停。
  • 红灯变绿,绿灯变红

$t(p,q)$就是$p$走到$q所需要的时间。

问: BOB从 $\sum^{n-1}{p=0} \sum{q=p+1}^nt(p,q)$的时间总和。

题解

对于第$i$个单独的红绿灯我们可以证明他对答案的贡献是

​ $(i)(len-i+1)(t(i))$

我们对于两个灯进行分析。

01 第一个零要2s,第二个一要1s

10 第一个一要1s,第二个零要1s

00 第一个零要2s,第二个一要2s

11 第一个一要1s,第二个一要2s

综上可以发现,

  • 该灯初始为0,那么他当头的时候贡献为2,如果不当头那么他的贡献就为1,除非跟前者相同。
  • 该灯初始为1,那么他和前一个灯相同时贡献为2,就算变成0了,不在头上的话贡献也为1.

我他妈sb了,不应该看着一段一段的区间,应该把红绿灯作为每一次状态的扩展,从红绿灯这$n$个出发开始计算,不应该考虑一个一个的单位为1的区间。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// CSL 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1 << 17;
char s[N];
typedef long long ll;
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
scanf("%s", s);
ll ans = 0;
int n = strlen(s);
for (int i = 0; i < n; i++) ans += 1LL * (i + 1) * (n - i);
for (int i = 0; s[i]; i++)
{
if (s[i] == '0') ans += n - i;
if (i && (s[i] == s[i - 1])) ans += 1LL * i * (n - i);
//要跟包含前者的可能,要两个相同才能这么加。
}
printf("%lld\n", ans);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head

const int maxn = 1e5 + 10;
char s[maxn];
int main(){
#ifdef LOCAL
freopen("h.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
scanf("%s",s);
int len = strlen(s);
ll ans = 0; ll w = 0;
if(s[0]=='1') ans = w = 1;
else ans = w = 2;
rep(i,1,len){
if(s[i]==s[i-1]) w += i*2;
else w += i*1;
if(s[i]=='1') w += 1;
else w += 2;
ans += w;
}
printf("%lld\n",ans);
}

return 0;
}

reference:

https://blog.csdn.net/tianyizhicheng/article/details/82728350