S+3-数据结构1
A. 约瑟夫问题
- 还是很简单的，用链表直接维护就好了
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
32signed main() {
IOS;
int n, m;
cin >> n >> m;
vector<int> P(n + 1), RE(n + 1);
P[0] = 1;
for (int i = 1; i <= n; i++)
{
P[i] = i + 1;
RE[i] = i - 1;
if (i == 1)
{
RE[i] = n;
}
if (i == n)
{
P[i] = 1;
}
}
int idx = 0;
for (int i = 1; i <= n; i++)
{
int op = m;
while (op--) {
idx = P[idx];
}
cout << idx << ' ';
P[RE[idx]] = P[idx];
RE[P[idx]] = RE[idx];
}
return 0;
}
B. 第K大和
用链表可以轻松维护区间
1 | struct node { |
C. 子矩阵
- 经典题，在单调栈修改的时候解决，对单调栈的理解很深刻
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
79signed main()
{
IOS;
int n, m;
cin >> n >> m;
vector<vector<char> > s(n + 1, vector<char>(m + 1));
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++) {
cin >> s[i][j];
}
}
vector<vector<int>> DP(n + 2, vector<int>(m + 2, 0)), IDX(n + 2, vector<int>(m + 2, 0));
int ans = 0;
for (int i = 1; i <= n; i++)
{
//cout << s[i] << endl;
for (int j = 1; j <= m; j++)
{
if (s[i][j] == 'R')
continue;
DP[i][j] = DP[i - 1][j] + 1;
}
}
for (int i = 1; i <= n; i++)
{
deque<int> q;
DP[i][0] = 0;
q.push_back(0);
for (int j = 1; j <= m; j++)
{
while (!q.empty() && DP[i][j] <= DP[i][q.back()])
{
//cout << j << ' ' << q.back() << ' ' << DP[i][j] << ' ' << IDX[i][j] << endl;
ans = max(ans, (j - IDX[i][q.back()] - 1) * DP[i][q.back()]);
q.pop_back();
//cout << ans << ' ';
}
if (q.empty()) {
q.push_back(0);
}
IDX[i][j] = q.back();
int len = j - q.back();
q.push_back(j);
//cout << len << endl;
ans = max(ans, DP[i][j] * len);
}
//cout << endl;
}
for (int i = 1; i <= n; i++)
{
deque<int> q;
DP[i][m + 1] = 0;
q.push_back(m + 1);
for (int j = m; j >= 1; j--)
{
while (!q.empty() && DP[i][j] <= DP[i][q.back()])
{
//cout << j << ' ' << q.back() << ' ' << DP[i][j] << ' ' << DP[i][q.back()] << endl;
q.pop_back();
}
if (q.empty()) {
q.push_back(0);
}
int len = q.back() - j;
q.push_back(j);
//cout << len << endl;
ans = max(ans, DP[i][j] * len);
}
//cout << endl;
}
cout << 3 * ans << endl;
return 0;
}
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
32const int N=1e5+10;
int n,k,a[N<<1],sum[N<<1],l[N];
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]),a[i+n]=a[i];
for(int i=1;i<=2*n;++i)
sum[i]=sum[i-1]+a[i];
deque<int>qu;
qu.push_back(0);
int ans=0;
for(int i=1;i<=2*n;++i){
while(!qu.empty()&&(i-qu.front()>k))qu.pop_front();
ans=max(ans,sum[i]-sum[qu.front()]);
l[i]=qu.front();
while(!qu.empty()&&sum[qu.back()]>sum[i]) qu.pop_back();
qu.push_back(i);
}
printf("%d ",ans);
for(int i=1;i<=2*n;++i){
if(sum[i]-sum[l[i]]==ans){
printf("%d %d\n",l[i]+1==n?n:(l[i]+1)%n,i==n?n:i%n);
break;
}
}
return 0;
}
E. 完美子区间
- 很经典的二分查找
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
62signed main() {
IOS;
int n, A, B;
cin >> n >> A >> B;
vector<int> v(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> v[i];
}
int l = 0, r = n;
auto check = [&](int x) -> bool
{
deque<int> q1, q2;
for (int i = 1; i <= n; i++)
{
while (!q1.empty() && q1.front() + x <= i)
{
q1.pop_front();
}
while (!q2.empty() && q2.front() + x <= i)
{
q2.pop_front();
}
while (!q1.empty() && v[q1.back()] < v[i])
{
q1.pop_back();
}
while (!q2.empty() && v[q2.back()] > v[i])
{
q2.pop_back();
}
q1.push_back(i);
q2.push_back(i);
if (i >= x)
{
int len = v[q1.front()] - v[q2.front()];
if (A <= len && len <= B)
{
return true;
}
}
}
return false;
};
while (l + 1 < r) {
int mid = (l + r) / 2;
if (check(mid)) {
l = mid;
} else {
r = mid;
}
}
if (check(r)) {
cout << r << endl;
} else {
cout << l << endl;
}
return 0;
}
F. 最大数maxnumber
- 很有意思的可以用ST表做的题
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
35int query(int l,int r)
{
int len=lg[r-l+1];
return max(f[r][len],f[l+pw[len]-1][len]);
}
signed main()
{
// std::ios_base::sync_with_stdio(false);
// cin>>n>>mod;
n=read();mod=read();
for(int i=2;i<=n;++i)
lg[i]=lg[i/2]+1;
pw[0]=1;
for(int i=1;i<=lg[n];++i)
pw[i]=pw[i-1]*2;
for(int i=1;i<=n;++i)
{
char opt=0;int x;
// cin>>opt>>x;
while(opt!='Q'&&opt!='A')opt=getchar();x=read();
if(opt=='Q')
{
t=query(cnt-x+1,cnt);
print(t);puts("");
}
else
{
x+=t;x%=mod;
f[++cnt][0]=x;
for(int j=1;j<=lg[cnt];++j)
f[cnt][j]=max(f[cnt][j-1],f[cnt-pw[j-1]][j-1]);
}
}
return 0;
}
G. 跳石头
- 一个很经典的用倍增解决问题的方法，在倍增的时候解决问题，要不会超时
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
const int N = 1e6 + 5;
int n, k, m, a[N], dp[N][2], ans[N];
signed main() {
scanf("%lld%lld%lld", &n, &k, &m);
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
ans[i] = i;
}
int l = 1;
for (int i = 1; i <= n; i++) {
while (l + k < n && a[l + k + 1] - a[i] < a[i] - a[l]) {
l++;
}
dp[i][0] = (a[l + k] - a[i] <= a[i] - a[l] ? l : l + k);
}
for (int j = 0; j <= 60; j++) {
if (m & (1ll << j)) {
for (int i = 1; i <= n; i++) {
ans[i] = dp[ans[i]][j & 1];
}
}
for (int i = 1; i <= n; i++) {
dp[i][(j + 1) & 1] = dp[dp[i][j & 1]][j & 1];
}
}
for (int i = 1; i <= n; i++) {
printf("%lld ", ans[i]);
}
}
H. 约瑟夫问题升级
- 关键是做二分之前到提前预处理吧
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
int a[100010];
int n, m;
int lowbit(int x) {
return x & (-x);
}
void update(int pos, int num) {
while(pos <= n) {
a[pos] += num;
pos += lowbit(pos);
}
}
int sum(int pos) {
int cnt = 0;
while(pos) {
cnt += a[pos];
pos -= lowbit(pos);
}
return cnt;
}
signed main() {
scanf("%lld%lld", &n, &m);
for(int i = 1; i <= n; i++) {
update(i, 1);
}
int last = 0;
for(int i = 1; i <= n; i++) {
int mm = m;
int c = sum(n) - sum(last);
int tot = sum(n) - sum(0);
while(mm > tot) {
mm -= tot;
}
if(c < mm) {
mm -= c;
last = 0;
}
//printf("%lld %lld %lld\n", last, c, mm);
int l = last + 1, r = n;
int ans;
while(l <= r) {
int mid = (l + r) / 2;
int cc = sum(mid) - sum(last);
if(cc >= mm) {
r = mid - 1;
ans = mid;
}
else {
l = mid + 1;
}
//printf("%lld %lld\n", mid, cc);
}
last = ans;
update(ans, -1);
printf("%lld ", ans);
//printf("\n");
}
}
I. 区间开根
- 这个题的重点是开根最多60次左右，单点维护不会超时
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
constexpr int maxn=100005;
//势能线段树.每个点最大被操作的次数是log级的.
int n,tree[maxn<<2],m,avi[maxn<<2],ns[maxn];//tree[i]表示下标为i的节点的权值和,avi[i]表示这个节点是否全为1.
void build(int l,int r,int p){
if(l==r){tree[p]=ns[l]; return;}
int mid=(l+r)>>1;
build(l,mid,p*2);
build(mid+1,r,p*2+1);
tree[p]=tree[p*2]+tree[p*2+1];
if(tree[p]<=r-l+1)avi[p]=1;
}
int query(int l,int r,int p,int nl,int nr){
if(l>=nl and r<=nr)return tree[p];
int mid=(l+r)>>1,ans=0;
if(nl<=mid)ans+=query(l,mid,p*2,nl,min(nr,mid));
if(nr>mid)ans+=query(mid+1,r,p*2+1,max(nl,mid+1),nr);
return ans;
}
void update(int l,int r,int p,int nl,int nr){
if(avi[p])return;
if(l==r){
tree[p]=(int)floor(sqrt(tree[p]));
if(tree[p]<=1)avi[p]=1;
return;
}
int mid=(l+r)>>1;
if(nl<=mid and !avi[p*2])update(l,mid,p*2,nl,min(nr,mid));
if(nr>mid and !avi[p*2+1])update(mid+1,r,p*2+1,max(nl,mid+1),nr);
tree[p]=tree[p*2]+tree[p*2+1];
avi[p]=avi[p*2] and avi[p*2+1];
}
int t,l,r;
signed main(){
cin >> n;
for(int i=1;i<=n;i++)cin >> ns[i];
cin >> m;
build(1,n,1);
for(int i=1;i<=m;i++){
cin >> t >> s >> r;
if(t==1){
cout<<query(1,n,1,l,r)<<endl;
}
else if(t==2) update(1,n,1,l,r);
}
}
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Ysmmm的快乐小屋！
