1 1 有关long long 运算的建议 打完代码一定要考虑long long问题,该开的一定要开! 方案1 取模三件套 int add(int a,int b){ return (a+b)%MOD; } int mul(int a,int b){ return 1LL*a*b%MOD; } int sub(int a,int b){ return (a-b+MOD)%MOD; } 快速乘 LL mul(LL x,LL y,LL MOD){ LL res=(x*y-(LL)((double)x*y/MOD+0.1)*MOD)%MOD; if(res<0)res+=MOD; return res; } 方案2 #define int_ long long 很浪费空间\时间,不建议… 2 空间消耗问题 3 栈空间问题 关于爆栈: 两种情况,递归层数太多(RE),递归时传了一个数组[还包括STL(set,bitset,map…)](RE或MLE) 解决方案: 4 重载运算符的运用 bool operator <(const state &b)const{//STL习惯用<符号 return step>b.step; } 5 STL 用STL的时候要小心边界,很容易崩溃 5.1 set/multiset s.lower_bound(val)——寻找第一个大于等于val valval的s ss中的元素(被坑过两次,一次是某次Atcoder 还有一次是NOIP 开车旅行) s.upper_bound(val)——set用这东西好像没用 s.find(val)——找到当前=val =val=val的迭代器。 s.erase(*it)——一定注意里面是迭代器,如果要删val的话需要先s.find(val)。 s.count(val)——multiset才用的着,元素中=val =val=val的个数。 5.2 string C++的string真的很好用…虽然很慢…但在模拟题中是很实用的(CSP能用)。 s.substr(l,len)取以l开始的后面len个字符,len如果省去的话就默认直到结尾。 s.substr(l,len)删除l开始的后面len个字符,len如果省去的话就默认直到结尾,与上一个(大概是)反函数。 s.find(string)找string是否存在,存在返回第一个出现的第一个字符所在位置,否则返回string::npos。 5.3 vector 不建议用…因为有些操作是可以被卡到O(n) O(n)O(n)的。 G.resize(siz)预留siz的空间,[siz,end)的全部删掉。 5.4 bitset S.set(idx,val)将idx位置置为val,val省略是默认为1。 S.count()数bitset中1的个数。 S.size()bitset的大小。 S.test(idx)查询当前下标是否为1。 S.any()查询bitset中是否有1。 S.all()查询bitset中是否全部都是1。 eg.biset Floyd 闭包 for(register int i=1;i<=n;i++)//相当于之前的k,要放在外面 for(register int j=1;j<=n;j++) if(d[j][i])d[j]|=d[i]; 6 CE/文件操作相关 众所周知CE和MLE是OI中最可怕的两种错误 注意一些变量名在NOI Linux下是禁用的! 最可怕的就是x1,y1这种东西…还有一些常见的英文单词,因此拼写的时候尽量在英文单词中删几个字母(不过像slove这样的单词就没必要了,今年我还是别用process了)。 #include<cstdio> #include<iostream> 头文件一定要加!虽然可能能够通过编译! 还有要注意莫名其妙的多余隐藏字符(当然这个比较玄学)。 freopen('road.in','r',stdin); freopen('road.out','w',stdout); 必须一个单词不多不少!空格也不行!! 7 对拍相关 考试的时候肯定是首先测大样例,输出多的时候要用fc A.out B.out。 然后自己出几组小数据,如果行的话构造一些大数据。 如果考试时间十分充足,一定要进行对拍 以下是对拍的程序: #include<iostream> #include<windows.h> using namespace std; int main() { int testdata=100; while(1) { testdata--; system('makedata_plus.exe %random% > data.in');//%random%是随机参数,可加可不加 system('cheat.exe < data.in > cheat.out');//< 就是读入 > 就是输出 system('bf.exe < data.in > bf.out'); if(system('fc cheat.out bf.out'))break; } if(testdata==0) cout<<'no error'<<endl; else cout<<'error'<<endl; system('pause'); return 0; } 随机生成数据(仅供参考): #include <bits/stdc++.h> #define LL long long #define MAXN 200000 #define RANGE 100000 using namespace std; stringstream ss; int n,fa[MAXN+5],p[MAXN+5]; int get_num(){ return 1LL*rand()*rand()%(RANGE*2)-RANGE; } int xfind(int x){ return (fa[x]==x)?x:fa[x]=xfind(fa[x]); } int main(int argc, char *argv[]) { int i=10,kd=0; if(argc){ ss.clear(); ss<<argv[1]; ss>>i; //kd=(i/20)%2; i%=20; } int data[21][3]={ {1,1,1}, {10,2,6}, {17,4,10}, {35,5,8}, {70,3,14}, {200,5,18}, {200,6,37}, {500,20,868}, {500,20,742}, {1000,100,998}, {1000,100,997}, {1000,99,996}, {1000,99,995}, {1000,100,994}, {1000,100,993}, {1000,99,992}, {1000,99,991}, {1000,100,990}, {1000,100,989}, {1000,99,988}, {1000,99,987}}; static char buf[1000]; srand(time(NULL)); n=data[i][0]; printf('%d\n',n); p[1]=1; for(int j=2;j<=n;j++) fa[j]=1LL*rand()*rand()%(j-1)+1,p[j]=j; for(int j=1;j<=n;j++) printf('%d ',get_num()); printf('\n'); for(int j=1;j<=n;j++) printf('%d ',get_num()); printf('\n'); if(kd){ for(int j=2;j<=n;j++)printf('%d %d\n',j-1,j); return 0; }else{ random_shuffle(p+1,p+n+1); for(int j=2;j<=n;j++) printf('%d %d\n',p[fa[j]],p[j]); } return 0; } 8 一些小细节 倍增:注意先枚举k再枚举i。 线段树如果有负下标应将mid设为(l+r)>>1,不能用(l+r)/2,因为C++除法向取整。 多关键字更新答案一定要注意顺序。 example: if(maxh==h&&mxa>a)mxa=a; if(maxh<h)maxh=h,mxa=a;//不能够交换顺序 4.以后检查代码的时重点还是应该在检查是否手残上:)因为我经常手残:) 5.多组数据一定要清空!!清空!!清空!! 数据千万条,清空第一条。 多测不清空,爆零两行泪。 9 考试策略相关 拿到题目首先看第一页的时空限制以及文件及题目名(感受出题人的毒瘤)。 然后看题面,最好把三道题目都读完,预估一下总体难度如何,最好心里排个序,但在NOIP这种情况还是很少见(除了NOIP2016 day1)。 然后开始做题,建议从子任务一步一步做着走,这在NOIP中是十分有用的,因为出题人会给你很多提示,但平时的考试就很难说了… 通过的测试点可以在上面打个标记,可以让你有一种成就感。 选择打正解还是打暴力一直是我很头疼的事情。按理来说NOIP的部分分大多是思维型的,不会浪费太多时间。 做完一道难题可以去上上厕所,实测很实用。 ———————————————— 本文来源:https://blog.csdn.net/qq_34940287/article/details/102066630 |
|