hdu 3727 Jewel 主席树

最近在学主席树。。。反正感觉挺神奇的。。。
我高中想学,但是并没有看懂。可能是他们写的太屎了
kuangbin的板子也不太行。
poj 2104 那题入门,程序是没错
但是太耦合了,变量也有点意义不明。。。
于是我又去找了找。。。发现应该给一个比利比利的链接

阅读全文

HHUACM 综合训练2

本次综合训练主要是2013年的大连online的题目,有难有易,其中题意不太清楚和要求非常高的题目就直接剔除了。这样题数少了,于是又加了2题2016年大连online的我觉得挺不错的题目。后来发现知识点有点重叠,不过训练一下也无妨。

Find the maximum

题意:给出 $N$ 求出最小的 $2\leq n\leq N$ 使得 $n/\varphi(n)$ 最大。
题解:做这题首先要知道 $\varphi(n)$ 的计算式(不作证明): $\varphi(n)=n(1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})…(1-\frac{1}{p_{k}})$
$$\therefore n/\varphi(n)=\frac{1}{(1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})…(1-\frac{1}{p_{k}})}$$ $$=\frac{1}{\frac{p_1-1}{p_1}\frac{p_2-1}{p_2}…\frac{p_k-1}{p_k}}$$ $$=\frac{p_1}{p_1-1}\frac{p_2}{p_2-1}…\frac{p_k}{p_k-1}$$ $$=(1+\frac{1}{p_1-1})(1+\frac{1}{p_2-1})…(1+\frac{1}{p_k-1})$$
其中 $p_1,p_2,…p_k$ 为 $n$ 的质因子。(考虑到大家提交的很多代码都是打表,这里我写的比较详细)

阅读全文

hdu 4417 Super Mario

这题很明显离线做比较水。。。

把询问和每块砖都按高度排序
不断向树状数组插入满足条件的砖的位置
对每个询问求在 [L,R] 的区间和
也就是把前缀和减一减
【树状数组不能有0,所以传参之前我都加了1。。。

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1e5+5;
const int MAX=N;
struct query {
int l,r,h,id;
} q[N];
struct brick {
int h,pos;
} a[N];
int c[MAX],ans[N];
struct cmp {
template<typename T>
bool operator()(const T &a,const T &b)
{
return a.h<b.h;
}
};
void ins(int x,int d)
{
for (;x<MAX;x+=x&(-x)) {
c[x]+=d;
}
}
int query(int x)
{
int res=0;
for (;x;x-=x&(-x)) {
res+=c[x];
}
return res;
}
int main()
{
int T,n,m;
scanf("%d",&T);
for (int t=1;t<=T;t++) {
scanf("%d%d",&n,&m);
for (int i=0;i<n;i++) {
scanf("%d",&a[i].h);
a[i].pos=i;
}
for (int i=0;i<m;i++) {
scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].h);
q[i].id=i;
}
sort(a,a+n,cmp());
sort(q,q+m,cmp());
int k=0;
for (int i=0;i<m;i++) {
for (;k<n&&a[k].h<=q[i].h;k++)
ins(a[k].pos+1,1);
ans[q[i].id]=query(q[i].r+1)-query(q[i].l-1+1);
}
printf("Case %d:\n",t);
for (int i=0;i<m;i++)
printf("%d\n",ans[i]);
memset(c,0,sizeof(c));
}
return 0;
}

阅读全文

poj 3690 Constellations

最近在翻 ICPC online 的题。。。
终于找到一个能做的水题结果WA了七八次。。。
可能我果然还是不会C/C++语言吧 OTZ

行状压和列状压都行吧。。。
然后我就暴力枚举右下角
感觉写的比能查到的题解好看一点。。。
【差点就全服最短了2333333

阅读全文

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风格的
想了想还是丢到博客了

阅读全文