淘宝上做的网站 域名到期可以自己续费吗,朗坤智能企业管理系统,韩国美容网站 模板,徐州免费建站模板#x1f680;欢迎来到本文#x1f680; #x1f349;个人简介#xff1a;陈童学哦#xff0c;彩笔ACMer一枚。 #x1f3c0;所属专栏#xff1a;杭电多校集训 本文用于记录回顾总结解题思路便于加深理解。 #x1f4e2;#x1f4e2;#x1f4e2;传送门 A - 循环位移解… 欢迎来到本文 个人简介陈童学哦彩笔ACMer一枚。 所属专栏杭电多校集训 本文用于记录回顾总结解题思路便于加深理解。 传送门 A - 循环位移解题思路AC代码 B - 星星解题思路AC代码 H - 位运算解题思路AC代码 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 ] 中。 定义字符串SS0⋯Sn−1循环位移k次为S(k)Skmodn⋯Sn−1S0⋯S(k−1)modn。 定义[A]{A(k),k∈N}. 给出T组串A,B询问B有多少个子串在[A]中。 定义字符串SS0⋯Sn−1循环位移k次为S(k)Skmodn⋯Sn−1S0⋯S(k−1)modn。定义[A]A(k),k∈N.给出T组串A,B询问B有多少个子串在[A]中。
Input 第一行一个 T 表示输入组数。接下来每行两个字符串表示 A 和 B 保证 ∣ A ∣ ≤ ∣ B ∣ 。保证 ∑ ∣ B ∣ ≤ 1048576. 并且字符串均由大写字母组成。 第一行一个T表示输入组数。 接下来每行两个字符串表示A和B保证∣A∣≤∣B∣。保证∑∣B∣≤1048576.并且字符串均由大写字母组成。 第一行一个T表示输入组数。接下来每行两个字符串表示A和B保证∣A∣≤∣B∣。保证∑∣B∣≤1048576.并且字符串均由大写字母组成。 Output 输出 T 行每行一个数表示答案。 输出T行每行一个数表示答案。 输出T行每行一个数表示答案。 解题思路
题目要我们求字符串B中有多少个子串属于字符串A的循环位移串。 一般对于这种循环位移的东西我们都可以去倍增一下会比较好写。 在这里我们可以将字符串A倍增一倍然后去字符串B中找有多少个长度为字符串A长度的字串然后通过字符串哈希统计答案。 首先我们可以计算一下倍增后的字符串A的每个字符的的哈希值然后再将每个区间长度为原字符串A长度的字串的哈希值标记为1最后再类似的处理字符串B的每个字符的哈希值然后再判断字符串B中长度为原字符串A长度的哈希值是否被标记如果被标记那么答案就。 还需要注意的就是在此之前我们需要预处理一个数组f用于计算哈希值以及区间哈希值如何计算。
AC代码
#includebits/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];}mapi64,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;//统计答案被标记了就是答案加1for(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;//预处理的数组ffor(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种选择他必须做出恰好一种选择 小A有n次获得星星的机会。在第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 。 保证0a_i≤b_i≤c_i≤d_i≤10^9。 保证0ai≤bi≤ci≤di≤109。 他想要获得恰好 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. 1≤n≤1000,0≤k≤n×4. 满足 ∑ n ≤ 100000 满足∑n≤100000 满足∑n≤100000 Output 对于每组数据输出一个数字表示这组数据的答案。 对于每组数据输出一个数字表示这组数据的答案。 对于每组数据输出一个数字表示这组数据的答案。 解题思路
n次获得星星中恰好获得k颗星星的最小代价是不是有点和01背包的n件物品中背包容量恰好为v的最大价值有点类似。 对的那么这题肯定大概率应该就是个变形版的01背包了。 那么就直接考虑dp d p [ N ] dp[N] dp[N]代表的是获得星星为 N N N时所付出的最小代价。
AC代码
#includebits/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⊗00,0⊗10,1⊗00,1⊗11。 按位与⊗二进制下每一位做与即0⊗00,0⊗10,1⊗00,1⊗11。 按位异或 ⊕ 二进制下每一位做异或即 0 ⊕ 0 0 , 0 ⊕ 1 1 , 1 ⊕ 0 1 , 1 ⊕ 1 0 。 按位异或⊕二进制下每一位做异或即0⊕00,0⊕11,1⊕01,1⊕10。 按位异或⊕二进制下每一位做异或即0⊕00,0⊕11,1⊕01,1⊕10。 按位或 ⊖ 二进制下每一位做或即 0 ⊖ 0 0 , 0 ⊖ 1 1 , 1 ⊖ 0 1 , 1 ⊖ 1 1 。 按位或⊖二进制下每一位做或即0⊖00,0⊖11,1⊖01,1⊖11。 按位或⊖二进制下每一位做或即0⊖00,0⊖11,1⊖01,1⊖11。 现在对于一个在 [ 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⊖dn a⊗b⊕c⊖dn 注意运算符是从左往右依次顺序结合的即可以认为原表达式为 注意运算符是从左往右依次顺序结合的即可以认为原表达式为 注意运算符是从左往右依次顺序结合的即可以认为原表达式为 ( ( ( a ⊗ b ) ⊕ c ) ⊖ d ) n (((a⊗b)⊕c)⊖d)n (((a⊗b)⊕c)⊖d)n Input 本题单个测试点内包含多组测试数据。 本题单个测试点内包含多组测试数据。 本题单个测试点内包含多组测试数据。 第一行一个整数 T ( 1 ≤ T ≤ 10 ) 表示数据组数。 第一行一个整数T(1≤T≤10)表示数据组数。 第一行一个整数T(1≤T≤10)表示数据组数。 对于每组数据一行两个整数 n , k ( 1 ≤ k ≤ 15 , 0 ≤ n 2 k ) 。 对于每组数据一行两个整数n,k(1≤k≤15,0≤n2^k)。 对于每组数据一行两个整数n,k(1≤k≤15,0≤n2k)。 Output 对于每组数据输出 q 行每行一个整数表示答案。 对于每组数据输出q行每行一个整数表示答案。 对于每组数据输出q行每行一个整数表示答案。 解题思路
对于这种位运算的题绝大部分情况下直接枚举十进制下的数肯定会TLE的一般都是找二进制下每位的规律。 要使得 ( ( ( a ⊗ b ) ⊕ c ) ⊖ d ) n (((a⊗b)⊕c)⊖d)n (((a⊗b)⊕c)⊖d)n那么 a 、 b 、 c 、 d a、b、c、d a、b、c、d二进制的这位数字要么为1要么为0如果它们当前位通过 ⊗ 、 ⊕ 、 ⊖ ⊗、⊕、⊖ ⊗、⊕、⊖运算后的结果1那么n的二进制下的当前位也应该位1反之则为0。 那么我们便可以通过预处理 a 、 b 、 c 、 d a、b、c、d a、b、c、d四个数取1或0的所有情况然后通过判断n的二进制下每位是1还是0累加答案即可。 或者我们可以通过分类讨论。 一、n的当前位在二进制下位1时 1、当d的当前位为1时 ( ( a ⊗ b ) ⊕ c ) ((a⊗b)⊕c) ((a⊗b)⊕c)中的a、b、c无论如何取值都不会影响结果所有共有 2 3 2^3 23即8。 2、当d的当前位为0时再分类讨论下 ( ( a ⊗ b ) ⊕ c ) ((a⊗b)⊕c) ((a⊗b)⊕c)为1还是0。 ①、当c为1时 ( a ⊗ b ) (a⊗b) (a⊗b)共有3种情况使得 ( ( ( a ⊗ b ) ⊕ c ) ⊖ d ) (((a⊗b)⊕c)⊖d) (((a⊗b)⊕c)⊖d)为1 ②、当c为0时 ( a ⊗ b ) (a⊗b) (a⊗b)共有1种情况使得 ( ( ( a ⊗ b ) ⊕ c ) ⊖ d ) (((a⊗b)⊕c)⊖d) (((a⊗b)⊕c)⊖d)为1 综上所述共有12种情况使得进制位为1。
二、n的当前位在二进制下位0时 1、当d的当前位为1时 ( ( a ⊗ b ) ⊕ c ) ((a⊗b)⊕c) ((a⊗b)⊕c)中的a、b、c无论如何取值无法使得 ( ( a ⊗ b ) ⊕ c ) ((a⊗b)⊕c) ((a⊗b)⊕c)满足条件即0种情况。 2、当d的当前位为0时再分类讨论下 ( ( a ⊗ b ) ⊕ c ) ((a⊗b)⊕c) ((a⊗b)⊕c)为1还是0。 ①、当c为1时 ( a ⊗ b ) (a⊗b) (a⊗b)共有1种情况使得 ( ( ( a ⊗ b ) ⊕ c ) ⊖ d ) (((a⊗b)⊕c)⊖d) (((a⊗b)⊕c)⊖d)为0 ②、当c为0时 ( a ⊗ b ) (a⊗b) (a⊗b)共有3种情况使得 ( ( ( a ⊗ b ) ⊕ c ) ⊖ d ) (((a⊗b)⊕c)⊖d) (((a⊗b)⊕c)⊖d)为0 综上所述共有12种情况使得进制位为4。
最后总结也就能看出来如果n二进制下的当前位为1的话就 ∗ 12 *12 ∗12否则 ∗ 4 *4 ∗4
AC代码
#includebits/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;
}
