2016.11.9 小测试

来源:互联网 时间:2016-11-09

第一题

背单词

(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 。

开两个数组存行、列的天,hang[i]表示第i行最后一次背是在哪天,lie[i]表示第i列最后一次背是在哪天。行列交叉的地方输出较大的。

 附上略丑的代码。

 

 1 #include<string>

2 #include<iostream>

3 #include<cstdio>

4 #include<cstring>

5 #include<algorithm>

6

7 using namespace std;

8

9 int r,c,l,t,n,m,k,i,j,hang[5000],lie[5000];

10 int main()

11 {

12 // freopen("word.in","r",stdin);

13 // freopen("word.out","w",stdout);

14 cin>>n>>m>>k;

15 for(i=1;i<=k;++i)

16 {

17 cin>>r>>c;

18 if(r==1) hang[c]=i;

19 if(r==2) lie[c]=i;

20 }

21 for(i=1;i<=n;++i)

22 {

23 for(j=1;j<=m;++j)

24 {

25 if(hang[i]>lie[j]) cout<<hang[i]<<" ";

26 else cout<<lie[j]<<" ";

27 }

28 cout<<endl;

29 }

30 fclose(stdin);

31 fclose(stdout);

32 return 0;

33 }

View Code

 

第二题

脱水缩合

(merge.c/cpp/pas)

【题目描述】

fqk 退役后开始补习文化课啦, 于是他打开了生物必修一开始复习

蛋白质,他回想起了氨基酸通过脱水缩合生成肽键,具体来说,一个

氨基和一个羧基会脱去一个水变成一个肽键。于是他脑洞大开,给你

出了这样一道题:

fqk 将给你 6 种氨基酸和 m 个脱水缩合的规则,氨基酸用

' a' , 'b ' , 'c ' , 'd ' , 'e ' , 'f '  表示,每个规则将给出两个字符串 t s, ,其中

 |s |= 2 ,| t|=1 ,表示 s 代表的两个氨基酸可以通过脱水缩合变成 t 。然后

请你构建一个长度为 n ,且仅由 ' a' , 'b ' , 'c ' , 'd ' , 'e ' , 'f '  构成的氨基酸序列,

如果这个序列的前两个氨基酸可以进行任意一种脱水缩合, 那么就可

以脱水缩合,脱水缩合后序列的长度将 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<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

char s[50][3],t[50][3];

char a[10];

int n,q,ans;

bool vis[50];

inline int read()

{

int a=0,f=1; char c=getchar();

while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();}

while (c>='0'&&c<='9') {a=a*10+c-'0'; c=getchar();}

return a*f;

}

bool judge(int x)

{

if (x==n&&a[n]=='a') return true;

for (int i=1;i<=q;i++)

if (s[i][1]==a[x]&&s[i][2]==a[x+1])

{

int tmp=a[x+1];

a[x+1]=t[i][1];

int flag=judge(x+1);

a[x+1]=tmp;

if (flag) return true;

}

return false;

}

void dfs(int x)

{

if (x==n+1)

{

if (judge(1)) ans++;

return;

}

for (int i=0;i<6;i++)

{

a[x]=i+'a';

dfs(x+1);

}

}

int main()

{

freopen("merge.in","r",stdin);

freopen("merge.out","w",stdout);

n=read(); q=read();

for (int i=1;i<=q;i++)

{

scanf("%s",s[i]+1);

scanf("%s",t[i]+1);

}

dfs(1);

cout<<ans<<endl;

fclose(stdin);

fclose(stdout);

return 0;

}

View Code

第三题

一次函数
(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 。

#include<iostream>

#include<cstdio>

using namespace std;

const int mod=1e9+7;

const int N=200005;

int n,m,K[N],b[N];

struct node

{

int l,r;

long long mul,sum;

}t[N<<2];

inline int read()

{

int a=0,f=1; char c=getchar();

while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();}

while (c>='0'&&c<='9') {a=a*10+c-'0'; c=getchar();}

return a*f;

}

inline node Unite(node x,node y)

{

node ans;

ans.l=x.l; ans.r=y.r;

ans.mul=x.mul*y.mul%mod;

ans.sum=(x.sum*y.mul%mod+y.sum)%mod;

return ans;

}

inline void pushup(int k)

{

t[k]=Unite(t[k<<1],t[k<<1|1]);

}

void build(int k,int x,int y)

{

if (x==y)

{

t[k].l=t[k].r=x;

t[k].sum=b[x];

t[k].mul=K[x];

return;

}

int mid=x+y>>1;

build(k<<1,x,mid); build(k<<1|1,mid+1,y);

pushup(k);

}

void modify(int k,int x,int K,int B)

{

if (t[k].l==t[k].r)

{

t[k].sum=B;

t[k].mul=K;

return;

}

int mid=t[k].l+t[k].r>>1;

if (x<=mid) modify(k<<1,x,K,B); else modify(k<<1|1,x,K,B);

pushup(k);

}

node query(int k,int x,int y)

{

if (t[k].l==x&&t[k].r==y) return t[k];

int mid=t[k].l+t[k].r>>1;

if (y<=mid) return query(k<<1,x,y);

else if (x>mid) return query(k<<1|1,x,y);

else return Unite(query(k<<1,x,mid),query(k<<1|1,mid+1,y));

}

int main()

{

freopen("fx.in","r",stdin);

freopen("fx.out","w",stdout);

n=read(); m=read();

for (int i=1;i<=n;i++)

K[i]=read(),b[i]=read();

build(1,1,n);

for (int i=1;i<=m;i++)

{

char opt[5];

scanf("%s",opt);

if (opt[0]=='M')

{

int x=read(),k=read(),b=read();

modify(1,x,k,b);

}

else

{

int l=read(),r=read(),x=read();

node ans=query(1,l,r);

printf("%I64d\n",(ans.mul*x%mod+ans.sum)%mod);

}

}

fclose(stdin);

fclose(stdout);

return 0;

}

View Code

 

相关阅读:
Top