TimusOJ杂题集锦

发表于

1008. Image Encoding

题意：有一个 10×1010\times 10 的矩阵，左下角为 (0,0)(0,0)，右上角为 (10,10)(10,10)（平面直角坐标系）。一部分格子被涂成了黑色，保证为一个联通块。有如下两种描述状态的方式：

  1. 第一行给出黑格子的个数 nn，接下来 nn 行依次给出黑格子的坐标。以 xx 位第一关键字、yy 为第二关键字从小到大给出。
  2. 第一行给出左下角（关键字同上）的格子坐标，接下来，第一行一个字符串描述与该格子相邻的、还没有被描述过的格子，用 R,T,L,B\texttt{R,T,L,B} 表示右、上、左、下（严格以此为顺序）；接下来用广度优先遍历的顺序来描述这些“第二层”的格子；以此类推直至描述完。每行以逗号 , 结尾，最后一行以 . 结尾。

要求在两种方式之间转化。

首先我们要判断输入的是哪种方式，这需要判断第一行有几个数（即有没有空格）。我们使用 getline 读入一整行，判断有没有空格即可。而要正常读入一遍第一行的内容，可以使用 stringstream 来简化这一步骤。

首先考虑如何从方式 1 变成方式 2。对于输入，我们在二维数组上直接记录图像。由于排序关键字相同，输入的第一个坐标即为左下角坐标。我们维护一个队列表示当前准备扩展的节点，模拟广度优先搜索过程并输出扩展的过程。为了保证只遍历“还没有被描述过的格子”，可以描述一个格子就直接把该格子涂成白色。

然后考虑如何从方式 2 变成方式 1。我们同样维护一个队列存待扩展的坐标，模拟广度优先搜索，不过这次是根据他的输入来判断往哪边扩展。我们将描述到的格子扔到 vector<pair> 里，最后利用 pair 自带的比较函数排序后输出即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<bits/stdc++.h>
using namespace std;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const char w[4]={'R','T','L','B'};
bool a[15][15];
signed main() {
    string s;
    bool flag=1;
    getline(cin,s);
    for(int i=0;i<s.size();i++)
        if(s[i]==' ') flag=0;
    stringstream fin(s);
    if(flag==1) {
        int n,sx=0,sy=0;
        fin>>n;
        for(int i=1;i<=n;i++) {
            int x,y;
            cin>>x>>y;
            a[x][y]=1;
            if(sx==0) sx=x,sy=y;
        }
        cout<<sx<<" "<<sy<<endl;
        queue<pair<int,int> > q;
        q.push({sx,sy});
        a[sx][sy]=0;
        while(!q.empty()) {
            auto now=q.front();q.pop();
            for(int i=0;i<4;i++)
                if(a[now.first+dx[i]][now.second+dy[i]]) {
                    cout<<w[i];
                    q.push({now.first+dx[i],now.second+dy[i]});
                    a[now.first+dx[i]][now.second+dy[i]]=0;
                }
            if(q.empty()) puts(".");
            else puts(",");
        }
    }
    else {
        int sx,sy;
        fin>>sx>>sy;
        vector<pair<int,int> > ans;
        ans.push_back({sx,sy});
        queue<pair<int,int> > q;
        q.push({sx,sy});
        while(1) {
            auto now=q.front();q.pop();
            string s;
            cin>>s;
            for(int i=0;i<s.size()-1;i++) {
                for(int j=0;j<4;j++)
                    if(s[i]==w[j]) {
                        q.push({now.first+dx[j],now.second+dy[j]});
                        ans.push_back({now.first+dx[j],now.second+dy[j]});
                    }
            }
            if(s[s.size()-1]=='.') break;
        }
        sort(ans.begin(),ans.end());
        cout<<ans.size()<<endl;
        for(auto v:ans) cout<<v.first<<" "<<v.second<<endl;
    }
    return 0;
}

1133. Fibonacci Sequence

题意：定义扩展的斐波那契序列为 ∀i∈(−∞,+∞)f[i]=f[i−1]+f[i−2]\forall i\in(-\infty,+\infty) f[i]=f[i-1]+f[i-2]，给出两个位置 i,ji,j 的值，求另一个位置 nn 的值。保证三个位置 ∈[−1000,1000]\in [-1000,1000] 且这三个位置之间所有数都 ∈[−2e9,2e9]\in [-2e9,2e9]。

假设 i<ji<j，我们可以设 x=f[i+1]x=f[i+1]，则 f[i+2]=f[i]+x,f[i+3]=f[i]+2x,f[i+4]=2f[i]+3x⋯f[i+2]=f[i]+x,f[i+3]=f[i]+2x,f[i+4]=2f[i]+3x\cdots 可以发现，每个 ii 之后的数都可以用 f[i]f[i] 和 xx 的线性方程来表示，所以我们求出 f[j]f[j] 的表示方程，即可反推出 xx。得知 f[i],f[i+1]f[i],f[i+1] 后再推到 nn 即可。注意递推线性方程的系数时需要使用 __int128 来存储。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
using namespace std;
#define int long long
int f[2010];
signed main() {
    int i,j,n;
    cin>>i>>f[i+1000]>>j>>f[j+1000]>>n;
    if(f[i+1000]==0&&f[j+1000]==0) {
        cout<<0<<endl;
        return 0;
    }
    if(i>j) swap(i,j);
    if(j>i+1) {
        pair<__int128,__int128> now={0,1},lst={1,0};
        for(int k=i+2;k<=j;k++) {
            auto tmp=now;
            now.first+=lst.first,now.second+=lst.second;
            lst=tmp;
        }
        f[i+1000+1]=(f[j+1000]-f[i+1000]*now.first)/now.second;
    }
    for(int k=i-1+1000;k>=n+1000;k--)
        f[k]=f[k+2]-f[k+1];
    for(int k=i+2+1000;k<=n+1000;k++)
        f[k]=f[k-1]+f[k-2];
    cout<<f[n+1000]<<endl;
    return 0;
}

1164. Fillword

题意：有一个 n×mn\times m 的矩阵，每个格子写着一个字母，你需要从中找出若干个给定的单词，使得每个单词的格子集合互不相交，且每个单词在矩阵中可以四连通地依次连成一条链。从小到大输出剩下的字母集合。保证有解。

由于保证有解，这题就变成了一个彻底的诈骗题。我们根本不需要从矩阵中找到单词，只需要维护字母的出现次数即可。矩阵中出现则加，单词中出现则减，最后剩下的输出即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
char s[15][15];
int t[26];
signed main() {
    int n,m,p;
    scanf("%d%d%d",&n,&m,&p);
    for(int i=1;i<=n;i++) {
        scanf("%s",s[i]);
        for(int j=0;j<m;j++)
            t[s[i][j]-'A']++;
    }
    for(int i=1;i<=p;i++) {
        scanf("%s",s[i]);
        int len=strlen(s[i]);
        for(int j=0;j<len;j++)
            t[s[i][j]-'A']--;
    }
    for(int i=0;i<26;i++)
        for(int j=1;j<=t[i];j++)
            printf("%c",i+'A');
    puts("");
    return 0;
}

1125. Hopscotch

题意：有一个 n×mn\times m 的矩阵，每个格子非黑即白，当你进入一个格子时，所有与它距离为整数的格子取反。给出每个格子进入的次数和终止矩阵，求起始矩阵。

又是一个诈骗题。根据取反的性质，题目转化为给出起始矩阵求终止矩阵，且操作顺序没有影响。而一个格子进入的次数为偶数时没有效果，进入奇数次相当于进入一次。于是，我们 n2n^2 枚举每个操作格子，如果进入了奇数次，则暴力更改与其距离为整数的格子即可。判断是否为整数可以预处理加快速度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
string s[55];
bool flag[55][55];
signed main() {
    int n,m;
    cin>>n>>m;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++) {
            if(sqrt(i*i+j*j)-floor(sqrt(i*i+j*j))<=1e-6)
                flag[i][j]=1;
        }
    for(int i=1;i<=n;i++) {
        cin>>s[i];
        s[i]=s[i];
    }
    for(int i=1;i<=n;i++)
        for(int j=0;j<m;j++) {
            int x;
            cin>>x;
            if(x%2==0) continue;
            for(int k=1;k<=n;k++)
                for(int l=0;l<m;l++)
                    if(flag[abs(k-i)][abs(l-j)])
                        s[k][l]='B'+'W'-s[k][l];
        }
    for(int i=1;i<=n;i++)
        cout<<s[i]<<endl;
    return 0;
}