模板匹配

题型

$stl$ $map$ 使用

分析

简单的匹配问题一般用 map 即可，这里使用要数字和字符串每个位置的一一对应（就是该相同时相同，不该相同时不同，而且还得是双向的），那就开两个 map 分别来指向各自对应即可。

注意最后多开判断函数或者直接存答案最后输出，不然continue,break,return没使用好连样例都过不了

代码

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=2e5+10;
int t;
string work(vector<int>& a,string& s)
{
    unordered_map<int,char>mp1;
    unordered_map<char,int>mp2;
    int n=a.size();
    for(int i=0;i<n;i++)
    {
        if(mp1.find(a[i])!=mp1.end())
        {
           if(mp1[a[i]]!=s[i])
           {
            return "NO";
            }   
        } 
        else mp1[a[i]]=s[i];

        if(mp2.find(s[i])!=mp2.end())
        {
            if(mp2[s[i]]!=a[i])
            {
                return "NO";
            }
        }
        else mp2[s[i]]=a[i];
    }
    return "YES";
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>t;
    vector<string>ans;
    while(t--)
    {
        int n,m;
        cin>>n;
        vector<int>a(n);
        for(int i=0;i<n;i++)cin>>a[i];
        cin>>m;
        while(m--)
        {
            string s;
            cin>>s;
            if(s.length()!=n)ans.push_back("NO");
            else ans.push_back(work(a,s));
        }
    }
    for(auto &w:ans)cout<<w<<endl;
    return 0;
}

最大LR

题型

贪心 前缀和

分析

被题意和最后一个样例误导了，贪心也一直往这个方向贪，其实由于区间的不可再用性，每次选择两端的L和R，这样肯定是最大的和，由两端向中间走，这样得到的和是最大的。

注意

既然不习惯用 p[i+1]=p[i]+a[i] 这种写法，那另外那种写的时候要注意，但是嘛，前缀和数组不需要重置，l和r数组每次去更新也不必重置。

代码

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=2e5+10;
int n,a[N],s[N];
int l[N],r[N];
string str;
void solve()
{
    cin>>n;
    int k1=0,k2=0;
    for(int i=1;i<=n;i++)
    {
    cin>>a[i];
    s[i]=s[i-1]+a[i];   
    }
    cin>>str;
    str=" "+str;
    for(int i=1;i<=n;i++)
    {
        if(str[i]=='L')l[++k1]=i;
        else r[++k2]=i;
    }
    reverse(r+1,r+k2+1);
    int ans=0;
    for(int i=1;i<=min(k1,k2);i++)
    {
        if(l[i]<r[i])//这里别粗心了
        {
            ans+=s[r[i]]-s[l[i]-1];
        }
    }
    cout<<ans<<endl;
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

分配猩猩

题型

贡献法 贪心

分析

计算每个网格位置在子正方形的出现次数，即为其观赏性贡献，然后贪心，将最高的猩猩分给贡献最大的网格位置。

代码

#include <bits/stdc++.h>
using namespace std;
using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
void solve() {
    int n, m, k;
    cin >> n >> m >> k;

    int w;
    cin >> w;

    vector<int> a(w);
    for (int i = 0; i < w; i++) {
        cin >> a[i];
    }

    vector<i64> f;
    f.reserve(n * m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            i64 res = 1LL * (min(i, n - k) - max(0, i - k + 1) + 1) * (min(j, m - k) - max(0, j - k + 1) + 1);
            f.push_back(res);
        }
    }

    i64 ans = 0;
    sort(f.begin(), f.end(), greater<i64>());
    sort(a.begin(), a.end(), greater<int>());
    for (int i = 0; i < w; i++) {
        ans += a[i] * f[i];
    }
    cout<<ans<< "\n";
}
int main() 
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);    
    int t;
    cin>>t;
    while(t--)solve();

    return 0;
}