欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

codevs1735 方程的解数(meet in the middle)

程序员文章站 2022-07-08 19:51:05
题意 "题目链接" Sol 把前一半放在左边,后一半放在右边 meet in the middle一波 统计答案的时候开始想的是hash,然而MLE了两个点 实际上只要排序之后双指针扫一遍就行了 cpp include using namespace std; const int MAXN = 7, ......

题意

sol

把前一半放在左边,后一半放在右边

meet in the middle一波

统计答案的时候开始想的是hash,然而mle了两个点

实际上只要排序之后双指针扫一遍就行了

#include<bits/stdc++.h>
using namespace std;
const int maxn = 7, max = 1e7 + 10;
int k[maxn], p[maxn], n, m, ans;
int a1[max], c1, a2[max], c2, cnt[max];
int fp(int a, int p) {
    int base = 1;
    while(p) {
        if(p & 1) base = base * a;
        a = a * a; p >>= 1;
    }
    return base;
}
void dfs(int x, int lim, int opt, int sum) {
    if(x == lim + 1) {
        if(!opt) a1[++c1] = sum;
        else a2[++c2] = -sum;
        return ;
    }
    for(int i = 1; i <= m; i++) dfs(x + 1, lim, opt, sum + k[x] * fp(i, p[x]));
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> k[i] >> p[i];
    if(n <= 2) {
        a1[++c1] = 0;
        dfs(1, n, 1, 0);
    } else {
        dfs(1, n / 2, 0, 0);
        dfs(n / 2 + 1, n, 1, 0);
    }
    sort(a1 + 1, a1 + c1 + 1);
    sort(a2 + 1, a2 + c2 + 1);
    int j = 1;
    for(int i = 1; i <= c2; i++) {
        if(i != 1 && (a2[i] == a2[i - 1])) {cnt[i] = cnt[i - 1]; continue;}
        while(a1[j] <= a2[i] && j <= c1) {
            if(a1[j] == a2[i]) cnt[i]++;
            j++;
        }
    }
    /*
    for(int i = 1; i <= c1; i++)
        for(int j = 1; j <= c2; j++)    
            ans += (a1[i] == a2[j]);
    */
    for(int i = 1; i <= c2; i++) ans += cnt[i];
    cout << ans;
    return 0;
}