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]);
}
}
分享到:
相关推荐
Some Solution of Problem in SPOJ (Sphere Online Judge) solved in various algorithm.
Online Judge Problem solution VN.SPOJ
Some solution of problems in SPOJ, all of them use DP technique to attack the problems.
SPOJ 应对spoj.com的挑战
My solution for some spoj problems
RandomGoCode:算法,SPOJ,涂鸦...但是在Go中!
SPOJ解决方案 我已解决的SPOJ问题的解决方案。 仅当您自己尝试过该问题并且无法提出任何解决方案,也可以随意报告任何错误并为该存储库提供解决方案时,才请参考这些解决方案。 我的个人资料链接 会费 分叉仓库并为...
SPOJ题库( http://www.spoj.pl)的离线题库。 包括索引+内容。PDF格式。 主要是Classical的problemset。
SPOJ( )上选定问题的解决方案
SPOJ 解决来自难题
Spoj 用户工具基于 Django 的 Spoj 用户分析工具。 目前托管在 Google Appengine 上: ://spojtool.appspot.com/安装获取列出的包,并将它们放在指定的项目目录中。 为了安全,请修改 secret_key.py 中的 SECRET_KEY...
杨弋SPOJ做题表格
spoj reverse 的solution
个人这两天做的SPOJ上的题目。。 主要都是前面的几道,不是很多 希望能收到资源分。。
2.12 求 A B 的约数之和对 MOD 取模 . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.13 莫比乌斯反演 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.13.1 莫比乌斯...
SPOJ上的SUBLEX,后缀自动机实现,可以作为后缀自动机的模板,包含计数排序和dfs两种更新方式实现。
hdu 1914稳定婚姻 sgu176 有源汇的上下界 求最小满足的流 poj 2230 递归求欧拉回路 poj 2985 bst模板 poj2723 2-sat验证,二分答案 poj2455 dinic (ek会超时) hdu1689 求最小奇数环 poj2391 isap最快,dinic不减枝...
A platform which can host online programming competitions (much like codechef and spoj). API of Hackerearth was used for online compilation and execution of programmes. Technology Used : HTML,CSS,...
SPOJ-Solutions:SPOJ算法问题的解决方案
spoj MSTS kruskal +生成树