D是个交互，一看就不太想做，于是把CE写了些，C算是比较简单的遍历，E写了老半天，近期感觉自己编码能力没以前那么强了
#include<bits/stdc++.h> using namespace std; #define ll long long #define N 200005 int n,T,a,b; struct Node{int len,time;}p[N]; int cmp(Node a,Node b){return a.time<b.time;} int suf1[N],suf2[N]; int main(){ int t;cin>>t; while(t--){ cin>>n>>T>>a>>b; //gthththfghhghg suf1[n+1]=suf2[n+1]=0; ll sum=0; for(int i=1;i<=n;i++){ int f;scanf("%d",&f); if(f) p[i].len=b; else p[i].len=a; sum+=p[i].len; } for(int i=1;i<=n;i++)scanf("%d",&p[i].time); if(sum<=T){ cout<<n<<' '; continue; } sort(p+1,p+1+n,cmp); for(int i=n;i>=1;i--) if(p[i].len==a){ suf1[i]=suf1[i+1]+1; suf2[i]=suf2[i+1]; } else { suf1[i]=suf1[i+1]; suf2[i]=suf2[i+1]+1; } ll total=0; int ans=0; p[0].time=-1; for(int i=1;i<=n;i++){ if(p[i].time==p[i-1].time){total+=p[i].len;continue;} int now=p[i].time-1;//考试时间 if(now<total){total+=p[i].len;continue;} int last=now-total; int res=i-1; if(last/a>suf1[i]){ res+=suf1[i]; last-=suf1[i]*a; res+=min(suf2[i],last/b); } else res+=last/a; ans=max(ans,res); total+=p[i].len; } cout<<ans<<' '; } }
E
/* 用分割后的多边形建图，按拓扑排序的思想，当一个结点度数为2时，它就是下一个被割掉三角形的顶点 所以先把度数是2的点进队， 拓扑排序：当前结点now,每次求出当前和其相连的两个点a，b(有且仅有两个未割掉的点和其相连),在新图上链接now-a,now-b 割掉的顶点用vis标记了 新图必定是个环，最后用dfs扫描一次这个环即可 顺便用map保存编号,ans存每次割掉三角形的编号 */ #include<bits/stdc++.h> #include<map> #include<queue> #include<set> #include<vector> using namespace std; #define N 200005 map<pair<int,int> ,int>mp1; map<pair<int,pair<int,int>>, int> mp; int n,in[N],vis[N]; set<int>E[N]; vector<int>G[N],g[N]; vector<int>ans; vector<int>v; int dfn[N]; void dfs(int x){ dfn[x]=1;v.push_back(x); for(auto y:g[x]) if(!dfn[y])dfs(y); } void init(){ for(int i=1;i<=n;i++){ dfn[i]=in[i]=vis[i]=0; E[i].clear(); G[i].clear(); g[i].clear(); } ans.clear(); v.clear(); mp.clear(); mp1.clear(); } void add1(int u,int v){ E[u].insert(v);E[v].insert(u); } void add2(int u,int v){ G[u].push_back(v); } void add3(int u,int v){ g[u].push_back(v);g[v].push_back(u); } int main(){ int t;cin>>t; while(t--){ init(); cin>>n; for(int i=1;i<=n-2;i++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); add1(a,b);add1(b,c);add1(a,c); mp[make_pair(a,make_pair(b,c))]=i; mp[make_pair(a,make_pair(c,b))]=i; mp[make_pair(b,make_pair(a,c))]=i; mp[make_pair(b,make_pair(c,a))]=i; mp[make_pair(c,make_pair(b,a))]=i; mp[make_pair(c,make_pair(a,b))]=i; } for(int i=1;i<=n;i++) for(auto x:E[i]){ in[i]++; add2(i,x); } queue<int>q; for(int i=1;i<=n;i++)if(in[i]==2)q.push(i); int cnt=0,tot=0; while(q.size()){ int now=q.front();q.pop(); vis[now]=1; int a,b; for(auto x:G[now]) if(!vis[x]){a=x;break;} for(auto x:G[now]) if(!vis[x] && x!=a){b=x;break;} mp1[make_pair(a,b)]=1; mp1[make_pair(b,a)]=1; if(tot<n){ if(!mp1[make_pair(now,a)]) add3(now,a),tot++; if(!mp1[make_pair(now,b)]) add3(now,b),tot++; } ans.push_back(mp[make_pair(now,make_pair(a,b))]); in[a]--;in[b]--; if(in[a]==2)q.push(a); if(in[b]==2)q.push(b); if(++cnt==n-2)break; } dfs(1); // for(int i=1;i<=n;i++) // cout<<g[i].size()<<' '; for(auto x:v)cout<<x<<' '; puts(""); for(auto x:ans)cout<<x<<' '; puts(""); } }