ps：由于本人一直补不出咖啡题，所以只能写两道签到题的题解了
量子弹弓
贪心 #图
题目
思路
本题有一个理解的关键点：\([1,n]\)的排列\(a\)
如果没有发现给出的点可以自己随意排列，那么本题将会卡死
其次，如何理解量子弹弓强度？
实际上题目的意思是：
- 构造一棵树，使得可以从起点走到终点，再从终点走到起点
- 需要保证每个点都走过
- 每个点都只能作为走一步的起点与终点各一次
- 从\(u\)走到\(v\)时，需要保证\(dis(u,v)\leq W_{u}\)，其中\(W_{u}\)为\(u\)的量子弹弓强度
当所有强度都为1时，很好构造，此时的图即为一条链：
当出现了长度大于等于2的点时（后文解释为什么为2），则出现了一个个“跳板”：
我们采取第一次走完所有的1，接下来走完所有强度大于1的点的贪心策略
图中黄线为第一次走完所有1的路线
为了区分每一次走了多少步，我给每个点走的路都换了颜色~
由于在从终点返回的路上不可以停在来时路上，所以我们需要再来时路（1构成的链）上用强度大于 2的点建跳板
每一次都从当前跳板走到下一个跳板上，直到走到终点
不难发现，每一个强度为\(k\)的跳板对于在单链上返程的贡献都为\(k-2\)步，因为走出当前跳板和进入下一个跳板各要消耗一步
特别地，在下一个目的地是终点或者当前点是起点的时候，消耗的步数从2变成了1，对返程的贡献为\(k-1\)
此外，强度为2的点没有任何贡献，但她们也可以被上述理论所概括
因此我们只需要统计所有强度为1的点的个数，剩余的点都去累积其对返程的贡献
总贡献需要减2来计算返程起点与终点的特殊贡献
如果返程总贡献小于了1链的长度，那么返程失败 ，否则成功
别忘了各种奇妙特判哦~
代码实现
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
#include<set>
using namespace std;
using ll = long long;
#define rep(i, a, b) for(ll i = (a); i <= (b); i++)
#define per(i, a, b) for(ll i = (a); i >= (b); i--)
#define mid ((l+r)>>1)
#define see(stl) for(auto&ele:stl)cout<<ele<<" "; cout<<'\n';const ll N = 2e5+5,mod=998244353,inf=0x3f3f3f3f3f3f3f3f;
ll p[N];
void solve() {ll n;cin>>n;ll ma=0,cnt=0,sum=0;bool zero=0;rep(i,1,n){cin>>p[i];ma=max(ma,p[i]);sum+=max(0ll,p[i]-2);if(p[i]==0)zero=1;if(p[i]==1)cnt++;}sum+=2;if(n==1){cout<<"YES\n";return;}if(zero){cout<<"NO\n";return;}if(n==2&&p[1]>=1&&p[2]>=1){cout<<"YES\n";return;}if(sum<cnt){cout<<"NO\n";return;}cout<<"YES\n";
}int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--)solve();return 0;
}
回忆与展望
数学 #模拟 #贪心
题目
思路
实际上我们很容易想到，这道题只有两个策略，尽可能多的单调增（增减增减），尽可能多的单调不减
然而实际上这道题不能选中其中一个策略贯彻到底，需要找到一个临界点来区分这两种策略哪个更优
开始时先采取增减增减策略，为了保障尽可能多的\(x\)，我们每次选取的上升段的长度都要尽可能大，这就导致了每次选取的上升段长度会越来越小
而上述两种策略就可以转化为对于每次选出来的上升段（长度为\(len\)）进行不同的两种操作：
- 增减增减：
- 加入\(len-1\)个\(x\)贡献，加入一个\(z\)贡献
- 单调不减：
- 将这\(len\)个数并入之前的上升段中，即加入\(len\)个\(y\)
因此比较\(x\times(len-1)+z\)与\(y\times len\)即可知道何时选用何种策略
- 将这\(len\)个数并入之前的上升段中，即加入\(len\)个\(y\)
至于如何找出所有的上升段的长度，我们可以开一个桶数组\(cnt[N]\)记录每个数字出现的次数，桶数组\(term[N]\)记录第\(i\)个上升段的长度
每遍历一个\(a_{i}\)，\(cnt[a_{i}]\!+\!+,term[cnt[a_{i}]\!+\!+]\)
代码实现
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
#include<map>
#include<unordered_map>
using namespace std;
using ll = long long;
#define rep(i, a, b) for(ll i = (a); i <= (b); i++)
#define per(i, a, b) for(ll i = (a); i >= (b); i--)
#define mid ((l+r)>>1)
#define see(stl) for(auto&ele:stl)cout<<ele<<" "; cout<<'\n';const ll N = 5e6+5,mod=998244353,inf=0x3f3f3f3f3f3f3f3f;
ll a[N];
unordered_map<int,int>cnt;
map<int,int>term;
void solve() {cnt.clear();term.clear();int n,x,y,z;cin>>n>>x>>y>>z;rep(i,1,n)cin>>a[i];rep(i,1,n){cnt[a[i]];cnt[a[i]]++;term[cnt[a[i]]];term[cnt[a[i]]]++;}ll ans;bool find=0;int pos=0;for(auto&ele:term){pos++;ll len=ele.second;if(pos==1){ans=len*x;continue;}ll cmp=(x-y==0)?inf:(int)ceil((1.0)*(x-z)/(x-y));if(len<cmp){find=1;}if(!find){ans+=(len-1)*x+z;}else{ans+=(len)*y;}}cout<<ans<<'\n';
}int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--)solve();return 0;
}