首页 > 其他分享 >练习记录-cf-Educational Codeforces Round 156 (Rated for Div. 2)(A-C)

练习记录-cf-Educational Codeforces Round 156 (Rated for Div. 2)(A-C)

时间:2023-10-10 10:24:48浏览次数:54  
标签:tmp Educational Rated const sta int ll Codeforces 1.0

好久没打了

还是就出了三道 不过还好没掉分

A. Sum of Three

就是问能不能把一个数拆成三个不同的 且都不能被三整除的数

我的思路就是拆成1+2+一个大于等于4的数

如果拆了后另一个数是%3==0 那么我拆成1+4它肯定就不被整除

然后判下相同

#include<bits/stdc++.h>
#define close     std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN = 3e5+7;
const ll mod =1e9+7;
const ll inf =0x3f3f3f3f;
const ll INF =0x3f3f3f3f3f3f3f3f;
#define int ll
void solve(){
    int n;cin>>n;
    if((n-3)%3!=0&&(n-3)!=1&(n-3)!=2&&(n-3)>0){
        cout<<"Yes\n";
        cout<<"1 2 "<<n-3<<"\n";
    }
    else if((n-5)%3!=0&&(n-5)!=1&(n-5)!=4&&(n-5)>0){
        cout<<"Yes\n";
        cout<<"1 4 "<<n-5<<"\n"; 
    }
    else cout<<"No\n";
}
signed main(){
    close;
    int t;
    cin>>t;
    while(t--) 
    solve();
}
View Code

B. Fear of the Dark

问最小的半径 让两点能联通 被覆盖

分三种情况讨论 1两点都被A圆覆盖 2两点都被B圆覆盖 3两点都被覆盖的同时 两圆相切

12都很好写 写完取min

3的话 就是算两个点分别离AB圆的最小距离取最大值 再和相切的半径取最大值 

最后3和1 2取min就行了

3写错wa了一发 血亏

#include<bits/stdc++.h>
#define close     std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN = 3e5+7;
const ll mod =1e9+7;
const ll inf =0x3f3f3f3f;
const ll INF =0x3f3f3f3f3f3f3f3f;
void solve(){
    int x,y;cin>>x>>y;
    int a,b,c,d;cin>>a>>b>>c>>d;
    double ans=inf; 
    //其中一个覆盖 
    double tmp=max((a-x)*(a-x)+(b-y)*(b-y)*1.0,a*a*1.0+b*b);
    ans=min(ans,tmp);
    tmp=max((c-x)*(c-x)*1.0+(d-y)*(d-y),c*c*1.0+d*d);
    ans=min(ans,tmp);
    double tmp1=min((a-x)*(a-x)+(b-y)*(b-y)*1.0,(c-x)*(c-x)*1.0+(d-y)*(d-y));
    double tmp2=min(a*a*1.0+b*b,c*c*1.0+d*d);
    tmp=max(tmp1,tmp2);
    tmp=max(tmp,((a-c)*(a-c)*1.0+(b-d)*(b-d))/4.0);
    ans=min(ans,tmp);
    printf("%.10f\n",sqrt(ans));
}
signed main(){
    int t;cin>>t;
    while(t--)
    solve();
}
View Code

C. Decreasing String

这个就是说 它会依此删除字母 每次都会选 删除后字典序最小的字母删除 最后把删的过程的所有字符串拼到一起 询问第k位是什么

如果它问第k位是什么 我们可以很快算出 这是删了idx个字母后的第x位 我是O(n)算的 一个一个减

知道这个了之后 我们就模拟那个过程 去删掉这idx个字母 然后对这几个字母打上标记 从前往后扫字符串 扫第x个不被标记的 就好了

删字母的过程 手玩一下发现就是一个单调栈 删除从左往右第一个降序的字母最优 就写个单调栈 最后记得把栈里的都丢掉就好了

就是模拟 

#include<bits/stdc++.h>
#define close     std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN = 2e6+7;
const ll mod =1e9+7;
const ll inf =0x3f3f3f3f;
const ll INF =0x3f3f3f3f3f3f3f3f;
#define int ll
stack<pair<char,int> > sta;
int f[MAXN];
void solve(){
    string s;cin>>s;
    while(sta.size()){
        sta.pop();
    }
    int n=s.length();
    s=" "+s;
    for(int i=1;i<=n;i++) f[i]=0;
    int k;cin>>k;
    int sum=0;
    int idx;
    int least;
    for(int i=n;i>=0;i--){
        sum+=i;
        if(sum>=k){
            idx=n-i;//删这么多个 
            least=k-(sum-i);
            break;
        }
    }
    for(int i=1;i<=n&&idx;i++){
        while(sta.size()&&sta.top().first>s[i]&&idx){
                f[sta.top().second]=1;
                sta.pop();
                idx--;
        }
        sta.push({s[i],i});
    }
    while(sta.size()&&idx){
        f[sta.top().second]=1;
                sta.pop();
                idx--;
    }
    int now=0;
    for(int i=1;i<=n;i++){
        if(!f[i]) now++;
        if(now==least){
            cout<<s[i];
            break;
        }
    }
}
signed main(){
    close;
    int t;cin>>t;
    while(t--)
    solve();
}
View Code

 

标签:tmp,Educational,Rated,const,sta,int,ll,Codeforces,1.0
From: https://www.cnblogs.com/xishuiw/p/17753928.html

相关文章

  • Codeforces Round 902 (Div. 2) C. Joyboard 规律
    CodeforcesRound902(Div.2)C.Joyboard//思路:在k=1,k=2,k=3时有解//当k=1时为全0//当k=2时,若m>=n,则先是0然后为1~n,最后一位可以为n的倍数也符合,即n+m/n-1//若m<n则为1~m即m//当k=3时,只能在n+1位是第3个不同情况(大于n),且不能为n的倍数,即(m-n)-(m/n-1)//只......
  • Codeforces Round 726 (Div. 2) B. Bad Boy
    给一个\(n\timesm\)的平面,一个初始位置\((i,j)\)。需要放两个废弃物在平面上,位置为\((x_1,y_1),(x_2,y_2)\)。使得从\((i,j)\)出发,捡起两个废弃物后,回到原位置,所经过的曼哈顿距离最长。询问一组合法的\((x_1,y_1),(x_2,y_2)\)。性质:二维平面上有关的曼哈......
  • Codeforces Round 902 (Div. 2, based on COMPFEST 15 - Final Round)
    Preface难得这么好时间的CF,我直接找来队友组队练题当然比赛的过程没有三人三机,就跟平时训练一样搞了个新号三人一机的写中间因为溜去先看F了导致E题留给徐神solo因此出的偏慢,不过后面一起讨论了一下还是出了最后开F结果好家伙我和祁神双双看错题,对着假题意苦战1h最后无奈投降,......
  • CodeForces 1876D Lexichromatography
    洛谷传送门CF传送门这说明你的能力还不足以维持IM。显然balanced的充要条件是,对于每个值,染色一定是RB交替。然后一种值只会有先染红或先染蓝两种情况。然后还剩下字典序严格小于的条件。我场上的想法是枚举\(\text{LCP}\),然后推出来一个巨大麻烦做法,根本写不出来。但......
  • Codeforces Round 902 (Div. 1, based on COMPFEST 15 - Final Round) A~D
    A.HelmetsinNightLight首先注意到一个关键性质\(b_i\geq1\),这就意味着当我们花\(p\)的代价解锁了\(b_i\)最小的后,仅凭接下来的“连锁反应”就能解锁全部的点。注意到我们“连锁反应”的一定是按\(b_i\)从小到大排序后的一段前缀(因为越往后连锁代价越昂贵),找到转折点......
  • Codeforces Round 902 (Div. 2) (CF1877) B、C、D 题解
    B题目大意你要传话给\(n\)个人,每传一下话需要花费\(p\),当一个人被传话后,他可以最多传给\(a_i\)个人,每次花费\(b_i\)。问把话传给\(n\)个人的最小花费。分析首先传给第一个人只少要\(p\)下来贪心,每次让花费最小、且能够传话的人去传话。考虑建一个堆,堆内的信息是......
  • Codeforces Round 902 Div. 2 - A B C D
    目录A.GoalsofVictoryB.HelmetsinNightLightnull传送门A.GoalsofVictory对给定n-1组队伍的净得分求和取负即为最后一组队伍的净得分B.HelmetsinNightLight赛时想法假了,赛后更正对所有人按照传递花费升序排序,从小到大逐步选取先花费p为传递花费最小的居......
  • Codeforces Round #902 (Div.1)
    A注意到\(a_i\ge1\),因此我们先花\(p\)的代价买下\(b\)最小的,然后一定可以一直用当前可能的最小代价买下后续的人。不难发现这一定是最优的方案。只需要将序列排序或者用std::multiset来维护。单组数据时间复杂度\(O(n\logn)\)。https://codeforces.com/contest/1876/......
  • 【题解】CodeForces-1874/1875
    CodeForces-1875AJellyfishandUndertale一定是等待降到\(1\)或者能补满到\(a\)时才使用工具,依题意模拟即可。提交记录:Submission-CodeForcesCodeForces-1874AJellyfishandGame这种题目有点思路但是不是很会。赛时第一发写得根据奇偶性判断,\(k\)为偶数错了,然后感......
  • Codeforces Round 900 (Div. 3) E. Iva & Pav (位运算)
    CodeforcesRound900(Div.3)E.Iva&Pav//思路:10^9转换为2^32上的位,进行位运算,a[x][i]为到x为止第i位的1个数前缀和//对于与运算,如果当前i的前缀和不为r-l+1,则这一位的与运算结果为0//当找到从左往右第一个位置i为1使得k在这位为0,则与运算前缀大于k//二分查找最后一......