¿Qué deben preparar y leer los principiantes de acm?
En primer lugar, el idioma es la habilidad básica más importante.
No importa en qué te centres, siempre que sea una competición que en última instancia se realice a través de un programa informático, el idioma es el primer obstáculo que todo el mundo tiene que superar. Los lenguajes soportados por los Juegos Asiáticos incluyen C/C++ y JAVA. El autor habla primero de JAVA. Como todos sabemos, JAVA, como lenguaje de triunfo orientado a objetos, tiene sus propias ventajas únicas en la organización y seguridad de proyectos a gran escala, pero no es tan adecuado para ocasiones específicas de competencias de informática. Su funcionamiento en iostream es mucho más complejo que el de C++. Más importante aún, la velocidad de ejecución de los programas JAVA es más de 10 veces más lenta que la de C++. Sin embargo, el límite de tiempo de ejecución de los programas JAVA en las competiciones a menudo no se relaja. misma proporción. De hecho, no recomiendo que la gente utilice demasiado el pensamiento de programación orientada a objetos en esta situación, porque para programas pequeños, no solo lleva más tiempo escribir código, sino que también reduce la eficiencia de ejecución del programa.
Hablemos de C y C++. Muchos de los estudiantes que asisten a la clase todavía son estudiantes de primer año. Acaban de aprender los conceptos básicos de C y aún no han estado expuestos a C++. De hecho, hay muchos jugadores que utilizan C puro en la competición. Valoran principalmente las ventajas de eficiencia del C puro. Por lo tanto, estos estudiantes no necesitan apresurarse a aprender un nuevo idioma si el tiempo es limitado. Siempre que mejoren sus conocimientos sobre el diseño de algoritmos, el C puro puede desempeñar un papel importante.
En comparación con C, la encapsulación de C++ en iostream facilita enormemente nuestras operaciones, reduce la posibilidad de errores y puede cambiar fácilmente entre secuencias estándar y secuencias de archivos para facilitar la depuración. Si a algún estudiante le interesa esto, puede intentar mezclar C y C++. Después de todo, no lleva mucho tiempo aprender las operaciones de flujo de C++.
Otro soporte para C++ proviene de la Biblioteca de plantillas estándar (STL). La operación de interfaz unificada de estructuras de datos básicas y la implementación de algoritmos básicos proporcionados en la biblioteca pueden acortar la longitud de nuestro código y ahorrar algo de tiempo. Pero en comparación, el uso de STL requiere algunos sacrificios en eficiencia. Para preguntas con una gran escala de entrada, a veces se debe abandonar STL. En otras palabras, no puede existir la idea de que "con STL, se puede ignorar la implementación del algoritmo básico". Además, para utilizar STL de manera competente y adecuada, debe acumular un cierto período de tiempo, comprender con precisión la complejidad temporal de varias operaciones y evitar abusar de partes desconocidas de STL, porque contiene muchas trampas que no son fáciles de descubrir para los principiantes; .
A través del análisis anterior, podemos ver que en lo que respecta a la Olimpiada de Informática, no se requiere que el dominio del idioma sea integral, pero las partes de uso frecuente deben ser muy competentes y debe haber sin ambigüedad. Permítanme dar un ejemplo real para ilustrar este principio: incluso una ligera barrera del idioma puede generar errores:
En la competencia de Tsinghua del año pasado, un equipo usó cout y resultados mixtos de printf. Debido a que uno tiene almacenamiento en búfer y el otro no, la salida se estropeará después de mucho tiempo. Fue solo porque la persona a cargo de la pregunta F en el equipo de jueces tenía buen ojo y vio que las respuestas eran correctas pero en el orden incorrecto (las respuestas ocupaban más de una página y eran las más largas entre todas las preguntas). Eché un vistazo al programa y descubrí que solo generaba preguntas, por lo que hizo una demostración Error (formato incorrecto). Si el examinador no hace esto y da directamente una respuesta incorrecta, creo que será difícil para el equipo descubrir dónde se equivocó.
Ahora pasamos a la segunda discusión, la acumulación de conocimientos básicos de la materia.
En segundo lugar, los conocimientos básicos basados en matemáticas son muy importantes
Aunque se define como un concurso de programación, los problemas que encuentran los concursantes son más bien una falta de ideas para resolver los problemas. No es una falta de conocimientos básicos acumulados en la vida diaria. La final mundial de este año la ganó la Universidad de Varsovia en Polonia, con miembros del Departamento de Matemáticas en lugar de Ciencias de la Computación. Este es un ejemplo vívido. Las materias básicas involucradas en la competencia son principalmente matemáticas. Puede haber algunas aplicaciones en física, circuitos, etc., pero no muchas. Por lo tanto, los estudiantes de primer año no tienen que pensar que aún no han terminado de aprender las estructuras de datos y aprenden matemáticas rápidamente. Permítanme hablar de las principales ramas de las matemáticas utilizadas en las competiciones.
1. Matemáticas discretas: como base de la informática, las matemáticas discretas son la rama de las matemáticas más involucrada en la competencia. Lo más importante es la teoría de grafos y las matemáticas combinatorias, especialmente la teoría de grafos.
La razón por la que la teoría de grafos se usa ampliamente es que tiene la mayor cantidad de cambios y puede combinar fácilmente estructuras de datos básicas con las ideas básicas de muchos algoritmos. El conocimiento de uso común incluye juicio de conectividad, DFS y BFS, puntos de conexión y rutas críticas, rutas de Euler, árboles de expansión mínima, rutas más cortas, coincidencia de gráficos bipartitos y flujo de red. Aunque esta parte tiene una gran proporción, suele ser un problema difícil en las competiciones. Si un principiante se siente abrumado por parte del contenido específico de esta parte, no se preocupe, puede ir acumulándolo poco a poco.
La mayoría de los problemas de conteo combinatorio diseñados en el concurso requieren matemáticas combinatorias para su resolución. En comparación con la teoría de grafos, el conocimiento de las matemáticas combinatorias es más simple y muchos de ellos son familiares para los estudiantes que tomaron la Olimpiada de Matemáticas en la escuela primaria. Sin embargo, algunas partes requieren una comprensión preliminar de la teoría de grupos en estructuras algebraicas para aprender. Las matemáticas combinatorias rara vez aparecen como un problema difícil en las competiciones, pero si no hay suficiente acumulación, cualquier cuestión en este campo puede convertirse en un problema difícil.
2. Teoría de números: el problema de la construcción del modelo de congruencia de juicio de números primos a menudo requiere más conocimientos de teoría de números para resolverlo. No es muy importante en la competencia, pero solo una pieza es suficiente para satisfacer a las personas con insuficiencia. conocimiento. Piensa bien por un momento. El juicio de números primos y la congruencia son las preguntas más comunes en temas basados en criptografía. Después de utilizar el sentido común en criptografía para determinar el proceso de aproximación, el algoritmo central suele implicar la teoría de números.
3. Geometría computacional: la geometría computacional es relativamente independiente de otras partes, lo que significa que rara vez se combina con otros puntos de conocimiento. Las partes de uso común incluyen el juicio de intersección de segmentos de línea, el cálculo del área del polígono, el juicio de puntos interiores y exteriores, casco convexo, etc. Los problemas de geometría computacional no serán difíciles, pero nunca serán los problemas más débiles.
4. Álgebra lineal: la aplicación del álgebra lineal gira en torno a matrices. Algunos problemas aparentemente analógicos a menudo pueden encontrar mejores algoritmos con la ayuda de matrices.
5. Teoría de la probabilidad: la competencia se juzga mediante una caja negra, lo que significa que difícilmente se puede utilizar la idea de algoritmos probabilísticos, pero esto no significa que la probabilidad sea inútil. En este punto, sólo podemos entenderlo a través de ciertas prácticas.
6. Matemáticas elementales y geometría analítica: estos son conocimientos principalmente en las escuelas intermedias, no se utilizan mucho, pero al menos más que las matemáticas avanzadas. Creo que es necesario familiarizarse con el contenido relevante del manual de matemáticas, o al menos saber dónde buscar.
7. Matemáticas avanzadas: solo encontré una pregunta basada exclusivamente en matemáticas avanzadas, pero el trasfondo narrativo de algunas preguntas a menudo debe estar relacionado con esta parte. Nunca está de más tenerlo bien controlado.
Los anteriores son los campos de las matemáticas involucrados en la competencia, que se puede decir que son bastante amplios. Muchas personas que conozco participan en concursos de informática sólo para obligarse a aprender más matemáticas, porque las matemáticas son la base de todo.
En tercer lugar, las estructuras de datos y los algoritmos son el verdadero núcleo.
Aunque las matemáticas son importantes, si tres personas que solo entienden matemáticas participan en la competencia, creo que en la mayoría de los casos obtendrán un final más trágico que tres personas que solo entienden estructuras de datos y algoritmos.
Permítanme hablar primero sobre la estructura de datos. Debe dominar las expresiones y operaciones básicas de colas, pilas y gráficos. En cuanto a los árboles, personalmente creo que hay algunos, pero no muchos, problemas que es necesario construir. (Pero los árboles suelen ser herramientas de análisis muy importantes). Además, ordenar y buscar no requiere dominar todos los métodos, pero sí debe asegurarse de tener una solución que cumpla con los requisitos mínimos en complejidad temporal para cada caso. Hablando de complejidad temporal, es hora de hablar de tablas hash. El límite de tiempo en el juego es mucho mayor que el límite de espacio, lo que requiere que todos dominen el principio y la estrategia de "intercambiar espacio por tiempo" lo antes posible. Los datos que se pueden almacenar en una tabla hash no deben poder buscarse en ese momento. Si es realmente imposible crear una tabla hash, veamos si podemos crear un árbol de búsqueda binario, etc. ——Estas son estrategias para ganar tiempo. Dominar estas habilidades requiere que todos tengan una comprensión racional y emocional integral de las estructuras de datos, especialmente la complejidad de los algoritmos.
Entonces hablemos del algoritmo. El algoritmo más básico y comúnmente utilizado es la búsqueda, que utiliza principalmente métodos de retroceso y ramificación y vinculación. Lo que quiero decir aquí es que algunos principiantes no prestan mucha atención a la poda cuando aprenden estos algoritmos de búsqueda básicos. Esto es muy indeseable porque no todas las preguntas de búsqueda le brindarán casos de prueba a gran escala. A menudo no se nota, pero los datos de prueba reales definitivamente filtrarán esos algoritmos sin podarlos. De hecho, los concursantes utilizan básicamente algoritmos de búsqueda de uso común y el grado de diferenciación de las preguntas a menudo se basa en optimizaciones como la poda.
Otra clase de algoritmos comúnmente utilizada se basa en "subproblemas similares o idénticos", que incluyen recursividad, recursividad, métodos codiciosos y programación dinámica. Entre ellos, la programación dinámica es más difícil de dominar y cómo abstraer subproblemas repetidos es una dificultad en muchos temas. Sugiero que los principiantes comprendan cuidadosamente algunos algoritmos básicos basados en la programación dinámica en la teoría de grafos (como el algoritmo de Floyd-Warshall) y lean más pruebas de teoremas. Aunque no puede ayudar directamente, la perseverancia a largo plazo será muy útil para pensar.
Cuarto, trabajo en equipo
Como se puede ver en la introducción anterior, el conocimiento de la Olimpiada de Informática es muy amplio y le resulta muy difícil digerir estas cosas por sí mismo. Es necesario ejercer el espíritu de trabajo en equipo tanto como sea posible. La cooperación hábil y el entendimiento tácito entre miembros del mismo grupo requieren tiempo. La situación específica varía según la composición de los miembros, por lo que no entraré en detalles aquí.
5.Practicar, practicar, volver a practicar
La acumulación de conocimientos es importante, pero al fin y al cabo la informática no es algo que se pueda ver, sino que se practique. Esta es la experiencia más profunda. de muchas personas mayores. Sólo a través del análisis y la práctica de temas específicos podemos dominar verdaderamente la aplicación de las matemáticas y los algoritmos, y aumentar la experiencia y las habilidades de programación a través de la práctica continua, mejorar nuestra comprensión perceptiva de la complejidad del tiempo, optimizar la asignación del tiempo y fortalecer el trabajo en equipo. En resumen, aquí no hay absolutamente ningún lugar para hablar sobre el papel. Tienes que entrenarte a través del combate real.
Todo el mundo debe preguntarse, ¿dónde podemos encontrar problemas y cómo podemos comprobar si el programa es correcto? No te preocupes por esto. Actualmente existen muchos sitios web de resolución de problemas en línea que proporcionan una gran cantidad de bancos de preguntas y admiten la calificación en línea. Solo necesita enviar el código fuente del programa e inmediatamente sabrá si su programa es correcto, el tiempo de ejecución y la memoria consumida. A continuación te recomiendo algunos sitios web. No recomiendo que hagas todas las preguntas de estos sitios, solo elige una, porque las preguntas de cada sitio tienen cierto grado de dificultad. Un banco de preguntas sistemático permite conocer preguntas de diversas dificultades y tipos.
1. Ural:
Ural es la abreviatura de Universidad Estatal de los Urales en Rusia por parte de estudiantes chinos. La escuela ha creado un conjunto de preguntas en línea sobre los Urales para respaldar la evaluación en línea. Muchas de las preguntas de Ural son algorítmicas, muy interesantes y muy apreciadas por los estudiantes nacionales. Según las estadísticas del sitio web "Home for Beginners in Informatics", los tipos de preguntas de Ural se distribuyen aproximadamente de la siguiente manera:
Tipos de preguntas de examen
Búsqueda
Dinámica Programación
p>Estructura codiciosa
Teoría de grafos
Geometría computacional
Problemas matemáticos puros
Estructura de datos
Proporción de otros
Aproximadamente el 10 %
Aproximadamente el 15 %
Alrededor del 5%
Aproximadamente el 5%
Aproximadamente el 10%
Aproximadamente el 5%
Aproximadamente el 20%
Alrededor del 5%
Aproximadamente el 25%
Esto es más o menos lo mismo que la distribución de preguntas en la competencia real. Los amigos interesados pueden ir a echar un vistazo.
2. UVA:
La UVA representa al Club de Fútbol Universitario Valladolid en España. Una de las universidades ha creado un archivo de preguntas con evaluación en línea para respaldar la evaluación en línea, similar al banco de preguntas de la Universidad de los Urales. Pero a diferencia de los Urales, en la UVA hay muchas y complejas preguntas, y los datos de las pruebas para algunas preguntas son más difíciles. Esto hace que los amigos que acaban de llegar allí para hacer las preguntas a menudo se sientan perdidos, o les resulte difícil encontrar una pregunta adecuada, o hayan cometido muchos errores y todavía no sepan dónde se equivocaron. Si las preguntas de los Urales son principalmente para entrenar algoritmos, entonces las preguntas de la UVA pueden entrenar una gama completa de habilidades básicas y algunas cualidades de programación necesarias. La UVA y muchas universidades de renombre mundial organizan conjuntamente competiciones en línea simultáneas, por lo que hay innumerables jugadores fuertes allí, pero primero debes entender de qué están hablando :)
3. >ZOJ es un juez en línea establecido por la Universidad de Zhejiang. Es el primer sitio web similar creado por una universidad china y también es el mejor y más popular. El autor y muchos compañeros de clase están haciendo prácticas aquí. Aunque ZOJ también se posiciona como un sitio web en inglés, hay muchos estudiantes chinos aquí, lo que hace que la gente se sienta muy amigable. Actualmente hay más de 500 preguntas con dificultad moderada y el índice cubre tipos de preguntas de todos los continentes. Además, el sistema JUDGE de ZOJ es uno de varios sitios web que funcionan bien y rara vez hay confusión entre errores de respuesta y errores de demostración. También hay aquí un concurso online todos los meses en el que pueden participar todos los usuarios registrados.
Hablando de jueces nacionales en línea, la Universidad de Pekín, que recién comenzó a participar en competencias ACM el año pasado, ahora ha establecido su propio sistema de presentación. Nuestra escuela también comenzó a participar en el concurso el año pasado y ahora es posible lanzar su propio sistema de presentación. Si se puede hacer, entonces todos pueden acudir a TI para hacer las preguntas. El rápido crecimiento de sitios como este muestra que cada vez más estudiantes están interesados en explorar el campo de la informática, lo cual es bueno y significa más competencia.
¡Mira lo que este artículo puede hacer por ti! ¡También soy principiante en ACM!