• Codeforces Round #835 (Div. 4) A~G

    比赛链接：https://codeforces.com/contest/1760

    A. Medium Number 

    题目大意：

    t组测试，每组给三个数求中位数。

    代码：

    1. #include
    2. #define rep(i,a,b) for (register int i=a;i
    3. #define per(i,a,b) for (register int i=a;i>b;--i)
    4. #define endl '\n'
    5. using namespace std;
    6. void solve()
    7. {
    8. 	int a[3];
    9. 	cin>>a[0]>>a[1]>>a[2];
    10. 	sort(a,a+3);
    11. 	cout<1]<
    12. }
    13. int main()
    14. {
    15. 	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    16. 	int _=1;
    17. 	cin>>_;
    18. 	while(_--){
    19. 		solve();
    20. 	}
    21. 	return 0;
    22. }

    B. Atilla's Favorite Problem 

    题目大意：

    t组测试，每组给一个字符串，字母表顺序a-z中从a开始，最短多长可以包含给定的字符串。

    思路：

    找字符串中出现最大的字母。

    代码：

    1. #include
    2. #define rep(i,a,b) for (register int i=a;i
    3. #define per(i,a,b) for (register int i=a;i>b;--i)
    4. #define endl '\n'
    5. using namespace std;
    6. void solve()
    7. {
    8. 	int n,mx=0;
    9. 	string s;
    10. 	cin>>n>>s;
    11. 	rep(i,0,n) mx=max(mx,s[i]-'a');
    12. 	cout<1<
    13. }
    14. int main()
    15. {
    16. 	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    17. 	int _=1;
    18. 	cin>>_;
    19. 	while(_--){
    20. 		solve();
    21. 	}
    22. 	return 0;
    23. }

     C. Advantage

    题目大意：

    t组测试，每组给一个长度为n的数组，输出数组每一个数和数组中最大值的差，如果等于最大值输出其与第二大值的差。

    代码：

    1. #include
    2. #define rep(i,a,b) for (register int i=a;i
    3. #define per(i,a,b) for (register int i=a;i>b;--i)
    4. #define endl '\n'
    5. using namespace std;
    6. const int N=2e5+10;
    7. int a[N];
    8. void solve()
    9. {
    10. 	int n,mx1=0,mx2=0;
    11. 	cin>>n;
    12. 	rep(i,0,n){
    13. 		cin>>a[i];
    14. 		if(a[i]>=mx1) mx2=mx1,mx1=a[i];
    15. 		else if(a[i]>mx2) mx2=a[i];
    16. 	}
    17. 	rep(i,0,n) if(a[i]==mx1) cout<" "; else cout<" ";
    18. 	cout<
    19. }
    20. int main()
    21. {
    22. 	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    23. 	int _=1;
    24. 	cin>>_;
    25. 	while(_--){
    26. 		solve();
    27. 	}
    28. 	return 0;
    29. }

     D. Challenging Valleys

    题目大意：

     t(1≤t≤10^4)组测试，每组给定长度为n(1≤n≤2⋅10^5)的数组，1≤ai≤10^9，问是否仅仅存在一段[l,r]满足：

    1.[l,r]中每个ai相等；

    2.l=0 or a_{l-1}>a_{l}

    3.r=n−1 or a_{r}>a_{r+1}.

    思路：

    双指针。处理一段连续相等的一段[l,r]，判断两边是否合法，然后将l指针指向r指针。时间复杂度为O(n)

    为方便处理可两个边界设置哨兵。

    代码：

    1. #include
    2. #define rep(i,a,b) for (register int i=a;i
    3. #define per(i,a,b) for (register int i=a;i>b;--i)
    4. #define endl '\n'
    5. using namespace std;
    6. const int N=2e5+10;
    7. int a[N];
    8. void solve()
    9. {
    10. 	int n;
    11. 	cin>>n;
    12. 	rep(i,1,n+1) cin>>a[i];
    13. 	a[n+1]=2e9;
    14. 	int cnt=0;
    15. 	rep(i,1,n+1){
    16. 		int r=i;
    17. 		while(r+1<=n&&a[r+1]==a[r]) ++r;
    18. 		if(a[i-1]>a[i]&&a[r+1]>a[r]) ++cnt;
    19. 		if(cnt>1){
    20. 			cout<<"NO"<
    21. 			return;
    22. 		}
    23. 		i=r;
    24. 	}
    25. 	if(cnt==1) cout<<"YES"<
    26. 	else cout<<"NO"<
    27. }
    28. int main()
    29. {
    30. 	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    31. 	int _=1;
    32. 	cin>>_;
    33. 	a[0]=2e9;
    34. 	while(_--){
    35. 		solve();
    36. 	}
    37. 	return 0;
    38. }

    E. Binary Inversions

    题目大意：

     t(1≤t≤10^4)组测试，每组给定长度为n(1≤n≤2⋅10^5)的数组，数组中元素为0或1。问仅可以修改一次，某一个0改为1或者1改为0，整个数组逆序对最大为多少。

    思路：

    预处理两个前缀和。s0[i]表示1-i中0出现的次数，s1[i]表示1-i中1出现的次数。一个0的位置会和它前面所有的1形成逆序对，所以初始逆序对个数就是\sum s1[i-1]，之中i为第i个a[i]=0。

    某个位置i为0，如果将其改成1，减少的逆序对个数为前面1的个数：s1[i-1]，增加的逆序对个数为后面0的个数：s0[n]-s0[i]。显然i越靠左边，减少的越少，增加的越多。

    将1改为0同理，靠右为最优。

    比较两个修改和不修改取最大即可。

    代码：

    1. #include
    2. #define rep(i,a,b) for (register int i=a;i
    3. #define per(i,a,b) for (register int i=a;i>b;--i)
    4. #define endl '\n'
    5. using namespace std;
    6. typedef long long LL;
    7. const int N=2e5+10;
    8. int a[N],s0[N],s1[N];
    9. void solve()
    10. {
    11. 	int n,lst=0,pre=0;
    12. 	LL ans=0;
    13. 	cin>>n;
    14. 	rep(i,1,n+1){
    15. 		cin>>a[i];
    16. 		s1[i]=s1[i-1],s0[i]=s0[i-1];
    17. 		if(a[i]) ++s1[i],lst=i;
    18. 		else{
    19. 			++s0[i],ans+=s1[i-1];
    20. 			if(pre==0) pre=i;
    21. 		}
    22. 	}
    23. 	int mx=0;
    24. 	if(pre) mx=max(mx,s0[n]-s0[pre]-s1[pre]);
    25. 	if(lst) mx=max(mx,s1[lst-1]-(s0[n]-s0[lst]));
    26. 	cout<
    27. }
    28. int main()
    29. {
    30. 	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    31. 	int _=1;
    32. 	cin>>_;
    33. 	while(_--){
    34. 		solve();
    35. 	}
    36. 	return 0;
    37. }

    F. Quests

    题目大意：

    t(1≤t≤10^4)组测试，每组给定长度为n(1≤n≤2⋅10^5)的数组，以及价值c，天数d。选择数组ai可以获得ai的价值，但是在k天之内都不能再选择ai。问求k的最大值，满足能在d天内可以有获得价值大于等于c的方案。

    思路：

    贪心策略先选择大的。将数组从大到小排序，再维护前缀和数组s。考虑k为无穷的情况，如果前d个a[i]加起来>=c，说明可以取无穷。如果k=0，d天中每一天都选最大的，仍

    如果存在需要找满足条件的最大k，对k在0-d做二分即可。

    判断函数：考虑最优策略计算价值，第一天选了a[1]，需要经过k天才能在选择a[1]，期间可以选a[2],a[2]...a[k+1]，等到经过k天之后a[1]可以再选，再经过一天a[2]可以再选。重复这个过程，保证每一天都尽量选前面比较大的值。

    代码：

    1. #include
    2. #define rep(i,a,b) for (register int i=a;i
    3. #define per(i,a,b) for (register int i=a;i>b;--i)
    4. #define endl '\n'
    5. using namespace std;
    6. typedef long long LL;
    7. const int N=2e5+10;
    8. int a[N];
    9. int n,d;
    10. LL c,s[N];
    11. bool cmp(int x,int y)
    12. {
    13. 	return x>y;
    14. }
    15. bool che(int m)
    16. {
    17. 	int q=d/(m+1),r=d%(m+1);
    18. 	LL res=s[min(m+1,n)]*q+s[min(r,n)];
    19. 	if(res>=c) return true;
    20. 	return false;
    21. }
    22. void solve()
    23. {
    24. 	cin>>n>>c>>d;
    25. 	rep(i,1,n+1) cin>>a[i];
    26. 	sort(a+1,a+n+1,cmp);
    27. 	rep(i,1,n+1) s[i]=s[i-1]+a[i];
    28. 	if(1ll*a[1]*d
    29. 		cout<<"Impossible"<
    30. 		return;
    31. 	}
    32. 	if(s[min(d,n)]>=c){
    33. 		cout<<"Infinity"<
    34. 		return;
    35. 	}
    36. 	int l=0,r=d;
    37. 	while(l
    38. 		int m=l+r+1>>1;
    39. 		if(che(m)) l=m;
    40. 		else r=m-1;
    41. 	}
    42. 	cout<
    43. }
    44. int main()
    45. {
    46. 	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    47. 	int _=1;
    48. 	cin>>_;
    49. 	while(_--){
    50. 		solve();
    51. 	}
    52. 	return 0;
    53. }

    G. SlavicG's Favorite Problem

    题目大意：

     t(1≤t≤10^4)组测试，每组给定n(1≤n≤2⋅10^5)个结点的树，结点编号1-n，树上每一条边有一个权值，问能否从a点走到b点，且路径所有边异或值为0。

    运行在任意点进行一次传送，可以传送到除了b点之外的任意一点。

    思路：

    两次搜索，搜索时维护当前异或值。第一次从a搜到b的邻接点，判断能否走到b点。如果能不需要进行第二次搜索。

    在第一次搜索的时候将所有得到异或值记录到集合中，第二次从b开始搜索，如果到某个点的异或和在能集合中找到，说明存在合法路径：a-i点的异或值为x，b-j点的异或值也为x，可以先从a走到i，使用一次传送到j点，走到b，此时总异或和为0。

    注意处理边界情况，必须先将0加入集合中，因为a点本身也是可传送点。

    代码：

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7. #include 
    8. #include 
    9. #include 
    10. #include 
    11. #include 
    12. #include
    13. #include 
    14. #include 
    15. #define pii pair
    16. #define pll pair
    17. #define pil pair
    18. #define pli pair
    19. #define pdd pair
    20. #define se second 
    21. #define fi first
    22. #define endl '\n'
    23. #define rep(i,a,b) for (register int i=a;i
    24. #define per(i,a,b) for (register int i=a;i>b;--i)
    25. #define MEM(a,x) memset(a,x,sizeof(a))
    26. #define M(x) ((x)%MOD)
    27. #define db double
    28. #define eps 1e-9
    29. typedef long long LL;
    30. typedef unsigned long long ULL;
    31. using namespace std;
    32. const LL MOD=998244353;
    33. const int N=1e5+10,M=2*N;
    34. int h[N],e[M],ne[M],idx,w[M];
    35. set<int>st;
    36. int n,a,b;
    37. bool f;
    38. void add(int x,int y,int c)
    39. {
    40. 	e[idx]=y,ne[idx]=h[x],w[idx]=c,h[x]=idx++;
    41. }
    42. void dfs1(int u,int fa,int v)
    43. {
    44. 	if(f) return;
    45. 	for(int i=h[u];i!=-1;i=ne[i]){
    46. 		int j=e[i];
    47. 		if(j==fa) continue;
    48. 		if(j==b){
    49. 			if(v==w[i]){
    50. 				f=1;
    51. 				break;
    52. 			}
    53. 			else continue;
    54. 		}
    55. 		st.insert(v^w[i]);
    56. 		dfs1(j,u,v^w[i]);
    57. 	}
    58. }
    59. void dfs2(int u,int fa,int v)
    60. {
    61. 	if(f) return;
    62. 	for(int i=h[u];i!=-1;i=ne[i]){
    63. 		int j=e[i];
    64. 		if(j==fa) continue;
    65. 		if(st.count(v^w[i])){
    66. 			f=1;
    67. 			return;
    68. 		}
    69. 		dfs2(j,u,v^w[i]);
    70. 	}
    71. }
    72. void solve()
    73. {
    74. 	st.clear();st.insert(0);
    75. 	f=0;
    76. 	idx=0;
    77. 	MEM(h,-1);
    78. 	cin>>n>>a>>b;
    79. 	rep(i,0,n-1){
    80. 		int x,y,c;
    81. 		cin>>x>>y>>c;
    82. 		add(x,y,c),add(y,x,c);
    83. 	}
    84. 	dfs1(a,-1,0);
    85. 	if(f){
    86. 		cout<<"YES"<
    87. 		return;
    88. 	}
    89. 	dfs2(b,-1,0);
    90. 	if(f) cout<<"YES"<
    91. 	else cout<<"NO"<
    92. }
    93. int main()
    94. {
    95. //	#ifndef ONLINE_JUDGE
    96. //    freopen("title.in","r",stdin);
    97. //    freopen("title.out","w",stdout);
    98. //    #endif
    99. 	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    100. 	int _=1;
    101. 	cin>>_;
    102. 	while(_--){
    103. 		solve();
    104. 	}
    105. //	rep(i,1,_+1){
    106. //		printf("Case %d: ",i);
    107. //		solve();
    108. //	}
    109. 	return 0;
    110. }

  • 相关阅读:
    机器学习-分类器-总结
    MyBatis开发的详细步骤
    Android 官方屏幕适配之ScreenMatch
    虚基类设计 c++
    python-函数-统计函数
    一篇文章让你熟悉unordered_map及其模拟实现
    四、《任务列表案例》后端程序实现和测试
    C++ 同构字符串/ 单词规律
    EMAS Serverless 到底有多便利？
    2022 华为 Java 高级面试题及答案
  • 原文地址：https://blog.csdn.net/qq_60256199/article/details/127989316