NOIP 二十连测 day4 温度 很显然的是我们可以先把所有的 a_i 都对 k 取模一下，然后排个序，此时的答案就应该是最大值和最小值的平均值（向上取整） 最优解是要考虑有些 a_i 多减去了一个 k 变成负数，这些 a_i 肯定是排序后数列的一个后缀，枚举这个后缀，每次计算是 O(1) 的。 代码： #include using namespace std; int n,k,ans,a[500005]; signed main(){ cinnk; for(int i=1;ia[i],a[i]%=k; sort(a+1,a+1+n); ans=(a[n]-a[1]+1)/2; for(int i=1;i 小恐龙 考虑这是一个最短路问题，障碍是不能连边的。如果是添加障碍的话很难处理，但如果我们倒着处理，每次减少了一个障碍，由于 k 的大小限制，最短路更新的复杂度是可行的，这样就做完了。 代码： #include using namespace std; #define int long long const int N=1e6+5,inf=1e9; int n,q,k,f[N],ans[N],cnt; bool ob[N],iq[N]; struct node{ int op,x; }op[N]; void push(int s){ queue q0,q1; q0.push(s),iq[s]=1; while(q0.size()||q1.size()){ int u; if(q0.empty()) u=q1.front(),q1.pop(); else if(q1.empty()) u=q0.front(),q0.pop(); else if(q0.front()nqk; for(int i=1;iop[i].opop[i].x; if(op[i].op==1) ob[op[i].x]=1; } for(int i=1;i=1;i--){ if(op[i].op==2){ int x=op[i].x; ans[++cnt]=f[x]=inf?-1:f[x]; } else{ int x=op[i].x; ob[x]=0; int nd=inf; if(x==1) nd=0; else{ if(x-1=1&&!ob[x-1]) nd=min(nd,f[x-1]); if(x-k=1&&!ob[x-k]) nd=min(nd,f[x-k]+1); } if(nd=1;i--) cout
2026-10-22 比赛总结
ooliver