投稿
  1. 首页
  2. python

P1118 [USACO06FEB]Backward Digit Sums GS

code • 2022-5-6 • python • 阅读 27

P1118 [USACO06FEB]Backward Digit Sums GS,第1张

一、题目

二、解题思路
  1. 看到n的规模比较小，首先想到了使用暴力求解，最大规模为12！。但是考虑到，当n=12时，如果我们每次按照游戏的方式去模拟计算sum，效率将会很低。
  2. 分析游戏规则不难发现，sum的值由最上层的排序决定，并且每层均是上一层的和，所以，最终的sum必然可以写成第一层数字的和，即 s u m = ∑ a i ∗ k i sum=\sum{ai*ki} sum=∑ai∗ki，而且 k i ki ki与 a i ai ai无关。那么如果我们得到了 k i ki ki，计算效率将会显著提高。除此之外，通过模拟游戏的过程可以发现，数列 k i ki ki是关于中点对称的，根据这一特性，就可以将排序问题变为组合问题。
  3. 经过上面分析以后，实际上我们需要做的就两件事：穷举所有可能的排列和查看该排列的sum值是否等于目标值。值得注意的是，在穷举时，由于 k i ki ki对称的特性，我们并不需要穷举n!种可能，可以人为假定，对于位于对称位置上的两个数，左边的数一定大于右边的数，那么复杂度将会显著降低。以n=12为例，最大规模为 C 12 2 C 10 2 C 8 2 C 6 2 C 4 2 C 2 2 C^2_{12}C^2_{10}C^2_{8}C^2_{6}C^2_{4}C^2_{2} C122​C102​C82​C62​C42​C22​而非12！。
三、代码 
#inclass="superseo">clude
#include
#include
#include
#include
#include
#include
using namespace std;
int n,sum, ret[12], times[12]={0}, visit[13], final_ret[12];
int find_ret=false;

int comp(int data1[], int data2[]){
    for(int i=0;idata2[i])return 0;
        else if(data1[i]>n>>sum;
    if(n==1){
        if(sum==1)cout<<1;
    }
    else {
        search_times(n, 0);
        search_ret(0);
    }
    if(find_ret){
        for(int i=0;i

欢迎分享，转载请注明来源：内存溢出

原文地址: https://outofmemory.cn/langs/796209.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
code code 管理员组
0 0
上一篇 2022-05-06
下一篇 2022-05-06

发表评论

登录后才能评论

评论列表（0条）

保存