自学内容网 自学内容网

2024中国大学生算法设计超级联赛(1)

🚀欢迎来到本文🚀
🍉个人简介:陈童学哦,彩笔ACMer一枚。
🏀所属专栏:杭电多校集训
本文用于记录回顾总结解题思路便于加深理解。

A - 循环位移

ProblemDescription

定义字符串 S = S 0 + ⋯ + S n − 1 循环位移 k 次为 S ( k ) = S k m o d n + ⋯ + S n − 1 + S 0 + ⋯ + S ( k − 1 ) m o d n 。定义 [ A ] = A ( k ) , k ∈ N . 给出 T 组串 A , B ,询问 B 有多少个子串在 [ A ] 中。 定义字符串S=S0+⋯+Sn−1循环位移k次为S(k)=Skmodn+⋯+Sn−1+S0+⋯+S(k−1)modn。 定义[A]={A(k),k∈N}. 给出T组串A,B,询问B有多少个子串在[A]中。 定义字符串S=S0++Sn1循环位移k次为S(k)=Skmodn++Sn1+S0++S(k1)modn。定义[A]=A(k),kN.给出T组串A,B,询问B有多少个子串在[A]中。
在这里插入图片描述

Input

第一行一个 T 表示输入组数。接下来每行两个字符串,表示 A 和 B ,保证 ∣ A ∣ ≤ ∣ B ∣ 。保证 ∑ ∣ B ∣ ≤ 1048576. ,并且字符串均由大写字母组成。 第一行一个T表示输入组数。 接下来每行两个字符串,表示A和B,保证∣A∣≤∣B∣。保证∑∣B∣≤1048576.,并且字符串均由大写字母组成。 第一行一个T表示输入组数。接下来每行两个字符串,表示AB,保证A∣≤∣B。保证B∣≤1048576.,并且字符串均由大写字母组成。

在这里插入图片描述

Output

输出 T 行,每行一个数表示答案。 输出T行,每行一个数表示答案。 输出T行,每行一个数表示答案。

在这里插入图片描述

解题思路

题目要我们求字符串B中有多少个子串属于字符串A的循环位移串。
一般对于这种循环位移的东西,我们都可以去倍增一下会比较好写。
在这里我们可以将字符串A倍增一倍然后去字符串B中找有多少个长度为字符串A长度的字串然后通过字符串哈希统计答案。
首先我们可以计算一下倍增后的字符串A的每个字符的的哈希值,然后再将每个区间长度为原字符串A长度的字串的哈希值标记为1,最后再类似的处理字符串B的每个字符的哈希值,然后再判断字符串B中长度为原字符串A长度的哈希值是否被标记,如果被标记那么答案就++。
还需要注意的就是在此之前我们需要预处理一个数组f用于计算哈希值,以及区间哈希值如何计算。

AC代码

#include<bits/stdc++.h>
#define look(x) cout << #x << " ==  " << x << "\n"
using namespace std;
using i64 = long long;
const int N = 5e5 + 10;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
//h1代表字符串A中字符的哈希值
//h2代表字符串B中字符的哈希值
i64 h1[N],h2[N];
//预处理的数组
i64 f[N];
//字符串A中区间哈希值的计算
i64 get1(int l,int r){
return h1[r] - h1[l - 1] * f[r - l + 1];
}
//字符串B中哈希值的计算
i64 get2(int l,int r){
return h2[r] - h2[l - 1] * f[r - l + 1];
}
void solve(){
string s1,s2;
cin >> s1 >> s2;
int n1 = s1.size();
int n2 = s2.size();
s1 = '?' + s1 + s1;
s2 = '?' + s2;
//计算字符串A的每个字符的哈希值
for(int i = 1;i < s1.size();i ++){
h1[i] = h1[i - 1] * 11 + s1[i];
}
map<i64,int> mp;
//标记A的每个循环位移串
for(int i = 1;i < s1.size();i ++){
if(i + n1 - 1 < s1.size()){
mp[get1(i,i + n1 - 1)] = 1;
}
}
//计算字符串B的每个字符的哈希值
for(int i = 1;i < s2.size();i ++){
h2[i] = h2[i - 1] * 11 + s2[i];
}
i64 ans = 0;
//统计答案,被标记了就是答案,加1
for(int i = 1;i < s2.size();i ++){
if(i + n1 - 1 < s2.size()){
ans += mp[get2(i,i + n1 - 1)];
}
}
cout << ans << "\n";
}

int main(){

ios::sync_with_stdio(false);
cin.tie(nullptr);
f[0] = 1;
//预处理的数组f
for(int i = 1;i <= N;i ++){
f[i] = f[i - 1] * 11;
}

int t = 1;
cin >> t;

while(t --){
solve();
}

return 0;
}

B - 星星

ProblemDescription

小 A 有 n 次获得星星的机会。在第 i 次机会里他有如下的 5 种选择(他必须做出恰好一种选择): 小A有n次获得星星的机会。 在第i次机会里他有如下的5种选择(他必须做出恰好一种选择): An次获得星星的机会。在第i次机会里他有如下的5种选择(他必须做出恰好一种选择):
− 跳过这一轮。 -跳过这一轮。 跳过这一轮。
− a i 的代价获得 1 颗星星。 -ai的代价获得1颗星星。 ai的代价获得1颗星星。
− b i 的代价获得 2 颗星星。 -bi的代价获得2颗星星。 bi的代价获得2颗星星。
− c i 的代价获得 3 颗星星。 -ci的代价获得3颗星星。 ci的代价获得3颗星星。
− d i 的代价获得 4 颗星星。 -di的代价获得4颗星星。 di的代价获得4颗星星。
保证 0 < a i ≤ b i ≤ c i ≤ d i ≤ 1 0 9 。 保证0<a_i≤b_i≤c_i≤d_i≤10^9。 保证0<aibicidi109
他想要获得恰好 k 颗星星,但是并不知道最小代价是多少,请你帮他计算这个最小值。 他想要获得恰好k颗星星,但是并不知道最小代价是多少,请你帮他计算这个最小值。 他想要获得恰好k颗星星,但是并不知道最小代价是多少,请你帮他计算这个最小值。

在这里插入图片描述
Input

本题有多组数据 本题有多组数据 本题有多组数据
第一行输入数据组数 T 。 第一行输入数据组数T。 第一行输入数据组数T
对于每组数据的第一行,有两个正整数表示 n , k 。接下来 n 行,输入四个数字 a i , b i , c i , d i 。 对于每组数据的第一行,有两个正整数表示n,k。接下来n行,输入四个数字a_i,b_i,c_i,d_i。 对于每组数据的第一行,有两个正整数表示n,k。接下来n行,输入四个数字ai,bi,ci,di
1 ≤ n ≤ 1000 , 0 ≤ k ≤ n × 4. 1≤n≤1000,0≤k≤n×4. 1n1000,0kn×4.
满足 ∑ n ≤ 100000 满足∑n≤100000 满足n100000

在这里插入图片描述
Output

对于每组数据,输出一个数字表示这组数据的答案。 对于每组数据,输出一个数字表示这组数据的答案。 对于每组数据,输出一个数字表示这组数据的答案。

在这里插入图片描述

解题思路

n次获得星星中恰好获得k颗星星的最小代价,是不是有点和01背包的n件物品中背包容量恰好为v的最大价值有点类似。
对的,那么这题肯定大概率应该就是个变形版的01背包了。
那么就直接考虑dp, d p [ N ] dp[N] dp[N]代表的是获得星星为 N N N时所付出的最小代价。

AC代码

#include<bits/stdc++.h>
#define look(x) cout << #x << " ==  " << x << "\n"
using namespace std;
using i64 = long long;
const int N = 2e5 + 10;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
//获得1、2、3、4颗星星时所需要付出的代价
int a[1010],b[1010],c[1010],d[1010];
//获得星星数为x时所需付出的最小代价
i64 dp[4040];
void solve(){
//初始化为无穷大
memset(dp,0x3f,sizeof(dp));
//获得0颗星星时不需要付出代价
dp[0] = 0;
int n,k;
cin >> n >> k;
for(int i = 1;i <= n;i ++){
cin >> a[i] >> b[i] >> c[i] >> d[i];
}
//第i次获得星星的机会
for(int i = 1;i <= n;i ++){
//目前获得的星星数
for(int j = k;j >= 0;j --){
//在获得1、2、3、4颗星星时依次转移
for(int t = 1;t <= 4;t ++){
if(j >= t){
if(t == 1){
dp[j] = min(dp[j],dp[j - t] + a[i]);
}else if(t == 2){
dp[j] = min(dp[j],dp[j - t] + b[i]);
}else if(t == 3){
dp[j] = min(dp[j],dp[j - t] + c[i]);
}else if(t == 4){
dp[j] = min(dp[j],dp[j - t] + d[i]);
}
}
}
}
}
//输出恰好获得k颗星星时的最小代价
cout << dp[k] << "\n";
}


int main(){

ios::sync_with_stdio(false);
cin.tie(nullptr);

int t = 1;
cin >> t;

while(t --){
solve();
}

return 0;
}

H - 位运算

ProblemDescription

小丁最近对位运算很感兴趣,通过学习,他知道了按位与 ⊗ ,按位异或 ⊕ ,以及按位或 ⊖ 三种常见位运算。 小丁最近对位运算很感兴趣,通过学习,他知道了按位与⊗,按位异或⊕,以及按位或⊖三种常见位运算。 小丁最近对位运算很感兴趣,通过学习,他知道了按位与,按位异或,以及按位或三种常见位运算。
按位与 ⊗ :二进制下每一位做与,即 0 ⊗ 0 = 0 , 0 ⊗ 1 = 0 , 1 ⊗ 0 = 0 , 1 ⊗ 1 = 1 。 按位与⊗:二进制下每一位做与,即0⊗0=0,0⊗1=0,1⊗0=0,1⊗1=1。 按位与:二进制下每一位做与,即00=0,01=0,10=0,11=1
按位异或 ⊕ :二进制下每一位做异或,即 0 ⊕ 0 = 0 , 0 ⊕ 1 = 1 , 1 ⊕ 0 = 1 , 1 ⊕ 1 = 0 。 按位异或⊕:二进制下每一位做异或,即0⊕0=0,0⊕1=1,1⊕0=1,1⊕1=0。 按位异或:二进制下每一位做异或,即00=0,01=1,10=1,11=0
按位或 ⊖ :二进制下每一位做或,即 0 ⊖ 0 = 0 , 0 ⊖ 1 = 1 , 1 ⊖ 0 = 1 , 1 ⊖ 1 = 1 。 按位或⊖:二进制下每一位做或,即0⊖0=0,0⊖1=1,1⊖0=1,1⊖1=1。 按位或:二进制下每一位做或,即00=0,01=1,10=1,11=1
现在,对于一个在 [ 0 , 2 k ) 中的整数 n ,小丁想要知道,有多少组也在 [ 0 , 2 k ) 中的整数 a , b , c , d ,满足: 现在,对于一个在[0,2^k)中的整数n,小丁想要知道,有多少组也在[0,2^k)中的整数a,b,c,d,满足: 现在,对于一个在[0,2k)中的整数n,小丁想要知道,有多少组也在[0,2k)中的整数a,b,c,d,满足:

a ⊗ b ⊕ c ⊖ d = n a⊗b⊕c⊖d=n abcd=n
注意,运算符是从左往右依次顺序结合的,即可以认为原表达式为: 注意,运算符是从左往右依次顺序结合的,即可以认为原表达式为: 注意,运算符是从左往右依次顺序结合的,即可以认为原表达式为:
( ( ( a ⊗ b ) ⊕ c ) ⊖ d ) = n (((a⊗b)⊕c)⊖d)=n (((ab)c)d)=n

在这里插入图片描述
Input

本题单个测试点内包含多组测试数据。 本题单个测试点内包含多组测试数据。 本题单个测试点内包含多组测试数据。
第一行一个整数 T ( 1 ≤ T ≤ 10 ) ,表示数据组数。 第一行一个整数T(1≤T≤10),表示数据组数。 第一行一个整数T(1T10),表示数据组数。
对于每组数据,一行两个整数 n , k ( 1 ≤ k ≤ 15 , 0 ≤ n < 2 k ) 。 对于每组数据,一行两个整数n,k(1≤k≤15,0≤n<2^k)。 对于每组数据,一行两个整数n,k(1k15,0n<2k)

在这里插入图片描述

Output

对于每组数据输出 q 行,每行一个整数表示答案。 对于每组数据输出q行,每行一个整数表示答案。 对于每组数据输出q行,每行一个整数表示答案。

在这里插入图片描述

解题思路

对于这种位运算的题,绝大部分情况下直接枚举十进制下的数肯定会TLE的,一般都是找二进制下每位的规律。
要使得 ( ( ( a ⊗ b ) ⊕ c ) ⊖ d ) = n (((a⊗b)⊕c)⊖d)=n (((ab)c)d)=n,那么 a 、 b 、 c 、 d a、b、c、d abcd二进制的这位数字要么为1要么为0,如果它们当前位通过 ⊗ 、 ⊕ 、 ⊖ ⊗、⊕、⊖ 运算后的结果1,那么n的二进制下的当前位也应该位1,反之则为0。
那么我们便可以通过预处理 a 、 b 、 c 、 d a、b、c、d abcd四个数取1或0的所有情况,然后通过判断n的二进制下每位是1还是0累加答案即可。
或者我们可以通过分类讨论。
一、n的当前位在二进制下位1时
  1、当d的当前位为1时, ( ( a ⊗ b ) ⊕ c ) ((a⊗b)⊕c) ((ab)c)中的a、b、c无论如何取值都不会影响结果,所有共有 2 3 2^3 23即8。
  2、当d的当前位为0时,再分类讨论下 ( ( a ⊗ b ) ⊕ c ) ((a⊗b)⊕c) ((ab)c)为1还是0。
    ①、当c为1时, ( a ⊗ b ) (a⊗b) (ab)共有3种情况使得 ( ( ( a ⊗ b ) ⊕ c ) ⊖ d ) (((a⊗b)⊕c)⊖d) (((ab)c)d)为1
    ②、当c为0时, ( a ⊗ b ) (a⊗b) (ab)共有1种情况使得 ( ( ( a ⊗ b ) ⊕ c ) ⊖ d ) (((a⊗b)⊕c)⊖d) (((ab)c)d)为1
综上所述共有12种情况使得进制位为1。

二、n的当前位在二进制下位0时
  1、当d的当前位为1时, ( ( a ⊗ b ) ⊕ c ) ((a⊗b)⊕c) ((ab)c)中的a、b、c无论如何取值无法使得 ( ( a ⊗ b ) ⊕ c ) ((a⊗b)⊕c) ((ab)c)满足条件,即0种情况。
  2、当d的当前位为0时,再分类讨论下 ( ( a ⊗ b ) ⊕ c ) ((a⊗b)⊕c) ((ab)c)为1还是0。
    ①、当c为1时, ( a ⊗ b ) (a⊗b) (ab)共有1种情况使得 ( ( ( a ⊗ b ) ⊕ c ) ⊖ d ) (((a⊗b)⊕c)⊖d) (((ab)c)d)为0
    ②、当c为0时, ( a ⊗ b ) (a⊗b) (ab)共有3种情况使得 ( ( ( a ⊗ b ) ⊕ c ) ⊖ d ) (((a⊗b)⊕c)⊖d) (((ab)c)d)为0
综上所述共有12种情况使得进制位为4。

最后总结也就能看出来如果n二进制下的当前位为1的话就 ∗ 12 *12 12,否则 ∗ 4 *4 4

AC代码

#include<bits/stdc++.h>
#define look(x) cout << #x << " ==  " << x << "\n"
using namespace std;
using i64 = long long;
const int N = 2e5 + 10;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
void solve(){
int n,k;
cin >> n >> k;
i64 ans = 1;
for(int i = 0;i < k;i ++){
if((n >> i) & 1){
ans *= 12;
}else{
ans *= 4;
}
}
cout << ans << "\n";
}


int main(){

ios::sync_with_stdio(false);
cin.tie(nullptr);

int t = 1;
cin >> t;

while(t --){
solve();
}

return 0;
}

原文地址:https://blog.csdn.net/H1727548/article/details/140602689

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!