Codeforces Round #485 (Div. 2)

A

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define IT set<ll>::iterator
 6 #define sqr(x) ((x)*(x))
 7 #define pb push_back
 8 #define eb emplace_back
 9 #define maxn 1000006
10 #define eps 1e-8
11 #define pi acos(-1.0)
12 #define rep(k,i,j) for(int k=i;k<j;k++)
13 typedef long long ll;
14 typedef pair<int,int> pii;
15 typedef pair<ll,ll>pll;
16 typedef pair<ll,int> pli;
17 typedef pair<pair<int,string>,pii> ppp;
18 typedef unsigned long long ull;
19 const long long MOD=998244353;
20 const double oula=0.57721566490153286060651209;
21 using namespace std;
22 
23 map<string,string>mp;
24 int main(){
25     std::ios::sync_with_stdio(false);
26     int n;
27     cin>>n;
28     string s[15];
29     mp["purple"]="Power";
30     mp["green"]="Time";
31     mp["blue"]="Space";
32     mp["orange"]="Soul";
33     mp["red"]="Reality";
34     mp["yellow"]="Mind";
35     for(int i=0;i<n;i++){
36         cin>>s[i];
37         mp[s[i]]="0";
38     }
39     cout<<6-n<<endl;
40     for(auto it:mp){
41         if(it.second!="0") cout<<it.second<<endl;
42     }
43 }

View Code

B

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define IT set<ll>::iterator
 6 #define sqr(x) ((x)*(x))
 7 #define pb push_back
 8 #define eb emplace_back
 9 #define maxn 1000006
10 #define eps 1e-8
11 #define pi acos(-1.0)
12 #define rep(k,i,j) for(int k=i;k<j;k++)
13 typedef long long ll;
14 typedef pair<int,int> pii;
15 typedef pair<ll,ll>pll;
16 typedef pair<ll,int> pli;
17 typedef pair<pair<int,string>,pii> ppp;
18 typedef unsigned long long ull;
19 const long long MOD=998244353;
20 const double oula=0.57721566490153286060651209;
21 using namespace std;
22 
23 map<string,string>mp;
24 int main(){
25     std::ios::sync_with_stdio(false);
26     ll x,y;
27     cin>>x>>y;
28     if(x==y||(x==2&&y==4)||(x==4&&y==2)){cout<<"="<<endl;return 0;}
29     if(x==2&&y==3||x==1){cout<<"<"<<endl;return 0;}
30     if(x==3&&y==2||y==1){cout<<">"<<endl;return 0;}
31     else if(x<y){cout<<">"<<endl;return 0;}
32     else if(x>y){cout<<"<"<<endl;return 0;}
33     return 0;
34 }

View Code

C

题意：给n个数， $每个位置有两个属性$

$思路：原本想了个三重for循环暴力，但是看了数据觉得不可行，然后发现，如果枚举中间那个数j,那么i往前枚举，k往后枚举，这样只要O（n^2$

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define IT set<ll>::iterator
 6 #define sqr(x) ((x)*(x))
 7 #define pb push_back
 8 #define eb emplace_back
 9 #define maxn 1000006
10 #define eps 1e-8
11 #define pi acos(-1.0)
12 #define rep(k,i,j) for(int k=i;k<j;k++)
13 typedef long long ll;
14 typedef pair<int,int> pii;
15 typedef pair<ll,ll>pll;
16 typedef pair<ll,int> pli;
17 typedef pair<pair<int,string>,pii> ppp;
18 typedef unsigned long long ull;
19 const long long MOD=998244353;
20 const double oula=0.57721566490153286060651209;
21 using namespace std;
22 
23 int n;
24 struct sair{
25     int pos,v;
26     bool operator<(const sair&b)const{
27         return pos<b.pos;
28     }
29 }a[3005];
30 vector<sair>ve;
31 
32 int main(){
33     std::ios::sync_with_stdio(false);
34     cin>>n;
35     for(int i=1;i<=n;i++){
36         cin>>a[i].pos;
37     }
38     for(int i=1;i<=n;i++){
39         cin>>a[i].v;
40     }
41     ll ans=0x3f3f3f3f3f3f3f3f;
42     for(int i=2;i<n;i++){
43         ll Min1=0x3f3f3f3f3f3f3f3f,Min2=0x3f3f3f3f3f3f3f3f;
44         int posl=i-1,posr=i+1;
45         while(posl>=1){
46             if(a[posl].pos<a[i].pos){
47                 if(Min1>a[posl].v){
48                     Min1=a[posl].v;
49                 }
50             }
51             posl--;
52         }
53         while(posr<=n){
54             if(a[posr].pos>a[i].pos){
55                 if(Min2>a[posr].v){
56                     Min2=a[posr].v;
57                 }
58             }
59             posr++;
60         }
61         if(Min1!=0x3f3f3f3f3f3f3f3f&&Min2!=-0x3f3f3f3f3f3f3f3f){
62             ans=min(ans,Min1+Min2+a[i].v);
63         }
64     }
65     if(ans==0x3f3f3f3f3f3f3f3f) cout<<-1<<endl;
66     else cout<<ans<<endl;
67 }

View Code

D

题意：一些公司将在某地举办展览会，该地有n个城市，有m条双向道路。有k种类型的物品，每个城市可以生产出一个类型的物品。举办展览会需要有s种物品。每种物品运输需要一定的费用，费用等于路径的长度，问在n个城市举办展览会的最少费用

思路：把每种物品跑最短路即可

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define IT set<ll>::iterator
 6 #define sqr(x) ((x)*(x))
 7 #define pb push_back
 8 #define eb emplace_back
 9 #define maxn 5000005
10 #define eps 1e-8
11 #define pi acos(-1.0)
12 #define rep(k,i,j) for(int k=i;k<j;k++)
13 typedef long long ll;
14 typedef pair<int,int> pii;
15 typedef pair<ll,ll>pll;
16 typedef pair<ll,int> pli;
17 typedef pair<pair<int,string>,pii> ppp;
18 typedef unsigned long long ull;
19 const long long MOD=998244353;
20 const double oula=0.57721566490153286060651209;
21 using namespace std;
22 
23 int n,m,s,k;
24 int a[100005];
25 vector<int>ve[100005];
26 int book[100005];
27 int dis[100005][105];
28 
29 void bfs(){
30     queue<int>Q;
31     memset(dis,-1,sizeof(dis));
32     for(int i=1;i<=s;i++){
33         while(!Q.empty()) Q.pop();
34         for(int j=1;j<=n;j++){
35             if(a[j]==i){
36                 Q.push(j);
37                 dis[j][i]=0;
38             }
39         }
40         while(!Q.empty()){
41             int ss=Q.front();
42             Q.pop();
43             for(auto au:ve[ss]){
44                 if(dis[au][i]==-1){
45                     dis[au][i]=dis[ss][i]+1;
46                     Q.push(au);
47                 }
48             }
49         }
50     }
51     ll ans;
52     for(int i=1;i<=n;i++){
53         ans=0;
54         sort(dis[i]+1,dis[i]+s+1);
55         for(int j=1;j<=k;j++){
56             ans+=dis[i][j];
57         }
58         cout<<ans<<" ";
59     }
60 }
61 
62 int main(){
63     std::ios::sync_with_stdio(false);
64     cin>>n>>m>>s>>k;
65     for(int i=1;i<=n;i++){
66         cin>>a[i];
67     }
68     int x,y;
69     for(int i=1;i<=m;i++){
70         cin>>x>>y;
71         ve[x].pb(y);
72         ve[y].pb(x);
73     }
74     bfs();
75 }

View Code

E

题意：有1-n按顺序排列的数，A进行3*n操作，每次交换两个数，B进行7*n+1操作，给个1-n的排列，问是谁打乱的

思路：每次交换逆序对都会加一或减一，且从一个序列变回该序列需要至少两次操作，所以判断逆序对和n的奇偶性即可

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define IT set<ll>::iterator
 6 #define sqr(x) ((x)*(x))
 7 #define pb push_back
 8 #define eb emplace_back
 9 #define maxn 5000005
10 #define eps 1e-8
11 #define pi acos(-1.0)
12 #define rep(k,i,j) for(int k=i;k<j;k++)
13 typedef long long ll;
14 typedef pair<int,int> pii;
15 typedef pair<ll,ll>pll;
16 typedef pair<ll,int> pli;
17 typedef pair<pair<int,string>,pii> ppp;
18 typedef unsigned long long ull;
19 const long long MOD=998244353;
20 const double oula=0.57721566490153286060651209;
21 using namespace std;
22 
23 int n;
24 int a[1000006];
25 int tree[1000006];
26 
27 int lowbit(int x){return x&(-x);}
28 int ask(int x){int ans=0;while(x){ans+=tree[x];x-=lowbit(x);}return ans;}
29 void add(int x){while(x<=n){tree[x]+=1;x+=lowbit(x);}}
30 
31 
32 int main(){
33     std::ios::sync_with_stdio(false);
34     cin>>n;
35     for(int i=1;i<=n;i++){
36         cin>>a[i];
37     }
38     int sum=0;
39     for(int i=n;i;i--){
40         sum+=ask(a[i]);
41         add(a[i]);
42     }
43     sum&=1,n&=1;
44     if(sum==n) cout<<"Petr"<<endl;
45     else cout<<"Um_nik"<<endl;
46 }

View Code

F

题意：有m个整数，每个整数都在0~2^n-1之间，以每个整数为顶点建立一个无向图，当x&y==0时，则认为x,y之间存在一条边。计算图中联通块的数量。

思路：1010和0101符合条件，那1010和0001，0100，0000也符合条件，所以当一个数为x时，直接找～x（就是x转二进制后每位数与1异或后的值）的子集，然后搜索找联通块即可

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define IT set<ll>::iterator
 6 #define sqr(x) ((x)*(x))
 7 #define pb push_back
 8 #define eb emplace_back
 9 #define maxn 5000005
10 #define eps 1e-8
11 #define pi acos(-1.0)
12 #define rep(k,i,j) for(int k=i;k<j;k++)
13 typedef long long ll;
14 typedef pair<int,int> pii;
15 typedef pair<ll,ll>pll;
16 typedef pair<ll,int> pli;
17 typedef pair<pair<int,string>,pii> ppp;
18 typedef unsigned long long ull;
19 const long long MOD=998244353;
20 const double oula=0.57721566490153286060651209;
21 using namespace std;
22 
23 int n,m;
24 int book[maxn],a[maxn],num[maxn];
25 
26 void bfs(int x){
27     queue<int>Q;
28     Q.push(x);
29     book[x]=1;
30     while(!Q.empty()){
31         int s=Q.front();
32       //  cout<<s<<endl;
33         Q.pop();
34         for(int i=0;i<n;i++){
35             if(s&(1<<i)){
36                 int tmp=s-(1<<i);
37                 if(!book[tmp]){
38                     book[tmp]=1;
39                     Q.push(tmp);
40                     if(num[tmp]){
41                         tmp=(1<<n)-1-tmp;
42                         if(!book[tmp]){
43                             book[tmp]=1;
44                             Q.push(tmp);
45                         }
46                     }
47                 }
48             }
49         }
50     }
51 }
52 
53 int main(){
54     std::ios::sync_with_stdio(false);
55     cin>>n>>m;
56     for(int i=1;i<=m;i++){
57         cin>>a[i];
58         num[a[i]]=1;
59     }
60     int ans=0;
61     for(int i=1;i<=m;i++){
62         if(!book[a[i]]){
63             ans++;
64             book[a[i]]=1;
65             int tmp=(1<<n)-1-a[i];
66             bfs(tmp);
67         }
68     }
69     cout<<ans<<endl;
70 }

View Code