Codeforces Round 976 (Div. 2) (部分题解)

先做一个提前的小结，感觉这场每题有很特别的结论或者很难去guess的点，但就是能对，可能在证明上有点复杂吧。 

A. Find Minimum Operations

思路：题意的话就是用来代替的最小操作步骤，

这里其实可以转换成求将改写成进制下的各位上的数的和

AC代码：

#include <bits/stdc++.h>
using namespace std;int find_min_oper(int n, int k){if(k == 1) return n;int ans = 0;while(n){ans += n%k;n /= k;}return ans;
}int main()
{int t;cin >> t;while(t--){int n,k;cin >> n >> k;cout << find_min_oper(n,k) << "\n";}return 0;
}

有人光看函数体内可能不是很清楚，其实这也就是换成二进制的步骤，可能画出图来比较形象，以样例的第四个举例：

这样应该能懂了，跟转换成二进制同理。 

B. Brightness Begins

思路：这道题不好看出规律来，应该用打表来好观察一点，接下来是我的打表代码（可以参考一下）：

void solve(){vector<int> s(21,0);for (int i = 2; i<=20; i++){for (int j = 1;j<=20; j++){if (j%i == 0) s[j] = 1-s[j];if (j <= i) cout << s[j] << " \n"[j==i];}}
}

这样我们就能观察出规律，只要是平方数就为0，其余为1，所以我们可以使用二分来求解答案 

AC代码：

#include <bits/stdc++.h>
using namespace std;
int main(){int t;cin >> t;while(t--){long long k, l = 1, r = 2e18;cin >> k;while(l+1 < r){long long mid = (l+r)>>1;long long n = mid - int(sqrtl(mid));if(n >= k) r = mid;else l = mid;}cout << r << "\n";}return 0;
}

而官方题解给出了一个公式，能直接求出结果

 

感兴趣的可以去证一下。

C. Bitwise Balancing

 思路：首先对于每一位我们都能得出的关系，先将其列出来

会发现对于的组合为011，100是不会出现的，当遇到了就返回输出-1，接下来观看a必须输出为1的的组合为110，001，所以当遇到这样组合时a就加上该进制位，其余组合可以为0，不用管，并且这里注意最后求出a还要判断判断一下。

AC代码：

void solve()
{int b, c, d;cin >> b >> c >> d;int mask = 1, bit_b, bit_c, bit_d;int a = 0, flag = 0;for (int i = 0; i<62; i++){bit_b = (b & mask ? 1 : 0);bit_c = (c & mask ? 1 : 0);bit_d = (d & mask ? 1 : 0);if ((!bit_b && bit_c && bit_d) || (bit_b && !bit_c && !bit_d)){cout << -1 << endl;return ;}else if ((!bit_b && !bit_c && bit_d) || (bit_b && bit_c && !bit_d)){a += (1ll<<i);}mask <<= 1;}if ((a|b)-(a&c)!=d){cout << -1 << endl;}else cout << a << endl;
}

心得：之前也是想着枚举每一位二进制来做，但考虑的是（a|b）与（a&c）这样之类的来考虑，想到这一块如果是0，1的话不得相减向前借一位，很难考虑，后来发现这样的情况根本不会存在，因为这一位（a|b)的a、b都为0，那么后面的(a&c)也肯定为0.

这里还有个结论直接就能给出结果，具体见如下代码：

void solve()
{int b, c, d;cin >> b >> c >> d;int a = b^d;if ((a|b)-(a&c)!=d) cout << -1 << endl;else cout << a << endl;
}

D. Connect the Dots

思路：因为这道题的d的取值很小，所以我们可以存储d的差分来实现连接存贮，这样对于一个点总是往后连接就行了，再用并查集来找联通块

struct ufSet{vector<int> fa,siz;// fa[N]用于存储每个元素的父节点信息// siz[N]用于存储每个集合的大小void init(int n){fa.resize(n+5),siz.resize(n+5);for(int i=1;i<=n;i++) fa[i]=i,siz[i]=1;}int find(int x){if(x==fa[x]) return x;fa[x]=find(fa[x]);return fa[x];}bool mrg(int x,int y){x=find(x),y=find(y);if(x==y) return 0;if(siz[x]<siz[y]) swap(x,y);fa[y]=x,siz[x]+=siz[y];return 1;}
}t;
void solve()
{int n, m;cin >> n >> m;t.init(n);vector<vector<int>> s(n+1, vector<int>(M, 0));for (int i = 1; i<=m; i++){int a, d, k;cin >> a >> d >> k;if (a+d <= n){s[a+d][d]++;}if (a+k*d+d <= n){s[a+k*d+d][d]--;}}for (int i = 1; i<=n; i++){for (int j=0; j<M; j++){if (i-j >= 1){s[i][j] += s[i-j][j];if (s[i][j] && i-j >= 1){t.mrg(i, i-j);}}}}set<int> st;for (int i = 1; i<=n; i++) st.insert(t.find(i));cout << st.size() << endl;
}