Codeforces Round 992 (Div. 2)

这场cf只在b卡了一下，因为b真是犯蠢了，我以为会向下取整，结果是完全就不取整，或者说是向上取整，卡了我半个小时，要不是紧急看了题一下，昨天那场就毁了

话不多说，直接开讲

A. Game of Division

思路：很容易就能看出来就是同余定理，能够找到一个取模k的数，且只有这一个数取模k为当前的余数，那么就输出这个数，否则一定存在两个数相减会导致能被k整除

#include <bits/stdc++.h>  
using namespace std;  
#define int long long  int t;  
int n, k;  
int a[200005];  void solve() {  cin >> n >> k;  int m[k + 1];  memset(m, 0, sizeof(m));  int index[k + 1]; memset(index, -1, sizeof(index)); for (int i = 1; i <= n; i++) {  cin >> a[i];  a[i] = a[i] % k;  m[a[i]]++;  index[a[i]] = i;  }  for (int i = 0; i < k; i++) {  if (m[i] == 1) {  cout << "YES\n";  cout << index[i] << "\n"; return;  }  }  cout << "NO\n";  
}  signed main() {  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);  cin >> t;  while (t--) {  solve();  }  return 0;  
}

 B. Paint a Strip

思路：我们发现，如果要输出最小的第一次操作，那么我们的放置位置一定是

1,4,10,22防置，为什么呢？

因为我们手玩一下，就可简单的发现，其实在1,4放完之后，可以直接2操作将前四个都变成1，然后在10再放置一个，就会有5个1，刚好能够把1~10全部渲染，后面同理可得

找到规律，flag=2*flag+2;

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n,k;
int a[200005];void solve()
{cin>>n;if(n<=4){if(n==1){cout<<1<<"\n";}else{cout<<2<<"\n";}}else{int ans=2;int flag=4;while(flag<n){flag=flag*2+2;ans++;}cout<<ans<<"\n";}
}signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin>>t;while(t--)solve();return 0;
}

 C. Ordered Permutations

思路：我自己纯手写了个数从2到4的情况下，有多少个是最大的，然后发现，当个数为n的时候，有2^(n-1)个数是最大的，如果k大于这个数，就是无解，否则有解

然后我自己又手玩了一下，又发现一个规律，我们每次一个分段的最小值都应当放在两边，当我们这个分段k值大于一半，那么我们当前位的数就放在末尾，否则放在第一位

然后我们就可以用类二进制思想轻松解决

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n,k;
int l,r;
int a[200005];
int flag[200005];
int vec[200005];
void solve()
{cin>>n>>k;k--;memset(flag,-1,sizeof(flag));for(int i=n-1; i>=1; i--){if(k&1){flag[i]=1;}k=k>>1;}if(k!=0){cout<<-1<<"\n";return;}l=1,r=n;for(int i=1; i<=n; i++){if(flag[i]==1){vec[r--]=i;}else{vec[l++]=i;}}for(int i=1; i<=n; i++){cout<<vec[i]<<" ";}cout<<"\n";
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>t;while(t--)solve();return 0;
}

 D. Non Prime Tree

思路：我们将跟结点赋值为1，然后将后续其第一个子节点赋值为父节点的值+1，其余子节点与父节点的值的差值为除了2以外的偶数即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n,k;
int u,v;
vector<int> e[200005];
int ans[200005];
int flag;
void dfs(int v,int fa)
{for(int u:e[v]){if(u!=fa){ans[u]=flag+1;while(ans[u]!=ans[v]+1&&(ans[u]%2!=ans[v]%2||abs(ans[u]-ans[v])==2)){ans[u]++;}flag=ans[u];dfs(u,v);}}return ;
}
void solve()
{cin>>n;for(int i=1;i<=n-1;i++){cin>>u>>v;e[u].push_back(v);e[v].push_back(u);}flag=1;ans[1]=1;dfs(1,-1);for(int i=1;i<=n;i++){cout<<ans[i]<<" ";ans[i]=0;e[i].clear();}cout<<"\n";
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>t;while(t--)solve();return 0;
}