NOIp 2015 day2 解题报告

T1 跳石头

二分即可


#include<bits/stdc++.h>
using namespace std;
int n,m,d,l,r,mid,ans,a[100000];
bool judge(int x){
	int tot=0,i=0,now=0;
	while (i<n+1) {
		i++;
		if(a[i]-a[now]<x) tot++;
		else now=i;
		
	}
	 return tot<=m;
}
int main(){
 	freopen("stone.in","r",stdin);
 	freopen("stone.out","w",stdout);	
	cin>>d>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	a[n+1]=d,l=1,r=d;
	while(l<=r){
		mid=(l+r)/2;
		if (judge(mid)){
			ans=mid;
			l=mid+1;
		}
		else r=mid-1;
	}
	cout<<ans;
	return 0;
}

T2 子串

DP。我觉得和背包的思路挺像的一道题。用f1[i][j][k]表示两串分别到a[i],b[j],且a[i]必须使用时,用了k个子串的方案数。f2[i][j][k]表示无论用不用当前字符(A[i])时的方案数总和。那么转移方程就显而易见了:

f1[i][j][k]=f1[i-1][j-1][k-1]+f2[i-1][j-1][k]

f2[i][j][k]=f2[i][j][k]+f[i][j][k]

我们发现i这个维度是可以滚动的,于是就节省了一维空间


#include<bits/stdc++.h>
using namespace std;
int mod=1000000007;
char a[1001],b[201];
int n,m,k1,y,ans,f1[1001][200],f2[201][201];
int main(){
	//freopen("substring.in","r",stdin);
 	//freopen("substring.out","w",stdout);
	cin>>n>>m>>k1;
	cin>>a>>b;
	f1[0][0]=f2[0][0]=1;
    for (int i=1; i<=n; i++)
        for (int j=m; j>=1; j--)
            for (int k=1; k<=k1; k++)
            {
                if (a[i-1]!=b[j-1]) {f1[j][k]=0; continue;}
                f1[j][k]=(f1[j-1][k]%mod+f2[j-1][k-1]%mod)%mod;
                f2[j][k]=(f2[j][k]%mod+f1[j][k]%mod)%mod;
            }
    printf("%d",f2[m][k1]);
	return 0;
}

T3 运输计划

先Tarjan求m对点的lca,然后二分答案,把所有大于二分的答案的路径记录,判断有没有一条边被所有大于二分的答案的路径所重复,如果有,那么这条边必须大于等于最大的路径减二分的答案,如果上述两个条件都符合那么这个二分的答案就是合法的,细节参考代码。如果TLE加个快读即可。


#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;
typedef pair<int,int>PP;
struct node{
    int to,dist,nu;
};
struct P{
    int a,b,c;
};
int q[300002],n,m,hh[300002],ans[300002],anss[300002],lca[300002],h[300002],fa[300002],left,right,mid,f[300002];
P y[300002];
bool fl[300002];
vector<node>s[300002];
vector<PP>t[300002];
int find(int x){
    if (fa[x]==x)return x;
    else return fa[x]=find(fa[x]);
}
void dfs(int x,int tt){
    anss[x]=tt;fa[x]=x;
    for (int i=0;i<s[x].size();i++)
    if (!fa[s[x][i].to])
    {
        h[s[x][i].to]=s[x][i].nu;
        dfs(s[x][i].to,tt+s[x][i].dist);
        fa[s[x][i].to]=find(x);
    }
    for (int i=0;i<t[x].size();i++)
    if (fa[t[x][i].first])lca[t[x][i].second]=find(t[x][i].first);
}
void dfs(int x){//c++支持重载函数
    for (int i=0;i<s[x].size();i++)
    if (!fl[s[x][i].to])
    {
        fl[s[x][i].to]=1;
        dfs(s[x][i].to);
        f[h[x]]+=f[h[s[x][i].to]];
    }
}
bool pd(int x){
    int t=0,u,maxn=0;
    memset(f,0,sizeof(f));
    memset(fl,0,sizeof(fl));
    for (int i=0;i<m;i++)
    if (ans[i]>x){maxn=max(ans[i],maxn);q[t++]=i;}
    if (!t)return true;
    for (int i=0;i<t;i++)
    {
        u=q[i];
        f[h[y[u].a]]++;//这条边+1
        f[h[y[u].b]]++;//这条边+1
        f[h[lca[u]]]-=2;//这条边-2,因为这条边虽然计算了两次,实际上一次都没有走到
    }
    dfs(1);
    for (int i=1;i<n;i++)
    if (f[i]==t && hh[i]>=maxn-x)return true;
    return false;
}
int main()
{
    scanf("%d%d",&n,&m);
    int u,v,w,sum=0;
    for (int i=1;i<n;i++)
    {
        scanf("%d%d%d",&u,&v,&w);sum+=w;
        hh[i]=w;node g;
        g.to=v;g.dist=w;g.nu=i;
        s[u].push_back(g);
        g.to=u;
        s[v].push_back(g);
    }
    for (int i=0;i<m;i++)
    {
        scanf("%d%d",&y[i].a,&y[i].b);
        t[y[i].a].push_back(PP(y[i].b,i));
        t[y[i].b].push_back(PP(y[i].a,i));
    }
    dfs(1,0);
    for (int i=0;i<m;i++)
    ans[i]=anss[y[i].a]+anss[y[i].b]-2*anss[lca[i]];//a到b的距离等于1到a的距离+1到b的距离-1到lca(a,b)的距离
    left=0;right=sum;
    while(left<right)//二分答案
    {
        mid=(left+right)/2;
        if (pd(mid))right=mid;
        else left=mid+1;
    }
    printf("%d",right);
    return 0;
}

以上

发表评论

电子邮件地址不会被公开。 必填项已用*标注