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(n2)的时间复杂度来进行区间修改和O(n)的复杂度来查询统计，数据弱时，对于60%的数据能水过。
# include <cstdio>
# include <iostream>
# include <algorithm>
# include <cmath>
# include <cstring>
using namespace std;
int main()
{
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
int l,m,le,ri,pd[],i,j,sum=;
scanf("%d%d",&l,&m);
for (i=;i<=l;i++)pd[i]=;
for (i=;i<=m;i++)
{
scanf("%d%d",&le,&ri);
for (j=le;j<=ri;j++)
pd[j]=;
}
for (i=;i<=l;i++)
if (pd[i]==)sum++;
printf("%d",sum);
return ;
}
2、线段树保90分（人品好100分）。思路就很简单了，区间修改，只不过代码量有点长。
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXX=;
int t[MAXX*+],lazy[MAXX*+]={};
int l,m;
void build(int node,int begin,int end)
{
if(begin==end)
{
t[node]=;
return;
}
else
{
int mid=(begin+end)>>;
build(node<<,begin,mid);
build(node<<|,mid+,end);
t[node]=t[node<<]+t[node<<|];
}
return;
}
void pushdown(int node,int left,int right)
{
int mid=(left+right)>>;
lazy[node<<]+=lazy[node];
lazy[node<<|]+=lazy[node];
t[node<<]-=lazy[node]*(mid-left+);
if(t[node<<]<) t[node<<]=;
t[node<<|]-=lazy[node]*(right-mid);
if(t[node<<|]<) t[node<<|]=;
lazy[node]=;
return;
}
void update(int node,int left,int right,int l,int r)
{
if(l<=left&&right<=r)
{
lazy[node]+=;
t[node]-=(right-left+);
if(t[node]<) t[node]=;
return;
}
if(l>right||r<left) return;
int mid=(left+right)>>;
if(lazy[node]) pushdown(node,left,right);
if(l<=mid) update(node<<,left,mid,l,r);
if(mid<r) update(node<<|,mid+,right,l,r);
t[node]=t[node<<]+t[node<<|];
return;
}
int read()
{
int ans=,f=;
char i=getchar();
while(i>=''&&i<='')
{
ans=(ans<<)+(ans<<)+i-'';
i=getchar();
}
return ans*f;
}
int main()
{
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
int x,y;
l=read(),m=read();
build(,,l);
for(int i=;i<=m;i++)
{
x=read(),y=read();
update(,,l,x,y);
}
printf("%d",t[]);
return ;
}
3、对区间进行排序(建议桶排，快排可能卡)100分，之后就合并区间，最后统计。
#include<cstdio>
#include<algorithm>
using namespace std;
char buf[], *p1=buf, *p2=buf;
#define SWAP(a, b) ((a)^=(b),(b)^=(a),(a)^=(b))
#define get_char() (p1==p2&&(p2=(p1=buf)+fread(buf,1,10000000,stdin),p1==p2)?EOF:*p1++)
#define gi(a) do { \
register char ch; \
while((ch = get_char()) > '' || ch < ''); \
for(a = ch-''; (ch = get_char()) >= '' && ch <= ''; a = a*+ch-''); \
} while()
struct cut {
int s, e;
} data[];
inline bool comp(const cut &a, const cut &b) {
return a.s<b.s;
}
int main() {
freopen("tree.in", "r", stdin);
freopen("tree.out", "w", stdout);
int N, M, i, s = -, e = -;
gi(N); gi(M);
for(i = ; i <= M; i++) {
gi(data[i].s); gi(data[i].e);
if(data[i].s > data[i].e) SWAP(data[i].s, data[i].e);
}
sort(data+, data++M, comp);
data[M+].s = ;
for(i = ; i <= M; i++) {
if(data[i+].s+ > e) N -= (e-s+), s = data[i+].s, e = data[i+].e;
else if(data[i+].e > e) e = data[i+].e;
}
printf("%d\n", N+);
return ;
}
4、正解：差分100分。（不要问我差分是什么，不懂去度娘问。）取树相当于每次修改区间【i,j】只需更改第i点-1和第j+1点+1，对于重复更改当然也行，反正小于0就没有树。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int n,m,sum,now,dis[];
inline int getint()
{
int a=;char x=getchar();bool f=;
while((x>''||x<'')&&x!='-')x=getchar();
if(x=='-')f=,x=getchar();
while(x>=''&&x<='')a=a*+x-'',x=getchar();
return f?-a:a;
}
int main()
{
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
n=getint();m=getint();
while(m--)
{
int a=getint(),b=getint();
dis[a]=max(dis[a],b-a+);
}
sum=n+;
for(int i=;i<=n+;i++)
{
now=max(now,dis[i]);
if(now)sum--,now--;
}
printf("%d",sum);
return ;
}
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
4
27
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*di3)。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
long long c[],k,s,p,sum,t;
inline int getint()
{
int a=;char x=getchar();bool f=;
while((x<''||x>'')&&x!='-')x=getchar();
if(x=='-')f=,x=getchar();
while(x>=''&&x<='')a=a*+x-'',x=getchar();
return f?-a:a;
}
int main()
{
freopen("happy.in","r",stdin);
freopen("happy.out","w",stdout);
for(int i=;i<;i++)c[i]=getint();k=getint();
while(k--)
{
sum=;int x=getint(),y=getint(),z=getint(),l=getint();s=getint();
for(int i=;i<=x;i++)
{
for(int j=;j<=y;j++)
{ for(int q=;q<=z;q++)
{
t+=(c[]*i+c[]*j+c[]*q);
if(t<=s&&((s-t)%c[]==&&(s-t)/c[]<=l))sum++;
t=;
}
}
}
printf("%lld\n",sum);
}
return ;
}
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)。
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
ll ans,f[];
int T;
int c[],d[];
inline int read()
{
int x=;char ch=getchar();
while(ch<''||ch>'')ch=getchar();
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x;
}
void dfs(int x,int k,int sum)
{
if(sum<)return;
if(x==)
{
if(k&)ans-=f[sum];
else ans+=f[sum];
return;
}
dfs(x+,k+,sum-(d[x]+)*c[x]);
dfs(x+,k,sum);
}
int main()
{
freopen("happy.in","r",stdin);
freopen("happy.out","w",stdout);
for(int i=;i<=;i++)c[i]=read();
T=read();
f[]=;
for(int i=;i<=;i++)
for(int j=c[i];j<=;j++)
f[j]+=f[j-c[i]];
for(int i=;i<=T;i++)
{
for(int k=;k<=;k++)d[k]=read();
int x=read();
ans=;
dfs(,,x);
printf("%lld\n",ans);
}
fclose(stdin);fclose(stdout);
return ;
}
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)
1
Hint
对于10%的数据 n<=20,m<=50
对于40%的数据 n<=5000,m<=50000
对于100%的数据 n<=100000,m<=500000
Solution：
1、暴力40分。直接搜索，暴力每一个点。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
int h[],m,sum=,sums=,v[],n,sumd;
struct edge{
int to;
int next;
}road[];
inline int getint()
{
int a=;char x=getchar();bool f=;
while((x<''||x>'')&&x!='-')x=getchar();
if(x=='-')f=,x=getchar();
while(x>=''&&x<='')a=a*+x-'',x=getchar();
return f?-a:a;
}
void add(int x1,int y1)
{
road[sum].to=x1;
road[sum].next=h[y1];
h[y1]=sum++;
}
void dfs(int i)
{
v[i]=;
sumd++;
int j;
for(j=h[i];j!=;j=road[j].next)
{
if(v[road[j].to]==)
dfs(road[j].to);
}
}
int main()
{
freopen("tui.in","r",stdin);
freopen("tui.out","w",stdout);
int i,x,y,j,f;
scanf("%d%d",&n,&m);
for(i=;i<=m;i++)
{x=getint();y=getint();
add(x,y);
}
for(i=;i<=n;i++)
{
f=;
memset(v,,sizeof(v));
sumd=;
dfs(i);
if(sumd==n)
sums++;
}
printf("%d",sums);
return ;
}
2、正解：tarjan缩点 不懂度娘 原题：洛谷p2341受欢迎的牛
先将原图反向连边，则只要求能到所有点的点的个数。。tarjan缩点，缩点后显然所有答案都在一个强连通分量中。。
重新构图，找一个没有入度的强连通分量，若它能到达其他的所有强连通分量，则为答案。。证明略。。想一下就清楚了。。
#include<cstdio>
#include<iostream>
#include<cstring>
#define N 100010
#define M 500010
using namespace std;
int n,m,a,b,cnt,ind,top,tot,rt,list[N],list2[N],low[N];
int dfn[N],st[N],fa[N],sum[N],d[N];
int toit[M],nex[M],toit2[M],next2[M];
bool fl,vis[N],inst[N];
int read()
{
int x=;char ch=getchar();
while(ch<''||ch>'')ch=getchar();
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x;
}
void add(int u,int v)
{
toit[++tot]=v;nex[tot]=list[u];list[u]=tot;
}
void add2(int u,int v)
{
toit2[++tot]=v;next2[tot]=list2[u];list2[u]=tot;
}
void tarjan(int x)
{
ind++;low[x]=ind;dfn[x]=ind;
top++;st[top]=x;inst[x]=;
vis[x]=;
for(int t=list[x];t;t=nex[t])
if(!vis[toit[t]])
{
tarjan(toit[t]);
low[x]=min(low[x],low[toit[t]]);
}
else
if(inst[toit[t]])low[x]=min(low[x],dfn[toit[t]]);
if(dfn[x]==low[x])
{
cnt++;
while(st[top+]!=x)
{
inst[st[top]]=;
sum[cnt]++;fa[st[top]]=cnt;
top--;
}
}
}
void dfs(int x)
{
vis[x]=;
for(int t=list2[x];t;t=next2[t])
if(!vis[toit2[t]])dfs(toit2[t]);
}
int main()
{
freopen("tui.in","r",stdin);
freopen("tui.out","w",stdout);
n=read();m=read();
for(int i=;i<=m;i++)
a=read(),b=read(),add(b,a);
for(int i=;i<=n;i++)
if(!vis[i])tarjan(i);
tot=;
for(int i=;i<=n;i++)
for(int t=list[i];t;t=nex[t])
if(fa[i]!=fa[toit[t]])
{
add2(fa[i],fa[toit[t]]);
d[fa[toit[t]]]++;
}
memset(vis,,sizeof(vis));
for(int i=;i<=cnt;i++)
if(d[i]==){dfs(i);rt=i;break;}
fl=;
for(int i=;i<=cnt;i++)
if(!vis[i]){fl=;break;}
if(fl)printf("%d",sum[rt]);
else printf("");
return ;
}