vj4补题（上午）
线段树+multiset（buhui)
原文链接：https://blog.csdn.net/m0_64158084/article/details/127790615
补充）set和mutiset
一个自动去重，一个不去重。
字典树/map
题目：给你一个N x N的矩阵，矩阵由小写字母和#组成，#为障碍。然后给出m个字符串和该字符串对应的值。然后从矩阵中截取子串，子串指矩阵中水平方向从左到右碰到障碍的最长串，或者竖直方向从上到下碰到障碍的最长串，也或是碰到矩阵边界的最长串，问这些子串是否都存在于m个给定的字符串中，若存在则输出值的总和，否则输出-1。
如果从矩阵中得到的单词在字典中不存在，那么输出 -1
补充 unordered_map和map
unordered_map
不需要元素有序，只关心快速的插入、删除和查找操作，大多数查找操作都是常数时间复杂度的情况下。
map
元素的有序访问。
mp.count(s) 表示统计关联容器 mp 中键为 s 的元素出现的次数，返回次数。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define mem(a,b) memset(a,b,sizeof a)
#define int long long
#define fi first
#define se second
#define endl '\n'
/**/
const int N = 2010, mod = 1e9+7;
int T, n, m;
char a[N][N];
unordered_map<string,int> mp, f;
signed main()
{
Ios;
cin >> T;
while(T--)
{
cin >> n >> m;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
cin >> a[i][j];
}
}
mp.clear();
//记得清空
for(int i=1; i<=m; i++)
{
string s;
cin >> s;
int x;
cin>>x;
mp[s] = x;
}
int ans = 0, flag = 1;
//横着扫描
for(int i=1; i<=n; i++)
{
string s;
for(int j=1; j<=n; j++)
{
if(a[i][j] == '#')
{
if(s != "" && !mp.count(s)) flag = 0;
//矩阵中的单词不存在
else ans += mp[s];
s = "";
//置空s，重新统计
}
else s += a[i][j];
//string的拼接可用+
}
//到了边界
if(s != "" && !mp.count(s)) flag = 0;
else ans += mp[s];
}
//竖着扫描
for(int j=1; j<=n; j++)
{
string s;
for(int i=1; i<=n; i++)
{
if(a[i][j] == '#')
{
if(s != "" && !mp.count(s)) flag = 0;
else ans += mp[s];
s = "";
}
else s += a[i][j];
}
if(s != "" && !mp.count(s)) flag = 0;
else ans += mp[s];
}
if(!flag) cout << -1 << endl;
else cout << ans << endl;
}
return 0;
}