Codeforces div2 c~e

题意:给定n个节点的有根树，根是1号节点。你可以选择k个节点将其设置为工业城市，其余设置为旅游城市。对于一个工业城市，定义它的幸福值为工业城市到根的路径经过的旅游城市的数量。你需要求出所有工业城市的幸福值之和的最大可能值。注意工业城市到工业城市不计幸福值..那么怎么计算幸福?肯定我选这个的时候后面的点我都选了..
图片说明
看看这幅图,假如是5个点要染色,那么,3,4中任选一个,因为工业城市到工业城市不计算,那么,我现在增加一个3,那么我就会失去,子树中所有点到3这个幸福值,同时我们也增加了3到1的幸福值.
所以得到结论,深度-子树大小+1.取前k个最大的就好了.

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pb push_back
typedef long long ll;
const ll inf=132913423200339;
const ll mod=998244353676776;
const int N=2e5+5;
const ll M=1e9;
const double eps=1e-7;
using namespace std;
ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b) { return a*b/gcd(a,b);    }
ll qp(ll a,ll b, ll p){ll ans = 1;while(b){if(b&1){ans = (ans*a)%p;--b;}a = (a*a)%p;b >>= 1;}return ans%p;}
ll Inv(ll x)          { return qp(x,mod-2,mod);}
ll C(ll n,ll m){if (m>n) return 0;ll ans = 1;for (int i = 1; i <= m; ++i) ans=ans*Inv(i)%mod*(n-i+1)%mod;return ans%mod;}
ll A(ll n,ll m,ll mod){ll sum=1; for(int i=n;i>=n-m+1;i--) sum=(sum*i)%mod; return sum%mod;}
ll lowbit(ll x) {return x&(-x);}
ll c[N],sum1[N],sum2[N],b[N],lsh[N],n,m,k,fa[13],a[N];
void add1(ll i,ll k){ while(i<=n) {c[i]+=k;i+=lowbit(i);}}//预处理ai单点修改 区间查询***预处理a[i]-a[i-1]区间修改单点查询
ll  Sum1(ll i) {ll res=0; while(i>0) res+=c[i],i-=lowbit(i);return res;}//预处理ai单点修改 区间查询***预处理a[i]-a[i-1]区间修改单点查询
void add2(ll i,ll k){ ll x=i;while(i<=n) {sum1[i]+=k;sum2[i]+=k*(x-1);i+=lowbit(i);}}//区间修改,区间查询
ll  Sum2(ll i) {ll res=0,x=i;while(i>0){ res+= x * sum1[i]-sum2[i]; i -= lowbit(i);}return res;}//区间修改,区间查询
void ls(){ll cnt; for(ll i=1;i<=n;i++) lsh[i]=a[i]; sort(lsh+1,lsh+n+1);cnt = unique(lsh+1,lsh+n+1)-lsh-1; for(int i=1;i<=n;i++)a[i]=lower_bound(lsh+1,lsh+cnt+1,a[i])-lsh;}
ll lca(ll x) { if(x==fa[x]) return x;else return fa[x]=lca(fa[x]); }//找祖先.
ll sum[N];//记录子树大小.
vector<ll>v[N];
vector<ll>cnt;//记录深度-子树大小+1也就是答案
int dfs(int x,int fa,int dep)//return 子树大小
{
    sum[x]++;
    if(v[x].size()==1&&x!=1) {cnt.pb(dep-sum[x]+1); return 1;}
    for(int i=0;i<v[x].size();i++)
    {
        int son=v[x][i];//儿子.
        if(son==fa) continue;//父节点不可能=子节点
        sum[x]+=dfs(son,x,dep+1);
    }
    cnt.pb(dep-sum[x]+1);
    return sum[x];
}

int main()
{
    ll ans=0;
    ios;
    ll n,k;
    cin>>n>>k;
    for(int i=1;i<=n-1;i++)
    {
        int x,y;
        cin>>x>>y;
        v[x].pb(y);
        v[y].pb(x);
    }
    dfs(1,0,0);//自己 爸爸 深度
    sort(cnt.begin(),cnt.end());
    for(ll i=cnt.size()-1;i>=cnt.size()-k;i--) ans+=cnt[i];
    cout<<ans<<endl;
    return 0;
}

d题题意:t组测试,输入3个数na,nb,nc.分别表示数组a,b,c的大小.现在要你从3个数组中各取一个数x,y,z,使得(x-y)(x-y)+(y-z)(y-z)+(x-z)(x-z)最小..思路也比较简单,你枚举一元ai/bi/ci，第二个数二分选择(bi/ci)/(ai/ci)/(ai/bi)中比ai/bi/ci大一点的数.然后第三个数就直接二分使得答案最小的数.就是答案了.复杂度nlogn*logn.

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pb push_back
typedef long long ll;
const ll inf=132913423200339;
const ll mod=998244353676776;
const int N=1e5+5;
const ll M=1e9;
const double eps=1e-7;
using namespace std;
ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b) { return a*b/gcd(a,b);    }
ll qp(ll a,ll b, ll p){ll ans = 1;while(b){if(b&1){ans = (ans*a)%p;--b;}a = (a*a)%p;b >>= 1;}return ans%p;}
ll Inv(ll x)          { return qp(x,mod-2,mod);}
ll C(ll n,ll m){if (m>n) return 0;ll ans = 1;for (int i = 1; i <= m; ++i) ans=ans*Inv(i)%mod*(n-i+1)%mod;return ans%mod;}
ll A(ll n,ll m,ll mod){ll sum=1; for(int i=n;i>=n-m+1;i--) sum=(sum*i)%mod; return sum%mod;}
ll lowbit(ll x) {return x&(-x);}
ll c[N],sum1[N],sum2[N],b[N],lsh[N],n,m,k,fa[13],a[N];
void add1(ll i,ll k){ while(i<=n) {c[i]+=k;i+=lowbit(i);}}//预处理ai单点修改 区间查询***预处理a[i]-a[i-1]区间修改单点查询
ll  Sum1(ll i) {ll res=0; while(i>0) res+=c[i],i-=lowbit(i);return res;}//预处理ai单点修改 区间查询***预处理a[i]-a[i-1]区间修改单点查询
void add2(ll i,ll k){ ll x=i;while(i<=n) {sum1[i]+=k;sum2[i]+=k*(x-1);i+=lowbit(i);}}//区间修改,区间查询
ll  Sum2(ll i) {ll res=0,x=i;while(i>0){ res+= x * sum1[i]-sum2[i]; i -= lowbit(i);}return res;}//区间修改,区间查询
void ls(){ll cnt; for(ll i=1;i<=n;i++) lsh[i]=a[i]; sort(lsh+1,lsh+n+1);cnt = unique(lsh+1,lsh+n+1)-lsh-1; for(int i=1;i<=n;i++)a[i]=lower_bound(lsh+1,lsh+cnt+1,a[i])-lsh;}
ll lca(ll x) { if(x==fa[x]) return x;else return fa[x]=lca(fa[x]); }//找祖先.
ll get_ans(ll x,ll y,ll z) { return (x-y)*(x-y)+(y-z)*(y-z)+(x-z)*(x-z); }
ll ck(ll a[],ll la,ll b[],ll lb,ll c[],ll lc)
{
    ll sum=2e18;
    for(ll i=1;i<=la;i++)
    {
        ll x=a[i];//枚举第一个数
        ll pos=lower_bound(b+1,b+1+lb,a[i])-b;
        if(pos>lb) continue;
        ll y=b[pos];//找到第一个比它大的数.
        ll r=lc;ll l=1;ll cnt=-1;
        while(l<=r)
        {
            ll mid=(l+r)>>1;
            if(c[mid]<=x)
            {
                cnt=max(cnt,mid);
                l=mid+1;
            }
            else  r=mid-1;
        }
        if(cnt==-1) continue;//假如没有找到1个比x小的数,那么continue
        ll z=c[cnt];
        sum=min(get_ans(x,y,z),sum);
    }
    return sum;
}//6种判断,写个函数比较好.

int main()
{
    ios;
    ll ans,t,na,nb,nc;
    cin>>t;
    while(t--)
    {
        cin>>na>>nb>>nc;
        for(ll i=1;i<=na;i++) cin>>a[i]; sort(a+1,a+1+na);
        for(ll i=1;i<=nb;i++) cin>>b[i]; sort(b+1,b+1+nb);
        for(ll i=1;i<=nc;i++) cin>>c[i]; sort(c+1,c+1+nc);
        ans=min(ck(a,na,b,nb,c,nc),ck(a,na,c,nc,b,nb));
        ans=min(ck(b,nb,a,na,c,nc),ans);
        ans=min(ck(b,nb,c,nc,a,na),ans);
        ans=min(ck(c,nc,a,na,b,nb),ans);
        ans=min(ck(c,nc,b,nb,a,na),ans);
        cout<<ans<<endl;
    }
    return 0;
}

e题题意:给定串S,T，长度分别为n,m，和一个空串A，每次把S的第一个字母删除然后加到A的前面或者后面。问所有的操作的过程中使得A的前缀为T的情况有多少种。
思路:区间dp.每次进行把s串的第一个字母取出,然后进行匹配,看它可以放在哪些位子.然后再计算dp[1][n]~dp[1][m]的和即可.dp[i][j]表示,与T串在i-j相同的S串的种数.

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pb push_back
typedef long long ll;
const ll inf=132913423200339;
const ll mod=998244353;
const int N=3e3+5;
const ll M=1e9;
const double eps=1e-7;
using namespace std;
ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b) { return a*b/gcd(a,b);    }
ll qp(ll a,ll b, ll p){ll ans = 1;while(b){if(b&1){ans = (ans*a)%p;--b;}a = (a*a)%p;b >>= 1;}return ans%p;}
ll Inv(ll x)          { return qp(x,mod-2,mod);}
ll C(ll n,ll m){if (m>n) return 0;ll ans = 1;for (int i = 1; i <= m; ++i) ans=ans*Inv(i)%mod*(n-i+1)%mod;return ans%mod;}
ll A(ll n,ll m,ll mod){ll sum=1; for(int i=n;i>=n-m+1;i--) sum=(sum*i)%mod; return sum%mod;}
ll lowbit(ll x) {return x&(-x);}
ll c[N],sum1[N],sum2[N],b[N],lsh[N],n,m,k,fa[13],a[N];
void add1(ll i,ll k){ while(i<=n) {c[i]+=k;i+=lowbit(i);}}//预处理ai单点修改 区间查询***预处理a[i]-a[i-1]区间修改单点查询
ll  Sum1(ll i) {ll res=0; while(i>0) res+=c[i],i-=lowbit(i);return res;}//预处理ai单点修改 区间查询***预处理a[i]-a[i-1]区间修改单点查询
void add2(ll i,ll k){ ll x=i;while(i<=n) {sum1[i]+=k;sum2[i]+=k*(x-1);i+=lowbit(i);}}//区间修改,区间查询
ll  Sum2(ll i) {ll res=0,x=i;while(i>0){ res+= x * sum1[i]-sum2[i]; i -= lowbit(i);}return res;}//区间修改,区间查询
void ls(){ll cnt; for(ll i=1;i<=n;i++) lsh[i]=a[i]; sort(lsh+1,lsh+n+1);cnt = unique(lsh+1,lsh+n+1)-lsh-1; for(int i=1;i<=n;i++)a[i]=lower_bound(lsh+1,lsh+cnt+1,a[i])-lsh;}
ll lca(ll x) { if(x==fa[x]) return x;else return fa[x]=lca(fa[x]); }//找祖先.
ll dp[N][N];
char s[N],t[N];
int main()
{
    ll ans=0;
    scanf("%s",s+1);n=strlen(s+1);
    scanf("%s",t+1);m=strlen(t+1);
    //根据状态转移赋初值.
    for(ll i=1;i<=n+1;i++) dp[i][i-1]=1;
    for(ll i=1;i<=n;i++)//枚举区间长度,以及新来的i
    {
        char c=s[i];
        for(ll k=1,j=i;j<=n;k++,j++)//拿新来的i匹配各种
        {
            if(k>m||c==t[k]) dp[k][j]=(dp[k][j]+dp[k+1][j])%mod;//假如前面的一个数
            if(j>m||c==t[j]) dp[k][j]=(dp[k][j]+dp[k][j-1])%mod;//假如后面的一个数
        }
    }
    for(ll i=m;i<=n;i++) ans=(ans+dp[1][i])%mod;
    cout<<ans<<endl;
    return 0;
}

lpt的小屋文章被收录于专栏

我想要一份甜甜的爱情