负担集训-Test15（多校联合训练-6）
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
--------------------------------------------------------
惨啊，12题看错题活生生少了一道签到题...
话说最近负担是越来越重了啊，今天居然要补到8题...（国内的大学怎么都那么强啊Orz）
--------------------------------------------------------
1011:
题意是说有多组数据，每组数据是有A、B、C三个集合，分别给出三个集合的并集中，属于A、B、C、A∩B、A∩C、A∩B、A∩B∩C的元素个数，并且有一些数据是错的，需要忽略这些数据，问合法的数据中最大的|A∪B∪C|是多少
把只属于A、B、C、A∩B、A∩C、A∩B、A∩B∩C的元素个数分别求出来，如果有小于0的，那么就不合法，否则就合法。
--------------------------------------------------------
1001:
题意是说给出一些字符串和一些询问，每次询问给出一个前缀，一个后缀，求同时有这个前缀和这个后缀，并且这两个前后缀不相交的字符串个数。
字符串个数、询问个数<=10^5，字符串总长度、前后缀总长度<=5*10^6
首先假设没有前后缀不能相交这个条件，那么只需要先把字符串排个序，找到和前缀匹配的区间，然后用可持久化字典树求出这个区间内有多少个和后缀匹配的字符串就行了，然后考虑怎么去掉前后缀相交的情况，只需要枚举相交的位数，就可以得到不合法的字符串长什么样，然后询问一下有没有这样的字符串就行了。
--------------------------------------------------------
1012:
题意是有一个宽度确定的屏幕，给你一些单词和一个已经固定了左边缘和宽度的图片，每次询问给出这个图片的上边缘和高度，问把单词按顺序输入这个屏幕，要求两个单词之间如果没有图片或者换行的话必须有一个空格，然后图片和换行不能把一个单词切开，这样最少要多少行把这些都放下。
预处理4个数组，d[i][j]表示从单词i开始，在没有图片的情况下，往后添加单词直到填满2^j行为止，需要用到第几个单词，e[i][j]示从单词j开始，在没有图片的情况下，往后添加单词直到填满2^j行为止，需要用到第几个单词，f[i]表示填满i行，要多少单词，g[i]表示从第一个单词填到单词i，假设不换行，宽度数是多少。
然后每次询问只需要首先把图片前面的单词数用f询问出来，这样就知道了有图片的行第一个单词是谁，然后用e数组求出图片部分用了多少单词，再用d数组求出图片后面有多少行，这样就得到答案了。
--------------------------------------------------------
评论 (0)
