526互联

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

发布时间 2023-10-10 10:21:24作者: xishuiw

好久没打了

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

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