小蓝xlanll

这个屌丝很懒，什么也没留下！

热门标签

刷题记录（自己看的习题本）_第五届山东师范大学与齐鲁工业大学icpc新生联谊赛题解

作者：小蓝xlanll | 2024-04-13 10:58:45

踩

第五届山东师范大学与齐鲁工业大学icpc新生联谊赛题解

杂

区间和（离散化）

题目链接：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.com/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.cn)

题解：（蓝桥杯填空题原题）这个题就是个找规律题。根据题目提示找到数与数之间的规律。

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.com.cn)

此类数学题遇到了就会，没遇到就不会。当公式记住了

if(i==j) sqr+=(n-i)*(m-j);//如果i==j，说明是正方形
else rec+=(n-i)*(m-j);//如果不等说明是矩形

bhq的小物块（数学）

链接：L-bhq的小物块_第五届山东师范大学与齐鲁工业大学ICPC新生联谊赛 (nowcoder.com)

描述：

代码：


#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.com.cn)

描述：

代码：


#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进制

//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.com)

问题描述：

补：注意题目的意思是没有必须左右相邻的树判断高度，所以例如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.com.cn)

描述：

代码：


#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.com)

描述：

代码：


 
#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.com.cn)

描述：

代码：


#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.com.cn)

描述：

代码：


#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.com.cn)

描述：

理解：其实和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.com.cn)

描述：

代码：


#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. 四平方和（二分）（哈希）

链接：

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小蓝xlanll/article/detail/416055