Paiza 命运石之门活动 题解

命运逻辑门，活动入口：STEINS;GATE 電脳言語のオルダーソンループ

这次比上次那个《程序员死绝了》简单多了，只给出剧情相关的四个题解

由于咱は日本語本当上手实在不懂日文（全靠浏览器实时翻译成中/英文读题，黑盒测试），只能说一下大概的题意

第一题 正則表現のエントリーポイント

题意

输入两个字符串，在两个字符串间添加分号 ‘;’ 后输出

题解

过于简单，无题解

第二题 性能解析のタイプセーフ

题意

大意是游戏中的角色升级：

第一行输入： N 和 K 代表 N 个角色，以及进行一次游戏能够获得 K 点经验（小数）

之后每行给出每一个角色所需的经验点数

计算需要打多少场游戏

题解

累加角色经验值得到 sum，计算 res 使得 res * k > sum

简单，无代码

第三题 例外処理のタブーサーチ

题意

第一行输入：给出 N、M 和 L，分别代表第一个表格的行数、两个表格的列数、第二个表格的行数

往后的 N 行是第一个表格的元素，再往后的 L 行是第二个表格的元素

根据第二个表格的数据计算出第三个表格，规则为：在第二个表格中，对于每一行数据的每个元素，用下一行的同列元素减去本行元素，得到第三个表格对行对应列的元素

拿第三个表格的数据与第一个表格对比，输出第三个表格中的行在第一个表格中的行数

题解

C# 代码

数据量不大，用了 Linq 和 List<> 的 SequenceEqual()，替换成其他方法效率会高一点

得到差后立即搜索第一个表格，也可以减少时间/空间消耗

using System;
using System.Linq;
using System.Collections.Generic;

namespace Paiza {
    class Program {
        static void Main() {
            List<List<int>> l1 = new List<List<int>>(), l2 = new List<List<int>>(), l3 = new List<List<int>>();

            string[] input = Console.ReadLine().Split();
            int n = Convert.ToInt32(input[0]), m = Convert.ToInt32(input[1]), l = Convert.ToInt32(input[2]);

            for (int i = 0; i < n; i++)
                l1.Add(Console.ReadLine().Split().Select(x => int.Parse(x)).ToList());

            for (int i = 0; i < l; i++)
                l2.Add(Console.ReadLine().Split().Select(x => int.Parse(x)).ToList());

            for (int i = 0; i < l - 1; i++) {
                List<int> subs = new List<int>();
                for (int j = 0; j < m; j++) {
                    subs.Add(l2[i + 1][j] - l2[i][j]);
                }
                l3.Add(subs);
            }

            for (int i = 0; i < l - 1; i++)
                for (int j = 0; j < n; j++)
                    if (l1[j].SequenceEqual(l3[i])) 
                        Console.WriteLine(j + 1);

        }
    }
}

第四题 進化戦略のプロシージャ

题意

一个地牢游戏，房间里有游戏角色，每个角色都想移动到指定房间，判断角色移动过程中是否出现“死锁”

第一行输入：N 代表 N 个房间，M 代表有 M 个角色

之后一行代表一个角色的数据，每行给出两个整数 S 和 T，S 是当前角色所在的房间，T 是当前角色想去的房间

如果一个角色要去的房间里有人，并且这个人也想去这个角色的房间，这种情况就是“死锁”

题解

给出边，判断回路

根据每个角色要去的房间，可以生成一个链（1 去 2，2 去 4，4 去3 …），只要最后一个角色不回到之前某个角色的房间（也可以理解成链表无环），都不会有“死锁”发生

C# 代码

注意两点：

1. M ≦ N：M 是可以等于 N 的，但又有 S_i = T_i，也就是说当房间住满了人也可能没有回路，因为每个角色可以原地不动
2. S_i != S_j，T_i ≠ T_j：不会出现两个角色住同一间房，或者两个角色想去同一间房的情况

懒得没做优化

不负责任的构想一下：也可以用链表实现，用快慢指针判环

using System;
using System.Linq;

namespace Paiza { 
    class Program { 
        static void Main() {
            int[] input = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray(), roomTo;
            int n = input[0], m = input[1];

            roomTo = Enumerable.Repeat(0, n + 2).ToArray(); // 0 代表房间内无角色

            for (int i = 0; i < m; i++) {
                input = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();
                roomTo[input[0]] = input[1]; // roomTo 记录当前房间内的人想去的房间
            }

            for (int i = 1; i <= n; i++) {
                if (roomTo[i] == i || roomTo[i] == 0) continue; // 玩家原地不动 或 此房间没有玩家

                bool[] visited = Enumerable.Repeat(false, n + 2).ToArray(); // visited 记录房间是否已经有角色想去
                int j = i;
                while (roomTo[j] != 0) { // 开始判断回路
                    if (visited[j]) {
                        Console.WriteLine("Yes");
                        return;
                    }
                    visited[j] = true;
                    j = roomTo[j];
                }
            }

            Console.WriteLine("No");
        }
    }
}