UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#199788#546. 分组GS12810076ms1880kbC++112.1kb2023-12-21 09:50:062023-12-21 12:02:18

answer

#include<bits/stdc++.h>
#define lowbit(x) x&(-x)
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double LD;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;

const ll MOD=1e9+7;
const ll INF=0x3f3f3f3f3f3f3f3f;
const LD eps=1e-14;

inline ll read()
{
	ll ans=0, f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') ans=ans*10+c-'0', c=getchar();
	return ans*f;
}

const int N=5050;

ll n;
vector<string> ve;
map<string,bool> mp;

bool vis[N];

void solve()
{
	n=read();
	string s;
	for(int i=1;i<=n;i++)
	{
		cin>>s;
		reverse(s.begin(),s.end());
		ve.push_back(s);
	}
	
	sort(ve.begin(),ve.end());
	
//	for(int i=0;i<n;i++) cout<<ve[i]<<endl;
	
	s=""; mp[""]=1;
	priority_queue<pair<int,pii>, vector<pair<int,pii> >, less<pair<int,pii> > > pr;
	
	for(int i=0;i<n-1;i++)
	{
		s="";
		for(int k=0;k<min(ve[i].size(),ve[i+1].size());k++)
		{
			if(ve[i][k]==ve[i+1][k])  s+=ve[i][k];
			else break;
		}
		pr.push(make_pair(s.size(),make_pair(i,i+1)));
	}
	
	set<int> se;
	for(int i=0;i<n;i++) se.insert(i);
	se.insert(-1), se.insert(114514);
	
	int a,b;
	int c,d;
	int ans=0;
	while(!pr.empty())
	{
		a=pr.top().second.first;
		b=pr.top().second.second;
		pr.pop();
		if(vis[a]||vis[b]) continue;
		
		s="";
		for(int k=0;k<min(ve[a].size(),ve[b].size());k++)
		{
			if(ve[a][k]==ve[b][k])  s+=ve[a][k];
			else break;
		}
		
		bool flag=0;
		for(int i=s.size();i;i--)
		{
			if(mp[s.substr(0,i)]==0)
			{
				flag=1;
				ans+=2;
				vis[a]=vis[b]=1;
				c=*(--se.find(a)), d=*(++se.find(b));
				se.erase(a), se.erase(b);
				mp[s.substr(0,i)]=1;
				
				break;
			}
		}
		
		if(flag)
		{
			if(c!=-1&&d!=114514)
			{
				s="";
				for(int k=0;k<min(ve[c].size(),ve[d].size());k++)
				{
					if(ve[c][k]==ve[d][k])  s+=ve[c][k];
					else break;
				}
				pr.push(make_pair(s.size(),make_pair(c,d)));
			}
		}
	}
	
	cout<<ans;
	
	return ;
}

int main()
{
//	freopen("ex_data4.in","r",stdin);
	solve();
	
	return 0;
}

详细

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 20
Accepted

Test #1:

score: 20
Accepted
time: 0ms
memory: 1256kb

input:

2
CAAAECCCEDEECBEAE
EDECADAAADCACADE

output:

2

result:

ok "2"

Test #2:

score: 0
Accepted
time: 0ms
memory: 1252kb

input:

1
LKIEIDLCKFLCGCKJIJBACED

output:

0

result:

ok "0"

Test #3:

score: 0
Accepted
time: 1ms
memory: 1244kb

input:

1
N

output:

0

result:

ok "0"

Test #4:

score: 0
Accepted
time: 0ms
memory: 1248kb

input:

1
PPNOMCGAPHHJDJ

output:

0

result:

ok "0"

Test #5:

score: 0
Accepted
time: 0ms
memory: 1248kb

input:

1
BBK

output:

0

result:

ok "0"

Test #6:

score: 0
Accepted
time: 0ms
memory: 1248kb

input:

1
CBFBBFAABDEFC

output:

0

result:

ok "0"

Test #7:

score: 0
Accepted
time: 0ms
memory: 1256kb

input:

2
GIQHAOASGPJMQJKONKIHJRSHHTBTJANNGKMUPAKQAQILFN
FQJMJNBELCEQFDRTCGQGK

output:

0

result:

ok "0"

Test #8:

score: 0
Accepted
time: 0ms
memory: 1252kb

input:

1
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

output:

0

result:

ok "0"

Test #9:

score: 0
Accepted
time: 0ms
memory: 1248kb

input:

1
IFNNAAJOCCLECHIOCLHKFCGMHFH

output:

0

result:

ok "0"

Test #10:

score: 0
Accepted
time: 0ms
memory: 1248kb

input:

1
JJAAAGAHEGBFHCGAIFHGGACEDFCHCHJJCGDFJGEDEICDDAHAI

output:

0

result:

ok "0"

Subtask #2:

score: 20
Accepted

Test #11:

score: 20
Accepted
time: 0ms
memory: 1256kb

input:

4
CAAAECCCEDEECBEAE
EDECADAAADCACADE
ECABDEBBBEB
EACCADEEEDDECE

output:

2

result:

ok "2"

Test #12:

score: 0
Accepted
time: 0ms
memory: 1260kb

input:

3
JGAPJCOFFIAKD
JCOFBQDAMJLHNCMILCCGQLKBKBAIDKDHCNCBNLFP
ELJIKANDOKFMIDAPCNOIENEFLMOC

output:

0

result:

ok "0"

Test #13:

score: 0
Accepted
time: 0ms
memory: 1260kb

input:

2
BAACAD
ECECDBEDEBEDEBABACADAABADCEBECBABABBAEDBECBBBA

output:

0

result:

ok "0"

Test #14:

score: 0
Accepted
time: 0ms
memory: 1260kb

input:

2
TULORMUJFFQNPSJICFCHUNFRUCTNILJGTOHQB
CCNSDCCRBFLRSTDBHKUQOUHMPROGQJIABDCSESDAKAIHFBHPI

output:

0

result:

ok "0"

Test #15:

score: 0
Accepted
time: 0ms
memory: 1260kb

input:

6
CBICGFABIBDBEEHFFDIFFBCAFBAGEIDAGHFAEDE
GBAHICCGC
IHGIEBCCFDDEBEECCEEBHGDHCDDGECCBFF
DGBFGBEBHGEGI...

output:

2

result:

ok "2"

Test #16:

score: 0
Accepted
time: 0ms
memory: 1256kb

input:

5
HLLBAFBCGGJFJFIIDDDACCCDJHKI
FICLEIJHLHJBGBIJEEF
CHICKEHBBKLEKLEKBIJIJAICGIADHGKABCI
KHCIDIILHJFLG...

output:

2

result:

ok "2"

Test #17:

score: 0
Accepted
time: 0ms
memory: 1256kb

input:

4
WIUGWACETCIGKCNSFY
GOFVBP
XLXFBUXPQ
HLGAURGVZXNJMSRYQQYWERNV

output:

0

result:

ok "0"

Test #18:

score: 0
Accepted
time: 0ms
memory: 1256kb

input:

4
G
CAGBFBIEAGCGIAHHEIFCIAFBAADBCEIHGIACDAAGB
FFIECF
AFHCCCFEHBGF

output:

2

result:

ok "2"

Test #19:

score: 0
Accepted
time: 0ms
memory: 1260kb

input:

6
BFJAMCKLHEIMLDAGCFACALBDHIGKJGLMGMHACJCHBLJCAJ
KIHLGHFBHKLDKAACLKLCJBLEBAEBJMKDBFFKLKLD
CHABBIMHFF...

output:

2

result:

ok "2"

Test #20:

score: 0
Accepted
time: 0ms
memory: 1260kb

input:

5
MHBIEBHLABHCGBBGJMCLAJMKFEMJGGE
NNHONNAMMJEEMJIINNDGHHEJGNNGKJJDJNBJADBB
DFAMKCEDNNMLFNDNDGLLJHCCF...

output:

0

result:

ok "0"

Subtask #3:

score: 20
Accepted

Test #21:

score: 20
Accepted
time: 1ms
memory: 1260kb

input:

6
CAAAECCCEDEECBEAE
EDECADAAADCACADE
ECABDEBBBEB
EACCADEEEDDECE
ACDCDDCEABC
CBBEECBBECEDDCDCDDCCCCDD...

output:

2

result:

ok "2"

Test #22:

score: 0
Accepted
time: 0ms
memory: 1252kb

input:

1
APBPEFENOQJCAKNHQHM

output:

0

result:

ok "0"

Test #23:

score: 0
Accepted
time: 0ms
memory: 1248kb

input:

1
VHJFSVEKVBULFQURHMJVNTQRCWNXPLNIJEGWA

output:

0

result:

ok "0"

Test #24:

score: 0
Accepted
time: 0ms
memory: 1248kb

input:

1
EDDIIBFEGBRLOEORKLLQOPOFRHMENCR

output:

0

result:

ok "0"

Test #25:

score: 0
Accepted
time: 0ms
memory: 1260kb

input:

2
GIDGHKFHCJACDCHFBJIFEDEBCIDABJGIJ
AAAGAHEGBFHCGAIFHGGACEDFCHCH

output:

0

result:

ok "0"

Test #26:

score: 0
Accepted
time: 0ms
memory: 1256kb

input:

5
DFAEADDBAFECEBDFFEECBFFACD
FEABBEEFFAFCFBFACEDDECDDAECDBDBEDEDBCCFDCDFEACEBF
FDAEBEEFFEBEEDAECDAAE...

output:

2

result:

ok "2"

Test #27:

score: 0
Accepted
time: 0ms
memory: 1260kb

input:

8
LBAFBCGGJFJFII
DDACCCDJHKIIFICLEIJHLH
BGBIJEEFACHICKEHBBKLEKLEKBIJIJAICGIADHGKABCIFKHCID
ILHJFLGFJ...

output:

6

result:

ok "6"

Test #28:

score: 0
Accepted
time: 0ms
memory: 1256kb

input:

5
RPCKPGCJPKOKIEJPCGRAQQERFLIA
BAADKCNRQPRALDJA
BFFFIELFFAOQLLCFNQBGFFKHLGOIDQ
JDLKIEOLBCNBMNERLEQKH...

output:

2

result:

ok "2"

Test #29:

score: 0
Accepted
time: 0ms
memory: 1260kb

input:

3
DIDKCFLIAI
FLDJJGJHGBBABKJAADJGGKFGAECLACFKJDKFJELIDDHHFJA
CIJIJBIFJKJIDBJGLIAJHHIFHJHKLAFEEIAGKEC...

output:

0

result:

ok "0"

Test #30:

score: 0
Accepted
time: 0ms
memory: 1256kb

input:

6
CGB
GJMCLAJMKFEMJGGEENNHONNAMMJ
EMJIINNDGHHEJGNNGKJJDJNBJADBBIDFAMKCEDNNMLFND
DGLLJHCCFFMJNJHFALKC...

output:

0

result:

ok "0"

Subtask #4:

score: 20
Accepted

Test #31:

score: 20
Accepted
time: 0ms
memory: 1264kb

input:

56
CAAAECCCEDEECBEAE
EDECADAAADCACADE
ECABDEBBBEB
EACCADEEEDDECE
ACDCDDCEABC
CBBEECBBECEDDCDCDDCCCCD...

output:

48

result:

ok "48"

Test #32:

score: 0
Accepted
time: 0ms
memory: 1260kb

input:

9
ARPCJLNGNIFQKEJKCEILOLRBCKNNMMOQMPDMA
QEOKINGQRMBGFQLECCAGPPJRPROLKJCCQEC
NBQFHLLIDLHHB
NGIBEQIMDP...

output:

2

result:

ok "2"

Test #33:

score: 0
Accepted
time: 0ms
memory: 1268kb

input:

84
AGCEDECJFKHBFGKKIDJJIEHCIFDDCCDGDDB
GG
DDAFCEHBECJEHCJHHBHJFHBABGIFJKIICBDFFDIC
ECFKIDBKECKJDCCHK...

output:

62

result:

ok "62"

Test #34:

score: 0
Accepted
time: 0ms
memory: 1260kb

input:

32
GEDFEBK
EIBHHKFDCEKGIBFGAJG
EEHDLAHKDDLFIH
IIFIGIGFIBFBIFHJCCEFCCBFIC
HGCLKCGEFCBJGCFJIJEBCICCJBI...

output:

22

result:

ok "22"

Test #35:

score: 0
Accepted
time: 0ms
memory: 1260kb

input:

41
BCABCBAACCBCAAAABBBACACBAAAACCCCCABA
BBCCABACCCCBACBCCACBBA
BCBCABCCACAABABB
AAABBCAABAA
ABBACBCA...

output:

40

result:

ok "40"

Test #36:

score: 0
Accepted
time: 0ms
memory: 1268kb

input:

77
DJDNFJAPAHPBNBMCOID
KAMMEMOQDOCNKPKALGLFFGBAOOKPPLB
ICLHOPDBMFHAQJ
BKLPNBELLFBJPCMAHKJLCMJHPJ
NDD...

output:

48

result:

ok "48"

Test #37:

score: 0
Accepted
time: 0ms
memory: 1260kb

input:

2
GAGICDBFHGFFEDAIHBHHHEFBBIFFCFID
GDFCIIIACFFICGFIIHIIFCCCEDHCDFGCBCBCHAGGGFDEECHCCH

output:

0

result:

ok "0"

Test #38:

score: 0
Accepted
time: 0ms
memory: 1264kb

input:

57
BGAGCBFCGAAGECDBDBGGBBDGFFBEFDCAADFEGEECDHHD
CHBBGEHABAE
ECEEGDGGAEHAHGFGGBFBBGGGDF
FAHGDEFAACHBC...

output:

50

result:

ok "50"

Test #39:

score: 0
Accepted
time: 0ms
memory: 1272kb

input:

91
DFLFVUFNVTOHTJGVNRMJUJSOUUPPRMOTAISQQLAHNOF
AMNRERBNBERENSAEJAEPEINHDP
NJTMFUMFJSKETBNTKFEAQATACV...

output:

54

result:

ok "54"

Test #40:

score: 0
Accepted
time: 2ms
memory: 1260kb

input:

5
ADDAADDBDBACCADDBDDBAADDACDDBAD
CADACACBCADCBCDADBBAC
ACAC
CDDCCACACADBCCBDADCADBADBADCCABCDBABACD...

output:

4

result:

ok "4"

Subtask #5:

score: 20
Accepted

Test #41:

score: 20
Accepted
time: 0ms
memory: 1568kb

input:

1956
CAAAECCCEDEECBEAE
EDECADAAADCACADE
ECABDEBBBEB
EACCADEEEDDECE
ACDCDDCEABC
CBBEECBBECEDDCDCDDCCC...

output:

1726

result:

ok "1726"

Test #42:

score: 0
Accepted
time: 11ms
memory: 1864kb

input:

3829
FBCBCCCEEDDBDFDEEFEFDBCBABFDEAA
ACDDCFDFFABEDEAFCFDBBAEEAAAADAACFCBCFABCAFCCFCDAEE
EAFDADDFACEA...

output:

3212

result:

ok "3212"

Test #43:

score: 0
Accepted
time: 4ms
memory: 1408kb

input:

996
LNNEEDH
EBHLBHBBIHHMLFOJEHCMDCFOAIEB
ELHBAKHKILGGCALAKN
LCMF
FHFANKHDG
JELGLABHMABFBHHALHOCJOBHE...

output:

656

result:

ok "656"

Test #44:

score: 0
Accepted
time: 13ms
memory: 1860kb

input:

4114
AADBADBECCDAACBB
CECDBDECDCEAEBDEDCADDDACCCDBE
CCADABECBEEEBEACCADCCEEDAAEEDAEEDCEDCDEEDDCBEDAD...

output:

3580

result:

ok "3580"

Test #45:

score: 0
Accepted
time: 5ms
memory: 1624kb

input:

2398
NECOONFCAGOELGFMLOJIDEEMKBJKBKKIAGBKECAE
OGNGNLOGAGOHJNHEJPMCBPQB
IHKNFIILIAIFGGJ
OIBACCOKEKKJM...

output:

1434

result:

ok "1434"

Test #46:

score: 0
Accepted
time: 7ms
memory: 1520kb

input:

1734
UAGA
VMSTUQLKKND
TUTGJNEBBFTOSOGUKOACMGJPIPJIDMKJRNEGMDHVPSWLFE
NPCCBOTVGIIBCTKKQIDWOTWHCVOGVOE...

output:

1072

result:

ok "1072"

Test #47:

score: 0
Accepted
time: 15ms
memory: 1880kb

input:

3958
BACBABECBDFEBAAACFFCDBEFFAFBEEFDFFCBFBFBFBCD
D
DDABEBCDBEFDAECDACFD
ACABCBAADEFCDDFAEECCD
EDDDA...

output:

3358

result:

ok "3358"

Test #48:

score: 0
Accepted
time: 7ms
memory: 1428kb

input:

1249
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAA...

output:

100

result:

ok "100"

Test #49:

score: 0
Accepted
time: 8ms
memory: 1572kb

input:

2081
JSSPPJFAAAGRBOMRVDFIILDQUSIHEHC
QBA
QLLRGNR
SBHJBUVFRCGR
JNMUDKPFCESRAJQNTDATDCNHTAFTAKIICPB
VF...

output:

1242

result:

ok "1242"

Test #50:

score: 0
Accepted
time: 2ms
memory: 1472kb

input:

1376
BDIHBNAFNKGCODANIONCOJCKAEHAMJDEIGLLHIMHHMADDGL
OMEI
MABFG
NC
MOHJMJGOJIKHLHELKGLFEOACOB
DDCAEB...

output:

852

result:

ok "852"

Extra Test:

score: 0
Extra Test Passed