作者归档：Jack

洛谷 P2114 [NOI2014]起床困难综合症

参看题解：
https://www.luogu.org/blog/user17941/solution-p2114
https://www.luogu.org/blog/user25845/solution-p2114

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

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
int n, m, t[100005];
string s[100005];
int zero = 0, one = 0x7fffffff;
int ans = 0;
void process(int & x) {
for (int i = 1; i <= n; i++) {
switch (s[i][0]) {
case 'A':
x &= t[i];
break;
case 'O':
x |= t[i];
break;
case 'X':
x ^= t[i];
break;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; i++)cin >> s[i] >> t[i];
process(zero);
process(one);
for (int i = 31; i >= 0; i--) {
if (ans + (1 << i) > m)continue;
if (!(zero&(1<<i))&&(one&(1 << i)))ans |= (1 << i);
}
process(ans);
cout << ans;
}

Openjudge BJUTACM 2018 周末集训 1005:Largest Rectangle in a Histogram

发表评论

可以说是非常不好想也非常不好做的一道题了……大佬的提示是单调栈，自己随便想了想就开始写，结果就挂掉了，然后看题解，也没太大用，最后是单步调试让我差不多搞清楚了。Solve()函数里的每一行都博大精深，有很多用。我也实在讲不清楚，把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

#include<cstdio>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
long long solve(vector<long long> & heights) {
long long remax = 0;
stack<long long> spos;
heights.push_back(0);
for (int i = 0; i < heights.size(); i++) {
while (!spos.empty() && heights[spos.top()] >= heights[i]) {
int curpos = spos.top();
spos.pop();
remax = max(remax, heights[curpos] * (spos.empty() ? i : ((i - 1) - (spos.top() + 1) + 1))); //这里大部分题解写的是i-spos.top()-1，我搞明白之后把这里写成了易于理解的形式
}
spos.push(i);
}
return remax;
}
int main() {
do {
int n;
scanf("%d", &n);
if (n == 0)break;
vector<long long> v;
for (int i = 1; i <= n; i++) {
long long x;
scanf("%lld", &x);
v.push_back(x);
}
printf("%lld", solve(v));
} while (1);
}

此题为LeetCode原题：https://leetcode.com/problems/largest-rectangle-in-histogram/description/
该题BJUTACM地址：http://bjutacm.openjudge.cn/bjut2018/1005/
（数据范围有可能会不相同）
题解：
https://www.cnblogs.com/grandyang/p/4322653.html
https://blog.csdn.net/princexiexiaofeng/article/details/79652003
https://siddontang.gitbooks.io/leetcode-solution/content/array/largest_rectangle_in_histogram.html
https://tech.pic-collage.com/algorithm-largest-area-in-histogram-84cc70500f0c
我个人看题解是没看懂的，单步调试拯救了我。。如果看不懂就单步吧。。有的地方我没解释清楚，从网上搜搜题解就好。
强烈建议这道题单步跟，多跟几个样例，不单步你看不懂其中的逻辑。。
我按照雪花大佬做法写的，经我垃圾的改编加了一堆cruft：不要问我怎么回事我也搞不清楚

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

#include<cstdio>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
struct P {
long long h, i;
};
long long solve(vector<long long> & heights) {
long long remax = 0;
stack<P> s;
heights.push_back(0);
for (int i = 0; i < heights.size(); i++) {
long long l = i;
while (!s.empty() && s.top().h > heights[i]){
l = s.top().i;
remax = max(remax, s.top().h * ( (i - 1) - s.top().i + 1));
s.pop();
}
s.push(P{ heights[i],l });
}
return remax;
}
int main() {
do {
int n;
scanf("%d", &n);
if (n == 0)break;
vector<long long> v;
for (int i = 1; i <= n; i++) {
long long x;
scanf("%lld", &x);
v.push_back(x);
}
printf("%lld\n", solve(v));
} while (1);
}

雪花大佬的不cruft的代码

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

#include <iostream>
#include <algorithm>

using namespace std;

using ll = long long;

struct Candidate { // candidate rectangle. area = height * (end_pos - start_pos)
ll h; // the height
ll i; // the start position;
// end position is implied
};

Candidate monostack[100100];
ll size = 0;

ll max_area = 0;

void monostack_push(ll h, ll i) {
ll pos = i; // start pos

while (size > 0 && monostack[size - 1].h >= h) { // equality is optional
Candidate const & p = monostack[--size]; // pop

pos = p.i; // update start pos

max_area = max(max_area, p.h * (i - p.i));
}

monostack[size++] = {h, pos}; // push
}

int main() {
// init
size = 0;
max_area = 0;

// for each input
// monostack_push(height, pos);
// monostack_push(0, last pos + 1); // another trick

// output max_area
}

启用Google reCAPTCHA

2条回复

本站即日起启用Google reCAPTCHA进行评论验证。

Openjudge BJUTACM 1036:括号画家

发表评论

智障的一开始竟然想用递归/记忆化做。。。老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

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<vector>
#include<typeinfo>
using namespace std;
void E() {
cout << "No";
exit(0);
}
void S() {
cout << "Yes";
exit(0);
}
stack<char> s;
int main() {
char c;
while (cin >> c) {
switch (c) {
case '(':case '[':case '{':
s.push(c);
break;
case ')':case ']':case '}':
if (s.empty())E();
switch (c) {
case ')':
if (s.top() == '(')s.pop();
else E();
break;
case ']':
if (s.top() == '[')s.pop();
else E();
break;
case '}':
if (s.top() == '{')s.pop();
else E();
break;
}
}
}
S();
}

http://bjutacm.openjudge.cn/lianxi/1036/

Openjudge BJUTACM 1018:简单计算器

发表评论

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

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<stack>
#include<vector>
#include<typeinfo>
using namespace std;
int t;
stack<double> si;
stack<char> sc;
inline bool execute() {
if (sc.empty()) return false;
double x2 = si.top();
si.pop();
double x1 = si.top();
si.pop();
char symbol = sc.top();
sc.pop();
switch (symbol) {
case '+':si.push(x1 + x2); break;
case '-':si.push(x1 - x2); break;
case '*':si.push(x1 * x2); break;
case '/':si.push(x1 / x2); break;
}
return true;
}
int main() {
scanf("%d", &t);
do {
char c = getc(stdin);
if (c == -1)break;
if (c == '\n') {
while (execute());
if (si.empty())continue;
double v = si.top();
while (!si.empty())si.pop();
while (!sc.empty())sc.pop();
printf("%.2lf\n", v);
continue;
}
if (c <= '9' && c >= '0') {
ungetc(c, stdin);
double v;
scanf("%lf", &v);
if (sc.empty())si.push(v);
else if (sc.top() == '-') {
si.push(-v);
sc.pop();
sc.push('+');
}
else if (sc.top() == '/') {
si.push(1.0 / v);
sc.pop();
sc.push('*');
}
else si.push(v);
}
else if (c == '+' || c == '-' || c == '*' || c == '/') {
while (!sc.empty() && (c == '+' || c == '-') && (sc.top() == '*' || sc.top() == '/')) {
execute();
}
sc.push(c);
}
} while (1);
}

http://bjutacm.openjudge.cn/lianxi/1018/

Openjudge BJUTACM 181A:素数和

发表评论

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

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<vector>
#include<typeinfo>
using namespace std;
int n, m;
bool isprime[10000005];
int prime[10000005];
vector<int> primeList;
inline void genPrime() {
memset(isprime, true, sizeof(isprime));
isprime[0] = isprime[1] = false;
for (int i = 2; i <= 10000000; i++) {
if (!isprime[i])continue;
primeList.push_back(i);
for (int j = 2 * i; j <= 10000000; j += i) {
isprime[j] = false;
}
}
}
inline void putIn(int v) {
for (int i = 0; i < primeList.size() && v >= primeList[i] && v != 1; i++) {
if (v%primeList[i] == 0) {
prime[primeList[i]]++;
while (v%primeList[i] == 0)v /= primeList[i];
}
if (isprime[v]) {
prime[v]++;
break;
}
}
}
int main() {
genPrime();
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int v;
scanf("%d", &v);
putIn(v);
}
for (int i = 1; i <= 10000000; i++) {
prime[i] += prime[i - 1];
}
scanf("%d", &m);
for (int i = 1; i <= m; i++) {
int l, r;
scanf("%d%d", &l, &r);
if (r > 10000000)r = 10000000;
if (l > 10000000)l = 10000000;
printf("%d\n", prime[r] - prime[l - 1]);
}
}

http://bjutacm.openjudge.cn/lianxi/181A/

C++指针

发表评论

仅做保留参考个人使用，谁要是能看懂，那就是C++大神了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include<iostream>
#include<typeinfo>
using namespace std;
char s[2010][2010];
int * func1(int a, int b) { return 0; }
int *(*func)(int, int) = func1;
int main() {
cout << typeid(func1).name() << endl;
cout << typeid(func).name() << endl;
auto ptr = &s;
cout << typeid(&ptr).name() << " " << sizeof(&ptr) << " " << (int)(&ptr + 1) - (int)(&ptr) << endl;
cout << typeid(ptr).name() << " " << sizeof(ptr) << " " << (int)(ptr + 1) - (int)(ptr) << endl;
cout << typeid(&s).name() << " " << sizeof(&s) << " " << (int)(&s + 1) - (int)(&s) << endl;
cout << typeid(s).name() << " " << sizeof(s) << " " << (int)(s + 1) - (int)(s) << endl;
cout << typeid(*s).name() << " " << sizeof(*s) << " " << (int)(*s + 1) - (int)(*s) << endl;
cout << typeid(&s[0]).name() << " " << sizeof(&s[0]) << " " << (int)(&s[0] + 1) - (int)(&s[0]) << endl;
cout << typeid(s[0]).name() << " " << sizeof(s[0]) << " " << (int)(s[0] + 1) - (int)(s[0]) << endl;
cout << typeid(*s[0]).name() << " " << sizeof(*s[0]) << endl;
cout << typeid(&s[0][0]).name() << " " << sizeof(&s[0][0]) << " " << (int)(&s[0][0] + 1) - (int)(&s[0][0]) << endl;
cout << typeid(s[0][0]).name() << " " << sizeof(s[0][0]) << endl;
}

输出结果（找一个好点的编译器，别用g++，输出的Typeinfo没法看）：

1
2
3
4
5
6
7
8
9
10
11
12

int * __cdecl(int,int)
int * (__cdecl*)(int,int)
char (* *)[2010][2010] 4 4
char (*)[2010][2010] 4 4040100
char (*)[2010][2010] 4 4040100
char [2010][2010] 4040100 2010
char [2010] 2010 1
char (*)[2010] 4 2010
char [2010] 2010 1
char 1
char * 4 1
char 1

总结：对某类型做sizeof运算，返回的是本类型本身的大小；对某类型指针做加减操作，数值为n，是对其绝对地址加减：对该指针解除引用后的类型的sizeof运算的数值乘以n。

洛谷 P1972 [SDOI2009]HH的项链

发表评论

参考题解：https://www.luogu.org/blog/skylee/solution-p1972

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

#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
int arr[500005];
int c[500000];
int last[1000001];
int flag=0;
struct question{
int id,l,r,ans;
bool operator < (const question& q2) const{
if(flag==0)return r<q2.r;
else return id<q2.id;
}
}qs[200005];
inline int lowbit(int i){
return i&(-i);
}
int query(int x){
int sum=0;
while(x>0){
sum+=c[x];
x-=lowbit(x);
}
return sum;
}
void update(int i,int v){
while(i<=n){
c[i]+=v;
i+=lowbit(i);
}
}
int main(){
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++){
cin>>arr[i];
}
cin>>m;
for(int i=1;i<=m;i++){
cin>>qs[i].l>>qs[i].r;
qs[i].id=i;
}
sort(qs+1,qs+m+1);
int ptr=1;
for(int i=1;i<=m;i++){
for(;ptr<=qs[i].r;ptr++){
if(last[arr[ptr]]!=0)update(last[arr[ptr]],-1);
update(last[arr[ptr]]=ptr,1);
}
qs[i].ans=query(qs[i].r)-query(qs[i].l-1);
}
flag=1;
sort(qs+1,qs+m+1);
for(int i=1;i<=m;i++){
cout<<qs[i].ans<<endl;
}
}

洛谷 P2023 [AHOI2009]维护序列

发表评论

没啥说的，和上一道题一模一样。。只是把输入改掉就可以了。。

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

#include<iostream>
using namespace std;
struct segmentTree{
typedef long long ll;
const static int MAX=100000;
ll MOD;
ll v[4*MAX],aTg[4*MAX],mTg[4*MAX];
inline static ll lson(ll r){return r*2;}
inline static ll rson(ll r){return r*2+1;}
void build(ll r,ll* a,ll s,ll e){
aTg[r]=0;mTg[r]=1;
if(s==e){v[r]=a[s]%MOD;return;}
ll m=(s+e)>>1;
build(lson(r),a,s,m);
build(rson(r),a,m+1,e);
v[r]=(v[lson(r)]+v[rson(r)])%MOD;
}
void pushDown(ll r,ll s,ll e){
if(aTg[r]==0&&mTg[r]==1)return;
ll m=(s+e)>>1;
v[lson(r)]=(v[lson(r)]*mTg[r]%MOD+aTg[r]*(m-s+1)%MOD)%MOD;
v[rson(r)]=(v[rson(r)]*mTg[r]%MOD+aTg[r]*(e-m)%MOD)%MOD;
aTg[lson(r)]=(aTg[lson(r)]*mTg[r]%MOD+aTg[r]%MOD)%MOD;
aTg[rson(r)]=(aTg[rson(r)]*mTg[r]%MOD+aTg[r]%MOD)%MOD;
mTg[lson(r)]=(mTg[lson(r)]*mTg[r])%MOD;
mTg[rson(r)]=(mTg[rson(r)]*mTg[r])%MOD;
aTg[r]=0;mTg[r]=1;
}
ll query(ll r,ll cs,ll ce,ll qs,ll qe){
if(qe<cs||ce<qs)return 0;
if(qs<=cs&&ce<=qe)return v[r]%MOD;
pushDown(r,cs,ce);
ll cmd=(cs+ce)>>1;
return (query(lson(r),cs,cmd,qs,qe)+query(rson(r),cmd+1,ce,qs,qe))%MOD;
}
void update(ll r,ll cs,ll ce,ll us,ll ue,ll addv=0,ll mulv=1){
if(ue<cs||ce<us)return;
if(us<=cs&&ce<=ue){
v[r]=(v[r]*mulv%MOD+addv*(ce-cs+1))%MOD;
aTg[r]=(aTg[r]*mulv%MOD+addv)%MOD;
mTg[r]=(mTg[r]*mulv)%MOD;
return;
}
pushDown(r,cs,ce);
ll cmd=(cs+ce)>>1;
update(lson(r),cs,cmd,us,ue,addv,mulv);
update(rson(r),cmd+1,ce,us,ue,addv,mulv);
v[r]=(v[lson(r)]+v[rson(r)])%MOD;
}
}ST;
typedef long long ll;
ll n,m,p;
ll a[100005];
int main(){
ios::sync_with_stdio(false);
cin>>n>>p;
for(int i=1;i<=n;i++)cin>>a[i];
cin>>m;
ST.MOD=p;
ST.build(1,a,1,n);
for(int i=1;i<=m;i++){
ll op,x,y,k;
cin>>op;
if(op==1||op==2){
cin>>x>>y>>k;
if(op==1)ST.update(1,1,n,x,y,0,k);
else ST.update(1,1,n,x,y,k);
}else{
cin>>x>>y;
cout<<ST.query(1,1,n,x,y)%p<<endl;
}
}
}

洛谷 P3373 【模板】线段树 2

发表评论

总算写出来了。。。线段树同时维护乘法和加法，欢迎体验！

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

#include<iostream>
using namespace std;
struct segmentTree{
typedef long long ll;
const static int MAX=100000;
ll MOD;
ll v[4*MAX],aTg[4*MAX],mTg[4*MAX];
inline static ll lson(ll r){return r*2;}
inline static ll rson(ll r){return r*2+1;}
void build(ll r,ll* a,ll s,ll e){
aTg[r]=0;mTg[r]=1;
if(s==e){v[r]=a[s]%MOD;return;}
ll m=(s+e)>>1;
build(lson(r),a,s,m);
build(rson(r),a,m+1,e);
v[r]=(v[lson(r)]+v[rson(r)])%MOD;
}
void pushDown(ll r,ll s,ll e){
if(aTg[r]==0&&mTg[r]==1)return;
ll m=(s+e)>>1;
v[lson(r)]=(v[lson(r)]*mTg[r]%MOD+aTg[r]*(m-s+1)%MOD)%MOD;
v[rson(r)]=(v[rson(r)]*mTg[r]%MOD+aTg[r]*(e-m)%MOD)%MOD;
aTg[lson(r)]=(aTg[lson(r)]*mTg[r]%MOD+aTg[r]%MOD)%MOD;
aTg[rson(r)]=(aTg[rson(r)]*mTg[r]%MOD+aTg[r]%MOD)%MOD;
mTg[lson(r)]=(mTg[lson(r)]*mTg[r])%MOD;
mTg[rson(r)]=(mTg[rson(r)]*mTg[r])%MOD;
aTg[r]=0;mTg[r]=1;
}
ll query(ll r,ll cs,ll ce,ll qs,ll qe){
if(qe<cs||ce<qs)return 0;
if(qs<=cs&&ce<=qe)return v[r]%MOD;
pushDown(r,cs,ce);
ll cmd=(cs+ce)>>1;
return (query(lson(r),cs,cmd,qs,qe)+query(rson(r),cmd+1,ce,qs,qe))%MOD;
}
void update(ll r,ll cs,ll ce,ll us,ll ue,ll addv=0,ll mulv=1){
if(ue<cs||ce<us)return;
if(us<=cs&&ce<=ue){
v[r]=(v[r]*mulv%MOD+addv*(ce-cs+1))%MOD;
aTg[r]=(aTg[r]*mulv%MOD+addv)%MOD;
mTg[r]=(mTg[r]*mulv)%MOD;
return;
}
pushDown(r,cs,ce);
ll cmd=(cs+ce)>>1;
update(lson(r),cs,cmd,us,ue,addv,mulv);
update(rson(r),cmd+1,ce,us,ue,addv,mulv);
v[r]=(v[lson(r)]+v[rson(r)])%MOD;
}
}ST;
typedef long long ll;
ll n,m,p;
ll a[100005];
int main(){
ios::sync_with_stdio(false);
cin>>n>>m>>p;
for(int i=1;i<=n;i++)cin>>a[i];
ST.MOD=p;
ST.build(1,a,1,n);
for(int i=1;i<=m;i++){
ll op,x,y,k;
cin>>op;
if(op==1||op==2){
cin>>x>>y>>k;
if(op==1)ST.update(1,1,n,x,y,0,k);
else ST.update(1,1,n,x,y,k);
}else{
cin>>x>>y;
cout<<ST.query(1,1,n,x,y)%p<<endl;
}
}
}

杰克部落

一个大学生的博客

作者归档：Jack

洛谷 P2114 [NOI2014]起床困难综合症

Openjudge BJUTACM 2018 周末集训 1005:Largest Rectangle in a Histogram

启用Google reCAPTCHA

Openjudge BJUTACM 1036:括号画家

Openjudge BJUTACM 1018:简单计算器

Openjudge BJUTACM 181A:素数和

C++指针

洛谷 P1972 [SDOI2009]HH的项链

洛谷 P2023 [AHOI2009]维护序列

洛谷 P3373 【模板】线段树 2