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\) 分鐘，如果到達最大忍耐時間還沒有到達離開，詢問每個人的那個時間打飯

模拟

#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;
}
           

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]

#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;
}
           

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")