首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式碼之家 >> 編程語言 >  >> C語言 >> C++ >> 關於C++

Codeforces Round #290 (Div. 2) 題解:A-D 四題完整分析

     編輯:關於C++

A. Fox And Snake —— 模擬輸出蛇形圖案

奇數行全 #;偶數行:4 的倍數行首 # 其餘 .,其他偶數行尾 # 其餘 .。

B. Fox And Two Dots —— DFS 判環

網格中尋找同顏色環(長度 ≥ 4)。DFS 記錄深度,遇到已訪問同色鄰居且深度差 ≥ 3 → 存在環。注意重置訪問標記避免干擾。

C. Fox And Names —— 拓撲排序

給定 n 個名字,判斷是否存在字母順序使其字典序有序。相鄰名字找首個不同字符建立有向邊,檢測圖中是否有環(Kahn 算法)。若某名字是前一個的前綴但更長 → Impossible。

D. Fox And Jumping —— GCD 動態規劃

選若干數使其 GCD 為 1,最小化總代價。n ≤ 300,所有可能 GCD 狀態較少。用 map<gcd, cost> 維护狀態,每個數轉移更新,最終查 gcd=1 的最小代價。

代碼統一模板

#include <bits/stdc++.h>
using namespace std;
// ... 四題代碼見原文 ...

核心技巧總結

  • A:找規律直接輸出
  • B:DFS + 深度記錄判環
  • C:字典序約束建圖 + 拓撲排序
  • D:GCD 狀態少 + 類背包 DP
  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式碼之家 All Rights Reserved