专栏首页数据结构与算法codevs1735 方程的解数(meet in the middle)

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

题意

题目链接

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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • T4701 【卜卜】树状数组模板

    题目描述 在二维平面内给定n个点: 0 x y v表示给(x,y)的权值减去v 1 x y v表示给(x,y)的权值加上v 然后有m个操作 0 x y v ,...

    attack
  • TopcoderSRM679 Div1 250 FiringEmployees(树形dp)

    有一个 \(n\) 个点的树,每个点有点权(点权可能为负) ,求包含点\(1\)的最 大权连通子图(的权值和) 。 \(n \leqslant 2500\)

    attack
  • 2017.5.13阶段模拟考试

    预计分数:100+50(其实感觉自己写的对)+100 实际分数:100+0+100 P1149 火柴棒等式 题目描述 给你n根火柴棍,你可以拼出多少个形如“A+...

    attack
  • TopcoderSRM679 Div1 250 FiringEmployees(树形dp)

    有一个 \(n\) 个点的树,每个点有点权(点权可能为负) ,求包含点\(1\)的最 大权连通子图(的权值和) 。 \(n \leqslant 2500\)

    attack
  • hdu1040

    @坤的
  • T4701 【卜卜】树状数组模板

    题目描述 在二维平面内给定n个点: 0 x y v表示给(x,y)的权值减去v 1 x y v表示给(x,y)的权值加上v 然后有m个操作 0 x y v ,...

    attack
  • 【未完成】1050 螺旋矩阵 (25 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • 2017.5.13阶段模拟考试

    预计分数:100+50(其实感觉自己写的对)+100 实际分数:100+0+100 P1149 火柴棒等式 题目描述 给你n根火柴棍,你可以拼出多少个形如“A+...

    attack
  • 挑战程序竞赛系列(95):3.6数值积分(1)

    挑战程序竞赛系列(95):3.6数值积分(1) 传送门:AOJ 1313: Intersection of Two Prisms 题意: 有一个侧棱与Z轴平行...

    用户1147447
  • 查找(上)

    AngelNH

扫码关注云+社区

领取腾讯云代金券