A.Beautiful Sequence
算法本质
思维
题目大意
对于长度n的数组a[]，定义其美丽的：
- 至少存在一个
a[i]=i
定义其帅气的：
- 其子序列至少一个是美丽的
现在检查长度为n的a[]是否帅气。
思路推演
题目转化为，我们找到一个子序列，其中的一个元素等于其下标，这个元素称为奇点。
假设a[1]为奇点，则必须保证a[1]=1，若a[2]为奇点，则必须保证a[2]<=2。
随后验证a[i]<=n时可以称为奇点。
检测一遍即可。
B.Candies
算法本质
思维
题目大意
初始时有一颗糖，可以进行以下两种操作（操作数之和最多40）：
- 糖数 = 原糖数*2 - 1
- 糖数 = 原糖数*2 + 1
最终需要得到n颗糖，复述操作步骤。（不能输出-1）
思路推演
显然，偶数是不可行的。
倒推可以发现，设当前有y颗糖，操作后为x颗糖。若已知y，想保证x为奇数，则只有其中一个操作可以做到。
选择可行的操作，然后循环这个逻辑即可。
C.Make It Permutation
算法本质
思维
题目大意
给定长度n的a[]，进行以下操作，使a[]变为非空排列（下标1开始）：
- c元：删除一个元素
- d元：在任意地方插入一个任意元素
思路推演
有一种方法肯定可行：删除所有元素再加个1。
不过这个结论用处有限，继续思考。
既然最后是排列，则重复的元素一定需要删除。
对于a[]，先排序再去重。
设a[i]为最后排列的最大值。
遍历所有情况的成本，选最小即可。（包括全删加1的情况）
D.Climbing the Tree
算法本质
思维、模拟
题目大意
对于一只蜗牛和树，树高h，蜗牛白天爬a，晚上下降b。
现在给你一颗高度暂时不知的树，接下来有q只蜗牛会来和你交流，有以下两种交流：
- 爬过树的蜗牛：
会告诉你关于它的a b数值，和其所用时间d。如果你目前收集到的情况能证明它说谎，不用理会它；否则当作真实信息接受。 - 没爬过树的蜗牛：
告诉你关于它的a b数值，希望你计算出一个切确的爬树时间。若无法切确到多少天，则输出-1。
思路推演
我们设定树可能最大高度、可能最小高度。
- 爬过树的蜗牛：
通过a b d计算出其爬树的最大可能高度、最小可能高度，与原范围取交集。（若无交集说明其说谎） - 没爬过树的蜗牛：
用当前树的最大可能高度、最小可能高度与a b计算出最长、最短的爬树时间，若一致则输出，否则-1。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
int f(int a, int b, int h) // 给定属性，看需要爬多少天
{
if (a>=h) return 1;
int res=1;
h -= a;
res += (h+a-b-1)/(a-b);
return res;
}
inline void solve()
{
//init
int q;
cin>>q;
int mm=1e18, mi=-1e18;
while (q--)
{
int op, a, b, d;
cin>>op;
if (op==1) // 爬过树的蜗牛
{
cin>>a>>b>>d;
int da = (a-b)*(d-1) + a; // 当前蜗牛爬树的最大可能高度
int xiao = (a-b)*(d-2) + a + 1; // 最小可能高度
if (d==1) // 如果d==1的话，xiao需要特殊处理一下
xiao = 1;
if (da>=mi && xiao<=mm) // 与原数据有交集，说的是大实话
{
mi = max(mi, xiao); // 更新
mm = min(mm, da);
cout<<1<<" ";
}
else // 在说谎
cout<<0<<" ";
}
else if (op==2) // 没爬树的蜗牛
{
cin>>a>>b;
int d1 = f(a, b, mm); // 最长时间
int d2 = f(a, b, mi); // 最短时间
if (d1==d2)
cout<<d1<<" ";
else
cout<<-1<<" ";
}
}
cout<<endl;
return;
}E.Monsters
算法本质
思维
题目大意
给定一个无向图，每个节点存在一个防御力为a[i]的怪物（需要主角的攻击力>=a[i]才能击杀），只有当前节点的怪物被消灭了才可以随意通行。
主角初始攻击力为0，每击杀一个怪物攻击力+1。
主角可以选择某个节点开始，问是否可以击杀所有的怪物。
思路推演
显然，起点只能是a[i]=0的点。
对于一个起点来说，判断是否可行相对简单，类似prime最小生成树的模型即可。
还需要解决的一个问题是：多个起点怎么降低复杂度：
当我们跑某个起点时，遇到其他起点可以顺路标记了（不用重复跑了），这个优化使得最多跑2n个节点。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
int a[maxn];
vector<int> g[maxn];
set<int> v0_used; // 记录已经使用过的0值下标
struct node
{
int val, pos; //
bool operator < (const node &b) const
{
return val > b.val;
}
};
int f(int s)
{
// v0_used.insert(s);
vector<bool> vis(n+5, 0);
priority_queue<node> q;
int power=0;
q.push({a[s], s});
while (q.size())
{
if (power < q.top().val)
return -1;
node u=q.top(); q.pop();
if (vis[u.pos]==1) continue; // 检测是否用过了
vis[u.pos] = 1;
if (u.val==0) v0_used.insert(u.pos); // 优化复杂度
power++;
for (int nxt:g[u.pos])
{
if (vis[nxt]==0)
q.push({a[nxt], nxt});
}
}
return power==n;
}
void clear()
{
for (int i=1; i<=n; i++)
g[i].clear();
v0_used.clear();
}
inline void solve()
{
//init
cin>>n>>m;
clear();
vector<int> v0; // 记录0值下标
for (int i=1; i<=n; i++)
{
cin>>a[i];
if (a[i]==0)
v0.push_back(i);
}
while (m--)
{
int u, v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
//cal
flag=0;
for (int s:v0)
{
if (v0_used.count(s)) continue; // 已经遍历过了
if (f(s)==1)
{
flag=1;
break;
}
}
// out
if (flag)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
return;
}
评论 (0)