• zzu2024三月招新(A-F,I-L)

    目录

    1.A

     2.B

    3.C

    4.D

    5.E

    6.F

    7.I

    8.J

    9.K

    10.L

    先吐槽一波,比赛的dev超级难用,没有编辑错误提示,不能复制样例,太草了,开局还开错题了,第一个小时没出题,还好后面写了几个签到,最后出了7题.

    1.A

    这题n比较小,只有1e3,可以n方暴力过,稍大一点就很难了.具体来说就是枚举每个位置作为左端点,然后取两个值作为最大值ma,和最小值cma,往右边遍历加一个值,容易想到有三种情况:

    如果大于ma,则更新为现在的最大值,原来的最大值变成次大值,如果处于ma和cma之间,则原来的次大值更新为这个数,原来的最大值不变,如果小于cma,则无任何变化

    1. #include
    2. using namespace std;
    3. #define int long long
    4. signed main()
    5. {
    6. 	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    7. 	int n;
    8. 	cin>>n;
    9. 	vector<int>a(n+5);
    10. 	for(int i=1;i<=n;i++)cin>>a[i];
    11. 	int ci,zu,ans=0;
    12. 	for(int i=1;i<=n;i++)
    13. 	{
    14. 		ci=min(a[i],a[i+1]);
    15. 		zu=max(a[i],a[i+1]);
    16. 		ans+=ci;
    17. 		for(int j=i+2;j<=n;j++)
    18. 		{
    19. 			if(a[j]>zu)
    20. 			{
    21. 				ci=zu;
    22. 				zu=a[j];
    23. 				ans+=ci;
    24. 			}
    25. 			else if(a[j]ci)
    26. 			{
    27. 				ci=a[j];
    28. 				ans+=ci;
    29. 			}
    30. 			else if(a[j]
    31. 			{
    32. 				ans+=ci;
    33. 			}
    34. 		}
    35. 	}
    36. 	cout<
    37. 	return 0;
    38. }
    39.  
    40.  
    41.

     2.B

    这题是压轴题,容易想到最短路,而求"最大值的最小值"就很二分答案了,所以每试一个x,就检查这个x是否能跑出一个满足a[i]<=x的最短路且不超时,然后根据二分的套路"最小化"答案就行,但不知道为什么二分这个点集的体力数组会wa,如果有人知道,请教教我!这里也贴一个可以ac的代码

    1. #include 
    2. using namespace std;
    3. #define int long long
    4.  
    5. const int N = 1e4 + 10;
    6. int a[N];
    7.  
    8. struct edge {
    9.     int v, w;
    10. };
    11. vector e[N];
    12. int n, m, st, ed, h;
    13. int d[N];
    14. int vis[N];
    15. bool check(int x) {
    16.     for (int i = 0; i <= n; i++) {
    17.         d[i] = 1e18;
    18.         vis[i] = 0;
    19.     }
    20.     priority_queueint,int>> q;
    21.     q.push({0, st});
    22.     d[st] = 0;
    23.  
    24.     if (a[st] > x) return false;
    25.  
    26.     while (!q.empty()) {
    27.         auto now = q.top();
    28.         q.pop();
    29.         int u = now.second;
    30.         if (vis[u]) continue;
    31.         vis[u] = 1;
    32.         for (auto t: e[u]) {
    33.             int v = t.v, w = t.w;
    34.             if (d[v] > d[u] + w && a[v] <= x) {
    35.                 d[v] = d[u] + w;
    36.                 q.push({-d[v], v});
    37.             }
    38.         }
    39.     }
    40.  
    41.     return d[ed] <= h;
    42. }
    43. int bfind()
    44. {
    45.     int l = 0, r = 1e7 + 5;
    46.     while (l+1 < r) {
    47.         int mid = l + r >> 1;
    48.         if (check(mid)) r = mid;
    49.         else l = mid;
    50.     }
    51.     return r;
    52. }
    53. signed main() {
    54.     ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    55.     cin >> n >> m >> st >> ed >> h;
    56.     for (int i = 1; i <= n; i++) {
    57.         cin >> a[i];
    58.     }
    59.     
    60.     for (int i = 1; i <= m; i++) {
    61.         int u, v, w; cin >> u >> v >> w;
    62.         e[u].push_back({v, w});
    63.         e[v].push_back({u, w});
    64.     }
    65.     int ans=bfind();
    66.     if (ans == 1e7 + 5) cout << -1 << '\n';
    67.     else cout << ans << '\n';
    68.     return 0;
    69. }

    3.C

    这题就纯模拟题了,就是代码要写的比较长,没啥思维难度

    1. #include
    2. using namespace std;
    3. #define int long long
    4. string mp[5005];
    5. map<char,pair<int,int>>mmp;
    6. mapint,int>,pair<int,int>>p;
    7. signed main()
    8. {
    9. 	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    10. 	int n,m;
    11. 	cin>>n>>m;
    12. 	for(int i=1;i<=n;i++)
    13. 	{
    14. 		cin>>mp[i];
    15. 		mp[i]=' '+mp[i];
    16. 	}
    17. 	int stx,sty;
    18. 	cin>>stx>>sty;
    19. 	int l;
    20. 	cin>>l;
    21. 	string s;
    22. 	cin>>s;
    23. 	//怎么解决传送
    24. 	for(int i=1;i<=n;i++)
    25. 	{
    26. 		for(int j=1;j<=m;j++)
    27. 		{
    28. 			if(isalpha(mp[i][j]))
    29. 			{
    30. 				if(mmp.find( mp[i][j] )!=mmp.end())
    31. 				{
    32. 					p[mmp[mp[i][j]]]={i,j};
    33. 					p[{i,j}]=mmp[mp[i][j]]; 
    34. 				}
    35. 				else
    36. 				{
    37. 					mmp[ mp[i][j] ]={i,j};
    38. 				}
    39. 			}
    40. 		}
    41. 	}
    42. 	int x=stx,y=sty;
    43. 	//cout<
    44. 	for(int i=0;isize();i++)
    45. 	{
    46. 		int fx,fy;
    47. 		if(s[i]=='R')
    48. 		{
    49. 			 fx=x,fy=y+1;
    50. 		}
    51. 		else if(s[i]=='L')
    52. 		{
    53. 			 fx=x,fy=y-1;
    54. 		}
    55. 		else if(s[i]=='D')
    56. 		{
    57. 			 fx=x+1,fy=y;
    58. 		}
    59. 		else if(s[i]=='U')
    60. 		{
    61. 			 fx=x-1,fy=y;
    62. 		}
    63. 		if(fx<1||fx>n||fy<1||fy>m||mp[fx][fy]=='#')
    64. 			{
    65. 				//cout<
    66. 				continue;
    67. 			}
    68. 		if(p.find({fx,fy})!=p.end())//发现传送阵 
    69. 		{
    70. 			x=p[{fx,fy}].first;
    71. 			y=p[{fx,fy}].second;
    72. 		} 
    73. 		else
    74. 		{
    75. 			x=fx;
    76. 			y=fy;
    77. 		}
    78. 		//cout<
    79. 	}
    80. 	cout<" "<
    81. 	return 0;
    82. }
    83.  
    84.  
    85.

    4.D

    这题是bfs最短路板题,就不多说了

    1. #include
    2. using namespace std;
    3. //#define int long long
    4. string mp[5005];
    5. bool vis[5005][5005];
    6. int dx[]={0,1,0,-1};
    7. int dy[]={1,0,-1,0};
    8. int step[5005][5005];
    9. map<char,pair<int,int>>mmp;
    10. mapint,int>,pair<int,int>>p;
    11. signed main()
    12. {
    13. 	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    14. 	memset(step,0x3f,sizeof(step));
    15. 	int n,m;
    16. 	cin>>n>>m;
    17. 	for(int i=1;i<=n;i++)
    18. 	{
    19. 		cin>>mp[i];
    20. 		mp[i]=' '+mp[i];
    21. 	}
    22. 	//怎么解决传送
    23. 	for(int i=1;i<=n;i++)
    24. 	{
    25. 		for(int j=1;j<=m;j++)
    26. 		{
    27. 			if(isalpha(mp[i][j]))
    28. 			{
    29. 				if(mmp.find( mp[i][j] )!=mmp.end())
    30. 				{
    31. 					p[mmp[mp[i][j]]]={i,j};
    32. 					p[{i,j}]=mmp[mp[i][j]]; 
    33. 				}
    34. 				else
    35. 				{
    36. 					mmp[ mp[i][j] ]={i,j};
    37. 				}
    38. 			}
    39. 		}
    40. 	}
    41. 	//bfs
    42. 	int x1,y1,x2,y2;
    43. 	cin>>x1>>y1>>x2>>y2;
    44. 	queueint,int>>q;
    45. 	step[x1][y1]=0;
    46. 	q.push({x1,y1});
    47. 	//vis[x1][y1]=true;
    48. 	while(!q.empty())
    49. 	{
    50. 		auto t=q.front();q.pop();
    51. 		int x=t.first,y=t.second;
    52. 		if(vis[x][y])continue;
    53. 		vis[x][y]=1;
    54. 		if(x==x2&&y==y2)
    55. 		{
    56. 			break;
    57. 		}
    58. 		for(int i=0;i<4;i++)
    59. 		{
    60. 			int fx=x+dx[i],fy=y+dy[i];
    61. 			if(fx<1||fx>n||fy<1||fy>m||mp[fx][fy]=='#'||vis[fx][fy])
    62. 			continue;
    63. 			if(p.find({fx,fy})!=p.end())
    64. 			{
    65. 				int tx=fx;
    66. 				fx=p[{fx,fy}].first;
    67. 				fy=p[{tx,fy}].second;
    68. 			}
    69. 			q.push({fx,fy});
    70. 			step[fx][fy]=min(step[x][y]+1,step[fx][fy]);
    71. 		}
    72. 	}
    73. 	if(step[x2][y2]!=0x3f3f3f3f)
    74. 	cout<
    75. 	else
    76. 	cout<<-1;
    77. 	return 0;
    78. }
    79.  
    80.  
    81.

    5.E

    这题脑筋急转弯,cf原,题面说的很玄乎,容易把人带进沟里,但其实就是最后一把谁赢了,谁就是最终的获胜者,是本场最简单的题

    1. #include
    2. using namespace std;
    3. #define int long long
    4. signed main()
    5. {
    6. 	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    7. 	string s;
    8. 	cin>>s;
    9. 	cout<back();
    10. 	return 0;
    11. }
    12.  
    13.  
    14.

    6.F

    这题找规律吧,其实有点dp的思想,因为大方向只能往右走,所以每个点的方案数只能由它的左边和左上边推出,想到这个就很简单,就是个斐波那契数列.建议用dp求,不要用dfs求,dfs要写记忆化才能不超时!

    1. #include
    2. using namespace std;
    3. #define int long long
    4. const int maxn=1e6+5;
    5. const int mod=1e9+7;
    6. int dp[maxn];
    7. signed main()
    8. {
    9. 	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    10. 	int n;
    11. 	cin>>n;
    12. 	dp[1]=1,dp[2]=1;
    13. 	for(int i=3;i<=n;i++)
    14. 	{
    15. 		dp[i]=(dp[i-1]+dp[i-2])%mod;
    16. 	}
    17. 	cout<
    18. 	return 0;
    19. }
    20.  
    21.  
    22.

    7.I

    这题纯签到,就遍历一个二维数组,维护一个最大值和一个行标

    1. #include
    2. using namespace std;
    3. #define int long long
    4. signed main()
    5. {
    6. 	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    7. 	int n,m;
    8. 	cin>>n>>m;
    9. 	int a[n+5][m+5];
    10. 	for(int i=1;i<=n;i++)
    11. 	{
    12. 		for(int j=1;j<=m;j++)
    13. 		{
    14. 			cin>>a[i][j];
    15. 		}
    16. 	}
    17. 	int ma=-1,idx;
    18. 	for(int i=1;i<=n;i++)
    19. 	{
    20. 		int cnt=0;
    21. 		for(int j=1;j<=m;j++)
    22. 		{
    23. 			if(a[i][j]==1)
    24. 			cnt++;
    25. 		}
    26. 		if(cnt>ma)
    27. 		{
    28. 			ma=cnt;
    29. 			idx=i;
    30. 		}
    31. 	} 
    32. 	cout<" "<
    33. 	return 0;
    34. }

    8.J

    这题要贪心,因为普通去掉一位数只能降一位,而如果第二位是0,去掉第一位数就可以降大于等于两位,这是最优的,需要特判,如果第二位不是0就只能降一位了,删掉第一个出现的最大的那位数就行,最后还有一个去除前导0的操作.

    1. #include
    2. using namespace std;
    3. #define int long long
    4. signed main()
    5. {
    6. 	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    7. 	int n;
    8. 	cin>>n;
    9. 	string s;
    10. 	cin>>s;
    11. 	int ma=-1,idx=s.size()-1;
    12. 	string st;
    13. 	if(s[1]=='0'&&n>1)
    14. 	{
    15. 		s.erase(s.begin());
    16. 	}
    17. 	else
    18. 	{
    19. 		st.push_back(0);
    20. 	for(int i=0;isize();i++)
    21. 	{
    22. 		if(s[i]>=s[st.back()])
    23. 		{
    24. 			st.push_back(i);
    25. 		}
    26. 		else
    27. 		{
    28. 			idx=st.back();
    29. 			break;
    30. 		}
    31. 	}
    32. 	
    33. 	s.erase(s.begin()+idx);
    34. 	}
    35. 	if(s.size()==0)
    36. 	{
    37. 		cout<<0;
    38. 	}
    39. 	else
    40. 	{
    41. 		int start=s.size();
    42. 		for(int i=0;isize();i++)
    43. 		{
    44. 			if(s[i]!='0')
    45. 			{
    46. 				start=i;
    47. 				break;
    48. 			}
    49. 		}
    50. 		if(start==s.size())
    51. 		{
    52. 			cout<<0;
    53. 		}
    54. 		else
    55. 		{
    56. 			cout<substr(start);
    57. 		}
    58. 	}
    59. 	return 0;
    60. }
    61.  
    62.  
    63.

    9.K

    这题容易以为是dp,但又不知道咋弄,其实是个数学题,结论就是进行k次操作一直正着走能走到多少层,如果n刚好比其中某个数少一,就是操作数加1,如果不是,答案就是那个第一个比它大的数的操作数比如走四步可以走到7,那6的答案就是5,5的答案就是4,因为5比七小二,那只要第1次操作走负1就少了2,正好凑成5

    1. #include
    2. using namespace std;
    3. #define int long long
    4. int n;
    5. bool check(int x)
    6. {
    7.     if(x*(x+1)/2>=n)
    8.     {
    9.         return true;
    10.     }
    11.     else
    12.     return false;
    13. }
    14. int bfind()
    15. {
    16.     int l=0,r=1e6;
    17.     while(l+1
    18.     {
    19.         int mid=l+r>>1;
    20.         if(check(mid))r=mid;
    21.         else l=mid;
    22.     }
    23.     return r;
    24. }
    25. signed main()
    26. {
    27.     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    28.     int t;
    29.     cin>>t;
    30.     while(t--)
    31.     {
    32.         cin>>n;
    33.         int ans=bfind();
    34.         if(ans*(ans+1)/2==n+1)
    35.         cout<<(ans+1)<<"\n";
    36.         else
    37.         cout<"\n";
    38.     }
    39.     return 0;
    40. }

    10.L

    这题签到,就求个前缀和二分就能搞定

    1. #include
    2. using namespace std;
    3. #define int long long
    4. signed main()
    5. {
    6. 	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    7. 	int n,q;
    8. 	cin>>n>>q;
    9. 	vector<int>v(n+5),pre(n+5,0);
    10. 	for(int i=1;i<=n;i++)
    11. 	{
    12. 		cin>>v[i];
    13. 		pre[i]=pre[i-1]+v[i];
    14. 	}	
    15. 	while(q--)
    16. 	{
    17. 		int t;
    18. 		cin>>t;
    19. 		auto it=lower_bound(pre.begin()+1,pre.begin()+1+n,t);
    20. 		if(it!=pre.begin()+1+n)
    21. 		{
    22. 			cout<<(it-pre.begin())<<"\n";
    23. 		}
    24. 		else
    25. 		{
    26. 			cout<<-1<<"\n";
    27. 		}
    28. 	}
    29. 	return 0;

  • 相关阅读:
    error LNK2038: mismatch detected for ‘RuntimeLibrary
    centos7.9 扩容swap分区
    屏幕不清晰，可能是你的设置不正确
    nginx基础
    2022年最新江西建筑施工物料提升（建筑特种作业）模拟题库及答案
    Python 深度学习入门之CNN
    嵌入式学习——网络编程（TCP）——day31
    站内搜索引擎
    下载图片的小程序
    arcgis属性表十进制度转换成度分秒格式--转换坐标注记法
  • 原文地址：https://blog.csdn.net/2301_79076926/article/details/136603226