前四题都比较水

A

求连续LIS,嗯扫一遍就好了

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
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn = 1e5 + 10;
int a[maxn];

int main()
{
//freopen("test.txt","r",stdin);
int n;
while(scanf("%d",&n)==1)
{
for(int i=0;i<n;++i) scanf("%d",a+i);
int cnt = 1,res = 1;
for(int i=1;i<n;++i)
{
if(a[i]>=a[i-1]) ++cnt;
else cnt = 1;
res = max(cnt,res);
}
printf("%d\n",res);
}
return 0;
}

B

排序后扫一遍,维护一个队列,保证差值小于d

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
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

const int maxn = 1e5 + 10;
struct Node
{
int a,b;
Node(int a=0,int b=0):a(a),b(b) {}
bool operator<(const Node& rhs) const
{
return a<rhs.a;
}
} a[maxn];

int main()
{
//freopen("test.txt","r",stdin);
int n,d;
while(scanf("%d",&n)==1)
{
scanf("%d",&d);
for(int i=0;i<n;++i)
{
int x,y;
scanf("%d %d",&x,&y);
a[i] = Node(x,y);
}
sort(a,a+n);
LL res = a[0].b , cur = res;
queue<int> Q;
Q.push(0);
for(int i=1;i<n;++i)
{
while(!Q.empty() && a[i].a - a[Q.front()].a >= d)
{
cur -= a[Q.front()].b;
Q.pop();
}
Q.push(i);
cur += a[i].b;
res = max(res,cur);
}
printf("%I64d\n",res);
}
return 0;
}

C

dfs,维护d1[u]包含当前节点的最大连续cat,d2[u]最大连续cat数,到叶子节点更新下即可
后来发现其实只用维护一个d2[u],当d2[u]大于m时不再向下遍历

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
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn = 1e5 + 10;
vector<int> G[maxn];
int d1[maxn],d2[maxn],cat[maxn],ans;
int n,m;

void dfs(int fa,int u)
{
if(cat[u]) d1[u] = d1[fa] + 1;

d2[u] = max(d1[u],d2[fa]);

if(G[u].size() == 1 && u!=1)
{
if(d2[u] <= m) ++ans;
}

for(int i=0;i<G[u].size();++i)
{
int v = G[u][i];
if(v!=fa)
{
dfs(u,v);
}
}
}

int main()
{
//freopen("test.txt","r",stdin);
while(scanf("%d %d",&n,&m)==2)
{
for(int i=1;i<=n;++i) scanf("%d",cat+i);
for(int i=1;i<n;++i)
{
int u,v;
scanf("%d %d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
memset(d1,0,sizeof d1);
memset(d2,0,sizeof d2);
ans = 0;
dfs(0,1);
printf("%d\n",ans);
}
return 0;
}

D

状压dp d[i][S] 表示以i结尾,遍历过的点集为S,的最优结果

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
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn = 18;
LL d[maxn+2][1<<maxn];
LL a[maxn+2],G[maxn+2][maxn+2];

inline int next(int x)
{
int l = x & -x, y = x + l;
return y | (((x^y) / l) >> 2);
}

void check(LL &x,LL y)
{
if(x<y) x = y;
}

int main()
{
//freopen("test.txt","r",stdin);
int n,m,k;
while(scanf("%d%d%d",&n,&m,&k)==3)
{
for(int i=0;i<n;++i) scanf("%lld",a+i);
memset(G,0,sizeof G);
for(int i=0;i<k;++i)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
G[x-1][y-1] = c;
}
memset(d,0,sizeof d);
for(int i=0;i<n;++i)
{
d[i][1<<i] = a[i];
}
for(int i=0;i<(1<<n);++i)
{
for(int j=0;j<n;++j)
{
if(i&(1<<j)) continue;
for(int t = 0;t<n;++t)
{
if(i&(1<<t))
{
check(d[j][i|(1<<j)],d[t][i]+G[t][j]+a[j]);
}
}
}
}
LL ans = 0;
for(int i=(1<<m)-1 ; i<(1<<n) ;i = next(i))
{
for(int j=0;j<n;++j)
{
if(i & (1<<j))
{
check(ans,d[j][i]);
}
}
}
printf("%lld\n",ans);
}
return 0;
}

E

hash+线段树
比较的时候即比较 s[i,|s|-k] 和 s[i+k,|s|] 的hash
自然溢出会被卡,这里用双hash容错
奇怪的是用 memcpy 和 memcmp 可以水过

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 100100
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
using namespace std;
typedef long long ull;

const ull base[2] = {11,13};
const ull mod[2] = {1e9+7,1073676287};

int n,m,k;
char s[N];
ull pow[2][N],sum[2][N];
ull hash[2][N<<2];
int col[2][N<<2];

void init()
{
for(int d = 0;d<2;++d)
{
pow[d][0]=sum[d][0]=1;
for(int i=1;i<=n;i++)
{
pow[d][i]=pow[d][i-1]*base[d]%mod[d];
sum[d][i]=(sum[d][i-1]+pow[d][i])%mod[d];
}
}
memset(col,-1,sizeof(col));
}
void pushup(int rt,int l,int r,int d)
{
int mid=(l+r)>>1;
hash[d][rt]=(hash[d][rt<<1]+hash[d][rt<<1|1]*pow[d][mid - l + 1])%mod[d];
}
void pushdown(int rt,int l,int r,int d)
{
if(col[d][rt]!=-1)
{
int mid=(l+r)>>1;
col[d][rt<<1]=col[d][rt];
hash[d][rt<<1]=col[d][rt]*sum[d][mid-l]%mod[d];
col[d][rt<<1|1]=col[d][rt];
hash[d][rt<<1|1]=col[d][rt]*sum[d][r-mid-1]%mod[d];
col[d][rt]=-1;
}
}
void build(int l,int r,int rt)
{
if(l==r)
{
hash[0][rt] = hash[1][rt] =s[l]-'0';
return;
}
int mid=(l+r)>>1;
build(lson);
build(rson);
pushup(rt,l,r,0);
pushup(rt,l,r,1);
}
void update(int v,int L,int R,int l,int r,int rt,int d)
{
if(L<=l&&r<=R)
{
col[d][rt]=v;
hash[d][rt]=v*sum[d][r-l]%mod[d];
return;
}
int mid=(l+r)>>1;
pushdown(rt,l,r,d);
if(L<=mid)update(v,L,R,lson,d);
if(R>mid)update(v,L,R,rson,d);
pushup(rt,l,r,d);
}
ull query(int L,int R,int l,int r,int rt,int d)
{
ull ret=0;
if(L<=l&&r<=R)
{
return hash[d][rt];
}
int mid=(l+r)>>1;
pushdown(rt,l,r,d);
if(L>mid)ret=query(L,R,rson,d);
else if(R<=mid)ret=query(L,R,lson,d);
else ret=(query(L,mid,lson,d)+query(mid+1,R,rson,d)*pow[d][mid-L+1]%mod[d])%mod[d];
return ret;
}
int main()
{
// freopen("test.txt","r",stdin);
scanf("%d%d%d",&n,&m,&k);
scanf("%s",s+1);
init();
build(1,n,1);
for(int i=1;i<=m+k;i++)
{
int opt,l,r,g;
scanf("%d%d%d%d",&opt,&l,&r,&g);
if(opt==1)
{
for(int d=0;d<2;++d)
update(g,l,r,1,n,1,d);
}else
{
bool flag = true;
if(g>r-l+1){puts("NO");continue;}
if(g==r-l+1){puts("YES");continue;}
for(int d=0;d<2;++d)
{
ull tmp1=query(l+g,r,1,n,1,d);
ull tmp2=query(l,r-g,1,n,1,d);
if(tmp1 != tmp2)
{
flag = false;
break;
}
}
puts(flag?"YES":"NO");
}
}
}