• 程序设计入门竞赛

    等差数列  

     难绷，掉坑里了QAQ

    这道题首先要知道求等差数列的公式

    然后，求d的时候不要掉进坑以为最小的差值就是公差 No！！！！要是最小数值刚好是公差两倍不就错了是吧，所以这个时候就要求各个值之间的最大公因数！！懂了吧，这才是本题解题的关键（骂自己

    1. #include
    2. using namespace std;
    3. const int N = 1e5 + 10;
    4. int a[N];
    5. int n;
    6. int main()
    7. {
    8.     cin >> n;
    9.     for(int i = 1; i <= n; i ++ ) cin >> a[i];
    10.     sort(a + 1, a + 1 + n);
    11.     int d = a[2] - a[1];
    12.     for(int i = 3; i <= n; i ++ ) d = __gcd(d, a[i] - a[i - 1]);
    13.     if(d == 0) cout << n << endl;
    14.     else cout << (a[n] - a[1]) / d + 1<< endl;
    15.     return 0;
    16. }

    后缀表达式

     md巨坑一道题，一开始贪心错了，后面推把我推吐了QAQ

    推导过程：

    未改良版：

    1. #include
    2. using namespace std;
    3. #define ll long long
    4. int a[200009]; 
    5. int cnt;
    6. int main(){
    7.     int n, m;
    8.     while(cin >> n >> m){
    9.         int N = n + m + 1;
    10.         ll sum = 0;
    11.         for (int i = 0; i < N; i++) {
    12.             cin >> a[i];
    13.             if(a[i] < 0) cnt ++ ;
    14.         }
    15.         sort(a, a + N);
    16.         if (m == 0){
    17.             for (int i = 0; i < N; i++){
    18.                 sum += a[i];
    19.             }
    20.         }
    21.         else if(cnt >= m){
    22.             for(int i = 0; i < N; i ++ )
    23.                 sum += abs(a[i]);
    24.         }
    25.         else{
    26.             for(int i = 0; i < N; i++)
    27.                 sum += abs(a[i]);
    28.             if(cnt == 0) sum -= 2 * a[0]; 
    29.         }
    30.         cout << sum << endl;
    31.     }    
    32.     
    33.     return 0;
    34. }

     改良版

    1. #include
    2. using namespace std;
    3. #define ll long long
    4. int a[200009]; 
    5. int main(){
    6.     int n, m;
    7.     while(cin >> n >> m){
    8.         int N = n + m + 1;
    9.         ll sum = 0;
    10.         for (int i = 0; i < N; i++) cin >> a[i];
    11.         if (m == 0){
    12.             for (int i = 0; i < n + m + 1; i++){
    13.                 sum += a[i];
    14.             }
    15.         }
    16.         else{
    17.             sort(a, a + N);
    18.             sum = a[N - 1] - a[0];
    19.             for (int i = 1; i < N - 1; i++)
    20.                 sum += abs(a[i]);
    21.         }
    22.         cout << sum << endl;
    23.     }    
    24.     
    25.     return 0;
    26. }

    Amity Assessment

     思维题思维题。。。。最讨厌思维题但又比较好理解。。。

    1. #include
    2. using namespace std;
    3. string a, b, c, d;
    4. string s1, s2;
    5. int main(){
    6.     cin >> a >> b >> c >> d;
    7.     for(int i = 0; i < 2; i ++ ){
    8.         if(a[i] != 'X') s1 += a[i];
    9.     }
    10.     for(int i = 1; i >= 0; i -- ){
    11.         if(b[i] != 'X') s1 += b[i];
    12.     }
    13.     s1 += s1;
    14.     for(int i = 0; i < 2; i ++ ){
    15.         if(c[i] != 'X') s2 += c[i];
    16.     }
    17.     for(int i = 1; i >= 0; i -- ){
    18.         if(d[i] != 'X') s2 += d[i];
    19.     }
    20.     if(s1.find(s2) == string :: npos) puts("NO");
    21.     else puts("YES");
    22.     return 0;
    23. }

    Limak and Reverse Radewoosh

     倒在了分数取值不能是负数，应该要干脆点零分QAQ

    1. #include
    2. using namespace std;
    3. int n, c;
    4. const int N = 1010;
    5. int p[N], t[N];
    6. int main(){
    7.     cin >> n >> c;
    8.     for(int i = 0; i < n; i ++ ) cin >> p[i];
    9.     for(int i = 0; i < n; i ++ ) cin >> t[i];
    10.     int tsum1 = 0, sum1 = 0, sum2 = 0, tsum2 = 0;
    11.     for(int i = 0; i < n; i ++ ){
    12.         tsum1 += t[i];
    13.         sum1 += max(0, p[i] - c * tsum1);
    14.     }
    15.     for(int i = n - 1; i >= 0; i -- ){
    16.         tsum2 += t[i];
    17.         sum2 += max(0, p[i] - c * tsum2);
    18.     }
    19.     if(sum1 > sum2) cout << "Limak" << endl;
    20.     if(sum1 < sum2) cout << "Radewoosh" << endl;
    21.     if(sum1 == sum2) cout << "Tie" << endl;
    22.  
    23.     
    24.     return 0;
    25. }

    Limak and Displayed Friends 

    set自动从小到大排序 

    * 注意find函数在set中没有找到的表达

    1. set<int> s;
    2. if(s.find(b[j])==s.end())//b[j]不在set s中
    3. {
    4.      s.insert(b[j]);//执行操作
    5. }
    1. #include
    2. using namespace std;
    3. const int N = 150010;
    4. int t[N], flag[N];
    5. int n, k, q;
    6. set<int> s;
    7. int main(){
    8.     cin >> n >> k >> q;
    9.     for(int i = 1; i <= n; i ++ ) cin >> t[i];
    10.     while(q -- ){
    11.         int type, id;
    12.         cin >> type >> id;
    13.         if(type == 1){
    14.             s.insert(t[id]);
    15.             if(s.size() > k) s.erase(s.begin());
    16.         }
    17.         else if(type == 2){
    18.             if(s.find(t[id]) == s.end()) puts("NO");
    19.             else puts("YES");
    20.         }
    21.     }
    22. }

     看病要排队

     卡住的地方：优先队列的< 、>对应的升降序是不一样的

    1. #include 
    2. using namespace std;
    3. struct stu
    4. {
    5.     int priority, idx;
    6.     bool operator < (const stu &b)const{
    7.         if(priority == b.priority) return idx > b.idx;
    8.         return priority < b.priority;
    9.     }
    10. }temp;
    11.  
    12. int main()
    13. {
    14.     int n;
    15.     priority_queue q[4];
    16.     while(scanf("%d", &n) != EOF){
    17.         int x1, x2, t = 1;
    18.         for(int i = 1; i <= 3; i ++ ){
    19.             while(q[i].size()) q[i].pop();
    20.         }
    21.         string str;
    22.         for(int i = 0; i < n; i ++ ){
    23.             cin >> str;
    24.             if(str == "IN"){
    25.                 cin >> x1 >> x2;
    26.                 temp.idx = t ++ ;
    27.                 temp.priority = x2;
    28.                 q[x1].push(temp);
    29.             }
    30.             else if(str == "OUT"){
    31.                 cin >> x1;
    32.                 if(q[x1].size()){
    33.                     cout << q[x1].top().idx << endl;
    34.                     q[x1].pop();
    35.                 }
    36.                 else cout << "EMPTY" << endl;
    37.             }
    38.             
    39.         }
    40.     }
    41.     return 0;
    42. }

    Cupcake Bonuses 

    1. #include
    2. using namespace std;
    3. typedef long long LL;
    4. const int maxn = 1e6 + 5;
    5. LL base[maxn];
    6. LL ans[maxn];
    7. int n, num = 1;
    8. LL s;
    9. vector<int> vec[maxn];
    10. void dfs(int now,LL val){
    11. 	ans[now] += base[now] * val;
    12. 	for(int i = 0; i < vec[now].size(); i ++ ){
    13. 		dfs(vec[now][i], val);
    14. 	}
    15. }
    16. int main(){
    17.     cin >> n >> s;
    18.     for(int i = 0; i < maxn; i ++ ) base[i] = s;
    19.     memset(ans, 0, sizeof ans);
    20.     while(n -- ){
    21. 	    LL val;
    22.     	int op, id;
    23.     	cin >> op;
    24.     	if(op == 1){
    25.     		cin >> id;
    26.     		num ++ ;
    27.     		vec[id].push_back(num);
    28. 		}
    29. 		else if(op == 2){
    30. 			cin >> id >> val;
    31. 			base[id] = val;
    32. 		}
    33. 		else if(op == 3){
    34. 			cin >> id >> val;
    35. 			dfs(id, val);
    36. 		}
    37. 		else if(op == 4){
    38. 			cin >> id;
    39. 			cout << ans[id] << endl;
    40. 		}
    41. 	}
    42.     return 0;
    43. }

    免费馅饼 

    1. #include
    2. using namespace std;
    3. const int N=100005;
    4. int dp[N][12];
    5. int main()
    6. {
    7. 	int n;
    8. 	int x,T; 
    9. 	while(scanf("%d",&n)==1&&n!=0)
    10. 	{
    11. 		memset(dp,0,sizeof(dp));
    12. 		int m=0;
    13. 		for(int i=0;i
    14. 		{
    15. 			scanf("%d%d",&x,&T);
    16. 			dp[T][x]++;
    17. 			m = max(m, T);
    18. 		}
    19. 		for(int i=m-1;i>=0;i--)
    20. 		for(int j=0;j<11;j++)
    21. 		{
    22. 		    if(j==0)
    23. 		        dp[i][j]+=max(dp[i+1][j],dp[i+1][j+1]);
    24. 		    else if(j==10)
    25. 		        dp[i][j]+=max(dp[i+1][j-1],dp[i+1][j]);
    26. 		    else
    27. 		        dp[i][j]+=max(dp[i+1][j-1],max(dp[i+1][j],dp[i+1][j+1]));
    28. 		}
    29. 		
    30. 		printf("%d\n",dp[0][5]);
    31. 	}
    32. 	return 0;
    33.  } 
    34.

    组建足球队 

    1. #include
    2. using namespace std;
    3. int score[201][10][10], a[201], b[201], c[20], d[20];
    4. int main(){
    5. 	while(1){
    6. 		int j, k, s, n;
    7. 		scanf("%d", &n);
    8. 		int m1, m2, m3;
    9. 		if(n == 0) break;
    10. 		for(int i = 1; i <= n; i ++ ){
    11. 			scanf("%d %d ", &a[i], &b[i]);
    12. 		}
    13. 		for(int i = 0; i <= n; i ++ ){
    14. 			for(int j = 0; j <= 8; j ++ ){
    15. 				for(int k = 0; k <= 8; k ++ ){
    16. 					score[i][j][k] = 0;
    17. 				}
    18. 			}
    19. 		}
    20. 		score[1][1][0] = a[1];
    21. 		score[1][0][1] = b[1];
    22. 		for(int i = 2; i <= n; i ++ ){
    23. 			for(int j = 0; j <= 8 && j <=  i; j ++ ){
    24. 				for(int k = 0; k <= 8 && (j + k <= i); k ++ ){
    25. 					if(j + k == 0) continue;
    26. 					m1 = score[i - 1][j][k];
    27. 					if(j > 0) m2 = score[i - 1][j - 1][k] + a[i];
    28. 					else m2 = 0;
    29. 					if(k > 0) m3 = score[i - 1][j][k - 1] + b[i];
    30. 					else m3 = 0;
    31. 					score[i][j][k] = max(max(m1, m2), m3);
    32. 				}
    33. 			}
    34. 		}
    35. 		printf("%d\n", score[n][8][8]);
    36. 		j = k = 8; 
    37. 		s = 0;
    38. 		for(int m = n; m >= 1; m -- ){
    39. 			if(s == 16) break;
    40. 			if(score[m][j][k] != score[m - 1][j][k]){
    41. 				s ++ ;
    42. 				c[s] = m;
    43. 				if(j > 0){
    44. 					if(score[m][j][k] == score[m- 1][j - 1][k] + a[m]){
    45. 						d[s] = 1;
    46. 						j -- ;
    47. 					}
    48. 					else{
    49. 						d[s] = 2;
    50. 						k -- ;
    51. 					}
    52. 				}
    53. 				else{
    54. 					d[s] = 2;
    55. 					k -- ;
    56. 				}
    57. 			}
    58. 		}
    59. 		for(int i = 16; i >= 1; i -- ){
    60. 			printf("%d %d %d %d\n", c[i], a[c[i]], b[c[i]], d[i]);
    61. 		}
    62. 	}
    63. }

    子序列 

    dp[i] [j] 表示s的前i个包含t的前j个字符所需要修改的最少字符是多少

    当s[i] = t[j]时，也就是字符相同时，就代表这个字符不需要进行修改，故dp[i] [j] = dp[i - 1] [j - 1]

    当s[i] != t[j]时，也就是有可能得修改，修改的话就是dp[i - 1] [j - 1] + 1, 还有可能是之前就已经包含住他了， 就是dp[i - 1] [j]，所以dp[i] [j] = min(dp[i - 1] [j - 1] + 1, dp[i - 1] [j])

    1. #include
    2. #define INF 0x3f3f3f3f
    3. using namespace std;
    4. typedef long long LL;
    5. const int N = 1010;
    6. int dp[N][N];
    7. string s, t;
    8. int main(){
    9.     cin >> s >> t;
    10.     s = " " + s;
    11.     t = " " + t;
    12.     memset(dp, INF, sizeof dp);
    13.     dp[0][0] = 0;
    14.     for(int i = 1; i <= s.size(); ++i)dp[i][0] = 0;
    15.     for(int i = 1; i <= s.size(); ++i){
    16.         for(int j = 1; j <= t.size(); ++j){
    17.             if(s[i] == t[j]){
    18.                 dp[i][j] = dp[i - 1][j - 1];
    19.             }
    20.             else dp[i][j] = min(dp[i - 1][j - 1] + 1, dp[i - 1][j]);
    21.         }
    22.     }
    23.     cout<size()][t.size()]<
    24.     return 0;
    25. }

    年号字串 

    1. #include 
    2. using namespace std;
    3. typedef long long LL;
    4. void fun(LL n){
    5. 	if(n == 0) return;
    6. 	if(n % 26 != 0){
    7. 		fun(n / 26);
    8. 		printf("%c", n % 26 + 'A' - 1); 
    9. 	}
    10. 	else{
    11. 		fun((n - 1) / 26);
    12. 		printf("Z"); 
    13. 	}
    14. }
    15. int main(){
    16. 	LL num;
    17.     while(scanf("%lld", &num) != EOF){
    18.         fun(num);
    19.         puts("");
    20.     }
    21. 	return 0;
    22. }

  • 相关阅读:
    idea使用git版本控制
    Go--数据类型
    java springboot 如何实现小程序支付
    mysql分区表的增删改查操作
    基于NET蛋糕销售网站 毕业设计-附源码090918
    矩阵的乘法运算与css的3d变换（transform）
    IDEA重装后打开的一些设置
    贪心算法 之会议安排
    java学习笔记-初级
    EMNLP 2023 | DeepMind提出大模型In-Context Learning的可解释理论框架
  • 原文地址：https://blog.csdn.net/weixin_63914060/article/details/126453978