当前位置： 首页 > news >正文

2017-2018 ACM-ICPC Northern Eurasia (Northeastern European Regional) Contest (NEERC 17) 日常训练...

news 来源：原创 2024/5/20 23:50:29

A - Archery Tournament

题目大意：按时间顺序出现靶子和射击一个位置，靶子的圆心为(x, y）半径为r，即圆与x轴相切，靶子不会重叠，靶子被击中后消失，

每次射击找出哪个靶子被射中，或者没有射中靶子。

 

思路：关键点在于，圆都与x轴相切，那么我们能发现，如果射击在(x, y) 这个点，包含它的圆只可能是它左边第一个直径>= y的圆c1，

或者是它右边第一个直径 >=y 的圆c2，因为在c1 和 c2之间的圆不可能覆盖到(x, y)， 因为它们的直径小于y，在c1左边和c2右边的圆

通过画图我们也能得出不肯能包含(x, y)，那么每次射击我们只需要check两个圆就好了。

找圆的过程能用线段树维护，加入一个圆就在线段树对应的x的位置的值变成2*r，然后通过二分用线段树找圆，最后判一下是否在圆内。

#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define pii pair<int, int>

using namespace std;

const int N = 2e5 + 7;
const int M = 1e5 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 +7;


int n, tot, mx[N << 2], X[N], hs[N];

struct Qus {
    int op, x, y;
} qus[N];

void update(int pos, int v, int l, int r, int rt) {
    if(l == r) {
        mx[rt] = v;
        return;
    }

    int mid = l + r >> 1;
    if(pos <= mid) update(pos, v, l, mid, rt << 1);
    else update(pos, v, mid + 1, r, rt << 1 | 1);

    mx[rt] = max(mx[rt << 1], mx[rt << 1 | 1]);
}

int getMx(int L, int R, int l, int r, int rt) {
    if(l >= L && r <= R) return mx[rt];

    int mid = l + r >> 1, ans = 0;

    if(L <= mid) ans = max(ans, getMx(L, R, l, mid, rt << 1));
    if(R > mid) ans = max(ans, getMx(L, R, mid + 1, r, rt << 1 | 1));
    return ans;
}

bool check(int x, int y, int id) {
    LL dis1 = 1ll * qus[id].y * qus[id].y;
    LL dis2 = 1ll * (x - qus[id].x) * (x - qus[id].x) + 1ll * (y - qus[id].y) * (y - qus[id].y);
    return dis1 > dis2;
}

int main() {

    scanf("%d", &n);

    for(int i = 1; i <= n; i++) {
        scanf("%d%d%d", &qus[i].op, &qus[i].x, &qus[i].y);
        hs[++tot] = qus[i].x;
    }

    sort(hs + 1, hs + 1 + tot);
    tot = unique(hs + 1, hs + 1 + tot) - hs - 1;


    for(int i = 1; i <= n; i++) {
        int op = qus[i].op, x = qus[i].x, y = qus[i].y;

        int pos = lower_bound(hs + 1, hs + 1 + tot, x) - hs;

        if(op == 1) {
            X[pos] = i;
            update(pos, 2 * y, 1, tot, 1);
        } else {
            int l = 1, r = pos, ret = -1;
            while(l <= r) {
                int mid = l + r >> 1;
                if(getMx(mid, pos, 1, tot, 1) >= y) ret = mid, l = mid + 1;
                else r = mid - 1;
            }

            if(ret != -1 && check(x, y, X[ret])) {
                printf("%d\n", X[ret]);
                update(ret, 0, 1, tot, 1);
                continue;
            }

            l = pos, r = tot, ret = -1;
            while(l <= r) {
                int mid = l + r >> 1;
                if(getMx(pos, mid, 1, tot, 1) >= y) ret = mid, r = mid - 1;
                else l = mid + 1;
            }

            if(ret != -1 && check(x, y, X[ret])) {
                printf("%d\n", X[ret]);
                update(ret, 0, 1, tot, 1);
                continue;
            }

            puts("-1");

        }
    }
    return 0;
}
View Code

 

B - Box

题目大意：问长宽高为a, b, c的立方体，能不能用n * m的纸折出来。

思路：暴力枚举判断。。

#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define pii pair<int, int>

using namespace std;

const int N = 1000 + 7;
const int M = 1e5 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 +7;


int n, m, a[3], id[3];

bool check(int x, int y) {
    if(x <= n && y <= m) return true;
    if(x <= m && y <= n) return true;
    return false;
}
int main() {
    scanf("%d%d%d", &a[0], &a[1], &a[2]);
    id[0] = 0, id[1] = 1, id[2] = 2;
    scanf("%d%d", &n, &m);

    sort(a, a + 3);

    do {
        int x = a[id[0]], y = a[id[1]], z = a[id[2]];

        if(check(2 * z + x, 2 * y + 2 * z)) {
            puts("Yes");
            return 0;
        }

        if(check(x + y + z, 2 * x + y + z)) {
            puts("Yes");
            return 0;
        }

        if(check(2 * z + x, x + 2 * y + z)) {
            puts("Yes");
            return 0;
        }

        if(check(3 * y + x + z, x + z)) {
            puts("Yes");
            return 0;
        }
    } while(next_permutation(id, id + 3));
    puts("No");
    return 0;
}


/*
2z + x
2y + 2z

x + y + z
2x + y + z

2z + x
x + 2y + z


*/
View Code

 

C - Connections

题目大意：给你一个 n 个点 m (m >= 2 * n)条边的有向图，且原图为一个强连通分量，要求你选出2 * n条边，其他的删掉仍然是一个

强连通分量。

思路：比赛的时候我没想到，队友想出来的。。 用1号点跑一遍图，建反边用1号点再跑一次就好了。 应该挺听容易想到的，题目说2 * n

应该想到由两个树组成。

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define ll long long
#define vi vector<int>
#define mod 1000000007
#define ld long double
#define C 0.5772156649
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#define pil pair<int,ll>
#define pli pair<ll,int>
#define pii pair<int,int>
#define cd complex<double>
#define ull unsigned long long
#define base 1000000000000000000
#define fio ios::sync_with_stdio(false);cin.tie(0)

using namespace std;

const double eps=1e-6;
const int N=100000+10,maxn=500000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f;

vector<pair<int,int> >v[N],rev[N];
pii p[N];
bool vis[N],used[N];
void dfs(int u)
{
    vis[u]=1;
    for(int i=0;i<v[u].size();i++)
    {
        int x=v[u][i].fi;
        if(!vis[x])
        {
            used[v[u][i].se]=1;
            dfs(x);
        }
    }
}
void dfs1(int u)
{
    vis[u]=1;
    for(int i=0;i<rev[u].size();i++)
    {
        int x=rev[u][i].fi;
        if(!vis[x])
        {
            used[rev[u][i].se]=1;
            dfs1(x);
        }
    }
}
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)v[i].clear(),rev[i].clear();
        for(int i=0;i<m;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            v[x].pb(mp(y,i));
            rev[y].pb(mp(x,i));
            p[i]=mp(x,y);
            used[i]=0;
        }
        memset(vis,0,sizeof vis);
        dfs(1);
        memset(vis,0,sizeof vis);
        dfs1(1);
        int sum=0;
        for(int i=0;i<m;i++)
            if(used[i])
                sum++;
        int now=2*n-sum;
        for(int i=0;i<m;i++)
        {
            if(!used[i]&&now)
            {
                now--;
                used[i]=1;
            }
        }
        for(int i=0;i<m;i++)
            if(!used[i])
                printf("%d %d\n",p[i].fi,p[i].se);
    }
    return 0;
}
/********************

********************/
View Code

 

D - Designing the Toy

题目大意：给你三视图的每个面能看见的方块个数a, b, c，然后构造出这样的图形。

思路：一起想了挺久的，三维立体很难实现，我们就考虑把所有点放一个面里面，构成图形的个数就是max(a, b, c)，

斜着放三面个数都加一，横着放两面个数加一，填补空缺一个面加一，构造一下。细节挺多的。。。

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define ll long long
#define vi vector<int>
#define mod 1000000007
#define ld long double
#define C 0.5772156649
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#define pil pair<int,ll>
#define pli pair<ll,int>
#define pii pair<int,int>
#define cd complex<double>
#define ull unsigned long long
#define base 1000000000000000000
#define fio ios::sync_with_stdio(false);cin.tie(0)

using namespace std;

const double eps=1e-6;
const int N=100+10,maxn=500000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f;

int a[3], b[3];

struct point{
    int x,y,z;
};
int ok[N][N];
void solve(int x,int y,int z){
    vector<point> v;
    vector<point> ans;
    for(int i=0;i<x;i++)
        v.pb({0,i,i});
    for(int i=x;i<y;i++)
        v.pb({0,x-1,i});
    for(int i=0;i<v.size();i++)ok[v[i].y][v[i].z]=1;
    int now=z-y;
    for(int i=0;i<x;i++)
    {
        for(int j=0;j<y;j++)
        {
            if(!ok[i][j]&&now)
            {
                v.pb({0,i,j});
                ok[i][j]=1;
                now--;
            }
        }
    }
    if(now!=0){puts("-1");return ;}
    if(b[0]==a[0]&&b[1]==a[2]&&b[2]==a[1])
    {
        for(int i=0;i<v.size();i++)swap(v[i].x,v[i].y);
    }
    else if(b[0]==a[1]&&b[1]==a[0]&&b[2]==a[2])
    {
        for(int i=0;i<v.size();i++)swap(v[i].y,v[i].z);
    }
    else if(b[0]==a[1]&&b[1]==a[2]&&b[2]==a[0])
    {
        for(int i=0;i<v.size();i++)
        {
            swap(v[i].x,v[i].z);
            swap(v[i].y,v[i].z);
        }
    }
    else if(b[0]==a[2]&&b[1]==a[0]&&b[2]==a[1])
    {
        for(int i=0;i<v.size();i++)
        {
            swap(v[i].x,v[i].y);
            swap(v[i].y,v[i].z);
        }
    }
    else if(b[0]==a[2]&&b[1]==a[1]&&b[2]==a[0])
    {
        for(int i=0;i<v.size();i++)
        {
            swap(v[i].x,v[i].z);
        }
    }
    printf("%d\n",v.size());
    for(int i=0;i<v.size();i++)
        printf("%d %d %d\n",v[i].x,v[i].y,v[i].z);
}
int main(){

    for(int i = 0; i < 3; i++) {
        scanf("%d", &a[i]);
        b[i] = a[i];
    }
    sort(a, a + 3);
    solve(a[0],a[1],a[2]);
    return 0;
}
/********************

********************/
View Code

 

E - Easy Quest

队友写的水题，不知道啥意思。

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define ll long long
#define vi vector<int>
#define mod 1000000007
#define ld long double
#define C 0.5772156649
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#define pil pair<int,ll>
#define pli pair<ll,int>
#define pii pair<int,int>
#define cd complex<double>
#define ull unsigned long long
#define base 1000000000000000000
#define fio ios::sync_with_stdio(false);cin.tie(0)

using namespace std;

const double eps=1e-6;
const int N=20000+10,maxn=500000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f;

multiset<int>p;
int a[N];
int ans[N];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1,x;i<=n;i++)
    {
        scanf("%d",&x);
        if(x>0)a[x]++;
        else if(x==0)p.insert(i);
        else
        {
            if(a[-x]>0)a[-x]--;
            else if(p.size()!=0)
            {
//                printf("--%d\n",*p.begin());
                ans[*p.begin()]=-x;
                p.erase(p.begin());
            }
            else return 0*puts("No");
        }
    }
    while(p.size()!=0)ans[*p.begin()]=1,p.erase(p.begin());
    puts("Yes");
    for(int i=1;i<=n;i++)
        if(ans[i]!=0)
            printf("%d ",ans[i]);
    puts("");
    return 0;
}
/********************

********************/
View Code

 

补题****************************************************************************

F - The Final Level

题目大意，有若干个L形连通块，两边长为n，有一个重叠， 问你最少用几个能把(0 , 0)和（a, b）连起来， L形的物件不能有交叉。

 

思路：分类讨论贪心，分为一下几种情况。

1.a - x < n && b - y < n   用一个L就能连通

2.a - x > n && b - y > n   贪心地继续连在前一个的末端

3.a - x > n && b - y < n   y这维不用贪了，贪x这维。

4.与3相反。

#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define pii pair<int, int>

using namespace std;

const int N = 2e5 + 7;
const int M = 1e5 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 +7;

    
int T;
LL a, b, n;
bool flag = false;
vector<pair<pair<LL, LL>, pair<LL, LL> > > ans;

void dfs(LL x, LL y) {
    if(a - x < n && b - y < n) {
        if(!flag) {
            int x1 = x - (x + n - 1 - a);
            int y1 = y;
            int x2 = a;
            int y2 = y + n - 1;
            ans.push_back(mk(mk(x2, y2), mk(x1, y1)));
            return;
        } else {
            int x2 = x;
            int y2 = y - (y + n - 1 - b);
            int x1 = x + n - 1;
            int y1 = b;
            ans.push_back(mk(mk(x2, y2), mk(x1, y1)));
        }
        return;
    }

    if(b - y < n) {
        ans.push_back(mk(mk(x + n - 1, y - n + 1), mk(x, y)));
        flag = true;
        dfs(x + n, y);
        return;
    }

    if(a - x < n) {
        ans.push_back(mk(mk(x, y), mk(x - n + 1, y + n - 1)));
        flag = false;
        dfs(x, y + n);
        return;
    }


    if(a - x >= n && b - y >= n) {
        ans.push_back(mk(mk(x + n - 1, y + n - 1), mk(x, y)));
        if(abs(a - x) >= abs(b - y)) flag = true, dfs(x + n, y + n - 1);
        else flag = false, dfs(x + n - 1, y + n);
        return;
    }

}

int main() {
    scanf("%d", &T);
    while(T--) {
        ans.clear();
        scanf("%lld%lld%lld", &a, &b, &n);
        int x = a, y = b;
        if(a < 0) a = -a;
        if(b < 0) b = -b;

        dfs(0, 0);

        for(int i = 0; i < ans.size(); i++) {
            if(a != x) ans[i].fi.fi = -ans[i].fi.fi, ans[i].se.fi = -ans[i].se.fi;
            if(b != y) ans[i].fi.se = -ans[i].fi.se, ans[i].se.se = -ans[i].se.se;
        }

        printf("%d\n", (int) ans.size());

        for(int i = 0; i < ans.size(); i++) {
            printf("%lld %lld %lld %lld\n", ans[i].fi.fi, ans[i].fi.se, ans[i].se.fi, ans[i].se.se);
        }
    }
    return 0;
}


/*
1
4 1 3
*/
View Code

 

转载于:https://www.cnblogs.com/CJLHY/p/9291194.html

相关文章：

  • 2.6map映照容器
  • mysql_fetch_row ()出现段错误_高能：燕郊出现虚假地铁站公示牌，很多人信以为真...
  • marquee标签详解
  • arduino编程语言教程_Arduino语言编写(初学)
  • vue方法传值到data_vue的六种传值方式
  • 华为交换机关闭网口_华为交换机如何关闭网络端口号
  • 马逊s3云存储接口_云原生在京东丨如何在Kubernetes上部署有状态的云原生应用？（下）...
  • 文本处理工具之grup 正则表达式
  • ak47怎么得 rust_UZI直播一波操作火到国外，Reddit网友：这不是乌兹，这是AK47
  • [转] 版本二 写代码的小女孩
  • 芯片工程师成长之路_一个FPGA工程师的成长之路
  • bzoj 3489: A simple rmq problem
  • stlinkv2stm32接线_ST-LINK/V2是怎么和STM32单片机连接的
  • 第三十九篇 入门机器学习——Numpy.array的基础操作——合并与分割向量和矩阵...
  • pdf做成翻页电子书_如何一分钟将PDF制作成电子书？这个热门电子书刊制作软件推荐给你！...
  • 【node学习】协程
  • 【跃迁之路】【585天】程序员高效学习方法论探索系列（实验阶段342-2018.09.13）...
  • 5、React组件事件详解
  • canvas绘制圆角头像
  • CAP 一致性协议及应用解析
  • exif信息对照
  • extjs4学习之配置
  • javascript数组去重/查找/插入/删除
  • Java读取Properties文件的六种方法
  • LeetCode29.两数相除 JavaScript
  • Nodejs和JavaWeb协助开发
  • Phpstorm怎样批量删除空行？
  • React-生命周期杂记
  • spring学习第二天
  • Synchronized 关键字使用、底层原理、JDK1.6 之后的底层优化以及 和ReenTrantLock 的对比...
  • vue：响应原理
  • Webpack 4x 之路 （ 四 ）
  • 简单基于spring的redis配置(单机和集群模式)
  • 容器服务kubernetes弹性伸缩高级用法
  • 鱼骨图 - 如何绘制？
  • 再次简单明了总结flex布局，一看就懂...
  • 【运维趟坑回忆录 开篇】初入初创, 一脸懵
  • 格斗健身潮牌24KiCK获近千万Pre-A轮融资，用户留存高达9个月 ...
  • ​插件化DPI在商用WIFI中的价值
  • #{} 和 ${}区别
  • #《AI中文版》V3 第 1 章 概述
  • (ctrl.obj) : error LNK2038: 检测到“RuntimeLibrary”的不匹配项: 值“MDd_DynamicDebug”不匹配值“
  • （附源码）php新闻发布平台 毕业设计 141646
  • （附源码）springboot码头作业管理系统 毕业设计 341654
  • （亲测）设​置​m​y​e​c​l​i​p​s​e​打​开​默​认​工​作​空​间...
  • (求助)用傲游上csdn博客时标签栏和网址栏一直显示袁萌 的头像
  • （四）Linux Shell编程——输入输出重定向
  • （转）fock函数详解
  • （转）JVM内存分配 -Xms128m -Xmx512m -XX:PermSize=128m -XX:MaxPermSize=512m
  • **Java有哪些悲观锁的实现_乐观锁、悲观锁、Redis分布式锁和Zookeeper分布式锁的实现以及流程原理...
  • .NET Core中Emit的使用
  • .NET/C# 使用 SpanT 为字符串处理提升性能
  • .NET/MSBuild 中的发布路径在哪里呢？如何在扩展编译的时候修改发布路径中的文件呢？
  • .NET学习教程二——.net基础定义+VS常用设置
  • /usr/bin/perl:bad interpreter:No such file or directory 的解决办法