A.Yura's New Name
算法本质
思维、读题
题目大意
给定一串由^和_组成的字符串，现在要求你向其中添加字符，使其合法。
合法字符串的定义：
- 对于任意字符，其可以和相邻的若干个字符组成
^_^或^^字符串
输出最小化添加字符数。
思路推演
分类讨论，文字详述略微复杂。
B.JoJo's Incredible Adventures
算法本质
思维
题目大意
给定长度n的01字符串s，复制n个s分别称作s[1]、 s[2]、...、s[n]，组成一个n*n的01矩阵。
随后将s[i]字符循环左移i位。
对变化后的01矩阵，输出其中最大全1矩形面积。
n <= 2e5思路推演
稍加模拟可以发现，1的出现都是成片的，其源头是s中连续的1。
- 若
s全为1，显然面积为n*n - 否则：对于
s连续的x个1，一定会形成一个倾斜角为45度的x*x的平行四边形。
其中可以选中的矩形，长边之和固定为x+1，所以最大面积为(x+1)/2 * (x-(x+1)/2)
C.Constructive Problem
算法本质
思维
题目大意
给定长度n的数组a[]，现在选择一对l r，使a[l~r]元素变成同样的任意正整数。
能否使得改变后的a[]的MEX值恰好为改变前a[]的MEX值+1。
输出Yes或No。
思路推演
设改变前的MEX值为x。
我们想要使得改变后MEX为x+1，需要3个条件：
- 创造出
x - 消灭
x+1 - 保留
0~x-1
为了满足创造x的条件，则我们这个任意正整数的值，必须是x。
为了满足消灭x+1的条件，则x+1出现的区间，我们一定需要选中。
至于能不能保留0~x-1，尽可能使选中的区间较小即可。
当然，这里需要讨论一个额外的可能：不存在x+1，那只需要看改变前的MEX是否为n值即可。
D.The Butcher
算法本质
思维、模拟
题目大意
原有数据不详的大矩形a*b，现在对其切割n-1刀（横切or竖切），分割成n个矩形，切割规则如下：
- 每次切割后的矩形，其中一块放入盒子里，另外一块留在案板上继续等待切割
- 矩形无法旋转
现给出这n个打乱顺序后的矩形，请计算其可能的初始形状。
思路推演
现在，这种题要么从最先切的块的矩形开始猜，要么从最后切的块的开始猜。
最后切的块不太好找，最先切的块可以把范围缩小，分别是长最长，宽最长。
因为其独特的切割规则，所以初始矩形必然存在长or宽可以被找到。
所以我们可以假设其第一次是横切、第一次是竖切。
然后依次用长宽还原其切割方式，若能还原则说明可行，不能说明不可行。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
int l[maxn], r[maxn];
map<int, vector<int>> a2b, b2a;
bool vis[maxn];
bool qie(int &a, int &b, char c)
{
bool f=0;
if (c=='a')
{
for (int idx:b2a[b])
{
if (vis[idx]) continue;
a -= l[idx];
f = 1;
vis[idx] = 1;
}
}
else if (c=='b')
{
for (int idx:a2b[a])
{
if (vis[idx]) continue;
b -= r[idx];
f = 1;
vis[idx] = 1;
}
}
return f;
}
// 还原，返回1表示可行，返回0表示不可行
bool dfs(int a, int b, int ct=0)
{
if (a==0 || b==0) return 1;
if (ct%2)
{
if (!qie(a, b, 'a'))
return 0;
}
else
{
if (!qie(a, b, 'b'))
return 0;
}
return dfs(a, b, ct+1);
}
inline void solve()
{
//init
cin>>n;
int ma=0, mb=0, sum=0;
a2b.clear(), b2a.clear();
for (int i=1; i<=n; i++)
{
cin>>l[i]>>r[i];
sum += l[i]*r[i]; // 拿到总面积
ma=max(ma, l[i]);
mb=max(mb, r[i]);
a2b[l[i]].push_back(i);
b2a[r[i]].push_back(i);
}
set<pair<int, int> > ans;
if (sum%ma==0) // 初步判断是否第一次为竖切
{
rep(i,1,n) vis[i]=0;
if (dfs(ma, sum/ma, 0)) // 进一步判断，第一次竖切能否切割成功
ans.insert({ma, sum/ma}); // 可行加入答案
}
if (sum%mb==0)
{
rep(i,1,n) vis[i]=0;
if (dfs(sum/mb, mb, 1))
ans.insert({sum/mb, mb});
}
cout<<ans.size()<<endl;
for (auto i:ans)
cout<<i.first<<" "<<i.second<<endl;
return;
}
评论 (0)