新猫
Λ Λ＿_
／(*ﾟーﾟ)／＼
／| ￣U U￣|＼／
| |／
A.Candy Button \(\text{diff } 19\)
你按一次按钮就会得到一颗糖，如果这次按按钮和上次得到糖的间隔时间小于 \(C\) 则不会得到糖，给你若干按按钮的时间，问能得到多少糖
int n,c;
int a[1000001];
signed main(){
cin>>n>>c;
int tot=0;
int last=-1;
for(int i=1;i<=n;++i){
cin>>a[i];
if(last==-1 or a[i]-last>=c){
tot++;
last=a[i];
}
}
cout<<tot<<endl;
}
B.Hands on Ring(Easy) \(\text{diff } 290\)
一个环上有 \(N\) 段，初始时左手在 \(1\)，右手在 \(2\)，手可以每次任意方向移动一步，但是左右手不能重叠，给你若干个操作，表示将一只手移到 \(p_i\)（另一只手不能动）的最小步数
罕见的把史放 T2 的 ABC
我选择分别对两个方向 dfs 一遍
int n,q;
int l=1,r=2;
inline int fixed(int x){
while(x<1) x+=n;
while(x>n) x-=n;
return x;
}
int dfs(int now,bool isadd,bool isl,int step,int goal){
if((isl and now==r) or (isl==false and now==l)) return 0x7fffffff;
if(now==goal) return step;
return dfs(fixed(now+(isadd?1:-1)),isadd,isl,step+1,goal);
}
char getch(){
char ch=getchar();
while(!(ch=='L' or ch=='R')) ch=getchar();
return ch;
}
long long ans=0;
signed main(){
cin>>n>>q;
for(int i=1;i<=q;++i){
char c=getch();int x;cin>>x;
if(c=='L'){
ans+=min(dfs(l,true,true,0,x),dfs(l,false,true,0,x));
l=x;
}
else{
ans+=min(dfs(r,true,false,0,x),dfs(r,false,false,0,x));
r=x;
}
}
cout<<ans<<endl;
}
C.Prepare Another Box \(\text{diff } 366\)
给你若干物品和盒子及其大小，一个盒子只能装一个大小不超过盒子大小的物品，并且你可以买若干个任意容量的盒子，问是否有办法使得所有玩具都装在盒子里，并且没有剩余的盒子，如果有，输出其最小花费
贪心地想，将所有容量从大到小排序，开双指针，如果能放就放，否则直接买，最后判断盒子是否用完即可
int n;
int a[1000001],b[1000001];
signed main(){
cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i];
}
for(int i=1;i<=n-1;++i){
cin>>b[i];
}
sort(a+1,a+n+1,[](int x,int y){return x>y;});
sort(b+1,b+n,[](int x,int y){return x>y;});
int i=1,j=1,ans=0;
while(i<=n){
if(j>n-1){
ans+=a[i];i++;
continue;
}
if(a[i]<=b[j]){
i++;j++;
continue;
}
ans+=a[i];i++;
}
cout<<(j==n?ans:-1)<<endl;
}
D.Cycle \(\text{diff } 743\)
给定有向图，寻找包含 \(1\) 的最小环
\(N\le 2\times 10^5\)
好题
比较考察对 dij 的理解，包含 \(1\) 的最小环，可以看成找一条从 \(1\) 到 \(1\) 的最短路
一般来说我们干这个的时候都是枚举起始点相邻的点，尝试断开连边跑最短路
但是可以发现，如果我们一开始将 \(dis_1\) 设为 \(inf\)，然后对 \(1\) 跑最短路，也能有这个效果
那么你显然就不能用 \(dis_1\) 去做一开始的松弛了，否则你什么也松弛不到，因此你可以往优先队列里放一个 \(dis_1=0\)，然后每次拿出优先队列里的值来松弛其他节点，这样也能做到断边的效果
#define int long long
int n,m;
vector<int>e[200001];
int dis[200001];
bool vis[200001];
struct node{
int id,dis;
bool operator <(const node&A)const{
return dis>A.dis;
}
};
priority_queue<node>q;
void dij(int s){
memset(dis,0x3f,sizeof dis);
q.push({s,0});
while(!q.empty()){
node u=q.top();q.pop();
if(vis[u.id]) continue;
vis[u.id]=true;
for(int i:e[u.id]){
if(dis[i]>u.dis+1){
dis[i]=u.dis+1;
q.push({i,dis[i]});
}
}
}
}
signed main(){
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=m;++i){
int x,y;cin>>x>>y;
e[x].push_back(y);
}
dij(1);
cout<<(dis[1]>=0x3f3f3f3f3f?-1:dis[1])<<endl;
}
E.Max×Sum \(\text{diff } 1063\)
给定两个长为 \(N\) 的数列 \(A,B\)，从 \(N\) 中选 \(K\) 个数，最小化 \(\max\{A_i\}\times \sum\{B_i\}\) 的值
枚举 \(A_i\)，钦定当前的 \(A_i\) 是最大值
就变成了从 \(A_j\) 不超过 \(A_i\) 的 \(j\) 里求 \(b_j\) 的最小值
如果我们从小到大枚举 \(A_i\)，则动态地每次维护 \(b_j\) 前 \(K\) 小之和即可
可以用优先队列实现
#define int long long
int n,k;
int id[200001];
int a[200001],b[2000001];
priority_queue<int>q;
signed main(){
ios::sync_with_stdio(false);
int cases;cin>>cases;while(cases--){
int ans=0x7fffffffffffffff;
while(!q.empty()) q.pop();
cin>>n>>k;
for(int i=1;i<=n;++i){
cin>>a[i];
}
for(int i=1;i<=n;++i){
cin>>b[i];
}
iota(id+1,id+n+1,1);
sort(id+1,id+n+1,[](int x,int y){return a[x]<a[y];});
int tmp=0;
for(int i=1;i<=n;++i){
if(q.size()<k){
tmp+=b[id[i]];q.push(b[id[i]]);
}
else if(q.top()>b[id[i]]){
tmp+=b[id[i]]-q.top();
q.pop();q.push(b[id[i]]);
}
if((int)q.size()<k) continue;
ans=min(ans,a[id[i]]*tmp);
}
cout<<ans<<'\n';
}
}
F.Hands on Ring(Hard) \(\text{diff } 2089\)
考虑 DP 实现
可以 DP 是因为，前一个操作已经帮我们确定了一个手的位置，因此我们可以设 \(f_{i,j}\) 表示进行到操作 \(i\) 的时候，另一只手的位置为 \(j\)
转移很水，直接分讨挪左手右手就行了，但是这个题的转移比 B 题沟史十倍
滚动数组压一下，或者直接压成一维也行
#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
int n,q;
int dp[200001];
int old[200001];
void f(int s,int g,int x,int cnt){
//从 s 到 g 的转移（cnt=f_{i-1}）
g=(g-s+n)%n;
x=(x-s+n)%n;
for(int j=0;j<2;++j){
if(x<=g){
int nt=(g+1)%n;
if(j==1) nt=n-nt;
dp[(nt+s)%n]=min(dp[(nt+s)%n],cnt+g+g+1-x);
}
else{
int nt=x;
if(j==1) nt=n-nt;
dp[(nt+s)%n]=min(dp[(nt+s)%n],cnt+g);
}
g=n-g;
x=n-x;
}
};
int main(){
ios::sync_with_stdio(false);
cin>>n>>q;
char lh='L';int lt=0;
memset(dp,0x3f,sizeof dp);
dp[1]=0;
while(q--){
char h;int t;
cin>>h>>t;
t--;
swap(dp,old);
memset(dp,0x3f,sizeof dp);
for(int i=0;i<n;++i){
if(old[i]!=inf){
if(h==lh){
f(lt,t,i,old[i]);
}
else{
f(i,t,lt,old[i]);
}
}
}
lh=h;lt=t;
}
int ans=inf;
for(int i=0;i<n;++i) ans=min(ans,dp[i]);
cout<<ans<<endl;
}