9月24日noip模拟赛解题报告

1.校门外的树(tree.c/cpp/pas 128M,1s)

Description

LSGJ扩建了，于是校门外有了一条长为L的路。路上种了一排的树，每相邻两棵树之间的距离为1，我们可以把马路看成一个数轴，马路的一端在数轴0的位置另一端在数轴L的位置，数轴上的每个整数点都有一棵树。

众所周知，zd是个非常喜欢研究生活中的各种问题的人，zd看到这个现象非常的欣喜，于是他立马就有了一个想法，假如现在要把m个区间内的树全都移走，他想知道最后还剩下多少棵树，由于他刚想出这个问题就被twt拿去一起颓了，临走之前他把这个问题交给了你，你能帮他解决这个问题吗？

Input(tree.in)

第一行有两个整数L，m，分别表示路的长度，要移走的区间的个数

接下来m行，每行两个整数l，r，表示区间的端点。

Output(tree.out)

一个整数，表示剩余树的数量。

Sample Input

500 3

150 300

100 200

470 471

Sample Output

298

Hint

对于10%的数据，区间之间互不重叠

对于30%的数据，L<=10000,m<=100

对于60%的数据，L，m<=100000

对于100%的数据，L，m<=1000000

Solution：

1、暴力60分。我们观察数据，很明显可以用O(n²)的时间复杂度来进行区间修改和O(n)的复杂度来查询统计，数据弱时，对于60%的数据能水过。

 1 # include <cstdio>
 2 # include <iostream>
 3 # include <algorithm>
 4 # include <cmath>
 5 # include <cstring>
 6 using namespace std;
 7 int main()
 8 {
 9     freopen("tree.in","r",stdin);
10     freopen("tree.out","w",stdout);
11     int l,m,le,ri,pd[1000005],i,j,sum=0;
12     scanf("%d%d",&l,&m);
13     for (i=0;i<=l;i++)pd[i]=1;
14     for (i=1;i<=m;i++)
15     {
16     scanf("%d%d",&le,&ri);
17     for (j=le;j<=ri;j++)
18     pd[j]=0;    
19     }
20     for (i=0;i<=l;i++)
21     if (pd[i]==1)sum++;
22     printf("%d",sum);
23     return 0;
24 }

2、线段树保90分（人品好100分）。思路就很简单了，区间修改，只不过代码量有点长。

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 const int MAXX=1000000;
 5 int t[MAXX*4+10],lazy[MAXX*4+10]={0};
 6 int l,m;
 7 void build(int node,int begin,int end)
 8 {
 9     if(begin==end)
10     {
11         t[node]=1;
12         return;
13     }
14     else
15     {
16         int mid=(begin+end)>>1;
17         build(node<<1,begin,mid);
18         build(node<<1|1,mid+1,end);
19         t[node]=t[node<<1]+t[node<<1|1];
20     }
21     return;
22 }
23 void pushdown(int node,int left,int right)
24 {
25     int mid=(left+right)>>1;
26     lazy[node<<1]+=lazy[node];
27     lazy[node<<1|1]+=lazy[node];
28     t[node<<1]-=lazy[node]*(mid-left+1);
29     if(t[node<<1]<0) t[node<<1]=0;
30     t[node<<1|1]-=lazy[node]*(right-mid);
31     if(t[node<<1|1]<0) t[node<<1|1]=0;
32     lazy[node]=0;
33     return;
34 }
35 void update(int node,int left,int right,int l,int r)
36 {
37     if(l<=left&&right<=r)
38     {
39         lazy[node]+=1;
40         t[node]-=(right-left+1);
41         if(t[node]<0) t[node]=0;
42         return;
43     }
44     if(l>right||r<left) return;
45     int mid=(left+right)>>1;
46     if(lazy[node]) pushdown(node,left,right);
47     if(l<=mid) update(node<<1,left,mid,l,r);
48     if(mid<r) update(node<<1|1,mid+1,right,l,r);
49     t[node]=t[node<<1]+t[node<<1|1];
50     return;
51 }
52 int read()
53 {
54     int ans=0,f=1;
55     char i=getchar();
56     while(i>='0'&&i<='9')
57     {
58         ans=(ans<<3)+(ans<<1)+i-'0';
59         i=getchar();
60     }
61     return ans*f;
62 }
63 int main()
64 {
65     freopen("tree.in","r",stdin);
66     freopen("tree.out","w",stdout);
67     int x,y;
68     l=read(),m=read();
69     build(1,0,l);
70     for(int i=1;i<=m;i++)
71     {
72         x=read(),y=read();
73         update(1,0,l,x,y);
74     }
75     printf("%d",t[1]);
76     return 0;
77 }

3、对区间进行排序(建议桶排，快排可能卡)100分，之后就合并区间，最后统计。

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std; 
 4 char buf[10000010], *p1=buf, *p2=buf;
 5 #define SWAP(a, b) ((a)^=(b),(b)^=(a),(a)^=(b))
 6 #define get_char() (p1==p2&&(p2=(p1=buf)+fread(buf,1,10000000,stdin),p1==p2)?EOF:*p1++)
 7 #define gi(a) do { 
 8   register char ch; 
 9   while((ch = get_char()) > '9' || ch < '0');                
10   for(a = ch-'0'; (ch = get_char()) >= '0' && ch <= '9'; a = a*10+ch-'0'); 
11   } while(0)
12 struct cut {
13   int s, e;
14 } data[1000100];
15 inline bool comp(const cut &a, const cut &b) {
16   return a.s<b.s;
17 }
18 int main() {
19   freopen("tree.in", "r", stdin);
20   freopen("tree.out", "w", stdout); 
21   int N, M, i, s = -1, e = -2;
22   gi(N); gi(M);
23   for(i = 1; i <= M; i++) {
24     gi(data[i].s); gi(data[i].e);
25     if(data[i].s > data[i].e) SWAP(data[i].s, data[i].e);
26   }
27   sort(data+1, data+1+M, comp);
28   data[M+1].s = 987654321;
29   for(i = 0; i <= M; i++) {
30     if(data[i+1].s+1 > e) N -= (e-s+1), s = data[i+1].s, e = data[i+1].e; 
31     else if(data[i+1].e > e) e = data[i+1].e;
32   }
33   printf("%d
", N+1);
34   return 0;
35 }

4、正解：差分100分。（不要问我差分是什么，不懂去度娘问。）取树相当于每次修改区间【i,j】只需更改第i点-1和第j+1点+1，对于重复更改当然也行，反正小于0就没有树。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<cstring>
 7 using namespace std;
 8 int n,m,sum,now,dis[1000005];
 9 inline int getint()
10 {    
11     int a=0;char x=getchar();bool f=0;
12     while((x>'9'||x<'0')&&x!='-')x=getchar();
13     if(x=='-')f=1,x=getchar();
14     while(x>='0'&&x<='9')a=a*10+x-'0',x=getchar();
15     return f?-a:a;
16 }
17 int main()
18 {
19     freopen("tree.in","r",stdin);
20     freopen("tree.out","w",stdout);
21     n=getint();m=getint();
22     while(m--)
23     {
24         int a=getint(),b=getint();
25         dis[a]=max(dis[a],b-a+1);
26     }
27     sum=n+1;
28     for(int i=0;i<=n+1;i++)
29     {
30         now=max(now,dis[i]);
31         if(now)sum--,now--;
32     }
33     printf("%d",sum);
34     return 0;
35 }

2.开心的zpl(happy.c/cpp/pas 128M,1s)

Description

zpl今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间，更让他开心的是，他从twt那里得到了一些硬币，twt给的硬币很奇怪，它们一共有四面值分别为c1,c2,c3,c4,由于zpl要买的东西太多，因此他一共去了k次，他每次只带di枚面值为ci的硬币要买价值为si的物品，而且他不想要商店找钱，你能告诉他每次有多少种付款方法吗？

Input

第一行为5个整数，分别为c1,c2,c3,c4,k

下面k行，d1,d2,d3,d4,s表示每种硬币的数量和商品的总价格。

Output

k行，表示每次的方案数

Sample Input

1 2 5 10 2

3 2 3 1 10

1000 2 2 2 900

Sample Output

Hint

对于30%的数据，k<=5.di<=5

对于60%的数据，k<=10,di<=50,s<=1000

对于100%的数据，k<=1000, s<=100000,di<=100000

Solution:

1、暴力60分。观察数据，对于每次询问，枚举能构成的面额，符合就记录，然后输出，时间复杂度O(k*di³)。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cmath>
 5 #include<cstring>
 6 using namespace std;
 7 long long c[5],k,s,p,sum,t;
 8 inline int getint()
 9 {
10     int a=0;char x=getchar();bool f=0;
11     while((x<'0'||x>'9')&&x!='-')x=getchar();
12     if(x=='-')f=1,x=getchar();
13     while(x>='0'&&x<='9')a=a*10+x-'0',x=getchar();
14     return f?-a:a;
15 }
16 int main()
17 {
18     freopen("happy.in","r",stdin);
19     freopen("happy.out","w",stdout);
20     for(int i=0;i<4;i++)c[i]=getint();k=getint();
21     while(k--)
22     {
23         sum=0;int x=getint(),y=getint(),z=getint(),l=getint();s=getint();
24         for(int i=0;i<=x;i++)
25         {
26             for(int j=0;j<=y;j++)
27             {
28         
29                 for(int q=0;q<=z;q++)
30                 {
31                     t+=(c[0]*i+c[1]*j+c[2]*q);
32                     if(t<=s&&((s-t)%c[3]==0&&(s-t)/c[3]<=l))sum++;
33                     t=0;
34                 }
35             }
36         }
37         printf("%lld
",sum);
38     }
39     return 0;
40 }

2、正解:dp预处理+容斥原理(100分)。原题是洛谷：p1450硬币购物

显然直接用多重背包做会超时，先不考虑每种硬币数量的限制，设f[i]为不考虑每种硬币数量的限制时，面值为i的方案数，则状态转移方程就呼之欲出了:f[i]=sum{f[i-c[k]]}(i-c[k]>=0&&1<=k<=4)

为避免方案重复，要以k为阶段递推，边界条件为f[0]=1，这样预处理的时间复杂度就是O(s)。

接下来对于每次询问，根据容斥原理，答案即为得到面值为S的不超过限制的方案数=得到面值S的无限制的方案数即f[s]

– 第1种硬币超过限制的方案数 – 第2种硬币超过限制的方案数 – 第3种硬币超过限制的方案数 – 第4种硬币超过限制的方案数

+ 第1,2种硬币同时超过限制的方案数 + 第1,3种硬币同时超过限制的方案数 + …… + 第1,2,3,4种硬币全部同时超过限制的方案数。

用dfs实现，当选择的个数是奇数时用减号否则用加号。

当第1种硬币超过限制时，只要要用到D[1]+1枚硬币，剩余的硬币可以任意分配，所以方案数为 F[ S – (D[1]+1)*C[1] ]，

当且仅当(S – (D[1]+1)*C[1])>=0，否则方案数为0。其余情况类似，每次询问只用问16次，所以询问的时间复杂度为O(1)。

 1 #include<iostream>
 2 #include<cstdio>
 3 #define ll long long
 4 using namespace std;
 5 ll ans,f[100005];
 6 int T;
 7 int c[5],d[5];
 8 inline int read()
 9 {
10     int x=0;char ch=getchar();
11     while(ch<'0'||ch>'9')ch=getchar();
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x;
14 }
15 void dfs(int x,int k,int sum)
16 {
17     if(sum<0)return;
18     if(x==5)
19     {
20         if(k&1)ans-=f[sum];
21         else ans+=f[sum];
22         return;
23     }
24     dfs(x+1,k+1,sum-(d[x]+1)*c[x]);
25     dfs(x+1,k,sum);
26 }
27 int main()
28 {
29      freopen("happy.in","r",stdin);
30      freopen("happy.out","w",stdout);
31     for(int i=1;i<=4;i++)c[i]=read();
32     T=read();
33     f[0]=1;
34     for(int i=1;i<=4;i++)
35         for(int j=c[i];j<=100000;j++)
36             f[j]+=f[j-c[i]];
37     for(int i=1;i<=T;i++)
38     {
39         for(int k=1;k<=4;k++)d[k]=read();
40         int x=read();
41         ans=0;
42         dfs(1,0,x);
43         printf("%lld
",ans);
44     }
45     fclose(stdin);fclose(stdout);
46     return 0;
47 }

3.谁是最颓的？(tui.c/cpp/pas 128M,1s)

Description

qyp是一个非常会颓的人，在qyp的班级中，有n个同学，许多同学都有有别的同学比自己颓的想法，现在有m个想法，用如(p,q)这样的整数对表示p认为q比自己颓，显然这种关系是具有传递性的，即如果p认为q比自己颓，q认为r比自己颓，那么显然p也就认为r比自己颓了。

现在qyp拿到了这m个想法，他想知道有多少同学是班上其他所有同学都认为是比自己颓的，但是由于有太多的同学都仰慕qyp来到qyp的班上，导致他们班的人太多，qyp已经算不清了，于是他希望你能写一个程序来帮助他完成这个任务。

Input(tui.in)

第一行两个数n,m。

接下来m行，每行两个数p,q，意思是p认为q比自己颓（给出的信息有可能重复，即有可能出现多个p,q）

Output(tui.out)

一个数，即有多少个同学被其他所有的同学认为是受欢迎的。

Sample Input(tui.in)

3 3

1 2

2 1

2 3

Sample Output(tui.out)

Hint

对于10%的数据 n<=20,m<=50

对于40%的数据 n<=5000,m<=50000

对于100%的数据 n<=100000,m<=500000

Solution：

1、暴力40分。直接搜索，暴力每一个点。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cstdlib>
 6 using namespace std;
 7 int h[100001],m,sum=1,sums=0,v[100001],n,sumd;
 8 struct edge{
 9 int to;
10 int next;
11 }road[100001];
12 inline int getint()
13 {
14     int a=0;char x=getchar();bool f=0;
15     while((x<'0'||x>'9')&&x!='-')x=getchar();
16     if(x=='-')f=1,x=getchar();
17     while(x>='0'&&x<='9')a=a*10+x-'0',x=getchar();
18     return f?-a:a;
19 }
20 void add(int x1,int y1)
21 {
22     road[sum].to=x1;
23     road[sum].next=h[y1];
24     h[y1]=sum++;
25 }
26 void dfs(int i)
27 {    
28     v[i]=1;    
29     sumd++;
30     int j;
31     for(j=h[i];j!=0;j=road[j].next)
32     {    
33     if(v[road[j].to]==0)
34     dfs(road[j].to);    
35     }
36 }
37 int main()
38 {
39     freopen("tui.in","r",stdin);
40     freopen("tui.out","w",stdout);
41     int i,x,y,j,f;    
42     scanf("%d%d",&n,&m);
43     for(i=1;i<=m;i++)
44     {x=getint();y=getint();
45     add(x,y);
46     }
47     for(i=1;i<=n;i++)
48     {
49     f=1;
50     memset(v,0,sizeof(v));    
51     sumd=0;
52     dfs(i);
53     if(sumd==n)
54     sums++;
55     }
56     printf("%d",sums);
57     return 0;
58 }

2、正解：tarjan缩点不懂度娘原题：洛谷p2341受欢迎的牛

先将原图反向连边，则只要求能到所有点的点的个数。。tarjan缩点，缩点后显然所有答案都在一个强连通分量中。。

重新构图，找一个没有入度的强连通分量，若它能到达其他的所有强连通分量，则为答案。。证明略。。想一下就清楚了。。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #define N 100010
 5 #define M 500010
 6 using namespace std;
 7 int n,m,a,b,cnt,ind,top,tot,rt,list[N],list2[N],low[N];
 8 int dfn[N],st[N],fa[N],sum[N],d[N];
 9 int toit[M],nex[M],toit2[M],next2[M];
10 bool fl,vis[N],inst[N];
11 int read()
12 {
13      int x=0;char ch=getchar();
14      while(ch<'0'||ch>'9')ch=getchar();
15      while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
16      return x;
17 }
18 void add(int u,int v)
19 {
20      toit[++tot]=v;nex[tot]=list[u];list[u]=tot; 
21 }
22 void add2(int u,int v)
23 {
24      toit2[++tot]=v;next2[tot]=list2[u];list2[u]=tot; 
25 }
26 void tarjan(int x)
27 {
28      ind++;low[x]=ind;dfn[x]=ind;
29     top++;st[top]=x;inst[x]=1;
30     vis[x]=1;
31     for(int t=list[x];t;t=nex[t])
32         if(!vis[toit[t]])
33         {
34              tarjan(toit[t]);
35             low[x]=min(low[x],low[toit[t]]);              
36         }                      
37         else
38             if(inst[toit[t]])low[x]=min(low[x],dfn[toit[t]]);
39     if(dfn[x]==low[x])
40     {
41          cnt++;    
42         while(st[top+1]!=x)
43         {
44              inst[st[top]]=0;
45             sum[cnt]++;fa[st[top]]=cnt;
46             top--;                
47           }           
48      }        
49 }
50 void dfs(int x)
51 {
52      vis[x]=1;
53     for(int t=list2[x];t;t=next2[t])
54         if(!vis[toit2[t]])dfs(toit2[t]);          
55 }
56 int main()
57 {
58      freopen("tui.in","r",stdin);
59      freopen("tui.out","w",stdout);
60      n=read();m=read();
61      for(int i=1;i<=m;i++)
62          a=read(),b=read(),add(b,a);
63     for(int i=1;i<=n;i++)
64         if(!vis[i])tarjan(i);    
65     tot=0;
66     for(int i=1;i<=n;i++)
67          for(int t=list[i];t;t=nex[t])
68              if(fa[i]!=fa[toit[t]])
69             {
70                  add2(fa[i],fa[toit[t]]);
71                 d[fa[toit[t]]]++;                   
72             }
73     memset(vis,0,sizeof(vis));
74     for(int i=1;i<=cnt;i++)
75         if(d[i]==0){dfs(i);rt=i;break;}
76     fl=1;    
77     for(int i=1;i<=cnt;i++)
78         if(!vis[i]){fl=0;break;}
79     if(fl)printf("%d",sum[rt]);
80     else printf("0");                                                    
81      return 0;
82 }

PS：～蒟蒻写博客不易，转载请注明出处，万分感谢！～