Torn Lucky Ticket
算法本质
思维角度
题目大意
有若干由数字组成的短字符串（长度<=5），现在选择2个字符串（可以重复选择一个字符串），将其拼接得到字符串s，定义幸运s：
注意不同的拼接方式算两种，但是重复选择一个字符串拼接方式只能算一种
s.length()为偶数s前半部分的数字和等于后半部分数字和
计算有多少种拼接方式可以组成幸运字符串。
思路推演
显然，我们看对于某个字符串s来说，我们希望在其身上提取出一些特征来进行匹配。
如果对于字符串123，这些字符串可以和它匹配：
右侧匹配：
- 长度1、数字和为0
- 长度3、数字和为6
左侧匹配：
- 长度1、数字和为4
- 长度3、数字和为6
但显然，我们可以写一个长度5的字符串来与其匹配。这里就发现了规律，对于幸运字符串来说，用长的字符串去找短的字符串是一个优解。
我们构建一个映射(字符串长度, 字符串数字之和) --> 个数。
然后匹配即可，注意同样长度需要特殊一点，别计算重复了。
XOR Construction
算法本质
思维
题目大意
给定数字n，还有长度n-1的数组a[]，我们需要构建一个长度n的排列p[]（排列值为0~n-1），需要满足：
p[i-1]^p[i] == a[i]
题目保证有解。
思路推演
稍加模拟可以发现，每改变一个元素的值，所有元素的值都会被影响。
我们可以先随意让p[1]=0，然后通过a[]求得p[]。p[]的所有元素异或某个值来满足答案。
实际这个题是看题解才想到的，后面的思路是题解的
既然可以改变二进制位，我们也从二进制位上观察最后的p[]，其每个二进制位上的01个数是一定的。
所以我们只需要检查二进制位，如果不满足就异或这一位。
题目保证有解
还剩下一个问题，如果这个二进制位的01数目一致，则我们如何判断是否该改。
稍加模拟或者思考，即可发现改不改不影响最后的答案。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
cin>>n;
vector<int> v(n);
for (int i=1; i<n; i++) // 给v[0]=0
{
int x=in();
v[i] = x^v[i-1];
}
for (int i=0, val=1; i<=30; i++, val*=2)
{
int cnt=0;
for (int j=0; j<n; j++)
cnt += (val & j) > 0;
for (int j=0; j<n; j++)
cnt -= (val & v[j]) > 0;
if (cnt!=0) // 数目不对
{
for (int j=0; j<n; j++)
v[j] ^= val;
}
}
for (int x:v)
cout<<x<<" ";
return;
}Infinite Card Game
算法本质
思维
题目大意
A有n张卡、B有m张卡，每张卡有2个属性：攻击值和防御值。接下来有2个设定：
- 桌面上至多存在一张卡x，如果希望使用另一张卡y击退它，必须y的攻击值严格大于x的防御值
- 如果卡y击退了卡x，则卡x会退回给它的主人，卡y会留在桌上
初始时，A会随机选择一张卡放在桌上，然后BA轮流行动，如果谁无法击退敌人的卡则算失败。
现在计算A胜利、平局、失败的概论，为了方便输出将其乘以n。
思路推演
勇气，即是信念
游戏有卡牌回收机制，这表明了每次战斗不需要留手，应该选出自己最强的卡牌：
- 能够击败敌人的卡牌，且防御值最高（当攻击值超过敌人的防御时，攻击值就没有了意义。）
我们先思考A可以胜利的情况，需要掏出防御力最强的卡牌，且对手无计可施。我们可以给这张卡牌涂上金色表示其掏出必胜。
如果掏出任意一张卡牌，在对手给予回击后，我们可以掏出一张金色的卡牌，则当前卡牌为金色。
这显然是图的传播方式，同时由于存在贪心思路，我们可以预处理我们每一张卡牌使用之后，对手的策略，然后检查我们是否可以使用金色卡牌。
在脑海中模拟这个预处理的时候有所察觉，也许代码不需要写这么复杂。
为了使得预处理，我们需要将A的卡牌防御值升序，B的卡牌攻击值升序，这有一个小结论：
- A的金色卡牌一定是一个后缀区间（使用防御值升序时）
证：A的金色卡牌一定是一个后缀区间（使用防御值升序时）
反证法，假设存在金色卡牌不是一个后缀区间，则一定存在两张牌a b，其中a是金色卡牌，b非金色卡牌，且防御值：b>=a
B用某张卡牌击退b时，A可以采取面对“B用某张卡牌击退a时”的相同策略。鉴于此，我们可以双指针搞一下即可。
随后为了方便，来计算A失败的卡牌数目，则一定是B有一张强力的防御卡牌。
于是我们可以同样方式求得B的金色卡牌，如果A的第一轮出的牌，B可以使用金色卡牌应对（取最大攻击值即可），则A注定失败。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
// 防御优先
bool cmp(pair<int,int> p1, pair<int, int> p2)
{
if (p1.second == p2.second)
return p1.first < p2.first;
return p1.second < p2.second;
}
inline void solve()
{
vector<pair<int,int>> v1, v2;
cin>>n;
v1.resize(n);
for (int i=0; i<n; i++)
cin>>v1[i].first;
for (int i=0; i<n; i++)
cin>>v1[i].second;
cin>>m;
v2.resize(m);
for (int i=0; i<m; i++)
cin>>v2[i].first;
for (int i=0; i<m; i++)
cin>>v2[i].second;
sort(v1.begin(), v1.end(), cmp); // v1防御优先
sort(v2.begin(), v2.end()); // v2攻击优先
int hackmax = 0; // 表示目前已经确定的金色卡牌的最大攻击值
int defenmax = -1; // 对手面临当前情况会出的牌，其中的最大防御值
// 初始的-1值是为了让初始的hack > defen
int p2 = v2.size()-1;
int p1;
for (p1=v1.size()-1; p1>=0; p1--)
{
while (p2>=0 && v2[p2].first>v1[p1].second) // p2这张牌可以击败p1
defenmax = max(defenmax, v2[p2].second), p2--;
if (hackmax <= defenmax) // 如果打不过对面
break;
hackmax = max(hackmax, v1[p1].first);
}
// [p1+1 ~ v1.size()-1] 为金色卡牌
int num_win = n - (p1+1); // 必胜的次数
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end(), cmp);
hackmax = 0;
defenmax = -1;
p1 = v1.size()-1;
for (p2=v2.size()-1; p2>=0; p2--)
{
while (p1>=0 && v1[p1].first>v2[p2].second)
defenmax = max(defenmax, v1[p1].second), p1--;
if (hackmax <= defenmax)
break;
hackmax = max(hackmax, v2[p2].first);
}
// [p2+1 ~ v2.size()-1] 为金色卡牌
int num_lose=0;
for (auto [x, y] : v1)
if (y < hackmax)
num_lose++;
int num_draw = n - num_win - num_lose;
cout<<num_win<<" "<<num_draw<<" "<<num_lose<<endl;
return;
}title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
评论 (0)