哦我想这不用看都知道是为了水任务
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_{i=1}^n num[i] = k \\ \sum_{i=2}^{n+1} num[i] = k\end{matrix}
∑i=1nnum[i]=k∑i=2n+1num[i]=k
两式相减就可以得到: n u m [ i ] = n u m [ i + n ] num[i] = num[i+n] num[i]=num[i+n]
所以我们就发现了所有模 n n n 余数相同的列的值时一样的
剩下的我就不知道了
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;
}
当时还把 colour 打成了 color , 幸好最后改回来了
cspj的时候文件保存按成了撤销痛失100分我不说是谁
T2 造城墙
有一说一这题数据是真的弱啊
首先,对于 40 % 40\% 40% 的数据,可以直接状压
然后对于另外 20 % 20\% 20% 的数据可以直接染色跑二分图
分析
正文开始
看到这题其实像 czy 那样的猥琐小子大佬,第一反应应该就是网络流罢,对棋盘黑白染色,这个应该不难想
没错这个跟这道题的正解没关系
但是可以帮助你理解思路
注意下面均用 0 代表偶数 1 代表奇数
首先一个很显然的贪心就是 所有横着的砖块肯定放在最顶上
如果你用脚造了几组数据玩玩的话你会发现,所有横着放的砖块会构成多个倒三角
like this
如果对于这个倒三角还有点懵的可以在这里停一下搞清楚先
所以我们考虑维护当前列倒三角的高度
让我们随便造几组数据(下面的数据均是空白格的个数)
一列一列枚举:1 高度为 1, 10 高度为 2 , 101 高度为 3,1011 高度为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 = 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
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 = 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 骑士与国王
这题其实就是个容斥对吧(逃)
Code
我这题没打,那就放一下
x
h
g
u
a
⋅
h
y
x
xhgua\cdot hyx
xhgua⋅hyx 大帝的代码罢
黄瓜好吃,拜谢黄瓜!!!
结语
谁家 noip 3道数学题起步啊
谁家 noip 3小时不到啊
谁家 noip 有人踹电源线啊
有一说一 OI这玩意真的运气成分很高文章来源:https://www.toymoban.com/news/detail-633857.html
我爱优先队列 ! 优先队列好闪 拜谢优先队列!!! 以后找对象就找优先队列这样的 ! ! ! \begin{matrix}\color{white}{我爱优先队列!} \\ \color{white}{优先队列好闪\ 拜谢优先队列!!!}\\ \color{white}{以后找对象就找优先队列这样的!!!}\end{matrix} 我爱优先队列!优先队列好闪 拜谢优先队列!!!以后找对象就找优先队列这样的!!!文章来源地址https://www.toymoban.com/news/detail-633857.html
到了这里,关于最后一次模拟考试题解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!