比赛链接：Dashboard - Educational Codeforces Round 135 (Rated for Div. 2) - Codeforces
又是一场edu，不过这场掉大分，做的太慢，心态有点炸，A还读错题。
A. Colored Balls: Revisited
题意：给你$n$个颜色的球，每个颜色有$a_i$个，都放在一个盒子里面，你每次拿出两个不同颜色的球，求最后盒子里只有一种颜色是第几种，输出任意一个即可。
思路：读错题是因为觉得问的是一共有多少种可能，那不就是感觉都有可能嘛，但又一想每次要拿出不同颜色的，那又不简单了..再一读题发现是输出任意一个即可，我就用了一个队列模拟了一遍...
实际上用最大的那个数字的下标在第几个就可以了。
代码：
inline void Case_Test()
{
cin>>n;
vector<int> v(n);
for (auto &e:v) cin>>e;
cout<<max_element(v.begin(),v.end())-v.begin()+1<<endl;
}
B. Best Permutation（构造）
题意：给你一个$n$，求构造一个长度为$n$的排列，求以下定义最大的排列“值”：
- 一开始有一个$x=0$
- 如果当前$x\lt a[i]$，那么$x:=x+a[i]$
- 否则$x:=0$
思路：通过看样例可以大胆猜测，一个排列的最大值只有$(n-1)+n$也就是后面两个，具体证明我也没去证明。
那么想象出来这个数列的后面两位，也就是长这个样_,_,_,...,_,n-1,n。那么前面的目的就是清零，也就是倒数第三个需要清零，那么就一直变小？比如：4,3,2,1,5,6，这样可以得到x: 4,0,2,0,5,11。
但是这只是偶数的时候是可以的，奇数的时候是不可以的，比如3,2,1,4,5，这样的x: 3,0,1,5,0，所以需要做一点小操作，只需要错开一位即可，也就是1,3,2,4,5，把1放在前面就好。
代码：
inline void Case_Test()
{
cin>>n;
if (n%2==1)
{
cout<<1<<" ";
for (int i=n-2;i>1;i--) cout<<i<<" ";
}
else
{
for (int i=n-2;i>=1;i--) cout<<i<<" ";
}
cout<<n-1<<" "<<n<<endl;
}
C. Digital Logarithm
题意：给你两个长度为$n$的数组$a,b$，你有一个操作可以对于其中一个数字（a数组或者b数组中的）使其变化，求最小的操作数可以使他们变得一样。
- 选择一个数$x$，使其变成$x:=f(x)$，$f(x)$是$x$的十进制位数。
思路：主要是注意到一点，因为数组的范围最大是$10^9$，所以只需要执行一次的$f(x)$即可变成个位数，所以操作没有那么多。
我原来写法很复杂，现在有Wolfycz的代码很好看，在这里写他的。
一开始设置一个[x,y]:map用来存放数字x出现了y次。
然后读入$a$数组的时候加入到map里面，使其个数++，然后$b$数组的时候会有抵消的作用，为什么呢？因为如果有相同的，那么就肯定不用管的。
那么该如何做呢？就是倒序遍历：
for (auto it = mp.rbegin();it!=mp.rend();it++)
用结构化绑定[x,y]:*it，x就是数字，y就是出现的次数（有可能出现负数，负数的意义就是上面的）
如果y==0的话，那么就continue，因为此时不用管，不然怎么办呢？那就需要进行y次操作（每一个都需要，一共y个），
然后在map中将新的加入，因为是倒序遍历的，所以最后也是可以遍历到的。答案也需要加上Abs(y)，因为y有负数，但是实际上算肯定是需要算正数的。
代码：
map<int,int> mp;
inline void Case_Test()
{
mp.clear();
cin>>n;
for (int i=1;i<=n;i++)
{
cin>>x;
mp[x]++;
}
for (int i=1;i<=n;i++)
{
cin>>x;
mp[x]--;
}
ans = 0;
auto f = [&](int x)
{
int res = 0;
while (x) x/=10, res++;
return res;
};
for (auto it = mp.rbegin();it!=mp.rend();it++)
{
auto [x,y] = *it;
if (y==0) continue;
mp[f(x)] += y;
ans += Abs(y);
}
cout<<ans<<endl;
}
D. Letter Picking（博弈+区间DP）
题意：给你一个长度是偶数的字符串，Alice和Bob互相拿走当前字符串两端的，并且放在自己手中的最前面，最后都取完之后字典序最小的赢，或者平局。
思路：首先需要知道的是，一定不会有Bob的赢得情况，所以要么是一定平局，要么是Alice赢。
区间DP的思路当然就是dp[i][j]表示区间[i,j]是否有一定平局的情况。
注意一定是一定，大部分人都是这个地方错bbabba，比如我在判断dp[1][6]发现转移的时候可以从dp[3][6]的时候转移过来（这里很容易得出dp[3][6]=1也就是有平局的情况）
但是这个情况是基于Alice选择最左边的也就是s[1]='b'，但是实际上这个字符串是Alice赢而不是Draw平局。因为这时候Alice选择的是最右边的a（可以手动模拟一下）
所以需要如何思考呢？因为要求的是一定平局，所以对于当前需要判断的dp[l][r]无论Alice选择的是s[l]还是s[r]，都要有平局的情况才可以使得dp[l][r]=1。
那么对于当前区间[l,r]分为四种情况：
- 1)
Alice选择的是s[l]，Bob选择的是s[l+1]。这时候首先需要dp[l+2][r]=1. - 2)
Alice选择的是s[l]，Bob选择的是s[r]。这时候首先需要dp[l+1][r-1]=1. - 3)
Alice选择的是s[r]，Bob选择的是s[r-1]。这时候首先需要dp[l][r-2]=1. - 4)
Alice选择的是s[r]，Bob选择的是s[l]。这时候首先需要dp[l+1][r-1]=1.
也就是Alice选择s[l]的情况1和情况2的两种情况里，至少需要一个满足条件。Alice选择s[r]的情况3和情况4的两种情况里，至少需要满足一个条件。
所以在两两取或的之后再取并。也就是说不论Alice选择是s[l]还是s[r]，都有一定平局的情况，才可以转移到dp[i][j]=1。
inline bool check(int l,int r)
{
bool r1 = ((dp[l][r-2])&&(s[r-1]==s[r])||(dp[l+1][r-1])&&(s[l]==s[r]));
bool r2 = ((dp[l+2][r])&&(s[l]==s[l+1])||(dp[l+1][r-1])&&(s[l]==s[r]));
return r1&&r2;
}
初始化的话就是基础区间DP的操作，相邻的相等的赋值为1即可，然后每次区间+2扩展。
代码：
int dp[N][N];
inline bool check(int l,int r)
{
bool r1 = ((dp[l][r-2])&&(s[r-1]==s[r])||(dp[l+1][r-1])&&(s[l]==s[r]));
bool r2 = ((dp[l+2][r])&&(s[l]==s[l+1])||(dp[l+1][r-1])&&(s[l]==s[r]));
return r1&&r2;
}
inline void Case_Test()
{
cin>>s;
n = s.size();
for (int i=0;i<n-1;i++)
dp[i][i+1] = (s[i]==s[i+1]);
for (int k=3;k<n;k+=2)
for (int i=0,j=k;j<n;i++,j++)
dp[i][j] = check(i,j);
if (dp[0][n-1]) cout<<"Draw"<<endl;
else cout<<"Alice"<<endl;
}
文章评论
tql carry哥