首页 > 代码库 > 小问题

小问题

2024-07-12 21:38:29   224人阅读

内容『给定一个字符串 str 和一个数字 P ，并且由字符串的第I项和第J项的乘积构成  矩阵B的元素dij；

　　　　矩阵生成后，在这个矩阵里找满足条件的矩形（矩形内的元素包『括边界的元素』的和为P）

　　　　问一共有多少个这样的矩形（数字P【0，1e9】，串的长度【1，4000】）』

 我们来看一下由“1234”生成的矩阵！

 

（虽然很难看 请忍受下，红色的没啥意义）其中绿色的矩阵由  3*3+3*4+4*4+4*3  生成和为49！

对于这个矩阵可以 意测出就是 本题 就是求

对给定的字符串STR 求 俩个区间段和的乘积！如果积与P 相等那么就是所球

假设俩个区是【a，b】，【b，c】 那么有点（a，c）和（b，d）所组成的举行的积就是P  ，并且如果俩个区间不同那么就有对称的另一个矩形

比如  点（2，3）到 点 （4，4）  的矩阵是有该串 中【2，4】和与【3，4】的乘积！

 

对于数据范围也能看出 ！区间和！不多于 9*4000；

只要开一个数组记录下区间和可以出现多少次！

P==0，特判，其他的暴力就好了。

 

 1 int n,p; 2 char str[4005]; 3 long long sum[4005]; 4 long long t[40005]={0}; 5 int main() 6 { 7     scanf("%d%s",&p,str); 8     n=strlen(str); 9     sum[0]=str[0]-‘0‘;10     t[sum[0]]++;11     for(int i=1;i<n;i++)12         sum[i]=sum[i-1]+str[i]-‘0‘,t[sum[i]]++;13     for(int i=0;i<n;i++)14         for(int j=0;j<i;j++)15             t[sum[i]-sum[j]]++;16     if(p==0)17     {18         cout<<n*(n+1)*t[0]-t[0]*t[0]<<endl;19 ///     对于n个数字一共   n*(n+1)/2  组区间和  对于每一组都与 t[0]匹配，20 ///     因为对称所以和一共是n*(n+1)*t[0]，但是对于  [1,1]到[2,2]的矩阵没有对称的对象，21 ///     所以去重减去   t[0]*t[0]；22         return 0;23     }24     long long  ans=0;25     for(int i=1;i<=40000;i++)26         if(t[i]&&p%i==0&&p/i<=40000) ans+=t[i]*t[p/i];27     cout<<ans<<endl;28     return 0;29 }


联系
我们