绯色 IOI（开端）
之前做过了，见杂题题解（一），话说这个系列是不是好久没更新了。
Code
const int N=2e5+5;
int n,m,a[N];
int main() {
n=read();
FOR(i,1,n) a[i]=read();
sort(a+1,a+n+1);
ll ans=0;
for(int j=1;j<n-1;j++) ans+=1ll*(a[j]-a[j+2])*(a[j]-a[j+2]);
ans+=1ll*(a[1]-a[2])*(a[1]-a[2])+1ll*(a[n]-a[n-1])*(a[n]-a[n-1]);
printf("%lld\n",ans);
}
绯色 IOI（抵达）
首先先用一个类似 bfs 的过程求出每一个点的庇护所是哪一个点，具体使用 set 稍微维护一下就行。
根据庇护所的关系，可以得到若干个危险指数间的大小关系，将这些关系建边，用堆拓扑排序即可。
Code
const int N=5e5+5;
vi G[N],D[N];
set<int> f[N];
int p[N],don[N],deg[N],a[N],cnt;
int main() {
int n;scanf("%d",&n);
if(n%2==1) return puts("-1"),0;
FOR(i,1,n-1) {
int x,y;scanf("%d %d",&x,&y);
G[x].pb(y),G[y].pb(x);
}
FOR(u,1,n) for(int v:G[u]) f[u].insert(v);
queue<int> q1;
FOR(u,1,n) if(sz(f[u])==1) don[u]=1,q1.push(u);
while(sz(q1)) {
int u=q1.front();q1.pop();
p[u]=*f[u].begin();
for(int v:G[p[u]]) {
f[v].erase(p[u]);
if(don[v]&&!p[v]) return puts("-1"),0;
}
for(int v:G[p[u]]) if(sz(f[v])==1) don[v]=1,q1.push(v);
}
FOR(u,1,n) for(int v:G[u]) if(v!=p[u]) D[p[u]].pb(v),deg[v]++;
priority_queue<int,vector<int>,greater<int> > dq;
FOR(i,1,n) if(deg[i]==0) dq.push(i);
while(sz(dq)) {
int u=dq.top();dq.pop();
a[++cnt]=u;
for(int v:D[u]) if(--deg[v]==0) dq.push(v);
}
if(cnt!=n) return puts("-1"),0;
FOR(i,1,n) printf("%d ",a[i]);
puts("");
}
绯色 IOI（危机）
因为转移代价没有性质，大胆猜测暴力建出 DAG 复杂度是对的。
事实上确实是这样，我们求出每个点可以间接或直接炸到哪里，建出 DAG 拓扑排序 DP 即可。
代码中使用了单调栈来求出区间。
Code
const int N=3e5+5,mod=998244353;
struct bomb {ll x,r;int v,id;} b[N];
bool cmp(bomb a,bomb b) {return a.x<b.x;}
int val[N],deg[N],rid[N],l[N],r[N],st[N],top;
ll f[N],x[N],R[N];
vi G[N];
int main() {
int n;scanf("%d",&n);
FOR(i,1,n) scanf("%lld",&b[i].x),b[i].id=i;
FOR(i,1,n) scanf("%lld",&b[i].r);
FOR(i,1,n) scanf("%d",&b[i].v);
sort(b+1,b+n+1,cmp);
FOR(i,1,n) x[i]=b[i].x,R[i]=b[i].r,val[i]=b[i].v,rid[b[i].id]=i;
FOR(i,1,n) {
l[i]=lower_bound(x+1,x+n+1,x[i]-R[i])-x;
r[i]=upper_bound(x+1,x+n+1,x[i]+R[i])-x-1;
}
FOR(i,1,n) {
while(top&&st[top]>=l[i]) chkmin(l[i],l[st[top]]),top--;
st[++top]=i;
}
top=0;
ROF(i,n,1) {
while(top&&st[top]<=r[i]) chkmax(r[i],r[st[top]]),top--;
st[++top]=i;
}
FOR(i,1,n) FOR(j,l[i],r[i]) if(j!=i) G[i].pb(j),deg[j]++;
queue<int> q;
FOR(i,1,n) if(deg[i]==0) q.push(i);
while(sz(q)) {
int u=q.front();q.pop();
for(int v:G[u]) {
f[v]=max(f[v],f[u]+(1ll*val[u]*val[v]%mod+(val[u]^val[v])%mod)%mod);
if(--deg[v]==0) q.push(v);
}
}
FOR(i,1,n) printf("%lld\n",f[rid[i]]);
}
绯色 IOI（悬念）
我们将问题稍微转化一波，考虑对于两条从左部点 \(a_i\) 出发的边，设他们连向 \(b_i,b_j\)，改为将 \(b_i,b_j\) 连一条无向边，要求将所有的无向边定向，使得每个点入度为 \(1\) 并且对应的权最大。
因为左侧满匹配，利用 Hall 定理得到，在左侧的任意一个 \(k\) 的点集，往右边连到的点集大于等于左边点的个数，左边是边而右边是点，故图的任意一个连通块为基环树或树。
基环树是简单的，因为每个点入度为 \(1\)，故树边一定是叶向的，而环边要么是顺时针要么是逆时针的，这些都很好维护。
树的话考虑定根，定成叶向树，维护每个点的答案，若一条边定成 \(u\to v\)，则根不在 \(v\) 的子树内会有贡献，否则则根在 \(v\) 的子树内会有贡献。
区间加维护区间 \(\max\) 即可。
不想写。
标签：q1,03,int,top,push,NOIP2022,deg,2022.11,dq From： https://www.cnblogs.com/cnyzz/p/16854899.html