NOIP 模拟赛那些年，我们学过的文化课 --致已退役的fqk神犇.

/*

这大概是我第一次整理模拟赛吧.

唉.

T2打了很长时间.

一开始读错题了中间都能缩合了.

真心对不起生物老师hhh.

这种状态判重的题目还是做的太少！

*/

背单词

【题目描述】

　　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,nm<=100000,k<=100000。

【时空限制】

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

/*

暴力.

kn.

*/

#include<iostream>

#include<cstdio>

#define MAXN 5001

using namespace std;

int l[MAXN],c[MAXN],n,m,k,g[MAXN][MAXN];

int read()

{

    int x=0,f=1;char ch=getchar();

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

    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

    return x*f;

}

int main()

{

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

    //freopen("word1.out","w",stdout);

    int x,y;

    n=read(),m=read(),k=read();

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

    {

        x=read(),y=read();

        if(x&1)

        {

            for(int j=1;j<=m;j++) g[y][j]=i;

        }

        else

        {

            for(int j=1;j<=n;j++) g[j][y]=i;

        }

    }

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

    {

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

        printf("%d ",g[i][j]);

      printf("\n");

    }

    return 0;

}

/*

模拟.

*/

#include<iostream>

#include<cstdio>

#define MAXN 5001

using namespace std;

int l[MAXN],c[MAXN],n,m,k;

int read()

{

    int x=0,f=1;char ch=getchar();

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

    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

    return x*f;

}

int main()

{

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

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

    int x,y;

    n=read(),m=read(),k=read();

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

    {

        x=read(),y=read();

        if(x&1) l[y]=i;

        else c[y]=i;

    }

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

    {

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

        printf("%d ",max(l[i],c[j]));

      printf("\n");

    }

    return 0;

}

【题目描述】

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 。

/*

Bfs.

从末状态向前找合法状态.

状态总数不到700w.

数据太水乱搞即可23333.

*/

#include<iostream>

#include<cstdio>

#include<queue>

#define MAXN 1001

#define INF 7000001

#define MAXM 40

using namespace std;

int n,m,ans,t[9];

struct data{int x,l;};

struct node{int x[MAXM],tot;}a[MAXM];

bool b[INF];

queue<data>q;

int read()

{

    int x=0,f=1;char ch=getchar();

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

    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

    return x*f;

}

inline void check()

{

    if(n==1)

    {

        for(int i=1;i<=6;i++) ans+=b[i];

    }

    else if(n==2)

    {

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

        for(int j=1;j<=6;j++)

          ans+=b[i*10+j];

    }

    else if(n==3)

    {

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

        for(int j=1;j<=6;j++)

        for(int k=1;k<=6;k++)

          ans+=b[i*100+j*10+k];

    }

    else if(n==4)

    {

        for(int l=1;l<=6;l++)

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

        for(int j=1;j<=6;j++)

        for(int k=1;k<=6;k++)

          ans+=b[l*1000+i*100+j*10+k];

    }

    else if(n==5)

    {

        for(int w=1;w<=6;w++)

        for(int l=1;l<=6;l++)

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

        for(int j=1;j<=6;j++)

        for(int k=1;k<=6;k++)

        ans+=b[w*10000+l*1000+i*100+j*10+k];

    }

    else if(n==6)

    {

        for(int p=1;p<=6;p++)

        for(int w=1;w<=6;w++)

        for(int l=1;l<=6;l++)

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

        for(int j=1;j<=6;j++)

        for(int k=1;k<=6;k++)

        ans+=b[p*100000+w*10000+l*1000+i*100+j*10+k];

    }

}

void bfs()

{

    t[0]=1;int x,z,w;

    for(int i=1;i<=7;i++) t[i]=t[i-1]*10;

    q.push((data){1,1});

    while(!q.empty())

    {

        data u=q.front();q.pop();

        if(u.l==n) continue;

        for(int i=1;i<=min(u.l,1);i++)

        {

            x=(u.x%t[u.l-i+1])/t[u.l-i];

            z=(u.x-u.x%t[u.l-i+1])*10;

            w=u.x%t[u.l-i];

            for(int j=1;j<=a[x].tot;j++)

            {

                int y=a[x].x[j]*t[u.l-i];

                if(!b[z+y+w])

                b[z+y+w]=true,q.push((data){z+y+w,u.l+1});

            }

        }

    }

}

int main()

{

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

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

    char x,y,z;

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

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

    {

        cin>>x>>y>>z;x-=96,y-=96,z-=96;

        a[z].x[++a[z].tot]=x*10+y;

    }

    bfs();

    check();

    cout<<ans;

    return 0;

}

一次函数

【题目描述】

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 行，每行两个整数，表示

mod 1000000007 的值。接下来 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 。

【时空限制】

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

/*

线段树.

对于合并两者的k,b

设前为k1,b1 后为 k2,b2.

则合并k2*(k1*x+b1)+b2.

则转化为k2*k1*x+k2*b1+b2

即k为k2*k1,b为k2*b1+b2.

线段树维护即可.

*/

#include<iostream>

#include<cstdio>

#define MAXN 200001

#define LL long long

#define mod 1000000007

using namespace std;

int n,m,cut;

struct data{int l,r,lc,rc;LL b,k;}tree[MAXN*4];

inline int read()

{

    int x=0,f=1;char ch=getchar();

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

    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

    return x*f;

}

inline void build(int l,int r)

{

    int k=++cut;tree[k].l=l,tree[k].r=r;

    if(l==r)

    {

        tree[k].k=read(),tree[k].b=read();return ;

    }

    int mid=(l+r)>>1;

    tree[k].lc=cut+1;

    build(l,mid);

    tree[k].rc=cut+1;

    build(mid+1,r);

    tree[k].k=tree[tree[k].lc].k*tree[tree[k].rc].k%mod;

    tree[k].b=

    (tree[tree[k].rc].k*tree[tree[k].lc].b%mod+tree[tree[k].rc].b)%mod;

    return;

}

void add(int k,int p,int kk,int b)

{

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

    {

        tree[k].k=kk,tree[k].b=b;

        return ;

    }

    int mid=(tree[k].l+tree[k].r)>>1;

    if(p<=mid) add(tree[k].lc,p,kk,b);

    else add(tree[k].rc,p,kk,b);

    tree[k].k=tree[tree[k].lc].k*tree[tree[k].rc].k%mod;

    tree[k].b=

    (tree[tree[k].rc].k*tree[tree[k].lc].b%mod+tree[tree[k].rc].b)%mod;

    return;

}

LL queryk(int k,int l,int r)

{

    if(l<=tree[k].l&&tree[k].r<=r) return tree[k].k;

    LL tot=1,mid=(tree[k].l+tree[k].r)>>1;

    if(l<=mid) tot*=queryk(tree[k].lc,l,r)%mod;

    if(r>mid) tot*=queryk(tree[k].rc,l,r)%mod;

    return tot%mod;

}

LL queryb(int k,int l,int r)

{

    if(l<=tree[k].l&&tree[k].r<=r) return tree[k].b;

    LL tot=0,mid=(tree[k].l+tree[k].r)>>1;

    if(l<=mid) tot=queryb(tree[k].lc,l,r);

    if(r>mid) {

        tot=(tot*queryk(tree[k].rc,l,r)%mod+queryb(tree[k].rc,l,r))%mod;

    }

    return tot;

}

int main()

{

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

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

    int x,y,z;char ch;

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

    build(1,n);

    while(m--)

    {

        cin>>ch;

        x=read(),y=read(),z=read();

        if(ch=='M') add(1,x,y,z);

        else

        {

            LL p=queryk(1,x,y),q=queryb(1,x,y);

            printf("%lld\n",(p*z%mod+q)%mod);

        }

    }

    return 0;

}

巴特西

NOIP 模拟赛那些年，我们学过的文化课 --致已退役的fqk神犇.

最新文章

热门文章

巴特西

NOIP 模拟赛 那些年，我们学过的文化课 --致已退役的fqk神犇.

最新文章

热门文章

NOIP 模拟赛那些年，我们学过的文化课 --致已退役的fqk神犇.