NEERC2017

链接：https://codeforces.com/gym/101630/attachments

A - Archery Tournament

题意

执行以下操作的两种：
1、在点$(x,y)$建立一个圆形靶子，靶子与x轴相切。
2、在点$(x,y$进行射击，如果射中靶子，输出靶子编号，并将靶子移除；否则输出$-1$。

思路

将坐标离散化后，在坐标轴建立线段树。结点使用set维护靶子信息。
更新信息每次都是找到最底层，不需要up和down。
注意删除靶子信息时不能找到后原地删除，因为这个靶子的信息不只存于当前要找的区间。
注意共有2n个点，线段树大小应为8n。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
using namespace std;

typedef long long ll;

const int N = 4e5 + 7;

struct operation{
    int op;
    ll l, r;
}a[N];

struct Sgt{
    int l,r;
    set<int> id;
    #define l(u) tr[u].l
    #define r(u) tr[u].r
    #define ls u<<1
    #define rs u<<1|1
}tr[N<<2];

void build(int u,int l,int r) {
    l(u) = l, r(u) = r;
    if (l == r) return;
    int mid = l + r >> 1;
    build(ls, l, mid), build(rs, mid + 1, r);
}

void change(int u,int l,int r,int idx) {
    if (l(u) == l && r(u) == r) {//找到了要找的结点，修改靶子标号。
        tr[u].id.insert(idx);
        return;
    }
    int mid = l(u) + r(u) >> 1;
    if (r <= mid) change(ls, l, r, idx);//完全在左子树
    else if (l > mid) change(rs, l, r, idx);//完全在右子树
    else change(ls, l, mid, idx), change(rs, mid + 1, r, idx);//区间被mid分隔
}

int ask(int u,int p,int idx) {
    for (auto it : tr[u].id) {//查询覆盖该点的所有靶子信息
        ll y = a[it].r;
        ll dx = a[idx].l - a[it].l, dy = a[idx].r - a[it].r;
        if (dx *dx + dy * dy < y * y) return it;//如果在某个靶子内部，返回答案
    }
    if (l(u) == r(u)) return -1;//没有找到，返回-1
    int mid = l(u) + r(u) >> 1;//二分
    if (p <= mid) return ask(ls, p, idx);
    else return ask(rs, p, idx);
}

void del(int u,int l,int r ,int idx) {//同change操作
    if (l(u) == l && r(u) == r ) {
        tr[u].id.erase(idx);
        return;
    }
    int mid = l(u) + r(u) >> 1;
    if (r <= mid) del(ls, l, r, idx);
    else if (l > mid) del(rs, l, r, idx);
    else del(ls, l, mid, idx), del(rs, mid + 1, r, idx);
}

int n,tot;
ll b[N];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) {
        scanf("%d%lld%lld", &a[i].op,&a[i].l, &a[i].r);
        if (a[i].op == 1) b[++tot] = a[i].l - a[i].r, b[++tot] = a[i].l + a[i].r;
        else b[++tot] = a[i].l;
    }
    //排序去重离散化
    sort(b + 1, b + 1 + tot);
    tot = unique(b + 1, b + 1 + tot) - (b + 1);
    build(1, 1, tot);
    for (int i = 1; i <= n; i ++ ) {
        if (a[i].op == 1) {
            int l = lower_bound(b + 1, b + 1 + tot, a[i].l - a[i].r) - b;
            int r = lower_bound(b + 1, b + 1 + tot, a[i].l + a[i].r) - b;
            //得到离散化后的靶子左右端点，在这个区间上覆盖其编号信息。
            change(1, l, r, i);
        } else {
            int po = lower_bound(b + 1, b + 1 + tot, a[i].l) - b;
            int ans = ask(1, po, i);
            //查询在po点的所有信息，如果需要删除就进行更新
            printf("%d\n",ans);
            if (ans != -1) {
                int l = lower_bound(b + 1, b + 1 + tot, a[ans].l - a[ans].r) - b;
                int r = lower_bound(b + 1, b + 1 + tot, a[ans].l + a[ans].r) - b;
                del(1, l, r, ans);
            }
        }
    }
    return 0;
}

C - Connections

题意

给出一个由$n$个点，$m$条边组成的的有向强连通图。
输出删除$m-2*n$条边后仍是强连通图的删边方案。

思路

由强连通图知各点两两可达。找一个点，正向跑出来一棵树，再反向跑出来一棵树，在反图上跑相当于所有点向该点跑。两棵树组成的图各点之间两两可达，需要$2*(n-1)$条边。

代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <map>
#include <set>
using namespace std;

const int N = 2e5 + 7;

typedef pair<int,int> PII;

vector<int> eg[N],deg[N];

bool v[N];

set<PII> res;

void dfs(int x) {
    v[x] = 1;
    for ( auto i : eg[x] ) {
        if (!v[i])
        dfs(i),res.insert({x,i});
    }
}

void dfs2(int x) {
    v[x] = 1;
    for (auto i : deg[x]) {
        if (!v[i]) dfs2(i), res.insert({i,x});
    }          
}

void solve() {
    int n,m;
    cin >> n >> m;
    vector<PII> edge;
    res.clear();
    for (int i = 1; i <= n; i ++ ) eg[i].clear(), deg[i].clear();
    for (int i = 1;  i<= m; i ++ ) {
        int x,y;
        cin >> x >> y;
        edge.push_back({x,y});
        eg[x].emplace_back(y);
        deg[y].emplace_back(x);
    }
    memset(v,0,sizeof v);
    dfs(1);
    memset(v,0,sizeof v);
    dfs2(1);
    int idx = 0;
    for (int i = 0; i < m && idx < m - 2*n; i ++ ) {
        if (res.find({edge[i].first,edge[i].second}) == res.end() ) printf("%d %d\n",edge[i].first,edge[i].second),idx++;
    }
}

signed main() {
    int t ;
    cin >> t;
    while (t--) solve();
}

F - The Final Level

题意

给出一个由两个$1*n$的矩形拼接成的折角行，要求在$x*y$网格图上使用这种折角型铺路，使得可以从$(0,0)$点走到$(x,y)$点。求最少使用的道具数量。

思路

不难发现，每次可以在水平或者垂直方向上选择一个未走过的点进行铺设，在该方向上就会多铺一个。
如图：在水平轴上铺设：

在竖直轴上铺设。

在铺设的方向上就会多走一格。
那么就可以贪心地选择，每次优先在距离目标点较远的那个轴上铺设。
另外在铺设的时候，为了防止冲突（道具之间有交叉的情况），需要保持铺设的方向一致。
在最后两个维度距离都小于道具长度时，还要根据上一次道具摆放的方向来确定最后一个道具摆放的方向。
如果倒数第二块道具是从竖直方向过来的，

那么最后一块道具应该这样放

如果是从水平轴走过来，

应该这样摆放。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

vector<vector<int> > res;
int x,y,n;
// 占用y，fg为0
void work(int x,int y,int fg = -1) {
    if ( x >= n && y >= n ) {
        if (x <= y) {
            res.push_back(vector<int>{x, y, x - n + 1, y - n + 1});
            work(x - n + 1, y - n, 0);//优先走y轴
        }else {
            res.push_back(vector<int> {x, y, x - n + 1, y - n + 1});
            work(x - n, y - n + 1, 1);//优先走x轴
        }
    }else if (x >= n ) {
        res.push_back(vector<int>{x, y - n + 1, x - n + 1, y});
        work(x - n, y, 1);
    }else if (y >= n ) {
        res.push_back(vector<int>{x, y - n + 1, x - n + 1, y});//方向只能向下，不然可能会冲突
        work(x, y - n, 0);
    }else {
        if (fg == 0) res.push_back(vector<int>{0, y - n + 1, n - 1, y});//从y轴走过来
        else res.push_back(vector<int>{x, n - 1, x - n + 1, 0});//从x轴走过来
    }
}

void solve () {
    cin>> x >> y >> n;
    res.clear();
    int fx = 1, fy = 1;
    if (x < 0) fx = -1, x = -x;
    if (y < 0) fy = -1, y = -y;
    //转换方向
    work(x, y);
    printf("%d\n",res.size());
    for (auto i : res) printf("%d %d %d %d\n",i[0]*fx,i[1]*fy,i[2]*fx,i[3]*fy);
}

int main() {
    int  t;
    cin >> t ; 
    while (t--) solve();
}