Προγραμματισμός
Για GRCPC, SEERC και ICPC: οι αλγόριθμοι που ζητούνται ξανά και ξανά, με κώδικα C++ που έχει ελεγχθεί, και προβλήματα για να τους γράψεις μόνος σου.
Βασικές τεχνικές
- Αθροίσματα προθεμάτων
Άθροισμα οποιουδήποτε διαστήματος σε , μετά από ένα πέρασμα . Και το αντίστροφο: πολλές προσθέσεις σε διαστήματα με τον πίνακα διαφορών.
- Δυαδική αναζήτηση στην απάντηση
Όταν το «γίνεται με ;» είναι μονότονο ως προς , βρίσκεις το μικρότερο που γίνεται σε ελέγχους.
- Μέγιστη αύξουσα υπακολουθία
Το μήκος της σε , κρατώντας για κάθε μήκος το μικρότερο δυνατό τελευταίο στοιχείο.
Δομές δεδομένων
- Ένωση ξένων συνόλων (DSU)
Ενώνεις σύνολα και ρωτάς αν δύο στοιχεία είναι στο ίδιο, σε σχεδόν σταθερό χρόνο ανά πράξη.
- Δέντρο Fenwick
Αλλαγή ενός στοιχείου και άθροισμα προθέματος, και τα δύο σε , με έναν πίνακα και δύο βρόχους.
- Δέντρο διαστημάτων (segment tree)
Ερωτήματα σε διαστήματα για οποιαδήποτε προσεταιριστική πράξη, με αλλαγές σημείων ή, με lazy propagation, ολόκληρων διαστημάτων. ανά πράξη.
- Sparse table
Ελάχιστο σε διάστημα στατικού πίνακα σε , μετά από προεπεξεργασία .
Γράφοι και δέντρα
- BFS και 0-1 BFS
Συντομότερες αποστάσεις σε γράφο χωρίς βάρη σε . Με βάρη μόνο 0 και 1, το ίδιο με μια ουρά δύο άκρων.
- Dijkstra
Συντομότερες διαδρομές από μία κορυφή με μη αρνητικά βάρη, σε .
- Τοπολογική ταξινόμηση
Σειρά των κορυφών ενός DAG ώστε κάθε ακμή να πηγαίνει προς τα εμπρός, σε . Πάνω της τρέχει κάθε DP σε DAG.
- Ισχυρά συνεκτικές συνιστώσες
Ομαδοποίηση των κορυφών ενός κατευθυνόμενου γράφου σε συνιστώσες όπου όλοι φτάνουν σε όλους, με δύο DFS, σε . Από εκεί και το 2-SAT.
- Ελάχιστο συνδετικό δέντρο (Kruskal)
Ταξινομείς τις ακμές κατά βάρος και κρατάς όσες ενώνουν δύο διαφορετικές συνιστώσες. , με DSU.
- Ελάχιστος κοινός πρόγονος (binary lifting)
Ο -οστός πρόγονος κάθε κορυφής σε πίνακα. Με αυτόν, -οστός πρόγονος, LCA και απόσταση σε δέντρο, σε το καθένα.
- Μέγιστη ροή (Dinic)
Η μέγιστη ροή από το στο και, από το τελευταίο BFS, μια ελάχιστη τομή. Πάνω της στηρίζονται ταίριασμα σε διμερή γράφο και ξένες διαδρομές.
Συμβολοσειρές
- Συνάρτηση προθέματος (KMP)
Για κάθε θέση, το μακρύτερο γνήσιο πρόθεμα που είναι και επίθεμα. Δίνει αναζήτηση μοτίβου σε και τις «περιόδους» μιας λέξης.
- Z-function
Για κάθε θέση , πόσοι χαρακτήρες από το συμπίπτουν με την αρχή της λέξης. Σε , με ένα «παράθυρο» που ξέρουμε ήδη.
- Hashing συμβολοσειρών
Σύγκριση δύο οποιωνδήποτε υπολέξεων σε , μετά από προεπεξεργασία . Πιθανοτικό, με modulo και τυχαία βάση.
Μαθηματικά
- Αριθμητική modulo και συνδυαστική
Γρήγορη ύψωση σε δύναμη, αντίστροφος με το μικρό θεώρημα του Fermat, και σε μετά από προεπεξεργασία .
- Γραμμικό κόσκινο
Οι πρώτοι μέχρι το και ο μικρότερος πρώτος διαιρέτης κάθε αριθμού σε . Μετά, παραγοντοποίηση σε .
Πώς δουλεύεις
Διάβασε την ιδέα, κλείσε τη σελίδα και γράψε τον αλγόριθμο από την αρχή. Υπόβαλε στο CSES. Τον κώδικα της σελίδας τον κοιτάς μόνο για να συγκρίνεις, ή όταν τον χρειάζεσαι έτοιμο και οι κανόνες επιτρέπουν τυπωμένο υλικό (π.χ. το team reference document του ICPC).
Οι υποβολές γίνονται στο ίδιο το CSES ή στο Codeforces· εδώ δεν τρέχει judge.