@jerrywcy 2018-08-21T14:02:41.000000Z 字数 14743 阅读 562

南外集训：2018-8-18

南外集训 2018

南外集训：2018-8-18
上午
下午

上午

A题：图的存储和遍历

问题描述：

已知图 G 已用邻接矩阵存储。

（1）编写一个程序，将图 G 转化为邻接表

（2）输出图的深度优先遍历结果 (从节点 1 开始遍历，序号从小到大)

（3）输出图的广度优先遍历结果（从节点 1 开始遍历，序号从小到大）

输入文件

第一行：节点总数 n

下面 n 行：图 G 的邻接矩阵

输出文件

第一行：图的深度优先遍历

第二行：图的广度优先遍历

样例：

输入：

0 1 1 1 0 0 0 0

1 0 0 0 0 1 0 0

1 0 0 0 1 0 0 0

1 0 0 0 1 1 1 0

0 0 1 1 0 0 0 0

0 1 0 1 0 0 0 0

0 0 0 1 0 0 0 1

0 0 0 0 0 0 1 0

输出：

1 2 6 4 5 3 7 8

1 2 3 4 6 5 7 8

(模板题你还想要题目链接？！)

题解

模板啊模板

贴代码：

#include<bits\stdc++.h>
#define fz1(i,n) for ((i)=1;(i)<=(n);(i)++)
using namespace std;
int n,m,i,j,mp[1005][1005],vis[1005],cnt;
vector<int> bi[1005];
void dfs(int x)
{
    if (vis[x]) return;
    vis[x]=1;
    printf("%d%c",x,((++cnt)==n?'\n':' '));
    int i;
    for (i=0;i<bi[x].size();i++) dfs(bi[x][i]);
}
void bfs()
{
    queue<int> qx;
    vis[1]=1;
    qx.push(1);
    while (!qx.empty())
    {
        int x=qx.front();qx.pop();
        printf("%d%c",x,((++cnt)==n?'\n':' '));
        for (i=0;i<bi[x].size();i++) if (!vis[bi[x][i]])
        {
            vis[bi[x][i]]=1;
            qx.push(bi[x][i]);
        }
    }
}
int main()
{
    scanf("%d",&n);
    fz1(i,n) fz1(j,n)
    {
        scanf("%d",&mp[i][j]);
        if (mp[i][j]) bi[i].push_back(j);
    }
    dfs(1);
    cnt=0;
    memset(vis,0,sizeof(vis));
    bfs();
    return 0;
}

B题：家庭问题

问题描述：

有 n 个人，编号分别为 1，2，…n，另外还知道存在 k 个关系。一个关系的表达为二元组（α，β）形式，表示 α，β
为同一家庭的成员。

问题：当 n,k 和 k 个关系给出之后，求出其中共有多少个家庭、最大的家庭中有多少人。

例如：n=6,k=3,三个关系为：(1，2)，(1，3)，(4，5)

此时，6 个人组成三个家庭，即：{1，2，3}为一个家庭，{4，5}为一个家庭，{6}单独为一个家庭，第一个家庭的人数最多。

输入文件

输入的第一行为 n,k 二个整数(0≤n≤100) （用空格分隔） ,接下来的 k 行，每行二个整数（用空格分隔）表示关系。

输出文件

二个整数（分别表示家庭个数和最大家庭人数）

样例：

输入：

6 3

1 2

1 3

4 5

输出：

3 3

题解

并查集模板题

贴代码：

#include<bits\stdc++.h>
#define fz1(i,n) for ((i)=1;(i)<=(n);(i)++)
using namespace std;
int n,m,i,j,fa[105],x,y,cnt[105],s1,s2;
int fnd(int x)
{
    if (fa[x]==x) return x;
    return fa[x]=fnd(fa[x]);
}
int main()
{
    scanf("%d%d",&n,&m);
    fz1(i,n) fa[i]=i;
    fz1(i,m)
    {
        scanf("%d%d",&x,&y);
        fa[fnd(x)]=fnd(y);
    }
    fz1(i,n) cnt[fnd(i)]++;
    fz1(i,n) if (cnt[i])
    {
        s1++;
        s2=max(s2,cnt[i]);
    }
    printf("%d %d\n",s1,s2);
    return 0;
}

C题：无线电通讯网

问题描述：国防部计划用无线网络连接若干个边防哨所。2 种不同的通讯技术用来搭建无线网络：每个边防哨所都要配备无线电收发器；有一些哨所还可以增配卫星电话。

任意两个配备了一条卫星电话线路的哨所均可以通话，无论它们相距多远。而只通过无线电收发器通话的哨所之间的距离不能超过 $D$ ，这是受收发器的功率限制。

收发器的功率越高，通话距离 $D$ 会更远，但同时价格也更贵。
收发器需要统一购买和安装，所以全部哨所只能选择安装一种型号的收发器。换句话说，每一对哨所之间的通话距离都是同一个 $D$ 。
你的任务是确定收发器必须的最小通话距离 $D$ ，使得每一对哨所之间至少有一条通话路径（直接的或者间接的）。

输入文件

第 1 行：2 个整数 $S$ （ $1<=S<=100$ ）和 $P$ （ $S<P\leq 500$ ）, $S$ 表示可安装的卫星电话的线路数， $P$ 表示边防哨所的数量。

接下来 $P$ 行，每行描述一个哨所的平面坐标 $(x,y)$ ,以 km 为单位，整数， $0 \leq x,y \leq 10000$ 。

输出文件

第 1 行：1 个实数 $D$ ，表示无线电收发器的最小传输距离。精确到小数点后两位。

样例：

输入：

2 4

0 100

0 300

0 600

150 750

输出：
212.13

题解

最小生成树中最长边即为答案。

贴上代码：

#include<bits/stdc++.h>
using namespace std;
int s,p;
double minn[505],dis[505][505];
struct point
{
    int x;
    int y;
};
double dist(point a,point b)
{
    return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));
}
int comp(int a,int b)
{
    return a>b;
}
point a[505];
bool u[505];
int main()
{
    int i,j;
    cin>>s>>p;
    for(i=1;i<=p;i++)
        cin>>a[i].x>>a[i].y;
    for(i=1;i<=p;i++)
        for(j=1;j<=p;j++)
            dis[i][j]=dist(a[i],a[j]);
    memset(minn,0x7f,sizeof(minn));
    minn[1]=0;
    memset(u,1,sizeof(u));
    for(i=1;i<=p;i++)
    {
        int k=0;
        for(j=0;j<=p;j++)
            if(u[j]&&(minn[j]<minn[k]))
                k=j;
        u[k]=0;
        for(j=1;j<=p;j++)
            if(u[j] && dis[k][j]<minn[j])
                minn[j]=dis[k][j];
    }
    sort(minn+1,minn+p+1,comp);
    cout<<setprecision(2)<<fixed<<minn[s]<<endl;
    return 0;
}

D题：最小差值生成树

问题描述

MST（最小生成树）是图论中的一类非常重要的问题。对你来说可能已经非常容易了。

给出一个带权图 G(V,E)，最小生成树T是图G的一棵子树。问题是：输出图的最小生成树中最长边与最短边的差。

输入文件

第一行两个数 N（ $2<N \leq 200$ ）和 $M$ ( $M \leq 5000$ ), 表示图中点的个数和边的条数。

接下来有 M 行，第 i 行有三个整数 $X_i$ ( $0<X_i \leq N$ )， $Y_i$ ( $0<Y_i \leq N$ ), $D_i$ ( $0<D_i \leq 10^8$ ),表示 $X_i$ 与 $Y_i$ 的一条边，权值为 $D_i$ ，图中任意两点间最多一条边。

输出文件：

一行，一个数，表示最小生成树中最大权值与最小权值的差。

样例：

输入：

3 3

1 2 10

1 3 20

2 3 30

输出：

题解

最小生成树模板+最长边减最短边=题解

贴代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <climits>
const int maxn = 105;
const int maxm = 10005;
int par[maxn],rank[maxn];
struct edge
{
    int from;
    int to;
    int dis;
};
edge edges[maxm];
int n,m;
void init()
{
    int i;
    for(i=0;i<=n;i++){
        par[i]=i;
        rank[i]=0;
    }
}
int find(int x)
{
    return par[x] == x ? x : par[x] = find(par[x]);
}
void unite(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x==y) return ;
    if(rank[x]<rank[y])
        par[x]=y;
    else{
        par[y]=x;
        if(rank[x]==rank[y])
            rank[x]++;
    }
}
bool cmp(edge a,edge b)
{
    return a.dis<b.dis;
}
bool same(int x,int y)
{
    return find(x)==find(y);
}
int Kruskal()
{
    int ans=INT_MAX/10;
    std::sort(edges+1,edges+1+m,cmp);
    bool flag=0;
    int i,j;
    for(i=1;i<=m;i++){
        init();
        int l,r;
        l=r=edges[i].dis;
        int cnt=0;
        unite(edges[i].from,edges[i].to);
        cnt++;
        for(j=i+1;j<=m;j++){
            if(!same(edges[j].from,edges[j].to)){
                unite(edges[j].from,edges[j].to);
                cnt++;
                r=std::max(r,edges[j].dis);
            }
        }
        if(cnt==n-1){
            ans=std::min(ans,r-l);
            flag=1;
        }
    }
    if(!flag) ans=-1;
    return ans;
}
int main()
{
    scanf("%d %d",&n,&m);
    int i,j;
    for(i=1;i<=m;i++)
        scanf("%d %d %d",&edges[i].from,&edges[i].to,&edges[i].dis);
    printf("%d\n",Kruskal());
    return 0;
}

E题：传话

问题描述

兴趣小组的同学来自各个学校，为了增加友谊，晚会上又进行了一个传话游戏，

如果 $a$ 认识 $b$ ，那么 $a$ 收到某个消息，就会把这个消息传给 $b$ ，以及所有 $a$ 认识的人。如果 $a$ 认识 $b$ ， $b$ 不一定认识 $a$ 。

所有人从 $1$ 到 $n$ 编号，给出所有“认识”关系，问如果 $i$ 发布一条新消息，那么会不会经过若干次传话后，这个消息传回给了 $i$ ， $1 \leq i \leq n$ 。

输入文件

输入的第一行是两个数 $n$ ( $n<1000$ )和 $m$ ( $m<10000$ )，两数之间有一个空格，表示人数和认识关系数。

接下来的 $m$ 行，每行两个数 $a$ 和 $b$ ，表示 $a$ 认识 $b$ 。 $1 \leq a$ , $b \leq n$ 。认识关系可能会重复给出，但一行的两个数不会相同。

输出文件

输出一共有 $n$ 行，每行一个字符 T 或 F。第 $i$ 行如果是 T，表示 $i$ 发出一条新消息会传回给 $i$ ；如果是 F，表示 $i$ 发出一条新消息不会传回给 $i$ 。

样例：

输入：

4 6

1 2

2 3

4 1

3 1

1 3

2 3

输出：

题解

我一开始还以为有多复杂其实只要暴搜就好了啊哈哈哈哈(我试图用不加句读的方式来掩饰尴尬)

贴代码：

#include<bits\stdc++.h>
#define fz1(i,n) for ((i)=1;(i)<=(n);(i)++)
#define sqr(x) (x)*(x)
using namespace std;
int n,m,i,j,vis[1005],x,y;
vector<int> bi[1005];
void dfs(int x)
{
    int i;
    for (i=0;i<bi[x].size();i++)
    {
        if (vis[bi[x][i]]) continue;
        vis[bi[x][i]]=1;
        dfs(bi[x][i]);
    }
}
int main()
{
    cin>>n>>m;
    fz1(i,m)
    {
        cin>>x>>y;
        bi[x].push_back(y);
    }
    fz1(i,n)
    {
        memset(vis,0,sizeof(vis));
        dfs(i);
        if (vis[i]) puts("T"); else puts("F");
    }
    return 0;
}

下午

A题 A Pie for a Pie

题意翻译

Bessie和Elsie都会烤N个派（ $1≤N≤10^5$ ）。是Bessie和Elsie口味不同，每个派都有两个美味值,分别是Bessie和Elsie的。

Bessie想给Elsie一个她的派。如果Elsie从Bessie那里收到一个派，她会觉得自己有义务给Bessie一个派，比如美味值为x。这样就不会显得小气、Elsie会挑一种派，至少是比她收到的派好吃的（在Elsie看来），但又美味值不增加D单位（ $0≤D≤10^9$ ），也就是[x，x+D]范围内的。这个派可能不存在，在这种情况下，Elsie将使用一个化名，把自己放逐到日本去。

但如果Elsie不给Bessie回赠一个馅饼，Bessie同样会给Elsie一个馅饼，这个派好吃但美味值不增加D单位（在Bessie眼中）。如果这是不可能的，Bessie也会放逐自己，否则她会将她选择的派给Elsie。这个循环将持续到一头牛被放逐，或一头牛收到一个价值为0（在她自己看来）的派，此时交换结束，两只奶牛都会很快乐。

请注意，一个馅饼不会被送两次，任意一只牛也不能把馅饼送给她自己。

Bessie可以选择她最初送给Elsie的礼物，请确定在交换结束之前，两只奶牛的交换次数。

感谢 @wflengxuenong 提供的翻译。

题目描述

Bessie and Elsie have each baked $N$ pies ( $1≤N≤10^5$ ). Each of the 2N2N2N pies has a tastiness value according to Bessie and a (possibly different) tastiness value according to Elsie.

Bessie is thinking about giving one of her pies to Elsie. If Elsie receives a pie from Bessie, she will feel obligated to give one of her pies to Bessie. So as to not appear stingy nor flamboyant, Elsie will try to pick a pie that is at least as tasty (in Elsie's eyes) as the pie she received, but no more than $D$ units tastier ( $0≤D≤10^9$ ). Such a pie may not exist, in which case Elsie will adopt a pseudonym and exile herself to Japan.

But if Elsie does give Bessie a pie in return, Bessie will similarly try to give Elsie a pie which is at least as tasty but no more than $D$ units tastier (in Bessie's eyes) as the pie Elsie just gave her. Should this be impossible, Bessie too will exile herself. Otherwise she will give her chosen pie to Elsie. This cycle will continue until one of the cows is exiled, an unhappy outcome, or one of the cows receives a pie which she accords a tastiness value of $0$ , in which case the gift exchange will end and both cows will be happy.

Note that a pie may not be gifted twice, nor can either cow return a pie gifted to her.

For each of the $N$ pies Bessie could select as her initial gift to Elsie, determine the minimum number of pies that could possibly be gifted in the resulting exchange before the cows are happy.

输入输出格式

输入格式：

The first line contains the two integers NNN and DDD .

The next $2N$ lines contain two space-separated integers each, respectively denoting the value of a particular pie according to Bessie, and the value of that pie according to Elsie.

The first $N$ lines refer to Bessie's pies, and the remaining $N$ lines refer to Elsie's pies.

It is guaranteed that all tastiness values are in the range $[0,10^9]$ .

输出格式：

There should be $N$ lines in the output. Line iii should contain a single integer: the minimum number of pies that could be gifted in a happy gift exchange started with Bessie's pie $i$ . If no gift exchange starting with pie iii is happy, then line iii should contain the single integer $-1$ instead.

输入输出样例

输入样例#1：

2 1
1 1
5 0
4 2
1 4

输出样例#1：

3
1

题目链接

题解

思路是建图，然后bfs

对于pie #u，和每一个一方给出#u后可以回赠的pie #v，连接单向边(v,u)。

定义dis数组，dis[i]表示从pie #i开始，最少交换多少次pie可以达到happy ending。

对于每一个属于一方，但对另一方的价值是0的pie #i，dis[i]=1。余下的都是-1。

然后bfs，如果下家dis值是-1就用当前dis值去更新，并把下家加入队列(突然发现这就是个spfa)。

贴代码：

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
struct node{
    int b,e,id;
}bs[200010],el[200010];
int n,d;
vector<int> g[200010];
int dis[200010];
queue<int> q;
bool cmpb(node x,node y){
    return x.b<y.b;
}
bool cmpe(node x,node y){
    return x.e<y.e;
}
void build(){//建图
    sort(bs+1,bs+2*n+1,cmpb);
    sort(el+1,el+2*n+1,cmpe);//排序
    int i,j;
    //对于每一个Bessie可能送来的pie #u，考虑所有满足v.e>u.e的pie #v，连接单向边(v,u)。
    for (i=1;i<=2*n;i++){
        int u=el[i].id;
        if (u>n || el[i].e==0)continue;
        for (j=i-1;j>1;j--)if (el[j].e<el[i].e)break;//找到分界点，因为排过序，所以分界点之后的都是满足条件的
        if (j<1)j=1;
        for (;j<=2*n;j++){
            if (el[j].e<el[i].e)continue;
            if (el[j].e>el[i].e+d)break;
            int v=el[j].id;
            if (v>n)g[v].pb(u);//连接单向边(v,u)。
        }
    }
    //和上面那段差不多
    for (i=1;i<=2*n;i++){
        int u=bs[i].id;
        if (u<=n || bs[i].b==0)continue;
        for (j=i-1;j>1;j--)if (bs[j].b<bs[i].b)break;
        if (j<1)j=1;
        for (;j<=2*n;j++){
            if (bs[j].b<bs[i].b)continue;
            if (bs[j].b>bs[i].b+d)break;
            int v=bs[j].id;
            if (v<=n)g[v].pb(u);
        }
    }
}
void bfs(){//spfa?
    int i,j;
    while (!q.empty()){
        int u=q.front();
        q.pop();
        for (i=0;i<g[u].size();i++){
            int v=g[u][i];
            if (dis[v]!=-1)continue;
            dis[v]=dis[u]+1;//用dis[u]更新dis[v]
            q.push(v);//v入队
        }
    }
}
int main()
{
    cin>>n>>d;
    int i,j;
    memset(dis,-1,sizeof(dis));//dis数组初始化
    for (i=1;i<=2*n;i++){
        int x,y;
        cin>>x>>y;
        bs[i]={x,y,i};
        el[i]={x,y,i};
        if ((i<=n && y==0) || (i>n && x==0))dis[i]=1,q.push(i);//边界条件
    }
    build();
    bfs();
    for (i=1;i<=n;i++)cout<<dis[i]<<endl;
    return 0;
}

B题： Barn Painting

题意翻译

题意：给定一颗N个节点组成的树，3种颜色，其中K个节点已染色，要求任意两相邻节点颜色不同，求合法染色方案数。

翻译贡献者：Il_ItzABC_lI

题目描述

Farmer John has a large farm with $N$ barns( $1≤N≤10^5$ ), some of which are already painted and some not yet painted. Farmer John wants to paint these remaining barns so that all the barns are painted, but he only has three paint colors available. Moreover, his prize cow Bessie becomes confused if two barns that are directly reachable from one another are the same color, so he wants to make sure this situation does not happen.

It is guaranteed that the connections between the NNN barns do not form any 'cycles'. That is, between any two barns, there is at most one sequence of connections that will lead from one to the other.

How many ways can Farmer John paint the remaining yet-uncolored barns?

输入输出格式

输入格式：

The first line contains two integers $N$ and $K$ ( $0≤K≤N$ ), respectively the number of barns on the farm and the number of barns that have already been painted.

The next N−1N-1N−1 lines each contain two integers $x$ and $y$ ( $1≤x,y≤N,x≠y$ ) describing a path directly connecting barns xxx and yyy .

The next KKK lines each contain two integers $b$ and $c$ ( $1≤b≤N,1≤c≤3$ ) indicating that barn $b$ is painted with color ccc .

输出格式：

Compute the number of valid ways to paint the remaining barns, modulo $10^9+7$ , such that no two barns which are directly connected are the same color.

输入输出样例

输入样例#1：

4 1
1 2
1 3
1 4
4 3

输出样例#1：

题目链接

题解

这是一道树形dp

状态转移方程不太好写，贴代码核心部分好了

void dfs(int x,int fa){
    f[x][1]=f[x][2]=f[x][3]=1;//边界
    int i,j;
    int y,tmp;
    for (i=0;i<g[x].size();i++){//遍历所有子节点
        int y=g[x][i];
        if (y==fa)continue;//如果是父节点就跳过
        dfs(y,x);
        tmp=add(f[y][1],add(f[y][2],f[y][3]));//所有颜色的方案数之和
        for (j=1;j<=3;j++)
            f[x][j]=f[x][j]*(long long)add(tmp,mod-f[y][j])%mod;//每一种颜色乘以子节点中另外两种颜色的方案数之和
    }
    if (color[x])//如果当前节点的颜色已经指定
        for (i=1;i<=3;i++)
            if (i!=color[x])
                f[x][i]=0;//别的颜色的方案数为0
}

完整代码：

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int mod=1e9+7;
int n,k;
vector<int> g[100010];
int color[100010];
long long f[100010][4];
int add(int x,int y){
    x+=y;
    if (x>=mod)return x-mod;
    else return x;
}
void dfs(int x,int fa){
    f[x][1]=f[x][2]=f[x][3]=1;
    int i,j;
    int y,tmp;
    for (i=0;i<g[x].size();i++){
        int y=g[x][i];
        if (y==fa)continue;
        dfs(y,x);
        tmp=add(f[y][1],add(f[y][2],f[y][3]));
        for (j=1;j<=3;j++)
            f[x][j]=f[x][j]*(long long)add(tmp,mod-f[y][j])%mod;
    }
    if (color[x])
        for (i=1;i<=3;i++)
            if (i!=color[x])
                f[x][i]=0;
}
int main()
{
    cin>>n>>k;
    int i,j;
    for (i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
    }
    for (i=1;i<=k;i++){
        int b,c;
        cin>>b>>c;
        color[b]=c;
    }
    dfs(1,0);
    cout<<add(f[1][1],add(f[1][2],f[1][3]))<<endl;
    return 0;
}

C题 Haybale Feast

题意翻译

题意：给定2个由N个数字组成的数列 $F$ , $S$ ,需要找到使得 $\sum_{k=i}^{j}F_k⩾M$ 的 $i$ , $j$ 并输出在所有满足条件的 $i$ , $j$ 中， $max(Si,Si+1,...Sj−1,Sj)$ 的最小值。

翻译贡献者：Il_ItzABC_lI

题目描述

Farmer John is preparing a delicious meal for his cows! In his barn, he has NNN haybales ( $1≤N≤100,000$ ). The iii th haybale has a certain flavor $F_i$ ( $1≤F_i≤10^9$ ) and a certain spiciness SiS_iSi( $1≤Si≤10^9$ ).

The meal will consist of a single course, being a contiguous interval containing one or more consecutive haybales (Farmer John cannot change the order of the haybales). The total flavor of the meal is the sum of the flavors in the interval. The spiciness of the meal is the maximum spiciness of all haybales in the interval.

Farmer John would like to determine the minimum spiciness his single-course meal could achieve, given that it must have a total flavor of at least $M$ ( $1≤M≤10^{18}$ ).

输入输出格式

输入格式：

The first line contains the integers $N$ and $M$ , the number of haybales and the minimum total flavor the meal must have, respectively. The next $N$ lines describe the $N$ haybales with two integers per line, first the flavor $F$ and then the spiciness $S$ .

输出格式：

Please output the minimum spiciness in a single course meal that satisfies the minimum flavor requirement. There will always be at least one single-course meal that satisfies the flavor requirement.

输入输出样例

输入样例#1：

5 10
4 10
6 15
3 5
4 9
3 6

输出样例#1：

题目链接

题解

这题比较简单，连我这样的菜鸡都能AC。。。

两个指针l，r，如果当前总风味不到m，r++，反之l++。其中总辣度用单调队列维护。

据说还有一种线段树解法，不过我没去想。。。

单调队列：

#include <bits/stdc++.h>
using namespace std;
struct num{
    int x,i;
};
class simple_queue{
    public:
        num a[100010];
        int l,r;
        void clear(){
            memset(a,0,sizeof(a));
            l=1,r=0;
        }
        void push(int x,int i){
            while (a[r].x<x && r>=l)r--;
            r++;
            a[r].x=x,a[r].i=i;
        }
        void pop(int t){
            while (a[l].i<t && l<=r)l++;
        }
        int front(){
            return a[l].x;
        }
};
long long n,m;
int f[100010],s[100010];
int ans=-1;
int main()
{
    cin>>n>>m;
    int i,j;
    for (i=1;i<=n;i++){
        cin>>f[i]>>s[i];
    }
    long long l,r,sumf;
    l=1,r=1,sumf=0;
    simple_queue sums;
    sums.clear();
    while (r<=n){
        while (sumf<m && r<=n){
            sumf+=f[r];
            sums.push(s[r],r);
            r++;
        }
        if (sumf>=m){
            if (ans!=-1)ans=min(ans,sums.front());
            else ans=sums.front();
//          cout<<l<<' '<<r<<' '<<ans<<endl;
        }
        while (sumf>=m && l<r){
            l++;
            sumf-=f[l];
        }
        sums.pop(l);
    }
    cout<<ans<<endl;
    return 0;
}

线段树代码：

//按b从小到大排序，然后按顺序往里扔，维护最大子段和，如果合法了即得到答案。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 100010
#define pa pair<int,int>
inline char gc(){
    static char buf[1<<16],*S,*T;
    if(S==T){T=(S=buf)+fread(buf,1,1<<16,stdin);if(T==S) return EOF;}
    return *S++;
}
inline ll read(){
    ll x=0,f=1;char ch=gc();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc();
    return x*f;
}
int n;
ll K;
struct hhh{
    int a,b,id;
    friend bool operator<(hhh a,hhh b){return a.b<b.b;}
}a[N];
struct node{
    ll ls,rs,s;bool cov;
}tr[N<<2];
inline void update(int p){
    if(tr[p<<1].cov&&tr[p<<1|1].cov){
        tr[p].cov=1;tr[p].ls=tr[p].rs=tr[p].s=tr[p<<1].s+tr[p<<1|1].s;return;
    }tr[p].ls=tr[p<<1].ls;tr[p].rs=tr[p<<1|1].rs;
    if(tr[p<<1].cov) tr[p].ls+=tr[p<<1|1].ls;
    if(tr[p<<1|1].cov) tr[p].rs+=tr[p<<1].rs;
    tr[p].s=max(tr[p<<1].s,tr[p<<1|1].s);
    tr[p].s=max(tr[p].s,tr[p<<1].rs+tr[p<<1|1].ls);
}
inline void build(int p,int l,int r){
    tr[p].ls=tr[p].rs=tr[p].s=tr[p].cov=0;
    if(l==r) return;
    int mid=l+r>>1;
    build(p<<1,l,mid);
    sbuild(p<<1|1,mid+1,r);
}
inline void ins(int p,int l,int r,int x,int val){
    if(l==r){tr[p].ls=tr[p].rs=tr[p].s=val;tr[p].cov=1;return;}
    int mid=l+r>>1;
    if(x<=mid) ins(p<<1,l,mid,x,val);
    else ins(p<<1|1,mid+1,r,x,val);update(p);
}
int main(){
    n=read();K=read();
    for(int i=1;i<=n;++i) a[i].a=read(),a[i].b=read(),a[i].id=i;
    sort(a+1,a+n+1);build(1,1,n);int ans=0;
    for(int i=1;i<=n;++i){
        ins(1,1,n,a[i].id,a[i].a);
        if(tr[1].s>=K){ans=a[i].b;break;}
    }printf("%d\n",ans);
    return 0;
}

完毕

南外集训：2018-8-18

上午

A题：图的存储和遍历

问题描述：

输入文件

输出文件

样例：

输入：

输出：

题解

B题：家庭问题

问题描述：

输入文件

输出文件

样例：

输入：

输出：

题解

C题：无线电通讯网

题解

D题：最小差值生成树

问题描述

输入文件

输出文件：

样例：

输入：

输出：

题解

E题：传话

问题描述

输入文件

输出文件

样例：

输入：

输出：

题解

下午

A题 A Pie for a Pie

题意翻译

题目描述

输入输出格式

输入格式：

输出格式：

输入输出样例

输入样例#1：

输出样例#1：

题解

B题： Barn Painting

题意翻译

题目描述

输入输出格式

输入格式：

输出格式：

输入输出样例

输入样例#1：

输出样例#1：

题解

C题 Haybale Feast

题意翻译

题目描述

输入输出格式

输入格式：

输出格式：

输入输出样例

输入样例#1：

输出样例#1：

题解

内容目录