按题意模拟，用 set 存储已经经过的点的坐标，在判断有无重复即可。
LL n;
set<pair<LL, LL> > s;
string str;
int main(){
Fcin;
cin >> n;
cin >> str;
LL x = 0, y = 0;
s.insert(mkp(0, 0));
for (auto it : str){
if (it == 'U')
++ x;
else if (it == 'D')
-- x;
else if (it == 'L')
-- y;
else
++ y;
if (s.find(mkp(x, y)) != s.end()){
cout << "Yes";
return 0;
}
s.insert(mkp(x, y));
}
cout << "No";
return 0;
}
DP 题。
用 表示第 个位置翻转或不翻转后合法的总数。
若 , 则 加上 。
若 , 则 加上 。
若 , 则 加上 。
若 , 则 加上 。
LL n, A[N], B[N], DP[N][2];
int main(){
Fcin;
cin >> n;
for (LL i = 1; i <= n; i ++){
cin >> A[i] >> B[i];
}
DP[1][1] = DP[1][0] = 1;
for (LL i = 2; i <= n; i ++){
if (A[i] != A[i - 1])
DP[i][0] = (DP[i][0] + DP[i - 1][0]) % 998244353;
if (A[i] != B[i - 1])
DP[i][0] = (DP[i][0] + DP[i - 1][1]) % 998244353;
if (B[i] != A[i - 1])
DP[i][1] = (DP[i][1] + DP[i - 1][0]) % 998244353;
if (B[i] != B[i - 1])
DP[i][1] = (DP[i][1] + DP[i - 1][1]) % 998244353;
}
cout << (DP[n][1] + DP[n][0]) % 998244353;
return 0;
}
拓扑排序。
对于每一对 ， 向 连一条单向边，最终即形成一个 DAG。然后进行拓扑排序。 如果能完整的拓扑出长度为 的答案序列，则唯一。
若最开始拓扑时入度为 的点有多个，则同样不唯一。
const LL N = 2e5 + 10;
vector<LL> G[N];
LL n, m, in[N], res[N], Ans[N];
int main(){
Fcin;
cin >> n >> m;
LL x, y;
for (LL i = 1; i <= m; i ++){
cin >> x >> y;
G[x].emplace_back(y);
in[y] ++;
}
queue<pair<LL, LL> > q;
for (LL i = 1; i <= n; i ++)
if (!in[i])
q.push(mkp(i, 1));
if (q.size() != 1){
cout << "No";
return 0;
}
while (!q.empty()){
LL x = q.front().first, k = q.front().second; q.pop();
res[k] = x;
if (k == n){
cout << "Yes\n";
for (LL i = 1; i <= n; i ++)
Ans[res[i]] = i;
for (LL i = 1; i <= n; i ++)
cout << Ans[i] << " ";
return 0;
}
for (auto it : G[x]){
in[it] --;
if (in[it] == 0)
q.push(mkp(it, k + 1));
}
}
cout << "No";
return 0;
}