8.15 考试反思

T1

P2434 区间

求多个线段的的交。

由题意得，对于任意两条线段来说，关系有三种：

1. 一条在另一条内部，为重合。
2. 一条线段和另一条有接触的部分，称为相接。
3. 一条与另一条完全无接触部分，称为相间。

于是可得：

当我们发现两条线段重合时，舍去较短的一条

如果发现有相接的线段，我们就锁定相接的线段中较靠右的一条，寻找与之相接的线段，一直下循环去

如果发现没有与当前线段相接的线段，就输出目前找到的线段的前端和后端，因为这条线段已经到头了

那么此题也就出来了，排序+贪心。

AC code:

#include<bits/stdc++.h>
#define seq(q,w,e) for(int q=w;q<=e;q++)
using namespace std;
const int maxn=1e5+10;
struct node{
    int b,e;
}a[maxn];
vector<node> v;
bool cmp(node a,node b){
    if(a.b==b.b) return a.e<b.e;
    return a.b<b.b;
}
int n;
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i].b>>a[i].e;
    }
    sort(a,a+n,cmp);
    v.push_back(a[0]);
    for(int i=1;i<n;i++){
        if(v.back().b<=a[i].b&&v.back().e>=a[i].e)
			continue;
        v.push_back(a[i]);
    }
    int sz=v.size();
	int i=0,j=0;
	while(i<sz){
		j=i; 
		while(v[j].e>=v[j+1].b&&j<sz-1)
			++j;
        cout<<v[i].b<<" "<<v[j].e<<endl;
		i=j+1; 
	} 
    return 0;
}

T2

P2296 寻找道路

一眼 \(BFS\) ，由于边权为一。(由于没看限制，喜报20)

由于题目要求必须满足 \(task1\) 所以，应优先处理 \(task1\) ;

然后就是快乐的 \(BFS\) 。

预处理：需要先满足 \(task1\) 的要求，建反图，执行一个从终点开始 \(BFS\) ，就可以在这张有向图上处理出所有“可达终点”的结点了。

AC code:

#include<bits/stdc++.h>
#define seq(q,w,e) for(int q=w;q<=e;q++)
using namespace std;
const int maxn=1e4+10,maxm=2e5+10;
int n,m,st,ed;
int deg[maxn];
vector<int> tow_G[maxn],rev_G[maxn];
bool vis[maxn];
queue<int> q;
void BFS(){
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		int u,v; scanf("%d%d",&u,&v);
		tow_G[u].push_back(v); 
		rev_G[v].push_back(u);
	}
	cin>>st>>ed;
	q.push(ed);
	while(!q.empty()){
		int tmp=q.front(); q.pop();
		if(vis[tmp]) continue; vis[tmp]=true;
		for(int i=0;i<rev_G[tmp].size();++i){
			int j=rev_G[tmp][i];
			deg[j]++;
			q.push(j);
		}
	}
}
int dis[maxn];
void s_BFS(){
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f,sizeof(dis)); 
	dis[st]=0;
	q.push(st);
	while(!q.empty()){
		int tmp=q.front(); q.pop();
		if(vis[tmp]) continue; vis[tmp]=true;
		if(deg[tmp]!=tow_G[tmp].size()) continue;
		for(int i=0;i<tow_G[tmp].size();++i){
			int j=tow_G[tmp][i];
			if(dis[j]>dis[tmp]+1){
				dis[j]=dis[tmp]+1;
				q.push(j);	
			}
		}
	}
}
int main(){
    // ios::sync_with_stdio(false);cin.tie(0);
    BFS();
    s_BFS();
    cout<<(dis[ed]!=0x3f3f3f3f?dis[ed]:-1);
    return 0;
}

T3

看的不是很懂，引用一下题解(QAQ)。

用递推，推一下递推式子。

\(n\) 个物品中取 \(m\) 个物品，若不取这个物品，则从 \(n-1\) ，\(m\) 推过来，若取这个物品则从 \(n-1\) ，\(m-1\) 推过来。

所以 \(f[i][j]=f[i-1][j-1]+f[i-1][j]\) 。

AC code：

#include<bits/stdc++.h>
#define seq(q,w,e) for(int q=w;q<=e;q++)
#define ll long long
using namespace std;
const int maxn=2011;
ll f[maxn][maxn];
ll h[maxn],l[maxn]; 
ll ff[maxn][maxn];
ll n,m,k,t,i,j;
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>t>>k;
    f[0][0]=1;
    for (i=1;i<=2001;i++){   
        f[i][0]=1;
        for (j=1;j<=i;j++){
            f[i][j]=(f[i-1][j-1]+f[i-1][j])%k;
            if (f[i][j]==0){
                h[i]++;
            }
            ff[i][j]=ff[i-1][j]+h[i];
            if (j==i) ff[i][j]=h[i]+ff[i-1][j-1];
        }
    }
    while (t--){
        cin>>n>>m;
        if (m>n) m=n;
        cout<<ff[n][m]<<"\n";
    }
    return 0;
}