`
zhouxiaojie
  • 浏览: 9402 次
  • 性别: Icon_minigender_2
  • 来自: 杭州
最近访客 更多访客>>
社区版块
存档分类
最新评论

spoj 11575. A Famous Equation

    博客分类:
  • spoj
dp 
阅读更多
https://www.spoj.pl/problems/EQ2/
我的做法在这个网站上能过,但是过不了杭电的,郁闷了很久。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[100],b[100],c[100];
char str[105];
int aa,bb,cc;
long long suma,sumb,sumc;
long long f[105][2];
int main()
{
    int i,j,k,t,cas=0,ss,tt;
    while(scanf("%s",str)!=EOF)
    {
        cas++;
        int len = strlen(str);
        aa=1;bb=1;cc=1;k=0;
        memset(f,0,sizeof(f));
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(c,0,sizeof(c));
        suma=0,sumb=0,sumc=0;
        int ttt=0;
        for(i=len-1;i>=0;i--)
        {
            if(str[i]=='=')break;
            if(str[i]=='?')ttt=1,c[cc++]=-1;
            else
            c[cc++]=str[i]-'0';
        }i--;k=max(k,cc);
        for(;i>=0;i--)
        {
            if(str[i]=='+')break;
            if(str[i]=='?')ttt=1,b[bb++]=-1;
            else
            b[bb++]=str[i]-'0';
        }i--;k=max(k,bb);
        for(;i>=0;i--)
        {
            if(str[i]=='?')ttt=1,a[aa++]=-1;
            else
            a[aa++]=str[i]-'0';
        }
        k=max(k,aa);
        int sa,ea,sb,eb,sc,ec;
        int flag=0,state=0;
        for(int l=1;l<k;l++)
        {
            if(state)break;
            sa=a[l]<0?((l<aa-1||aa==2)?0:1):a[l];
            ea=a[l]<0?9:a[l];
            sb=b[l]<0?((l<bb-1||bb==2)?0:1):b[l];
            eb=b[l]<0?9:b[l];
            sc=c[l]<0?((l<cc-1||cc==2)?0:1):c[l];
            ec=c[l]<0?9:c[l];
            if(flag==0)
            {
                ss=f[l][0],tt=f[l][1];
                for(i=sa;i<=ea;i++)
                {
                    for(j=sb;j<=eb;j++)
                    {
                        for(t=sc;t<=ec;t++)
                        {
                            if(i+j==10+t&&f[l-1][1]==0)
                              f[l][1]++;
                            if(i+j==t&&f[l-1][1]==0)
                              f[l][0]++;
                            if(f[l-1][1]&&i+j+1==10+t)
                              f[l][1]++;
                            if(f[l-1][1]&&i+j+1==t)
                              f[l][0]++;
                            if(f[l][0]>ss)flag=1;
                            if(f[l][1]>tt)flag=1;
                        }
                    }
                }
                if(ss==f[l][0]&&tt==f[l][1])
                {
                    state=1;break;
                }
                continue;
            }
            ss=f[l][0],tt=f[l][1];
            for(i=sa;i<=ea;i++)
            {
                for(j=sb;j<=eb;j++)
                {
                    for(t=sc;t<=ec;t++)
                    {
                        if(i+j==10+t)
                          f[l][1]+=(f[l-1][0]);
                        if(i+j==9+t)
                          f[l][1]+=(f[l-1][1]);
                        if(i+j==t)
                          f[l][0]+=(f[l-1][0]);
                        if(i+j+1==t)
                          f[l][0]+=(f[l-1][1]);
                    }
                }
            }
            if(ss==f[l][0]&&tt==f[l][1])
            {
                state=1;break;
            }
        }
        if(state)
        printf("Case %d: 0\n",cas);
        else
        printf("Case %d: %lld\n",cas,f[k-1][0]);
    }
}
分享到:
评论

相关推荐

    SPOJ-2.zip_SPOJ_SPOJ-TRIKA.cpp_online judge_sPOJ-Solution_spoj2

    《SPOJ在线判题平台的解题策略与实例解析》 SPOJ(Sphere Online Judge)是一个全球知名的在线编程竞赛平台,它为程序员提供了一个检验自己算法能力的场所。这个名为"SPOJ-2.zip"的压缩包包含了在SPOJ上解决不同...

    SPOJ.rar_SPOJ

    这个名为"SPOJ.rar_SPOJ"的压缩包文件,很可能包含了越南版SPOJ(VN.SPOJ)上的问题解决方案,帮助用户提升编程技能和算法理解。 在SPOJ平台上,用户可以遇到各种难度级别的算法问题,从基础的数据结构和算法到复杂...

    SPOJ.zip_SPOJ_sgu_them

    "SPOJ.zip_SPOJ_sgu_them"这个压缩包文件就包含了针对SPOJ上的一些问题的解决方案,特别的是,所有这些解决方案都采用了动态规划(Dynamic Programming, 简称DP)这一强大的算法思想。下面我们将深入探讨动态规划...

    CPP.zip_SPOJ-HOTELS.cpp_circular game spoj_cpp_segment tree_usac

    标题 "CPP.zip_SPOJ-HOTELS.cpp_circular game spoj_cpp_segment tree_usac" 提到了几个关键元素,包括一个编程挑战(SPOJ-HOTELS)、特定的编程语言(C++)、一种算法(circular game)以及数据结构(segment tree...

    SPOJ:应对spoj.com的挑战

    针对"SPOJ:应对spoj.com的挑战"这一主题,我们将深入探讨如何使用C#语言在SPOJ平台上有效地解决问题。 1. **SPOJ平台介绍** SPOJ是一个在线的编程竞赛平台,它提供了一个广泛的编程题目库,涵盖了数据结构、算法、...

    SPOJ-Solutions:解决了我解决的http://www.spoj.com问题的解决方案

    SPOJ解决方案 我已解决的SPOJ问题的解决方案。 仅当您自己尝试过该问题并且无法提出任何解决方案,也可以随意报告任何错误并为该存储库提供解决方案时,才请参考这些解决方案。 我的个人资料链接 会费 分叉仓库并为...

    SPOJ:我对 SPOJ 问题的解决方案 (www.spoj.com)

    SPOJ,全称为Sphere Online Judge,是一个在线的编程竞赛平台,它提供了各种算法和数据结构问题供用户解决,以提升编程技能和算法理解。在这个平台上,你可以使用多种编程语言,包括C++,来编写代码并提交解决方案。...

    SPOJ题库-离线题库-索引+内容+PDF

    SPOJ题库( http://www.spoj.pl)的离线题库。 包括索引+内容。PDF格式。 主要是Classical的problemset。

    SPOJ:解决来自 www.spoj.com 的难题

    SPOJ,全称为Sphere Online Judge,是一个在线编程竞赛平台,专为程序员提供了一个测试和提升算法技能的环境。在SPOJ上,用户可以挑战各种来自世界各地的编程难题,通常涉及数学、数据结构和算法等领域。这个压缩包...

    RandomGoCode:算法,SPOJ,涂鸦...但是在Go中!

    它为开发者提供了一个平台,可以在Go语言环境中练习和提升自己的算法技巧,同时也涉及到SPOJ(Sphere Online Judge)等在线编程竞赛平台的题目解决。该项目的目标是帮助Go程序员深入理解数据结构、算法,并通过实践...

    spoj做题表格

    标题:“spoj做题表格”与描述“杨弋SPOJ做题表格”共同指向了在SPOJ(Sphere Online Judge)平台上的编程题目列表,这通常被用于记录和跟踪解决算法问题的进度。SPOJ是一个知名的在线裁判系统,为全球范围内的...

    Spoj-User-Tool:基于 Django 的 Spoj.pl 用户分析工具

    Spoj 用户工具基于 Django 的 Spoj 用户分析工具。 目前托管在 Google Appengine 上: ://spojtool.appspot.com/安装获取列出的包,并将它们放在指定的项目目录中。 为了安全,请修改 secret_key.py 中的 SECRET_KEY...

    SPOJ极少量的源程序。

    【SPOJ极少量的源程序】这个主题主要涉及到的是编程竞赛平台SPOJ(Sphere Online Judge)上的一些编程挑战。SPOJ是一个在线的编程练习平台,它提供了各种算法和逻辑难题,让程序员通过编写代码来解决。下面将详细...

    spoj 第42题 reverse

    spoj reverse 的solution

    kuangbin acm模板超级好用

    2.12 求 A B 的约数之和对 MOD 取模 . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.13 莫比乌斯反演 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.13.1 莫比乌斯...

    sublex.tar.gz_SUBLEX_spoj SUBLEX

    《SUBLEX与后缀自动机在SPOJ平台的应用》 SUBLEX是SPOJ平台上一个关于后缀自动机(Suffix Automaton)的挑战,这个题目旨在考察程序员对后缀自动机的理解以及实现能力。后缀自动机是一种非常重要的字符串处理工具,...

    Problem Set 1.zip_FFT simulink_SPOJ

    标题中的"Problem Set 1.zip_FFT simulink_SPOJ"揭示了这是一个关于傅立叶变换(FFT)的项目,具体来说是8点快速傅立叶变换(8-point Fast Fourier Transform),并且它与MATLAB仿真工具Simulink以及在线编程挑战...

    acm pku spoj sgu 经典 图论题解题报告

    hdu 1914稳定婚姻 sgu176 有源汇的上下界 求最小满足的流 poj 2230 递归求欧拉回路 poj 2985 bst模板 poj2723 2-sat验证,二分答案 poj2455 dinic (ek会超时) hdu1689 求最小奇数环 poj2391 isap最快,dinic不减枝...

    MSTS.rar_ MSTS-CN_MSTS-CN_SPOJ_msts

    本主题将深入探讨Kruskal算法及其在SPoj(Sphere Online Judge)在线编程平台上的应用。 首先,让我们了解什么是MSTS(Minimum Spanning Tree)。在无向加权图中,MSTS是一棵包括所有顶点的树,其边的权重之和尽...

    SPOJ-Solutions:SPOJ算法问题的解决方案

    SPOJ(Sphere Online Judge)是一个在线编程竞赛平台,它提供了大量的算法问题供程序员解决,以提高他们的编程技能和算法理解。"SPOJ Solutions"是这个领域的一个资源集合,包含了解决SPOJ上各种问题的代码示例,...

Global site tag (gtag.js) - Google Analytics