11.9 noip模拟试题

时间:2021-08-23 20:25:21

NOIP2016 模拟赛
——那些年,我们学过的文化课
背单词
(word.c/cpp/pas)
【题目描述】
fqk 退役后开始补习文化课啦, 于是他打开了英语必修一开始背单
词。 看着满篇的单词非常头疼, 而每次按照相同的顺序背效果并不好,
于是 fqk 想了一种背单词的好方法!他把单词抄写到一个 n 行 m 列的
表格里,然后每天背一行或者背一列。他的复习计划一共有 k 天,在
k 天后, fqk 想知道,这个表格中的每个单词,最后一次背是在哪一
天呢?
【输入格式】
第一行三个整数 k m n , , 。
接下来 k 行,每行的格式可能如下:
1. r ,表示当前天 fqk 背了第 r 行的单词。
. 2 c ,表示当前天 fqk 背了第 c 列的单词。
【输出格式】
输出包含 n 行, 每行 m 个整数, 表示每个格子中的单词最后一次背
是在哪天,如果这个单词没有背过,则输出 0 。
【输入样例】
3 3 3
1 2
2 3
1 3
【输出样例】
0 0 2
1 1 2
3 3 3
【数据范围】
对于 % 30 的数据, 1000 , ,  k m n 。
对于 % 100 的数据, 100000 , 100000 , 5000 ,     k m n m n 。
【时空限制】
对于每个测试点,时间限制为 s 1 ,空间限制为 MB 512 。

模拟

#include<cstdio>
#define maxn 5010
using namespace std;
int n,m,k,mxc[maxn],mxl[maxn];
int init(){
int x=,f=;char s=getchar();
while(s<''||s>''){if(s=='-')f=-;s=getchar();}
while(s>=''&&s<=''){x=x*+s-'';s=getchar();}
return x*f;
}
int Max(int x,int y){
return x>y?x:y;
}
int main(){
freopen("word.in","r",stdin);
freopen("word.out","w",stdout);
n=init();m=init();k=init();
int x,y;
for(int i=;i<=k;i++){
x=init();y=init();
if(x==)mxc[y]=i;
if(x==)mxl[y]=i;
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++)
printf("%d ",Max(mxc[i],mxl[j]));
printf("\n");
}
fclose(stdin);fclose(stdout);
return ;
}

脱水缩合
(merge.c/cpp/pas)
【题目描述】
fqk 退役后开始补习文化课啦, 于是他打开了生物必修一开始复习
蛋白质,他回想起了氨基酸通过脱水缩合生成肽键,具体来说,一个
氨基和一个羧基会脱去一个水变成一个肽键。于是他脑洞大开,给你
出了这样一道题:
fqk 将给你 6 种氨基酸和 m 个脱水缩合的规则,氨基酸用
' ' , ' ' , ' ' , ' ' , ' ' , ' ' f e d c b a 表示,每个规则将给出两个字符串 t s, ,其中
1 | | , 2 | |   t s ,表示 s 代表的两个氨基酸可以通过脱水缩合变成 t 。然后
请你构建一个长度为 n ,且仅由 ' ' , ' ' , ' ' , ' ' , ' ' , ' ' f e d c b a 构成的氨基酸序列,
如果这个序列的前两个氨基酸可以进行任意一种脱水缩合, 那么就可
以脱水缩合,脱水缩合后序列的长度将 1  ,这样如果可以进行 1  n 次
脱水缩合,最终序列的长度将变为 1 ,我们可以认为这是一个蛋白质,
如果最后的蛋白质为 ' 'a , 那么初始的序列就被称为一个好的氨基酸序
列。 fqk 想让你求出有多少好的氨基酸序列。
注:题目描述可能与生物学知识有部分偏差(即氨基酸进行脱水
缩合后应该是肽链而不是新的氨基酸),请以题目描述为准。
【输入格式】
第一行两个整数 q n, 。
接下来 q 行,每行两个字符串 t s, ,表示一个脱水缩合的规则。
【输出格式】
一行,一个整数表示有多少好的氨基酸序列。
【输入样例】
3 5
ab a
cc c
ca a
ee c
ff d
【输出样例】
4
【样例解释】
一共有四种好的氨基酸序列,其脱水缩合过程如下:
"abb" "ab" "a"
"cab" "ab" "a"
"cca" "ca" "a"
"eea" "ca" "a"
【数据范围】
对于 % 100 的数据, 36 , 6 2    q n 。数据存在梯度。
【时空限制】
对于每个测试点,时间限制为 s 2 ,空间限制为 MB 512 。

这题卡读题啊 无语了

#include<cstdio>
#define maxn 110
using namespace std;
int n,m,f[maxn][maxn][maxn],r[maxn],ans;
char s[],c[];
bool vis[];
void dfs(int now,int x,int y){
if(now==n+){
if(x!=)return;
int mx=;
for(int i=;i<=n;i++)
mx=mx*+r[i];
if(vis[mx])return;
vis[mx]=;
ans++;return;
}
for(int i=;i<=;i++)
if(f[x][y][i])dfs(now+,i,r[now+]);
}
void Dfs(int now){
if(now==n+){
dfs(,r[],r[]);return;
}
for(int i=;i<=;i++){
r[now]=i;Dfs(now+);r[now]=;
}
}
int main()
{
freopen("merge.in","r",stdin);
freopen("merge.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
scanf("%s%s",s,c);
int x=s[]-'a'+,y=s[]-'a'+,z=c[]-'a'+;
f[x][y][z]=;
}
Dfs();printf("%d\n",ans);
fclose(stdin);fclose(stdout);
return ;
}

一次函数
(fx.c/cpp/pas)
【题目描述】
fqk 退役后开始补习文化课啦, 于是他打开了数学必修一开始复习
函数, 他回想起了一次函数都是 b kx x f   ) ( 的形式, 现在他给了你 n 个
一次函数
i i i
b x k x f   ) ( , 然后将给你 m 个操作, 操作将以如下格式给出:
M . 1 i k b ,把第 i 个函数改为 b kx x f i   ) ( 。
Q . 2 l r x ,询问 ))) ( (... (
1
x f f f
l r r 
mod 1000000007 的值。
【输入格式】
第一行两个整数 n , m ,代表一次函数的数量和操作的数量。
接下来 n 行,每行两个整数,表示
i
k ,
i
b 。
接下来 m 行,每行的格式为 M i k b 或 Q l r x 。
【输出格式】
对于每个操作 Q ,输出一行表示答案。
【输入样例】
5 5
4 2
3 6
5 7
2 6
7 5
Q 1 5 1
Q 3 3 2
M 3 10 6
Q 1 4 3
Q 3 4 4
【输出样例】
1825
17
978
98
【数据范围】
对于 % 30 的数据, 1000 ,  m n 。
对于 % 100 的数据, 1000000007 , , , 200000 ,   x b k m n 。
【时空限制】
对于每个测试点,时间限制为 s 2 ,空间限制为 MB 512 。

暴力不粘了

线段树

/*线段树 每个节点维护 k b 合并的时候手推一下式子就好了 跑的略慢 */
#include<cstdio>
#define mod 1000000007
#define ll long long
#define lc k*2
#define rc k*2+1
#define mid (l+r)/2
#define maxn 200010
#ifdef unix
#define LL "%lld\n"
#else
#define LL "%I64d\n"
#endif
using namespace std;
int n,m;
ll A[maxn*],B[maxn*];
char s[];
int init(){
int x=,f=;char s=getchar();
while(s<''||s>''){if(s=='-')f=-;s=getchar();}
while(s>=''&&s<=''){x=x*+s-'';s=getchar();}
return x*f;
}
void Insert(int k,int l,int r,int x,int a,int b){
if(l==r){
A[k]=a;B[k]=b;return;
}
if(x<=mid)Insert(lc,l,mid,x,a,b);
else Insert(rc,mid+,r,x,a,b);
A[k]=A[lc]*A[rc]%mod;B[k]=(A[rc]*B[lc]%mod+B[rc])%mod;
}
ll Queryk(int k,int l,int r,int x,int y){
if(x<=l&&y>=r)return A[k];
if(y<=mid)return Queryk(lc,l,mid,x,y);
else if(x>mid)return Queryk(rc,mid+,r,x,y);
else{
ll kl=Queryk(lc,l,mid,x,y);
ll kr=Queryk(rc,mid+,r,x,y);
return kl*kr%mod;
}
}
ll Queryb(int k,int l,int r,int x,int y){
if(x<=l&&y>=r)return B[k];
if(y<=mid)return Queryb(lc,l,mid,x,y);
else if(x>mid)return Queryb(rc,mid+,r,x,y);
else{
ll bl=Queryb(lc,l,mid,x,y);
ll br=Queryb(rc,mid+,r,x,y);
ll kr=Queryk(rc,mid+,r,x,y);
return (kr*bl%mod+br)%mod;
}
}
int main()
{
freopen("fx.in","r",stdin);
freopen("fx.out","w",stdout);
n=init();m=init();ll x,y,z;
for(int i=;i<=n;i++){
x=init();y=init();
Insert(,,n,i,x,y);
}
for(int i=;i<=m;i++){
scanf("%s",s);x=init();y=init();z=init();
if(s[]=='M')Insert(,,n,x,y,z);
else if(s[]=='Q'){
ll K=Queryk(,,n,x,y);
ll BB=Queryb(,,n,x,y);
printf(LL,(K*z%mod+BB)%mod);
}
}
fclose(stdin);fclose(stdout);
return ;
}