【20170920校内模拟赛】小Z爱学习

所有题目开启-O2优化,开大栈空间,评测机效率为4亿左右。


T1 小 Z 学数学(math)

Description

​ 要说小 Z 最不擅长的学科,那一定就是数学了。这不,他最近正在学习加法运算。老师为了考核小 Z,给他出了一个问题。

​ 给定一个操作序列,每个操作形如 t a 。如果 t 是 0,那么意味着加上 a;如果 t 是 1,那么意味着改成 a。那么问题来了,给定一开始有一个数字 0,按照从左到右的顺序执行操作序列中[l,r]段的操作,最后得到的数字是什么?为了确定小 Z 已经掌握了加法运算,老师给了他许多询问。小 Z 这下可 慌了,因为他昨天晚上都在 dota,没有学习,自然也就回答不出问题。他准备向你求助,你能告诉他每个询问的答案吗?

​ 由于数据过大,所以小 Z 告诉了你数据的生成方式,并且你只要告诉他所有答案按照指定方式加密后的结果就行了。

Input

​ 从 math.in 中读取数据。

​ 一行三个数字 n,m,seed 表示操作数量和询问数量,以及用于生成接下来所需要的数据的变量。

​ 生成数据的模板在下发文件 math.cpp 中给出。

Output

​ 假设 m 个询问按照输入的顺序分别是 a1,a2,…,am,你需要输出一个整数,它等于\(\Sigma_{i=1}^{m} 233^{i} * ai\)对 998244353 取膜的结果。

Sample Input

5 5 23333

Sample Output

50333483

Hint

对于 30%的数据, \(n,m \leq 5000\)

对于 100%的数据,$ n,m \leq 10^7 , 0 \leq seed \leq 10^9 $

样例解释

获得的数据分别是

0 880345150

1 787931255

0 2943464295

1 876592220

0 2063957658

3 3

1 4

2 5

2 4

3 5

询问的答案是 2943464295,876592220,2940549878, 876592220, 2940549878

输出 50333483

下发文件(math.cpp)

#include<iostream>
#include<cstdio>
using namespace std;
unsigned int seed,a[10000005];
int n,m,l[10000005],r[10000005],ans=0;
bool type[10000005]; unsigned int GetNext()
{
seed^=(seed<<7);
seed^=(seed>>8);
seed^=(seed<<13);
return seed;
} int main()
{
scanf("%d%d%u",&n,&m,&seed);
for(int i=1;i<=n;++i) type[i]=GetNext()%2,a[i]=GetNext(); //获得n个操作的t和a
for(int i=1;i<=m;++i) //获得m个询问的左右端点
{
l[i]=GetNext()%n+1,r[i]=GetNext()%n+1;
int tmp;
if(l[i]>r[i]) tmp=l[i],l[i]=r[i],r[i]=tmp;
long long res = 0;
// blablabla...
}
cout<<ans;
return 0;
}

Solution

显然修改操作之后的加法只对修改操作尝试影响,故利用好前缀和,记录一下之前一次修改操作的位置,即可O(1)回答询问。时间效率O(n+m).

Code

#include <stdio.h>
#define ui unsigned int
#define mod 998244353LL
#define MN 10000005
#define R register
#define Filename "math"
bool opt[MN];ui val[MN],belongs[MN],sum=0,n,m,x,cnt,p=233;
inline ui read(){
R ui x; R bool f; R char c;
for (f=0; (c=getchar())<'0'||c>'9'; f=c=='-');
for (x=c-'0'; (c=getchar())>='0'&&c<='9'; x=(x<<3)+(x<<1)+c-'0');
return f?-x:x;
}
inline ui Getnext(){return x^=x<<7,x^=x>>8,x^=x<<13;}
int main(){
#ifndef Debug
freopen(Filename".in","r",stdin);
freopen(Filename".out","w",stdout);
#endif
n=read(),m=read(),x=read();
for (R int i=1; i<=n; ++i)
opt[i]=(Getnext()%2),belongs[i]=(opt[i]?++cnt:cnt),val[i]=(opt[i]?Getnext():((ui)((1ll*Getnext()+1ll*val[i-1])%mod)))%mod;
for (R int i=1; i<=m; ++i,p=(ui)(233ll*p%mod)){
R ui l=Getnext()%n+1,r=Getnext()%n+1;if (l>r) l^=r,r^=l,l^=r;
if (belongs[r]!=belongs[l]) sum=(ui)((1ll*sum+1ll*p*val[r]%mod)%mod);
else sum=(ui)((1ll*sum+1ll*p*((1ll*val[r]-1ll*(opt[l]?0:val[l-1])+mod)%mod)%mod)%mod);
}printf("%u",sum);
#ifndef Debug
fclose(stdin); fclose(stdout);
#endif
return 0;
}

T2 小 Z 学英语(english )

Description

​ 好不容易混过了数学课,英语课又快开始了。小 Z 十分紧张,毕竟他还没有背好要考的单词,所以他想争取在英语课之前背完单词。小 Z 要背的单词有 n个,并且他们有着相同的长度。为了节约时间,小 Z 准备将一些循环同构的单词一起背。

我们称两个单词循环同构,当且仅当满足至少一个下面的条件。

​ 1) 两个单词相同

​ 2) 把其中一个单词的最后一位接到最前面(例如”abc”变成”cab”),得到的单词和另一个单词循环同构。

例如”abc”和”abc”,”cab”,”bca”循环同构。

小 Z 现在想知道这些单词中有多少对<i,j>(i<j),满足第 i 个单词和第 j 个单词循环同构?

Input

​ 从 english.in 中读取数据。

​ 第一行两个数 n,m, 表示有 n 个单词,每个单词的长度是 m 。

​ 接下来 n 行,每行读入一个长度为 m 的单词,单词只包含小写字母

Output

​ 输出一个数字表示答案。

Sample Input

4 4

abcd

acbd

bcda

dabc

Sample Output

3

Hint

本题采用子任务制,只有你通过一个 subtask 内所有的数据点才能得到这个数据点对应的分数。

Subtask1 包含 30Points, 满足$ 1 \leq n,m \leq 300\(
Subtask2 包含 30Points,满足\) m \leq 5$

Subtask3 包含 40Points 没有特殊限制条件

对于所有数据,满足 $1 \leq n,m \leq 10^6 , n*m \leq 10^6 $

样例解释

abcd、 bcda、 dabc 循环同构,答案是 3

Solution

对字符串求最小表示法然后扔trie树解决即可。时间复杂度\(O(nm)\),空间复杂度\(O(26nm)\)

Code

#include <stdio.h>
#define MN 1000005
#define R register
#define ll long long
#define Filename "english"
inline int read(){
R int x; R bool f; R char c;
for (f=0; (c=getchar())<'0'||c>'9'; f=c=='-');
for (x=c-'0'; (c=getchar())>='0'&&c<='9'; x=(x<<3)+(x<<1)+c-'0');
return f?-x:x;
}
char st[MN<<1];int n,m,cnt;ll ans;int trie[MN][26],val[MN];
inline int getans(){
R int i=0,j=1;
while(i<m&&j<m){
R int k=0;
while (st[i+k]==st[j+k]&&k+2<m) ++k;
if (st[i+k]>st[j+k]) i=i+k+1;
else j=j+k+1;if(i==j) ++j;
}return i<j?i:j;
}
int main(){
#ifndef Debug
freopen(Filename".in","r",stdin);
freopen(Filename".out","w",stdout);
#endif
n=read(),m=read();
for (R int i=1; i<=n; ++i){
scanf("%s",st);for (R int j=0; j<m; ++j) st[j+m]=st[j];
R int stpos=getans();R int x=0;
for (R int i=0; i<m; ++i){
if (!trie[x][st[stpos+i]-'a']) trie[x][st[stpos+i]-'a']=++cnt;
x=trie[x][st[stpos+i]-'a'];
}ans+=val[x]++;
}printf("%lld\n",ans);
#ifndef Debug
fclose(stdin); fclose(stdout);
#endif
return 0;
}

T3 小 Z 学化学 (chemistry )

Description

​ 小 Z 最喜欢的学科是化学,甚至参加了化学学科比赛,获得了优异的成绩。

但他更有兴趣探索宇宙的奥秘,这天他遇到了一个难题。

​ 小 Z 利用 α-666 射线观察了一种结构未知的 β-233 分子,并且发现这个分子的结构形成了一棵以 1 为根三叉树。因为物质的平衡问题,树上的每一个节点只可能有 0 或者 3 个儿子。这棵树上的每个叶节点都会有一些核能,因此所有节点都会因此获得一些能量值,而这个分子的能量值就等于根节点的能量值。

​ 经过不断的探寻,小 Z 终于发现了能量值的奥秘。原来每个叶节点的能量值就等于它的核能,而每个非叶节点的能量值等于他的三个儿子的能量值的中位数。小 Z 现在已经知道了所有叶子节点的核能值,也知道了这个分子能量值是多少,但他可以运用一些新技术,交换其中部分节点的核能。

​ 小 Z 想知道在任意交换的情况下,这个分子的能量值最大能是多少。 这对他的研究有着重要意义。

Input

​ 从 chemistry.in 中读取数据。

​ 第一行两个数字 n,m,表示有 n 个节点,有 m 个叶子节点的核能可以任意交换。

​ 接下来 n 行,第 i 行描述第 i 个节点的信息。

​ 如果这个节点是一个叶子结点,那么这一行包括两个整数,第一个数是-1,第二个数 ai 表示这个节点的能量值。否则的话,这一行包括三个不同的整数,表示这个节点的三个子节点。

​ 最后一行 m 个数,表示可以任意交换的叶子节点的编号。

Output

输出一个数字,表示所有情况下分子的能量值的最大值。

Sample Input

7 5

2 4 5

3 6 7

-1 1

-1 3

-1 4

-1 2

-1 5

3 4 5 6 7

Sample Output

4

Hint

本题采用子任务制,只有你通过一个 subtask 内所有的数据点才能得到这个数据

点对应的分数。

Subtask1 包含 20Points 满足$ n,m \leq 8\(
Subtask2 包含 10Points 满足\) m \leq 1 \(
Subtask3 包含 20Points 满足\) n\leq 100000, m \leq 5\(
Subtask4 包含 20Points 满足\) n,m \leq 5000\(
Subtask5 包含 30Points 满足\) n,m \leq 10^6\(
对于所有数据,满足\) m \leq n \leq 10^6 , n \geq 1 , 0 \leq ai \leq 10^9$

由于读入数据较大,建议使用较快速的读入方式。

样例解释

不交换情况下能量值是 3。假如交换节点 4 和节点 7 的核能,那么能量值就变成了 4,可以证明这是最大的能量值。

Solution

显然答案一定是叶节点中的某一个数,考虑枚举答案,判断合法性。

​ 确定要判断的数字之后,就只剩下了两种数字,分别大等于或者小于要判断的数字。这里认为大等于的数字是合法的。

​ 我们用 f[i]表示 i 的能量值大等于要判断的数字最少需要填入几个合法的数字,那么对于确定的叶子结点,如果他合法, f[i]=0,否则 f[i]=INF。对于不确定的, f[i]=1。

​ 然后就有了转移, f[i]就等同于它的三个儿子中比较小的两个 f 的和。最后我们只需要判断是否有足够的数字填入即可 。

​ 如果只是这样做的话,时间复杂度可以看做是\(O(n^2)\)的,可以得到70分。

​ 仔细观察一下,发现作为一个判定性问题,显然对于一个答案如果它合法,那么比它小的答案必然是合法的,故可以二分答案解决,将问题转化为判定性问题。时间复杂度\(O(n \log_{2} n)\)

Code

#include <stdio.h>
#include <algorithm>
#define MN 1000005
#define R register
#define Filename "chemistry"
using namespace std;
inline int read(){
R int x; R bool f; R char c;
for (f=0; (c=getchar())<'0'||c>'9'; f=c=='-');
for (x=c-'0'; (c=getchar())>='0'&&c<='9'; x=(x<<3)+(x<<1)+c-'0');
return f?-x:x;
}
int val[MN],n,m,s[MN][3],L[MN],mid;bool mark[MN];
inline int dp(int u){
if (s[u][0]== -1) return mark[u]?1:(val[u]>=mid?0:n+1);
R int f1=dp(s[u][0]),f2=dp(s[u][1]),f3=dp(s[u][2]);
return min(n+1,f1+f2+f3-max(f1,max(f2,f3)));
}
int main(){ #ifndef Debug
freopen(Filename".in","r",stdin);
freopen(Filename".out","w",stdout);
#endif
n=read(),m=read();
for (R int i=1; i<=n; ++i){
if ((s[i][0]=read())==-1) val[i]=read();
else s[i][2]=read(),s[i][1]=read();
}for (R int i=1; i<=m; ++i) mark[read()]=1;
for (R int i=1,cnt=0; i<=n; ++i) if (mark[i]) L[++cnt]=val[i];
sort(L+1,L+m+1);R int l=1,r=1e9;
for (;l<r;){
mid=l+r+1>>1;if (dp(1)<=m-(lower_bound(L+1,L+m+1,mid)-L)+1) l=mid;
else r=mid-1;
}printf("%d",l);
#ifndef Debug
fclose(stdin); fclose(stdout);
#endif
return 0;
}
上一篇:[noip模拟赛]虫洞holes


下一篇:校内模拟赛 Zbq's Music Challenge