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");
        }
    }
}

 

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据