• Codeforces Round #830 (Div. 2)（A~D）

    A. Bestie

    给出一个数组a，通过下面若干次操作使得所有数的gcd为1：选择任意一个数，将它换成gcd(a[i],i)，代价是n-i+1，计算将数组变为满足条件所需的最小代价。

    思路：首先我们需要知道，只要数组中有两个数互质就可以满足条件，因为要最小化代价，所以从最后向前修改一定是最优的，如果数组已经满足条件了，那代价为0；若修改最后一个可以满足条件，那就只修改最后一个，代价为1；若只修改倒数第二个就可以满足条件，那代价为2；若前面的操作都不能满足条件，那一定是要修改两个，即倒数两个，代价为3。

    AC Code：

    1. #include 
    2.  
    3. typedef long long ll;
    4. const int N=1e5+5;
    5. int t,n;
    6. int a[N];
    7.  
    8. int main(){
    9. 	std::ios::sync_with_stdio(false);
    10. 	std::cin.tie(0);
    11. 	std::cout.tie(0);
    12. 	std::cin>>t;
    13. 	while(t--){
    14. 		std::cin>>n;
    15. 		for(int i=1;i<=n;i++){
    16. 			std::cin>>a[i];
    17. 		}
    18. 		int gcd=std::__gcd(a[1],a[2]);
    19. 		for(int i=3;i<=n;i++){
    20. 			gcd=std::__gcd(gcd,a[i]);
    21. 		}
    22. 		if(n==1){
    23. 			if(a[1]==1) std::cout<<0<<'\n';
    24. 			else std::cout<<1<<'\n';
    25. 			continue;
    26. 		}
    27. 		if(gcd==1){
    28. 			std::cout<<0<<'\n';
    29. 			continue;
    30. 		}
    31. 		int x=a[n];
    32. 		a[n]=std::__gcd(a[n],n);
    33. 		gcd=std::__gcd(a[1],a[2]);
    34. 		for(int i=3;i<=n;i++){
    35. 			gcd=std::__gcd(gcd,a[i]);
    36. 		}
    37. 		if(gcd==1){
    38. 			std::cout<<1<<'\n';
    39. 			continue;
    40. 		}
    41. 		a[n]=x;
    42. 		a[n-1]=std::__gcd(a[n-1],n-1);
    43. 		gcd=std::__gcd(a[1],a[2]);
    44. 		for(int i=3;i<=n;i++){
    45. 			gcd=std::__gcd(gcd,a[i]);
    46. 		}
    47. 		if(gcd==1){
    48. 			std::cout<<2<<'\n';
    49. 			continue;
    50. 		}
    51. 		std::cout<<3<<'\n';
    52. 	}
    53. 	return 0;
    54. }

     B. Ugu

    给出一个01串，每次可以选择一个位置，将这个位置以后的所有数全部翻转，即0变为1,1变为0，求最少的操作次数，使得01串变为非递减序列。

    思路：贪心求解，每次遇到与前一个状态不同的都要翻转，要保证0在前。

    AC Code：

    1. #include 
    2.  
    3. typedef long long ll;
    4. const int N=1e5+5;
    5. int t,n;
    6. std::string s;
    7.  
    8. int main(){
    9. 	std::ios::sync_with_stdio(false);
    10. 	std::cin.tie(0);
    11. 	std::cout.tie(0);
    12. 	std::cin>>t;
    13. 	while(t--){
    14. 		std::cin>>n;
    15. 		std::cin>>s;
    16. 		int cnt=0;
    17. 		int flag=0;
    18. 		for(int i=1;i
    19. 			if(s[i]-1]&&!flag){
    20. 				cnt++;
    21. 				flag^=1;
    22. 			} 
    23. 			if(s[i]>s[i-1]&&flag){
    24. 				cnt++;
    25. 				flag^=1;
    26. 			}
    27. 		}
    28. 		std::cout<'\n';
    29. 	}
    30. 	return 0;
    31. }

    C1. Sheikh (Easy version) 

    给出一个数组a，只有一个询问，给出L，R，在a[L]，a[R]之间找一个区间[l,r]，使得区间内所有数之和-区间内所有数异或和的值最大且长度最短。

    思路： 分析可知，定义的f(l,r)函数必定是随着区间长度变长而增加，因为数字中无负值，异或和每加入一个数异或，只能小于等于之前的值，所以这个函数是单调递增的，我们可以采用二分解决。考虑对于长度二分，check函数内枚举左端点，根据最长的区间的函数值判断修改左右端点。

    AC Code：

    1. #include 
    2.  
    3. typedef long long ll;
    4. const int N = 2e5 + 5;
    5. int t, pos1, pos2;
    6. ll n, q, ans, L, R;
    7. ll dif[N], xo[N], a[N];
    8.  
    9. bool check(int mid) {
    10. 	for (int i = 1; i <= n - mid + 1; i ++) {
    11. 		ll res = dif[i + mid - 1] - dif[i - 1] - (xo[i + mid - 1] ^ xo[i - 1]);
    12. 		if (res == ans) {
    13. 			pos1 = i, pos2 = i + mid - 1;
    14. 			return true;
    15. 		}
    16. 	}
    17. 	return false;
    18. }
    19.  
    20. int main () {
    21. 	std::ios::sync_with_stdio(false);
    22. 	std::cin.tie(0);
    23. 	std::cout.tie(0);
    24. 	std::cin >> t;
    25. 	while (t --) {
    26. 		std::cin >> n >> q;
    27. 		for (int i = 1; i <= n; i ++) {
    28. 			std::cin >> a[i];
    29. 			dif[i] = dif[i - 1] + a[i];
    30. 			xo[i] = xo[i - 1] ^ a[i];
    31. 		}
    32. 		pos1 = 0, pos2 = 0;
    33. 		while (q --) {
    34. 			std::cin >> L >> R;
    35. 			ans = dif[R] - dif[L - 1] - (xo[R] ^ xo[L - 1]);
    36. 			int l = 1, r = n;
    37. 			while (l < r) {
    38. 				int mid = l + r >> 1;
    39. 				if (check(mid)) 
    40. 					r = mid;
    41. 				else
    42. 					l = mid + 1;
    43. 			}
    44. 			if (l == n) pos1 = 1, pos2 = n;
    45. 			std:: cout << pos1 << ' ' << pos2 << '\n';
    46. 		}
    47. 	}
    48. 	return 0;
    49. }

    C2. Sheikh (Hard Version)

    题意同C1，但是q的范围与n相同，不再是1了。 

    思路：如果还是按照C1的思路，时间复杂度为O(nqlogn)，肯定不行，考虑优化。首先我们对于开头结尾的0而言，去掉不影响结果，所以一定要去掉；对于中间的数，我们可以定左端点，二分找右端点，需要处理每个数后面最近的非0数，枚举这些数为左端点；最重要的优化是，因为数据范围可以用64位（大约）二进制数表示，所以最多删去64个数，仅当每个数对于答案中某一位的1有唯一的贡献，例如若答案是111111，则最多有6个数对答案有贡献，即每个数贡献答案中的一位。为什么从左侧删除呢，是因为其实而言是整个数组最多删除64个数（大约），但是这64个数也有可能是左侧的，且因为右端点我们二分查找解决了，所以可以仅考虑左端点。所以n次的枚举变成了仅有64次，时间复杂度O(64*qlogn)，可以过。

    AC Code：

    1. #include 
    2.  
    3. typedef long long ll;
    4. const int N = 1e5 + 5;
    5. const int mod = 1e9 + 7;
    6. #define INF 0x3f3f3f3f
    7. int t, n, q, L, R;
    8. ll a[N], sum[N], xo[N];
    9. int next[N];
    10.  
    11. int main() {
    12. 	std::ios::sync_with_stdio(false);
    13. 	std::cin.tie(0);
    14. 	std::cout.tie(0);
    15. 	std::cin >> t;
    16. 	while(t --) {
    17. 		std::cin >> n >> q;
    18. 		for(int i = 1; i <= n; i ++) {
    19. 			std::cin >> a[i];
    20. 		}
    21. 		for(int i = 1; i <= n; i ++) {
    22. 			sum[i] = sum[i - 1] + a[i];
    23. 			xo[i] = xo[i - 1] ^ a[i];
    24. 		}
    25. 		next[n] = INF;
    26. 		for(int i = n - 1; i >= 1; i --) {
    27. 			if(a[i + 1] > 0)
    28. 				next[i] = i + 1;
    29. 			else
    30. 				next[i] = next[i + 1];
    31. 		}
    32. 		int st, cnt, len, l, r;
    33. 		while(q --) {
    34. 			std::cin >> L >> R;
    35. 			ll ans = sum[R] - sum[L - 1] - (xo[R] ^ xo[L - 1]);
    36. 			st = L, cnt = 64; len = R - L + 1, l = L, r = R;
    37. 			while(st <= R) {
    38. 				if(sum[R] - sum[st - 1] - (xo[R] ^ xo[st - 1]) < ans)
    39. 					break;
    40. 				int left = st, right = R, mid;
    41. 				while(left <= right) {
    42. 					mid = left + right >> 1;
    43. 					if(sum[mid] - sum[st - 1] - (xo[mid] ^ xo[st - 1]) == ans)
    44. 						right = mid - 1;
    45. 					else
    46. 						left = mid + 1;
    47. 				}
    48. 				if(len > left - st + 1)
    49. 					len = left - st + 1, l = st, r = left;
    50. 				if(a[st] > 0) {
    51. 					if(!cnt) break;
    52. 					cnt--;
    53. 				} 
    54. 				st = next[st];
    55. 				if(st == INF)
    56. 					break;
    57. 			}
    58. 			std::cout << l << ' ' << r << '\n';
    59. 		}
    60. 	}
    61. 	return 0;
    62. }

    D1. Balance (Easy version)

    有一个一开始只有0的集合，每次有两种操作，可以向集合中加入一个数x，也可以询问集合的最小的不在集合中的x的倍数。

    思路：暴力求解即可，但是对于前面出现过的数字，在下一次再开始查找时要从之前的数字开始，这样做一个简单的优化，保证不会TLE。

    AC Code：

    1. #include 
    2.  
    3. typedef long long ll;
    4. const int N=1e5+5;
    5. int q;
    6.  
    7. int main(){
    8. 	std::ios::sync_with_stdio(false);
    9. 	std::cin.tie(0);
    10. 	std::cout.tie(0);
    11. 	std::cin>>q;
    12. 	std::setss;
    13. 	ss.insert(0);
    14. 	std::mapmp;
    15. 	while(q--){
    16. 		char c;
    17. 		ll x;
    18. 		std::cin>>c>>x;
    19. 		if(c=='+'){
    20. 			ss.insert(x);			
    21. 		}
    22. 		else{
    23. 			ll t=x,tmp=mp[t];
    24. 			if(tmp&&!ss.count(mp[t])){
    25. 				std::cout<'\n';
    26. 				continue;
    27. 			}
    28. 			if(tmp!=0) t=mp[t];
    29. 			while(ss.count(t)){
    30. 				t+=x;
    31. 			}
    32. 			mp[x]=t;
    33. 			std::cout<'\n';
    34. 		}
    35. 	}
    36. 	return 0;
    37. }

    os：一开始因为集合中没加0WA5了。。。xD

    D2. Balance (Hard version)

    题意与D1相同，只是加入一个删除操作。

    思路：参考hpgg的思路！在C1的基础上再开一个set存储被删除的数，每次加入时如果这个set中有这个数，那就从原来集合中删去，在输出答案时，每次在被删除的set中二分找第一个大于x的数输出，如果找到的数大于mp[x]了，就从mp[x]开始暴力查询结果。

    AC Code：

    1. #include 
    2.  
    3. typedef long long ll;
    4. const int N = 1e5 + 5;
    5. int q;
    6.  
    7. int main() {
    8. 	std::ios::sync_with_stdio(false);
    9. 	std::cin.tie(0);
    10. 	std::cout.tie(0);
    11. 	std::cin >> q;
    12. 	std::set ss, del;
    13. 	ss.insert(0);
    14. 	std::map mp;
    15. 	while(q --) {
    16. 		char c;
    17. 		ll x;
    18. 		std::cin >> c >> x;
    19. 		if(c == '+') {
    20. 			if(del.count(x)) del.erase(x);
    21. 			ss.insert(x);			
    22. 		}
    23. 		else if(c == '-') {
    24. 			ss.erase(x);
    25. 			del.insert(x);
    26. 		}
    27. 		else {
    28. 			ll t = x;
    29. 			if(!mp[t]) {
    30. 				while(ss.count(t))
    31. 					t += x;
    32. 				mp[x] = t;
    33. 				std::cout << mp[x] << '\n';
    34. 			}
    35. 			else {
    36. 				auto it = del.lower_bound(x);
    37. 				bool flag = false;
    38. 				for(it; it != del.end(); it ++) {
    39. 					if(*it > mp[x]) break;
    40. 					if(*it % x == 0) {
    41. 						std::cout << *it << '\n';
    42. 						flag = true;
    43. 						break;
    44. 					}
    45. 				}
    46. 				if(!flag) {
    47. 					t = mp[x];
    48. 					while(ss.count(t))
    49. 						t += x;
    50. 					std::cout << t << '\n';
    51. 					mp[x] = t;
    52. 				}
    53. 			}
    54. 		}
    55. 	}
    56. 	return 0;
    57. }

    os：部分题解感觉是在胡言乱语，，若有错误请指教

  • 相关阅读:
    AIGC 时代，Amazon DeepRacer 带你驶入机器学习的快车道
    测试用例设计方法六脉神剑——第二剑：招式组合，因果判定出世
    three.js r146动态加载fbx文件，非module模式
    最长公共子序列 递归
    WebGL 的 Hello World
    Java面试题大全（整理版）1000+面试题附答案详解最全面看完稳了
    Lazarus上好用的 Indy TCP client 组件
    MySQL中 JOIN关联查询的原理以及优化手段
    Java全栈工程师：技术与视野的双重拓展
    近似法概率潮流
  • 原文地址：https://blog.csdn.net/m0_62289613/article/details/127521862