能查個(gè)人信息的網(wǎng)站百度競(jìng)價(jià)托管代運(yùn)營公司
哦我想這不用看都知道是為了水任務(wù)
T1 黑白染色
其實(shí)這題有原
什么手寫體 md (指 markdown)
分析
首先這題如果你題目沒看錯(cuò)的話 ,會(huì)發(fā)現(xiàn)其實(shí)他是 n × m n \times m n×m 讓你求 n × n n \times n n×n 的區(qū)域內(nèi)的點(diǎn)(不會(huì)只有我一個(gè)人題目看錯(cuò)了罷
然后我們會(huì)發(fā)現(xiàn)其實(shí)我們只關(guān)心每一列放了多少,并不關(guān)心是怎么放的(這一步可以用組合數(shù)算出來)
波利亞說過解題時(shí)可以回到定義上去 , 所以列出公式(這里 n u m [ i ] num[i] num[i] 代表每一列放置點(diǎn)的數(shù)量)
∑ i = 1 n n u m [ i ] = k ∑ i = 2 n + 1 n u m [ i ] = k \begin{matrix} \sum_{i=1}^n num[i] = k \\ \sum_{i=2}^{n+1} num[i] = k\end{matrix} ∑i=1n?num[i]=k∑i=2n+1?num[i]=k?
兩式相減就可以得到: n u m [ i ] = n u m [ i + n ] num[i] = num[i+n] num[i]=num[i+n]
所以我們就發(fā)現(xiàn)了所有模 n n n 余數(shù)相同的列的值時(shí)一樣的
剩下的我就不知道了
Code
我講不來但是我有代碼
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define int long long
const int N = 1e6+10;
const int M = 1e5+10;
const int mod = 1e9+7;
using namespace std;
int c[200][200];
int d[200][200];
int dp[200][10005];
int n,m,k;
int ksm(int a, int b){int x = a,ans = 1;while(b){if(b & 1){ans = ans * x % mod;}x = x * x % mod;b >>= 1;}return ans;
}
signed main(){freopen("discolour.in","r",stdin);freopen("discolour.out","w",stdout);cin >> n >> m >> k;for(int i =1;i <= 100; i++){c[i][0] = c[i][i] = 1;for(int j = 1; j < i; j++){c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod;}}for(int i = 1;i <= n; i++){for(int j = 0; j <= n; j++){d[i][j] = ksm(c[n][j],m/n+(m/n*n+i<=m));
// cout << d[i][j] << endl;}}dp[0][0] = 1;for(int i = 1; i <= n; i++){for(int j = 0; j <= min(k,n*i); j++){for(int kk = 0; kk <= min(j,n); kk++){dp[i][j] = (dp[i][j] + dp[i-1][j-kk]*d[i][kk] % mod)%mod;
// cout << dp[i][j] << endl;}}}cout << dp[n][k];return 0;
}
當(dāng)時(shí)還把 colour 打成了 color , 幸好最后改回來了
cspj的時(shí)候文件保存按成了撤銷痛失100分我不說是誰
T2 造城墻
有一說一這題數(shù)據(jù)是真的弱啊
首先,對(duì)于 40 % 40\% 40% 的數(shù)據(jù),可以直接狀壓
然后對(duì)于另外 20 % 20\% 20% 的數(shù)據(jù)可以直接染色跑二分圖
分析
正文開始
看到這題其實(shí)像 czy 那樣的猥瑣小子大佬,第一反應(yīng)應(yīng)該就是網(wǎng)絡(luò)流罷,對(duì)棋盤黑白染色,這個(gè)應(yīng)該不難想
沒錯(cuò)這個(gè)跟這道題的正解沒關(guān)系
但是可以幫助你理解思路
注意下面均用 0 代表偶數(shù) 1 代表奇數(shù)
首先一個(gè)很顯然的貪心就是 所有橫著的磚塊肯定放在最頂上
如果你用腳造了幾組數(shù)據(jù)玩玩的話你會(huì)發(fā)現(xiàn),所有橫著放的磚塊會(huì)構(gòu)成多個(gè)倒三角
like this
如果對(duì)于這個(gè)倒三角還有點(diǎn)懵的可以在這里停一下搞清楚先
所以我們考慮維護(hù)當(dāng)前列倒三角的高度
讓我們隨便造幾組數(shù)據(jù)(下面的數(shù)據(jù)均是空白格的個(gè)數(shù))
一列一列枚舉:1 高度為 1, 10 高度為 2 , 101 高度為 3,1011 高度為3 , 10110 高度為2
這里發(fā)現(xiàn)什么,當(dāng)出現(xiàn) 00 或者 11 的時(shí)候高度不會(huì)再增加,并且下一行如果奇偶性不同高度還會(huì)減 1 (其實(shí)這個(gè)應(yīng)該看圖就知道了罷
如果您無法理解
可以把他看成一個(gè)黑白染色,每一列不能匹配的黑格子都會(huì)被放到最頂上,這樣一列一列的黑格子剩下來就是高度了
那接下來就考慮維護(hù)高度,有了上面的規(guī)律之后,我們記 b l a c k black black 為當(dāng)前的高度(黑格子數(shù))
不難發(fā)現(xiàn),如果當(dāng)前的空白格數(shù)小于黑格子數(shù),肯定就不能滿足。如果空白格數(shù)減黑格子數(shù)為奇數(shù),那黑格子數(shù)就要加一,如果為偶數(shù),那就減一
最后別忘了在黑格子減一的時(shí)候和 0 取 m a x max max (其實(shí)不取你也能得到 80 分的好成績(jī))
Code
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define int long long
const int N = 1e6+10;
const int M = 1e5+10;using namespace std;
int n;
priority_queue<pair<int,int>,vector<pair<int,int> > , greater<pair<int,int> > > q;
int x,y,z;signed main(){freopen("chicken.in","r",stdin);freopen("chicken.out","w",stdout);cin >> n;cin >> x >> y >> z;int t,a;cin >> t >> a;q.push(make_pair(t-z+y,a));int sum = a;for(int i = 2; i <= n; i++){cin >> t >> a;while(a){int xx = q.top().first,num = q.top().second;if(xx + x <= t){
// cout << xx << " " << num << endl;q.pop();if(num > a){num -= a;q.push(make_pair(xx,num));q.push(make_pair(max(xx+x+z,t-y+z),a));a = 0;}else{a -= num;q.push(make_pair(max(xx+x+z,t-y+z),num));}
// cout << xx << " xx ";
// cout << max(xx+x+y,t-z+y) << " xx ";}else{q.push(make_pair(t-y+z,a));
// cout << t-y+z << " " << a << endl;sum += a;a = 0;
// cout << t-z+y << " yy ";}}
// cout << endl;}cout << sum;return 0;
}
T3 炸雞
這手寫的 LaTeX \LaTeX LATE?X 是真的一言難盡
分析
這題有一個(gè)很重要的性質(zhì)就是 :同一份訂單中,不會(huì)有任何一口鍋?zhàn)龀^一份的雞(因?yàn)殡u的保存時(shí)間小于制作時(shí)間)
接下來考慮貪心
雖然我們是非常單純美好的,但是這題的做法非常的黑心,那就是 給顧客的雞能多接近保質(zhì)期就多接近保質(zhì)期
然后我們就可以用優(yōu)先隊(duì)列維護(hù)每口鍋?zhàn)钤玳_始的閑置時(shí)間,然后每次取最早的就行,如果沒有鍋滿足要求那就新買幾口鍋 為了讓顧客吃上臨近保質(zhì)期的雞我還新買鍋我真是太偉大了)
寫代碼的時(shí)候記得搞清楚每口鍋?zhàn)钤玳_始閑置的時(shí)間是什么
好的我們寫完了這個(gè)非常czy的代碼,定睛一看,忽然發(fā)現(xiàn),數(shù)據(jù)范圍是 1 0 9 10^9 109 而不是 10
那這樣我們一個(gè)一個(gè)丟肯定不對(duì),那么怎么辦呢?
如果你把每次取出的鍋的時(shí)間都輸出來,你會(huì)發(fā)現(xiàn),有很多鍋的時(shí)間其實(shí)是一樣的
(別問我為什么要輸出,因?yàn)楫?dāng)時(shí)把 y , z y,z y,z 看反了)
這樣想到什么? 沒錯(cuò)往堆里面丟 p a i r pair pair 不就好了嗎
Code
這里有個(gè)小技巧就是一開始就把第一次所用的鍋都扔進(jìn)去,這樣可以防止越界和代碼打漏
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define int long long
const int N = 1e6+10;
const int M = 1e5+10;using namespace std;
int n;
priority_queue<pair<int,int>,vector<pair<int,int> > , greater<pair<int,int> > > q;
int x,y,z;signed main(){freopen("chicken.in","r",stdin);freopen("chicken.out","w",stdout);cin >> n;cin >> x >> y >> z;int t,a;cin >> t >> a;q.push(make_pair(t-z+y,a));int sum = a;for(int i = 2; i <= n; i++){cin >> t >> a;while(a){int xx = q.top().first,num = q.top().second;if(xx + x <= t){
// cout << xx << " " << num << endl;q.pop();if(num > a){num -= a;q.push(make_pair(xx,num));q.push(make_pair(max(xx+x+z,t-y+z),a));a = 0;}else{a -= num;q.push(make_pair(max(xx+x+z,t-y+z),num));}
// cout << xx << " xx ";
// cout << max(xx+x+y,t-z+y) << " xx ";}else{q.push(make_pair(t-y+z,a));
// cout << t-y+z << " " << a << endl;sum += a;a = 0;
// cout << t-z+y << " yy ";}}
// cout << endl;}cout << sum;return 0;
}
T4 騎士與國王
這題其實(shí)就是個(gè)容斥對(duì)吧(逃)
Code
我這題沒打,那就放一下 x h g u a ? h y x xhgua\cdot hyx xhgua?hyx 大帝的代碼罷
黃瓜好吃,拜謝黃瓜!!!
結(jié)語
誰家 noip 3道數(shù)學(xué)題起步啊
誰家 noip 3小時(shí)不到啊
誰家 noip 有人踹電源線啊
有一說一 OI這玩意真的運(yùn)氣成分很高
我愛優(yōu)先隊(duì)列 ! 優(yōu)先隊(duì)列好閃?拜謝優(yōu)先隊(duì)列!!! 以后找對(duì)象就找優(yōu)先隊(duì)列這樣的 ! ! ! \begin{matrix}\color{white}{我愛優(yōu)先隊(duì)列!} \\ \color{white}{優(yōu)先隊(duì)列好閃\ 拜謝優(yōu)先隊(duì)列!!!}\\ \color{white}{以后找對(duì)象就找優(yōu)先隊(duì)列這樣的!!!}\end{matrix} 我愛優(yōu)先隊(duì)列!優(yōu)先隊(duì)列好閃?拜謝優(yōu)先隊(duì)列!!!以后找對(duì)象就找優(yōu)先隊(duì)列這樣的!!!?