https://wiki.universitas.ro/index.php?action=history&feed=atom&title=3889_-_Cnt_Subsir_Max 2026-05-01T21:51:15Z Revision history for this page on the wiki MediaWiki 1.42.1 https://wiki.universitas.ro/index.php?title=3889_-_Cnt_Subsir_Max&diff=10041&oldid=prev 2024-06-03T17:24:43Z

<p>Pagină nouă: == Cerinţa == Felicia este interesată de subșirul maxim lexicografic al unui șir de caractere. Rețineți că un șir a este considerat mai mic în ordine lexicografică decât un șir b dacă a este prefix al lui b, sau dacă există o poziție i pentru care avem a[1] = b[1], ..., a[i − 1] = b[i − 1], și a[i] &lt; b[i]. Astfel, subșirul maxim lexicografic al unui șir de caractere este cel mai mare subșir, în ordinea lexicografică, al unui șir de caractere (de exe...</p> <p><b>New page</b></p><div>== Cerinţa ==<br /> Felicia este interesată de subșirul maxim lexicografic al unui șir de caractere. Rețineți că un șir a este considerat mai mic în ordine lexicografică decât un șir b dacă a este prefix al lui b, sau dacă există o poziție i pentru care avem a[1] = b[1], ..., a[i − 1] = b[i − 1], și a[i] &lt; b[i]. Astfel, subșirul maxim lexicografic al unui șir de caractere este cel mai mare subșir, în ordinea lexicografică, al unui șir de caractere (de exemplu zzxx pentru azbxazbxaax). Pentru un șir s de caractere vom nota cu m(s) subșirul maxim lexicografic al lui s, și cu v(s) = |m(s)| lungimea acestui subșir. Felicia vă dă un șir s format din caractere mici ale alfabetului englez. Considerați toate subsecvențele continue s&#039; ale lui s. Felicia vrea să calculați suma valorilor v(s&#039;) pentru toate subsecvențele posibile s&#039; amintite anterior.<br /> == Date de intrare ==<br /> Pe singura linie citită de la tastatură se va găsi șirul s.<br /> == Date de ieșire ==<br /> Să se afișeze suma cerută, modulo 109+7.<br /> == Restricţii şi precizări ==<br /> * 1≤N≤106<br /> == Subtask ==<br /> * N≤15<br /> == Subtask ==<br /> * N≤200<br /> == Subtask ==<br /> * N≤2000<br /> == Subtask ==<br /> * N≤5⋅104<br /> == Subtask ==<br /> * Fară restricții suplimentare.<br /> == Exemplul 1 ==<br /> ; Intrare<br /> <br /> cab<br /> ; Ieșire<br /> <br /> 8<br /> == Explicație ==<br /> Pentru primul exemplu, observăm că m(c) = c, m(a) = a, m(b) = b, m(ca) = ca, m(ab) = b, m(cab) = cb.<br /> Astfel, răspunsul este 1 + 1 + 1 + 2 + 1 + 2 = 8. <br /> &lt;br&gt;<br /> <br /> == Exemplu 2 ==<br /> ; Intrare<br /> <br /> felicia<br /> ; Ieșire<br /> <br /> 59<br /> <br /> <br /> <br /> == Rezolvare ==<br /> &lt;syntaxhighlight lang=&quot;python&quot; line&gt;<br /> MOD = 10**9 + 7<br /> <br /> def max_lexicographic(s):<br /> max_substring = s[0]<br /> for i in range(1, len(s)):<br /> if s[i] &gt;= max_substring[0]:<br /> max_substring = s[i] + max_substring<br /> else:<br /> max_substring += s[i]<br /> return max_substring<br /> <br /> def sum_of_max_substrings(s):<br /> total_sum = 0<br /> for i in range(len(s)):<br /> max_substring = max_lexicographic(s[i:])<br /> total_sum += len(max_substring)<br /> total_sum %= MOD<br /> return total_sum<br /> <br /> def main():<br /> s = input().strip()<br /> result = sum_of_max_substrings(s)<br /> print(result)<br /> <br /> if __name__ == &quot;__main__&quot;:<br /> main()<br /> <br /> &lt;/syntaxhighlight&gt;</div>

RebecaBud