盒子
盒子
文章目录
  1. 题目
  2. 1001 Revenge of Segment Tree (水题)
    1. 思路
  3. 1002 Revenge of LIS II (dp)
  4. Revenge of Nim II (高斯消元)
  5. Revenge of iSea (数学 概率)
  6. 更新日志

BestCoder Round 16

题目

源地址:http://acm.hdu.edu.cn/search.php?field=problem&key=BestCoder+Round+%2316&source=1&searchmode=source

  • 5086 Revenge of Segment Tree (水题)
  • 5087 Revenge of LIS II (dp)
  • 5088 Revenge of Nim II (高斯消元)
  • 5089 Revenge of iSea (数学 概率)

BC第16场,感觉题目质量还可以。最近状态不太好,以前组队赛太依赖孟神的dp了,导致现在完全不会dp。。这是个忧伤的故事

1001 Revenge of Segment Tree (水题)

求一个序列的所有连续子序列的序列和的和。

思路

考虑每个数出现在多少个子序列之中,假设第i个数为$A_i$,区间为[L,R]。那么包含$A_i$的区间满足$L{\leq}i{\bigcap}R{\geq}i$。累加$(L+1){\times}(N−R){\times}A[i]$就可以了。
复杂度:O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/*
ID: wuqi9395@126.com
PROG:
LANG: C++
*/
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<fstream>
#include<cstring>
#include<ctype.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF (1 << 30)
#define LINF (1LL << 60)
#define PI acos(-1.0)
#define mem(a, b) memset(a, b, sizeof(a))
#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, a, n) for (int i = n - 1; i >= a; i--)
#define eps 1e-6
#define debug puts("===============")
#define pb push_back
#define mkp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define POSIN(x,y) (0 <= (x) && (x) < n && 0 <= (y) && (y) < m)
typedef long long ll;
typedef unsigned long long ULL;
const int N = 447000 + 30;
const int mod = 1000000007;
int n;
int main () {
int t;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
ll ans = 0;
int k;
for (int i = 1;i <= n; i++) {
scanf("%d", &k);
ll s = i, ed = (n - i) + 1;
ll p = (((s * ed) % mod) * k) % mod;
ans = (ans + p) % mod;
}
cout<<ans<<endl;
}
return 0;
}

1002 Revenge of LIS II (dp)

求序列第二长的上升子序列。
http://siofive.github.io/2014/11/04/BC16_2/

Revenge of Nim II (高斯消元)

Nim游戏的后手作弊移走一些整堆的物体(不能全拿走),可以保证先手必败吗?
http://siofive.github.io/2014/11/04/BC16_3/

Revenge of iSea (数学 概率)

给出N道难度递增的题目,难度用可能做出的百分比表示,选出K道题目使得做出K-1道题目的概率最大。
http://siofive.github.io/2014/11/04/BC16_4/

更新日志

  • 2014-11-4 AK