题解 | 双色塔

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

class Solution {
private:
    static const int MOD = 1000000007;
    
public:
    int buildTower(int red, int green) {
        // Handle special case
        if (red == 0 || green == 0) {
            return 1;
        }
        
        // Make sure red is smaller
        if (red > green) {
            swap(red, green);
        }
        
        vector<int> dp(300001, 0);
        dp[0] = dp[1] = 1;
        
        int currentSum = 1;
        int left = 0, right = 0;
        
        // Calculate maximum possible levels
        for (int level = 2; level <= sqrt(2 * (red + green)); level++) {
            currentSum += level;
            
            // Calculate valid range
            int maxStones = min(currentSum, red);
            int minStones = max(currentSum - green, 0);
            
            if (minStones > maxStones) {
                break;
            }
            
            right = maxStones;
            left = minStones;
            
            // Update dp array
            for (int stones = right; stones >= level + 1; stones--) {
                dp[stones] = (dp[stones] + dp[stones - level]) % MOD;
            }
            dp[level]++;
        }
        
        // Calculate final result
        int result = 0;
        for (int i = left; i <= right; i++) {
            result = (result + dp[i]) % MOD;
        }
        
        return result;
    }
};

int main() {
    int red, green;
    cin >> red >> green;
    
    Solution solution;
    cout << solution.buildTower(red, green) << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    static class Solution {
        private static final int MOD = 1000000007;
        
        public int buildTower(int red, int green) {
            // 特殊情况处理
            if (red == 0 || green == 0) {
                return 1;
            }
            
            // 确保red是较小值
            if (red > green) {
                int temp = red;
                red = green;
                green = temp;
            }
            
            int[] dp = new int[300001];
            dp[0] = dp[1] = 1;
            
            int currentSum = 1;
            int left = 0, right = 0;
            
            // 计算最大可能层数
            for (int level = 2; level <= Math.sqrt(2 * (red + green)); level++) {
                currentSum += level;
                
                // 计算有效范围
                int maxStones = Math.min(currentSum, red);
                int minStones = Math.max(currentSum - green, 0);
                
                if (minStones > maxStones) {
                    break;
                }
                
                right = maxStones;
                left = minStones;
                
                // 更新dp数组
                for (int stones = right; stones >= level + 1; stones--) {
                    dp[stones] = (dp[stones] + dp[stones - level]) % MOD;
                }
                dp[level]++;
            }
            
            // 计算最终结果
            int result = 0;
            for (int i = left; i <= right; i++) {
                result = (result + dp[i]) % MOD;
            }
            
            return result;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int red = sc.nextInt();
        int green = sc.nextInt();
        
        Solution solution = new Solution();
        System.out.println(solution.buildTower(red, green));
        
        sc.close();
    }
}

class Solution:
    def buildTower(self, red, green):
        MOD = 1000000007
        
        # Handle special case
        if red == 0 or green == 0:
            return 1
            
        # Make sure red is smaller
        if red > green:
            red, green = green, red
            
        dp = [0] * 300001
        dp[0] = dp[1] = 1
        
        current_sum = 1
        left = right = 0
        
        # Calculate maximum possible levels
        for level in range(2, int((2 * (red + green)) ** 0.5) + 1):
            current_sum += level
            
            # Calculate valid range
            max_stones = min(current_sum, red)
            min_stones = max(current_sum - green, 0)
            
            if min_stones > max_stones:
                break
                
            right = max_stones
            left = min_stones
            
            # Update dp array
            for stones in range(right, level, -1):
                dp[stones] = (dp[stones] + dp[stones - level]) % MOD
            dp[level] += 1
            
        # Calculate final result
        result = sum(dp[left:right+1]) % MOD
        
        return result

# Read input and solve
red, green = map(int, input().split())
solution = Solution()
print(solution.buildTower(red, green))