2025/4/2 心得

第一题

题目描述

给定1001个范围在[1,1000]的数字，保证只有1个数字重复出现2次，其余数字只出现1次。试用O(n)时间复杂度来求出出现2次的这个数字。

不允许用数组

输入格式

第一行：一个整数1001；

第二行：1001个用空格隔开的整数，具体入题面描述

输出格式

一个整数，即重复出现的数字

样例数据

请自己设计

数据规模与约定

如题目描述

时间限制：1 \text {s}1s

空间限制：256 \text {MB}256MB

这道题其实就是用异或

首先先抑或上所有的树。

。然后再抑或1~1000的数。

代码如下，

#include<bits/stdc++.h>
using namespace std;
int n,sum,x; 
int main(){
     freopen("num.in","r",stdin);
    freopen("num.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++)
    {cin>>x;
        sum=sum^x;
    }
    for(int i=1;i<=1000;i++)
    {
        sum=sum^i;
    }
    cout<<sum;
    return 0;
}
第二题

给定一个含有 nn 个数的序列 a_1a1​,a_2a2​...a_nan​, 求满足以下性质的二元组(i,j)的数量

• 1 1\leqslant i < j \leqslant n1⩽i<j⩽n

• 2 a_i\&a_j > a_i \quad xor \quad a_jai​&aj​>ai​xoraj​

其中 \&& 表示与运算, \hat{}^ 表示异或运算。

(0011)_2 \& (0101)_2 = (0001)_2(0011)2​&(0101)2​=(0001)2​

(0011)_2 \quad xor \quad (0101)_2 = (0110)_2(0011)2​xor(0101)2​=(0110)2​

\huge\textbf{输入格式}输入格式

第一行一个整数 TT ,表示数据组数

之后一行 11 个整数 nn ,表示序列长度

接下来一行 nn 个整数, 表示 a_1a1​,a_2a2​...a_nan​

\huge\textbf{输出格式}输出格式

对于每一次询问,输出一个整数表示答案

\huge\textbf{输入样例}输入样例

551 4 3 7 1031 1 146 2 5 322 411

Copy

\huge\textbf{输出样例}输出样例

13200

Copy

\huge\textbf{数据范围与约定}数据范围与约定

对于 30\%30% 的数据 1\leqslant n\leqslant 10^31⩽n⩽103,1\leqslant a_i\leqslant 10^91⩽ai​⩽109

对于另外 30\%30% 的数据 1\leqslant n\leqslant 10^51⩽n⩽105,1\leqslant a_i <2^{10}1⩽ai​<210

对于 100\%100% 的数据 1\leqslant T\leqslant 51⩽T⩽5,1\leqslant n\leqslant 10^51⩽n⩽105,1\leqslant a_i\leqslant 10^91⩽ai​⩽109

这道题。其实十分简单。

因为相同位数的第一位肯定是一，所以说如果相同位数比的话，那么相同位数的异或一定大于相同位数的与

所以说这道题其实我们就需要判断它们位数是否相同。

如果相同的话

，那么就加一

代码如下，

#include <bits/stdc++.h>
using namespace std;
long long t,n,a,b,c[45],d,sum;
int main()
{
    freopen("calc.in","r",stdin);
    freopen("calc.out","w",stdout);
    cin>>t;
    for(int i=1;i<=t;i++)
    {    
        memset(c,0,sizeof(c)); 
        cin>>n;
        for(int j=1;j<=n;j++)
        {
            cin>>a;
            b=int(log2(a)+1);
            c[b]++;
//            cout<<c[b]<<'*';
            
        }
//        cout<<endl;
        for(int i1=1;i1<=40;i1++)
        {
            sum+=(c[i1]*(c[i1]-1))/2;
        }
        cout<<sum<<endl;
        sum=0;
    }
第三集

问题陈述

给定一个长度恰好为9的字符串SS，由数字组成。0到9的所有数字都恰好在SS中出现一次。

打印出SS中缺失的数字。

约束条件

• SS是一个长度为9的数字字符串。
• SS中的所有字符都是不同的。

---

输入

从标准输入以以下格式给出输入：

SS

输出

打印出SS中缺失的数字。

---

样例输入1

023456789

样例输出1

1

字符串023456789只缺少了11。因此，应该打印出11。

---

样例输入2

459230781

样例输出2

6

字符串459230781只缺少了66。因此，应该打印出66。

注意，使用桶的思想完成该题目，不允许使用string

这道题有一种很简单的思路。

开玩笑的就把他们所有输出数字儿加起来然后呢再减去0~9。的数字之和就得到了。

但是我们现在要用异货做。

这道题其实跟一的思路基本一样。

只不过要把这个给转成数字罢了。

代码如下，

#include<bits/stdc++.h>
using namespace std;
int sum,x; 
string n;
int main(){
 //    freopen("num.in","r",stdin);
//    freopen("num.out","w",stdout);
    cin>>n;
    for(int i=0;i<9;i++)
    { 
        sum=sum^(n[i]-'0');
    }
    for(int i=0;i<=9;i++)
    {
        sum=sum^i;
    }
    cout<<sum;
    return 0;
}
第四题。

题目描述

给定一个长度为64的序列A=(A\_0,A\_1,\dots,A\_{63})A=(A_0,A_1,…,A_63)，由0和1组成。

求A\_0 2^0 + A\_1 2^1 + \dots + A\_{63} 2^{63}A_020+A_121+⋯+A_63263。

约束条件

• A\_iA_i是0或1。

---

输入

从标准输入中以以下格式给出输入：

A_0A0​ A_1A1​ \dots… A_{63}A63​

输出

将答案作为整数打印出来。

---

样例输入1

1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

样例输出1

13

A\_0 2^0 + A\_1 2^1 + \dots + A\_{63} 2^{63} = 2^0 + 2^2 + 2^3 = 13A_020+A_121+⋯+A_63263=20+22+23=13。

---

样例输入2

1 0 1 0 1 0 0 0 0 1 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0

样例输出2

766067858140017173

题目描述

给定n个数字，依次输出每个数字二进制中1的个数。

输入格式

第一行输入一个数N；

之后N行，每行输入一个数a[i]。

输出格式

输出N行，每行一个数每个数字二进制包含1的个数。

样例数据

input

315122

Copy

output

413

Copy

数据规模与约定

对于100%的数据，2≤N≤200000，1≤a[i]≤10^18；

时间限制：1 \text {s}1s

空间限制：256 \text {MB}256MB

这道题其实并不难

。只需要一次一次去掉最低位的一

然后计数器加加就好了。

代码如下，

#include<bits/stdc++.h>
using namespace std;
long long a,n,sum;

int main()
{
    freopen("count.in","r",stdin);
    freopen("count.out","w",stdout);
    cin>>n; 
    for(int i=1;i<=n;i++)
    {
        sum=0;
        cin>>a;
        while(a)
        {
            a-=a&(-a);
            sum++;
        }
        cout<<sum<<endl;
    }
    return 0;
}