算法本质
思维
题目大意（改）
n-1个连续白色格子，选择2个不靠边、且不相邻的格子涂黑。这样会出现3段连续的白色格子。
最大化（任意两段连续白色格子的格子数差 的 最小值）
思路推演
这实际意味，n-3个块饼干，分割三个人，假设三人的饼干数为a a+b a+b+c。
答案为min(b,c)，若b!=c，实际上会无故浪费饼干。
另外答案与a值无关，a值取最小的1。
三人的饼干数：1 1+x 1+2x（相同ans下所用饼干最少的方案）
于是答案为：ans = (n-3)/(3+3x)
B.Tea with Tangerines
算法本质
思维
题目大意
给n个元素，可以进行以下操作：
- 选择一个元素分成两个元素（和不变）
最小化操作次数，使得任意两个元素x y都保证x < 2y。
思路推演
首先想到的就是，若存在某个数字很小，其他元素需要进行多次操作。
所以我们找到最小的元素作为标值，分割出任意小于标值的操作收益为负，不会进行。
所以只需要保证其他元素在标值的两倍以内即可。
C.Phase Shift
算法本质
思维
题目大意
给定长度n的字符串s，由26个小写字母组成。
这个26个字母乱序形成了一个环，当前字符存在对顺时针方向字符的映射。s中所有字符通过映射改变后变成了t
通过调整字母环的的顺序，最小化t的字典序并输出。
思路推演
每个字母都有一个入度、一个出度，并且他们会整体形成一个环。
样例也明确表示，不能形成一些小环。
从左往右，对于靠前的字符，其肯定想映射能够映射的最小字符。
若说c1-->c2的能够映射包含的条件有：
c1的出度为0c2的入度为0c1-->c2，若会形成环，则必须是26字母形成的大环
其中出度、入度使用数组很容易解决，判断是否成环，则可以使用并查集来表示。
判断集合是否有26个元素：
- 修改一下并查集，新增一个数组：26n的复杂度
- 直接暴力检查，最多26*26n的复杂度
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
// 略作修改的并查集板子略了
inline void solve()
{
//init
cin>>n>>s;
map<char, char>to;
set<char> chu, ru;
init_set(); // 初始化并查集
//cal
for (char c1:s)
{
for (char c2='a'; c2<='z'; c2++)
{
if (chu.count(c1)==0 && ru.count(c2)==0) // 检查入度出度
{
if (find_set(c1)==find_set(c2) && len[c1]+len[c2]<26) // 检查成环的特殊情况
continue;
union_set(c1, c2); // 这里的union_set存在对集合内元素结合的鲁棒性判断
to[c1] = c2; // 维护映射、入度、出度
chu.insert(c1);
ru.insert(c2);
}
}
}
for (char c:s)
cout<<to[c];
cout<<endl;
return;
}D.Meta-set
算法本质
思维
题目大意
给n张卡片的id（保证不同），每张卡片的id由k个数字（数字仅限0 1 2）组成。
定义一个三元组（由三张卡片组成）为美丽三元组：
- 每张卡片的
id第i位要么都相同、或都不同
定义一个五元组为美丽五元组：
- 其中可以选出至少2个美丽三元组
求美丽五元组*数目。
n：[1, 1e3]
k：[1, 20]思路推演
首先看到这个范围，想能否找出所有的美丽三元组，如果可行的话最好。
理论上暴力需要n^3，不够，但是题目给定了限制条件，灵活使用限制条件说不定可行。
这只是看到题目的第一反应和尝试，美丽三元组对后面要求的美丽五元组有帮助，所以简单尝试思考一下，但是不花太多时间。
目前得到的结论是：可能可行具体怎么解，还是要从题目整体视角去看。
美丽五元组需要至少2个美丽三元组，那就从2个入手。
手动模拟一下容易发现，这2个美丽三元组会有1个 or 2个卡片相重合。
2个卡片相重合的情况很快就被抛弃了，只有1个卡片重合的情况。
当卡片a可以组成x个美丽三元组，其为重合卡片组成的美丽五元组有C(x, 2)种情况。
这时就可以发现，必须找到所有的美丽三元组。
当需要降低复杂度时，映射是一个很好的选择。
对于美丽三元组，我们两两组合卡片，剩余的一张卡片id可以计算获得，然后去映射池里寻找。
映射单位可以是数字（三进制转十进制），不过压缩成数字反而代码会写多一些，所以直接vector
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
void to(vector<int> &a, vector<int> &b, vector<int> &c) // 2卡片检测缺失的另一卡片
{
for (int i=1; i<=k; i++)
{
if (a[i] == b[i])
c[i] = a[i];
else
c[i] = 3-a[i]-b[i];
}
}
inline void solve()
{
//init
cin>>n>>k;
vector<vector<int>> cun(n+1, vector<int>(k+1)); // 存放id
map<vector<int>, int> mp; // id-->组合成美丽三元组次数 * 3
for (int i=1; i<=n; i++)
{
cun[i][0] = 0;
for (int j=1; j<=k; j++)
cin>>cun[i][j];
mp[ cun[i] ] = 0;
}
//cal
vector<int> v(k+1);
v[0] = 0;
for (int i=1; i<=n; i++)
{
for (int j=i+1; j<=n; j++)
{
to(cun[i], cun[j], v);
if (mp.count(v))
{
mp[v]++;
mp[ cun[i] ]++;
mp[ cun[j] ]++;
}
}
}
//out
int ans=0;
for (auto u:mp)
{
int x = u.second/3; // 记得除3
ans += x*(x-1)/2;
}
cout<<ans<<endl;
return;
}
评论 (0)