AcWing周赛 5

A：水题。

https://www.acwing.com/problem/content/3729/

 1 #include<iostream>
 2 using namespace std;
 3 const int N=110;
 4 int w[N];
 5 int main()
 6 {
 7     int T;
 8     cin>>T;
 9     while(T--){
10         int n;
11         cin>>n;
12         int maxx=-1;
13         for(int i=0;i<n;i++){
14             cin>>w[i];
15             maxx=max(maxx,w[i]);
16         }
17         bool flag=true;
18         for(int i=0;i<n;i++){
19             if((maxx-w[i])%2==1){
20                 flag=false;
21                 break;
22             }
23         }
24         if(flag) cout<<"YES"<<endl;
25         else cout<<"NO"<<endl;
26     }
27     return 0;
28 }

B：https://www.acwing.com/problem/content/3730/

给定一个目标数组和一个值k，原数组初始全为零，每次操作可以选择原数组中的一个数使其加上k^i ，也可以选择不加，问能否将原数组变为目标数组。

经过抽象可以发现，题目问的就是目标数组的所有数在k进制的表示下，能否每一位至多只有一个1。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 typedef long long LL;
 6 const int N=70;
 7 int s[N];
 8 int main()
 9 {
10     int T;
11     cin>>T;
12     while(T--){
13         memset(s,0,sizeof s);
14         int n,k;
15         cin>>n>>k;
16         for(int i=0;i<n;i++){//将每个x的k进制表示的数都加到每一位上去
17             LL x;
18             cin>>x;
19             for(int j=0;x;j++,x/=k){
20                 s[j]+=x%k;
21             }
22         }
23         bool flag=true;
24         for(int i=0;i<N;i++){//check
25             if(s[i]>1){
26                 flag=false;
27                 break;
28             }
29         }
30         if(flag) cout<<"YES"<<endl;
31         else cout<<"NO"<<endl;
32     }
33     return 0;
34 }

C：最小生成树问题。

注意建立超级原点。

https://www.acwing.com/problem/content/3731/

题目所要求的信息非常多，但是考试的时候最难受的就是需要具体的方案。

可以通过记录每一个点是经过哪里到达已经确定的树，diistp[ ]。

之后如果某一点确定为当前距离已确定的树的距离最小的点，distp[ ]即为需要连的边。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define x first
 5 #define y second
 6 using namespace std;
 7 typedef pair<int,int> PII;
 8 typedef long long LL;
 9 const int N=2010;
10 PII q[N];
11 int wc[N],wk[N];
12 int n;
13 LL get_distance(int a,int b){
14     int dx=abs(q[a].x-q[b].x);
15     int dy=abs(q[a].y-q[b].y);
16     return (LL)(dx+dy)*(wk[a]+wk[b]);
17 }
18 
19 LL dist[N],distp[N];//dist[i]表示i到目前已经确定的树的距离，distp[i]表示从i到目前确定的树是通过哪个点到的
20 bool st[N];
21 vector<int> ans1;
22 vector<PII> ans2;
23 LL prim(){
24     //建立超级原点0
25     for(int i=1;i<=n;i++){
26         dist[i]=wc[i];
27     }
28     dist[0]=0;
29     st[0]=true;
30     LL res=0;
31     for(int i=1;i<=n;i++){
32         int t=-1;
33         for(int j=1;j<=n;j++){
34             if(!st[j]&&(t==-1||dist[t]>dist[j]))
35                 t=j;
36         }
37         st[t]=true;
38         res+=dist[t];
39         if(distp[t]==0) ans1.push_back(t);
40         else ans2.push_back({distp[t],t});
41         for(int j=1;j<=n;j++){
42             if(!st[j]&&dist[j]>get_distance(j,t)){
43                 dist[j]=get_distance(j,t);
44                 distp[j]=t;
45             }
46         }
47     }
48     return res;
49 }
50 
51 int main()
52 {
53 
54     cin>>n;
55     for(int i=1;i<=n;i++) cin>>q[i].x>>q[i].y;
56     for(int i=1;i<=n;i++) cin>>wc[i];
57     for(int i=1;i<=n;i++) cin>>wk[i];
58     LL res=prim();
59     cout<<res<<endl;
60     cout<<ans1.size()<<endl;
61     for(auto& x:ans1) cout<<x<<" ";
62     cout<<endl;
63     cout<<ans2.size()<<endl;
64     for(auto p:ans2) cout<<p.x<<" "<<p.y<<endl;
65     return 0;
66 }