首页 > 代码库 > 7.22测试

7.22测试

NOIP2016 模拟赛

    ——那些年,我们学过的文化课

1.背单词

(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 的数据,n、m、k<=1000 。

对于 % 100 的数据,n、m<=5000,n*m<=100000,k<=100000。

【时空限制】

对于每个测试点,时间限制为 s 1 ,空间限制为 MB 512 。

上代码:

 

#include<cstdio>#include<iostream>using namespace std;const int M = 100001;int n,m,k,h[M],l[M];int type,hl;int main() {    freopen("word.in","r",stdin);    freopen("word.out","w",stdout);    scanf("%d%d%d",&n,&m,&k);    for(int i=1; i<=k; i++) {        scanf("%d%d",&type,&hl);        if(type==1) h[hl]=i;        if(type==2) l[hl]=i;     }    for(int i=1; i<=n; i++) {        for(int j=1; j<=m; j++)            printf("%d ",max(h[i],l[j]));        printf("\n");    }    fclose(stdin);    fclose(stdout);    return 0;}

 

2.脱水缩合

(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 的数据, 2<=n<=6,q<=36 。数据存在梯度。

【时空限制】

对于每个测试点,时间限制为 s 2 ,空间限制为 MB 512 。

思路:

  氨基酸种数只有6中,组成一个长度为n的序列,我们dfs就可以了。。

上代码:

 

#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; //当最后一个为‘a‘时,因为再往后没有了,最后一定为‘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];             //为什么只替换后一个?因为我们在一个序列中,替换后比较x+1和x+2,所以只需要替换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;}

3.一次函数(fx.c/cpp/pas)

【题目描述】

fqk 退役后开始补习文化课啦, 于是他打开了数学必修一开始复习函数, 他回想起了一次函数都是 f(x)=kx+b的形式, 现在他给了你 n 个一次函数fi(x)=kix+bi , 然后将给你 m 个操作, 操作将以如下格式给出:

1.M i k b,把第 i 个函数改为 fi(x)=kx+b 。
2.Q l r x,询问fr(fr-1(…fl(x)))mod 1000000007的值
【输入格式】
第一行两个整数 n , m ,代表一次函数的数量和操作的数量。
接下来 n 行,每行两个整数,表示ki,bi
接下来 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 的数据, m,n<=1000 。
对于 % 100 的数据,k,b,x<1000000007,  n,m<=200000 。
【时空限制】
对于每个测试点,时间限制为 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;}

自己选的路,跪着也要走完!!!

7.22测试