第一題

題目描述

給定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;
}