欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

周总结

程序员文章站 2024-01-29 14:03:28
...

1、数据结构学习
类:个人感觉和struct有点类似。但要注意public和private的引用范围。成员函数和普通函数除开头外感觉没什么差别。
构造函数:不能有返回类型,建立类时自动调用。形式:类名::类名(参数表)
析构函数:无参数,无返回值,运行结束自动调用。形式:类名::~类名()
成员函数形式:返回类型 类名::函数名(参数表){}

线性表:(顺序表示,链式表示)
上课主要是讲了一些定义相关的内容,实际操作要与类相结合。课下和实践课把整个表的定义部分和所有的成员函数都敲了一遍。顺序表示的时候和数组一样,但多了一些比较实用的函数,但简单的题感觉用不上,感觉对空间复杂度要求比较高的时候可以试着用来优化。

2、codeforce比赛总结
这题和hjl一起折腾,他出主要思路,我和他一起考虑优化(虽然弄到12点还是wa了)。
思路:不等式成立条件:两者二进制的长度相同。
优化思路:1、2n <=x<=2n+1 恒成立,利用log2(x)+1把所有的a[i]的长度求出来并排序。
2、记录长度相同的数的个数,如果后一个数与前一个数不同,计算可以使不等式成立的数对的个数。(有考虑用桶排序,但没想到用离散化,所以放弃了)

	#include <bits/stdc++.h>
using namespace std;
int t,n,a[100010],b[100010];
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        int sum=0;
        for(int i=1; i<=n; i++){
            cin>>a[i];
            b[i]=log2(a[i])+1;
        }
        sort(b+1,b+1+n);
        int k=0;
        for(int i=1;i<n;i++){
            if(b[i]!=b[i+1])
            {
                sum=sum+(k+1)*k/2;
                k=0;
            }
            else
            k++;
        }
        if(k!=0)
            sum=sum+(k+1)*k/2;
        cout<<sum<<endl;
    }
}

正解:直接用位操作循环求长+桶求解

long long ans = 0;
		for(int i = 0;i < n;i ++){
			int l = 0;
			while(z[i]){
				l ++;
				z[i] >>= 1;
			}
			ans += er[l];
			er[l] ++;
		}