坚持的第二天，给自己打个kao,加油
A题
题意：给你n个数，一个条件（一组里面的数任意两个数的差的绝对值不能为一），分组尽可能少；
思路：很显然如果把所有数对（一个数存在另一个数和它差值为一），把这两个数分开后，分成两组就可以；如果不存在就分为一组。
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7 using namespace std; 8 9 typedef long long ll; 10 11 int main() 12 { 13 int q; 14 cin >> q; 15 while(q--) 16 { 17 int n; 18 cin >> n; 19 int a[110]; 20 for(int i=1;i<=n;i++) 21 { 22 cin >> a[i]; 23 } 24 sort(a+1,a+1+n); 25 int flag=0; 26 for(int i=2;i<=n;i++) 27 { 28 if(a[i]-a[i-1]==1) 29 { 30 flag=1; 31 break; 32 } 33 } 34 if(flag){ 35 cout <<2<<endl; 36 } 37 else{ 38 cout << 1<<endl; 39 } 40 } 41 return 0; 42 }
B题
题意;一共有n个人，每个人可以把自己的书传给一个人，问传回自己手中所需的次数(给n个序列表示第i个人可以传给ai)
思路：
1.数据量比较小可以直接暴力写，每个人都循环一次；
2.另一种传书游戏，我们可以很容易知道，在一个环里面的人，所需的次数都是相同的，利用这一点我们可以进行优化（我们可以每次从一个没有找过的点开始，找到一个完整的环或者换上有的元素已经再别的环上找到过，我们就不再往下找，当前的就是我们这个环上所有点的次数）
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7 8 using namespace std; 9 typedef long long ll; 10 11 int main() 12 { 13 int q; 14 cin >> q; 15 while(q--) 16 { 17 int n; 18 cin >> n; 19 int a[210],b[210]; 20 for(int i=1;i<=n;i++) 21 { 22 cin >> a[i]; 23 b[i]=0; 24 } 25 for(int i=1;i<=n;i++) 26 { 27 28 if(b[i]!=0)continue; 29 // cout << a[i] <<i<<endl; 30 if(i == a[i]){ 31 b[i]=1; 32 // cout << b[i]<<i<<endl; 33 } 34 else{ 35 int t = a[i]; 36 int num =1; 37 while(t!=i) 38 { 39 t=a[t]; 40 num++; 41 } 42 b[t]=num; 43 b[a[i]]=num; 44 } 45 } 46 for(int i=1;i<n;i++) 47 { 48 printf("%d ",b[i]); 49 } 50 printf("%d ",b[n]); 51 } 52 return 0; 53 }
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <string> 5 #include <algorithm> 6 #include <cmath> 7 8 using namespace std; 9 typedef long long ll; 10 const int N = 2e5 +10; 11 int a[N],b[N]; 12 int main() 13 { 14 int q; 15 cin >> q; 16 while(q--) 17 { 18 int n; 19 cin >> n; 20 for(int i=1;i<=n;i++) 21 { 22 scanf("%d",&a[i]); 23 b[i]=0; 24 } 25 for(int i=1;i<=n;i++) 26 { 27 if(b[i]!=0)continue; 28 int t = a[i]; 29 if(t==i){ 30 b[i]=1; 31 continue; 32 } 33 int num =1; 34 int q[N]; 35 q[0]=t; 36 q[1]=i; 37 int cun =2; 38 while(b[t]==0&&t!=i) 39 { 40 t = a[t]; 41 num++; 42 q[cun]=t; 43 cun++; 44 } 45 // cout << num << endl; 46 if(num>=n) 47 { 48 for(int i=0;i<cun;i++)b[q[i]]=n;break; 49 } 50 if(t==i) 51 { 52 for(int i=0;i<cun;i++)b[q[i]]=num; 53 } 54 else{ 55 for(int i=0;i<cun;i++)b[q[i]]=b[t]; 56 } 57 } 58 for(int i=1;i<n;i++){ 59 printf("%d ",b[i]); 60 } 61 printf("%d ",b[n]); 62 } 63 }
C题
题意：给出一个数，让你输出大于等于这个数的一个特殊性质的数（就是由3的i次方的和，其中 i 不能重复 ，不可以同时含有2个及以上 3 的k次方）
思路;
1.暴力写法，由于数据较小我们可以直接暴力枚举出所有（1e5以内的）这种特殊的数
2.看了大佬的代码才了解竟然可以如此简单，我们先从一开始把三的所有次方都加起来（直到大于等于n）,然后将（保证在大于等于n的前提下，减掉可以减掉的所有3的次方）
就是一个简单的容斥思想（啊啊啊，我竟然没想到）
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <cmath> 5 #include <string> 6 #include <algorithm> 7 #include <vector> 8 #include <map> 9 using namespace std; 10 typedef long long ll; 11 map<ll,ll>mp; 12 ll a[10101000]; 13 int main() 14 { 15 int n; 16 cin >> n; 17 a[0]=1; 18 a[1]=3; 19 a[2]=4; 20 a[3]=9; 21 a[4]=10; 22 a[5]=12; 23 a[6]=13; 24 for(int i=0;i<7;i++)mp[a[i]]=1; 25 ll q=9; 26 int cun =6; 27 for(int i=3;i<18;i++) 28 { 29 q=q*3; 30 cout <<q <<endl; 31 int d=cun; 32 cun++; 33 a[cun]=q; 34 for(int j=0;j<=d;j++) 35 { 36 ll b = (ll)q+a[j]; 37 if(mp[b]==1)continue; 38 cun++; 39 a[cun]=b; 40 } 41 } 42 sort(a,a+cun+1); 43 while(n--) 44 { 45 int p; 46 cin >> p; 47 int j = lower_bound(a,a+cun+1,p)-a; 48 cout << a[j]<<endl; 49 } 50 return 0; 51 }
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <string> 5 #include <cmath> 6 #include <algorithm> 7 #include <map> 8 9 using namespace std; 10 typedef long long ll; 11 12 int main() 13 { 14 int n; 15 cin >> n; 16 while(n--) 17 { 18 ll p; 19 cin >> p; 20 ll res =1,q=3; 21 while(res<p) 22 { 23 res+=q; 24 q*=3; 25 } 26 while(q) 27 { 28 if(res-q>=p)res-=q; 29 q/=3; 30 } 31 cout << res <<endl; 32 } 33 return 0; 34 }
啊啊啊，我又是只能做简单的前三个题，我太难了，啊啊啊啊，明天再见！