本文主要是介绍2022年ICPC亚洲区域赛南京站题解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- I: 完美回文
- G: 邪恶铭刻
- A:停停,昨日请不要重现
- D: 聊天程序(待补)
I: 完美回文
解题思路:
签到题,没什么好讲的。
解题代码:
void solve() {vector<int> a(30, 0);string str;cin >> str;int maxx = 0;for(auto i : str){a[i - 'a'] ++;if(a[i - 'a'] > maxx) maxx = a[i - 'a'];}cout << str.size() - maxx << endl;
}
G: 邪恶铭刻
解题思路:
该题的主要思路就是反悔,这三种情况中,卡牌选择和神秘石头都属于固定操作,不需要什么特别的操作。
主要就是分岔路,分岔路以上两种选择,那么我们先想一下到底是哪一种更优,当然是减的更优,尽量让分母更小,当然一定要保证合法的条件下进行。
如果是两种情况下,那么卡牌选择是一定能执行的,那么就是能执行神秘石头就执行,并进行统计,如果后面导致不合法的情况下,那么就要进行让前面的神秘石头变为卡牌选择。
解题代码:
const int N = 1e6+5;
int arr[N];
void solve() {int n; cin >> n;for(int i = 1;i <= n; i++) cin >> arr[i];int p = 1,q = 1,sum = 0;for(int i = 1; i <= n; i++){if(arr[i] == 1){p ++, q++;}else if(arr[i] == -1){if(q <= 1) {if(sum >= 1){sum --;p ++ ,q ++, q++;}else{cout << -1 << endl;return ;}}q--;}else if(arr[i] == 0)if(q > 1) q--, sum ++;else p ++, q++;} int t = __gcd(p,q);cout << p / t << " " << q / t << endl;return ;
}
A:停停,昨日请不要重现
解题思路:
该题是用的二维前缀和;
该题的详细思路是:
- 首先处理边界的袋鼠,将本题想象为没有洞,那么就可以将该题的边界进行缩小,缩小为最后剩余袋鼠的区间。
- 然后进行移动,该题主要不是移动全部的袋鼠,而是移动洞,随便确定一个点,然后将这个点进行移动。
- 因为走过的点不会再有袋鼠进洞,所以要用一个数组进行去重操作。
- 因为要记录某个点被走过几次,那么就用二维前缀和进行计算。
不愧是区域赛的题,思维比省赛的题提高了一个档次。
解题代码:
const int N = 1e3 + 6;
int sum[N][N];
int user[N][N];void add(int x1,int y1, int x2,int y2){if(user[x1][y1]) return ;user[x1][y1] = 1;sum[x1][y1] ++ , sum[x2 + 1][y1] --, sum[x2 + 1][y2 + 1]++, sum[x1][y2 + 1] --;
}void solve(){int n,m,k;cin >> n >> m >> k;for(int i = 1; i <= n + 1; i++){for(int j = 1; j <= m + 1; j++){user[i][j] = 0;sum[i][j] = 0;}}string str;cin >> str;int U = 1, D = n, L = 1, R = m;for(int i = 0, u = 1,d = n, l = 1,r = m; i < str.size(); i++){if(str[i] == 'U') u ++ , d ++;if(str[i] == 'D') u -- , d--;if(str[i] == 'L') l ++, r ++;if(str[i] == 'R') l -- , r --;U = max(U,u);R = min(R,r);D = min(D,d);L = max(L,l);}if(U > D || L > R){if(k == 0) cout << n * m << endl;else cout << 0 << endl;return ;}int x = (D - U + 1) * (R - L + 1) - k; // 剩余的袋鼠的数量add(U,L,D,R);for(int i = 0; i < str.size(); i++){if(str[i] == 'U') U --, D --;if(str[i] == 'D') U ++, D ++;if(str[i] == 'L') L --, R --;if(str[i] == 'R') L ++, R ++;add(U,L,D,R);}for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){sum[i][j] = sum[i][j] + sum[i - 1][j] + sum[i][j -1] - sum[i - 1][j - 1];// cout << sum[i][j] << " ";}// cout << endl;}int res= 0;for(int i =1 ;i <= n; i++){for(int j = 1; j <= m; j++){if(sum[i][j] == x) res ++;}}cout << res << endl;return ;
}
D: 聊天程序(待补)
解题思路:
解题代码:
这篇关于2022年ICPC亚洲区域赛南京站题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!