2017 ACM/ICPC Asia Regional Qingdao Online(SDKD 2024 Summer Training Contest J2)

Seii's Blog / 2024-09-18 / 原文

C - The Dominator of Strings

题意

给定n个串，问是否有一个串包含其他所有串，有就输出这个串。

思路

如果有解，答案必定是最长串，一一比较即可。(没想到.find()就能过🤡)

代码一 .find()

点击查看代码

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

#define int long long

inline bool cmp(string a, string b)
{
    return a.length() > b.length();
}

void solve()
{
    int n;
    cin >> n;
    vector<string> v(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }
    sort(v.begin(), v.end(), cmp); 
    for (int i = 1; i < n; i++)
    {
        if (v[0].find(v[i]) == string::npos) 
        {
            cout << "No" << endl;
            return;
        }
    }
    cout << v[0] << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T;
    cin >> T;
    while (T--)
    {
        solve();
    }

    return 0;
}

代码二 KMP

点击查看代码

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

#define int long long

const int mxn = 1e6 + 5;

int kmp_next[mxn]; 

void getNext(string s) 
{
    int i = 0, j = -1;
    kmp_next[0] = -1;
    while (i < s.length())
    {
        while (j != -1 && s[i] != s[j])
        {
            j = kmp_next[j];
        }
        if (s[++i] == s[++j])
        {
            kmp_next[i] = kmp_next[j];
        }
        else
        {
            kmp_next[i] = j;
        }
    }
}

bool kmp(string a, string b) 
{
    int i = 0, j = 0;
    getNext(a);
    while (i < b.length())
    {
        while (j != -1 && b[i] != a[j])
        {
            j = kmp_next[j];
        }
        i++;
        j++;
        if (j >= a.length())
        {
            return true;
        }
    }
    return false;
}


void solve()
{
    int n;
    cin >> n;
    vector<string> v(n);
    int p = 0, maxn = -1;
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
        if ((int)v[i].size() > maxn)
        {
            maxn = v[i].length();
            p = i;
        }
    }
    for (int i = 0; i < n; i++)
    {
        if (i == p)
        {
            continue;
        }
        if (!kmp(v[i], v[p]))
        {
            cout << "No" << endl;
            return;
        }
    }
    cout << v[p] << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T;
    cin >> T;
    while (T--)
    {
        solve();
    }

    return 0;
}

H - Chinese Zodiac

题意

已知甲乙二人的属相(甲比乙年纪大)，求二者年龄最小差值。

思路

相等差12，其他相减即差值，但甲比乙大，所以再加12取余

代码

点击查看代码

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

string s[] = { "rat","ox", "tiger", "rabbit", "dragon", "snake", "horse", "sheep", "monkey", "rooster", "dog", "pig" };

void solve()
{
	string a, b;
	cin >> a >> b;
	if (a == b)
	{
		cout << 12 << endl;
		return;
	}
	int aa = 0, bb = 0;
	for (int i = 0; i < 12; i++)
	{
		if (a == s[i])
		{
			aa = i;
		}
		if (b == s[i])
		{
			bb = i;
		}
	}
	cout << (bb - aa + 12) % 12 << endl;
}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int T = 1;
	cin >> T;
	while (T--)
	{
		solve();
	}

	return 0;
}

K - A Cubic number and A Cubic Number

题意

给定质数$p$，问是否存在正整数a与b使得$a^3-b^3 = p$。

思路

立方差公式：$a^3-b^3 = (a-b)(a^2+ab+b^2)$，由于$p$是质数，因子只有$1$和它本身，显然$(a^2+ab+b^2)$不可能是$1$，故$a-b=1$，a和b相邻，数据不大直接枚举。

代码

点击查看代码

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


void solve()
{
	int p;
	cin >> p;
	for (int a = 1; a <= 1e6; a++) // p到1e12枚举到1e6就够
	{
		int b = a + 1;
		int t = a * a + a * b + b * b;
		if (t == p)
		{
			cout << "YES" << endl;
			return;
		}
	}
	cout << "NO" << endl;
}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int T = 1;
	cin >> T;
	while (T--)
	{
		solve();
	}

	return 0;
}