[HZOI] CSP-S模拟38 赛后总结
不予置评
T1:最小生成树（tree）
#include<bits/stdc++.h>
#define lid (id << 1)
#define rid (id << 1 | 1)
#define Blue_Archive return 0
#define int long long
using namespace std;
constexpr int N = 1e5 + 3;int n;
int m;
int ans;struct miku
{int l,r,val;friend bool operator < (miku a,miku b){return a.val < b.val;}
}a[N];struct mika
{int laz,sum;
}tr[N << 2];inline void pushdown(int id,int l,int r,int mid)
{if(!tr[id].laz) return;tr[lid].laz = 1;tr[rid].laz = 1;tr[lid].sum = (mid - l + 1);tr[rid].sum = (r - mid);tr[id].laz = 0;
}inline void ins(int id,int l,int r,int L,int R)
{if(L <= l && r <= R) {tr[id].laz = 1;tr[id].sum = r - l + 1;return;}int mid = (l + r) >> 1;pushdown(id,l,r,mid);if(L <= mid) ins(lid,l,mid,L,R);if(R > mid) ins(rid,mid + 1,r,L,R);tr[id].sum = tr[lid].sum + tr[rid].sum;
}inline int query(int id,int l,int r,int L,int R)
{if(L <= l && r <= R) return tr[id].sum;int mid = (l + r) >> 1,res = 0;pushdown(id,l,r,mid);if(L <= mid) res += query(lid,l,mid,L,R);if(R > mid) res += query(rid,mid + 1,r,L,R);tr[id].sum = tr[lid].sum + tr[rid].sum;return res;
} signed main()
{freopen("tree.in","r",stdin);freopen("tree.out","w",stdout);// freopen("data.in","r",stdin);freopen("data.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> m;for(int i = 1;i <= m;i ++) cin >> a[i].l >> a[i].r >> a[i].val;sort(a + 1,a + m + 1);for(int i = 1,val,l,r;i <= m;i ++){l = a[i].l;r = a[i].r - 1;val = query(1,1,n - 1,l,r);if(val == r - l + 1) continue;ans += a[i].val * (r - l + 1 - val);ins(1,1,n - 1,l,r);}if(query(1,1,n - 1,1,n - 1) != n - 1) cout << -1 << '\n';else cout << ans << '\n';Blue_Archive;
}
T2：最短路（roads）
#include<bits/stdc++.h>
#define Blue_Archive return 0
#define int long long
#define fi first
#define se second
#define add(u,v,a) to[++ tot] = v,w[tot] = a,nxt[tot] = h[u],h[u] = tot
using namespace std;
constexpr int N = 4e5 + 3;
constexpr int M = 2e6 + 3;
constexpr int INF = 1e18;int n;
int m;
int tot;
int cnt;
int h[N];
int w[M];
int to[M];
int nxt[M];
int dis[M];
int ans[N];bool vis[M];struct miku
{int u,v,a,b;
}a[N];struct mika
{int id,val;
}p[M];priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>> > q;vector<int> vec[N];inline void dijk()
{memset(dis,0x3f,sizeof(dis));q.push({0,vec[1].back()});dis[vec[1].back()] = 0;while(!q.empty()){int u = q.top().se;q.pop();if(vis[u]) continue;vis[u] = 1;for(int i = h[u];i;i = nxt[i]){if(!vis[to[i]] && dis[to[i]] > dis[u] + w[i]){dis[to[i]] = dis[u] + w[i];q.push({dis[to[i]],to[i]});}}}
}signed main()
{// freopen("data.in","r",stdin);freopen("data.out","w",stdout);freopen("roads.in","r",stdin);freopen("roads.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); // 366746381cin >> n >> m;for(int i = 1;i <= m;i ++){cin >> a[i].u >> a[i].v >> a[i].a >> a[i].b;a[i].b = a[i].a - a[i].b;p[++ cnt] = {a[i].v,a[i].a};vec[a[i].v].push_back(cnt);}for(int i = 1;i <= n;i ++) p[++ cnt] = {i,-INF},vec[i].push_back(cnt);for(int i = 1;i <= n;i ++) p[++ cnt] = {i,INF},vec[i].push_back(cnt);for(int i = 1;i <= n;i ++){sort(vec[i].begin(),vec[i].end(),[](int a,int b){return p[a].val < p[b].val;});for(int j = 0;j + 1 < (int)vec[i].size();j ++) add(vec[i][j],vec[i][j + 1],0); // 给每个点按入边排序}for(int i = 1,l,r,mid,res,as;i <= m;i ++){l = 0,r = vec[a[i].v].size() - 1;res = 0,as = 0;while(l <= r){mid = (l + r) >> 1;if(p[vec[a[i].v][mid]].val <= a[i].a) l = mid + 1,res = mid;else r = mid - 1;}add(vec[a[i].u].back(),vec[a[i].v][res],a[i].a);l = 0,r = (int)vec[a[i].u].size() - 1;while(l <= r){mid = (l + r) >> 1;if(p[vec[a[i].u][mid]].val < a[i].a) l = mid + 1,as = mid;else r = mid - 1; }add(vec[a[i].u][as],vec[a[i].v][res],a[i].b);}dijk();for(int i = 1;i <= n;i ++) ans[i] = -1;for(int i = 1;i <= cnt;i ++){if(!vis[i]) continue;if(ans[p[i].id] == -1) ans[p[i].id] = dis[i]; else ans[p[i].id] = min(ans[p[i].id],dis[i]);} for(int i = 1;i <= n;i ++) cout << ans[i] << ' ';cout << '\n';Blue_Archive;
}
T3：计算任务（mission）
#include<bits/stdc++.h>
#define Blue_Archive return 0
#define int long long
#define fi first
#define se second
using namespace std;
constexpr int N = 2e5 + 3;
constexpr int INF = 1e18;int n;
int m;
int tot;
int top;
int tpp;
int ans;
int laz[N];
int stk[N];
int tim[N];
int skk[N];bool del[N];struct miku
{int id;int val;friend bool operator < (miku a,miku b){return a.val < b.val;}friend bool operator > (miku a,miku b){return a.val > b.val;}
};vector<int> bel[N];priority_queue<miku,vector<miku>,greater<miku>> q[N];inline void change(int x,int val)
{if(del[x]) return;tim[x] = val;for(int v : bel[x]) tim[x] += laz[v];for(int v : bel[x]) q[v].push((miku){x,(val / bel[x].size()) + laz[v]});
}inline int query(int x)
{int res = 0;for(int v : bel[x]) res += laz[v];return res;
}signed main()
{freopen("mission.in","r",stdin);freopen("mission.out","w",stdout);// freopen("data.in","r",stdin);freopen("data.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> m;for(int i = 1,op,k,x,pos;i <= m;i ++){cin >> op;if(op == 1){tot ++;cin >> x >> k;x ^= ans;for(int j = 1;j <= k;j ++){cin >> pos;pos ^= ans;bel[tot].push_back(pos);}change(tot,x);}else {top = tpp = 0;cin >> pos >> x;pos ^= ans,x ^= ans;laz[pos] += x;while(q[pos].size() && (q[pos].top().val <= laz[pos] || del[q[pos].top().id])){if(del[q[pos].top().id]){q[pos].pop();continue;} if(query(q[pos].top().id) >= tim[q[pos].top().id]) stk[++ top] = q[pos].top().id,del[q[pos].top().id] = 1;else skk[++ tpp] = q[pos].top().id;q[pos].pop();}for(int j = 1;j <= tpp;j ++) change(skk[j],tim[skk[j]] - query(skk[j])); ans = top;sort(stk + 1,stk + top + 1);cout << top << ' ';for(int i = 1;i <= top;i ++) cout << stk[i] << ' ';cout << '\n';}}Blue_Archive;
}
// 不是她努力就一定能听懂相似三角形的题目。不是她想就可以和他们相似。
// "欢迎回来少年，机房为你开敞"
T4：树上纯树（ture）
#include<bits/stdc++.h>
#define int long long
#define Blue_Archive return 0
#define putchar_unlocked putchar
#define getchar_unlocked getchar
#define con putchar_unlocked(' ')
#define ent putchar_unlocked('\n')
#define add(x,y) to[++ tot] = y,nxt[tot] = h[x],h[x] = tot
#define calc(x,pos) (lin[pos].k * x + lin[pos].b)
using namespace std;
const int N = 1e5 + 3;
const int M = 2e5 + 3;
const int V = 1e6 + 3;
const int INF = 0x7f7f7f7f7f7f7f7f;int n;
int cnt;
int tot;
int tim;
int a[N];
int b[N];// k
int h[N];
int rt[N];
int dp[N];// b
int to[M];
int nxt[M];struct mika
{int k;int b;
}lin[N];struct miku
{int ls;int rs;int mn;
}tr[N << 5];inline int read()
{int k = 0,f = 1;char c = getchar_unlocked();while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar_unlocked();}while(c >= '0' && c <= '9') k = (k << 3) + (k << 1) + c - '0',c = getchar_unlocked();return k * f;
}inline void write(int u)
{if(u < 0) putchar_unlocked('-'),u = -u;if(u > 9) write(u / 10);putchar_unlocked(u % 10 + '0');
}inline void ins(int &id,int l,int r,int L,int R,int pos)
{if(l > R || L > r) return;if(!id) id = ++ cnt;if(!tr[id].mn) {tr[id].mn = pos;return;}int mid = (l + r) >> 1;if(L <= l && r <= R){if(calc(mid,pos) < calc(mid,tr[id].mn)) swap(pos,tr[id].mn);if(calc(l,pos) < calc(l,tr[id].mn)) ins(tr[id].ls,l,mid,L,R,pos);if(calc(r,pos) < calc(r,tr[id].mn)) ins(tr[id].rs,mid + 1,r,L,R,pos);return; }ins(tr[id].ls,l,mid,L,R,pos);ins(tr[id].rs,mid + 1,r,L,R,pos);
}inline int query(int id,int l,int r,int pos)
{if(!id) return INF;if(l == r) return calc(pos,tr[id].mn);int mid = (l + r) >> 1;int res = calc(pos,tr[id].mn);if(pos <= mid) return min(res,query(tr[id].ls,l,mid,pos));else return min(res,query(tr[id].rs,mid + 1,r,pos));
}inline int meg(int p,int q,int l,int r)
{if(!p || !q) return p | q;if(l == r) return calc(l,tr[p].mn) > calc(l,tr[q].mn) ? q : p;int mid = (l + r) >> 1;tr[p].ls = meg(tr[p].ls,tr[q].ls,l,mid);tr[p].rs = meg(tr[p].rs,tr[q].rs,mid + 1,r);ins(p,l,r,-V,V,tr[q].mn);return p;
}inline void dfs(int x,int fa)
{for(int i = h[x];i;i = nxt[i]){if(to[i] == fa) continue;dfs(to[i],x);rt[x] = meg(rt[x],rt[to[i]],-V,V);}if(rt[x]) dp[x] = query(rt[x],-V,V,a[x]);lin[++ tim] = (mika){b[x],dp[x]};ins(rt[x],-V,V,-V,V,tim);
}signed main()
{freopen("ture.in","r",stdin);freopen("ture.out","w",stdout);n = read();for(int i = 1;i <= n;i ++) a[i] = read();for(int i = 1;i <= n;i ++) b[i] = read();for(int i = 1,x,y;i < n;i ++){x = read();y = read();add(x,y);add(y,x);}dfs(1,0);for(int i = 1;i <= n;i ++) write(dp[i]),con;ent;Blue_Archive;
}
//dp[i] = min{dp[j] + a[i] * b[j]}//b[j] == k,dp[j] == b
