滁州建设网站,百度网站v认证,杭州做绒毛鉴定网站,长沙网络营销推广哦我想这不用看都知道是为了水任务
T1 黑白染色
其实这题有原 什么手写体 md (指 markdown)
分析
首先这题如果你题目没看错的话 ,会发现其实他是 n m n \times m nm 让你求 n n n \times n nn 的区域内的点#xff08;不会只有我一个人题目看错了罢
然后我们会发现…哦我想这不用看都知道是为了水任务
T1 黑白染色
其实这题有原 什么手写体 md (指 markdown)
分析
首先这题如果你题目没看错的话 ,会发现其实他是 n × m n \times m n×m 让你求 n × n n \times n n×n 的区域内的点不会只有我一个人题目看错了罢
然后我们会发现其实我们只关心每一列放了多少并不关心是怎么放的这一步可以用组合数算出来
波利亚说过解题时可以回到定义上去 所以列出公式这里 n u m [ i ] num[i] num[i] 代表每一列放置点的数量 ∑ i 1 n n u m [ i ] k ∑ i 2 n 1 n u m [ i ] k \begin{matrix} \sum_{i1}^n num[i] k \\ \sum_{i2}^{n1} num[i] k\end{matrix} ∑i1nnum[i]k∑i2n1num[i]k
两式相减就可以得到 n u m [ i ] n u m [ i n ] num[i] num[in] num[i]num[in]
所以我们就发现了所有模 n n n 余数相同的列的值时一样的
剩下的我就不知道了
Code
我讲不来但是我有代码
#include bits/stdc.h
#define ll long long
#define ull unsigned long long
#define int long long
const int N 1e610;
const int M 1e510;
const int mod 1e97;
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*nim));
// 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;
}
当时还把 colour 打成了 color , 幸好最后改回来了
cspj的时候文件保存按成了撤销痛失100分我不说是谁
T2 造城墙 有一说一这题数据是真的弱啊
首先对于 40 % 40\% 40% 的数据可以直接状压
然后对于另外 20 % 20\% 20% 的数据可以直接染色跑二分图
分析
正文开始
看到这题其实像 czy 那样的猥琐小子大佬第一反应应该就是网络流罢对棋盘黑白染色这个应该不难想
没错这个跟这道题的正解没关系 但是可以帮助你理解思路
注意下面均用 0 代表偶数 1 代表奇数
首先一个很显然的贪心就是 所有横着的砖块肯定放在最顶上
如果你用脚造了几组数据玩玩的话你会发现所有横着放的砖块会构成多个倒三角
like this 如果对于这个倒三角还有点懵的可以在这里停一下搞清楚先
所以我们考虑维护当前列倒三角的高度
让我们随便造几组数据下面的数据均是空白格的个数 一列一列枚举1 高度为 1 10 高度为 2 101 高度为 31011 高度为3 10110 高度为2
这里发现什么当出现 00 或者 11 的时候高度不会再增加并且下一行如果奇偶性不同高度还会减 1 其实这个应该看图就知道了罢
如果您无法理解
可以把他看成一个黑白染色每一列不能匹配的黑格子都会被放到最顶上这样一列一列的黑格子剩下来就是高度了
那接下来就考虑维护高度有了上面的规律之后我们记 b l a c k black black 为当前的高度黑格子数
不难发现如果当前的空白格数小于黑格子数肯定就不能满足。如果空白格数减黑格子数为奇数那黑格子数就要加一如果为偶数那就减一
最后别忘了在黑格子减一的时候和 0 取 m a x max max 其实不取你也能得到 80 分的好成绩
Code
#include bits/stdc.h
#define ll long long
#define ull unsigned long long
#define int long long
const int N 1e610;
const int M 1e510;using namespace std;
int n;
priority_queuepairint,int,vectorpairint,int , greaterpairint,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-zy,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(xxxz,t-yz),a));a 0;}else{a - num;q.push(make_pair(max(xxxz,t-yz),num));}
// cout xx xx ;
// cout max(xxxy,t-zy) xx ;}else{q.push(make_pair(t-yz,a));
// cout t-yz a endl;sum a;a 0;
// cout t-zy yy ;}}
// cout endl;}cout sum;return 0;
}
T3 炸鸡 这手写的 LaTeX \LaTeX LATEX 是真的一言难尽
分析
这题有一个很重要的性质就是 同一份订单中不会有任何一口锅做超过一份的鸡因为鸡的保存时间小于制作时间
接下来考虑贪心
虽然我们是非常单纯美好的但是这题的做法非常的黑心那就是 给顾客的鸡能多接近保质期就多接近保质期
然后我们就可以用优先队列维护每口锅最早开始的闲置时间然后每次取最早的就行如果没有锅满足要求那就新买几口锅 为了让顾客吃上临近保质期的鸡我还新买锅我真是太伟大了)
写代码的时候记得搞清楚每口锅最早开始闲置的时间是什么
好的我们写完了这个非常czy的代码定睛一看忽然发现数据范围是 1 0 9 10^9 109 而不是 10
那这样我们一个一个丢肯定不对那么怎么办呢 如果你把每次取出的锅的时间都输出来你会发现有很多锅的时间其实是一样的 别问我为什么要输出因为当时把 y , z y,z y,z 看反了
这样想到什么 没错往堆里面丢 p a i r pair pair 不就好了吗
Code
这里有个小技巧就是一开始就把第一次所用的锅都扔进去这样可以防止越界和代码打漏
#include bits/stdc.h
#define ll long long
#define ull unsigned long long
#define int long long
const int N 1e610;
const int M 1e510;using namespace std;
int n;
priority_queuepairint,int,vectorpairint,int , greaterpairint,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-zy,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(xxxz,t-yz),a));a 0;}else{a - num;q.push(make_pair(max(xxxz,t-yz),num));}
// cout xx xx ;
// cout max(xxxy,t-zy) xx ;}else{q.push(make_pair(t-yz,a));
// cout t-yz a endl;sum a;a 0;
// cout t-zy yy ;}}
// cout endl;}cout sum;return 0;
}
T4 骑士与国王 这题其实就是个容斥对吧逃)
Code
我这题没打那就放一下 x h g u a ⋅ h y x xhgua\cdot hyx xhgua⋅hyx 大帝的代码罢 黄瓜好吃拜谢黄瓜
结语
谁家 noip 3道数学题起步啊
谁家 noip 3小时不到啊
谁家 noip 有人踹电源线啊
有一说一 OI这玩意真的运气成分很高 我爱优先队列 ! 优先队列好闪 拜谢优先队列 以后找对象就找优先队列这样的 ! ! ! \begin{matrix}\color{white}{我爱优先队列!} \\ \color{white}{优先队列好闪\ 拜谢优先队列}\\ \color{white}{以后找对象就找优先队列这样的!!!}\end{matrix} 我爱优先队列!优先队列好闪 拜谢优先队列以后找对象就找优先队列这样的!!!
