T5

题目概述

题目要求我们计算通过一系列逻辑运算（AND 或 OR）后，最终结果为 true 的不同输入组合的数量。给定 N 个逻辑运算符（"AND" 或 "OR"），我们需要确定每个变量的取值（true 或 false），使得按照给定的顺序进行运算后，最终结果为 true 的方案数。

方法一：动态规划解法

思路分析

动态规划是解决此问题的直观方法。我们可以定义状态 dp[i][j]，其中：

• i 表示处理到第 i 个运算符
• j 表示当前运算的中间结果（0 表示 false，1 表示 true）

初始状态为 dp[0][0] = dp[0][1] = 1，因为在开始任何运算之前，结果为 true 和 false 的方案数各为 1（可以理解为初始状态）。

状态转移

对于每个运算符，我们需要考虑当前输入变量 x 的两种可能取值（0 或 1），并更新状态：

1. AND 运算符 (&):

   • 如果 x=0:
     • 无论当前结果是什么，AND 运算后结果都会变为 0
     • dp[i][0] += dp[i-1][0] + dp[i-1][1]
   • 如果 x=1:
     • 结果保持原值
     • dp[i][0] += dp[i-1][0]
     • dp[i][1] += dp[i-1][1]

2. OR 运算符 (|):

   • 如果 x=0:
     • 结果保持原值
     • dp[i][0] += dp[i-1][0]
     • dp[i][1] += dp[i-1][1]
   • 如果 x=1:
     • 无论当前结果是什么，OR 运算后结果都会变为 1
     • dp[i][1] += dp[i-1][0] + dp[i-1][1]

代码实现

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxm = 3e5+5;
int dp[maxm][2]; // dp[i][j]表示前i步,y为j的方案数
int op[maxm]; // 存储运算符类型
int n;

void solve() {
    cin >> n;
    for(int i=1; i<=n; i++) {
        string s; cin >> s;
        if(s[0] == 'A') op[i] = 1; // AND
        else if(s[0] == 'O') op[i] = 2; // OR
    }
    
    dp[0][0] = dp[0][1] = 1;
    for(int i=1; i<=n; i++) {
        if(op[i] == 1) { // AND
            // x[i] = 0
            dp[i][0] += dp[i-1][0] + dp[i-1][1];
            // x[i] = 1
            dp[i][0] += dp[i-1][0];
            dp[i][1] += dp[i-1][1];
        } else if(op[i] == 2) { // OR
            // x[i] = 0
            dp[i][0] += dp[i-1][0];
            dp[i][1] += dp[i-1][1];
            // x[i] = 1
            dp[i][1] += dp[i-1][0] + dp[i-1][1];
        }
    }
    cout << dp[n][1] << endl;
}

signed main() {
    ios::sync_with_stdio(0);
    solve();
    return 0;
}

方法二：数学观察法

思路分析

通过观察可以发现，当遇到 OR 运算符时，方案数会呈指数增长。具体来说：

1. 初始时，结果为 true 的方案数为 1（即初始状态）
2. 对于每个 OR 运算符，如果选择 x=1，则无论之前结果如何，最终结果都会为 true
3. 因此，每遇到一个 OR 运算符，可以将其视为增加 2^i 种方案（其中 i 是该 OR 运算符的位置）

代码实现

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

int n; 
ll ans = 1;
string op[67];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i++) cin >> op[i];
    for(int i = n; i >= 1; i--)
        if(op[i][0] == 'O') ans += (1ll << i);
    cout << ans;
    return 0;
}

复杂度分析

• 动态规划方法:

  • 时间复杂度：O(N)
  • 空间复杂度：O(N)

• 数学方法:

  • 时间复杂度：O(N)
  • 空间复杂度：O(1)（如果不考虑输入存储）

总结

本题可以通过动态规划直接解决，也可以通过数学观察找到规律。动态规划方法更加通用，而数学方法则利用了本题的特殊性质，代码更为简洁。

T6

问题描述

高桥君在二维平面的原点(0,0)处。他有N次传送机会，每次可以选择以下三种传送方式之一：

1. 从(x,y)传送到(x+A,y+B)
2. 从(x,y)传送到(x+C,y+D)
3. 从(x,y)传送到(x+E,y+F)

平面上有M个障碍点，不能传送到这些障碍点上。问高桥君完成N次传送后，有多少种不同的路径方案？答案需要对998244353取模。

解题思路

直接DP的问题

最直观的想法是使用动态规划，记录每次传送后的位置。设dp[i][x][y]表示第i次传送后位于(x,y)的方案数。但是这种方法的问题在于，坐标范围可能非常大，无法用数组存储。

关键观察

注意到每种传送方式的使用次数决定了最终位置。设三种传送方式分别使用了t₁、t₂、t₃次（t₁ + t₂ + t₃ = N），那么最终位置为： (x, y) = (t₁A + t₂C + t₃E, t₁B + t₂D + t₃F)

因此，我们可以将状态表示为(t₁, t₂, t₃)，而不需要直接记录坐标。

解法一：记忆化搜索

使用记忆化搜索可以优雅地解决这个问题。定义dfs(x, y, z)表示三种传送方式分别使用了x、y、z次的方案数。

#include<bits/stdc++.h>
#define int long long
using namespace std;
set<pair<int,int>> s;
int n,m,a,b,c,d,e,f,g[301][301][301];
const int mod = 998244353;

int dfs(int x,int y,int z) {
    int x0 = a*x + c*y + e*z;
    int y0 = b*x + d*y + f*z;
    if(s.find({x0,y0}) != s.end()) return 0; // 障碍点
    if(x + y + z == n) return 1; // 完成N次传送
    if(g[x][y][z]) return g[x][y][z]; // 记忆化
    return g[x][y][z] = (dfs(x+1,y,z) + dfs(x,y+1,z) + dfs(x,y,z+1)) % mod;
}

signed main() {
    ios::sync_with_stdio(false);
    cin >> n >> m >> a >> b >> c >> d >> e >> f;
    for(int i=0; i<m; i++) {
        int x,y; cin >> x >> y;
        s.insert({x,y});
    }
    cout << dfs(0,0,0) << endl;
    return 0;
}

复杂度分析

• 时间复杂度：O(N³)，因为状态数为组合数C(N+2,2) ≈ N²/2，每个状态处理时间为O(1)
• 空间复杂度：O(N³)，用于存储记忆化数组

解法二：动态规划

也可以使用递推式的动态规划来解决。定义dp[i][u][v]表示前i次传送中，第一种方式用了u次，第二种方式用了v次的方案数。

#include <bits/stdc++.h>
using namespace std;
const int N = 310, mod = 998244353;

int n, m, a, b, c, d, e, f;
long long ans, dp[N][N][N];
map<pair<long long, long long>, bool> mp;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m >> a >> b >> c >> d >> e >> f;
    while (m--) {
        int x, y;
        cin >> x >> y;
        mp[{x, y}] = 1;
    }
    dp[0][0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int u = 0; u <= i; u++) {
            for (int v = 0; u + v <= i; v++) {
                int w = i - u - v;
                long long x = 1ll * u * a + 1ll * v * c + 1ll * w * e;
                long long y = 1ll * u * b + 1ll * v * d + 1ll * w * f;
                if (!mp.count({x, y})) {
                    dp[i][u][v] = dp[i - 1][u][v];
                    if (u) dp[i][u][v] = (dp[i][u][v] + dp[i - 1][u - 1][v]) % mod;
                    if (v) dp[i][u][v] = (dp[i][u][v] + dp[i - 1][u][v - 1]) % mod;
                    if (i == n) ans = (ans + dp[i][u][v]) % mod;
                }
            }
        }
    }
    cout << ans;
    return 0;
}

复杂度分析

• 时间复杂度：O(N³)，三重循环
• 空间复杂度：O(N³)，可以优化到O(N²)但代码会更复杂