codeforce Number of Ways(暴力)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 500005
using namespace std;
typedef long long LL;
LL prefix[N], suffix[N], num[N];
LL cntSuf[N];
int main(){
    int n;
    scanf("%d", &n);
    for(int i=1; i<=n; ++i){
        scanf("%lld", &num[i]);
        prefix[i]=prefix[i-1]+num[i];//前缀和
    }
    for(int i=n; i>=1; --i)
        suffix[i]=suffix[i+1]+num[i];//后缀和
    LL s=prefix[n]/3;
    if(prefix[n]%3!=0){
        printf("0\n");
        return 0;
    }
    LL ans=0;
    for(int i=1; i<=n; ++i)
        if(suffix[n-i+1]==s) cntSuf[n-i+1]=cntSuf[n-i+2]+1;
        else cntSuf[n-i+1]=cntSuf[n-i+2];
    for(int i=1; i<=n; ++i)
        if(prefix[i]==s) ans+=cntSuf[i+2];
    printf("%lld\n", ans);
    return 0;
}

时间： 2024-11-22 17:13:13

codeforce Number of Ways(暴力)的相关文章

[LeetCode]91.Decode Ways

题目 A message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 - 'Z' -> 26 Given an encoded message containing digits, determine the total number of ways to decode it. For example, Given encode

【LeetCode从零单排】No198.House Robber &amp;&amp;No91.Decode Ways&amp;&amp;139 word break（动态规划典型应用）

1.题目一道典型的Dynamic Programming的题目. You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security

Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given an encoded message containing digits, determine the total number of ways to decode it. For example,Given encoded

[LeetCode] Decode Ways II 解码方法之二

A message containing letters from A-Z is being encoded to numbers using the following mapping way: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Beyond that, now the encoded string can also contain the character '*', which can be treated as one of the numbers

codeforces B - Preparing Olympiad（dfs或者状态压缩枚举）

B. Preparing Olympiad You have n problems. You have estimated the difficulty of the i-th one as integer ci. Now you want to prepare a problemset for a contest, using some of the problems you've made. A problemset for the contest must consist of at le

算法题：UVA 11125

Problem H Arrange Some Marbles Input: Standard Input Output: Standard Output you are given some marbles of n different color. You have to arrange these marbles in a line. The marbles adjacent with same color form a group. In each group there can be 1

实例：创建SWT项目的原生库导入问题

创建|问题|项目对于 Eclipse 3.1.x 而言,并没有书中提到的那个"org.eclipse.swt.win32_3.0.1"目录,自然也不会有目录下的 swt.jar 和 swt-win32-3063.dll,这个目录在 Eclipse 3.1.x 中被 org.eclipse.swt.win32.win32.x86_3.1.x.jar 文件替代,而原生库文件也被压缩到这个 jar 文件中,用 WinRAR 解压即可得到. 在安装了 SWT Designer 后通过其建立项

Common ASP.NET Code Techniques (DPC&dwc Reference)

Figure 2.1Output of Listing 2.1.1 when viewed through a browser. Adding Elements to an ArrayListIn Listing 2.1.1 we create two ArrayList class instances, aTerritories and aStates, on lines 5 and 6, respectively. We then populate the aStates ArrayList

Common ASP.NET Code Techniques (DPC&amp;DWC Reference)--3

asp.net Figure 2.2Output of Listing 2.1.2 when viewed through a browser. Adding Elements to a HashtableIn Listing 2.1.2, we begin by creating an instance of the Hashtable class, htSalaries, on line 5. Next, we populate this hash table with our variou