首页 > 代码库 > APIO 2016

APIO 2016

2024-09-05 23:55:45   220人阅读

我好菜啊都不会

 

T1.boats

题目大意：给你N段区间，每段区间可以选一个数或不选，若选则选的这个数必须大于所有在这之前选的数，求有多少种方案。（N<=500，区间在[1,1e9]范围内）

思路：我的做法比较奇怪……根据DP的思路，题目可以转化为一个数列一开始0的位置是1其他都是0，然后每次把一个区间里的数全部变成原来数列的前缀和，然后我按权值分了个块，预处理出一开始都为1的各个长度的区间经过多次前缀和后和为多少，每次操作把一个新的值插入离散出来的区间里，利用预处理的信息算答案，复杂度O(kn+1e9/k*n^2)，k为块大小，子任务制得分58/100（最后一个T），正解好像说用组合数什么的可以直接算出来……

技术分享 
#include<cstdio>
#include<algorithm>
using namespace std;
inline int read()
{
    int x;char c;
    while((c=getchar())<‘0‘||c>‘9‘);
    for(x=c-‘0‘;(c=getchar())>=‘0‘&&c<=‘9‘;)x=(x<<3)+(x<<1)+c-‘0‘;
    return x;
}
#define MN 500
#define MC 11000
#define K 100000
#define MOD 1000000007
int l[MN+5],r[MN+5],c[MC+5],cn;
int f[MN+5][K+5],s[MC+5],t[MC+5],p[MC+5][MN+5];
inline int mod(int x){return x>=MOD?x-MOD:x;}
int main()
{
    int n=read(),i,j,k,x,v;
    for(i=1;i<=K;++i)f[1][i]=i;
    for(i=2;i<=n;++i)for(j=1;j<=K;j+=4)
        f[i][j  ]=mod(f[i][j-1]+f[i-1][j  ]),
        f[i][j+1]=mod(f[i][j  ]+f[i-1][j+1]),
        f[i][j+2]=mod(f[i][j+1]+f[i-1][j+2]),
        f[i][j+3]=mod(f[i][j+2]+f[i-1][j+3]);
    for(i=1;i<=n;++i)c[++cn]=l[i]=read()-1,c[++cn]=r[i]=read();
    sort(c+1,c+cn+1);
    for(i=1,j=0;i<=cn;++i)if(c[i]!=c[j])c[++j]=c[i];cn=j;
    for(i=1,j=cn;i<j;++i)for(k=c[i];c[i+1]-k>K;)c[++cn]=k+=K;
    sort(c+1,c+cn+1);
    for(i=1;i<=n;++i)for(j=x=1;j<=cn;++j)
        if(c[j-1]>=l[i]&&c[j]<=r[i])
        {
            p[j][t[j]++]=x;x=mod(x+s[j]);v=c[j]-c[j-1];
            for(k=s[j]=0;k<t[j];++k)
                s[j]=(s[j]+1ll*p[j][k]*f[t[j]-k][v])%MOD;
        }
        else x=mod(x+s[j]);
    for(i=1,x=0;i<=cn;++i)x=mod(x+s[i]);
    printf("%d",x);
}
View Code

 

T2.fireworks

题目大意：给出一棵带边权的树，调整树上边长的消耗是调整后的减去调整前的绝对值，求使根节点到所有叶节点距离相等的最小花费，边长必须大等0。（叶节点个数<=300,000，每个非叶节点除连向父亲外至少连2条边）

思路：我只会边长没有非负限制的，树上DP，求出每棵子树根节点到所有叶节点距离相同的最小花费和达成这个花费所允许的根到叶距离（由后面求法可知必然是一个区间），最底层合并时所有子树（只有叶节点）允许的距离都只有一个，问题即为求一点到所有点距离最小，即求中位数，如果有两个中位数那么允许的距离就是两个中位数之间的区间，再向上合并时相当于求一点到多条线段距离最小，还是所有端点的中位数，于是就能求了，复杂度大约O(nlogn)，可惜如果这样做的话边长可能出现负数……子任务制下得分只有7/100 QAQ。

技术分享 
#include<cstdio>
#include<algorithm>
#include<vector>
#include<iostream>
using namespace std;
#define ll long long
inline int read()
{
    int x=0;char c;
    while((c=getchar())<‘0‘||c>‘9‘);
    for(;c>=‘0‘&&c<=‘9‘;c=getchar())x=(x<<3)+(x<<1)+c-‘0‘;
    return x;
}
#define MN 300000
struct edge{int nx,t,w;}e[MN*2+5];
int n,h[MN+5],en;
ll f[MN+5],l[MN+5],r[MN+5];
vector<ll> v[MN+5];
inline void ins(int x,int y,int w)
{
    e[++en]=(edge){h[x],y,w};h[x]=en;
    e[++en]=(edge){h[y],x,w};h[y]=en;
}
inline ll z(ll x){return x<0?-x:x;}
void dp(int x,int fa)
{
    if(x>n)return;
    for(int i=h[x];i;i=e[i].nx)if(e[i].t!=fa)
    {
        dp(e[i].t,x);
        f[x]+=f[e[i].t];
        v[x].push_back(l[e[i].t]+e[i].w);
        v[x].push_back(r[e[i].t]+e[i].w);
        f[x]-=r[e[i].t]-l[e[i].t];
    }
    sort(v[x].begin(),v[x].end());
    l[x]=v[x][v[x].size()/2-1];r[x]=v[x][v[x].size()/2];
    for(int i=0;i<v[x].size();++i)f[x]+=z(l[x]-v[x][i]);
}
int main()
{
    int m,i,x;
    n=read();m=read();
    for(i=2;i<=n+m;++i)x=read(),ins(x,i,read());
    dp(1,0);
    cout<<f[1]/2;
}
View Code

 

T3.gap

题目大意：交互题，有一个N个数的上升序列，不具体给出序列，仅支持一个操作：MinMax(l,r)，会给你数值大小在[l,r]内的序列中元素的最大值和最小值，要求你求出序列中相邻元素的最小差。subtask1：每次MinMax的代价为1，使用的代价不得超过(N+1)/2；subtask2：每次MinMax的代价为[l,r]间元素个数，使用的代价不得超过3N。（N<=100,000，序列中元素在[1,1e18]内）

思路：我只会subtask1，先询问[1,1e18]，得出最小值x最大值y，再询问[x+1,y-1]，以此类推，就能(N+1)/2次询问得出整个序列，得分30/100。

技术分享 
#include<cstdio>
#include<algorithm>
#include"gap.h"
#define ll long long
using namespace std;
#define MN 100000
#define INF 1e18
ll n,a[MN+5];
ll findGap(int t,int n)
{
        ll i=1,j=n,l=0,r=INF;
        for(;i<=j;l=a[i++]+1,r=a[j--]-1)MinMax(l,r,a+i,a+j);
        for(i=1,r=0;i<n;++i)r=max(r,a[i+1]-a[i]);
        return r;
}
View Code

 

APIO 2016


联系
我们