校园网站建设教程,网站模板中心,现在做网站怎么赚钱,宁波网站建设设计价格文章目录T1#xff1a;1-02E. JM的西伯利亚特快专递题目题解codeT2#xff1a;寿司晚宴题目题解codeT3#xff1a;荷马史诗题目题解codeT1#xff1a;1-02E. JM的西伯利亚特快专递
题目
今天JM收到了一份来自西伯利亚的特快专递#xff0c;里面装了一个字符串 s #x…
文章目录T11-02E. JM的西伯利亚特快专递题目题解codeT2寿司晚宴题目题解codeT3荷马史诗题目题解codeT11-02E. JM的西伯利亚特快专递
题目
今天JM收到了一份来自西伯利亚的特快专递里面装了一个字符串 s 仅包含小写英文字母。于是JM决定跟qz和寒域爷一起玩一个游戏
JM手里拿着字符串 sqz手里拿着字符串 t 寒域爷手里拿着字符串 u 初始时t和u均为空。有两种操作 将字符串 s 的首部字符取出插入字符串 t 的尾部。 将字符串 t 的尾部字符取出插入字符串 u 的尾部。
JMqz和寒域爷随意地进行上述两种操作直到字符串s和t均为空时才停止。现在JM想知道他们能得到的字典序最小的字符串 u 是什么。
注意对于一个字符串s其长度为n其中字符的下标为12…n则我们定义s的首部字符为s1s_1s1尾部字符为 sns_nsn
输入格式 一行一个字符串s。 输出格式 一行一个字符串u表示答案。
样例 样例输入 cbaa 样例输出 aabc 数据范围与提示 1≤∣s∣≤1051≤|s|\le10^51≤∣s∣≤105
题解
字典序最小的话也就是说对于一个字符串越小的字母就要尽可能越早离开sss 仔细读题会发现其实就是下图的过程 也就是说ttt只是起一个中转站的作用且性质与栈一样所以我们想到了↓ 用一个双关队列或者栈来储存当遍历到iii位时还剩余在sss里面的字母 接着我们来考虑对于一个字母xxx它将面临哪些选择 1.当xq.back()xq.back()xq.back()意思就是当前字母比已遍历的且没有丢进uuu的最后一个字母小 根据规则我们肯定想xxx先出来所以就可以直接放在队列的最后面 2.当xq.back()xq.back()xq.back()如果这个时候仍然选择放在队列后面 那么不管后面如何操作xxx一定比q.back()q.back()q.back()先出来字典序会变小 所以就要先把前面xxx的字母丢出去 如果你认为这样就能ACACAC那你真的是想多了仔细想想刚才的情况二我们太过于粗鲁 zzcadbde——abdcdezz 错误答案acbddezz 为什么会出现这种情况很简单因为在判断c,dc,dc,d时我们忽略了ddd后面还有个字典序更小的bbb 因此为了解决这种情况就定义一个后缀数组pre[i]pre[i]pre[i]表示i−ni-ni−n中字典序最小的字母是什么 那么我们只需要用ccc和ddd的preprepre进行比较即可也就相当于用ccc去和bbb比较就可以预知到后面的走向
code
#include cstring
#include cstdio
#include deque
using namespace std;
#define MAXN 100005
deque char q;
char s[MAXN], pre[MAXN];
int len;int main() {scanf ( %s, s );len strlen ( s );pre[len] z 1;for ( int i len - 1;i 0;i -- )pre[i] min ( s[i], pre[i 1] );for ( int i 0;i len;i ) {if ( q.empty() )q.push_back ( s[i] );else if ( ! q.empty() q.back() s[i] )q.push_back ( s[i] );else {while ( ! q.empty() ) {if ( q.back() s[i] q.back() pre[i] ) {printf ( %c, q.back() );q.pop_back();}elsebreak;}q.push_back ( s[i] );}}while ( ! q.empty() ) {printf ( %c, q.back() );q.pop_back();}return 0;
}T2寿司晚宴
题目
为了庆祝NOI的成功开幕主办方为大家准备了一场寿司晚宴。小G和小W作为参加NOI的选手也被邀请参加了寿司晚宴。
在晚宴上主办方为大家提供了n−1种不同的寿司编号1,2,3,⋯,n-1其中第种寿司的美味度为i1即寿司的美味度为从2到n。
现在小G和小W希望每人选一些寿司种类来品尝他们规定一种品尝方案为不和谐的当且仅当小G品尝的寿司种类中存在一种美味度为x的寿司小W品尝的寿司中存在一种美味度为y的寿司而x与y不互质
现在小G和小W希望统计一共有多少种和谐的品尝寿司的方案对给定的正整数p取模。注意一个人可以不吃任何寿司
输入格式 从文件dinner.in中读入数据。 输入文件的第1行包含2个正整数np中间用单个空格隔开表示共有n种寿司最终和谐的方案数要对p取模。
输出格式 输出到文件dinner.out中。 输出一行包含1个整数表示所求的方案模p的结果。
输入输出样例 输入 3 10000 输出 9
输入 4 10000 输出 21
输入 100 100000000 输出 3107203 说明/提示 【数据范围】 【时限1s内存512M】
题解
猜测一般这种方案数还带模99%99\%99%都是dpdpdp 两者选的寿司互质充要条件就是两人选的寿司的质因子是不重复的就可以用状压判断质因子证实了dpdpdp猜测 首先我们打个质数表发现500500500以内的质数个数为959595 但是我们再用计算机一算21∗23483,23∗2966721*23483,23*2966721∗23483,23∗29667也就是说500500500以内的数最多只会有一个质因数222222所以就可以单独提出来考虑没有就为0 那么剩下的小质因子数就只有888个2,3,5,7,11,13,17,192,3,5,7,11,13,17,192,3,5,7,11,13,17,19 设dp[i][j][k]dp[i][j][k]dp[i][j][k]表示在选第iii个寿司时甲选的质因子集合是jjj乙选的质因子集合是kkk则有 dp[i][j∣food[i].s][k]dp[i−1][j][k](kfood[i].s0)dp[i][j|food[i].s][k]dp[i-1][j][k](k\food[i].s0)dp[i][j∣food[i].s][k]dp[i−1][j][k](kfood[i].s0) dp[i][j][k∣food[i].s]dp[i−1][j][k](jfood[i].s0)dp[i][j][k|food[i].s]dp[i-1][j][k](j\food[i].s0)dp[i][j][k∣food[i].s]dp[i−1][j][k](jfood[i].s0) 前提都是另外一个所选的质因子中没有当前食物的质因子接着发现iii只与i−1i-1i−1有关所以用滚动将之滚成二维简单吧跳过
接着我们要处理一下大质因子这个玩意儿设fg[j][k],fw[j][k]fg[j][k],fw[j][k]fg[j][k],fw[j][k] 对于每一段大质因子相同的数我们在这一段开始的时候把dpdpdp的值赋给fgfgfg和fwfwfw然后在这一段内部用上面的递推方法继续搞 fg[j∣s][k]dp[j][k](ks0)fg[j|s][k]dp[j][k](k\s0)fg[j∣s][k]dp[j][k](ks0) fw[j][k∣s]dp[j][k](js0)fw[j][k|s]dp[j][k](j\s0)fw[j][k∣s]dp[j][k](js0) sss表示小质因子的集合 最后在重新丢给dpdpdp即可 dp[j][k]fg[j][k]fw[j][k]−dp[j][k]dp[j][k]fg[j][k]fw[j][k]-dp[j][k]dp[j][k]fg[j][k]fw[j][k]−dp[j][k] 因为有可能这个食物两个人都不选那么dpdpdp就分别被fg,fwfg,fwfg,fw统计了最后就是多统计了一次减掉就行了
具体的代码部分解释在codecodecode中
code
#include cstdio
#include cstring
#include algorithm
using namespace std;
#define LL long long
#define MAXN 505
int p[10] { 0, 2, 3, 5, 7, 11, 13, 17, 19, 0 };
struct node {int val, big, s;void init () {int tmp val;big s 0;for ( int i 1;i 8;i ) {if ( tmp % p[i] 0 ) {s | ( 1 ( i - 1 ) );while ( tmp % p[i] 0 )tmp / p[i];}}if ( tmp ! 1 )big tmp;}
}food[MAXN];
int n;
LL result, mod;
LL dp[MAXN][MAXN], fg[MAXN][MAXN], fw[MAXN][MAXN];bool cmp ( node x, node y ) {return x.big y.big;
}int main() {scanf ( %d %lld, n, mod );for ( int i 2;i n;i ) {food[i].val i;food[i].init();}sort ( food 2, food n 1, cmp );dp[0][0] 1;//初始化两人什么都不选也算一种情况 for ( int i 2;i n;i ) {if ( i 2 || food[i].big ^ food[i - 1].big || ! food[i].big ) {memcpy ( fg, dp, sizeof ( dp ) );memcpy ( fw, dp, sizeof ( dp ) );}for ( int j 255;j 0;j -- )//j枚举的是小G选择的质因子 for ( int k 255;k 0;k -- ) {//k枚举的是小W选择的质因子 if ( j k )//有重复肯定是不合法的 continue;if ( ( food[i].s k ) 0 )//该质因子没有被小W选择可以被小G选择 fg[j | food[i].s][k] ( fg[j | food[i].s][k] fg[j][k] ) % mod;if ( ( food[i].s j ) 0 )//该质因子没有被小G选择可以被小W选择fw[j][k | food[i].s] ( fw[j][k | food[i].s] fw[j][k] ) % mod;}if ( i n || food[i].big ^ food[i 1].big || ! food[i].big ) {for ( int j 0;j 255;j )for ( int k 0;k 255;k )dp[j][k] ( fg[j][k] fw[j][k] - dp[j][k] mod ) % mod;}}for ( int i 0;i 255;i )for ( int j 0;j 255;j )result ( result dp[i][j] ) % mod;printf ( %lld, result );return 0;
}T3荷马史诗
题目
追逐影子的人自己就是影子 ——荷马 Allison 最近迷上了文学。她喜欢在一个慵懒的午后细细地品上一杯卡布奇诺静静地阅读她爱不释手的《荷马史诗》。但是由《奥德赛》和《伊利亚特》 组成的鸿篇巨制《荷马史诗》实在是太长了Allison 想通过一种编码方式使得它变得短一些。
一部《荷马史诗》中有n种不同的单词从1到n进行编号。其中第i种单 词出现的总次数为wi。Allison 想要用k进制串si来替换第i种单词使得其满足如下要求
对于任意的 1 ≤ i, j ≤ n i ≠ j 都有si不是sj的前缀。
现在 Allison 想要知道如何选择si才能使替换以后得到的新的《荷马史诗》长度最小。在确保总长度最小的情况下Allison 还想知道最长的si的最短长度是多少
一个字符串被称为k进制字符串当且仅当它的每个字符是 0 到 k − 1 之间包括 0 和 k − 1 的整数。
字符串 str1 被称为字符串 str2 的前缀当且仅当存在 1 ≤ t ≤ m 使得str1 str2[1…t]。其中m是字符串str2的长度str2[1…t] 表示str2的前t个字符组成的字符串。
输入格式 输入的第 1 行包含 2 个正整数 n, k 中间用单个空格隔开表示共有 n种单词需要使用k进制字符串进行替换。 接下来n行第 i 1 行包含 1 个非负整数wi 表示第 i 种单词的出现次数
输出格式 输出包括 2 行 第 1 行输出 1 个整数为《荷马史诗》经过重新编码以后的最短长度。 第 2 行输出 1 个整数为保证最短总长度的情况下最长字符串 si 的最短长度。
输入输出样例 输入 4 2 1 1 2 2 输出 12 2
输入 6 3 1 1 3 3 9 9 输出 36 3 说明/提示 【样例说明 1】 用 X(k) 表示 X 是以 k 进制表示的字符串。 一种最优方案令 00(2) 替换第 1 种单词 01(2) 替换第 2 种单词 10(2) 替换第 3 种单词11(2) 替换第 4 种单词。在这种方案下编码以后的最短长度为 1 × 2 1 × 2 2 × 2 2 × 2 12 最长字符串si的长度为 2 。 一种非最优方案令 000(2) 替换第 1 种单词001(2) 替换第 2 种单词01(2)替换第 3 种单词1(2) 替换第 4 种单词。在这种方案下编码以后的最短长度为 1 × 3 1 × 3 2 × 2 2 × 1 12 最长字符串 si 的长度为 3 。与最优方案相比文章的长度相同但是最长字符串的长度更长一些
【样例说明 2】 一种最优方案令 000(3) 替换第 1 种单词001(3) 替换第 2 种单词01(3) 替换第 3 种单词 02(3) 替换第 4 种单词 1(3) 替换第 5 种单词 2(3) 替换第 6 种单词。 【提示】 选手请注意使用 64 位整数进行输入输出、存储和计算。 【时限1s内存512M】
题解
知识储备知识储备知识储备 哈夫曼树 给定NNN个权值作为NNN个叶子结点构造一棵二叉树若该树的带权路径长度达到最小称这样的二叉树为最优二叉树也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树权值较大的结点离根较近
哈夫曼树又称最优二叉树是一种带权路径长度最短的二叉树。所谓树的带权路径长度就是树中所有的叶结点的权值乘上其到根结点的路径长度若根结点为0层叶结点到根结点的路径长度为叶结点的层数。树的路径长度是从树根到每一结点的路径长度之和
应用有哈夫曼编码
多叉哈夫曼树 哈夫曼树也可以是kkk叉的只是在构造kkk叉哈夫曼树时需要先进行一些调整。构造哈夫曼树的思想是每次选kkk个权重最小的元素来合成一个新的元素该元素权重为kkk个元素权重之和。但是当k2k2k2时按照这个步骤做下去可能到最后剩下的元素少于kkk个。 解决这个问题的办法是假设已经有了一棵哈夫曼树(且为一棵满k叉树)则可以计算出其叶节点数目为(k−1)nk1(k-1)nk1(k−1)nk1,式子中的nknknk表示子节点数目为kkk的节点数目。于是对给定的nnn个权值构造k叉哈夫曼树时,可以先考虑增加一些权值为000的叶子节点使得叶子节点总数为(k−1)nk1(k-1)nk1(k−1)nk1这种形式,然后再按照哈夫曼树的方法进行构造即可 ——以上均来自百度百科 读完这道题你就会发现和上面的知识储备对应起来所以这道题对于一个了解哈夫曼树的人就是一道裸题对于别人就是。。。 类比于NOIP2004 合并果子 ——摘自luogu某dalao 看了这句话后可能许多人都有重见天日的感觉我也这么认为这句话真的揭示了这道题的本质
code
#include queue
#include cstdio
using namespace std;
#define int long long
#define MAXN 1000005
struct node {int w, h;node () {}node ( int W, int H ) {w W;h H;}
};
bool operator ( node a, node b ) {if ( a.w ! b.w )return a.w b.w;return a.h b.h;
}
priority_queue node q;
int n, k, cnt, result;
int w[MAXN];signed main() {scanf ( %lld %lld, n, k );for ( int i 1;i n;i ) {scanf ( %lld, w[i] );q.push( node ( w[i], 0 ) );}if ( ( n - 1 ) % ( k - 1 ) )//要判断是否需要加空节点不然cnt会算错 cnt ( k - 1 ) - ( n - 1 ) % ( k - 1 );//( n - 1 ) % ( k - 1 )是最后一次合并不足k的个数减掉才是要加的空节点 for ( int i 1;i cnt;i )q.push( node ( 0, 0 ) );cnt n;while ( cnt 1 ) {int sum 0, maxh 0;for ( int i 1;i k;i ) {sum q.top().w;maxh max ( maxh, q.top().h );q.pop();}result sum;q.push( node ( sum, maxh 1 ) );cnt - ( k - 1 );}printf ( %lld\n%lld\n, result, q.top().h );return 0;
}就完了有问题欢迎评论点个赞呗~
