比赛链接:https://codeforc.es/contest/1706
这次只A了 A题。比赛结束后,B题通过面向样例编程看出了一些猫腻,但是是真的不理解题意。也不知道是为什么这么做,更不知道怎么凑出来的塔。
A题:大意是有一个m长度的字符串是由b组成,给出n个数,对于每一个ai,可以使得在m中ai位置的字符变成A或者将m-ai+1位置的字符变成A。
简单模拟一下就好,可以根据贪心思想,看看这个ai是在左半边还是右半边。通过转换,以左为先,如果左已经为A,则将右转换。
code:
#include<bits/stdc++.h> using namespace std; vector<int>ve; char a[60]; int main() { int t; cin>>t; while(t--) { ve.clear(); memset(a,0,sizeof a); int n,m,x; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&x); ve.push_back(x); } for(int i=1;i<=m;i++) a[i] = 'B'; for(int i=0;i<ve.size();i++) { if(ve[i]<=m/2) { if(a[ve[i]]!='A') a[ve[i]] = 'A'; else a[m+1-ve[i]] = 'A'; }else { if(a[m+1-ve[i]]!='A') a[m+1-ve[i]] = 'A'; else a[ve[i]] = 'A'; } } for(int i=1;i<=m;i++) printf("%c",a[i]); printf("\n"); } }
B题:大意是什么我没读懂,反正就是凑个塔,然后就可以面向样例编程了,样例是个好东西啊。
这个题是个贪心或者说是dp的题。
解决方法就是对于给出的n个ai,每个奇数次或偶数次可以继承上一个奇数或偶数的值,并且可以在相反奇偶数情况下+1,题目嘛很复杂很复杂,我非常怀疑出题人是不是先做的样例再出的题。┭┮﹏┭┮
code:
#include "bits/stdc++.h" "bits/stdc++.h" using namespace std; #define ll long long const int MAXN = 100100; int t, n; int dp[2][MAXN]; int main() { /* ios_base::sync_with_stdio(false); cin.tie(NULL);*/ cin >> t; while (t--) { cin >> n; for (int i = 0; i < 2; i++) { for (int j = 1; j <= n; j++) { dp[i][j] = 0; } } for (int i = 1; i <= n; i++) { int x; cin >> x; dp[i & 1][x] = max(dp[i & 1][x], dp[(i ^ 1) & 1][x] + 1); } for(int i=1;i<=n;i++) cout<<dp[0][i]<<" \n"[i==n]; for(int i=1;i<=n;i++) cout<<dp[1][i]<<" \n"[i==n]; /*for (int i = 1; i <= n; i++) cout << max(dp[0][i], dp[1][i]) << " \n"[i == n];*/ } }C题:大意就是给出n个楼的高度,我们定义如果一个楼比它左右两边的楼都高,那么它是一个cool楼,问最少需要再修建多少层楼,可以使得cool楼最大。
一个比较明显的dp题吧。但是我...我推不出来。
分析:首先可以确定的是最多cool楼的数量一定是(n-1)/2向下取整。奇数比较简单,这个我也会,就是隔一个算一个cool楼。
如果是偶数那么会有很多种状态,因为会有“错位”,这里的解决方案就是,我们先正着隔一个数将顺序的一种状态所需要的层数记录下来。除了顺序状态之外的其他任意状态,必然需要最后留下的一个位置。这个是可以确定的。对于是否需要这个位置,我们可以通过一次相加一次相减前一个楼必定已经相加且目前不符合条件了,所以相减,然后通过max来保留一个答案。这里需要想到的是除了顺序第一种状态外,其他状态都需要用到最后一个符合条件楼。
code:
#include "bits/stdc++.h" using namespace std; #define ll long long const int MAXN = 100100; int t, n; ll a[MAXN]; ll get(int i) { return max(0ll, max(a[i - 1], a[i + 1]) - a[i] + 1); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> t; while (t--) { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; if (n & 1) { ll ans = 0; for (int i = 2; i < n; i += 2) ans += get(i); cout << ans << "\n"; continue; } ll tot = 0; for (int i = 2; i < n; i += 2) tot += get(i); ll ans = tot; for (int i = n - 1; i > 1; i -= 2) { tot -= get(i - 1); tot += get(i); ans = min(ans, tot); } cout << ans << "\n"; } }