AtCoder Beginner Contest 338 G. evall(枚举+递推 统计贡献)

2024-02-04 11:20

本文主要是介绍AtCoder Beginner Contest 338 G. evall(枚举+递推 统计贡献),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目

长为1e6的串,只由数字1-9、加号+、乘号*组成,

对1<=i<=j<=n,只要s[i]和s[j]均为数字,就将eval(i,j)(求值表达式)的值加入答案内

求答案对998244353取模的值

换言之,求以下程序的结果

s = input()
n = len(s)
ans, mod = 0, 998244353
def ok(x):return '0'<=x<='9'
for i in range(n):for j in range(i,n):if ok(s[i]) and ok(s[j]):ans = (ans + eval(s[i:j+1])) % mod
print(ans)

思路来源

乱搞ac

题解

把连乘的段单独处理,统计每一段的贡献

如果左侧顶到一个+号,那么加号往左的都可以取,右侧同理

如果左侧不是加号,那么左侧只能卡到i 

1234*2345*3456

枚举i=2时,这一位的贡献有:

2 23 234

234*2 234*23 234*234 234*2345

234*2345*3 234*2345*34 234*2345*345 234*2345*3456

发现需要处理一个形如(3+34+345+3456)的东西,

还需要处理一个形如2345*(3+34+345+3456)的东西,并加上2+23+234

于是开了一堆数组维护这些内容,

pre[i]表示i前有几个数字,suf[i]表示i后有几个数字

尺取相邻加号之间的段,处理连乘的贡献,

不妨称3+34+345+3456这样的段,叫3456这个数的前缀贡献

sum[i]形如(3+34+345+3456)+(2+23+234+2345),

只需要某个数的前缀贡献的时候,作差得到

sum2[i]形如2+23+234+2345*(3+34+345+3456),

转移要么乘上一个数,要么加上这个数的前缀贡献,可以递推实现

由4+45+456需要得到3+34+345+3456时,加上3333即可,

所以ten[i]维护10的幂次,形如1000,sten[i]维护其前缀和,形如1111

las[i]记录i这个位置后面的第一个符号的位置,可能为乘号或者加号

now[i]记录i这个位置所在的段往后延伸到尾部时,这个数字是多少

mul[i]表示i这个位置往后的第一个完整的数到尺取段尾这一段区间的积是多少

比如1+23*45*56+7,mul[4]表示45*56的值,而mul[3]表示23*45*56的值

总之,就是通过手玩发现,需要通过枚举+数贡献的方式计数,然后就是xjb乱搞

代码

#include<bits/stdc++.h>
#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<array>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=1e6+10,mod=998244353;
char s[N];
int n,pre[N],suf[N],sum[N],sum2[N],mul[N];
int ten[N],sten[N],cur,w,las[N],now[N],ans;
void add(int &x,int y){x=(x+y)%mod;
}
bool ok(char x){return '0'<=x && x<='9';
}
int cal(int l,int r){return (sum[l]-sum[r+1]+mod)%mod;
}
int main(){scanf("%s",s+1);n=strlen(s+1);s[0]=s[n+1]='+';ten[0]=sten[0]=1;rep(i,1,n){ten[i]=10ll*ten[i-1]%mod;sten[i]=(sten[i-1]+ten[i])%mod;}rep(i,1,n){pre[i]=pre[i-1]+ok(s[i]);}per(i,n,1){suf[i]=suf[i+1]+ok(s[i]);}for(int j=n+1;j>=0;){if(s[j]=='+'){mul[j]=1;las[j]=j;j--;continue;}int k=j;while(k && s[k]!='+')k--;cur=w=0;for(int i=j;i>k;--i){las[i]=las[i+1];sum[i]=sum[i+1];sum2[i]=sum2[i+1];mul[i]=mul[i+1];if(s[i]=='*'){cur=w=0;las[i]=i;continue;}cur++;int v=s[i]-'0';w=(w+1ll*v*ten[cur-1]%mod)%mod;now[i]=w;sum[i]=(sum[i+1]+1ll*v*sten[cur-1]%mod)%mod;//printf("i:%d sum2i:%d\n",i,sum2[i]);if(!ok(s[i-1])){sum2[i]=cal(i,las[i]-1)%mod;sum2[i]=(sum2[i]+1ll*w*sum2[las[i]]%mod)%mod;mul[i]=1ll*mul[i]*w%mod;}//printf("i:%d sum:%d sum2:%d las:%d cal:%d w:%d pre:%d\n",i,sum[i],sum2[i],las[i],cal(i,las[i]-1),w,sum2[las[i]]);}for(int i=k+1;i<=j;++i){if(s[i]=='*')continue;int w1=1ll*now[i]*sum2[las[i]]%mod;//*后面的sum2 和*前面结尾1的贡献 左端点在i 右端点在las[i]+号左的贡献int bs=(i==k+1?pre[k]+1:1);//左侧+左的也可以取(i=k+1时可以再往左任取)int w2=1ll*now[i]*mul[las[i]]%mod*suf[j+1]%mod;//右侧+右的也可以取 左端点在i 右端点在las[i]+号右的贡献int w3=cal(i,las[i]-1);w=(w1+w2)%mod;w=(w+w3)%mod;w=1ll*w*bs%mod;ans=(ans+w)%mod;//printf("i:%d s:%d las:%d now:%d bs:%d sum2lasi:%d w1:%d w2:%d w3:%d w:%d ans:%d\n",i,s[i]-'0',las[i],now[i],bs,sum2[las[i]],w1,w2,w3,w,ans);}j=k;}printf("%d\n",ans);return 0;
}
//2*(2+2*3+2*34)
/*
1*mul[2]
1*2*mul[3]
1*2*3*mul[4]
mul[3]+3*mul[4]
当前数做积2345*(3+34+345+3456)
+2+23+234+2345
每一段先乘完整数 然后加mul
两层递推
*/
/*
1+10*11+2
1 (2)
10 (2) 
10*1 (2)
10*11 (4)
*//*8 8*3 8*3*3 8*3*33*/

这篇关于AtCoder Beginner Contest 338 G. evall(枚举+递推 统计贡献)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/677325

相关文章

hdu1496(用hash思想统计数目)

作为一个刚学hash的孩子,感觉这道题目很不错,灵活的运用的数组的下标。 解题步骤:如果用常规方法解,那么时间复杂度为O(n^4),肯定会超时,然后参考了网上的解题方法,将等式分成两个部分,a*x1^2+b*x2^2和c*x3^2+d*x4^2, 各自作为数组的下标,如果两部分相加为0,则满足等式; 代码如下: #include<iostream>#include<algorithm

uva 568 Just the Facts(n!打表递推)

题意是求n!的末尾第一个不为0的数字。 不用大数,特别的处理。 代码: #include <stdio.h>const int maxn = 10000 + 1;int f[maxn];int main(){#ifdef LOCALfreopen("in.txt", "r", stdin);#endif // LOCALf[0] = 1;for (int i = 1; i <=

hdu 2489 (dfs枚举 + prim)

题意: 对于一棵顶点和边都有权值的树,使用下面的等式来计算Ratio 给定一个n 个顶点的完全图及它所有顶点和边的权值,找到一个该图含有m 个顶点的子图,并且让这个子图的Ratio 值在所有m 个顶点的树中最小。 解析: 因为数据量不大,先用dfs枚举搭配出m个子节点,算出点和,然后套个prim算出边和,每次比较大小即可。 dfs没有写好,A的老泪纵横。 错在把index在d

2014 Multi-University Training Contest 8小记

1002 计算几何 最大的速度才可能拥有无限的面积。 最大的速度的点 求凸包, 凸包上的点( 注意不是端点 ) 才拥有无限的面积 注意 :  凸包上如果有重点则不满足。 另外最大的速度为0也不行的。 int cmp(double x){if(fabs(x) < 1e-8) return 0 ;if(x > 0) return 1 ;return -1 ;}struct poin

2014 Multi-University Training Contest 7小记

1003   数学 , 先暴力再解方程。 在b进制下是个2 , 3 位数的 大概是10000进制以上 。这部分解方程 2-10000 直接暴力 typedef long long LL ;LL n ;int ok(int b){LL m = n ;int c ;while(m){c = m % b ;if(c == 3 || c == 4 || c == 5 ||

2014 Multi-University Training Contest 6小记

1003  贪心 对于111...10....000 这样的序列,  a 为1的个数,b为0的个数,易得当 x= a / (a + b) 时 f最小。 讲串分成若干段  1..10..0   ,  1..10..0 ,  要满足x非递减 。  对于 xi > xi+1  这样的合并 即可。 const int maxn = 100008 ;struct Node{int

flume系列之:查看flume系统日志、查看统计flume日志类型、查看flume日志

遍历指定目录下多个文件查找指定内容 服务器系统日志会记录flume相关日志 cat /var/log/messages |grep -i oom 查找系统日志中关于flume的指定日志 import osdef search_string_in_files(directory, search_string):count = 0

hdu4267区间统计

题意:给一些数,有两种操作,一种是在[a,b] 区间内,对(i - a)% k == 0 的加value,另一种操作是询问某个位置的值。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import

hdu4417区间统计

给你一个数列{An},然后有m次查询,每次查询一段区间 [l,r] <= h 的值的个数。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamRead

hdu3333区间统计

题目大意:求一个区间内不重复数字的和,例如1 1 1 3,区间[1,4]的和为4。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;