题解 CF896E 【Welcome home, Chtholly】
phil071128 · · 题解
蒟蒻的第一篇题解，希望管理大大能够通过
基础做法：暴力+卡常
思路简化： 输入n个数，存到一个一维数组里，然后再执行m次操作
每次操作输入4个数:opt,left,right,x
操作分为两种
- 当第opt==1：
将数组left~right区间里所有>x的数都减去x
- 当opt==2：
统计出数组left~right区间里所有等于x的数的个数
开始优化
一级优化方法：
难度：入门-
把cin都改成scanf()，把cout都改成printf()
把所有不会出现负数的变量都加上register
#include <bits/stdc++.h>
using namespace std;
const int MA=1e5+5;
int a[MA];
int n,m;
float x;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
while(m--){
register int opt,l,r,ans=0;
//ans=0;
scanf("%d%d%d%f",&opt,&l,&r,&x);
if(opt==1){
for(register int i=l;i<=r;i++) a[i]-=(a[i]>x)?x:0;
}else{
for(register int i=l;i<=r;i++){
ans+=(a[i]==x);
}
//cout<<ans<<endl;
printf("%d\n",ans);
}
}
return 0;
} 由于CF的题如果没AC，仅仅会显示第一个没有AC的点 （很难受的）
1级优化记录
测试点4运行了3秒,肯定超了
(不然这题怎么能叫做黑题？？？？）
二级优化
难度：普及-
没错，就是我们熟悉的快读
一篇极好的快读博客
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}然后，代码稍微改一下
#include <bits/stdc++.h>
using namespace std;
const int MA=1e5+5;
int a[MA];
int n,m;
float x;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
int main(){
n=read();
m=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
while(m--){
register int opt,l,r,ans=0;
opt=read();
l=read();
r=read();
x=read();
if(opt==1){
for(register int i=l;i<=r;i++){
if(a[i]>x){
a[i]-=x;
}
}
}else{
for(register int i=l;i<=r;i++){
if(a[i]==x){
ans++;
}
}
printf("%d\n",ans);
}
}
return 0;
} 好家伙，还是超时了 (不然这题怎么能叫做黑题？？？？）
三级优化（核心重点）
仅需在代码开始加上这三行代码（重点）
这也就是传说中的卡常 通过各种奇技淫巧让程序跑的更快
#pragma comment(linker,"/stack:200000000")
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")总共用时40.66s，#4用时2.32s，速度不止快了两倍
那这代码具体是什么意思呢？
1.#pragma comment(linker,"/stack:200000000")：手动扩充栈
2.#pragma GCC optimize("Ofast,no-stack-protector")：手动开Ofast（一种优化方式，O2优化的进阶）
3.#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")：开启各种奇怪的指令集，进行编译的优化当然，用了这优化以后，不用快读也可以轻松过
最后，送给大家一份卡常大全
#define fastcall __attribute__((optimize("-O3")))
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")用法：粘在头文件后面就行
转载自：https://www.cnblogs.com/qianr/p/13246543.html
AC代码：
#include <bits/stdc++.h>
#pragma comment(linker,"/stack:200000000")
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
const int MA=1e5+5;
int a[MA];
int n,m;
float x;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
while(m--){
register int opt,l,r,ans=0;
scanf("%d%d%d%f",&opt,&l,&r,&x);
if(opt==1){
for(register int i=l;i<=r;i++) a[i]-=(a[i]>x)?x:0;
}else{
for(register int i=l;i<=r;i++){
ans+=(a[i]==x);
}
printf("%d\n",ans);
}
}
return 0;
//再次感谢管理大大
} 这tm才叫做黑题