ALGO-192 二元函数

题目链接

代码

算法：栈的使用

#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>

using namespace std;

stack<int> num;

void eval(int a, int b) {
    int y = num.top(); num.pop();
    int x = num.top(); num.pop();
    int res = a * x + b * y;
    num.push(res);
}

int main() {
    int a, b;
    cin >> a >> b;
    string str;
    cin >> str;
    for(int i = 0; i < str.size(); i ++) {
        if(str[i] == ')') {
            eval(a, b);
        }else if(isdigit(str[i]) || str[i] == '-') {
            bool flag = false;
            if(str[i] == '-')
                flag = true;

            int j = i + (flag ? 1 : 0);
            int x = 0;
            while(j < str.size() && isdigit(str[j])) {
                x = x * 10 + str[j] - '0';
                j ++;
            }
            i = j - 1;
            if(flag)
                 x = -x;
            num.push(x);
        }
    }

    cout << num.top() << endl;
}

ALGO-990 Sticks

题目链接

代码

算法：dfs剪枝

#include<iostream>
#include<algorithm>
#include<cstring>
#define int long long
#define sd(x) scanf("%d", &x)
using namespace std;

const int N = 1e2;
int n; // 当前被分割的木棍数量
int p[N];
bool vis[N];
int sum_stick; // 原始长度的木棍数量

// 当前在拼接哪一根被分割的木棍, 当前在拼接的木棍长度为sum, 已拼接成的木棍数目, 假定的原始木棍长度
bool dfs(int cur, int sum, int cnt, int k) {

    if(cnt == sum_stick)
        return true;

    for(int i = cur; i < n; i ++) {

        // 冗余剪枝            
        if(vis[i] || (i && p[i] == p[i - 1] && !vis[i - 1]))
            continue;

        if(p[i] + sum == k) {
            vis[i] = true;
            if(dfs(0, 0, cnt + 1, k)) {
                return true;
            }
            vis[i] = false;
            return false;
        }

        if(p[i] + sum < k) {
            vis[i] = true;
            if(dfs(i + 1, p[i] + sum, cnt, k))
                return true;
            vis[i] = false;
            if(sum == 0) {
                return false;
            }
        }
    }

    return false;
}

signed main() {
    while(sd(n) && n){
        int sum = 0;
        for(int i = 0; i < n; i ++) {
            cin >> p[i];
            sum += p[i];
        }

        // 优化搜索顺序
        sort(p, p + n, greater<int>());

        int ans = -1;

        for(int i = p[0]; i <= sum / 2; i ++) {
            // i为每根木棍长度
            // 可行性剪枝
            if(sum % i == 0) {
                memset(vis, false, sizeof vis);
                sum_stick = sum / i;
                if(dfs(0, 0, 0, i)) {
                    ans = i;
                    break;
                }
            }
        }

        if(ans == -1) {
            cout << sum << endl;
        }else {
            cout << ans << endl;
        }
    }
    return 0;
}

ALGO-965 进击的青蛙

算法：递推

代码

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 1e6 + 10;
int a[N];
int mod = 1000000007;
int f[N];

int main() {
    int n;
    cin >> n;

    f[0] = 1;

    for(int i = 1; i <= n; i ++) {
        cin >> a[i];
    }

    for(int i = 1; i <= n; i ++) {
        if(i >= 1 && a[i] == 0) f[i] = (f[i] + f[i - 1]) % mod;
        if(i >= 2 && a[i] == 0) f[i] = (f[i] + f[i - 2]) % mod;
        if(i >= 3 && a[i] == 0) f[i] = (f[i] + f[i - 3]) % mod;
    }

    if(f[n]) {
        cout << f[n] << endl;
    }else {
        cout << "No Way!" << endl;  
    }

    return 0;
}