首页 > 其他分享 >The 2022 ICPC Asia Hangzhou Regional Programming Contest K. Master of Both

The 2022 ICPC Asia Hangzhou Regional Programming Contest K. Master of Both

时间:2024-10-11 22:11:48浏览次数:7  
标签:Both cnt Contest int Regional 26 字符串 节点 字典

题目链接

题意:

给定 n 个字符串,然后给定 q 种字典序规则,在这q种字典序规则下求出这n个字符串的逆序对数量。

思路:

我们发现 q 很大,对于每一种排序规则都遍历一遍 n 个字符串去求逆序对的数量复杂度太高,所以考虑预处理。我们知道要判断两个字符串字典序的大小关系,只需要知道它们第一个不同的字母,而这样的对应关系最多只有 26$\times$26 种,于是我们不妨先把这些对应关系给处理出来,然后在每种字典序规则下统计逆序对的数量,这样的时间复杂度是 26 \(\times\) 26 \(\times\) q 的。
我们假设 cnt[a][b] 表示由字符对 (a,b) 影响的且 a 所在字符串编号小于 b 所在字符串编号的字符串对数量,那么如果在当前字典序规则下 a 的字典序大于 b 的字典序,那么 (a,b) 就会对答案贡献 cnt[a][b]。
接下来的问题就是 cnt[a][b] 如何计算,由于两个字符串比较,我们假设前 i-1 个字符都是相同的,从第 i 个字符串开始不同,我们可以建 tire 树,加入当前字符串的时候,将它的每一位都尝试去遍历一下其它的字母,我们可以知道在同一父亲节点的两个不同的子节点处,就是两个字符串判断出字典序大小的位置,而且我们按照题目所给顺序插入字符串,那么此前已经加入 trie 树的节点所在字符串的编号一定小于当前字符串,则 cnt[a][b] 可以在此处累加,同时将当前节点表示的字符串数量 +1 。
注意:有可能会出现字符串 abc 和字符串 abcd 比较字典序的情况,这里我们可以在每个字符串的后面都添加一个小于所有小写字母的字符,比如 'a'-1,这样就可以正常比较了。

由于本人太菜了,可能对字符串和 trie 树的理解还不太深刻,表达也不是特别清楚 QAQ,下面是AC代码~~

代码

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long 
const int N = 2e6 + 10;
int son[N][30],sum[N][30];
int cnt[1003];
int idx;
void insert(string s)
{
	int p=0;
	for(int i=0;i<s.size();i++)
	{
		int k=s[i]-'a'+1;
		if(!son[p][k])son[p][k]=++idx;
		for(int j=0;j<27;j++)cnt[(j+1)*27+k+1]+=sum[p][j];
		sum[p][k]++;
		p=son[p][k];
	}
}
void solve()
{
	int n,q;
	cin>>n>>q;
	for(int i=1;i<=n;i++)
	{
		string s;
		cin>>s;
		char c='a'-1;
		s+=c;
		insert(s);
	}
	int pos[30];
	while(q--)
	{
		string s;
		cin>>s;
		char c='a'-1;
		s=c+s;
		int ans=0;
		for(int i=0;i<27;i++)pos[s[i]-'a'+1]=i;
		for(int i=0;i<27;i++)
		{
			for(int j=0;j<27;j++)
			{
				if(pos[i]>pos[j])
				{
					ans+=cnt[(i+1)*27+j+1];
				}
			}
		}
		cout<<ans<<endl;
	}
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T=1;
	// cin>>T;
	while(T--)
	{
		solve();
	}
	return 0;
}

标签:Both,cnt,Contest,int,Regional,26,字符串,节点,字典
From: https://www.cnblogs.com/Charlie983/p/18459381

相关文章

  • AtCoder Beginner Contest 373 (A-F)
    AtCoderBeginnerContest373(A-F)比赛链接A-September#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;voidShowball(){intans=0;for(inti=1;i<=12;i++){strings;cin>>s;ans+=((int)s.si......
  • The 2021 ICPC Asia Shenyang Regional Contest
    目录写在前面E签到F签到JBFSB带权并查集H图论I数学L树形DP,容斥M字符串,离线,单调性G贪心写在最后写在前面比赛地址:https://codeforces.com/gym/103427。以下按个人向难度排序。唉唉国庆vp三场唯一打的还像人的一场,最后手里还有两道题在写可惜都没出来呃呃。被树上背......
  • The 2023 ICPC Asia Hangzhou Regional Contest (The 2nd Universal Cup. Stage 22: H
    The2023ICPCAsiaHangzhouRegionalContest(The2ndUniversalCup.Stage22:Hangzhou)M.V-Diagram题意:给定一个“v图”,求平均值最大的子"v图"思路:原图的最低点以及左右两个点必须取,如何先取满左边或者右边在贪心即可voidsolve(){lln;cin>>n;vect......
  • AtCoder Beginner Contest 374(D-E)
    A-C:惯例是宝宝题,会打暴力就能过哈D:其实也是暴力dfs,有一个double打错成int(我是猪鼻),卡了我很久#include<bits/stdc++.h>usingnamespacestd;constintmaxn=1e3+10,eps=1e-7;intn,s,t;boolvis[10];doublesum=1e8;structNode{ doublex,y,x1,y1;}a[maxn];doub......
  • キーエンスプログラミングコンテスト2024(AtCoder Beginner Contest 374)
    A.Takahashisan2判断一个字符串是否以san结尾usingnamespacereader;intmain(){strings;cin>>s;if(s[s.length()-1]=='n'ands[s.length()-2]=='a'ands[s.length()-3]=='s'){cout<<"Yes";......
  • AtCoder Beginner Contest 355
    ABC355A-WhoAtetheCake?题目传送门代码(签到题)#include<cstdio>#include<cctype>#include<cstring>#include<algorithm>usingnamespacestd;intiut(){intans=0,f=1;charc=getchar();while(!isdigit(c))f=(c=='-'......
  • AtCoder Beginner Contest 373
    ABC373A-September题目传送门代码(签到题)#include<cstdio>#include<cstring>usingnamespacestd;chars[1111];intans;intmain(){for(inti=1;i<=12;++i){scanf("%s",s+1);if(strlen(s+1)==i)++ans;}pr......
  • The 2020 ICPC Asia Shenyang Regional Programming Contest Northeastern University
    The2020ICPCAsiaShenyangRegionalProgrammingContestNortheasternUniversity(SMU2024ICPC网络赛选拔赛2)D.JourneytoUn'Goro思路队友写得,没看。代码#include<bits/stdc++.h>usingnamespacestd;typedeflonglongintll;#defineintlonglong#defineP......
  • AtCoder Beginner Contest 374
    ABC374A-Takahashisan2题目传送门代码(签到题)#include<cstdio>#include<cctype>#include<cstring>#include<cmath>#include<queue>usingnamespacestd;intiut(){ intans=0,f=1;charc=getchar(); while(!isdigit(c))f=(c==&......
  • The 10th Shandong Provincial Collegiate Programming Contest
    A-Sekiro题意初始有\(n\)个金币,死了\(m\)次,死一次\(n=\lceil\fracn2\rceil\)。求最后的金币数。思路模拟。代码点击查看代码#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongvoidsolve(){ intn,m; cin>>n>>m; while(m--......