【Codeforces 466C】Number of Ways
2024-09-06 19:20:59
【链接】 我是链接,点我呀:)
【题意】
让你把数组分成3个连续的部分
每个部分的和要一样
问你有多少种分法
【题解】
先处理出来num[i]
表示i..n这里面有多少个j
满足aft[j] = aft[i]/2
这aft[i]=a[j]+a[j+1]..+a[n]
然后for从1..n
看看pre[i]*2=aft[i+1]是否成立。
如果成立的话那么答案就加上num[i+1]
【代码】
import java.io.*;
import java.util.*;
public class Main {
static int N = (int)5e5;
static InputReader in;
static PrintWriter out;
public static void main(String[] args) throws IOException{
in = new InputReader();
out = new PrintWriter(System.out);
//code start from here
new Task().solve(in, out);
out.close();
}
static class Task{
public void solve(InputReader in,PrintWriter out) {
int n = in.nextInt();
int []a = new int[N+10];
long []pre = new long[N+10];
long []aft = new long[N+10];
int []num = new int[N+10];
for (int i = 1;i <= n;i++) a[i] = in.nextInt();
for (int i = 1;i <= n;i++) pre[i] = pre[i-1]+a[i];
for (int i = n;i >= 1;i--) aft[i] = aft[i+1]+a[i];
Hashtable<Long, Integer> dic = new Hashtable<Long,Integer>();
for (int i = n;i >= 1;i--) {
if (aft[i]%2==0) {
long temp = aft[i]/2;
if (dic.get(temp)!=null)
num[i] = dic.get(temp);
}
Integer temp1 = dic.get(aft[i]);
if (temp1==null) {
dic.put( aft[i], 1);
}else {
dic.put(aft[i], temp1+1);
}
}
long ans = 0;
for (int i = 1;i <=n;i++) {
long cur = pre[i];
cur = pre[n]-cur;
if (cur!=pre[i]*2) {
continue;
}
ans = ans + num[i+1];
}
out.println(ans);
}
}
static class InputReader{
public BufferedReader br;
public StringTokenizer tokenizer;
public InputReader() {
br = new BufferedReader(new InputStreamReader(System.in));
tokenizer = null;
}
public String next(){
while (tokenizer==null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(br.readLine());
}catch(IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
}
最新文章
- Hadoop HDFS编程 API入门系列之HdfsUtil版本2(七)
- 【笔记】select2的使用
- android ListView详解继承ListActivity
- pyzmq missing when running ipython notebook
- oracle11g空表不能导出记录
- 基于jQuery向下弹出遮罩图片相册
- 微软的COM中GUID和UUID、CLSID、IID
- NOIP-2003 加分二叉树
- zoj 3657 策略题 easy
- java web开发 高并发处理
- linux(ubuntu)GCC编译包含库函数的问题
- Python条件判断 if-else for循环 while循环 break continue
- 从 Spring Cloud 看一个微服务框架的「五脏六腑」
- [转]经验分享:微信小程序外包接单常见问题及流程
- find中的-print0和xargs中-0的奥妙【转】
- Angular动态表单生成(八)
- java类同时引用父类和接口的成员变量,需要指明是父类的还是接口的
- 【最强】微软Tech Summit 2017动手实验室教程
- Apache Hive (七)Hive的DDL操作
- 使用js实现单向绑定