Aug.Day16 8.23总结
#A.填涂颜色
本题首先需要 推规律！
| 2 | 3 | 4 | |
|---|---|---|---|
| 3 | |||
| 4 | |||
| 5 |
最后终于发现规律：ans = min (n, k) * min (m, k)。
Code:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e3 + 10;
int n, m, k, a[N][N];
void Fio (string iofile)
{
string ifl = iofile + ".in", ofl = iofile + ".out";
freopen (ifl.c_str (), "r", stdin);
freopen (ofl.c_str (), "w", stdout);
}
signed main ()
{
Fio ("color");
cin >> n >> m >> k;
cout << min (k, n) * min (k, m);
return 0;
}
感受与学习：多推规律！！！（虽然但是这也需要那么一点点运气才能发现规律）。
错误原因：阿巴阿巴阿巴我没有那点运气（人话就是没发现规律）。
#B.密码
本题看似复杂，实际上 也不简单 非常简单。
只需要将一个转换数组 char cgcode[i][j] 求出来即可，所以我们需要发现规律。可以发现首先需要用双重循环 for (i, j : int ('A') ~ int ('Z'), int ('A') ~ int ('Z')) 枚举，发现当 i == 'A' 时 cgcode[i][j] = j，而当 j == 'A' 时，cgcode[i][j] = i，接下来每一项 cgcode[i][j] 都是上一项加 ，所以可以写 cgcode[i][j - 1] 或 cgcode[i - 1][j]，都可以，不过需要判断一下当上一个为 'Z' 时，这一个应该为 'A'。
接下来用 idx 表示密钥的下标，枚举密文的每一位，先考虑大小写的问题：由于 cgcode[i][j] 是全大写的，所以如果 code[i] 为小写字母，那么则用一个变量标记并转为大写，输出时再转为小写就行。
不过要注意，这里是将密文转为明文，所以输出时要用 for 循环在 cgcode[key[idx]] 中找到值为 code[i] 的第二维下标，下标即为明文（当然如果可以用公式也可以）。
Code:
#include <bits/stdc++.h>
using namespace std;
const int N = 5e2 + 10;
string key, code;
char cgcode[N][N];
int idx;
void Fio (string iofile)
{
string ifl = iofile + ".in", ofl = iofile + ".out";
freopen (ifl.c_str (), "r", stdin);
freopen (ofl.c_str (), "w", stdout);
}
void InitCode ()
{
int fra = int ('A'), toz = int ('Z');
for (int i = fra; i <= toz; i ++)
{
for (int j = fra; j <= toz; j ++)
{
if (i == fra)
{ cgcode[i][j] = j; continue; }
if (j == fra)
{ cgcode[i][j] = i; continue; }
cgcode[i][j] = (cgcode[i - 1][j] + 1);
if (cgcode[i - 1][j] == toz) cgcode[i][j] = fra;
}
}
}
int main ()
{
Fio ("vigenere");
cin >> key >> code;
InitCode ();
int fra = int ('A'), toz = int ('Z');
for (int i = 0; i < code.size (); i ++)
{
bool issml = false;
if (islower (code[i])) issml = true, code[i] = toupper (code[i]);
if (islower (key[idx])) key[idx] = toupper (key[idx]);
for (int j = fra; j <= toz; j ++)
if (cgcode[key[idx]][j] == code[i])
{
cout << (issml ? char (j - 'A' + 'a') : char (j));
break;
}
idx = (idx + 1) % key.size ();
}
return 0;
}
感受与学习：在写一道题写完后，首先检查正确性，其次检查语法错误，最后找一些奇奇怪怪的错误，比如在 Windows 环境下可以运行的代码到 Linux 环境下不能运行的错误，由于 CSP 评测时使用 NOI Linux 环境编译，所以 这点非常重要！！！
错误原因：qwq 本来用来初始化 cgcode 的函数类型想写 void 写成了 char，虽然 Dev-C++ 上能运行但是 Linux 环境不能通过...
#C.海港
本题真的非常非常简单而煎蛋。（ 所以就不讲了 ）。
首先本题需要看懂题面，看懂了就很好做了。这是一道模版滑动窗口（呃由于太过简单所以没觉得是滑动窗口），作者用了仨 STL 写，个人认为就是一道 小W的病毒歼灭战++，思路都有些十分相似。
首先需要一个 unordered_map 记录每种国籍的人有多少人和一个变量 cnt 记录有多少种不同的国籍，再用一个双端队列 + vector 记录每艘船的信息，队列中的每一个元素就是一艘船，vector 中第 位是这艘船进港的时间，（ 表示 vector 的大小）表示每个乘客的国籍，每新进一艘船就将其和队首元素作比较，如果大于等于 则遍历队首的 vector，将每位乘客的国籍编号在 unordered_map 中减 ，如果发现有一次减完了，则 cnt --。
接下来将当前船只入队并遍历当前船只的所有乘客 v[i]，将每个乘客在 unordered_map 中的变量加 ，如果发现某个国籍的人在加 之前是 ，那么说明有新国籍的人进来，cnt ++。
最后每次输出 cnt 即可。
Code:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
unordered_map <int, int> sta;
deque <vector<int> > ct;
int n, cnt;
void Fio (string iofile)
{
string ifl = iofile + ".in", ofl = iofile + ".out";
freopen (ifl.c_str (), "r", stdin);
freopen (ofl.c_str (), "w", stdout);
}
signed main ()
{
Fio ("port");
cin >> n;
for (int i = 1; i <= n; i ++)
{
int t, k; cin >> t >> k;
ct.push_back ({t});
for (int j = 1; j <= k; j ++)
{
int x; cin >> x;
if (! sta[x]) cnt ++;
sta[x] ++;
ct.back ().push_back (x);
}
if (ct.size () > 1)
while (ct.size () > 1 && ct.back ()[0] - ct.front ()[0] >= 86400)
{
for (int j = 1; j < ct.front ().size (); j ++)
{
sta[ct.front ()[j]] --;
if (! sta[ct.front ()[j]]) cnt --;
}
ct.pop_front ();
}
cout << cnt << '\n';
}
return 0;
}
感受与学习：要学会灵活运用 STL 中的数据结构，明白每种数据结构的用处。
错误原因：无。
#D.流星雨
本题就是一道广搜模版题（虽然但是我又双叒叕没做出来）。
首先用一个 g[][] 数组记录流星落下的时间，没有则赋值为 0x3f3f3f3f，不过记住要更新它和它周围的 个格子并考虑边界问题。
接下来套一个广搜模版，只不过需要改一点条件：
- 结束的条件需要改变，只要当前走到的
g[x][y]为0x3f3f3f3f说明走到了安全的地方，直接return。 - 广搜往四个方向搜时，
continue的条件要变，首先要判断边界，这里有一个细节，nx和ny的边界为 ，因为输入的x, y的最大值为 。其次遍历当前的步数是否小于当前位置流星砸下来的时间（因为步数就是用时），如果都满足，就新增当前节点。 - 最后特判一下，如果在 时刻点 就有陨石砸下来那么直接输出
-1（作者也不太确定有没有用）。
Code:
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int n, mnu = 2e9;
bool vis[310][310];
int g[310][310];
struct meteoJ
{
int x, y;
int step;
};
queue <meteoJ> mor;
void Fio (string iofile)
{
string ifl = iofile + ".in", ofl = iofile + ".out";
freopen (ifl.c_str (), "r", stdin);
freopen (ofl.c_str (), "w", stdout);
}
void BFSmt ()
{
mor.push ({0, 0, 0});
while (mor.size ())
{
auto now = mor.front (); mor.pop ();
if (g[now.x][now.y] == 0x3f3f3f3f)
{
mnu = now.step;
return;
}
for (int i = 0; i < 4; i ++)
{
int nx = now.x + dx[i];
int ny = now.y + dy[i];
int ns = now.step + 1;
if (nx < 0 || nx > 301 || ny < 0 || ny > 301) continue;
if (ns >= g[nx][ny]) continue;
if (vis[nx][ny]) continue;
vis[nx][ny] = true;
mor.push ({nx, ny, ns});
}
}
mnu = -1;
}
int main ()
{
Fio ("meteor");
cin >> n;
memset (g, 0x3f, sizeof (g));
for (int i = 1; i <= n; i ++)
{
int x, y, t; cin >> x >> y >> t;
g[x][y] = min (t, g[x][y]);
if (x + 1 < 301) g[x + 1][y] = min (t, g[x + 1][y]);
if (y + 1 < 301) g[x][y + 1] = min (t, g[x][y + 1]);
if (x - 1 > -1) g[x - 1][y] = min (t, g[x - 1][y]);
if (y - 1 > -1) g[x][y - 1] = min (t, g[x][y - 1]);
}
BFSmt ();
if (g[0][0] == 0) { cout << -1; return 0; }
cout << (mnu == 0x3f3f3f3f ? -1 : mnu);
return 0;
}
感受与学习：qwq 以后遇到这种又放在靠后又看起来复杂、涉及很难的算法的题应该仔细阅读，模版题的变形不一定就很难。
错误原因：qwq 有两点：
- 阿巴阿巴因为就像上面说的原因，觉得又放在靠后又看起来复杂、涉及很难的算法（
自己绝对做不出来的那种）。 - 没时间力...
