普及-交叉模拟*

这里也是模拟,但是会混有些别的部分。思维难度不大,但是编写起来会有些难度。

*P1023 税收与补贴问题 暴力经济学

题目背景

每样商品的价格越低,其销量就会相应增大。现已知某种商品的成本及其在若干价位上的销量(产品不会低于成本销售),并假设相邻价位间销量的变化是线性的且在价格高于给定的最高价位后,销量以某固定数值递减。(我们假设价格及销售量都是整数)

对于某些特殊商品,不可能完全由市场去调节其价格。这时候就需要政府以税收或补贴的方式来控制。(所谓税收或补贴就是对于每个产品收取或给予生产厂家固定金额的货币)

题目描述

你是某家咨询公司的项目经理,现在你已经知道政府对某种商品的预期价格,以及在各种价位上的销售情况。要求你确定政府对此商品是应收税还是补贴的最少金额(也为整数),才能使商家在这样一种政府预期的价格上,获取相对其他价位上的最大总利润。

总利润=单位商品利润 × 销量

单位商品利润=单位商品价格 - 单位商品成本 (- 税金 or + 补贴)

说明

所有数字均小于100000

Code

这道题太难读辣。。幸好我学过一点浑水摸鱼的经济学就当复习经济学了

尤其是出题人假设其实是的垄断市场,也就是说,只有一根需求曲线,最大营业额就是下图中的矩形面积的最大值

例:一个香烟垄断市场,生产者可以通过调节产量来获得最大的利润。

注意,本来矩形面积代表着最大营业额,取得最大利润还需要减去成本(往下平移曲线即可)。

而本题中政府能做的,同样是上下平移这条曲线(税收下移,补贴上移),使得矩形面积取最大值时,刚好顶边就是政府想要的价格。

实在不想做这个题。。orz太烦了。以后再做吧。想哭。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
using namespace std;

int main(){
int expect; cin>>expect;
vector<int> price, consume;
int Price, Consume; cin>>Price>>Consume;
int BIAS=Price; expect -=BIAS;
price.push_back(0); consume.push_back(Consume); //Price减去成本,只记录利润
while(1){
cin>>Price>>Consume;
if(Price == -1) break;
price.push_back(Price - BIAS); //Price减去成本,只记录利润
consume.push_back(Consume); //消费量
}
int lost_per_dollar; cin >> lost_per_dollar;
//---------------------------------------------------------------------------
int n = price.size(), dex, current_best_profit_price=0, dex_c_best=0;

cout<<"--------------------------"<<endl;
for(int i = 0; i < n; i++){
cout<<price[i]<<" "<<consume[i]<<endl;
}
cout<<"--------------------------"<<endl;

for(int i = 0; i < n; i++){ //找到预期价格在哪段区间[dex, dex+1)
dex = i;
if(expect < price[i])break;
}
cout<<"expect:"<<expect<<"--->Expected price["<<dex<<"]="<< price[dex]<<endl;
for(int i = 1; i < n; i++){ //找到现在的最大利润的价格区间[dex_c_best, dex_c_best+1)
if(current_best_profit_price < price[i]*consume[i]){
current_best_profit_price = price[i]*consume[i];
dex_c_best = i;
}
else break;
}
cout<<"Max Profit > price["<<dex_c_best<<"]--->"<< price[dex_c_best]<<endl;

int tax=0;
double expect_consume = (double)consume[dex] + (double)( dex==n-1 ? (double)lost_per_dollar*(expect-price[dex]) : (double)(consume[dex+1] - consume[dex])/(double)(price[dex+1] - price[dex])*(double)(expect-price[dex]) );
double expect_consume_pre, expect_consume_suc;
if(expect == price[dex]){
expect--;
dex--; expect_consume_pre = (double)consume[dex] + (double)( dex==n-1 ? (double)lost_per_dollar*(expect-price[dex]) : (double)(consume[dex+1] - consume[dex])/(double)(price[dex+1] - price[dex])*(double)(expect-price[dex]) );
dex++; expect_consume_suc = (double)consume[dex] + (double)( dex==n-1 ? (double)lost_per_dollar*(expect-price[dex]) : (double)(consume[dex+1] - consume[dex])/(double)(price[dex+1] - price[dex])*(double)(expect-price[dex]) );
expect++;
}
else{
expect_consume_pre = (double)consume[dex] + (double)( dex==n-1 ? (double)lost_per_dollar*(expect-price[dex]) : (double)(consume[dex+1] - consume[dex])/(double)(price[dex+1] - price[dex])*(double)(expect-price[dex]) );
expect_consume_suc = (double)consume[dex] + (double)( dex==n-1 ? (double)lost_per_dollar*(expect-price[dex]) : (double)(consume[dex+1] - consume[dex])/(double)(price[dex+1] - price[dex])*(double)(expect-price[dex]) );
}
cout<<"Expect Comsume:Pre["<< expect - 1 <<"]="<< expect_consume_pre <<", E[" <<expect <<"]="<< expect_consume <<", Suc["<< expect + 1 <<"]="<< expect_consume_suc <<""<<endl;

/*
if(dex < dex_c_best){ //曲线往下平移

while(expect + tax >= 0){

if()
break;
tax--;
}

}
else{ //曲线往上平移


} */


return 0;
}

P1031 均分纸牌

题目描述

1549876922319

Code

为什么这道题就这么水啊。。

思路就是,任意分成两个区间,如果两个区间的值需要交换一次才可能平均,那就记为交换一次。

相邻两堆牌间最多只会移动纸牌一次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

int main(){
int n; cin>>n;
vector<int> a;
int sum = 0;
for(int i = 0; i < n; i++){
int tmp; cin>>tmp;
a.push_back(tmp); sum+=tmp;
}

int P = sum/n; //每堆应有纸牌数
sum = 0;
int ans=0;
for(int i = 1; i <= n; i++){
sum += a[i-1]; //维护前缀和
if(sum != P*i) ans++; //只要需要交换就++
}
cout<<ans;

return 0;
}

P1042 乒乓球

题目背景

国际乒联现在主席沙拉拉自从上任以来就立志于推行一系列改革,以推动乒乓球运动在全球的普及。其中11分制改革引起了很大的争议,有一部分球员因为无法适应新规则只能选择退役。华华就是其中一位,他退役之后走上了乒乓球研究工作,意图弄明白11分制和21分制对选手的不同影响。在开展他的研究之前,他首先需要对他多年比赛的统计数据进行一些分析,所以需要你的帮忙。

题目描述

华华通过以下方式进行分析,首先将比赛每个球的胜负列成一张表,然后分别计算在111111分制和212121分制下,双方的比赛结果(截至记录末尾)。

比如现在有这么一份记录,(其中W表示华华获得一分,L表示华华对手获得一分):

WWWWWWWWWWWWWWWWWWWWWWLW

在11分制下,此时比赛的结果是华华第一局11比0获胜,第二局11比0获胜,正在进行第三局,当前比分1比1。

而在21分制下,此时比赛结果是华华第一局21比0获胜,正在进行第二局,比分2比1。如果一局比赛刚开始,则此时比分为0比0。直到分差大于或者等于2,才一局结束。

你的程序就是要对于一系列比赛信息的输入(WL形式),输出正确的结果。

说明

每行至多25个字母,最多有2500行

Code

有些小细节。

  • if(( le>=11 || ri>=11 ) && abs(le-ri)>=2 ),这个条件写对很重要

什!么!鬼!!!跟标准输出一模一样也给我判错?什!么!鬼!!!

我甚至写了一个对拍器:(结果对比完全一致,测例2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;

int main(){
string a[1000], b[1000];
int i = 0;

freopen("OJ.out", "r", stdin);
while(i < 186 && cin>>a[i]) i++;

i = 0;
while(i < 186 && cin>>b[i]) i++;

for(int i = 0; i < 186; ++i){
cout<<"a:"<<a[i]<<" b:"<<b[i]<<" \t---> "<<(a[i]==b[i])<<endl;
}

return 0;
}

我对模拟题产生了心理阴影

找了半天之后。。。

1549925105494

不对,不是这个问题。。

我真的佛了。orz

我特么else后面加上else if(str[i] == 'L')突然就过辣:

1
2
3
4
5
6
//原来是
if(str[i] == 'W') le++;
else ri++;
//改为
if(str[i] == 'W') le++;
else if(str[i] == 'L') ri++;

我明明都过滤了所有的\n,难道字符串里面除了W和L还能是别的???然而当我单独验证的时候,除了字符串里面确实只有W和L。。可是提交到OJ上却出现了奇怪的第三种字符的可能。这只能洛谷OJ的某种特殊机制

最后附上AC代码。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//AC代码
#include <bits/stdc++.h>
using namespace std;

int main(){
char c;
char str[1000005];
int index = 0;
while((c=getchar()) != 'E'){
if(c == '\n') continue;
str[index++] = c;
}

int le = 0, ri = 0;
for(int i = 0; i < index; i++){ //11分制
if(str[i] == 'W') le++;
else if(str[i] == 'L') ri++;

if(( le>=11 || ri>=11 ) && abs(le-ri)>=2 ){
cout<<le<<":"<<ri<<endl; le = ri = 0;
}
}
cout<<le<<":"<<ri<<endl<<endl; le = ri = 0;
for(int i = 0; i < index; i++){ //21分制
if(str[i] == 'W') le++;
else if(str[i] == 'L') ri++;

if(( le>=21 || ri>=21 ) && abs(le-ri)>=2 ){
cout<<le<<":"<<ri<<endl; le = ri = 0;
}
}
cout<<le<<":"<<ri<<endl;

return 0;
}

可能是因为:在Windows下,两行文本间有回车符 (ASCII 13) 和 换行符 (ASCII 10)。而在Linux下,只有换行符 (ASCII 10)。???类似。

P1086 花生采摘 排序+贪心

目描述

鲁宾逊先生有一只宠物猴,名叫多多。这天,他们两个正沿着乡间小路散步,突然发现路边的告示牌上贴着一张小小的纸条:“欢迎免费品尝我种的花生!――熊字”。

鲁宾逊先生和多多都很开心,因为花生正是他们的最爱。在告示牌背后,路边真的有一块花生田,花生植株整齐地排列成矩形网格(如图1)。有经验的多多一眼就能看出,每棵花生植株下的花生有多少。为了训练多多的算术,鲁宾逊先生说:“你先找出花生最多的植株,去采摘它的花生;然后再找出剩下的植株里花生最多的,去采摘它的花生;依此类推,不过你一定要在我限定的时间内回到路边。”

img

我们假定多多在每个单位时间内,可以做下列四件事情中的一件:

1) 从路边跳到最靠近路边(即第一行)的某棵花生植株;

2) 从一棵植株跳到前后左右与之相邻的另一棵植株;

3) 采摘一棵植株下的花生;

4) 从最靠近路边(即第一行)的某棵花生植株跳回路边。

现在给定一块花生田的大小和花生的分布,请问在限定时间内,多多最多可以采到多少个花生?注意可能只有部分植株下面长有花生,假设这些植株下的花生个数各不相同。

例如在图2所示的花生田里,只有位于(2,5),(3,7),(4,2),(5,4)的植株下长有花生,个数分别为13,7,15,9。沿着图示的路线,多多在21个单位时间内,最多可以采到37个花生。

说明

noip2004普及组第2题

Code $O(nlogn)$

排序+贪心。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;


struct plant{
int pea, x, y;
};

bool cmp(const plant a, const plant b){
return a.pea > b.pea;
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
/*
#ifndef OJ
freopen("OJ.in", "r", stdin);
#endif*/
int M,N,K; cin>>M>>N>>K;
vector<plant> a;
for(int i = 0; i < M; i++){
for(int j = 0; j < N; j++){
int tmp; cin>>tmp;
plant tem; tem.pea = tmp; tem.y = i+1; tem.x = j; //Note: y start from 0
a.push_back(tem);
}
}

sort(a.begin(), a.end(), cmp);

int ans = 0, i = 0, Size = a.size();
//cout<<"K:"<<K<<endl;
if(K >= 2*a[i].y + 1){
K -= a[i].y + 1;
ans += a[i].pea;
//cout<<"K1:"<<K<<" pea:"<<a[i].pea<<endl;
while(i+1 < Size){
if( K >= (abs(a[i].x - a[i+1].x) + abs(a[i].y - a[i+1].y) + a[i+1].y + 1)){
K -= abs(a[i].x - a[i+1].x) + abs(a[i].y - a[i+1].y) + 1;
ans += a[i+1].pea;

//cout<<"K:"<<K<<" pea:"<<a[i+1].pea<<endl;
i++;
}
else break;
}
}

cout<<ans;

return 0;
}

P1098 字符串的展开

题目描述

在初赛普及组的“阅读程序写结果”的问题中,我们曾给出一个字符串展开的例子:如果在输入的字符串中,含有类似于“d-h”或者“4-8”的字串,我们就把它当作一种简写,输出时,用连续递增的字母或数字串替代其中的减号,即,将上面两个子串分别输出为“defgh”和“45678“。在本题中,我们通过增加一些参数的设置,使字符串的展开更为灵活。具体约定如下:

(1) 遇到下面的情况需要做字符串的展开:在输入的字符串中,出现了减号“-”,减号两侧同为小写字母或同为数字,且按照ASCII码的顺序,减号右边的字符严格大于左边的字符。

(2) 参数p1p_1p1:展开方式。p1=1p_1=1p1=1时,对于字母子串,填充小写字母;p1=2p_1=2p1=2时,对于字母子串,填充大写字母。这两种情况下数字子串的填充方式相同。p1=3p_1=3p1=3时,不论是字母子串还是数字字串,都用与要填充的字母个数相同的星号“*”来填充。

(3) 参数p2p_2p2:填充字符的重复个数。p2=kp_2=kp2=k表示同一个字符要连续填充k个。例如,当p2=3p_2=3p2=3时,子串“d-h”应扩展为“deeefffgggh”。减号两边的字符不变。

(4) 参数p3p_3p3:是否改为逆序:p3=1p3=1p3=1表示维持原来顺序,p3=2p_3=2p3=2表示采用逆序输出,注意这时候仍然不包括减号两端的字符。例如当p1=1p_1=1p1=1、p2=2p_2=2p2=2、p3=2p_3=2p3=2时,子串“d-h”应扩展为“dggffeeh”。

(5) 如果减号右边的字符恰好是左边字符的后继,只删除中间的减号,例如:“d-e”应输出为“de”,“3-4”应输出为“34”。如果减号右边的字符按照ASCII码的顺序小于或等于左边字符,输出时,要保留中间的减号,例如:“d-d”应输出为“d-d”,“3-1”应输出为“3-1”。

说明

40%的数据满足:字符串长度不超过5

100%的数据满足:1≤p1≤3,1≤p2≤8,1≤p3≤21。字符串长度不超过100

NOIP 2007 提高第二题

Code

一次过~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;

bool verify(char a, char b){ //验证a,b满足 偏序+同类 条件
if((a < b) &&(a<='9' && a>='0') && (b<='9' && b>='0')) return 1;
else if((a < b) &&(a<='z' && a>='a') && (b<='z' && b>='a')) return 1;
return 0;
}

void print(char le, char ri, int p1, int p2, int p3){
char a[1000];
int dex=0;
for(char i = le + 1; i < ri; i+=1){
if(le<='9' && le>='0'){//数字
if(p1 == 3){ //填"*"号
for(int k = 0; k < p2;++k) a[dex++] = '*';
}
else{ //普通模式
for(int k = 0; k < p2;++k) a[dex++] = i;
}
}
else if(le<='z' && le>='a'){ //字母
if(p1 == 3){ //填"*"号
for(int k = 0; k < p2;++k) a[dex++] = '*';
}
else if(p1 == 2){ //大写
for(int k = 0; k < p2;++k) a[dex++] = i + 'A' - 'a';
}
else{ //普通模式
for(int k = 0; k < p2;++k) a[dex++] = i;
}
}
}
//output
if(p3 == 2){ //逆序
for(int j = 0; j < dex; j++){
cout<<a[dex - j - 1];
}
}
else{
for(int j = 0; j < dex; j++){
cout<<a[j];
}
}
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
/*
#ifndef OJ
freopen("OJ.in", "r", stdin);
#endif*/
int p1,p2,p3; cin>>p1>>p2>>p3;
string a; cin>>a;

int len = a.length();
for(int i = 0; i < len; ++i){
if(a[i] == '-' && verify(a[i-1],a[i+1])) print(a[i-1], a[i+1], p1, p2, p3);
else cout<<a[i];
}

return 0;
}

*P3952 时间复杂度

题目描述

小明正在学习一种新的编程语言 A++,刚学会循环语句的他激动地写了好多程序并 给出了他自己算出的时间复杂度,可他的编程老师实在不想一个一个检查小明的程序, 于是你的机会来啦!下面请你编写程序来判断小明对他的每个程序给出的时间复杂度是否正确。

A++语言的循环结构如下:

1
2
3
F i x y
循环体
E

其中F i x y表示新建变量 iii(变量 iii 不可与未被销毁的变量重名)并初始化为 xxx, 然后判断 iii 和 yyy 的大小关系,若 iii 小于等于 yyy 则进入循环,否则不进入。每次循环结束后 iii 都会被修改成 i+1i +1i+1,一旦 iii 大于 yyy 终止循环。

xxx 和 yyy 可以是正整数(xxx 和 yyy 的大小关系不定)或变量 nnn。nnn 是一个表示数据规模的变量,在时间复杂度计算中需保留该变量而不能将其视为常数,该数远大于 100100100。

“E”表示循环体结束。循环体结束时,这个循环体新建的变量也被销毁。

注:本题中为了书写方便,在描述复杂度时,使用大写英文字母“O”表示通常意义下“Θ”的概念。

说明

【输入输出样例解释1】

第一个程序 iii 从 1 到 1 是常数复杂度。

第二个程序 xxx 从 1 到 nnn 是 nnn 的一次方的复杂度。

第三个程序有一个 F 开启循环却没有 E 结束,语法错误。

第四个程序二重循环,nnn 的平方的复杂度。

第五个程序两个一重循环,nnn 的一次方的复杂度。

第六个程序第一重循环正常,但第二重循环开始即终止(因为nnn远大于100,100大于4)。

第七个程序第一重循环无法进入,故为常数复杂度。

第八个程序第二重循环中的变量 xxx 与第一重循环中的变量重复,出现语法错误②,输出 ERR

【数据规模与约定】

对于 30%30\%30%的数据:不存在语法错误,数据保证小明给出的每个程序的前 L/2L/2L/2 行一定为以 F 开头的语句,第 L/2+1L/2+1L/2+1 行至第 LLL 行一定为以 EEE 开头的语句,L≤10L \le 10L≤10,若 xxx、yyy 均 为整数,xxx 一定小于 yyy,且只有 yyy 有可能为 nnn。

对于 50%50\%50%的数据:不存在语法错误,L≤100L \le 100L≤100,且若 xxx、yyy 均为整数,xxx 一定小于 yyy, 且只有 yyy 有可能为 nnn。

对于 70%70\%70%的数据:不存在语法错误,L≤100L \le 100L≤100。

对于 100%100\%100%的数据:L≤100L \le 100L≤100。


如果需要Hack请私信@zhouyonglong或发讨论,提供数据和能Hack掉的P3952或本题的AC记录。

Code

做这个题可以大体体现出一个人的耐心和模拟能力。。。

以后再做。。orz

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;


int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
/*
#ifndef OJ
freopen("OJ.in", "r", stdin);
#endif*/
int t; cin>>t;
for(int i = 0; i < t; i++){
bool error_check = 1; //语法检查标记
char[26] = (0); //变量使用栈
int match = 0; //括号匹配(F+E)
int L; cin>>L;
string complex; cin >> complex;
int w;
if(complex == "O(1)") w = 0;
else w = (int)(complex[4] - '0');
for(int j = 0; j < L; j++){
char Mark, Var, X, Y;
cin>>Mark;
if(Mark == 'F'){

match++;
}
else{
if(j == 0) break;
match--;
if(match < 0){
error_check = 0;
continue;
}
}
}

if(match != 0){
error_check = 0;
continue;
}

if(error_check == 0){
cout<<"ERR"; //如果最后不匹配,输出ERR
}
}

return 0;
}
0%