$t3$不會

世界線

題解

題目讓求的就是每個點能到點的數量$-$出度

設每個點能到的點為$f[x]$

則$f[x]=x \sum\limits_{y}^{y\in son[x]} U f[y]$

用$bitset$優化一下即可,但單純這樣會炸內存,隨意$yy$一下,時間換空間,像平衡樹一樣開個垃圾桶都行

代碼

#include<bits/stdc++.h> using namespace std; #define ll int #define A 60001 ll dl[A],ans[A],head[A*5],nxt[A*5],ver[A*5],out[A],in[A]; ll n,m,tot,sbzzn=0; bitset<5005> bit[A]; void add(ll x,ll y){nxt[++tot]=head[x],head[x]=tot,ver[tot]=y; } void top(){deque<ll> q;for(ll i=1;i<=n;i++)if(in[i]==0) q.push_back(i);while(!q.empty()){ll top_now=q.front(); // printf("dl[0]=%d top_now=%d\n",dl[0],top_now);dl[++dl[0]]=top_now;q.pop_front();for(ll i=head[top_now];i;i=nxt[i]){ll y=ver[i];// printf("top_now=%d y=%d in[y]=%d\n",top_now,y,in[y]);in[y]--;if(in[y]==0) q.push_back(y);}} } void count(){for(ll l=1,r=5000;l<=n;l=r+1,r+=5000){for(ll i=1;i<=n;i++)bit[i].reset();for(ll i=dl[0];i>=1;i--){ll x=dl[i];for(ll j=head[x];j;j=nxt[j]){ll y=ver[j];bit[x]|=bit[y];}ans[x]+=bit[x].count();if(x>=l&&x<=r) bit[x][x-l]=1;}}for(ll i=1;i<=n;i++){sbzzn+=ans[i]-out[i];}printf("%d\n",sbzzn);} int main(){ //freopen("worldline2.in","r",stdin); //freopen("haha2.in","w",stdout);scanf("%d%d",&n,&m);for(ll i=1,a,b;i<=m;i++){scanf("%d%d",&a,&b);in[b]++;out[a]++;add(a,b);}top();count(); } View Code

時間機器

題解

貪心,簡單線段覆蓋貪心,按照左端點排序,從左端點找到右端點最靠左且能覆蓋的解

驗證正確性

每次枚舉到左端點之前所有比當前左端點還靠左的端點都已經考慮完,若當前取不是最符合的一定不會使結果變優,若當前點放不了一定無解

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long #define A 501010 ll T; ll n,m; struct node{ll l,r,cnt,op;friend bool operator < (const node &a,const node &b){ return (a.l==b.l)?a.op<b.op:a.l<b.l;} }t[A]; map<ll,ll> mp; map<ll,ll> :: iterator it; ll read(){ll f=1,x=0;char c=getchar();while(!isdigit(c)) {if(c=='-') f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return f*x; } int main(){T=read();while(T--){n=read();m=read();mp.clear();ll cnt=0;//先節點,再電阻for(ll i=1;i<=n;i++)t[++cnt].l=read(),t[cnt].r=read(),t[cnt].cnt=read(),t[cnt].op=1;for(ll i=1;i<=m;i++)t[++cnt].l=read(),t[cnt].r=read(),t[cnt].cnt=read(),t[cnt].op=-1;ll ok=1;//printf("oo\n");sort(t+1,t+1+cnt);//存節點,拿節點匹配電阻for(ll i=1;i<=cnt;i++){//printf("t.op=%lld\n",t[i].op);if(t[i].op==-1)mp[t[i].r]+=t[i].cnt;else{while(t[i].cnt){it=mp.lower_bound(t[i].r);// printf("mp[%lld]=%lld\n",t[i].r,mp[t[i].r]);if(it==mp.end()){ok=0;break;}if(t[i].cnt>=it->second) t[i].cnt-=it->second,mp.erase(it);else it->second-=t[i].cnt,t[i].cnt=0;// printf("mp[%lld]=%lld\n",t[i].r,mp[t[i].r]); }if(!ok)break;}}if(ok==0) printf("No\n");else printf("Yes\n");} } View Code

?

轉載于:https://www.cnblogs.com/znsbc-13/p/11516424.html

總結

以上是生活随笔為你收集整理的csp-s模拟测试42「世界线·时间机器·密码」的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。