hdu1394

传送门

本题就是求循环移位后逆序数的最小值。
其实主要就是求序列的逆序数。
逆序数的求法很多,可以用归并排序求。
也可以用树状数组和线段树求逆序数。

逆序数求得之后,把第一个数移到最后的逆序数是可以直接得到的。
比如原来的逆序数是ans,把a[0]移到最后,减少逆序数a[0],同时增加逆序数n-a[0]-1个,就是ans-a[0]+n-a[0]-1;

只要i从0-n-1循环一遍取最小值就可以了。

代码

树状数组(AC):

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 5050;
int n, e[maxn];

int lowbit(int k){
return k & (-k);
}

void add(int k, int v){
while(k <= n){
e[k] += v;
k += lowbit(k);
}
}

int sum(int k){
int re = 0;
while(k > 0){
re += e[k];
k -= lowbit(k);
}
return re;
}

int a[maxn];

int main(){
while(~scanf("%d", &n)){
int ans = 0;
memset(e, 0, sizeof(e));
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
a[i]++;
ans += sum(n) - sum(a[i]);
add(a[i], 1); //注意这里e[k]并没有初始化为a[k],而是用到了类似差值的思想
}
int Min = ans;
for(int i = 1; i <= n; i++){
ans += n - a[i] - (a[i] - 1);
if(ans < Min) Min = ans;
}
printf("%d\n", Min);
}
return 0;
}

hdu4576

题目

一个圆盘,有n个编号(1,2,3……n),从1出发,每次能逆时针或顺时针走w步,问经过m次后,最终停留在区间[l,r]的概率。

解析

首先,取模运算是一定要把1到n换成0到n-1;其次,利用temp来进行奇偶变换。

引用自博客:

https://www.cnblogs.com/kevinACMer/p/3723531.html

代码

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
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define maxn 1000005
int n, m, l, r;
double dp[205][2];
int w[maxn];
int main(){
while(scanf("%d%d%d%d", &n, &m, &l, &r) && (n || m || l || r)){
for(int i = 0; i < m; ++i) scanf("%d", &w[i]);
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
int cur = 0;
for(int j = 0; j < m; ++j){
int t = w[j] % n;
cur ^= 1;
for(int i = 0; i < n; ++i)
dp[i][cur] = 0.5 * dp[(i + t) % n][cur ^ 1] + 0.5 * dp[(i - t) % n][cur ^ 1];
}
double ans = 0;
for(int i = l - 1; i < r; ++i) ans += dp[i][cur];
printf("%.4lf\n", ans);
}
return 0;
}

hdu1024

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=1024

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
#include <algorithm>
#define FI(a, b, c) for(int a = (b); a <= (c); a++)
#define FD(a, b, c) for(int a = (b); a >= (c); a--)
using namespace std;

int n, m, t;
long long d[1000005], l[1000005];

int main(){
while(scanf("%d %d", &m, &n) != EOF){
FI(i, 1, m) d[i] = l[i] = -1e15;

while(n--){
scanf("%d", &t);
FD(i, m, 1){
d[i] = max(d[i], l[i - 1]) + t;
l[i] = max(l[i], d[i]);
}
}
printf("%lld\n", l[m]);
}
}

You need to set client_id and slot_id to show this AD unit. Please set it in _config.yml.