首页 > 小白菜又菜

模擬城市天際線下載,小白菜又菜

互联网 2021-06-18 03:32:23
原创UVa 11838 - Come and Go

题目:已知一个有向图,问是否所有节点间都连通(可以双向到达)。分析:图论。利用floyd算法求传递闭包,判断输出即可。说明:( ⊙ o ⊙ )。#include #include #include #include int maps[2002][2002];int main(){ int N, M, V, W, P; while (~scanf("%d%d",&N,

2017-06-19 11:51:09336

原创UVa 10264 - The Most Potent Corner

题目:一个n维的单位立方体,每个顶点上有一个权值,顶点的power为它的相邻顶点的权值和,            求两个相邻定点的power的和的最大值。分析:位运算。利用异或运算,求相邻节点求解。            n维的单位立方体,可以用二进制数来描述,每个位代表一个维度,二进制数对应向量;            相邻的节点,只有一个坐标是不同的,所以枚举所有位异或,可以得

2017-06-18 22:59:40365

原创UVa 11054 - Wine trading in Gergovia

题目:有一些等距排列在一条直线上的酒店,他们之间互相运送酒,供求相符,            每次运送以箱酒的代价为两家店的距离,求满足供求关系的总运送代价最小值。分析:贪心。可以采用需求或提供的量求解,这里使用需求量求解。            如果正数和负数分别在两端,那么无论怎么对应总代价相同;           (如:-a, -b, a b,可以变成0, -b, 0, b

2017-06-15 09:40:32445

原创UVa 10680 - LCM

题目:求解前n个数的LCM的最后的非零位。分析:数论。将前n个数的LCM因式分解,然后依次相乘取尾数。            将前n个数的LCM = 2^k1 * 3^k2 * ...*pn^kn,其中pn位第n个素数,且pn^kn ≤ n;            首先打表计算素数,然后利用素数去求对应的kn;            求最后的非零位,去掉5和2的公共个数即可(5不多

2017-06-13 16:08:53410

原创UVa 10720 - Graph Construction

题目:已知一个无向图的所有顶点的度,问能否构造成一个简单图。分析:图论。使用Havel定理或者Erdős定理。            构成图判定:所有点的度数和为偶数(防止溢出可以只判断奇偶);            构成简单图:            1.Havel定理:将所有边排序,将度数最大的顶点依次与剩下的顶点连接边(从度数大的开始),                 

2017-06-13 08:24:54400

原创UVa 1152 - 4 Values whose Sum is 0

題目:有四個集合(可以使重集)A、B、C、D,各含有n個元素,問每個集合中各取出一個數字,            使得他們的和為0,問有多少種取法。分析:排序。計算A+B中所有的可能組合、排序,C+D的所有可能組合、排序,然後匹配。            匹配過程,如果A+B中的元素x與C+D中的元素y不為0,移動對應索引(指針);            如果x+y = 0匹配,則

2017-05-25 20:03:36560

原创UVa 12100 - Printer Queue

題目:有一個打印機,裡面有很多任務。打印的時候,如果隊列中後面的文件優先級高,            則先打印優先級最高的文件,前面的任務依次放入隊尾,問第每m個文件何時打印。           (所有文件打印都只需要1個單位時間,其它動作不耗時)分析:數據結構、模擬。直接利用一個隊列模擬即可。說明:第911題,O(∩_∩)O~。#include #include in

2017-05-24 20:30:03874

原创UVa 602 - What Day Is It?

題目:判斷對應日期是星期幾。其中涉及閏年計算,閏年按歷史上的實際情況計算:            1.1752年9月2日之前,使用四年一閏的方式;            2.1752年9月14日之後,使用現在的閏年計算方式(四年一閏,百年不閏,四百年閏);            3.1752年9月2日的後一天為752年9月14日(缺少的11天補足之前閏年的遺漏);分析:模擬。按照上

2017-05-23 10:37:18447

原创UVa 843 - Crypt Kicker

題目:有一些單詞都成的字典,還有一些加密過的單詞組成的句子(除字母只有空格和換行);            求出一種可行的解碼方案(字母鍵間構成雙射),沒有解全都輸出*。分析:搜索、回溯、dfs。對應每個句子中的單詞在字典里搜索對應的匹配項。            利用回溯法搜索,每次在整個字典中尋找匹配項,如果矛盾則返回;            矛盾:對應字母映射不同,或被映射的

2017-05-19 17:44:30706

原创UVa 143 - Orchard Trees

題目:統計一個平面中在一個三角內的整點數目(包括在邊上)。分析:計算幾何。這裡利用叉乘判斷方向,以及在線段上的特判。            先將頂點排序(找左下角,然後利用叉乘),然後判斷在三條直線右側的點滿足題意;            如果點在三邊上進行特判;            這裡有一組比較好的數據:71.67 88.3 45.02 49.09 98.49 0.1說明

2017-05-16 16:15:19368

原创UVa 556 - Amazing

題目:機器人在一個二維平面上移動,會沿著右手邊的墻移動,無法前進就左轉,            直到可以前進,回到出發點是結束(左下角),統計每個格子經過幾次,            輸出每個經過次數(0-4)對應的格子數目。分析:模擬。直接按照題目模擬即可。每次先判斷右側,不行就左轉直到可以移動。說明:數據間沒有空格、沒有空格、沒有空格。#include #include

2017-05-09 21:03:06343

原创UVa 11839 - Optical Reader

題目:編寫答題卡識別程序,每道題目為單選題,五個 選項(ABCDE),            通過灰度值判斷選取的選項(不大於127),如果有多個滿足則輸出*。分析:模擬。直接安置數值判斷即可。說明:( ⊙ o ⊙ )!#include #include int mark[256][5];int main(){ int N; while (~scanf("%d",

2017-05-08 09:56:09247

原创UVa 10267 - Graphical Editor

題目:編輯圖像的二維數組,存在題目中的跟中操作(存在非法操作,直接跳過不處理);分析:圖論、搜索。直接模擬處理即可,這裡用floodfill處理K操作,注意dfs可能會暴棧。說明:注意坐標可能不是升序的,所以要先交換。#include #include char bmp[256][256];char name[1000];void floodfill(int n, int

2017-05-04 17:43:09565

原创UVa 10132 - File Fragmentation

題目:有一些相同的文件(01串)被分成兩部分,然後混亂在一起,問原始文件。分析:字符串、搜索。首先求出文件長度,然後枚舉所有可能組合判斷餘下碎片的合法性。            本來以為文件的順序是可能倒序的,但是一直WA,後來發現不能倒序;            文件碎片的組合只能是前後(str[i] + str[j])或者后前(str[j] + str[i]);       

2017-05-03 08:27:30483

原创UVa 796 - Critical Links

題目:統計一個圖中的橋(割边,原本连通去掉后就不连通了)的個數。分析:图论、搜索。这里没经验每条边,然后利用dfs求子图个数进行判断。說明:也可以使用求强连通,缩点然后求割边个数。#include #include #include #define NODE_SIZE 10001#define EDGE_SIZE 10001typedef struct _edge{

2017-05-01 12:47:41808

原创UVa 125 - Numbering Paths

題目:已知一些單向道路,求個城市間的路徑有多少種,存在環衛-1(無窮)。分析:圖論、最短路。利用floyd算法求出路徑條數,然後判斷無窮。            如果從a城市可以到達b城市,並且從b城市也可以到達a城市,則存在環;            再利用floyd更新所有存在環的路徑。說明:吐槽一下沒有給節點數目(⊙o⊙)…#include #include #inc

2017-04-28 13:01:01606

原创UVa 11242 - Tour de France

題目:變速自行車有兩個齒輪盤,每個盤上有幾個齒輪,變速級別是變速比的有序序列;            求變速序列中相鄰比例的最大值。分析:排序。存儲所有的變速比例,排序統計即可。說明:( ⊙ o ⊙ )!#include #include double F[11];double R[111];double D[1111];int cmp(const void *a,

2017-04-27 13:44:35425

原创UVa 900題記錄

終於刷到900題了,這50道題刷了半年多o(╯□╰)o。終於把白書看完了(第一版);看了幾門公開課,也不是很多;感覺這段時間成長不高;讀書:(最近兩個月只看了一本書)《平面國》對維度世界的描述很不錯;《牛津通俗讀本——數學》和之前的基本科普讀物一起看不錯;《Effective C++》看了之後發現自己基本不會C++;《丈量世界》高斯和洪堡的故事,測量的時代;

2017-04-26 13:04:253402

原创UVa 714 - Copying Books

題目:抄m本書,書的編號是連續的,現在要把這些書,按照連續編號分成k組,            每本書有頁數,使得頁數和最大的那組總頁數最小,輸出方案。分析:貪心、二分。利用二分頁數總和,貪心判斷最少需要的組數。            輸出答案是從後向前組合即可,這裡也是貪心。說明:900題了╮(╯▽╰)╭。#include int page[505];int part

2017-04-26 09:14:29312

原创UVa 320 - Border

題目:尋找一個圖形的外邊界,輸出位圖信息。分析:搜索,模擬。直接利用題目的描述求解。            跟蹤已知路徑(交叉點的位置),每次利用當前位置求解四個角的方框。’說明:還差一道題了╮(╯▽╰)╭。#include #include char maps[33][33] = {0}; int main(){ intn, x, y; char buf[10

2017-04-24 15:26:08279

原创UVa 11239 - Open Source

題目:學校有一些開源項目,學生會對項目進行登記,統計每個項目有多少學生註冊,            每個學生最多可以註冊一個,但是有些學生註冊了多個項目、則所有註冊無效,            有些學生同一項目註冊了多次、只計算一次。分析:字符串。使用map記錄查詢。            定義一個user_select標記數組,記錄學生註冊的第一個課程、如果多個記-1。說明:

2017-04-23 13:35:06307

原创UVa 584 - Bowling

題目:計算保齡球的得分。保齡球一共分為10局(frame),每局最多扔兩個球(roll);            如果第一次直接把10個球都打到就記10分(X),並且還要加下兩球的得分,           (注意是球,如果後面兩局都是X,加20分,如果后一局不是X,加下一局的得分)            如果第一次沒有全部打倒,可以再投一球,如果這次打倒,兩球的總分也是10分(/),

2017-04-22 15:32:24350

原创UVa 523 - Minimum Transport Cost

題目:在幾個城市間運送貨物,每個城市間的道路有固定的花費,            經過某個特定城市也有一個固定的花費,求最小代價和路徑。分析:圖論、最短路。使用floyd算法求解多元最短路記錄路徑即可。            記錄每個節點的後繼既可以保存路徑;說明:這道題真的很想吐槽:            1、輸入的格式沒有城市個數,需要字符串轉成數字統計個數;     

2017-04-21 22:01:48728

原创UVa 10181 - 15-Puzzle Problem

題目:15數碼求解。分析:搜索,A*。利用A*算法求解15數碼。利用逆序數判斷是否可解。            可解:左右移動時、逆序數不變,上下移動時、逆序數變化奇偶性、加上行變換次數,奇偶性不變;                       (這裡計算逆序數是,不計入0,這個是空位)            估值:哈密爾頓距離 + 當前步數(這兩項可以有個比例權值);   

2017-04-20 18:19:06442

原创UVa 10502 - Counting Rectangles

題目:計算一個01矩陣中有多少個不同的矩形。分析:動態規劃(DP)。這個題目中使用了多個不同狀態。            定義狀態:s(i,j)為矩形ixj中矩形個數,f(i,j)為矩形ixj中包含塊(i,j)的矩形個數;            轉移方程:s(i,j)= s(i-1,j)+ s(i,j-1)- s(i-1,j-1)+ f(i,j);            定義狀

2017-04-14 16:21:49367

原创UVa 10037 - Bridge

題目:過橋問題(數學競賽題),有n個人過一座橋,每次只能過兩個人必須帶著燈,            燈只有一個,問最少的過橋時間,以及一種過橋策略。分析:動態規劃(dp),記憶化搜索。建立地推關係求解(先把最久的兩個人或一個人送走)。            狀態定義:f(n)為n個人過橋的最少時間,min(i)(max(i))為第i小(大)的時間,            轉移方程:

2017-04-10 12:55:15544

原创UVa 450 - Little Black Book

題目:有一些不同部門的人事信息,需要將他們合併后按照姓氏排列。分析:字符串。直接按照題意模擬即可,讀取數據排序輸出。說明:注意數組開的大一點防止RE(RE了2次╮(╯▽╰)╭)。#include #include #include typedef struct _information{ char Title[101]; char FirstName[101]; cha

2017-04-04 09:44:1318774

原创UVa 787 - Maximum Sub-sequence Product

題目:計算一個序列的最大子段乘機。分析:動態規劃(DP)。dp過程和最大子段和類似。            因為乘數有負數,所以需要保留最小值(最小的負數乘以負數就是最大值);            狀態定義:max(i)為以i結束的子段的最大乘機,min(i)為以i結束的子段的最小乘機;            轉移方程:這裡 需要列出一個表格;             

2017-04-03 21:51:11802

原创UVa 314 - Robot

題目:一個機器人在一個矩形的地圖上行走,地圖上有些方形的障礙(1m*1m),            由於機器人有寬度,不能碰到障礙,每次機器人執行一條指令耗費1s時間,            指令包括向前走(1或2或3m),向左轉,向右轉,給定其實位置和方向,            以及目標的位置(方向任意),求最少的移動時間。分析:圖論、搜索。最短時間,使用bfs求解到達每個點的

2017-04-01 15:32:52441

原创UVa 10655 - Contemplation! Algebra

題目:已知a+b及ab的值求a^n + b^n的值。分析:分治法、快速冪。找到地推關係,利用矩陣的快速冪算法求解。            1.地推關係:                設 f(n)= a^n + b^n;                由 f(n)*(a + b)= a^(n+1)+ b^(n+1)+ ab^n+a^nb                    

2017-03-30 16:15:57289

原创UVa 10816 - Travel in Desert

题目:穿越沙漠有几个区域,每个区域间有路径链接(两点间路径不唯一);            寻找一条路径使得,路径中的最高温度最小(存在多组取距离最小)。分析:图论、最短路、最小生成树。分两步求解。            首先,寻找到最小的最高温度,這裡使用dijkstra算法;            然後,利用上述最高溫度作為選取路徑的閾值,求最短路,使用dijkstra算法。

2017-03-28 17:50:07403

原创UVa 11003 - Boxes

題目:有一些盒子(有重量和載重量),從中選出一些摞起來,問做多能選幾個;            選取箱子羅列時,需要按照已知的順序。分析:動態規劃(dp),01背包。            狀態定義:f(i,j)為前i個箱子羅成總重量為j時,使用的最大箱子數;            轉移方程:f(i,j)= max(f(i-1,j),f(i-1,j-weight[i]))後者需滿足

2017-03-27 23:22:18632

原创UVa 11496 - Musical Loop

题目:一直一些从信号中采集的点,询问峰值个数(极大极小值)。分析:模拟。极大值大于两侧的值,极小值小于两侧的值。说明:╮(╯▽╰)╭。#include #include int H[10005];int main(){ int n; while (~scanf("%d",&n) && n) { for (int i = 1; i

免责声明:非本网注明原创的信息,皆为程序自动获取自互联网,目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责;如此页面有侵犯到您的权益,请给站长发送邮件,并提供相关证明(版权证明、身份证正反面、侵权链接),站长将在收到邮件24小时内删除。

相关阅读