JSOI2010~2011

标签：sign   line   sim   har   query   define   交换   优化   top   

A 旅行

题面:bzoj
题解：神奇的\(dp\)
先按长度把边排序
指定必须走前\(l\)条边，枚举\(l\)
设\(dis[i][j][k]\)表示当前到了\(i\)节点，已走过了\(j\)条前\(l\)条边，用了\(k\)次交换次数
code

B 找零钱的洁癖

题面：bzoj
题解：更为神奇
首先直接bfs，到一定程度break
其次乱贪心
据\(\text{M}\)\(\color{red}{\text{_sea}}\)说正解是整数规划？
不会，告辞
code

H 柠檬

题面：Luogu
题解：斜率优化
首先有一个显然的性质就是：一段两端必定相同并且是这一段选定的大小（否则可以证明结果必定小于这种）
设\(dp[i]\)表示前\(i\)个的答案，\(s[i]\)表示\(i\)是\(1\sim n\)内相同大小的第几个
\[dp[i]=max_{0
于是有
只与\(i\)有关的：\(a[i]*s[i]^2+2*a[i]*s[i]+a[i]\)
只与\(j\)有关的：\(dp[j-1]+a[i]*s[j]^2-2*a[i]*s[j](a[i]==a[j])\)
既和\(i\)有关又和\(j\)有关的：\(-2a[i]s[i]s[j]\)
于是套斜率优化板子，维护上凸壳，栈顶最优决策
注意要先把自己丢进去再决策
由于空间问题用\(vector\)模拟栈
code

I 分特产

题面：Luogu
题解：容斥
设至少\(x\)个人什么都没有
也就是把\(a[i]\)个特产分给\(n-x\)个人
于是在\(n-x-1\)个空格里随意插\(a[i]\)块隔板
根据乘法原理，对每一种特产考虑最后再乘起来
方案数就是\(\prod_{i=1}^{m}{C_{n-x-1+a[i]}^{a[i]}}\)
反演一下（相比之下我更喜欢这个而不是容斥）
答案就是恰好0人什么都没有
\[ans=\sum_{i=0}^{n-1}{(-1)^iC_{n}^{i}\prod_{j=1}^{m}{C_{n-i-1+a[j]}^{a[j]}}}\]
code

J 棒棒糖

题面：Luogu
是重题
建一颗主席树，如果\([1,mid]\)内没有这么多个数字就显然没有，再看\([mid+1,r]\)
code

K 任务调度

题面：bzoj
题解：可并堆
修改操作就把这个点抠出来（合并它的左右儿子），再塞回去
据说可以用pb_ds水过去（然而我搞了一下午没搞出来）
code

code A

#include
using namespace std;
#define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout);
inline void read(int& x)
{
    x=0;char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
}
#define maxn 155
struct Edge
{
    int fr,to,val;
}eg[maxnb.dis;
        }
};
priority_queue q;
int dis[52][maxn][maxn],vis[52][maxn][maxn];
int n,m,k,ans=0x7fffffff;
inline void work(int l)
{
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    dis[1][0][0]=0;
    q.push((Node){1,0,0});
    int x,y,z;
    while(!q.empty())
    {
        x=q.top().x,y=q.top().y,z=q.top().z;
        q.pop();
        if(vis[x][y][z]) continue;
        vis[x][y][z]=1;
        for(int i=head[x];i;i=eg[i].fr)
        {
#define to eg[i].to
            if(idis[x][y][z]+d[y+1].val)
                    dis[to][y+1][z]=dis[x][y][z]+d[y+1].val,q.push((Node){to,y+1,z,dis[to][y+1][z]});
            }
            else
            {
                if(ydis[x][y][z]+d[y+1].val)
                    dis[to][y+1][z+1]=dis[x][y][z]+d[y+1].val,q.push((Node){to,y+1,z+1,dis[to][y+1][z+1]});
                if(dis[to][y][z]>dis[x][y][z]+eg[i].val)
                    dis[to][y][z]=dis[x][y][z]+eg[i].val,q.push((Node){to,y,z,dis[to][y][z]});
            }
#undef to
        }
    }
    for(int i=0;i

top

B code

#include
using namespace std;
#define ll long long
#define pa pair
#define mp make_pair
#define inf 0x7fffffff
queue q;
//unordered_map m;
map m;
ll n,a[105],x;
inline ll bfs()
{
    q.push(mp(0,0));
    ll val,step,tp;
    while(!q.empty())
    {
        val=q.front().first,step=q.front().second;
        q.pop();
        for(int i=1;i=1000000) return inf;
            val

top

H code

#include
using namespace std;
#define int long long
inline void read(int& x)
{
    x = 0; char c = getchar();
    while (!isdigit(c)) c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
}
#define maxn 100005
#define maxm 10005
#define ll long long
int las[maxm];
vector st[maxm];
int a[maxn], s[maxn], n;
ll dp[maxn];
inline int x(const int& i)
{
    return a[i] * s[i];
}
inline int y(const int& i)
{
    return dp[i - 1] + (a[i] * s[i] - 2) * s[i];
}
inline ll Pow(const int& X)
{
    return 1ll * X * X;
}
inline double slope(int i, int j)
{
    return 1.0 * (y(i) - y(j)) / (x(i) - x(j));
}
inline ll calc(int i, int j)
{
    return dp[j - 1] + a[i] * Pow(s[i] - s[j] + 1);
}
signed main()
{
    read(n);
    for (int i = 1; i = 2 && slope(A, i) >= slope(A, B)) st[t].pop_back();
        st[t].push_back(i);
        while (st[t].size() >= 2 && calc(i, A) >= calc(i, B)) st[t].pop_back();
        dp[i] = calc(i, st[t].back());
    }
    printf("%lld\n", dp[n]);
    return 0;
}

top

I code

#include
using namespace std;
inline void read(int& x)
{
    x = 0; char c = getchar();
    while (!isdigit(c)) c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
}
#define p 1000000007
#define maxn 2005
int fac[maxn], inv[maxn], f[maxn], a[maxn];
inline int qpow(int x, int y)
{
    int ans = 1;
    while (y)
    {
        if (y & 1) ans = 1ll * ans * x % p;
        x = 1ll * x * x % p;
        y >>= 1;
    }
    return ans;
}
inline int C(int n, int m)
{
    return 1ll * fac[n] * inv[m] % p * inv[n - m] % p;
}

int main()
{
    int ans = 0, n, m;
    read(n), read(m);
    for (int i = 1; i 

n; ++i) { f[0] = 1; for (int j = 1; j

top

J code

#include
using namespace std;
#define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout);
inline void read(int& x)
{
    x=0;char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
}
#define maxn 500005
int ls[maxn*32],rs[maxn*32],val[maxn*32],rt[maxn],tot;
int n,m,w;
void build(int& rt,int l,int r)
{
    rt=++tot;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(ls[rt],l,mid);
    build(rs[rt],mid+1,r);
}
void update(int& rt,int las,int l,int r,int pos)
{
    rt=++tot;
    ls[rt]=ls[las],rs[rt]=rs[las],val[rt]=val[las]+1;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(pos>1;
        if(((val[ls[to]]-val[ls[fr]])len) r=mid,fr=ls[fr],to=ls[to];
        else if(((val[rs[to]]-val[rs[fr]])len) l=mid+1,fr=rs[fr],to=rs[to];
        else return 0;
    }
}
int main()
{
    read(n),read(m);
    build(rt[0],1,n);
    for(int i=1;i

top

K code

#include
using namespace std;
inline void read(int& x)
{
    x=0;char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
}
#define maxn 300005
int dis[maxn],rt[maxn],val[maxn],fa[maxn],son[maxn][2];
int merge(int x,int y)
{
    if(!x||!y) return x|y;
    if(val[x]>val[y]) swap(x,y);
    son[x][1]=merge(son[x][1],y);
    if(dis[son[x][0]]

top

JSOI2010~2011

标签：sign   line   sim   har   query   define   交换   优化   top   

原文地址：https://www.cnblogs.com/123789456ye/p/12250181.html