ARC150 A+C题题解。

如题，ARC150 A题 C题 的解题报告。

# A - Continuous 1
### 题意：
有1, 0, ? 组成的一个序列（？可以为0/1）， 问恰好有且仅有k个i， 且连续的情况有多少种。
### 分析：
考虑O(n). 常见为转化成求以每个 i 结尾的信息。
即求长度为k的序列满足以下条件的有且仅有一个：
1. 没有零；（有连续k个1）
2. 前后没有1；（恰k个）

### 代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int n, k;
int a[N], b[N];
char s[N];
int main() {
int t;
scanf("%d", &t);
while(t--) { int ans=0, L=0, R=0;
scanf("%d%d", &n, &k);
cin>>s+1; s[n+1]='0', s[0]='0';

for(int i=1; i<=n; ++i) b[i]=b[i-1] + (s[i]=='1');
for(int i=1; i<=n; ++i) a[i]=a[i-1] + (s[i]=='0');

for(int i=k; i<=n; ++i) {
if(a[i]==a[i-k] && b[n]==b[i] && b[i-k]==0)
++ans;
}
if(ans==1) printf("Yes\n");
else printf("No\n");
}
return 0;
}
```

# C - Path and Subsequence
### 题意：
判断一张图上，每一条 1~n 的路径上的点的权值A顺序构成的序列中都有子序列`B[]`.

### 分析：
考虑什么时候失败。
当一条路径上的点权 没有顺序出现完整个`B[]`就输出No.
所以一条路径越容易到 n 越容易失败。

考虑 `b[i]`
使用BFS，当遍历到x使`a[x] = b[i]`时停止当前点的路径扩展。
一旦一条路径到了 n 就失败（因为还没有出现完 整个的`b[]`呢）。（特判`a[n]=b[k]`）

i 从 1~n 依次处理即可。

### 代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long xt;
#define R(i) for(int i=1; i<=n; ++i)
#define rep(i, x, y) for(int i=x; i<=y; ++i)
#define q Q[rp]
#define p Q[rp^1]
const int N=1e5+10;
const int M=4e5+10;

int n, m, k;
int head[N], nex[M], to[M], amtE;
int a[N], b[N];

void addE(int x, int y) {
++amtE;
to[amtE] = y;
nex[amtE] = head[x];
head[x] = amtE;
}

int e[N];
int main() {
int x, y;
scanf("%d%d%d", &n, &m, &k);
for(int i=1; i<=m; ++i) scanf("%d%d", &x, &y), addE(x, y), addE(y, x);
for(int i=1; i<=n; ++i) scanf("%d", &a[i]);
for(int i=1; i<=k; ++i) scanf("%d", &b[i]);

int rp=0;
queue<int> Q[2];
Q[rp].push(1), e[1]=1;
for(int key=1; key<=k-(a[n]==b[k]); ++key) {
while(q.size()) {
x=q.front(); q.pop();
if(a[x]==b[key]) p.push(x);
else {
for(int i=head[x]; i; i=nex[i]) { y=to[i];
if(y==n) return 0&printf("No");
if(!e[y]) {
e[y]=1;
if(a[y]!=b[key]) q.push(y);
else p.push(y);
}
}
}
}
rp^=1;
}
printf("Yes");
return 0;
}

```