首页 > 文章 > noip模拟测试42

noip模拟测试42


T1:世界线

  简单思考后会发现,每个点需要向它能到达(直接或间接)的所有点连边

  即:若点$i$能到达的点有$cnt_i$个,则答案为$\sum _{i=1} ^{n} cnt_i - deg_{out} [i]$

  考虑用bitset维护每个点能到达的点集,发现空间卡不下,而时间有剩余

  于是用时间换空间,bitset的大小只开一半,然后跑两次算法,分别计算$1->n/2$与$n/2+1->n$的答案

分享图片
 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<cstdlib>
 6 #include<algorithm>
 7 #include<bitset>
 8 #include<queue>
 9 #define ll long long
10 using namespace std;
11 const int MAXN=60233,MAXM=100233;
12 int n,m,h[MAXN],tot,deg[MAXN],du[MAXN],vis[MAXN];
13 ll ans;
14 struct node {
15     int to,nxt;
16 }mp[MAXM];
17 bitset<30005> bt[MAXN],zero;
18 queue<int> q;
19 inline int R() {
20     int a=0;char c=getchar();
21     while(c>9||c<0)c=getchar();
22     while(c>=0&&c<=9)a=a*10+c-0,c=getchar();
23     return a;
24 }
25 void add(int x,int y) {
26     mp[++tot].nxt=h[x];
27     mp[tot].to=y;
28     h[x]=tot;
29 }
30 int main() {
31     n=R();m=R();
32     for(int i=1,aa,bb;i<=m;i++) {
33         aa=R(),bb=R();
34         add(aa,bb);++du[bb];
35     }
36     
37     for(int i=1;i<=n;i++) {
38         if(i<=n/2)bt[i][i]=1;
39         deg[i]=du[i];
40         if(!du[i]) q.push(i);
41     }
42     while(!q.empty()) {
43         int u=q.front();q.pop();
44         for(int i=h[u];i;i=mp[i].nxt) {
45             int v=mp[i].to;
46             bt[v]|=bt[u];
47             if(!--deg[v]) q.push(v);
48         }
49     }
50     for(int i=1;i<=n;i++)
51         ans+=bt[i].count();
52     
53     for(int i=1;i<=n;i++) bt[i].reset();
54     
55     for(int i=1;i<=n;i++) {
56         if(i>n/2)bt[i][i-n/2]=1;
57         deg[i]=du[i];
58         if(!du[i]) q.push(i);
59     }
60     while(!q.empty()) {
61         int u=q.front();q.pop();
62         for(int i=h[u];i;i=mp[i].nxt) {
63             int v=mp[i].to;
64             bt[v]|=bt[u];
65             if(!--deg[v]) q.push(v);
66         }
67     }
68     for(int i=1;i<=n;i++)
69         ans+=bt[i].count();
70     
71     for(int i=1;i<=n;i++)
72         ans-=(du[i]+1);
73     
74     printf("%lld\n",ans);
75     return 0;
76 }
t1 Code


T2:时间机器

  深受网络流毒害……

  其实就是个简单的线段覆盖贪心,对左端点排序

  对于所有左端点小于当前线段的左端的区间,优先选择右端点较小的来覆盖当前线段

  用个set维护候选区间就行了

分享图片
 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<cstdlib>
 6 #include<algorithm>
 7 #include<set>
 8 using namespace std;
 9 const int MAXN=50233;
10 int T,n,m,p,flag;
11 inline int R() {
12     int a=0;char c=getchar();
13     while(c>9||c<0)c=getchar();
14     while(c>=0&&c<=9)a=a*10+c-0,c=getchar();
15     return a;
16 }
17 struct point {
18     int r,c;
19     point(int _r,int _c) {
20         r=_r,c=_c;
21     }
22     point() {r=c=0;}
23 };
24 bool operator < (const point &aa,const point &bb) {
25     return aa.r<bb.r;
26 }
27 set<point> st;
28 set<point>::iterator it;
29 struct node {
30     int l,r,s;
31 }nd[MAXN],ri[MAXN];
32 bool operator < (const node &aa,const node &bb) {
33     if(aa.l!=bb.l) return aa.l<bb.l;
34     return aa.r<bb.r;
35 }
36 int main() {
37     T=R();
38     while(T--) {
39         st.clear();
40         n=R(),m=R();
41         for(int i=1;i<=n;i++) nd[i].l=R(),nd[i].r=R(),nd[i].s=R();
42         for(int i=1;i<=m;i++) ri[i].l=R(),ri[i].r=R(),ri[i].s=R();
43         sort(nd+1,nd+n+1),sort(ri+1,ri+m+1);
44         int tp=1;
45         for(int i=2;i<=n;i++) {
46             if(nd[i].l==nd[tp].l&&nd[i].r==nd[tp].r) nd[tp].s+=nd[i].s;
47             else nd[++tp]=nd[i];
48         }
49         n=tp;tp=1;
50         for(int i=2;i<=m;i++) {
51             if(ri[i].l==ri[tp].l&&ri[i].r==ri[tp].r) ri[tp].s+=ri[i].s;
52             else ri[++tp]=ri[i];
53         }
54         m=tp;
55         p=1;flag=0;
56         for(int i=1;i<=n;i++) {
57             for(;p<=m&&ri[p].l<=nd[i].l;++p)
58                 st.insert(point(ri[p].r,ri[p].s));
59             while(nd[i].s&&st.size()) {
60                 it=st.lower_bound(point(nd[i].r,0));
61                 if(it==st.end()) {nd[i].s=1;break;}
62                 point tmp=*it;
63                 st.erase(it);
64                 if(tmp.c>nd[i].s) tmp.c-=nd[i].s,st.insert(tmp),nd[i].s=0;
65                 else nd[i].s-=tmp.c;
66             }
67             if(nd[i].s) {flag=1;break;}
68         }
69         if(flag) printf("No\n");
70         else printf("Yes\n");
71     }
72     return 0;
73 }
t2 Code


T3:密码

  数位dp,太麻烦,不想说,先咕着

分享图片
 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<cstdlib>
 6 #include<algorithm>
 7 #include<vector>
 8 #include<queue>
 9 #define ll long long
10 using namespace std;
11 const int MAXN=5000;
12 const ll D=1e9+7;
13 ll p,k,ans,f[MAXN][MAXN][2][2];
14 ll dig[MAXN],tot,s[MAXN],len;
15 char str[MAXN];
16 void change() {
17     len=strlen(str+1);
18     for(int i=1;i<=len;i++) s[len-i+1]=str[i]-0;
19     while(len) {
20         ll tmp=0;
21         for(int i=len;i>=1;i--) {
22             tmp=tmp*10+s[i];
23             s[i]=tmp/p;
24             tmp%=p;
25         }
26         dig[++tot]=tmp;
27         while(!s[len]&&len) --len;
28     }
29 }
30 void upt(ll &x,ll y) {
31     x=(x+y)%D;
32 }
33 int main() {
34     scanf("%s%lld%lld",str+1,&p,&k);
35     change();
36     f[tot+1][0][0][1]=1;
37     ll k1=p*(p+1)/2%D,k2=(p-1)*p/2%D;
38     for(int i=tot;i>=1;i--)
39         for(int j=tot+1;j>=0;j--) {
40             ll tk1=dig[i]*(dig[i]+1)/2%D,tk2=(dig[i]-1)*dig[i]/2%D;
41             ll tk3=(dig[i]*(dig[i]-1)/2+dig[i]*(p-dig[i]+1))%D;
42             ll tk4=((dig[i]+1)*dig[i]/2+(p-dig[i]-1)*dig[i])%D;
43             upt(f[i][j][0][0],f[i+1][j][0][0]*k1);
44             upt(f[i][j][1][0],f[i+1][j][0][0]*k2);
45             upt(f[i][j][0][0],f[i+1][j][0][1]*tk1);
46             upt(f[i][j][1][0],f[i+1][j][0][1]*tk2);
47             upt(f[i][j][1][1],f[i+1][j][0][1]*dig[i]);
48             upt(f[i][j][0][1],f[i+1][j][0][1]*(dig[i]+1));
49             if(j) {
50                 upt(f[i][j][1][0],f[i+1][j-1][1][0]*k1);
51                 upt(f[i][j][1][0],f[i+1][j-1][1][1]*tk3);
52                 upt(f[i][j][0][0],f[i+1][j-1][1][0]*k2);
53                 upt(f[i][j][0][0],f[i+1][j-1][1][1]*tk4);
54                 upt(f[i][j][1][1],f[i+1][j-1][1][1]*(p-dig[i]));
55                 upt(f[i][j][0][1],f[i+1][j-1][1][1]*(p-dig[i]-1));
56             }
57         }
58         //    for(int x=0;x<p;x++)
59             //    for(int y=0;y<p;y++) {
60                 //    if(x+y+1<p) {
61                 //        upt(f[i][j][1][0],f[i+1][j][0][0]);
62                 //        if(x+y<dig[i]) upt(f[i][j][0][0],f[i+1][j][0][1]);
63                 //        if(x+y+1<dig[i]) upt(f[i][j][1][0],f[i+1][j][0][1]);
64                 //    }
65                 //    if(x+y<p) upt(f[i][j][0][0],f[i+1][j][0][0]);
66                 //    if(j&&x+y+1>=p) {
67                 //        upt(f[i][j][1][0],f[i+1][j-1][1][0]);
68                 //        if(x+y+1-p<dig[i])
69                 //            upt(f[i][j][1][0],f[i+1][j-1][1][1]);
70                 //    }
71                 //    if(j&&x+y>=p) {
72                 //        upt(f[i][j][0][0],f[i+1][j-1][1][0]);
73                 //        if(x+y-p<dig[i])
74                 //            upt(f[i][j][0][0],f[i+1][j-1][1][1]);
75                 //    }
76                     
77                 //    if(x+y+1==dig[i]) upt(f[i][j][1][1],f[i+1][j][0][1]);
78                 //    if(x+y==dig[i]) upt(f[i][j][0][1],f[i+1][j][0][1]);
79                 //    if(j&&x+y+1-p==dig[i])    upt(f[i][j][1][1],f[i+1][j-1][1][1]);
80                 //    if(j&&x+y-p==dig[i]) upt(f[i][j][0][1],f[i+1][j-1][1][1]);
81             //    }
82     for(int i=k;i<=tot;i++) {
83         upt(ans,f[1][i][0][0]);
84         upt(ans,f[1][i][0][1]);
85     }
86     printf("%lld\n",ans%D);
87     return 0;
88 }
t3 Code

(注释掉的是80分的暴力)



 

时间:2019-09-11 22:47:23阅读(11)
联系我们 - 留言反馈
© 2017 版权所有 鲁ICP备17052893号