Codeforces Round #595 (Div. 3) A,B,C,D

A题:n个学生，分成任意组，要求每组中任意两名学生的技能值相差不等于1，问最小分组.

 1 #include
 2  
 3 using namespace std;
 4  
 5 #define int long long 
 6 int arr[150];
 7 signed main(){
 8     int _;
 9     cin>>_;
10     while(_--){
11         int n;
12         cin>>n;
13         for(int i=1;i<=n;i++)
14             cin>>arr[i];
15         sort(arr+1,arr+1+n);
16         int sum=0;
17         int flag=0;
18         for(int i=1;i){
19             if(arr[i+1]-arr[i]==1){
20                 flag=1;
21                 break;
22             }
23         }
24         if(flag){
25             printf("2\n");
26         }else{
27             printf("1\n");
28         }
29     }
30     return 0;
31 } 
32 /*
33  
34 */

B1题：

题意：n个学生，每个学生有单独的一本书，每天学生 i 会把 书给 a_i，问每个学生重新拿到自己的书经过的天数。

思路：一发暴力水过

 1 #include
 2  
 3 using namespace std;
 4 #define int long long 
 5 int arr[2050];
 6 int ans[2500];
 7 signed main(){
 8     int _;
 9     cin>>_;
10     while(_--){
11         int n;
12         cin>>n;
13         for(int i=1;i<=n;i++)
14             scanf("%lld",&arr[i]);
15         for(int i=1;i<=n;i++){
16             int sum=0;
17             int temp=i;
18             while(1){
19                 sum++;
20                 if(arr[temp]==i){
21                     break;
22                 }
23                 temp=arr[temp];
24             }
25             ans[i]=sum;
26         }
27         for(int i=1;i<=n;i++){
28             printf("%lld ",ans[i]);
29         }
30         printf("\n");
31     }
32     return 0;
33 }

B2：

找环，只要在同一个环的天数相等。开始暴力。。。。。。。。。。。

 1 #include
 2  
 3 using namespace std;
 4 #define int long long 
 5 #define N 200020
 6 int arr[N];
 7 int ans[N];
 8 int vis[N];
 9 int a[N];
10 signed main(){
11     int _;
12     cin>>_;
13     while(_--){
14         int n;
15         scanf("%lld",&n);
16         for(int i=1;i<=n;i++){
17             scanf("%lld",&arr[i]);
18             vis[i]=0;
19         }
20             
21         
22         for(int i=1;i<=n;i++){
23             int sum=0;
24             if(vis[i])
25                 continue;
26             int temp=i;
27             vector<int> v;
28             while(1){
29                 sum++;
30                 if(arr[temp]==i){
31                     break;
32                 }
33                 temp=arr[temp];    
34                 v.push_back(temp);
35             }
36             vis[i]=sum;
37             for(int j=0;j){
38                 vis[v[j]]=sum;
39             }
40         //    vis[i]=sum;
41         }
42         for(int i=1;i<=n;i++){
43             printf("%lld ",vis[i]);
44         }
45         printf("\n");
46     }
47     return 0;
48 }
49 /*
50         
51 3 6
52 1 3 4 9 10      
53 1 2 3 4 5
54 5 1 2 4 3
55 4 4 4 1 4
56 */

C1:

题意：求大于n的m，m有不同的3的次幂。

想到进制，即可知道符合的数字3进制转换后只有1和0. 暴力一下。

 1 #include
 2  
 3 using namespace std;
 4 #define int long long
 5 int ans[20050];
 6  
 7 signed main(){
 8     
 9     int _;cin>>_;
10     while(_--){
11         int n;
12         scanf("%lld",&n);
13         if(n==10000){
14             cout<<"19683"<continue;
15         }
16         if(n==1){
17             cout<<1<continue;
18         }
19         int i=n;
20         for(;;i++){
21             int temp=i;
22             int flag=1;
23             while(temp){
24                 int x=temp%3;
25                 if(x!=0&&x!=1){
26                     flag=0;
27                     break;
28                 }
29                 temp/=3;
30             }
31             if(flag){
32                 cout<endl;
33                 break;
34             }
35         }
36     }    
37     return 0;
38 }

C2:

思路：从左到右，找到第一个2的位置，然后开始模拟进位。第一个2后面的数全改为0。调了好久的BUG。

 1 /*
 2 10212121111
 3 11000000000
 4 110121212211
 5 111000000000
 6 11212211221
 7 10000000000
 8 */
 9 #include
10 using namespace std;
11 #define int long long
12 int fpow(int a,int b){
13     int res=1;
14     while(b){
15         if(b%2){
16             res*=a;
17         }
18         a*=a;
19         b/=2;
20     }
21     return res;
22 }
23 signed main(){
24     int _;cin>>_;
25     while(_--){
26         int n;
27         cin>>n;
28         vector<int> v;
29         int temp;
30         temp=n;
31         while(temp){
32             v.push_back(temp%3);
33             temp/=3;
34         }
35         int flag1=-1;
36         int flag2=0;
37         int cnt=0;
38         /*
39         for(int i=v.size()-1;i>=0;i--){
40             
41         } 
42         cout<43         */
44         for(int i=v.size()-1;i>=0;i--){
45             if(v[i]==2){
46                 flag1=i;
47                 break;
48             }
49             if(v[i]==0){
50                 flag2=i;
51             }
52         }
53         if(flag1==-1){
54             cout<endl;
55             continue;
56         }
57         if(!flag2){
58             int x=v.size();
59             cout<3,x)<<endl;
60             continue;
61         }else{
62             int ans[150];
63             int cnt=0;
64             for(int i=v.size()-1;i>=0;i--)
65                 ans[i]=v[i];
66             int j;
67             for( j=flag1;j){
68                 
69                 if(ans[j]==2){
70                     ans[j]=0;
71                     ans[j+1]=ans[j+1]+1;
72                 }
73             }/*
74             for(int i=v.size()-1;i>=0;i--){
75                 cout<76             }
77             cout<78             for(int i=0;i79                 cout<80             }
81             cout<*/
82             int X=0;
83         //    cout<
84             for(int i=j-1;;i--){
85                 if(i<=flag1){
86                     break;
87                 }
88                 if(ans[i])
89                 X+=fpow(3,i);
90             //    cout<
91             }
92             cout<endl;
93         }
94     }
95     return 0;
96 }

【补题...................................】

D1，D2题：

题意：给出n个线段，要求同一个点不能有超过k条线段覆盖。求最少要删多少条线段。

思路：r从小到大排序。r相等的时候l从小到大排序。然后进行区间的最值和区间修改。用线段树维护。

然后在网上找了一个板子 套了一下。

  1 #include 

E题待补。