admin管理员组文章数量:1567301
杂
区间和(离散化)
题目链接:802. 区间和 - AcWing题库
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 300010; //n次插入和m次查询相关数据量的上界
int n, m;
int a[N];//存储坐标插入的值
int s[N];//存储数组a的前缀和
vector<int> alls; //存储(所有与插入和查询有关的)坐标
vector<pair<int, int>> add, query; //存储插入和询问操作的数据
int find(int x) { //返回的是输入的坐标的离散化下标
int l = 0, r = alls.size() - 1;
while (l < r) {
int mid = l + r >> 1;
if (alls[mid] >= x) r = mid;
else l = mid + 1;
}
return r + 1;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
int x, c;
scanf("%d%d", &x, &c);
add.push_back({x, c});
alls.push_back(x);
}
for (int i = 1; i <= m; i++) {
int l , r;
scanf("%d%d", &l, &r);
query.push_back({l, r});
alls.push_back(l);
alls.push_back(r);
}
//排序,去重
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
//执行前n次插入操作
for (auto item : add) {
int x = find(item.first);
a[x] += item.second;
}
//前缀和
for (int i = 1; i <= alls.size(); i++) s[i] = s[i-1] + a[i];
//处理后m次询问操作
for (auto item : query) {
int l = find(item.first);
int r = find(item.second);
printf("%d\n", s[r] - s[l-1]);
}
return 0;
}
/*作者:liangshang
链接:https://www.acwing/solution/content/13511/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。*/
区间合并(区间合并)
题目链接:803. 区间合并 - AcWing题库
问题:给出多个区间,合并有交集的区间,最后得出剩余的单独区间有多少个。
思路:
用维护左右端点的数据typedef pair<int, int> PII; typedef pair<int, int> PII;
区间之间分为3种情况:完全没有交集,完全合并为一个大区间,有交集。
对vector<PII> segs排序
维护一个区间,每次这个区间对比下一个区间的3种情况。没有交集就存入vector<PII> res;
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
void merge(vector<PII> &segs) //模版
{
vector<PII> res;
sort(segs.begin(), segs.end());
int st = -2e9, ed = -2e9;
for (auto seg : segs)
if (ed < seg.first)
{
if (st != -2e9) res.push_back({st, ed});
st = seg.first, ed = seg.second;
}
else ed = max(ed, seg.second);
if (st != -2e9) res.push_back({st, ed});
segs = res;
}
int main()
{
int n;
scanf("%d", &n);
vector<PII> segs;
for (int i = 0; i < n; i ++ )
{
int l, r;
scanf("%d%d", &l, &r);
segs.push_back({l, r});
}
merge(segs);
cout << segs.size() << endl;
return 0;
}
数学
2582. 递枕头(模拟)(数学)
问题描述:
n
个人站成一排,按从 1
到 n
编号。
最初,排在队首的第一个人拿着一个枕头。每秒钟,拿着枕头的人会将枕头传递给队伍中的下一个人。一旦枕头到达队首或队尾,传递方向就会改变,队伍会继续沿相反方向传递枕头。
- 例如,当枕头到达第
n
个人时,TA 会将枕头传递给第n - 1
个人,然后传递给第n - 2
个人,依此类推。
给你两个正整数 n
和 time
,返回 time
秒后拿着枕头的人的编号。
思路:暴力模拟或者数学找规律
class Solution {
public:
int passThePillow(int n, int time) {
/*找规律*/
time %= (n - 1) * 2;
return time < n ? time + 1 : n * 2 - time - 1;
}
};
/*
模拟:
int ans = 1, k = 1;
while (time--) {
ans += k;
if (ans == 1 || ans == n) {
k *= -1;
}
}
return ans;
*/
AcWing 868. 筛质数(数学)(筛质数)
问题描述:给一个数n,筛出1到n里所有的质数的个数
思路与理解:
1.朴素:从2开始,筛出每个2的倍数,比如4,6,8,10.再从3开始筛出每个3的倍数,6,9,12,
代码:
#include <iostream>
#include <algorithm>
using namespace std;
const int N= 1000010;
int primes[N], cnt;
bool st[N];
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (st[i]) continue;
primes[cnt ++ ] = i;
for (int j = i + i; j <= n; j += i)
st[j] = true;
}
}
int main()
{
int n;
cin >> n;
get_primes(n);
cout << cnt << endl;
return 0;
}
蛇形填数(数学)
题目链接:蛇形填数 - 蓝桥云课 (lanqiao)
题解:(蓝桥杯填空题原题)这个题就是个找规律题。根据题目提示找到数与数之间的规律。
2020年第十一届蓝桥杯 - 省赛 - C/C++大学生A组 - C.蛇形填数_哔哩哔哩_bilibili
代码:
#include <iostream>
using namespace std;
int main()
{
int n=20,ans=1;
for (int i=0;i<n;i++)
{
ans+=i*4;
}
cout <<ans<<endl;
return 0;
}
P2241 统计方形(数学)
描述:给一个n * m 的矩形,得出这个矩形里面有多少个正方形和长方形
代码:
#include<iostream>
using namespace std;
long long n,m,rec,sqr;
int main() {
cin>>n>>m;
for(int i=0; i<n; i++)//循环,从n-0到n-(n-1)
for(int j=0; j<m; j++) {//循环,从m-0到m-(m-1)
if(i==j) sqr+=(n-i)*(m-j);//如果i==j,说明是正方形
else rec+=(n-i)*(m-j);//如果不等说明是矩形
}
cout<<sqr<<" "<<rec<<endl;//输出
return 0;
}
详细理解见:P2241 统计方形(数据加强版) - 洛谷 | 计算机科学教育新生态 (luogu)
此类数学题 遇到了就会,没遇到就不会。当公式记住了
if(i==j) sqr+=(n-i)*(m-j);//如果i==j,说明是正方形
else rec+=(n-i)*(m-j);//如果不等说明是矩形
bhq的小物块(数学)
链接:L-bhq的小物块_第五届山东师范大学与齐鲁工业大学ICPC新生联谊赛 (nowcoder)
描述:
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
const double PI = M_PI;
void solve(){
int n;
cin >> n;
cout << (int64)(PI * pow(10L, n)) << endl;
}
int main(){
int t;
cin >> t;
while(t-- > 0) solve();
}
学习了:
1.pow(10L, n)
表示10的n次方,10L 的 L 表示这个10是 long 型的
2.库里面的pi值 const double PI = M_PI;
P1143 进制转换
链接:P1143 进制转换 - 洛谷 | 计算机科学教育新生态 (luogu)
描述:
代码:
#include<bits/stdc++.h>
using namespace std;
string a;
int c[10000000],d,e,f,g,sum,ans;
int main()
{
scanf("%d",&d);
cin>>a;
scanf("%d",&f);
/*for(int x=0;x<a.size();x++){
if(a[x]<'A'){
e=pow(d,a.size()-x-1);
e*=(a[x]-'0');
sum+=e;
}
else{
e=pow(d,a.size()-1-x);
e*=(a[x]-'A'+10);
sum+=e;
}
}手写方法转换成10进制*/
sum=stoi(a,NULL,d); //d进制转换成10进制
while(sum>0){
c[g++]=sum%f;
sum/=f; //sum(10进制)转换成f进制
}
for(int x=g-1;x>=0;x--){
if(c[x]>=10)printf("%c",c[x]+'A'-10);
else printf("%d",c[x]);
}
return 0;
}
学习的都在代码里面了:
1. sum=stoi(a,NULL,d); //d进制转换成10进制
2.
//sum(10进制)转换成f进制
while(sum>0){
c[g++]=sum%f;
sum/=f;
}
for(int x=g-1;x>=0;x--){
if(c[x]>=10)printf("%c",c[x]+'A'-10);
else printf("%d",c[x]);
}
885. 求组合数 I(排列组合)
链接:885. 求组合数 I - AcWing题库
描述:
代码(直接开背):
#include<iostream>
using namespace std;
const int mod = 1e9+7;
long long f[2010][2010];
int main()
{
//预处理
for(int i=0;i<=2000;i++)
{
for(int j=0;j<=i;j++)
{
if(!j) f[i][j]=1;
else f[i][j]=(f[i-1][j-1]+f[i-1][j])%mod;
}
}
int n;
cin>>n;
while(n--)
{
int a,b;
cin>>a>>b;
printf("%ld\n",f[a][b]);
}
}
AcWing 1205. 买不到的数目(数论)(结论题)
链接:1205. 买不到的数目 - AcWing题库
描述:
代码:
#include<bits/stdc++.h>
using namespace std;
int main ()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
int a,b;
cin >>a>>b;
cout <<(a-1)*(b-1)-1<<endl;
return 0;
}
数学结论:如果两个数互质a,b(公约数只有1的两个数叫做互质数。 根据互质数的概念可以对一组数是否互质进行判断。 如:9和11的公约数只有1,则它们是互质数。)则不能凑出来的最大整数是(a-1)*(b-1)-1
1211. 蚂蚁感冒
链接:1211. 蚂蚁感冒 - AcWing题库
描述:
悟:
数学方面 建立好图(画好图)有利于更好的解决问题,然后是学会等价代还思维。就是根据描述等价成一个更易理解和利用的有效条件
1216. 饮料换购
链接:AcWing 1216. 饮料换购 - AcWing
描述:
代码1:直觉的做法
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int res = n;
while (n >= 3)
{
res += n / 3;
n = n / 3 + n % 3;
}
cout << res << endl;
return 0;
}
自己的做法就是这个,可是自己的代码太辣鸡了,忘了%可以直接得到除法之后的余数
代码2:等价代还出结论,换一瓶饮料,少俩盖
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int main()
{
int n;
cin>>n;
int res=n;
while(n>=3)
{
n-=2; //换一瓶饮料,少俩盖
res++;
}
cout<<res;
}
代码3:直觉做法+dfs(练习dfs大法的写法与用法)
#include <iostream>
using namespace std;
int cnt;
int dfs(int u){
if(u<3) return cnt;
dfs(u-2);
cnt++;
}
int main(){
int n;
cin>>n;
cout<<dfs(n)+n;
return 0;
}
#include <iostream>
using namespace std;
int cnt;
int dfs(int u){
if(u<3) return cnt;
dfs(u/3+u%3);
cnt+=u/3;
}
int main(){
int n;
cin>>n;
cout<<dfs(n)+n;
return 0;
}
4956. 冶炼金属(数学)(推公式)
链接:4956. 冶炼金属 - AcWing题库
描述 :
代码:
#include <bits/stdc++.h>
using namespace std;
int main ()
{
int n;
cin >>n;
int mi=0,mx=1e9;
for (int i=1;i<=n;i++)
{
int a,b;
cin >>a>>b;
int r= a/b, l =a/(b+1) +1;
mi = max (mi,l),mx= min (mx,r);
}
cout <<mi <<' '<<mx <<endl;
return 0;
}
细节: 最小值没有取到等于 所以算出的数要加上1,要是取到等于就不用 ,这样就都在那个范围内了(这就是数学转换到计算机编程计算时候的细节注意)
基础算法
史蒂夫的农场(模拟)
题目链接:D-史蒂夫的农场_一石月赛(第八期) (nowcoder)
问题描述:
补:注意题目的意思是没有必须左右相邻的树判断高度,所以例如1 0 0 0 0 0 1的结果 应是5
代码:
#include<iostream>
using namespace std;
const int N=1e5+10;
int nums[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
//int* nums = new int [n];
int mai = 0;
for (int i = 0; i < n; i++) {
cin >> nums[i];
if (nums[i] > nums[mai])
mai = i;
}
long long sum = 0;
for (int i = 0, si = i; i < mai; i++) {
if (nums[i] > nums[si])
si = i;
else sum += nums[si] - nums[i];
}
for (int i = n - 1, si = i; i > mai; i--) {
if (nums[i] > nums[si])
si = i;
else sum += nums[si] - nums[i];
}
cout << sum;
}
做题感想:
关于需要模拟的题就是阅读理解,要是理解错误,还不如一开始就不写,从一开始出发的方向都是错的。
怀疑自己是毒药。永远不要怀疑自己。不要给自己怀疑自己的机会。我信奉条理,只要按照一定的条理就会接近目的,达成目的。自己按照条理,就没有什么是自己的问题。
这题做不出来我还差点怀疑自己最近脑子玩坏了,结果其实就是题的问题。不是我的问题。
P1042 乒乓球(模拟)
链接:P1042 [NOIP2003 普及组] 乒乓球 - 洛谷 | 计算机科学教育新生态 (luogu)
描述:
代码:
#include <iostream>
#include <cstring>
using namespace std;
int win[62503];
int w,l;
int main()
{
char s;
for(int i=1;cin>>s&&s!='E';i++)//循环读入,当读到字符E结束
{
if(s=='W')win[i]=1;
else win[i]=2;
}
//----------------11分制 ----------------
for(int i=1;1;i++)
{
if(win[i]==1)w++;//胜场+1
if(win[i]==2)l++;//负场+1
if(win[i]==0)//读到0则记录结束,输出记录结束前的分数。
{
cout<<w<<":"<<l<<endl<<endl;
break;
}
if(w-l>=2||l-w>=2)
if(w>=11||l>=11)//当双方比分相差大于2且一方分数大等于11输出
{
cout<<w<<":"<<l<<endl;
w=0;//比分清零
l=0;
}
}
w=0;//清零,为21分制计算做准备
l=0;
//----------------21分制 ----------------
for(int i=1;1;i++)//一切同上,唯一区别就是判定从11变为21
{
if(win[i]==1)w++;
if(win[i]==2)l++;
if(win[i]==0)
{
cout<<w<<":"<<l;
break;
}
if(w-l>=2||l-w>=2)
if(w>=21||l>=21)//11变为21
{
cout<<w<<":"<<l<<endl;
w=0;
l=0;
}
}
return 0;//华丽地结束 ㄟ(▔▽▔)ㄏ
}
榫卯结构(模拟)
链接:B-榫卯结构_重庆移通学院第七届大学生程序设计大赛 (nowcoder)
描述:
代码:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n; cin >> n;
string s[n][3];
for (int i = 0; i < 3; i++) {
for (int j = 0; j < n; j++) {
cin >> s[j][i];
}
}
int a[8]; memset(a, 0, sizeof(a));
for (int i = 0; i < n; i++) {
// 第一对
if (s[i][0] == ".#.") a[0]++;
if (s[i][2] == "#.#") a[4]++;
// 第二对
if (s[i][0][2] == '.' && s[i][2][2] == '.') a[1]++;
if (s[i][1][0] == '.') a[5]++;
// 第三对
if (s[i][2] == ".#.") a[2]++;
if (s[i][0] == "#.#") a[6]++;
// 第四对
if (s[i][0][0] == '.' && s[i][2][0] == '.') a[3]++;
if (s[i][1][2] == '.') a[7]++;
}
if (a[0] == a[4] && a[1] == a[5] && a[2] == a[6] && a[3] == a[7]) {
cout << "Yes";
} else {
cout << "No";
}
return 0;
}
这个题就是被卡输入了我当时比赛的时候。我的思路是没有问题的。
输入应该这样理解:只输入三行,一行有n个小字符串。(n就是总共有多少个部件)
然后这个代码我学习了还可以这样定义string数组 string s[n][3]; 这样就是一个数组内的类型就是一个字符串。然后还可以开的是二维,最后再用三维表示某个点的具体位置
比如这个s[i][0][2] == '.' 意思就是 第i个字符串的第1行(0+1)的第3(2+1)个此处的字符(注意是字符)是‘.’
后面的三维s都是这样理解。
也有教训:好好读题。尤其是疑惑的时候,再多认真读读题,一是冷静下来,二是看遗漏了什么
P267 扫雷游戏(模拟)
链接:P2670 [NOIP2015 普及组] 扫雷游戏 - 洛谷 | 计算机科学教育新生态 (luogu)
描述:
代码:
#include<iostream>
using namespace std;
char a[105][105];
int b[105][105],n,m,i,j;//数组定义(二维)
int main()
{
cin>>n>>m;//读入行、列
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
cin>>a[i][j];
if(a[i][j]=='*')//判断:如果是地雷
{
b[i+1][j+1]++;
b[i+1][j-1]++;
b[i+1][j]++;
b[i][j+1]++;
b[i][j-1]++;
b[i-1][j]++;
b[i-1][j+1]++;
b[i-1][j-1]++;//相邻的八个格子都+1
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(a[i][j]=='*')
cout<<"*";//如果是地雷(*) 原样输出
else
cout<<b[i][j];//否则输出数字
}
cout<<endl;
}
return 0;
}
这题居然神奇的不用防止数组越界。可能是+1-1 本来就比较小,而且是从i==1,j==1开始遍历的。
1245. 特别数的和(模拟)
链接:1245. 特别数的和 - AcWing题库
描述:
代码:
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
int res = 0;
for (int i = 1; i <= n; i ++ )
{
int x = i;
while(x)
{
int t = x % 10; // 取出x的个位数
x /= 10; // 取它的上一位
if (t == 0 || t == 2 || t == 1 || t == 9)
{
res += i;
break;
}
}
}
cout << res << endl;
return 0;
}
AcWing 466. 回文日期(模拟)
链接:466. 回文日期 - AcWing题库
描述:
思路 :
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int months[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
bool check(int date)
{
int year = date / 10000;
int month = date % 10000 / 100;
int day = date % 100;
if (!month || month >= 13 || !day) return false;
if (month != 2 && day > months[month]) return false;
if (month == 2)
{
bool leap = year % 4 == 0 && year % 100 || year % 400 == 0;
//判断闰年公式
if (day > 28 + leap) return false;
}
return true;
}
int main()
{
int date1, date2;
cin >> date1 >> date2;
int res = 0;
for (int i = 0; i < 10000; i ++ )
{
int x = i, r = i;
for (int j = 0; j < 4; j ++ ) r = r * 10 + x % 10, x /= 10;
//根据前面4位数造后四位回文
if (r >= date1 && r <= date2 && check(r)) res ++ ;
}
printf("%d\n", res);
return 0;
}
AcWing 1204. 错误票据(模拟)(哈希计数)
链接:AcWing 1204. 错误票据 - AcWing
描述:
思路:
本题关键在于输入,思路很好想就是用哈希计数然后找出特定的只出现2次和0次的数就行
Oj输入钻漏子输入法:
cin >> n;//这个读入没什么用
int minv = INF, maxv = -INF;
int tp;
while(cin >> tp)//直接读到文件尾部停止
{
if(tp < minv) minv = tp;
if(tp > maxv) maxv = tp;
ha[tp] ++;
}
正规c++语法处理整行输入的一组数:
string line;
getline(cin, line); // 忽略掉第一行的回车
while (cnt -- )
{
getline(cin, line);
stringstream ssin(line);
while (ssin >> a[n]) n ++ ;
}
一整行带空格字母:
string str="i am a boy";
istringstream is(str);
string s;
while(is>>s) {
cout<<s<<endl;
}
代码:
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5+5, INF = 0x3f3f3f3f;
int ha[N];
int main()
{
int n;
cin >> n;//这个读入没什么用
int minv = INF, maxv = -INF;
int tp;
while(cin >> tp)//直接读到文件尾部停止
{
if(tp < minv) minv = tp;
if(tp > maxv) maxv = tp;
ha[tp] ++;
}
int ans1 = 0, ans2 = 0;
for(int i = minv; i <= maxv; ++ i)
{
if(ha[i] == 0) ans1 = i;
if(ha[i] == 2) ans2 = i;
}
cout << ans1 << " " << ans2 << endl;
}
P3613 寄包柜(模拟)(优化)(map_STL)
链接:P3613 【深基15.例2】寄包柜 - 洛谷 | 计算机科学教育新生态 (luogu)
描述:
代码:
#include<cstdio>
#include<map>
using namespace std;
int n,q,p,k;
map<long long,int>b;
long long i,j;
int main()
{
scanf("%d%d",&n,&q);
while(q--)
{
scanf("%d%d%d",&p,&i,&j);
if(p==1)
{
scanf("%d",&k);
b[i*100000+j]=k;
}
else printf("%d\n",b[i*100000+j]);
}
return 0;
}
学习了:
开long long int a[5000][5000]会爆掉(二维数组的上限1e5)
这里使用map<long long,int>b;
136. 只出现一次的数字(位运算)
问题描述:给你一个 非空 整数数组 nums
,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
思路与理解:要对位运算有一个高度的理解,不然还是用哈希表和其他方式解决好理解一些。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = 0;
for(int num : nums) res ^= num;
return res;
}
};
注意:这个方法只能处理2个相同的数。处理3个相同的数,找出2个个数为1的数又要另外写代码了。
1024节快乐!(位运算)
问题描述:给你一个16进制数,转换成10进制,然后对1024取模
代码:
#include <iostream>
#include <string>
using namespace std;
long long int f(string m)
{
long long int res=0,x=0;
int size=m.size();
for(int i = size - 1; res <= 1024 && i >= 0; i--)
{
//模1024 这里必须写res <= 1024 && i >= 0
//当 dec 大于 1024时 直接 % 1024 即可
//<< 4 等价于 * 16
if(m[i]>='0'&&m[i]<='9'){
res = res + ((m[i] - '0') << x);
}else if(m[i]>='A'&&m[i]<='Z'){
res = res + ((m[i] - 'A' + 10) << x);
}else{
res = res + ((m[i] - 'a' + 10) << x);
}
x += 4;
}
return res%1024;
}
int main ()
{
string n;
cin >>n;
cout<<f(n)<<endl;
return 0;
}
P1469 找筷子(位运算)
链接:P1469 找筷子 - 洛谷 | 计算机科学教育新生态 (luogu)
描述:
理解:其实和136.只出现一次的数一个原理
代码(自己写的):
#include <bits/stdc++.h>
using namespace std;
const int N=1e7+5;
int main ()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
long long int n,a,res=0;
cin >>n;
for (int i=0;i<n;i++)
{
cin >>a;
res^=a;
}
cout <<res<<endl;
return 0;
}
P1100 高低位交换(位运算)
链接:P1100 高低位交换 - 洛谷 | 计算机科学教育新生态 (luogu)
描述:
代码:
#include<bits/stdc++.h>
using namespace std;
int main(){
unsigned int n;
cin>>n;
cout<<(n>>16)+(n<<16);
return 0;
}
学习了:
789. 数的范围(二分)
题目链接:789. 数的范围 - AcWing题库
问题描述:
题解:这里需要二分出数的始末位置,所以要写两个二分来找到始位置和末位置。
找开始的位置二分写法和找末尾的位置的写法不同。需要注意
代码:
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int q[N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
while (m -- )
{
int x;
scanf("%d", &x);
int l = 0, r = n - 1;
while (l < r) //找到最后l==r ,跳出循环
{
int mid = l + r >> 1;
if (q[mid] >= x) r = mid; //找始位置
else l = mid + 1;
}
if (q[l] != x) cout << "-1 -1" << endl;
else
{
cout << l << ' ';
int l = 0, r = n - 1;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (q[mid] <= x) l = mid; //找末位置
else r = mid - 1;
}
cout << l << endl;
}
}
return 0;
}
790. 数的三次方根(二分)
链接:790. 数的三次方根 - AcWing题库
描述:
代码:
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
double a;
cin >>a;
if (a>0)
{
double l=0,r=a;
while (r-l>1e-8)
{
double x=(l+r)/2;
if (x*x*x>=a) r=x;
else l=x;
}
printf("%.6lf\n", l);
}
else if (a<0)
{
double l=a,r=0;
while (r-l>1e-8)
{
double x=(l+r)/2;
if (x*x*x>=a) r=x;
else l=x;
}
printf("%.6lf\n", l);
}
else if (a==0) cout <<"0.000000"<<endl;
return 0;
}
730. 机器人跳跃问题(二分)(递推)
链接:730. 机器人跳跃问题 - AcWing题库
描述:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int h[N];
bool check(int e)
{
for (int i = 1; i <= n; i ++ )
{
e = e * 2 - h[i];
if (e >= 1e5) return true;
if (e < 0) return false;
}
return true;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
int l = 0, r = 1e5;
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
printf("%d\n", r);
return 0;
}
收获:
1.Mid=(l+r)/2
r=mid
else l=mid+1
或者
Mid=(l+r)/2 +1
r=mid -1
else l=mid
2.做题一般都是先看直觉(暴力)(枚举)学过的哪些算法可以优化 顺序一般就是 二分 dfs dp 贪心
3.根据题目分析得出 递推或者关键的一些公式很有用
4.根据一套相关知识点的题 提高对这一个知识点的理解(很有用
5.有些细节的东西只需要仔细想一遍就可以了 ,以后不用反复想,直接用或者背。(回想之前擅长物理也是这样,那些公式和关键的东西想明白一遍就可以了)
1221. 四平方和(二分)(哈希)
链接:
版权声明:本文标题:刷题记录(自己看的习题本) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/xitong/1725586887a1031284.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论