Codeforces Round 877 (Div. 2)

D. Bracket Walk

题意

给出一个括号序列，每次可以向左或向右移动一格。问是否存在一种方式，从最左端走到最右端，且经过的路径是一个合法的括号序列。

题解

显然 $n$ 一定是偶数。

我们考虑维护这样一个集合：

$i$ 是偶数且 $s_i=$ ()
$i$ 是奇数且 $s_i=$ ()

如果 $A$ 为空，那么 $s$ 一定形如 ()()() ，它自身就是合法括号序列。

如果 $\min(A)$ 是奇数，那么 $s$ 一定形如 ()()())...，它一定不可走。

如果 $\max(A)$ 是偶数，那么 $s$ 一定形如 ...(()()()，它一定不可走。

否则， $s$ 形如 ()()((...))()()，一定可以通过连续走(或)构造出一种合法方案。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {

    int n, q; string s;
    cin >> n >> q >> s;

    set<int> a;

    for(int i = 1; i <= n; ++i)
        if((i % 2) != (s[i - 1] == '('))
            a.insert(i);

    while(q--) {
        int i; cin >> i;

        if(a.count(i)) a.erase(i);
        else a.insert(i);

        if(n % 2) cout << "NO\n";
        else if(a.size() && (*a.begin() % 2 || !(*a.rbegin() % 2))) cout << "NO\n";
        else cout << "YES\n";
    }
}

E. Count Supersequences

题意

给出一个长度为 $n$ 的数组 $a$ ，求包含 $a$ 为子序列的长度为 $m$ 的数组 $b$ 的个数。

题解

本题的核心在于，数组 $a$ 的元素对答案不会产生影响，所以我们可以令 $a$ 所有元素都为 $1$ 。这样问题就变成了求长度为 $m$ 的至少含有 $n$ 个 $1$ 的数组 $b$ 的数量。

代码

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
using LL = long long;
template<const int T>
struct ModInt {
    const static int mod = T;
    int x;
    ModInt(int x = 0) : x(x % mod) {}
    ModInt(long long x) : x(int(x % mod)) {} 
    int val() { return x; }
    ModInt operator + (const ModInt &a) const { int x0 = x + a.x; return ModInt(x0 < mod ? x0 : x0 - mod); }
    ModInt operator - (const ModInt &a) const { int x0 = x - a.x; return ModInt(x0 < 0 ? x0 + mod : x0); }
    ModInt operator * (const ModInt &a) const { return ModInt(1LL * x * a.x % mod); }
    ModInt operator / (const ModInt &a) const { return *this * a.inv(); }
    bool operator == (const ModInt &a) const { return x == a.x; };
    bool operator != (const ModInt &a) const { return x != a.x; };
    void operator += (const ModInt &a) { x += a.x; if (x >= mod) x -= mod; }
    void operator -= (const ModInt &a) { x -= a.x; if (x < 0) x += mod; }
    void operator *= (const ModInt &a) { x = 1LL * x * a.x % mod; }
    void operator /= (const ModInt &a) { *this = *this / a; }
    friend ModInt operator + (int y, const ModInt &a){ int x0 = y + a.x; return ModInt(x0 < mod ? x0 : x0 - mod); }
    friend ModInt operator - (int y, const ModInt &a){ int x0 = y - a.x; return ModInt(x0 < 0 ? x0 + mod : x0); }
    friend ModInt operator * (int y, const ModInt &a){ return ModInt(1LL * y * a.x % mod);}
    friend ModInt operator / (int y, const ModInt &a){ return ModInt(y) / a;}
    friend ostream &operator<<(ostream &os, const ModInt &a) { return os << a.x;}
    friend istream &operator>>(istream &is, ModInt &t){return is >> t.x;}

    ModInt pow(int64_t n) const {
        ModInt res(1), mul(x);
        while(n){
            if (n & 1) res *= mul;
            mul *= mul;
            n >>= 1;
        }
        return res;
    }
    
    ModInt inv() const {
        int a = x, b = mod, u = 1, v = 0;
        while (b) {
            int t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        if (u < 0) u += mod;
        return u;
    }
    
};
using mint = ModInt<1000000007>;

const int maxn = 2e5 + 5, mod = 1e9 + 7;
mint inv[maxn];
void init(){
    inv[1] = 1;
    for(int i = 2; i < maxn; i++)
        inv[i] = mint(mod - mod / i) * inv[mod % i];
}

int main(){

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    init();
    int T;
    cin >> T;
    while(T--){
        int n, m, k;
        cin >> n >> m >> k;
        for(int i = 0; i < n; i++){
            int x;
            cin >> x;
        }
        if (k == 1){
            cout << 1 << '\n';
            continue;
        }
        mint ans = mint(k).pow(m);
        mint c = 1;
        for(int i = 0, j = m; i <= n - 1; i++, j--){
            ans -= c * mint(k - 1).pow(m - i);
            c *= inv[i + 1] * j;
        }
        cout << ans << '\n';
    }

}

F. Stuck Conveyor

题意

给出一个 $n\times n(n\leq 100)$ 的方阵，每个方格上有一个传送带，有上下左右四个方向。每次询问时可以指定物品起始位置和每个传送带的方向，答案会返回物品的最终位置或物品陷入死循环。现在有一个传送带出现了故障，它的方向被固定（即无论指定什么方向，它只会朝着固定的一个方向），要求用不超过 $25$ 次询问找到出现故障的传送带及其方向。

题解

首先，每次询问一定要涉及尽可能多的传送带，可以想到这样一个蛇形的构造方法。从 $(1,1)$ 出发，传送带方向如下所示：

>>>>v
v<<<<
>>>>v
v<<<<
>>>>v

接下来，分析可能出现故障的传送带。

如果它在方阵的边缘，例如 $(2,5)$ $(2, 5)$ ，可能会有以下三种情况：
- 方向被固定为<或v，这时物品仍能顺利抵达预期位置 $(6,5)$ 。
- 方向被固定为^，这时物品陷入死循环。
- 方向被固定为>，这时物品提前离开传送带。
如果它在方阵的中间，只会出现两种情况：顺利抵达预期位置或陷入死循环。

对于提前离开的情况，我们很容易就能知道哪个方格出了故障以及它的方向，可以单独处理。对于顺利抵达的情况，我们可以反过来构造。从 $(n,n)$ 出发，传送带方向如下所示：

^<<<<
>>>>^
^<<<<
>>>>^
^<<<<

此时，就必然会陷入死循环。

所以，我们一定可以得到一种死循环的构造。这时，我们考虑整条传送路径，二分起始位置，就可以确定出现故障的方格了。

确定方格以后，可以这样来确定它的方向，以 $(3,3)$ 为例：

    ^  
    ^
< < X > >
    v
    v

这样总的询问次数最多为 $1+\log_2(10000)+1$ 在 $25$ 次以内。

代码

#include <bits/stdc++.h>
using namespace std;
int n;
pair<int,int> cal(int m,bool flag)
{
    int p,q;
    if(!flag) 
    {
        p=m/n,q=m%n;
        if(p&1) q=n-1-q;
    }
    else
    {
        p=m/n,q=m%n;
        if(n&1)
        {
            if(p%2==0) q=n-1-q;
            p=n-1-p;   
        }
        else
        {
            if(p&1) q=n-1-q;
            p=n-1-p;
        }    
    }
    return {p+1,q+1};
}
void solve(bool flag)
{
    int l=0,r=n*n-1,x,y;
    while(l<r)
    {
        int m=(l+r+1)/2;
        int p=cal(m,flag).first,q=cal(m,flag).second;
        cout<<"? "<<p<<' '<<q<<endl;
        if(!flag)
        {
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    if(i&1) cout<<((j==n)?'v':'>');
                    else cout<<((j==1)?'v':'<');
                }
                cout<<endl;
            }
        }
        else
        {
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    if(n%2==0)
                    {
                        if(i%2==n%2) cout<<((j==n)?'^':'>');
                        else cout<<((j==1)?'^':'<');
                    }
                    else
                    {
                        if(i%2==n%2) cout<<((j==1)?'^':'<');
                        else cout<<((j==n)?'^':'>');                       
                    }
                }
                cout<<endl;
            }    
        }
        cin>>x>>y;
        if(x==-1&&y==-1) l=m;
        else r=m-1;
    }
    int p=cal(l,flag).first,q=cal(l,flag).second;
    cout<<"? "<<p<<' '<<q<<endl;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==p) cout<<((j<q)?'<':'>');
            else cout<<((i<p)?'^':'v');
        }
        cout<<endl;
    }
    cin>>x>>y;
    cout<<"! "<<p<<' '<<q<<' ';
    if(x==p&&y==0) cout<<'<'<<endl;
    if(x==p&&y==n+1) cout<<'>'<<endl;
    if(x==0&&y==q) cout<<'^'<<endl;
    if(x==n+1&&y==q) cout<<'v'<<endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    cout<<"? 1 1"<<endl;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i&1) cout<<((j==n)?'v':'>');
            else cout<<((j==1)?'v':'<');
        }
        cout<<endl;
    }
    int x,y;cin>>x>>y;
    if(x==-1&&y==-1) solve(0);
    else if(((n&1)&&x==n+1&&y==n)||((n%2==0)&&x==n+1&&y==1)) solve(1);
    else
    {
        if(y==0) cout<<"! "<<x<<' '<<1<<' '<<'<'<<endl;
        else if(y==n+1) cout<<"! "<<x<<' '<<n<<' '<<'>'<<endl;
        else if(x==0) cout<<"! "<<1<<' '<<y<<' '<<'^'<<endl;
        else cout<<"! "<<n<<' '<<y<<' '<<'v'<<endl;
    }
    return 0;
}

ACM

#构造 #括号序列 #交互

Codeforces Round 877 (Div. 2)

https://je3ter.github.io/2023/06/19/ACM/Codeforces Round 877 (Div. 2)/

作者

Je3ter

发布于

2023年6月19日

许可协议

Codeforces Round 879 (Div. 2) 上一篇

AtCoder Beginner Contest 304 下一篇