首页 > 其他分享 >EPIC Institute of Technology Round August 2024 (Div. 1 + Div. 2) 补题记录(A~D1,E)

EPIC Institute of Technology Round August 2024 (Div. 1 + Div. 2) 补题记录(A~D1,E)

时间:2024-08-12 10:49:06浏览次数:13  
标签:August int cin long back 补题 Div define 二元

A

容易发现答案为 \(\min(n,k)\min(m,k)\)。

#include<bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int N=1000100;
int a[N];
signed main(){
    int T;
    cin>>T;
    while(T--){
        int n,m,k;cin>>n>>m>>k;
        n=min(n,k),m=min(m,k);
        cout<<n*m<<'\n';
    }
    return 0;
} // main

B

容易发现 Alice 如果想要赢必然一直从左或者右端口开始删除元素。若对于 Alice 两种选择方案 Bob 都能够获胜那么 Bob 就必胜,反之 Bob 必败。用一个双端队列维护 Bob 当前所有的元素即可,时间复杂度为 \(O(n)\)。

#include<bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int N=1000100;
int a[N],b[N];
signed main(){
    int T;
    cin>>T;
    while(T--){
        int n;cin>>n;
        for(int i=1;i<=n;++i)cin>>a[i];
        for(int i=1;i<=n;++i)cin>>b[i];
        deque<int>t;for(int i=1;i<=n;++i)t.push_back(b[i]);
        int ok=1;
        for(int i=1;i<=n;++i){
            if(a[i]==t.front())t.pop_front();
            else if(a[i]==t.back())t.pop_back();
            else{ok=0;break;}
        }
        reverse(a+1,a+n+1);
        for(int i=1;i<=n;++i)t.push_back(b[i]);
        for(int i=1;i<=n;++i){
            if(a[i]==t.front())t.pop_front();
            else if(a[i]==t.back())t.pop_back();
            else{ok=0;break;}
        }
        if(!ok)cout<<"Alice\n";
        else cout<<"Bob\n";
    }
    return 0;
} // main

C

谢谢你 C。考虑对于经过两点的直线 \(L\) 经过 \((x_1,y_1)\) 和 \((x_2,y_2)\),对于一个圆心为 \((x_0,y_0)\) 的圆,若在某一个时刻 \(r\) 满足半径为 \(r\) 的圆和直线 \(L\) 距离 \((x_1,y_1)\) \(r\) 个单位长度的地方相交,则不可以经过。问题是如何判定这一点。

pApM9Qf.md.png

容易发现若 C –> D 的路径上 B 点和 A 点所对应的圆产生交点,则连接 \(AC\) 之后根据三角形三边关系得到 \(AD<CD\),也就是从 \(C\) 走到 \(D\) 要花费的时间比圆半径从 \(A\) 扩展到 \(D\) 所需要的时间要长。

于是问题就十分简单了,只需要判断到达终点的时候是否有一个圆已经将终点覆盖即可。时间复杂度为 \(O(n)\)。

#include<bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int N=331080;
int x[N],y[N];
int get(int a,int b,int c,int d){
    return (c-a)*(c-a)+(d-b)*(d-b);
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin>>T;
    while(T--){
        int n;cin>>n;
        for(int i=1;i<=n;++i)cin>>x[i]>>y[i];
        int xs,ys,xt,yt;
        cin>>xs>>ys>>xt>>yt;
        int ok=1;
        int len=get(xs,ys,xt,yt);
        for(int i=1;i<=n;++i){
            int len1=get(x[i],y[i],xt,yt);;
            if(len1<=len){ok=0;break;}
        }
        if(ok)cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
} // main
/*
1
1
999999998 1000000000
999999999 999999999 1 1
*/

D1

考虑维护 \(2\)、\(3\) 两个结点所对应的子树的结点编号的和,以及每一层树上结点编号的和,将其和真正的答案对比若相同就合法否则就不合法。时间复杂度为 \(O(n\log n)\),需要使用 ds 维护。正确性显然。代码还没调出来。

E

这题还挺有意思的。考虑挖掘题目所求答案的性质,可以发现对于两个相邻的位置 \(i\),\(i+1\) 所对应的连续二元组,若两个连续二元组所对应的值不同且第一个二元组的元素个数 \(\le\) 第二个二元组的元素个数那么第一个二元组的元素一定会被第二个二元组全部消除,随后第二个二元组的元素数量减去第一个二元组的元素数量。因此发现这个东西十分类似于单调栈。直接用单调栈维护一下当前的递减个数二元组即可。当前所需要花费的最长时间即为栈底元素最多的二元组的元素个数。

时间复杂度为 \(O(n)\)。感觉这个题比 C 和 D 都要简单啊。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=500100;
int a[N],b[N],res[N];
signed main(){
    int T;cin>>T;
    while(T--){
        int n;cin>>n;
        for(int i=1;i<=n;++i)cin>>a[i]>>b[i];
        deque<int> stk;
        int remain=0;
        for(int i=1;i<=n;++i){
            while(stk.size()){
                if(b[i]!=b[stk.back()]){
                    if(a[i]>a[stk.back()])remain=a[stk.back()],stk.pop_back();
                    else break;
                }else{
                    a[i]+=a[stk.back()]-remain;
                    stk.pop_back();
                    remain=0;
                }
            }
            stk.push_back(i);
            cout<<a[stk.front()]<<' ';
        }
        cout<<'\n';
    }
    return 0;
}

标签:August,int,cin,long,back,补题,Div,define,二元
From: https://www.cnblogs.com/yhbqwq/p/18354484

相关文章

  • Codeforces Round 963 (Div. 2)
    Preface有懒狗上周日的比赛拖到这周日才写博客,我不说是谁这场比赛的时候因为C数组没开两倍卡了1h最后写对拍才看出来,直接心态爆炸导致D没写完掉大分A.QuestionMarks签到#include<cstdio>#include<iostream>#include<utility>#include<vector>#include<cstring>......
  • CF1998 div2 & abc366
    1CF1.1B被诈骗了。我们的构造要向“每个区间只有1个数不一样考虑”。1.2C比较难。但是出的好。注意到如果我们不删除中位数这个位置的数,那么那个数是一定的。所以我们可以把\(k\)加到最大的可以加的数上,统计答案就在这个数,然后二分算中位数即可。其它策略?我们可不......
  • Codeforces Round 965 (Div. 2) 题解
    个人难度顺序:A<D<B<C<E。A.FindKDistinctPointswithFixedCenter如果\(k\)是偶数,构造\((x_c+i,yc+i)\),其中\(-\frac{k}{2}\lei\le\frac{k}{2}\)。对于\(k\)是奇数,先加一个点\((xc,yc)\),然后就变成偶数的情况了。B.MinimizeEqualSumSubarr......
  • Codeforces Round 965 (Div. 2) 补题记录(A,B,D,E1)
    speedforcesagain~A<E1<<B<D<<CA若\(k\equiv1(\bmod2)\),则构造\((x,y)\),\((x-1,y)\),\((x+1,y)\),\((x-2,y)\),\((x+2,y)\),\(\ldots\)。否则构造\((x-1,y)\),\((x+1,y)\),\((x-2,y)\),\((x+2,y)\),\(\ldots\)。#pra......
  • Codeforces Round 964 (Div. 4)
    这场的题不错,就是一直在inqueue......
  • 8.9 线段树板子+三分补题+三维的bfs
    nowcoder训练区间线段树板子题,我们只需要把区间每一个点设置成1,然后修改的时候直接改点,然后查区间就行线段树维护最大字段和/01串最大连续1的个数模板题。把白色和黑色看成1/0两个数就行了。#include<bits/stdc++.h>usingnamespacestd;usingi64=longlon......
  • div-固定在页面中间,不被其他元素覆盖
    最开始设置的子元素D是text-align:center,子元素C的内容过长的时候,会发现子元素D不在页面正中了所以需要把子元素D设置成固定中间,把子元素D设置成固定中间后,发现元素B把子元素D给覆盖了一部分,所以需要在父元素A和元素B之间加一个空的div,给div设置高度后,父元素A和元素B之间的距离......
  • 2024-08-07 多校联合暑假训练赛第四场 补题+分析
    A.小盒子题意+思路:题意其实概括的不是非常准确简要题意:圆盒有n个格子,格子自带ai个棋子.是否通过任意起点通过顺时针-1,-2,...,-n的操作使得圆盒中所有所有的棋子都为0思路:贪心对于所有棋子通过顺时针操作的时候每一次都是(1+n)*n/2次是一个等差公式所以......
  • Codeforces Round 964 (Div. 4)
    知识点1.对于两个数字,一个乘n,一个除以n,可以理解为n进制下的这个数乘10和除10。比如E题用这个知识点就可以很快的解决问题。题解A.A+BAgain?#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;voidsolve(){ strings; cin>>s; cout<<s[0]-'0'+s[1]-......
  • Codeforces Round 964 (Div. 4)
    CodeforcesRound964(Div.4)A送分B大意:两个人两张牌随机翻求a翻出来的牌比b大的可能#include<cstdio>#include<cmath>#include<algorithm>#include<iostream>#include<cstring>#include<vector>#defineepemplace_backusingnamespace......