left_right_2022

题解

/ 注册

全部文章 / 题解（共45篇）

J-Different Integers 莫队算法板子题

题意：有一个数组 a[] 长度为n. q组询问，每组询问[L,R]表示询问a1……aL,aR……an中有多少个不同的数字。n,q=1e5. 令an+i=ai，将原数组a[]的长度扩大为2n 原询问等价于[R,n+L],即询问aR……an,an+1,……,an+L中有多少个不...

莫队

2021-10-06

0 748

Codeforces 597C.Subsequences

题目描述：给定由1-n组成的长度为n的a[]和k，问长度为k+1的子序列中有多少个单调递增的？n<=1e5,k<=10 终于想到了！开k+1个线段树/树状数组记f[i][j][o]为前i个数，以j结尾，长度为o的子序列有多少个。i维可以省略，f[j][o]=f[Σ1-(j-1)][o-1...

树状数组线段树动态规划

2021-06-06

0 615

Codeforces 597B.Restaurant

题目描述：一家餐厅收到了n份订单，每份订单有开始和结束时间，餐厅可以选择接或不接，接受的订单时间必须互不重合，即任意一刻都不能被两个订单占用。问餐厅最多能接受几份订单。啊这，乍看是经典DP，但是不能直接写，需要多思考。以订单结束顺序排序。f[i]表示处理订单数为i时，所用的最小时间，发现f[i]有...

二分离散化动态规划

2021-06-06

0 520

Codeforces 597A.Divisibility

题意描述：给定区间[a,b]，问有多少个整数可以被k整除。一个小思路是分别计算a到0、b到0有多少个整数被k整除，然后再分类讨论求解。尤其注意0和端点的判断。 #include<bits/stdc++.h> using namespace std; int main() { l...

数学

2021-06-06

0 645

Codeforces 1527C.Sequence Pair Weight

题意：给定长度n的数组a[]，问所有的连续子数组中有多少对相同的数。这不就是整个a[]有多少对相同的数的变种题吗是不是叫一维数点来着？~~ 一对相同的数ai,aj，它们一共在i*(n-j+1)个子数组内出现过。根据这个直接算贡献。用mp[a[i]]维护a[i]在1-(i-1)的出现过的坐标和。这样每...

前缀和

2021-05-29

0 667

Codeforces 1527B1.Palindrome Game (easy version)

题意：ALICE先手，每次能对一个字符串做两种操作:选择任意i(1≤i≤n)，其中s[i]= '0'，将s[i]改为'1'。支付1美元。把整个字符串反过来，付0元。此操作只允许在字符串当前不是回文且上次操作没有反转的情况下进行。也就是说，如果Alice翻转了串，那么Bob在下一个动作中就不能翻转，反...

贪心博弈论

2021-05-29

0 562

Codeforces 1527A.And Then There Were K

题目描述：给定n,求最大的k使得 n & (n−1) & (n−2) & (n−3) & ... (k) = 0 大胆猜测当且仅当n的最高位被0与掉了的时候这个式子会等于0，所以k满足2^m-1<n<=2^(m+1)-1，找到这个k=2^m-1输出即可...

数学二进制枚举

2021-05-29

0 952

Codeforces 1520E.Arranging The Sheep

题目描述：有一块长度为n的一维地，每格地可能为空('.')也可能有一只羊('*')每次可以令一只羊左移或右移一格，当且仅当目的地是空。问最少几步能让这些羊相邻。我的做法：记所有羊的坐标为ai,维护两个值f(x)=Σ|x-ai|，sum1[x]为x及之前的羊数，sum2[x]为x及之后的羊数，定义g...

曼哈顿距离贪心数学前缀和

2021-05-29

0 625

Codeforces 1520D.Same Differences

题意描述：给定长度n的数组a[],问有多少对(i,j)满足1<=i<j<=n使得aj-ai=j-i. 对式子整理得到aj-j=ai-i. 这……根本不带掩饰的？这太经典了给b[]=a[i]-i，问有多少对相同的数？这都见过吧？用map维护1到i-1中，b[i]出现了mp[b[...

数学前缀和

2021-05-29

0 939

Codeforces 1520C.Not Adjacent Matrix

题意描述：给定n，用1-n^2构造一个n×n矩阵，要求上下左右相邻的数的差值大于1，无解输出-1，有解就给出任意一组解。图省事特判n=1,n=2() n>=3时，按照对角线方向依次填数，先填对角线再轮流在上下侧填数，得到的矩阵符合要求，输出即可。大胆猜测小心使用不用证明编辑：网上有一种想...

贪心数学

2021-05-29

0 875