2016.11.9 小測試，2016.11.9測試

2016.11.9 小測試，2016.11.9測試

第一題

背單詞

(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列最後一次背是在哪天。行列交叉的地方輸出較大的。

 附上略丑的代碼。

#include<string>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

int r,c,l,t,n,m,k,i,j,hang[5000],lie[5000];
int main()
{
//    freopen("word.in","r",stdin);
//    freopen("word.out","w",stdout);
    cin>>n>>m>>k;
    for(i=1;i<=k;++i)
    {
        cin>>r>>c;
        if(r==1) hang[c]=i;
        if(r==2) lie[c]=i;
    }
    for(i=1;i<=n;++i)
    {
        for(j=1;j<=m;++j)
        {
            if(hang[i]>lie[j]) cout<<hang[i]<<" ";
            else cout<<lie[j]<<" ";
        }
        cout<<endl;
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

脫水縮合

(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;
}

第三題

一次函數
（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;
}