• 蓝桥杯第三场双周赛（AK）

    题目非常典型，很适合学算法。

    1111 第 3 场算法双周赛 - 蓝桥云课

    双十一的祈祷

            题意：求11^{1111}的个位数。

            思路：只需要求个位数，因此此题等效于求11^{1111} mod 10 ,可用快速幂或者直接看出为1。

    1. #include 
    2. using namespace std;
    3. #define LL long long
    4. #define pb push_back
    5. #define x first
    6. #define y second 
    7. #define endl '\n'
    8. const LL maxn = 4e05+7;
    9. const LL N=1e05+10;
    10. const LL mod = 10;
    11. typedef pair<int,int>pl;
    12. priority_queue, greater >t;
    13. priority_queue q;
    14. LL gcd(LL a, LL b){
    15. 	return b > 0 ? gcd(b , a % b) : a;
    16. }
    17.  
    18. LL lcm(LL a , LL b){
    19. 	return a / gcd(a , b) * b;
    20. }
    21. LL qpow(LL a , LL b)//快速幂
    22. {
    23. 	LL sum=1;
    24. 	while(b){
    25. 		if(b&1){
    26. 			sum=sum*a%mod;
    27. 		}
    28. 		a=a*a%mod;
    29. 		b>>=1;
    30. 	}
    31. 	return sum;
    32. }
    33. void solve() 
    34. {
    35. 	cout<<qpow(11,1111);
    36. }            
    37. int main() 
    38. {
    39.     ios::sync_with_stdio(false);
    40.     cin.tie(0);
    41.     cout.tie(0);
    42.     cout.precision(10);
    43.     int t=1;
    44. //	cin>>t;
    45.     while(t--)
    46.     {
    47.     	solve();
    48.     }
    49.     return 0;
    50. }

    疯狂的促销

            题意：三个电商平台优惠不同，现有若干商品，每个商品可以任选平台，求购买所有商品的最低价格。

            思路：直接模拟。

            

    1. #include 
    2. using namespace std;
    3. int algo(int cost){
    4.   int cost1 , cost2 , cost3;
    5.   cost1 = cost >= 500 ? cost - cost / 10 : cost;
    6.   cost2 = cost >= 1000 ? cost - 150 : cost;
    7.   cost3 = cost == 1111 ? 0 : cost - cost / 20;
    8.   return min(cost1 , min(cost2 , cost3));
    9. }
    10. int main()
    11. {
    12.   // 请在此输入您的代码
    13.   int n;
    14.   cin>>n;
    15.   long long sum = 0;
    16.   for(int i = 0 ; i < n ; i ++){
    17.     int num;
    18.     cin>>num;
    19.     sum += algo(num);
    20.   }
    21.   cout<
    22.   return 0;
    23. }

    被替换的身份证

            题意：两个人有两张牌，根据规则谁先出完牌谁赢。

            思路：还是模拟，考虑先手获胜情况：1、有对子/王炸。2、自己最大的牌比对面能打的最大的牌要大。其余都是后手赢。

            

    1. #include 
    2. #include 
    3. using namespace std;
    4. int main()
    5. {
    6.   // 请在此输入您的代码
    7.   int n;
    8.   cin>>n;
    9.   map<char , int>mp;
    10.   string mask = "3456789XJQKA2MF";
    11.   for(int i = 0 ; i < mask.size() ; i ++){
    12.     mp[mask[i]] = i;
    13.   }
    14.   while(n--){
    15.     string s1 , s2;
    16.     cin >> s1 >> s2;
    17.     int sd_1 , sd_2 , j_1 , j_2;
    18.     sd_1 = mp[s1[0]];
    19.     sd_2 = mp[s1[1]];
    20.     j_1 = mp[s2[0]];
    21.     j_2 = mp[s2[1]];
    22.     if(sd_1 > sd_2){
    23.       swap(sd_1 , sd_2);
    24.     }
    25.     if(j_1 > j_2){
    26.       swap(j_1,j_2);
    27.     }
    28.     if(sd_1 == 13 && sd_2 == 14){
    29.       cout<<"ShallowDream";
    30.     }
    31.     else if(sd_1 == sd_2){
    32.       cout<<"ShallowDream";      
    33.     }
    34.     else if(j_1 == 13 && j_2 == 14){
    35.       cout<<"Joker";
    36.     }
    37.     else if(sd_2 >= j_2){
    38.       cout<<"ShallowDream";
    39.     }
    40.     else{
    41.       cout<<"Joker";
    42.     }
    43.     cout<
    44.   }
    45.   return 0;
    46. }

    迷宫逃脱

            题意：迷宫问题，从左上角走到右下角，只能往右或者往下走，每个格子中含有一个数字，若从 a 走到 b 的两个格子中的数字互质，则需要一把钥匙才能走。现在共有 k 把钥匙。求从左上角走到右下角的路径上数字之和的最大值。

            思路：观察到迷宫格子数（1e6）, 钥匙数（3）因此考虑 dp 来做。定义dp[i][j][k]为走到第i行的第j列，消耗了k把钥匙的路径之和最大值。状态转移方程：dp[i][j][k] = max(dp[i][j][k] , dp[i - 1][j][k - 1] + a[i][j])\\ dp[i][j][k] = max(dp[i][j][k] , dp[i][j - 1][k - 1] + a[i][j])(互质情况）

    dp[i][j][k] = max(dp[i][j][k] , dp[i - 1][j][k] + a[i][j])\\ dp[i][j][k] = max(dp[i][j][k] , dp[i][j - 1][k] + a[i][j])（非互质情况）

    1. #include 
    2. using namespace std;
    3. #define LL long long
    4. #define pb push_back
    5. #define x first
    6. #define y second 
    7. #define endl '\n'
    8. const LL maxn = 4e05+7;
    9. const LL N=1e05+10;
    10. const LL mod=1e09+7;
    11. typedef pair<int,int>pl;
    12. priority_queue, greater >t;
    13. priority_queue q;
    14. LL gcd(LL a, LL b){
    15. 	return b > 0 ? gcd(b , a % b) : a;
    16. }
    17.  
    18. LL lcm(LL a , LL b){
    19. 	return a / gcd(a , b) * b;
    20. }         
    21. int main() 
    22. {
    23.     ios::sync_with_stdio(false);
    24.     cin.tie(0);
    25.     cout.tie(0);
    26.     cout.precision(10);
    27. 	int  n , m  , q;
    28. 	cin >> n >> m >> q;
    29. 	LL a[n + 5][m + 5];
    30. 	LL dp[n + 5][m + 5][q + 5];
    31. 	memset(dp , -0x3f3f, sizeof dp);
    32. 	for(int i = 1; i <= n ; i ++)
    33. 		for(int j = 1 ; j <= m ; j ++)
    34. 			cin >> a[i][j];
    35. 	dp[1][1][0] = a[1][1];
    36. 	for(int i = 1 ; i <= n ; i ++){
    37. 		for(int j = 1 ; j <= m ; j ++){
    38. 			for(int k = 0 ; k <= q; k ++){
    39. 				//从上方转移
    40. 				if(i > 1){
    41. 					if(gcd(a[i - 1][j] , a[i][j]) == 1){
    42. 						if(k > 0){
    43. 							dp[i][j][k] = max(dp[i][j][k] , dp[i - 1][j][k - 1] + a[i][j]);
    44. 						}
    45. 					}
    46. 					else{
    47. 						dp[i][j][k] = max(dp[i][j][k] , dp[i - 1][j][k] + a[i][j]);
    48. 					}
    49. 				}
    50. 				//从左侧转移
    51. 				if(j > 1){
    52. 					if(gcd(a[i][j - 1] , a[i][j]) == 1){
    53. 						if(k > 0){
    54. 							dp[i][j][k] = max(dp[i][j][k] , dp[i][j - 1][k - 1] + a[i][j]);
    55. 						}
    56. 					}
    57. 					else{
    58. 							dp[i][j][k] = max(dp[i][j][k] , dp[i][j - 1][k] + a[i][j]);						
    59. 					}
    60. 				}
    61. 			}
    62. 		}
    63. 	}
    64. 	LL maxx = -1e18;
    65. 	for(int i = 0 ; i <= q; i ++){
    66. 		maxx = max(maxx , dp[n][m][i]);
    67. 	}
    68. 	if(maxx > 0)
    69. 		cout<
    70. 	else
    71. 		cout<<-1;
    72.     return 0;
    73. }

    深秋的苹果

            题意：给定一个数组，要求分成m段连续子序列，定义一段子序列的价值为\sum _{i = l}^{r}\sum _{j = l + 1}^{r}A_{i}*A_{j}，求分成m段连续子序列中子序列价值的最大值的最小值。

            思路：最值问题考虑二分来解答，二分子序列价值的最大值即可。

    1. #include 
    2. using namespace std;
    3. const int N = 2e5 + 10;
    4. int n , m;
    5. int a[N];
    6. bool check(long long c){
    7.   long long cnt = 1;
    8.   long long sum = 0;
    9.   long long tt = 0;
    10.   for(int i = 0 ; i < n ; i ++){
    11.       if(tt + sum * a[i] > c){
    12.         cnt ++;
    13.         tt = 0;
    14.         sum = a[i];
    15.       }
    16.       else{
    17.         tt += sum * a[i];
    18.         sum += a[i];
    19.       }
    20.   }
    21.   if(cnt <= m){
    22.     return true;
    23.   }
    24.   else{
    25.     return false;
    26.   }
    27. }
    28. int main()
    29. {
    30.   // 请在此输入您的代码
    31.   cin >> n >> m;
    32.   for(int i = 0 ; i < n ; i ++)
    33.     cin>>a[i];
    34.   long long l = 0 , r = 3e18;
    35.   while(l < r){
    36.     long long mid = (l + r) / 2;
    37.     if(check(mid)){
    38.       r = mid;
    39.     }
    40.     else{
    41.       l = mid + 1;
    42.     }
    43.   }
    44.   cout<
    45.   return 0;
    46. }

     鲜花之海

    在一个幻想的王国中，有一个美丽的花园，花园里开满了各种不同颜色的鲜花。现在花园里一共有 N^2 朵鲜花，这些鲜花都有一个独特且 唯一 的编号，编号由 (a , b)(1 \leq a,b\leq N)两个数字组成。

    这些鲜花按如下规则摆放在花坛中（花坛可以视作一条直线）：

    1. 如果第 X 朵鲜花的编号之和 X_a + X_b小于第 Y 朵鲜花编号之和 Y_a + Y_b，则 XX 朵鲜花放在 YY 朵鲜花前面。
    2. 如果第 X 朵鲜花的编号之和 X_a + X_b 等于第Y 朵鲜花编号之和 Y_a + Y_b ，则哪一朵鲜花的编号 a 更小，哪一朵鲜花就摆在前面。

    现在小蓝需要找到花园中的第 K朵鲜花，但鲜花实在是太多了，他不想一朵朵的去找，你可以快速的告诉他第 K 朵鲜花的编号吗。

            思路：参考曼哈顿距离，将原正方形顺时针旋转90°之后再镜像一下得到一个菱形，其中第一行只有一个元素(1,1) , 第二行有两个元素(1 , 2)(2,1)....共有2 * n - 1行，且上面一行的两坐标之和必然小于下面一行。由于N很大，因此无法通过遍历N来找出第K朵花。对于整个菱形而言，前x行的总数是能够快速得到的，因此考虑二分第K朵花所在的行，然后再快速求出其坐标。

            

    1. #include 
    2. using namespace std;
    3. long long n , k;
    4. long long cnt(long long r){
    5.   long long res = 0;
    6.   if(r > n){
    7.     res += (n + 1) * n / 2;
    8.     res += (n - 1 + (n - (r - n))) * (r - n) / 2; 
    9.   }
    10.   else{
    11.     res += (1 + r) * r / 2;
    12.   }	
    13.   return res;
    14. }
    15. bool check(long long r){
    16.   long long res = cnt(r);
    17.   if(res >= k){
    18.     return true;
    19.   }
    20.   else{
    21.     return false;
    22.   }
    23. }
    24. int main()
    25. {
    26.   // 请在此输入您的代
    27.   int t;
    28.   cin >> t;
    29.   while(t--){
    30. 	  cin >> n >> k;
    31. 	  long long l = 0 , r = 2 * n - 1;
    32. 	  while(l < r){
    33. 	    long long mid = (l + r) / 2;
    34. 	    if(check(mid)){
    35. 	      r = mid;
    36. 	    }
    37. 	    else{
    38. 	      l = mid + 1;
    39. 	    }
    40. 	  }
    41. 	  k -= cnt(l - 1);
    42. 	  if(l <= n){
    43. 	  	int sum = l + 1;
    44. 	  	int x = k;
    45. 	  	int y = sum - k;
    46. 	  	cout << x << " " << y << endl;
    47. 	  }
    48. 	  else{
    49. 	  	int sum = l + 1;
    50. 	  	int x = k + (r - n);
    51. 	  	int y = sum - x;
    52. 	  	cout << x << " " << y << endl;
    53. 	  }
    54.   }
    55.   return 0;
    56. }

    斐波拉契跳跃

            题意：博弈游戏，小蓝和小桥在玩一个数学游戏，游戏规则如下：有一个长度为 n 的 排列  a 和一个棋子，两个人轮流按照游戏规则在排列上移动这个棋子，由小蓝先手，最先不能移动棋子的人判为输。对于某一次移动，设棋子的移动起点为 i，移动的终点为 j，两人移动棋子均需要满足以下游戏规则：

            1、a_{i} < a_{j}。

            2、abs(j - i)是一个斐波那契数。且跳跃的距离要严格大于上一次所跳跃的距离。

            思路：建立sg函数，定义sg[i][j]为第i个点，上一步已经跳了第j个斐波那契数的距离之后是否能走出最后一步，若移动之后无法再移动了，则sg[i][j] = 1（代表了必胜）, 反之sg[i][j] = 0（代表必输）.。其中sg[i][0]表示自身状态，若sg[i][0] == 0 , 则该点必输。由于每个点所能跳跃的点十分有限，因此考虑dfs+记忆化搜索来遍历所有可能情况。

            

    1. #include 
    2. using namespace std;
    3. #define LL long long
    4. #define pb push_back
    5. #define x first
    6. #define y second 
    7. #define endl '\n'
    8. const LL maxn = 4e05+7;
    9. const LL N=1e05+10;
    10. const LL mod=1e09+7;
    11. typedef pair<int,int>pl;
    12. priority_queue, greater >t;
    13. priority_queue q;
    14. LL gcd(LL a, LL b){
    15.     return b > 0 ? gcd(b , a % b) : a;
    16. }
    17. LL lcm(LL a , LL b){
    18.     return a / gcd(a , b) * b;
    19. }
    20. int n;
    21. int fib[30];
    22. int sg[N][30];
    23. int a[N];
    24. int dfs(int x , int l){
    25. 	if(sg[x][l] != -1)
    26. 		return sg[x][l];	
    27. 	int vis[2] = {0};
    28. 	for(int i = l + 1 ; i < 30 ; i ++){
    29. 		int v = fib[i];
    30. 		if(x - v >= 0 && a[x] < a[x - v]){
    31. 			dfs(x - v , i);
    32. 			vis[sg[x - v][i]] = 1;
    33. 		}
    34. 		if(x + v < n && a[x] < a[x + v]){
    35. 			dfs(x + v , i);
    36. 			vis[sg[x + v][i]] = 1;
    37. 		}
    38. 	}
    39. 	if(vis[0])
    40. 		return sg[x][l] = 1;
    41. 	else
    42. 		return sg[x][l] = 0;
    43. }
    44. int main() 
    45. {
    46.     ios::sync_with_stdio(false);
    47.     cin.tie(0);
    48.     cout.tie(0);
    49.     cout.precision(10);
    50. 	fib[0] = 0;
    51. 	fib[1] = 1;
    52. 	fib[2] = 2;
    53. 	for(int i = 3 ; i < 30 ; i ++){
    54. 		fib[i] = fib[i - 1] + fib[i - 2];
    55. 	}
    56. 	cin>>n;
    57. 	for(int i = 0 ; i < n ; i ++){
    58. 		cin >> a[i];
    59. 	}
    60. 	memset(sg , -1 , sizeof sg);
    61. 	for(int i = 0;i < n;i++)
    62. 	{
    63. 	if(dfs(i,0) == 0)
    64. 		cout<<"Little Qiao"<
    65. 	else 
    66. 		cout<<"Little Lan"<
    67. 	}	
    68.     return 0;
    69. }

    星石传送阵

           

            思路：首先答案显然是建完图之后BFS。对于求f(x),需要求出所有的质因子之和（由于要求价值之和最小，假设有一个能量为x * x的星石，那么将其拆为x + x 两块星石的总价值会更小）。需要先把1 ~ 1e4上所有的素数都找出来。然后再对 x 分解质因子。 接下来考虑如何去建图，对于规则2而言，编号为 x 和编号为f(x)的相连，那么总共只会有最多n条边（每个编号一条边）。但是对于规则1而言，若每个能量阵的f(x)都相同，那么需要建n * (n - 1)条边，这是无法接受的。因此不能用操作1来建边。因为其边权值都为1，那么无需存边，只需要将f(x)相等的点放一起即可。在BFS的过程中，对于能量值为 x 的传送阵而言，下一步只需要将f(x)相等的所有的点全部放进去即可，然后又因为此次操作做完以后所有f(x') = f(x)的点全都放进去了，下次再碰到f(y) = f(x)时无需再遍历f(x)相等的所有的点，如此便能无需建边且不重复的BFS。

            

    1. #include 
    2. using namespace std;
    3. #define LL long long
    4. #define pb push_back
    5. #define x first
    6. #define y second 
    7. #define endl '\n'
    8. const LL maxn = 4e05+7;
    9. const LL N = 2e05+10;
    10. const LL NN = 1e4;
    11. const LL mod=1e09+7;
    12. typedef pair<int,int>pl;
    13. priority_queue, greater >t;
    14. priority_queue q;
    15. LL gcd(LL a, LL b){
    16. 	return b > 0 ? gcd(b , a % b) : a;
    17. }
    18. LL lcm(LL a , LL b){
    19. 	return a / gcd(a , b) * b;
    20. }
    21. vectorprime;//存储素数
    22. bool vis[N+5];
    23. vector<int>mp[N];
    24. int depth[N];
    25. int vi[N];//x是否进去
    26. int v[N];//f[i]是否进去
    27. int n , A , B;
    28. struct Node{
    29. 	int x;
    30. 	int fx;
    31. }a[N];
    32. vector<int>f[N];
    33. void su() 
    34. {
    35. 	for(int i = 2;i <= NN;i++)
    36. 	{
    37. 		if(!vis[i])
    38. 		  prime.pb(i);
    39. 		for(int j=0;j < prime.size() && prime[j] * i <= NN;j ++)
    40. 		{
    41. 			vis[prime[j]*i]=1;
    42. 			if(i % prime[j]==0)
    43. 			break;
    44. 		}
    45. 	}
    46. }  
    47. int fun(int a){
    48. 	int len = prime.size();
    49. 	int sum = 0;
    50. 	for(int i = 0 ; i < len ; i++){
    51. 		int x = prime[i];
    52. 		if(a < x){
    53. 			break;
    54. 		}
    55. 		while(a % x == 0){
    56. 			sum += x;
    57. 			a /= x;
    58. 		}
    59. 	}
    60. 	if(a > 1){
    61. 		sum += a;
    62. 	}
    63. 	return (sum % n) + 1;
    64. }
    65. void dfs(){
    66. 	queue<int>q;
    67. 	q.push(A);
    68. 	vi[A] = 1;
    69. 	depth[A] = 0;
    70. 	while(!q.empty()){
    71. 		int x = q.front();
    72. 		q.pop();
    73. 		for(auto it : mp[x]){
    74. 			if(!vi[it]){
    75. 				depth[it] = depth[x] + 1;
    76. 				q.push(it);
    77. 				vi[it] = 1;
    78. 			}
    79. 		}
    80. 		int F = a[x].fx;
    81. 		if(v[F] == 0){
    82. 			for(auto it : f[F]){
    83. 				if(!vi[it]){
    84. 					depth[it] = depth[x] + 1;
    85. 					q.push(it);
    86. 					vi[it] = 1;
    87. 				}				
    88. 			}
    89. 			v[F] = 1;
    90. 		}
    91. 	}
    92. }
    93. int main() 
    94. {
    95.     ios::sync_with_stdio(false);
    96.     cin.tie(0);
    97.     cout.tie(0);
    98.     cout.precision(10);
    99. 	su();
    100. 	cin >> n >> A >> B;
    101. 	for(int i = 0 ; i <= n ; i ++){
    102. 		depth[i] = -1;
    103. 	}
    104. 	for(int i = 1 ; i <= n ; i ++){
    105. 		cin >> a[i].x;
    106. 		a[i].fx = fun(a[i].x);
    107. 		mp[i].pb(a[i].fx);
    108. 		mp[a[i].fx].pb(i);
    109. 		f[a[i].fx].pb(i);
    110. 	}
    111. 	dfs();
    112. 	cout<
    113.     return 0;
    114. }

            

            

  • 相关阅读:
    任务提醒摆件关联传感器调查
    C++ Reference: Standard C++ Library reference: Containers: array: array: at
    Sentinel安装
    JVM内存线程Dump
    python常见的数据类型
    Python - Numpy库的使用（简单易懂）
    linux查看根目录下的目录结构
    如何优雅的比较两个对象是否相等
    【LeetCode383. 赎金信】——map型哈希表、数组型哈希表
    Spire.Office for .NET 8.10.2 同步更新-Crk
  • 原文地址：https://blog.csdn.net/weixin_61825750/article/details/134368337