AcWing 周赛14

区间选数

题意

给出两个区间，要求分别输出两个不同的数，且第一个数属于第一个区间，第二个数属于第二个区间

题解

判断区间端点大小输出

c++

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int T; cin >> T;
    while(T--)
    {
        int l1, r1, l2, r2; cin >> l1 >> r1 >> l2 >> r2;
        if(r2 > r1)cout << l1 << " " << r2 << endl;
        else cout<< r1 << " " << l2 << endl;
    }
    return 0;
}

python

T = int(input())

for _ in range(T):
    l1, r1, l2, r2 = map(int, input().split())
    if(r1 > r2):
        print(r1, l2)
    else:
        print(l1, r2)

食堂排队

题意

有 \(n\) 个人，每个人都有到达时间 \(l\) 和最大忍耐时间 \(r\)，打饭时间为 \(1\) 分钟，如果到达最大忍耐时间还没有到达离开，询问每个人的那个时间打饭

题解

模拟

c++

#include<bits/stdc++.h>
#define PII pair<int, int>
using namespace std;

int main()
{
    int T; cin >> T;
    while(T--)
    {
        int n; cin >> n;
        vector<PII> v;
        int mx = 0;
        for(int i = 1; i <= n; i++)
        {
            int l, r; cin >> l >> r;
            v.push_back({l ,r}); mx = max(l + r, mx);
        }
        int p = 0;
        for(int i = 1; i <= mx; i++)
        {
            if(i < v[p].first) continue;
            if(i >= v[p].first &&  v[p].second < i) 
            {
                while(p < n && i >= v[p].first &&  v[p].second < i) 
                {
                    cout << 0 <<" "; p ++;
                }
            }
            if(i < v[p].first) continue;
            if(p < n && i >= v[p].first) cout << i << " ";
            p++;
            if(p >= n) break;
        }
        cout << endl;
    }
    return 0;
}

python

import collections
import heapq

T = int(input())
for _ in range(T):
    n = int(input())
    l = list()
    mx = 0
    for i in range(n):
        tmp = list(map(int, input().split()))
        mx = max(tmp[0] + tmp[1], mx)
        l.append(tmp)
    p = 0
    for i in range(1, mx + 1):
        if(i < l[p][0]):
            continue
        if i >= l[p][0] and i > l[p][1]:
            while p < n and i > l[p][0] and i > l[p][1]:
                print(0, end = ' ')
                p += 1
        if p >= n:
            break
        if i < l[p][0]:
            continue
        if i >= l[p][0]:
            print(i, end = ' ')
        p += 1
        if p >= n:
            break
    print()
            

寻找字符串

题意

给一个字符串， 要求找出一个子串，要求子串即使前缀也是后缀并且在中间出现过

题解

考察 KMP 中 next 数组的理解

ne[i] : 表示 [0...i] 中最长相同前后缀的长度，而次长串表示 i = ne[i]

至此，我们只要求出 next 数组，并标记长度遍历即可

c++

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 10;
char s[maxn];
int ne[maxn];
int st[maxn];
int main()
{
    int T; cin >> T;
    while(T--)
    {
        cin >> (s + 1);
        int n = strlen(s + 1);
        for(int i = 2, j = 0; i <= n; i ++)
        {
            while(j && s[i] != s[j + 1]) j = ne[j];
            if(s[i] == s[j + 1]) j++;
            ne[i] = j;
        }
        for(int i = 1; i <= n; i++) st[i] = false;
        for(int i = 1; i < n ; i++) st[ne[i]] = true;
        int res = 0;
        for(int i = ne[n]; i != 0; i = ne[i])
        {
            if(st[i])
            {
                res = i; break;
            }
        }
        if(res == 0) cout << "not exist" << endl;
        else 
        {
            s[res + 1] = 0;
            cout << (s + 1) << endl;
        }
    }
    return 0;
}

python

T = int(input())
for _ in range(T):
    s = input()
    s  = '#' + s
    n = len(s)
    ne, st = [0] * (n + 1), [False] * (n + 1)
    j = 0
    for i in range(2, n , 1):
        while j and s[i] != s[j + 1]:
            j = ne[j]
        if s[i] == s[j + 1]:
            j += 1
        ne[i] = j
    for i in range(1, n - 1, 1):
        st[ne[i]] = True
    i = ne[n - 1]
    flag = 0
    while i:
        if st[i] == True:
            print(s[1:i + 1])
            flag = 1
            break
        i = ne[i]
    if flag == 0:
        print("not exist")