90分,WA了第八点,求助
查看原帖
90分,WA了第八点,求助
1185696
afreshmanofclanguage楼主2024/7/28 19:52
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
const int M = 1e5 + 5;
int n, m; int cnt = N, len = N;
int vis[N];
string wor[N]; // words
string art[M]; // articles
typedef pair<int, int> PII;
PII ans;
int word_search(string s)
{
    int l = 0; int r = n + 1; int mid;
    while (l + 1 != r)
    {
        mid = (l + r) >> 1;
        if (s == wor[mid]) // isblue
            return mid;
        else if (s < wor[mid])
            r = mid;
        else
            l = mid;
    }
    return mid;
} // 在wor中找到这个单词,并且返回它在wor中的下标(排过序的)
bool word_observe(int x)
{
    int counts = 0;
    for (int i = 1; i <= n; i++)
        if (vis[i]) counts++;
    return x == counts;
} // 检查当前的已经读到至少一次的单词数目是否还是x


bool check(int x) // x == mid,要背单词数
{
    memset(vis, 0, N * 4); //重置vis数组
    int i = 1, j = 1;
    for (; i <= m; i++)
    {
        int flag = 0;
        vis[word_search(art[i])]++;
        while (j <= i && word_observe(x))
        {
            flag = 1;
            vis[word_search(art[j])]--;
            j++;
        } // 双指针
        if (flag)
        {
            if(x > ans.first) // 若x可以变大
            {
                ans.first = x;
                ans.second = i - j + 2;
            }
            else if(x == ans.first && ans.second > (i - j + 2))
             // 若x不变化,但是长度可以削减
                ans.second = (i - j + 2);
            else continue ;// 否则什么都不做
        }
    }
    if (i == n && j == 1) return 0; // 找不齐 x 个单词
    return 1;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        cin >> wor[i];
    sort(wor + 1, wor + 1 + n); // 字典序排列一下
    scanf("%d", &m);
    for (int i = 1; i <= m; i++)
        cin >> art[i];
    int l = 0; int r = n + 1; int mid;
    while (l + 1 != r)
    {
        mid = (l + r) >> 1;
        if (check(mid)) // isblue
            l = mid;
        else
            r = mid;
    }
    printf("%d\n%d", ans.first, ans.second);
    //不包含时的特判
    return 0;
} // P1381 luogu
2024/7/28 19:52
加载中...