10.10考試題

voteplus

【問題描述】
R 君博客上有?個投票板塊,?家可以使?投票的?式來表達??對某些問題的贊成或反對的意見。

投票結果是公開的,但是 R 君會把這個結果化成?個最簡分數,如 1:2,4:3。

注意到同?個最簡分數可能代表了不同的總?數,如: 300 ?贊同, 600?反對與 1 ?贊同, 2 ?反對顯?的都是 1:2。

Neetenin 同學發現了這?點,但是 Neetenin 同學想猜出有多少?參加了投票,他使?的?法是先看結果,??投?票贊同后再看結果。

?如?個當前的投票結果是 1:2,但是 Neetenin 同學投了?票贊成后變成了 301:600, Neetenin 同學就知道?共有 300+600+1=901 ?參加了此次投票。

現在 Neetenin 同學把之前和之后的結果都告訴你,讓你算算?共有多少?參加了投票!

當然, Neetenin 可能也有看錯了的時候,所以當問題?解的時候請輸出”fake”(不含雙引號)。

【輸入格式】

??四個整數 a,b,c,d,表?前?次結果是 a:b,后?次結果是 c:d。

【輸出格式】

輸出?個整數或?個字符串”fake”(不含雙引號),表?參加投票的總?數,包含 Neetenin 同學。

【樣例輸入 1】

1 4 1 3

【樣例輸出 1】

16

【樣例輸入 2】

1 3 1 4

【樣例輸出 2】

fake

【數據規模及約定】

對于前 50% 的數據, 1 ≤ a; b; c; d ≤ 100000。

對于前 50% 的數據, 1 ≤ 答案 ≤ 100000。

對于前 100% 的數據, 1 ≤ a; b; c; d ≤ 10^9。

對于前 100% 的數據, 1 ≤ 答案 ≤ 10^9。

【題解】

設之前是x人投贊成,y人反對,那么不難列出\(\displaystyle\frac x y=\frac a b,\frac{x+1}y=\frac c d\)

把這個方程組亂搞搞,就能得到\(\displaystyle x=\frac{ad}{bc-ad},y=\frac{bd}{bc-ad}\)

判斷\(bc-ad>0\),并且ad和bd都能整除即可輸出,否則當然是fake了

fire

【問題描述】
森林著?了,?勢還在不斷蔓延。

R 君作為森林管理員,看到?勢失去控制、在森林中四處蔓延,??很慌。

經過 R 君平?仔細的研究,這個森林的?勢傳播可以看成?個 n 個節點的帶邊權的?向圖 (節點標號為 1-n),每個節點代表森林的?個區域,?條邊 (u,v,w) 代表著?勢從區域 u 傳播到區域 v 需要花費 w 的時間。并且整個森林是?個連通圖,?旦著?,沒有節點可以幸免。

通過?動化的 IoT 設備, R 君觀察到了 0 時刻有 k 處起?點,然后??就按照?勢傳播圖的規則蔓延開來。

不幸的是森林?有 q 個區域存在著居民,所以 R 君?常想知道?勢蔓延到這 q 個區域的時間從?展開營救?動。
然? R 君覺得這個問題太難了,于是找到了學 OI 的你。

【輸入格式】

第??四個整數 n, m, k, q,表?圖的點數、邊數、起?點數量、存在居民的區域數量。

接下來 m ?,每?三個正整數 u, v, w,表??條 u 到 v,邊權為 w 的?向邊。

接下來?? k 個正整數,表? 0 時刻 k 個起?點的節點編號。

接下來?? q 個正整數,表?詢問的 q 個居民區的節點編號。

【輸出格式】

輸出 q ?,每??個整數,表??勢蔓延到該點的時間。

【樣例輸入】

5 5 2 5
1 2 5
1 3 2
2 3 5
2 4 5
3 5 2
2 5
5 4 3 2 1

【樣例輸出】

0 5 2 0 4

【數據規模及約定】

對于前 10% 的數據, 1 ≤ n ≤ 100。

對于另外 20% 的數據,圖為?棵樹。

對于另外 20% 的數據, k=1。

對于另外 20% 的數據, q=1。

對于前 100% 的數據, 1 ≤ n; m ≤ 10000, 1 ≤ k; q; u; v ≤ n, 1 ≤ w ≤10000。

【題解】

建立一個炒雞src,向所有著火的點連邊權為0的邊跑最短路。實際操作的時候可以直接把所有著火的點的dis設為0并放到堆中跑dij。

matrix

【問題描述】

? Y ?分喜歡計數,?天他遇到了這樣的?個問題:

有?個 n ? m 列的矩陣,剛開始每個位置的數字都是 0。? Y ?先進? r 次這樣的操作,選擇?? (可與之前選擇重復) 把這??的每個數字+1。之后? Y 進? c 次這樣的操作,選擇?列 (可與之前選擇重復) 把這?列的每個數字 +1。

最后? Y 數了?下,矩陣?總共有 k 個位置的數字是奇數。

但是? Y 忘了之前是怎么操作的了,所以現在? Y 想知道有多少種操作?案能夠使得最后?共有 k 個位置的數字是奇數。

兩種操作?案不同當且僅當存在某?或某列進?操作的次數不同。

因為答案很?,所以只需輸出這個答案除以 109 + 7 的余數。

【輸入格式】

輸?包含??五個空格隔開的整數, n,m,r,c,k。

【輸出格式】

輸出包含?個整數,表?答案。

【樣例輸入】

2 2 2 2 4

【樣例輸出】

4

【數據規模和約定】

對于 20% 的數據, 1 ≤ n; m; r; c ≤ 4;

對于 50% 的數據, 1 ≤ n; m; r; c ≤ 2000;

對于 100% 的數據, 1 ≤ n; m; r; c ≤ 10^5; 0 ≤ k ≤ nm。

【題解】

很值得思考很有趣的一道題。

我們先假設矩陣操作后,有x行操作了奇數次,有y列操作了奇數次。

那么不難列出x(m-y)+y(n-x)=k,即mx+ny=k+2xy。我們可以枚舉x而推出y,從而得出所有合法的x和y。這里給出根據x求y的式子:\(\displaystyle y=\frac{k-mx}{n-2x}\),很容易推出來。

但是我們觀察到分母是\(n-2x\),如果\(n-2x=0\)那么怎么辦?

我們可以考慮,當\(n-2x=0\)時,相當于操作完所有的行后,恰好有一半的行是奇數,另一半的行是偶數。那么如果再操作列,奇數元素的數量是不改變的。。所以當2k=mn時,y可以取任意合法值,否則y無解。

注意到還有\(m-2y=0\)的情況,也要考慮一下。我們可以直接枚舉x求y枚舉y求x,把所有合法的(x,y)塞到一個set里不就得了。。。其實最完美的做法是只枚舉x,并判斷那種情況。但是這里再告訴你一個事實,其實那種情況只需要判斷是否有2k=mn即可,如果有,那么那種情況一定存在,且其他情況不存在。這個結論可以通過GeoGebra探索出來。

我們處理出所有合法的(x,y)后,就枚舉剛才處理的所有(x,y)并計算貢獻。顯然的是行和列的貢獻是獨立的,這里只考慮行的貢獻。首先我們一共有n行,最后有x行被操作奇數次,那么方案數為\(\mathrm{C}_{n}^x\)。我們先把這x次操作干完,然后剩下的就可以每兩個操作組成一對去操作同一行,操作完成之后那行還是偶數,一共有\(\displaystyle\frac {r-x}{2}\)個操作對。由于每一行可以操作多次,那么就是多重集的組合數:\(\mathrm{C}_{n+\frac{r-x}{2}-1}^{\frac{r-x}{2}}\)了。

所以最后一個(x,y)的貢獻為\(\mathrm{C}_{n}^x\times\mathrm{C}_{n+\frac{r-x}{2}-1}^{\frac{r-x}{2}}\times\mathrm{C}_{m}^y\times\mathrm{C}_{m+\frac{c-y}{2}-1}^{\frac{c-y}{2}}\)。答案為所有(x,y)的貢獻。

注意如果\(r-x\)或者\(c-y\)不是偶數,那么貢獻為0

轉載于:https://www.cnblogs.com/oier/p/9776024.html

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/250504.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/250504.shtml
英文地址,請注明出處:http://en.pswp.cn/news/250504.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

koa --- 跨域,解析POST參數、路由配置

目標 將開發中經常遇見的問題寫在這里方便查詢. 使用Koa創建一個簡單的服務器 const Koa require("koa"); const app new Koa(); app.listen(3000, () >{console.log("[server] Server is running at http://localhost:3000") })使用koa2-cors解決…

mysql數據庫常用操作

目前最流行的數據庫: oracle、mysql、sqlserver、db2、sqline --:單行注釋 #:也是單行注釋 /* 注釋內容*/:多行注釋 mysql -uroot -p密碼:登錄mysql service mysqld restart重啟mysql /etc/my.cnfmysql的配置文件 /var…

數碼相機控制點的自動定位檢校

為簡化控制場相機檢校中的人工量測控制點的繁瑣工作,提高相機檢校精度,本文提出一種方法:只需均勻量測少量控制點的像方坐標獲取相機檢校初始參數,便可通過動態模板匹配實現單影像相機檢校的控制點高精度自動定位檢校。實驗證明此方法檢校精度與人工量測檢校精度相近。 https:/…

Java 常用類

Java 常用類 字符串相關類 String類:構造字符串對象 常量對象:字符串常量對象是用雙引號括起的字符序列。 例如:”你好”、”12.97”、”boy”等。 字符串的字符使用Unicode字符編碼,一個字符占兩個字節 String類較常用構…

koa --- restful規范及其栗子

遵循Restful規范的簡單的栗子 前端代碼: <html><head><script src"https://cdn.jsdelivr.net/npm/vue/dist/vue.js"></script><script src"https://unpkg.com/element-ui/lib/index.js"></script><script src&qu…

軟工五:四則運算

題目要求 本次作業要求兩個人合作完成&#xff0c;駕駛員和導航員角色自定&#xff0c;鼓勵大家在工作期間角色隨時互換&#xff0c;這里會布置兩個題目&#xff0c;請各組成員根據自己的愛好任選一題。 題目一&#xff1a; 我們在剛開始上課的時候介紹過一個小學四則運算自動生…

Tomcat 配置Https

https://www.cnblogs.com/wanghaoyuhappy/p/5267702.html JDK1.8 keytool 生存證書 C:\keys\tomcat.keystore 1:證書生成 命令如下: keytool -genkey -alias tomcat -keypass 123456 -keyalg RSA -keysize 1024 -keystore C:/keys/tomcat.keytore -storepass 123456 keytool 使…

koa --- 使用koa-multer和element-ui組件上傳頭像

文件上傳 前端代碼 <script src"https://cdn.jsdelivr.net/npm/vue/dist/vue.js"></script> <script src"https://unpkg.com/element-ui/lib/index.js"></script> <linkrel"stylesheet"href"https://unpkg.co…

PKUSC2018訓練日程(4.18~5.30)

(總計:共66題) 4.18~4.25&#xff1a;19題 4.26~5.2&#xff1a;17題 5.3~5.9: 6題 5.10~5.16: 6題 5.17~5.23: 9題 5.24~5.30: 9題 4.18 [BZOJ3786]星系探索(偽ETT) [BZOJ4337][BJOI2015]樹的同構(樹的最小表示法) [BZOJ3551][ONTAK2010]Peaks(加強版)(Kruskal重構樹,主席樹) …

筆記:less的三種使用方法

直接在瀏覽器端使用 第一步&#xff0c;引入 .less 文件&#xff08;注意要將 rel 屬性設置為“stylesheet/less”&#xff09; <link rel"stylesheet/less" type"text/css" href"styles.less" /> 第二步&#xff0c;引入Less.js文件 <…

koa --- nunjucks在Koa中的使用、中間件的配置

Nunjucks在Koa中的應用 app.js const koa require(koa); const app new koa(); const router require(./router) const nunjucks require(koa-nunjuncks-2); app.use(nunjucks({ext: html, // 指定視圖文件默認后綴path: path.join(__dirname, views), // 指定視圖目錄…

2018福大軟工實踐第六次作業

目錄 NABCD分析引用N(Need&#xff0c;需求)&#xff1a;A(Approach&#xff0c;做法)&#xff1a;B(Benefit&#xff0c;好處)&#xff1a;C(Competitors&#xff0c;競爭)&#xff1a;D(Delivery&#xff0c;交付)&#xff1a;初期中期個人貢獻分評定原則評定細則本組現場答辯…

day32—CSS多列布局學習

轉行學開發&#xff0c;代碼100天——2018-04-17 關于多列布局&#xff0c;前期已經梳理過&#xff0c;今天的培訓課程學習中再次提及&#xff0c;趁此也做個總結和檢驗。 多列布局的介紹參考&#xff1a; day08—css布局解決方案之多列布局關于多列布局的類型和方法&#xff1…

JDBC 事物處理

JDBC 事物處理 ?事務&#xff1a;指構成單個邏輯工作單元的操作集合 ?事務處理&#xff1a;保證所有事務都作為一個工作單元來執行&#xff0c;即使出現了故障&#xff0c;都不能改變這種執行方式。當在一個事務中執行多個操作時&#xff0c;要么所有的事務都被提交(commit…

centos6上安裝mysql8.0版本

本博客是采用yum源的方式安裝&#xff0c;非常的方便和快捷。(redhat 與centos7 等操作系統都可以采用此方法&#xff0c;步驟大體一致) mysql官網地址: https://dev.mysql.com 開始安裝&#xff1a; 1.清理環境&#xff0c;查看有沒有之前安裝過的mysql記錄&#xff0c;清理…

koa --- 使用koa-multer上傳文件+elementUI

核心代碼 const upload require(koa-multer) ({dest: ./public/images}); router.post(/upload, upload.single(file), ctx>{console.log(file, ctx.req.file);console.log(body, ctx.req.body);ctx.body 上傳成功; })目錄結構如下 基本思路 1.通過瀏覽器訪問url: http:…

[bzoj4003][JLOI2015]城池攻占_左偏樹

城池攻占 bzoj-4003 JLOI-2015 題目大意&#xff1a;一顆n個節點的有根數&#xff0c;m個有初始戰斗力的騎士都站在節點上。每一個節點有一個standard&#xff0c;如果這個騎士的戰斗力超過了這個門檻&#xff0c;他就會根據城池的獎勵增加自己的戰斗力。具體地&#xff1a;每一…

Java Web Servlet

Java Web Servlet Servlet是在服務器上運行的小程序。一個Servlet就是一個Java類&#xff0c;并且可以通過“請求-響應”編程模型來訪問的這個駐留在服務器內存里的Servlet程序。 Servlet可完成以下功能&#xff1a; 讀取客戶端&#xff08;瀏覽器&#xff09;發送的顯式的數…

第二篇 python基礎知識總結:數據、運算符

引子 我們跟任何人交流&#xff0c;說的每一句都是都一些文字組成&#xff0c;包含名詞、動詞、語句、標點符號等&#xff0c;組成我們說普通話構成的基本要素。同理我們學習python語言也要明白這些基本要素&#xff0c;也就是我們常說的基本語法&#xff0c;這是我們必須掌握的…

【BZOJ1797】[AHOI2009]最小割(網絡流)

【BZOJ1797】[AHOI2009]最小割&#xff08;網絡流&#xff09; 題面 BZOJ洛谷 題解 最小割的判定問題&#xff0c;這里就當做記結論吧。&#xff08;源自\(lun\)的課件&#xff09; 我們先跑一遍最小割&#xff0c;求出殘量網絡。然后把所有還有流量的邊拿出來跑\(Tarjan\)縮\(…