hdu 5828 Rikka with Sequence

多校8的一道题。。。 【看标题识出题人 ←_←
非常蛋疼的一道题,官方题解根本不知道在说什么,标程写得跟坨屎一样= =
先贴一份比赛中菊苣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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
/************************************************
*Author :mathon
*Email :luoxinchen96@gmail.com
*************************************************/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <stack>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
#define xx first
#define yy second
#define pr(x) cout << #x << " " << x << " "
#define prln(x) cout << #x << " " << x << endl
#define lson l, m, rt << 1
#define rson m+1, r, rt << 1|1
template<class T> inline T lowbit(T x) { return x & (-x); }
const int MAXN = 1e5 + 5;
int A[MAXN];
struct SegT {
ll sum[MAXN<<2];
ll is_same[MAXN<<2], lazy[MAXN<<2];
void init() {
memset(sum, 0, sizeof(sum));
memset(is_same, 0, sizeof(is_same));
memset(lazy, 0, sizeof(lazy));
}
void push_up(int rt) {
if(is_same[rt << 1] && is_same[rt << 1 | 1] &&
is_same[rt << 1] == is_same[rt << 1 | 1]) {
is_same[rt] = is_same[rt << 1];
} else {
is_same[rt] = 0;
}
sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
void push_down(int rt, int l, int r) {
int m = (l + r) >> 1;
if(is_same[rt]) {
is_same[rt << 1] = is_same[rt];
is_same[rt << 1 | 1] = is_same[rt];
sum[rt << 1] = is_same[rt] * (m - l + 1);
sum[rt << 1 | 1] = is_same[rt] * (r - m);
} else {
lazy[rt << 1] += lazy[rt];
lazy[rt << 1 | 1] += lazy[rt];
sum[rt << 1] += lazy[rt] * (m - l + 1);
sum[rt << 1 | 1] += lazy[rt] * (r - m);
lazy[rt] = 0;
if(is_same[rt << 1]) {
is_same[rt << 1] += lazy[rt << 1];
lazy[rt << 1] = 0;
}
if(is_same[rt << 1 | 1]) {
is_same[rt << 1 | 1] += lazy[rt << 1 | 1];
lazy[rt << 1 | 1] = 0;
}
}
}
void build(int l, int r, int rt) {
if(l == r) {
sum[rt] = A[l];
is_same[rt] = A[l];
return;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
push_up(rt);
}
void update1(int L, int R, int x, int l, int r, int rt) {
if(L <= l && r <= R) {
sum[rt] += (ll)x * (r - l + 1);
if(is_same[rt]) {
is_same[rt] += x;
} else {
lazy[rt] += x;
}
return;
}
int m = (l + r) >> 1;
push_down(rt, l, r);
if(m >= L) update1(L, R, x, lson);
if(m < R) update1(L, R, x, rson);
push_up(rt);
}
void update2(int L, int R, int l, int r, int rt) {
if(L <= l && r <= R && is_same[rt]) {
is_same[rt] = sqrt(is_same[rt]);
sum[rt] = is_same[rt] * (r - l + 1);
return;
}
int m = (l + r) >> 1;
push_down(rt, l, r);
if(m >= L) update2(L, R, lson);
if(m < R) update2(L, R, rson);
push_up(rt);
}
ll query(int L, int R, int l, int r, int rt) {
if(L <= l && r <= R) {
return sum[rt];
}
int m = (l + r) >> 1;
push_down(rt, l, r);
ll res = 0;
if(m >= L) res += query(L, R, lson);
if(m < R) res += query(L, R, rson);
return res;
}
}seg;
int main(void) {
#ifdef MATHON
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
int T; scanf("%d", &T);
while(T--) {
int n, m;
scanf("%d%d", &n, &m);
seg.init();
for (int i = 1; i <= n; i++) {
scanf("%d", &A[i]);
}
seg.build(1, n, 1);
for (int i = 0; i < m; i++) {
int op;
scanf("%d", &op);
if(op == 1) {
int l, r, x;
scanf("%d%d%d", &l, &r, &x);
seg.update1(l, r, x, 1, n, 1);
} else if(op == 2) {
int l, r;
scanf("%d%d", &l, &r);
seg.update2(l, r, 1, n, 1);
} else if(op == 3) {
int l, r;
scanf("%d%d", &l, &r);
ll res = seg.query(l, r, 1, n, 1);
printf("%lld\n", res);
}
}
}
return 0;
}

阅读全文

NOIP2012 借教室(classroom)

http://codevs.cn/problem/1217/
唉。。。即使是以我四年后的水平也要改一遍。。。
太菜了。。。
应该是目前最常用的线段树写法。。。确实是能过的

阅读全文

Crypto-特殊的日子

特殊的日子

阅读全文

PPC-字符统计

字符统计

题意也没什么好说的,主要是找了找 python 好用的 http 请求库,发现 requests 真的是很好用啊。。。还有就是一定要看清楚表单。。。

阅读全文

欧拉函数为什么是积性函数

以下全文转载自:http://www.cnblogs.com/372465774y/archive/2012/10/16/2726282.html

阅读全文

CCCC初赛 关于堆的判断

https://www.patest.cn/contests/gplt/L2-012
题意就不用我说了
比赛中写了个丑的不行的程序。。。
于是后来又写了一个非常STL风格的
想了想还是丢到博客了

阅读全文

广东工业大学(GDUT)2016校赛决赛

http://gdutcode.sinaapp.com/problemset.php?page=2
从1169~1175题

阅读全文

ACM 专题训练 最短最长路

A HDOJ-2544
模板题。不解释了。
顺便学习了一下dij+优先队列的姿势。
【感觉代码量跟普通dij很接近啊。。。
每个点入队一次,复杂度 O(NlogN)

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
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int,int> pii;
const int N=101;
const int M=10001*2;
const int INF=1<<29;
struct edge
{
int go,next,val;
};
edge eg[M];
int last[N],done[N],d[N],pre[N];
int tot;
void add(int x,int y,int z)
{
eg[++tot].go=y;
eg[tot].val=z;
eg[tot].next=last[x];
last[x]=tot;
}
int main()
{
int n,m,i,x,y,z;
while (scanf("%d%d",&n,&m),n)
{
tot=0;
memset(last,0,sizeof(last));
for (i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
priority_queue<pii,vector<pii>,greater<pii> > q;
for (i=1;i<=n;i++) d[i]=INF;
memset(done,0,sizeof(done));
memset(pre,0,sizeof(pre));
d[1]=0;pre[1]=1;
q.push(make_pair(0,1));
while (!q.empty())
{
pii u=q.top();
q.pop();
int v=u.second;
if (done[v]) continue;
done[v]=1;
for (i=last[v];i;i=eg[i].next)
{
int x=eg[i].go;
if (d[x]>d[v]+eg[i].val)
{
d[x]=d[v]+eg[i].val;
pre[x]=v;
q.push(make_pair(d[x],x));
}
}
}
printf("%d\n",d[n]);
}
return 0;
}

阅读全文

蓝桥杯 历届试题 大臣的旅费

。。。其实题意就是树的直径。。。
感觉自己挺傻逼的。。。直径就懂 最远路就不懂。。。
求直径就不用说了吧。。。自己查去。。。

。。。莫名其妙写了个O(n)的DP。。。

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
57
58
59
60
61
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=10010;
struct edge
{
int go,v,next;
};
edge eg[2*N];
int last[N],fm[N],sm[N];
//fm[] first max 记儿子、孙子等到该节点的最远路 sm[] 次远路
//当然,这两个值不能来自于同一个子树,因为不能重复经过结点
int tot=0;
void add(int x,int y,int z)
{
eg[++tot].go=y;
eg[tot].v=z;
eg[tot].next=last[x];
last[x]=tot;
}
void dfs(int x,int fa)
{
if (last[x]==0) return;
int p=0,q=0,i;
for (i=last[x];i;i=eg[i].next)
{
int u=eg[i].go;
if (u==fa) continue;
dfs(u,x);
if (eg[i].v+fm[u]>p)
{
q=p;
p=eg[i].v+fm[u];
}
else if (eg[i].v+fm[u]>q) q=eg[i].v+fm[u];
}
fm[x]=p;sm[x]=q;
}
int main()
{
int n,i,x,y,z,ans;
scanf("%d",&n);
for (i=1;i<n;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
dfs(1,0);
ans=-1;
for (i=1;i<=n;i++)
ans=max(ans,fm[i]+sm[i]);
printf("%d\n",ans*(ans+1)/2+ans*10);
return 0;
}

阅读全文

POJ 2823 //单调队列

选C++交
选C++交
选C++交
【重说三
因为是队里的专题训练。。。
所以我知道这题肯定是单调队列。。。
而且一看数据范围和时限。。。
12000ms 逗我?
随手一交。RE了。。。
再随手一交。尼玛!T了!!!
这怎么可能!!!
单调队列是 O(n) 啊!啊啊啊啊啊!!
然后再各种查资料查程序。。。
提交别人写的 AC 程序竟然还是TLE。。。
过了好几天(没错 好几天!)
跑到POJ的原题交了一下。
果然还是TLE了。。。
然后又开始搜各种搜。。。
直到发现这两个:
http://blog.csdn.net/chl_3205/article/details/8706307
http://blog.csdn.net/yihuikang/article/details/7771170
语言选到C++。。。果然 AC 了。。。
生无可恋的眼神 T^T

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
#include <cstdio>
#include <cstring>
const int N=1000010;
int a[N],q[N],c[N];
int main()
{
int n,k,i,l,r;
scanf("%d%d",&n,&k);
for (i=1;i<=n;i++) scanf("%d",&a[i]);
l=1;
r=0;
for (i=1;i<=k;i++)
{
while (q[r]>=a[i]&&r>=l) r--;
c[++r]=i;
q[r]=a[i];
}
for (;i<=n;i++)
{
printf("%d ",q[l]);
while (q[r]>=a[i]&&r>=l) r--;
c[++r]=i;
q[r]=a[i];
if (i-k>=c[l]) l++;
}
printf("%d\n",q[l]);
l=1;
r=0;
for (i=1;i<=k;i++)
{
while (q[r]<=a[i]&&r>=l) r--;
c[++r]=i;
q[r]=a[i];
}
for (;i<=n;i++)
{
printf("%d ",q[l]);
while (q[r]<=a[i]&&r>=l) r--;
c[++r]=i;
q[r]=a[i];
if (i-k>=c[l]) l++;
}
printf("%d\n",q[l]);
return 0;
}

阅读全文