新手场和普及场前6关

新手场

顺序与分支

P1422 小玉家的电费

控制输出精度:cout.xxx(); 待查询


P1089 津津的储蓄计划

注意 int 和 float 相乘,输出格式用 “%d” 数字会面目全非


P1909 买铅笔

INT_MAX存在<limits.h>里,不加.h也不行

循环

P1035 级数求和

  • 我写了一个求和的函数Sn(int x),然后把x从1到n开始试。这样其实n=3的时候,又要从新从1加到3。n等于4的时候,又要重新从1加到4。上一次的结果就全部浪费了。导致最后超时。所以要边加边判断。
  • 涉及到int和float夹杂在一起的运算,特别是结果要是float的。一定要处处注意不要写整形参数,1要写成1.0 0要写成0.00
  • 仔细分析n++后,最后输出的那个n,是ans+1了还是就是ans。
  • 用double别用float
  • 重刷标记

数组

P1047 校门外的树

数组声明后不遍历赋值,并不是默认都是0.(不同于Vector)

延伸:

局部数组:没有默认值,如果声明的时候不定义,则会出现随机数(undefined);如果声明的长度与赋值长度不相等,则有,声明的长度>赋值长度,后面用0补足,声明的长度>赋值长度,发生编译错误;

全局数组:声明时不赋值,默认值为0

指针new:动态获取的内存,默认值undefined

简单字符串

P1308 统计单词数

要高性能?怎么都做错了。

  • Mark

关键:在找单词出现的第一个位置时,因为有空格来区分单词,必须完全匹配。需要这样处理

1
2
3
target = " "+target+" ";
article = " "+article+" ";
int ans = article.find(target);

过程函数与递归

P1028 数的计算

递归的方法我写出来了。但是超时。

我每次跑都会把之前算过的值重新跑一遍。最后相当于浪费了很多。

解决方法就是:用数组存每个n的结果,然后读取就可以了。

P1036 选数

就是递归写排列组合,我竟写了这么久。

不写代码就是手生啊。

Boss战入门1

P2089 烤鸡

走前就是写不出来思绪混乱。周末回来后,思路比较清晰。划重点:学会把递归的现有结果暂存到数组中!然后把数组当做变量传入下一次递归。思路清晰。

Boss战入门2

P1464 Function

这题有个题解说用”记忆宏”,如下:(类似树状数组里定义左右孩子)

#define W_MEM(x,y,z) (w_mem[x][y][z] ? w_mem[x][y][z] : w_mem[x][y][z] = w(x, y, z))

P1014 Cantor表

简单题,不看

P1307 数字反转

j—到i后的情况 是if(j>i)还是if(j>=i)

最好模拟一下。不然有些极端情况还是考虑不到。

==>说白了不就是如果j==i的时候要不要执行下面的语句

普及练习场

简单模拟

P1003 铺地毯

  • 开数组开这么大干啥?没必要真的用数组模拟出一个地面。

    只需要用一个数组记录下来每次输入的四个坐标就行了啊。

    • 边输入(cin),可以直接把数存到数组里

P1067 多项式输出

  • 没考虑系数是1的情况 输出了 1x -1x这种尴尬
  • 没考虑x次数是1输出 x^1

P1056 排座椅

贪心入门 涉及知识点主要:

  • 结构体排序
1
2
3
bool cmp(s a,s b){//注意这个比较函数一定要写全局里
return a.value<b.value;//这就是小的放前面
}
  • 利用结构体排序,达到对一组数的值排序后,输出原下标的结果

    (因为题目输出结果是下标从小到大输出)开始我比较笨,先把结构体排序后。又把下标存起来。又排序。

    正解:直接写两个排序规则,第一个是按值,第二个是按下标:

    1
    2
    sort(ans1.begin(),ans1.end(),cmp);
    sort(ans1.begin(),ans1.begin()+K,cmp2);

    这样第一行对值排序了。 第二行拿出排序后的前K个(要求输出的),再按下标排序就符合输出要求了。

交叉模拟

P1031 均分纸牌

  • 想到思路很重要,这一题竟然只要每次都从左往右移动,就能成功。
  • 在循环中,遇到可以跳过(if(xxx)continue;)的情况,记得要把一些标志位(如flag)清空掉。不然虽然循环continue了,但上一次循环的”脏数据”会继续影响下面的循环。

P1042 乒乓球

简单题Pass

P1098 字符串的展开

这题繁琐不要重做,但要看看这几个要点

  • replace()

    我是把'a'换成str,然后注意的就是,第二个参数是长度。

    所以要写成s.replace(s.find(' '),1,str) 开始把第二个参数当成了

  • transform(temp.begin(),temp.end(),temp.begin(),::toupper); 这种写法要会。特别是最后一个参数。

P1086 花生采摘

花生这题简单的模拟。顺利AC。出了点小差错:

  • if的情况写完没有对应的else。

    这题里,我对数组循环遍历。if(xxx)就继续往下执行。结果if不成立没有对循环break;导致循环继续跑下去。要谨慎!

排序

P1177 【模板】快速排序

惊喜啊!我写快排超时了!!!纳尼。。。太好了啊。如果没有洛谷OJ。我都不知道其实我的快排都是有问题的!!!赶紧去改了!

看了这篇题解,https://www.luogu.org/blog/adamding/solution-p1177 和这篇博客https://blog.csdn.net/hacker00011000/article/details/52176100说明了快速排序的几个问题:

  • 已经有序的情况,每次只能安排好第一个元素 退化成O(n^2)的冒泡
  • 区间分割较小时,还是会层层递归
  • 大量重复数字时,(快排是不稳定的嘛),也会处理。

针对上面三个情况,楼主提出三种优化:

  • 随机比较
  • 小区间直接插入排序
  • 在一次分割结束后,可以把与Key相等的元素聚在一起,继续下次分割时,不用再对与key相等元素分割

哎。我最后也没弄明白为啥它这个解法能过。

https://blog.csdn.net/u011815404/article/details/79889355

问了龙哥,果然好使。上面这个人的写法。更像归并!

主要思想:取中间的数做标杆。然后每一趟循环之后,数组的左右两侧,左边的一定小于右边的。


最后找到了我的错误:就是这种情况:

1
int m = a[(i+j)/2];

是用m取出来和后面的比较呢。还是

1
2
int m = (i+j)/2;
a[m];

这样呢?

一定要看后面 i和j 会不会变啊!

然后根据情况决定。


排序这一组后面的题,借助于sort函数,基本都没写。但是基础的几个排序算法我还是很需要去加深的。就先这样吧继续往下刷了。

排序Ex

P1583 P1051 P1093

  • 不要重做标记

    P1583本身很简单,只不过题意中有个序号,有个编号。要看清都用来做什么、输出什么。

    后面两个题一样没技术含量

字符串

P1012 拼数

令人窒息的操作

1
2
3
bool cmp(string s1,string s2){
return s1+s2<s2+s1;
}

P1603 斯诺登的密码

虽然AC了。但我竟然之前傻傻地要把int转成string再比较。这题直接用int输出就行啊。

贪心

P1090 合并果子

开始我每次都用sort()对数组拍一次序,找到最小的2组合并。但是:超时了。

对啊。只要找到最小的两组就行了。为啥要对整个数组排序呢。那样复杂度怎么也是$\Theta(nlog_n)$及以上的啊。而我遍历整个数组找到最小的数只需要n次。

看到一个STL优先队列的解法(重点记一下声明时的三个参数

):

1
2
3
4
5
6
7
8
9
10
11
12
13
priority_queue<int,vector<int>,greater<int> >q;
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>x,q.push(x);
while(q.size()>=2){
int a=q.top(); q.pop();
int b=q.top(); q.pop();
ans+=a+b;
q.push(a+b);
}
cout<<ans<<endl;
return 0;
}

看来proirty可以实现每次有插入删除的时候都执行换位操作。

需要注意的是,优先队列里使用从greater排序,首元素最小(不同于sort里的调用)。所以题解中的q.top以及q.pop都是针对【首元素】的

查了下:priority_queue比较方式默认用operator<,所以如果把后面2个参数缺省的话,优先队列就是大顶堆(降序),队头元素最大

P1181 数列分段Section I

讨论:这题为何贪心是最优?

贪心多用反证法证明、如果这样划分不是最优,则假设有xxx解法是最优,最后推出矛盾。

P1208 [USACO1.3]混合牛奶 Mixing Milk

用sort对结构体排序。结果呢,人家数据是5000个一样的。神奇的事情发生了。这个用例能不能过,竟然就在一=号只差:

1
2
3
4
5
6
7
bool cmp(farmer f1,farmer f2){
if(f1.price!=f2.price)
return f1.price<f2.price;
else
return f1.count>f2.count;//这样就能过
return f1.count>=f2.count;//这样就不能过!!!
}

以后还是不要多加=号了!

猜测是。5000个一样的数据情况下,加了等号会导致相等的两个比较时仍做位置交换,导致时间变慢。