A.Garland
算法本质
思维
题目大意
给定长度为4、由数字组成的字符串s，表示有4个灯，不同的数字表示不同的灯。
最初灯都是关闭状态，尽量少的进行以下操作，使得灯最后全部为打开状态：（不行输出-1）
- 选择与上次操作选择不同种类的灯，改变其状态
思路推演
如果全部灯都是同一种类，理所当然不能全部打开。
如果有3个灯一样，手动模拟一下发现至少需要6次。
其他情况都不需要反复开关，4次就好。
B.Points on Plane
算法本质
思维、二分
题目大意
给定n，需要我们在一个网格状的无限大棋盘上，需要放置n个棋子：
- 棋子只能放在整数坐标上
- 必须保证所有棋子之间的距离大于1
定义最终棋盘的成本为：棋子与(0,0)的曼哈顿距离最大值。
输出可以最小化的成本。
思路推演
很显然的二分答案，所以我们去找成本 --> 最多棋子的函数。
手动模拟一下，就可以发现放置棋子有2种方式，一种是(0,0)放棋子的，一种是(0,0)不放棋子的。
- 对于第一种方式：
0~1 3~1+8 5~1+8+16……
这是一个简单的等差数列（抛开第一个点） - 对于第二种方式：
1~4 3~4+12 5~4+12+20……
同样是一个简单的等差数列
于是就简单地拿到了方程，二分即可。
如果进一步检查的话，其实可以发现，当成本为x时，最多放置的棋子个数是x^2，可以进一步简化函数。
但是请注意，自带的sqrt()在数字过大的时候有精度问题，1e18相当大，肯定有精度问题，需要自己手写。
C.Sum on Subarrays
算法本质
题目大意
对于长度为n的数组a[]来说，满足下列条件拥有魅力值：
- 元素范围
[-1e3 ~ 1e3] - 任意
[l,r]范围内元素之和不等于0
对于拥有魅力值的a[]来说，其魅力值的具体计算为：
- 其中
[l,r]范围内元素之和 > 0 的数目
现在需要你构造出一个长度为n、魅力值为k的数组。
n <= 30
t <= 5e3思路推演
对于任何区间+个数的题，首先想到的就是固定某一端点。
此题也是一样，假如固定左端点l后，能使得所有[l, ?]的元素和都大于0，则可以很轻松的凑出k来。
显然这理论上可行。
选择固定右端点：
先将k分为若干个<=n且各不相同的数字，设为集合Q。
历便右端点，当r 属于 Q时，表示[?, r]的元素和都需要大于0——相反不属于时，都需要小于0。
对于当前右端点r
如果
r 属于 Q：找到
[?, r-1]元素和的最小值，让a[r] = 最小值+1，保证[?, r]元素和都大于0- 如果
r 不属于 Q：
找到[?, r-1]元素和的最大值，让a[r] = 最大值-1，保证[?, r]元素和都小于0
同时这个做法，显然是：保证所用元素绝对值尽量小为前提。
此题做法很多，可以多看看开拓思路。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
D.Binary String Sorting
算法本质
思维、dp
题目大意
给定01字符串s，进行以下操作使得s变成一个非递减字符串：
- 1e12元：交换2个相邻字符
- 1e12+1元：去掉一个字符
输出最小化花费。
s.length <= 3e5思路推演-1
这个价格，表达的意思是：
- 尽可能减少操作次数
- 如果操作次数一致，尽可能使用交换操作
手动模拟一下就知道，去掉操作是显然优于交换操作（即交换一定可以用去掉代替、去掉不一定用交换代替）。
所以就想到，可以先思考去掉操作，找到最小操作值，然后再琢磨把其中的部分换成交换。
历便s最后01的分界线，前导1+后导0，就可以找到最少的去掉操作次数。
随后发现，当人为设定[1, l-1]全为0、[l, n]全为1的情况时，只有s[l-1]=1 && s[l]=0的情况，交换替换去掉才可以降低成本。
所以我们只需要历便的时候，人为检测一下即可。
思路推演-2
还可以思考一下dp方向，操作简单+不递减的特点，是可以构成前后区间的联系的。
定义dp[x]表示第s[1~x]变成不递减字符串的最少花费。
当我们想要扩展到dp[x+1]时：
- 如果
s[1~x]末尾没有1
很高兴，不用花钱，不管s[x+1]是1还是0，都可以直接放进去 - 如果
s[1~x]末尾有1个1
如果s[x+1]是0，可以用交换，最省钱 - 如果
s[1~x]末尾有多个1
如果s[x+1]是0，那还是去掉最省钱。
可以看到，我们简化为了3个状态，可行。（具体的状态转变不详述了，看代码）
ac核心代码-1
头文件、宏定义、快读模板、常见变量、常见变量等略。
int pre[2][maxn];
int que(int l,int r,int x)
{
return pre[x][r]-pre[x][l-1];
}
inline void solve()
{
//init
cin>>s;
n=s.length();
s=" "+s+" "; //可能会访问s[0]和s[n+1]
//cal 预处理前缀和
for (int i=1; i<=n; i++)
{
pre[0][i]=pre[0][i-1];
pre[1][i]=pre[1][i-1];
pre[s[i]-'0'][i]++;
}
//cal 2
int qu=INF, huan=INF;
for (int i=1; i<=n+1; i++) //[1, i-1]为0，[i, n]为1
{
int n_qu = que(1, i-1, 1) + que(i, n, 0); //全去掉操作
if (qu + huan > n_qu) // 更新答案
{
qu = n_qu;
huan = 0;
}
if (s[i]=='0' && s[i-1]=='1') // 如果可以用1个交换替换2个去掉
{
n_qu-=2;
int n_huan=1;
if (qu+huan > n_qu+n_huan) //重新更新答案
{
qu = n_qu;
huan = n_huan;
}
else if (qu+huan==n_qu+n_huan && huan<n_huan)
{
qu = n_qu;
huan = n_huan;
}
}
}
//out
int ans = qu*((int)1e12+1) + huan*(int)1e12; // 奇葩错误：double前12位准的，这里超了，最后的那个+1在转int的时候会被舍弃
cout<<ans<<endl;
return;
}ac核心代码-2
int dp[3][maxn]; //dp[i][j]：i表示状态，j表示s[1~j]的最小成本
inline void solve()
{
//init
cin>>s;
n=s.length();
s=" "+s;
//cal
int price[2];
price[0] = 1000000000000 + 1; // 去掉的花费
price[1] = 1000000000000; // 交换的花费
for (int i=1; i<=n; i++)
{
if (s[i]=='1')
{
dp[0][i] = dp[0][i-1] + price[0];
dp[1][i] = min(dp[0][i-1], dp[1][i-1]+price[0]);
dp[2][i] = min(dp[1][i-1], dp[2][i-1]);
}
else if (s[i]=='0')
{
dp[0][i] = dp[0][i-1];
dp[1][i] = dp[1][i-1]+price[1];
//dp[1][i]有可能由dp[2][i-1]去掉操作转化而来，但是保证那个不是最优解，且会破坏状态，所以不写
dp[2][i] = dp[2][i-1] + price[0];
}
}
//out
int ans = min(dp[0][n], min(dp[1][n], dp[2][n]));
cout<<ans<<endl;
return;
}
评论 (0)