深圳网站建设流程图,货代网站制作,自己做网站的软件下载,泉州seo排名A. Satisfying Constraints(模拟)
题意#xff1a;
给出 n n n个限制条件#xff0c;问有多少个数字 k k k同时满足这些限制条件。
限制条件分为以下三种#xff1a; k k k必须大于等于给出的一些数字 x x x k k k必须小于等于给出的一些数字 x x x k k k不能与给出的…A. Satisfying Constraints(模拟)
题意
给出 n n n个限制条件问有多少个数字 k k k同时满足这些限制条件。
限制条件分为以下三种 k k k必须大于等于给出的一些数字 x x x k k k必须小于等于给出的一些数字 x x x k k k不能与给出的数字 x x x相同
分析
对于限制条件1, 2可以使用两个变量维护数字 k k k的取值区间。
对于限制条件3可以采用容器(set, map等)存储这些不能取到的数字。
根据限制条件12得到的区间再遍历容器检查区间内有多少数字不能被取到剩下的数字个数就是答案。
代码
#includebits/stdc.husing namespace std;
typedef long long ll;setint s;void solve() {int n;cin n;int l -1e9, r 1e9;s.clear();for (int i 0; i n; i) {int a, x;cin a x;if (a 1) {l max(l, x);} else if (a 2) {r min(r, x);} else {s.insert(x);}}int ans r - l 1;for (auto i : s) {if (i l i r) ans--;}cout max(0, ans) endl;
}int main() {int Case;cin Case;while (Case--) {solve();}return 0;
}B. Summation Game(枚举)
题意
有一个包含 n n n个数字的序列 A a 1 , a 2 , . . . , a n A a_1, a_2, ..., a_n Aa1,a2,...,anAlice和Bob将会执行以下操作 首先Alice将会移除序列中至多 k k k个数字。 然后Bob将会选择剩余的序列中至多 x x x个数字并让这些数字乘上 − 1 -1 −1。
Alice想让剩下的数字之和尽可能大但Bob想让剩下的数字之和尽可能小假设两人均采取最优策略那么剩下的数字之和会是多少
分析
实际上Bob会做的事情是固定的即选择剩余的数组中最大的 x x x个数字进行操作。
既然Bob的操作固定了那就可以思考Alice的操作了由于Alice想要结果尽可能大那么Alice的操作就是删除部分最大的数字由于不知道删除多少个是最优的因此需要对删除的数字个数进行枚举记录最大的结果。
对删除后剩余的数字总和进行计算可以先对数组进行排序并维护前缀和使用前缀和来计算结果。
hint: 删除元素后剩余的数字不足 x x x个时计算区间和时需避免出现下标越界。
代码
#includebits/stdc.husing namespace std;
typedef long long ll;
const int N 2e5 5e2;
int a[N], pre[N];void solve() {int n, k, x;cin n k x;for (int i 1; i n; i) {cin a[i];}sort(a 1, a n 1);for (int i 1; i n; i) {pre[i] pre[i - 1] a[i];}int ans -1e9;for (int i 0; i k; i) {int m n - i;int sum;/*小心下标越界*/if (m x) sum pre[m - x] - (pre[m] - pre[m - x]);else sum -pre[m];ans max(ans, sum);}cout ans endl;
}int main() {int Case;cin Case;while (Case--) {solve();}return 0;
}C. Partitioning the Array(数学)
题意
给出一个包含 n n n个数字的数组 A a 1 , a 2 , . . . , a n A a_1, a_2, ..., a_n Aa1,a2,...,an你可以选择一个数字 k k k并对数字进行以下操作 将数组均分为 n k \frac{n}{k} kn个子数组子数组形如 [ a 1 , a 2 , . . . , a k ] , [ a k 1 , a k 2 , . . . , a 2 k ] , . . . , [ a n − k 1 , a n − k 2 , . . . , a n ] [a_1, a_2, ..., a_k], [a_{k 1}, a_{k 2}, ..., a_{2k}], ..., [a_{n - k 1}, a_{n - k 2}, ..., a_n] [a1,a2,...,ak],[ak1,ak2,...,a2k],...,[an−k1,an−k2,...,an] 如果可以选择一个数字 m m m让数组中所有元素对 m m m取余数且计算后得到的各个子数组均是相同的那么就可以获得一点积分。
问最多可以获得多少积分一个数字 k k k最多产生一点积分。
分析
首先思考 k k k的选择不难发现只有 k k k为 n n n的因子时各个子数组的长度才是相等的因此只需要考虑 n n n的所有因子作为 k k k的选择。
当只有两个数字 x , y x, y x,y时那么只要这两个数之间差的绝对值取模 m m m的结果为0那么这两个数字对于 m m m取模的结果必然是相同的。
将结论推广至全部数组中的内容为了尽可能使得到的 m m m更大令 m m m即为所有子数组中对位元素的差的绝对值之间的最大公约数。
为了便于计算每次计算只考虑相邻子数组中的元素进行对位计算即计算 m g c d ( ∣ a 1 − a 1 k ∣ , ∣ a 2 − a 2 k ∣ , . . . , ∣ a n − k 1 − a n ∣ ) m gcd(|a_1 - a_{1 k}|, |a_2 - a_{2 k}|, ..., |a_{n - k 1} - a_n|) mgcd(∣a1−a1k∣,∣a2−a2k∣,...,∣an−k1−an∣)
由于题目要求的 m ≥ 2 m \ge 2 m≥2那么只要得到的结果不为1那么就表示当前存在合法的 m m m能获得积分。
Tips: 当数组中对位元素之差均为0时即各子数组中相同位置的元素均相等此时得到的最大公约数为 0 0 0但此时任选一个 m m m均为合法的解因此也可以获得积分。
代码
#includebits/stdc.husing namespace std;
typedef long long ll;
const int N 2e5 5e2;
int a[N];void solve() {int n;cin n;for (int i 1; i n; i) {cin a[i];}int ans 0;for (int k 1; k n; k) {if (n % k 0) {int m 0;for (int j 1; j k n; j) {m __gcd(m, abs(a[j k] - a[j]));}if (m ! 1) ans;//m2 || m 0}}cout ans endl;
}int main() {int Case;cin Case;while (Case--) {solve();}return 0;
}D.Array Repetition(模拟)
题意
开始时有一个空的数组 a a a将对这个数组进行 n n n次操作每次操作为以下两种操作之一 选择一个数字 x x x将这个数字添加到数组 a a a的末尾。 将数组 a a a的内容复制 x x x遍放在数组 a a a的后面。
结束操作后会给出 q q q个询问每个询问需要你回答数组中第 k k k个元素是多少。
分析
虽然操作 2 2 2会使数组中数字总数增加的非常快但是由于题目的询问最多只会到 1 0 18 10^{18} 1018因此当数组中总数超过 1 0 18 10^{18} 1018时就不需要再进行操作了。
可以使用结构体记录下每次操作后数组中的数字总数 s u m sum sum以及操作 1 1 1添加进来的数字个数 c n t cnt cnt。如果是操作 2 2 2还需要记录下操作 2 2 2的复制次数 m u l mul mul。
对于操作 1 1 1还需将添加的数字记录到另一个数组 a a a中。
然后对于每次查询均可通过递归的方式从记录的操作信息回推到某一条操作 1 1 1对应的数字 如果当前查询的第 k k k个元素与当前结构体记录的总数字个数 s u m sum sum相等那么此时的答案就是数组 a a a中第 c n t cnt cnt个数字。 如果不相等说明需将本轮的复制操作消除继续递归查找将复制消除后需将 k k k也修改为 k m o d s u m m u l k \text{ } mod \text{ } \frac{sum}{mul} k mod mulsum而且需要注意如果余数为 0 0 0需要将 k k k修改为 s u m m u l \frac{sum}{mul} mulsum计算得到 k k k后继续递归查询。
对于每次递归查询遇到操作 1 1 1就会返回结果遇到操作 2 2 2就会移除复制操作后递归查询查询时间复杂度为对数级别。
坑点
虽然我们手动设置数字上限为 1 0 18 10^{18} 1018但如果使用long long类型存储依然不能保证运算中不会发生溢出因此需要使用__int128来进行存储。
代码
#includebits/stdc.husing namespace std;
typedef long long ll;
const int N 2e5 5e2;
struct Node{__int128 sum;//数字总数int cnt, mul;//操作1的次数mul为如果当前操作为操作2那么记录复制的次数bool operator (const Node o) const {if (sum ! o.sum) return sum o.sum;return cnt o.cnt;}
};int n, q;vectorint a;//数字表
vectorNode num;//信息表int search(ll k) {查询第k个数字//在信息表里查int id lower_bound(num.begin(), num.end(), Node{k, 0}) - num.begin();//当前查询的k与信息表的数字总数相等那么此时就是对应信息表中记录的最后一次操作1插入的数字if (num[id].sum k) {return a[num[id].cnt - 1];}k % num[id].sum / num[id].mul;//否则计算在当前的操作2前第k个数字对应的数字是第几个if (k 0) k num[id].sum / num[id].mul;return search(k);//递归查询
}void solve() {a.clear();num.clear();cin n q;__int128 sum 0;int cnt 0;for (int i 0; i n; i) {ll b, x;cin b x;int mul 0;if (sum 1e18) {//只有数字总数小于等于10的18次方才记录操作信息if (b 1) {cnt;sum;a.push_back(x);} else {mul x 1;sum * mul;//如果是long long类型这里就可以发生溢出}num.push_back(Node{sum, cnt, mul});}}while (q--) {ll k;cin k;cout search(k) ;}cout endl;
}int main() {int Case;cin Case;while (Case--) {solve();}return 0;
}E. Counting Binary Strings排列组合、dp
题意
对于一个只含有 0 0 0和 1 1 1的字符串 s s s如果它的子串 s ^ \hat{s} s^只含有 1 1 1个 1 1 1我们就称他为好子串。
现在我们希望知道有多少个字符串 s s s满足以下要求 s s s有且仅有 n n n个好子串 s s s的好子串的长度均不超过 k k k。
答案可能很大需要对 998244353 998244353 998244353取模。另外在考虑子串时我们需要考虑位置。比如说1010中我们认为有 2 2 2个子串 10 10 10因为他们的位置是不同的。
思路
对于由若干个 1 1 1和 0 0 0组成的字符串 s s s我们可以认为每一个 1 1 1都可以和它之前、之后的 0 0 0进行组合形成好字符串。比如0010对于这个 1 1 1它可以分别向前、向后与若干个 0 0 0进行组合当然也可以不向前选择、或者不想后选择。在这个例子中若我们不考虑 k k k的限制含有中间的 1 1 1的子串有 3 × 2 6 3\times26 3×26个。类似的00100010中含有 3 × 4 4 × 2 20 3\times44\times220 3×44×220个好子串。在这个过程中我们重点关注的是1左右两边 0 0 0的个数此处在计算过程中我们进行了 1 1 1操作。
对于一个给定的字符串 s s s我们可以把这些 0 0 0的个数 1 1 1以后的结果记作数组 a 1 , a 2 , … , a n a_1, a_2, \dots, a_n a1,a2,…,an的内容则 s s s中好子串的个数为 a 1 a 2 a 2 a 3 ⋯ a n − 1 a n a_1a_2a_2a_3\dotsa_{n-1}a_n a1a2a2a3⋯an−1an。此时若我们多加入一个 a n 1 a_{n1} an1就是在原来结果的基础上加上 a n a n 1 a_na_{n1} anan1。换言之假设我们用 d p [ s u m ] dp[sum] dp[sum]数组中的元素来表示好子串个数为 s u m sum sum的子串数即 s u m ∑ i 1 n 1 a n sum\sum_{i1}^{n1}a_n sum∑i1n1an那么我们可以发现 d p [ s u m ] dp[sum] dp[sum]与 d p [ s u m − a n ⋅ a n − 1 ] dp[sum-a_n\cdot a_{n-1}] dp[sum−an⋅an−1]有关。
但是并不是只有 a n a_n an结尾的方案才能得到和为 s u m sum sum的结果我们需要给 d p dp dp数组加上一个维度作为限制。此处我们以 d p [ s u m ] [ l a s t ] dp[sum][last] dp[sum][last]表示和为 s u m sum sum最后一个元素即我们前面讨论的 a n 1 a_{n1} an1为 l a s t last last的方案数那么我们有 d p [ s u m ] [ l a s t ] ∑ i d p [ s u m − i ⋅ l a s t ] [ i ] \begin{aligned} dp[sum][last]\sum_{i}dp[sum-i\cdot last][i] \end{aligned} dp[sum][last]i∑dp[sum−i⋅last][i]
其中 i i i的枚举范围要考虑到 i ⋅ l a s t ≤ s u m i\cdot last\le sum i⋅last≤sum避免出现负数下标 i l a s t − 1 ≤ k ilast-1\le k ilast−1≤k这一举动是为了保证加入以后长度不超过 k k k 如果你不理解为什么要 − 1 -1 −1请你回想我们在上面的计算过程中进行了 1 1 1操作当你要对 a a a数组加入元素 l a s t last last时实际上你是多加了好几个 0 0 0 i i i与 l a s t last last的数值如果代表长度会包含同一个 1 1 1计算长度时我们要避免重复计算这个 1 1 1的长度所以根据容斥原理进行 − 1 -1 −1操作。
初始化 d p dp dp数组时可以令满足 1 ≤ l a s t ≤ k 1\le last\le k 1≤last≤k的 d p [ 0 ] [ l a s t ] dp[0][last] dp[0][last]均为 1 1 1即对应全 0 0 0字符串。
hint: 清空 d p dp dp数组需要使用循环来清空避免超时。
代码
#includebits/stdc.husing namespace std;
int n, k, dp[3000][3000];
const int mod 998244353;void solve() {cin n k;for (int i 1; i n; i) for (int j 1; j k; j) dp[i][j] 0;int ans 0;//对全0字符串进行初始化操作for (int last 1; last k; last) {dp[0][last] 1;}//根据dp方程进行计算注意i的范围不要忘记取模for (int sum 1; sum n; sum) {for (int last 1; last k; last) {for (int i 1; i * last sum i last - 1 k; i) {dp[sum][last] (dp[sum][last] dp[sum - i * last][i]) % mod;}}}//统计满足要求的好子串个数不要忘记取模for (int last 1; last k; last) {ans (ans dp[n][last]) % mod;}cout ans endl;
}int main() {int Case;cin Case;while (Case--) {solve();}return 0;
}学习交流
以下为学习交流QQ群群号 546235402每周题解完成后都会转发到群中大家可以加群一起交流做题思路分享做题技巧欢迎大家的加入。
