2022.3.22

第一题

给个二维数组表示图形，将其等比放大。

我的思路：签到题，就是一个像素放大k倍，面积为原来的k^2。

第二题

给一个01串，下标从1开始，求两个窗口，窗口大小相等，可以相交但不能完全重叠，其中一个包含的0和1的个数和另外一个相等，取窗口长度最大的。

输入：11011

输出：1 4 2 5（1到4中有3个1和1个0，2到5中也有3个1和1个0）

数据量10^6。

我的思路：

1、直接输出1 n - 1 2 n，能过32%

2、求前缀和，然后遍历长度（从n-1到2），通过前缀和求1的长度，存max里，另存一个变量存max的数量，遍历完如果max数量大于1，则该长度就是所求答案，再遍历一次，任意找两对输出即可。

该方法是O(n^2)的，最后过了80%，不知道咋优化了。

第三题

题目输入挺复杂，是个图，按顺序一条条路走就行。

一个人送快递，有n个村庄（下标1开始），先输入m条单向边，再输入k条双向边，起点为s，每条边起点u终点v耗时w。

图中可能存在重边和自己到自己的边。

若到达一个地方时总耗时为单数，则再耗时a，否则耗时b。

一共q个快递，每个快递需要送到qi，按顺序送。

最后需要回到起点。

求最短所需时间。

输入：

3 0 3 1

1 2 3

3 2 6

1 3 9

6 3 3

1 2 3

输出：

30

数据量10^6。

我的思路：Floyd求最短路，自己到自己为0，然后按步骤来，最后回起点。

两个例子能过，提交只有4%，因为建图和路长存储都直接无脑数组n ^ 2了，算最短路更是n ^ 3，可能剩下都超时超内存了吧。。。