JSOI2014

标签：就是   odi   电信   last   gen   second   int   bre   else   

B 宅男计划

题面：bzoj
题解：三分+贪心
可以发现一个显然的性质
就是你买外卖的次数和你能维持的天数大概是成一个单峰函数证明不会
于是我们三分峰值
然后找到这个次数后再贪心
首先把那些又贵又放不久的扔掉，可以用单调栈
然后从最便宜的开始往上贪心
code

C 骑士游戏

题面：bzoj
题解：最短路？
可以显然的写出一个dp方程，然而你会发现会有环
我们发现这个方程的形式和spfa的转移形式差不多
所以把所有点扔到队列里，初值设置魔法攻击的代价，跑最短路
如果这个点被更新了，则反图上与它相连的点都有可能更新，入队
codeC

F 奇怪的计算器

题面：bzoj
题解：线段树
首先将这些值，因为不管怎么样都不会改变他们的大小关系
区间修改，如果最小的值小于下界就直接推平，上界同理
codeF

G 支线剧情2

题面：bzoj
题解：树形dp
设\(f[i]\)表示这个点有存档，之后都不存档的最少代价
\[f[u]=\sum_{(u,v,w)\in E}{f[v]+siz[v]*w}\]
设\(dp[u]\)表示这个点子树内有存档的最小代价
如果当前点存档，儿子也有一个存档则\(dp[u]+=dp[v]+deep[v]\)，\(deep\)为从1到这个点的距离
否则直接转移（就是枚举一个最小值）
codeG

I 强连通图

题面：bzoj
题解：缩点
直接缩点就可以了
codeI

J 歌剧表演

题面：bzoj
题解：
用set维护不能分辨出来的一群人，相当于染色
具体看代码吧
codeJ

M 电信网络

题面：bzoj
题解：最大权闭合子图
codeM

O 序列维护

题面：bzoj
题解：线段树
区间加法，区间乘法
codeO

B code

#include
using namespace std;
#define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout);
template
inline void read(T& x)
{
    x=0;char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
}
#define maxn 205
#define ll long long
struct Food
{
    ll v,t;
    inline friend bool operator 

top

C code

#include
using namespace std;
template
inline void read(T& x)
{
    x=0;char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
}
#define maxn 2000005
#define ll long long
struct Edge
{
    int fr,to;
}eg[maxn],eg_rev[maxn];
int head[maxn],head_rev[maxn],edgenum,vis[maxn],n;
inline void add(int fr,int to)
{
    eg[++edgenum]=(Edge){head[fr],to};
    eg_rev[edgenum]=(Edge){head_rev[to],fr};
    head[fr]=head_rev[to]=edgenum;
}
ll dis[maxn],s[maxn];
void spfa()
{
    queue q;
    for(int i=1;i

top

F code

#include
using namespace std;
#define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout);
template
inline void read(T& x)
{
    x=0;char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
}
#define maxn 200005
#define ll long long
struct OP
{
    int type;ll val;
}q[maxn];
pair a[maxn];
struct Node
{
    int l,r;
    ll ptag,mtag,ptag2,mn,mx;
}t[maxn>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup(rt);
}
void pushmin(const int& rt)
{
    if(t[rt].l==t[rt].r) return modify(rt,L,0,0);
    pushdown(rt);
    if(t[rs].mnR) modify(rs,R,0,0),pushmax(ls);
    else pushmax(rs);
    pushup(rt);
}
void dfs(const int& rt)
{
    if(t[rt].l==t[rt].r)
    {
        ans[a[t[rt].l].second]=t[rt].mn;
        return;
    }
    pushdown(rt);
    dfs(ls),dfs(rs);
}
int id[256];
int main()
{
    //file("test");
    int n,m;char op[2];
    id['+']=0,id['-']=1,id['*']=2,id['@']=3;
    read(n),read(L),read(R);
    for(int i=1;iR) pushmax(1);
    }
    dfs(1);
    for(int i=1;i

top

G 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 1000005
#define ll long long
struct Edge
{
    int fr,to,val;
}eg[maxn

top

I 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 1000005
struct Edge
{
    int fr,to;
}eg[maxn s;
void Tarjan(int rt)
{
    low[rt]=dfn[rt]=++dfn_clock;
    s.push(rt);
    vis[rt]=1;
    for(int i=head[rt];i;i=eg[i].fr)
    {
#define to eg[i].to
        if(!dfn[to]) Tarjan(to),low[rt]=min(low[rt],low[to]);
        else if(vis[to]) low[rt]=min(low[rt],dfn[to]);
#undef to
    }
    if(low[rt]==dfn[rt])
    {
        ++colnum;
        siz=0;
        while(s.top()!=rt)
        {
            int tp=s.top();
            s.pop();
            col[tp]=colnum;
            ++siz;
            vis[tp]=0;
        }
        s.pop();
        col[rt]=colnum;
        ++siz;
        vis[rt]=0;
        ans=max(ans,siz);
    }
}
int main()
{
    int n,m,x,y;
    scanf("%d%d",&n,&m);
    for(int i=1;i

top

J 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 100005
set s[maxn];
int a[maxn], col[maxn], ans[maxn], cnt, n, m;
inline bool cmp(int a, int b)
{
    return col[a] 

top

M code

#include
using namespace std;
template
inline void read(T& x)
{
    x=0;char c=getchar();int f=1;
    while(!isdigit(c)) {if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
    x*=f;
}
#define maxn 505
#define inf 0x3f3f3f3f
struct Edge
{
    int fr,to,val;
}eg[maxn*maxn*2];
int head[maxn],edgenum=1,n,m;
inline void add(int fr,int to,int val)
{
    eg[++edgenum]=(Edge){head[fr],to,val};
    head[fr]=edgenum;
}
int deep[maxn],gap[maxn],cur[maxn],s,t,maxflow;
void bfs()
{
    queue q;
    for(int i=0;i0) add(s,i,o[i].v),add(i,s,0),ans+=o[i].v;
        else add(i,t,-o[i].v),add(t,i,0);
    }
    ISAP();
    printf("%d\n",ans-maxflow);
    return 0;
}

top

O code

#include
using namespace std;
#define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout);
template
inline void read(T& x)
{
    x=0;char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
}
#define maxn 200005
#define ll long long
struct Node
{
    int l,r;
    ll val,ptag,mtag;
}t[maxn>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup(rt);
}
inline void update(int rt,int l,int r,int fr,int to,ll ptag,ll mtag)
{
    if(fr=r) return modify(rt,ptag,mtag);
    int mid=(l+r)>>1;
    pushdown(rt);
    if(frmid) update(rs,mid+1,r,fr,to,ptag,mtag);
    pushup(rt);
}
inline ll query(int rt,int l,int r,int fr,int to)
{
    if(fr=r) return t[rt].val;
    int mid=(l+r)>>1;ll ans=0;
    pushdown(rt);
    if(frmid) ans+=query(rs,mid+1,r,fr,to);
    return ans%p;
}
inline void print(int n)
{
    for(int i=1;i

top

JSOI2014

标签：就是   odi   电信   last   gen   second   int   bre   else   

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