¿Qué deberían preparar los principiantes de acm y qué libros deberían leer?

Los estudiantes que recién entran en contacto con el campo de la informática a menudo tienen mucha confusión y no saben por dónde empezar. En este artículo espero compartir mi pequeña experiencia con ustedes, esperando que así sea. te será de ayuda.

1. El idioma es la habilidad básica más importante

No importa en qué aspecto te centres, siempre que sea una competición que en última instancia se realice a través de programas informáticos, el idioma es el primero. obstáculo que todos deben superar. Los lenguajes admitidos en los concursos en Asia incluyen C/C++ y JAVA. El autor primero habla de JAVA. Como todos sabemos, como lenguaje de triunfo orientado a objetos, JAVA tiene sus propias ventajas únicas en la organización y seguridad de proyectos a gran escala. Sin embargo, para ocasiones específicas de competencias de informática, JAVA lo es. No es tan adecuado para la entrada. La operación del flujo de salida es mucho más complicada que la 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 ++. El límite de tiempo de los programas JAVA en las competiciones a menudo no se relaja en la misma proporción. Sin duda, impone requisitos más altos en el diseño de algoritmos, lo cual es bastante desventajoso. De hecho, el autor no recomienda que se utilice demasiado la programación orientada a objetos en esta situación, porque para programas pequeños, esto no solo tomará más tiempo para escribir código, sino que también reducirá la eficiencia de ejecución del programa.

Hablemos de C y C++. Muchos de los estudiantes que asistieron a la conferencia todavía están en su primer año de universidad y acaban de terminar de aprender los conceptos básicos de C y aún no han estado expuestos a C ++. De hecho, todavía hay muchos jugadores que usan C puro en la competencia. Valoramos principalmente la eficiencia del C puro. Por lo tanto, si estos estudiantes tienen un tiempo limitado, no necesitan apresurarse a aprender un nuevo lenguaje. Siempre que mejoren sus logros en el diseño de algoritmos, el C puro también puede ejercer un gran poder.

En comparación con C, la encapsulación de flujos de entrada y salida de C++ facilita enormemente nuestras operaciones, al tiempo que reduce la posibilidad de errores y puede cambiar de manera efectiva entre flujos estándar y flujos de archivos, lo cual es conveniente para realizar el trabajo de depuración. Si algunos estudiantes están más preocupados por esto, pueden probar una combinación de 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 biblioteca proporciona operaciones de interfaz unificadas para estructuras de datos básicas e implementación de algoritmos básicos, lo que puede reducir la longitud del código que escribimos. ahorrar algo de tiempo. Sin embargo, por el contrario, el uso de STL requiere algunos sacrificios en eficiencia. Para problemas con una gran escala de entrada, a veces se debe abandonar STL, lo que significa que no podemos tener la idea de que "con STL, podemos ignorar la idea de algoritmo básico". ​​​realizando "; además, el uso de STL de manera competente y adecuada debe acumularse durante un cierto período de tiempo y comprender con precisión la complejidad temporal de varias operaciones. Tenga cuidado de no abusar de partes desconocidas de STL, porque contiene muchas cosas que son difíciles para principiantes. Descubre la trampa.

A través del análisis anterior, podemos ver que en lo que respecta a la competencia de ciencias de la información, no se requiere que el dominio del idioma sea muy completo, pero para las partes de uso frecuente, se debe ser muy competente, y no se permite lo más mínimo. Si hay algo que no está claro, permítame darle un ejemplo real para ilustrar este principio; incluso una ligera barrera del idioma puede llevar a errores:

En la competencia de Tsinghua del año pasado, hubo. era un Cuando el equipo estaba haciendo la pregunta F, utilizaron una salida mixta de cout y printf. Dado que uno estaba almacenado en el búfer y el otro no, el resultado se volvió confuso a medida que se hacía más largo. Solo porque la persona a cargo de la pregunta F en el equipo de jueces tenía ojos agudos en ese momento, vio que la respuesta era correcta pero en el orden incorrecto (la respuesta ocupaba más de una página, que era el resultado más largo entre todas las preguntas). ), miró el programa y descubrió que solo estaba generando la pregunta. Obtuvo un error de presentación (formato incorrecto). Si el revisor no hace esto pero da directamente una respuesta incorrecta, creo que será difícil para el equipo descubrir dónde se equivocó.

Ahora pasamos al segundo aspecto de la discusión, la acumulación de conocimientos básicos de la materia.

2. Es muy importante tener conocimientos básicos principalmente en matemáticas.

Aunque se caracteriza como una competencia de programación, los problemas que encuentran los concursantes son más bien que no tienen ideas para resolverlos. , en lugar de tener una idea pero no poder implementarla, esto se debe a que los conocimientos básicos acumulados en la vida diaria no son suficientes.

El campeón absoluto de la final mundial de este año es la Universidad de Varsovia en Polonia. Sus miembros pertenecen al Departamento de Matemáticas y no al Departamento de Ciencias de la Computación. Este es un claro ejemplo. Las materias básicas involucradas en la competencia se centran principalmente en matemáticas. Además, puede haber algunas aplicaciones en física, circuitos, etc., pero no muchas. Por lo tanto, los estudiantes de primer año no tienen que preocuparse por dónde empezar a mejorar porque aún no han aprendido las estructuras de datos. ¡Simplemente aprenden matemáticas! Ahora permítanme hablar sobre 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. Su máxima prioridad radica en 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 es la más utilizada es que tiene la mayor cantidad de cambios y puede combinar fácilmente estructuras de datos básicas y las ideas básicas de muchos algoritmos. El conocimiento más utilizado incluye juicio de conectividad, DFS y BFS. , puntos de unión y caminos críticos, circuitos de Euler, árboles de expansión mínima, caminos más cortos, coincidencia de gráficos bipartitos, flujos de red y más. Aunque esta parte tiene una gran proporción, a menudo es un problema difícil en la competencia. Si un principiante se siente temporalmente incapaz de realizar algún contenido específico en esta parte, no hay necesidad de preocuparse y podrá acumularlo lentamente.

La mayoría de los problemas de conteo combinatorio diseñados en la competencia deben resolverse mediante matemáticas combinatorias. El conocimiento en matemáticas combinatorias es más simple que el de teoría de grafos. Muchos de los conocimientos ya son muy útiles para los estudiantes que tienen. Asistí a la Escuela Olimpíada en la escuela primaria Familiar, pero hay algunas partes que requieren una comprensión preliminar de la teoría de grupos en estructuras algebraicas antes de aprender. Las matemáticas combinatorias rara vez aparecen como un problema difícil en las competiciones, pero si la acumulación no es suficiente, cualquier cuestión en esta área puede convertirse en un problema difícil.

2. Teoría de números: las preguntas construidas basándose en el juicio de números primos y la congruencia a menudo requieren más conocimientos de teoría de números para resolverse. Esta parte no juega un papel importante en la competencia, pero siempre y cuando llegues a hacerlo. el anterior, también es suficiente para hacer pensar mucho por un rato a las personas con conocimientos insuficientes. El juicio de números primos y la congruencia aparecen con mayor frecuencia en preguntas con experiencia en criptografía. Después de utilizar el sentido común de la criptografía para determinar el proceso aproximado, el algoritmo central a menudo implica la teoría de números.

3. Geometría computacional: la geometría computacional es relativamente independiente en comparación con otras partes, lo que significa que rara vez se combina demasiado con otros puntos de conocimiento. Las partes más utilizadas incluyen: Juicio de intersección de segmentos de línea. cálculo del área del polígono, juicio de puntos interiores y exteriores, casco convexo, etc. Las preguntas de geometría computacional no serán muy difíciles, pero nunca serán las preguntas más débiles.

4. Álgebra lineal: la aplicación del álgebra lineal gira en torno a matrices. Algunas preguntas aparentemente de simulación 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 pensar en usar algoritmos de probabilidad, pero esto no significa que la probabilidad sea inútil. Esto sólo puede lograrse mediante cierta práctica.

6. Matemáticas elementales y geometría analítica: estos son principalmente conocimientos de la escuela secundaria que no se utilizan mucho, pero al menos son más que matemáticas avanzadas. Manual de matemáticas, al menos conócelo. ¿Dónde puedo encontrarlo?

7. Matemáticas avanzadas: solo me he encontrado con una pregunta que se resuelve exclusivamente con matemáticas avanzadas. Sin embargo, el trasfondo narrativo de algunas preguntas a menudo debe tener una cierta conexión con esta parte. en tener un agarre más firme.

Lo anterior es el campo de las matemáticas involucrado en la competencia. Se puede decir que el alcance es bastante amplio. Muchas personas que conozco participan en concursos de ciencias de la información sólo para obligarse a aprender más matemáticas, porque las matemáticas son la base de todo.

3. Las estructuras de datos y los algoritmos son el verdadero núcleo.

Aunque las matemáticas son muy importantes, si a tres personas que solo saben matemáticas se les permite participar en la competencia, creo que en la mayoría En algunos casos serán mejores que Tres personas que solo conocían estructuras de datos y algoritmos tuvieron un final más trágico.

Hablemos primero de la estructura de datos. Es necesario dominar las expresiones y operaciones básicas de colas, pilas y gráficos. En cuanto a los árboles, personalmente creo que hay algunos problemas que requieren la construcción de árboles, pero no muchos. (Pero los árboles suelen ser herramientas de análisis muy importantes). Además, la clasificación y la búsqueda no requieren el dominio de todos los métodos, pero debe asegurarse de tener un método que cumpla con la complejidad del tiempo para diversas situaciones.

Hablando de la complejidad del tiempo, es hora de volver a hablar de las tablas hash. El límite de tiempo durante la competencia es mucho mayor que el límite de espacio. Esto requiere que todos dominen el principio y la estrategia de "intercambiar espacio por tiempo" lo antes posible. poder usar tablas hash. Los datos almacenados en la tabla no se deben buscar más adelante. Si realmente no puede crear una tabla hash, vea si puede crear un árbol de búsqueda binario, etc., todas estas son estrategias para ganar. Dominar estas habilidades requiere que todos comprendan los datos y tengan una comprensión racional y perceptiva relativamente completa de la estructura, especialmente la complejidad del algoritmo.

Hablemos de algoritmos. El algoritmo más básico y comúnmente utilizado es la búsqueda, principalmente el uso de 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 los casos de prueba que le brindarán todas las preguntas de búsqueda no serán de gran escala y usted. A menudo, el problema del tiempo de ejecución del programa no se puede detectar, pero los datos de prueba reales definitivamente pueden filtrar esos algoritmos sin podarlos. De hecho, los concursantes utilizan básicamente algoritmos de búsqueda de uso común y la distinción de preguntas a menudo se basa en optimizaciones como la poda.

Otra categoría de algoritmos de uso común 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. Cómo abstraer subproblemas repetidos es la dificultad de muchos temas. El autor recomienda que los principiantes comprendan cuidadosamente algunos algoritmos básicos de la teoría de grafos basados ​​en la programación dinámica (como el algoritmo de Floyd-Warshall). y lea más demostraciones de teoremas. Aunque esto puede no ser de ayuda directa, la perseverancia a largo plazo será muy útil para pensar.

4. Trabajo en equipo

A través de la introducción anterior, también puede ver que la competencia de informática cubre una gama muy amplia de conocimientos. Es realmente difícil digerir todas estas cosas por su cuenta. Es bastante difícil, lo que requiere que ejercitemos el espíritu de trabajo en equipo tanto como sea posible. La formación de una cooperación hábil y un entendimiento tácito entre los miembros del mismo grupo lleva tiempo. La situación específica varía dependiendo de la composición de los miembros, por lo que no entraré en detalles aquí.

5. Practica, practica, vuelve 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 practica. Este es el conocimiento más profundo. De muchos predecesores, creo que solo a través del análisis y la práctica de temas específicos podemos dominar verdaderamente el uso de las matemáticas y la aplicación de 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 y optimizar el tiempo. asignación y fortalecer el trabajo en equipo. En resumen, es absolutamente imposible hablar aquí simplemente en papel. Debes entrenarte mediante el combate real.

Todos deben preguntarse: ¿dónde encontramos el problema y cómo comprobamos si el programa es correcto? No hay necesidad de preocuparse por esto. Ya existen muchos sitios para realizar exámenes en línea. Estos sitios proporcionan una gran cantidad de bancos de preguntas y respaldan el juicio en línea. Solo necesita enviar el código fuente del programa e inmediatamente sabrá si es su programa. es correcto y ejecutarlo. El tiempo utilizado, la memoria consumida, etc. A continuación le recomiendo algunos sitios. No recomiendo que responda preguntas en todos estos sitios. Simplemente elija uno, porque las preguntas en cada sitio tienen un cierto índice de dificultad. Hacer sistemáticamente un conjunto de bancos de preguntas puede ayudarlo. conocimiento de cuestiones de diversas dificultades y tipos.

1. Ural:

Ural es la abreviatura de Universidad Estatal de los Urales en Rusia por parte de estudiantes chinos, donde se ha creado un conjunto de problemas en línea de los Urales y respalda a Online Judge. Muchas de las preguntas de Ural son altamente algorítmicas y anecdóticas, y son amadas por una gran cantidad de estudiantes en todo el país. Según las estadísticas del sitio web "Informatics Beginners' Home", los tipos de preguntas de Ural se distribuyen aproximadamente de la siguiente manera:

Tipo de pregunta

Buscar

Programación dinámica

Codicioso

Construcción

Teoría de grafos

Geometría computacional

Problema de matemáticas puras

Datos estructura

Otros

Proporción

Aproximadamente el 10%

Aproximadamente el 15%

Aproximadamente el 5%

Aproximadamente el 5 %

Aproximadamente el 10 %

Aproximadamente el 5 %

Aproximadamente el 20 %

Aproximadamente el 5 %

Aproximadamente el 25%

Esto es más o menos lo mismo que la distribución de tipos de preguntas en la competencia real. Los amigos que estén interesados ​​pueden ir a echar un vistazo.

2. UVA:

La UVA representa a la Universidad de Valladolid en España. La universidad ha creado un ARCHIVO DE PROBLEMAS con JUEZ EN LÍNEA y admite JUEZ EN LÍNEA. El formulario es similar al banco de preguntas de la Universidad de los Urales. Sin embargo, a diferencia de Ural, en la UVA hay muchas más preguntas, que son más complicadas, y los datos de prueba de algunas preguntas son más complicados. Esto hace que los amigos que acaban de llegar allí para hacer las preguntas a menudo se sientan perdidos. O es difícil encontrar una pregunta adecuada o todavía no saben cuál es el error después de una respuesta incorrecta muchas veces. 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 competencias en línea simultáneas, por lo que hay innumerables personas fuertes allí, pero primero debes tener la calidad para entender de qué están hablando :)

3.

ZOJ es un JUEZ EN LÍNEA establecido por la Universidad de Zhejiang. Es el primer sitio de este tipo establecido por una universidad china y también es el mejor y más popular. El autor y muchos compañeros de clase practican aquí. Aunque ZOJ también se posiciona como un sitio web en inglés, hay muchos estudiantes chinos aquí, por lo que se siente muy amigable. Actualmente hay más de 500 preguntas aquí, con una distribución de dificultad moderada, que cubren tipos de preguntas de todos los continentes y están equipadas con índices. Además, el sistema JUDGE de ZOJ es uno de los mejores entre varios sitios web y rara vez aparecen errores de respuesta incorrecta y presentación. . También se celebra aquí un concurso en línea todos los meses y todos los usuarios registrados pueden participar.

Hablando del JUEZ EN LÍNEA de China, la Universidad de Pekín, que comenzó a participar en la competencia ACM el año pasado, ahora ha establecido su propio sistema de presentación y nuestra escuela también comenzó a participar en la competencia el año pasado, y ahora; Es posible lanzar su propio sistema de envío. Si se puede hacer, entonces todos pueden ir y hacer las preguntas. El rápido desarrollo de sitios web similares indica que cada vez más estudiantes están interesados ​​en explorar el campo de la informática. Esto es algo bueno, pero también significa una competencia más feroz.

¡Mira cómo este artículo puede ayudarte! ¡También soy un principiante en ACM!