每日一题6.4

495684945

郑州ccpc邀请赛第七题

E题

Fengyj

赛后10分钟秒了

[C++] 纯文本查看 复制代码

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
const int N = 2e5 + 10;
void solve()
{
    int n;
    cin >> n;
    vector<string> a(2 * n);
    for (int i = 0; i < 2 * n; i++)
    {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
  
    int idx = 0;
    vector<vector<int>> son(2 * N + 1, vector<int>(26));
    int cnt[N]{};
    auto insert = [&](string s) -> void
    {
        int p = 0;
        for (auto c : s)
        {
            //  cerr << c << endl;
            if (!son[p][c - 'a'])
                son[p][c - 'a'] = ++idx;
            p = son[p][c - 'a'];
            cnt[p]++;
            // cerr << "p:" << p << endl;
        }
    };
    for (int i = 0; i < 2 * n; i += 2)
    {
        insert(a[i]);
    }

    i64 ans = 0;

    auto ask = [&](string s) -> int
    {
        int res = 0;
        int p = 0;
        for (auto c : s)
        {
            if (son[p][c - 'a'] != 0)
            {
                p = son[p][c - 'a'];
                res += cnt[p];
            }
            else
            {
                return res;
            }
        }
        return res;
    };

    for (int i = 1; i < 2 * n; i += 2)
    {
        ans += ask(a[i]);
    }
    cout << ans << '\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

495684945

[C++] 纯文本查看 复制代码

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

void solve(){
	int n,idx=0;
	cin>>n;
	n*=2;
	vector<int>cnt(200010);
	vector<string>s(n+10);
	for(int i=1;i<=n;i++)cin>>s[i];
	vector tr(200010,vector<int>(26));
	auto insert=[&](string str){
		int p=0,t;
		for(int i=0;i<str.size();i++){
			t=str[i]-'a';
			if(!tr[p][t])tr[p][t]=++idx;
			p=tr[p][t];
			cnt[p]++;
		}
	};
	auto query=[&](string str){
		int p=0,t,res=0;
		for(int i=0;i<str.size();i++){
			t=str[i]-'a';
			if(!tr[p][t])return res;
			p=tr[p][t];
			res+=cnt[p];
		}
		return res;
	};
	sort(s.begin()+1,s.begin()+1+n);
	for(int i=1;i<=n;i+=2){
		insert(s[i]);
	}
	int ans=0;
	for(int i=2;i<=n;i+=2){
		ans+=query(s[i]);
	}
	cout<<ans<<endl;
}

signed main(){
	int t=1;ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//	cin>>t;
	while(t--)solve();
	return 0;
}