首页 > 其他分享 >Educational Codeforces Round 156 (Rated for Div. 2) A-E

Educational Codeforces Round 156 (Rated for Div. 2) A-E

时间：2023-10-12 19:55:24浏览次数：37  
标签：Educational Rated 156 int pos while ch ans define

A题签到题 分余1 余2 余0讨论 

#include<bits/stdc++.h>
using namespace std ;
#define maxn 400100
#define int long long
int read(){
    int ans = 0 , f = 1 ; char ch = getchar() ;
    while ( !isdigit(ch) ){ if( ch == '-' ) f = -1 ; ch = getchar() ; }
    while ( isdigit(ch) ) ans = (ans * 10) + (ch ^ '0') , ch = getchar() ;
    return ans * f ;
}
#define fer(i , a , b , c) for(int i = a ; i <= b ; i+= c)
#define fe(i , a, b , c) for(int i = a ; i >= b ; i -= c)
int t = read() ;  
signed main(){
    while(t--){
        int n = read() ; 
        bool flag = 1 ; 
        int x , y , z ; 
        if(n % 3 == 1){
            x = 1 , y = 4 ; 
        }
        else if(n % 3 == 2){
            x = 2 , y = 5  ; 
        }
        else {
            x = 1 , y = 4 ; 
        }
        z = n - x - y ; 
        if(z == x || z == y || z <= 0 ){
            flag = 0 ; 
        }
        if(flag){
            printf("YES\n%lld %lld %lld\n" , x , y , z) ; 
        }
        else printf("NO\n") ; 
    }
    return 0 ;
 }

B 二分一下 分别考虑先从A到B 和从B到A  二分注意一下精度 eps建议开到1e-12

#include<bits/stdc++.h>
using namespace std ;
#define maxn 400100
#define int long long
int read(){
    int ans = 0 , f = 1 ; char ch = getchar() ;
    while ( !isdigit(ch) ){ if( ch == '-' ) f = -1 ; ch = getchar() ; }
    while ( isdigit(ch) ) ans = (ans * 10) + (ch ^ '0') , ch = getchar() ;
    return ans * f ;
}
#define fer(i , a , b , c) for(int i = a ; i <= b ; i+= c)
#define fe(i , a, b , c) for(int i = a ; i >= b ; i -= c)
#define ddd double 
int t = read() ;  
ddd px , py , ax , ay , bx , by ; 
bool check(ddd x){
    if(sqrt(pow((ax - px) , 2) + pow(ay - py , 2) ) <= x) return 1 ; 
    if(sqrt(pow((bx - px) , 2) + pow(by - py , 2)) > x) return 0 ; 
    if(2.0 * x >= sqrt(pow((bx - ax) , 2) + pow(by - ay , 2))) return 1 ; 
    return 0 ; 
}
signed main(){
    while(t--){
        scanf("%lf%lf%lf%lf%lf%lf" , &px , &py , &ax , &ay , &bx , &by) ; 
        double l = sqrt(ax * ax + ay * ay) , r = 100000 ; 
        double eps = 1e-12 ; 
        double ans1 , ans2 ; 
        while(l + eps <= r){
            double mid = (l + r) / 2.0 ; 
            if(check(mid)){
                ans1 = mid , r = mid - eps ;
            } 
            else l = mid + eps ; 
        }
        swap(ax , bx) ; 
        swap(ay , by) ; 
        l = sqrt(ax * ax + ay * ay) , r = 100000 ; 
        eps = 1e-12 ; 
        while(l + eps <= r){
            double mid = (l + r) / 2.0 ; 
            if(check(mid)){
                ans2 = mid , r = mid - eps ;
            } 
            else l = mid + eps ; 
        }
        printf("%.10lf\n" , min(ans1 , ans2))  ; 
    }
    return 0 ;
 }

C 手玩之后发现每次会删除第一个s[i] > s[i+1] 的位置 所以这其实是一个单调栈  把每次删除的位置处理出来就行 

#include<bits/stdc++.h>
using namespace std ;
#define maxn 1000100
#define int long long
int read(){
    int ans = 0 , f = 1 ; char ch = getchar() ;
    while ( !isdigit(ch) ){ if( ch == '-' ) f = -1 ; ch = getchar() ; }
    while ( isdigit(ch) ) ans = (ans * 10) + (ch ^ '0') , ch = getchar() ;
    return ans * f ;
}
#define fer(i , a , b , c) for(int i = a ; i <= b ; i+= c)
#define fe(i , a, b , c) for(int i = a ; i >= b ; i -= c)
int t = read() ;  
char in[maxn] , a[maxn] ; 
int minnum , minpos ,num[maxn] ;  
int pre[maxn] ; 
signed main(){
    while(t--){
        scanf("%s" , in + 1) ; int n = strlen(in+ 1) ;  
        minnum = 9999 ; int cnt = 0 ; 
        for(int i = 1 ; i <= n ; i++){
            pre[i] = n ; 
        }
        deque<int> temp ; 
        for(int i = 1 ; i <= n ; i++){
            a[i] = in[i] - 'a'+ 1 ; 
        }
        temp.push_back(1) ; 
        for(int i = 2 ; i <= n ; i++){
            while(temp.size() && a[temp.back()] > a[i]){
                num[temp.back()] = ++cnt ; 
                temp.pop_back() ; 
            }
            temp.push_back(i) ; 
        }
        while(temp.size()){
            num[temp.back()] = ++cnt  ; 
            temp.pop_back() ; 
        }
//        printf("minnum : %lld minpos : %lld \n" , minnum , minpos) ;
        int l = 1 , r = n ; 
        int mubiao ; 
        int pos = read() ; 
        while(l <= r){
            int mid = (l + r) >> 1 ; 
            if((n + n - mid + 1) * mid / 2 >= pos) mubiao = mid , r = mid - 1 ; 
            else l = mid + 1 ;
        }
        mubiao-- ; 
        pos -= (2 * n - mubiao + 1) * mubiao / 2 ; 
//        printf("mubiao : %lld pos : %lld \n" , mubiao , pos) ; 
        vector<int> ans ; 
        for(int i = 1 ; i <= n ; i++){
//            printf("num : %lld \n" , num[i]) ; 
            if(num[i] > mubiao)
                ans.push_back(i) ; 
        }
        printf("%c" , in[ans[pos-1]]) ; 
    }
    return 0 ;
 }

D 考试的时候打表发现其实就是问号减一的下标之一 相乘 
但其实也很好理解 考虑前面放了 x个数 如果是？的话  我们就有大概x-2种方法插入 所以我们只关心？即可 

#include<bits/stdc++.h>
using namespace std ;
#define maxn 400100
#define int long long
int read(){
    int ans = 0 , f = 1 ; char ch = getchar() ;
    while ( !isdigit(ch) ){ if( ch == '-' ) f = -1 ; ch = getchar() ; }
    while ( isdigit(ch) ) ans = (ans * 10) + (ch ^ '0') , ch = getchar() ;
    return ans * f ;
}
#define fer(i , a , b , c) for(int i = a ; i <= b ; i+= c)
#define fe(i , a, b , c) for(int i = a ; i >= b ; i -= c)
int t = 1 ;  
char in[maxn] ; 
set<int> s ; 
const int mod = 998244353 ; 
int ksm(int a , int b){
    int sum = 1 ; 
    while(b){
        if(b & 1) sum = sum * a  %mod;
        a = a * a % mod ; 
        b >>= 1 ;
    }
    return sum ; 
}
signed main(){
    while(t--){
        int n = read() , m = read() ; 
        cin >> in + 1 ; 
        int ans = 1 ; 
        bool flag = 1 ; 
        for(int i = 2 ; i < n ; i++){
            if(in[i] == '?'){
                ans = ans * (i - 1) % mod ; 
            }
        }
        if(in[1] == '?')
            flag = 0 ; 
        if(flag){
            printf("%lld\n" , ans) ; 
        }
        else printf("0\n") ; 
        while(m--){
            int pos = read() ; char ch ; 
            cin >> ch ; 
            if(pos == 1){
                in[pos] = ch ; 
                if(in[pos] != '?'){
                    flag = 1;
                }
                else flag = 0 ; 
            }
            else {
                if(in[pos] == '?'){
                    ans = ans * ksm(pos - 1 , mod - 2) % mod ; 
                }
                in[pos] = ch ; 
                if(in[pos] == '?')
                    ans = ans * (pos - 1) % mod ; 
            }
//            printf("%lld -----\n" , ans) ; 
            if(flag){
                printf("%lld\n" , ans) ; 
            }
            else printf("0\n") ; 
        }
    }
    return 0 ;
 }

E 考虑对于每一个project来说 其实我们选择的是排序之后连续的一段 因此我们可以计算每个project从哪个开始选的时候选出的这一段出来 然后看到m是20 一个状压dp套上去转移就可以了 

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
using LL = long long;

int main(){

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int n, m;
    cin >> n >> m;
    if (n < m){
        cout << "NO" << '\n';
        return 0;
    }
    vector<int> a(n), b(m);
    vector<int> id(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
        id[i] = i;
    }
    for(int i = 0; i < m; i++) cin >> b[i];
    sort(id.begin(), id.end(), [&](int x, int y){
        return a[x] > a[y];
    });
    const int INF = 1e9;

    vector<vector<int> > nxt(m, vector<int>(n, INF));
    for(int i = 0; i < m; i++){
        for(int j = 0, k = 0; j < n; j++){
            while(k < n && 1LL * a[id[k]] * (k - j + 1) < b[i]) k++;
            if (k == n) break;
            nxt[i][j] = k;
        }
    }
    vector<int> dp(1 << m, INF), pre(1 << m);
    dp[0] = 0;
    for(int i = 0; i < 1 << m; i++){
        if (dp[i] >= n) continue;
        for(int j = 0; j < m; j++){
            if (i >> j & 1) continue;
            if (nxt[j][dp[i]] > INF / 2) continue;
            if (nxt[j][dp[i]] + 1 < dp[i | (1 << j)]){
                dp[i | (1 << j)] = nxt[j][dp[i]] + 1;
                pre[i | (1 << j)] = j;
            }
        }
    }
    if (dp[(1 << m) - 1] > INF / 2){
        cout << "NO" << '\n';
        return 0;
    }
    vector<vector<int> > ans(m);
    int state = (1 << m) - 1;
    for(int i = 0; i < m; i++){
        int last = dp[state];
        int cur = pre[state];
        state ^= (1 << cur);
        for(int j = dp[state]; j < last; j++){
            ans[cur].push_back(id[j]);
        }
    }
    cout << "YES" << '\n';
    for(auto &v : ans){
        cout << v.size();
        for(auto x : v){
            cout << ' ' << x + 1;
        }
        cout << '\n';
    }

}

 

标签：Educational,Rated,156,int,pos,while,ch,ans,define
From： https://www.cnblogs.com/Vellichor/p/17760420.html

相关文章

  • Educational Codeforces Round 156 A-D
    A.SumofThree思路1：1.把数拆成1，2，n-32.如果（n-3）%3==0,那么拆成1,4,n-5，可证明n-3如果可被3整除，那么再左移两位一定除不尽思路2：1.如果n是奇数，那么可取一个数为2，其他两数为相邻数，如果两数其中一位被整除，那么两者往外走2.如果n为偶，那么可取一个数为1，同理上点击查看代码#inclu......
  • Educational Codeforces Round 156 (Rated for Div. 2)
    Preface沉迷Galgame不打CF懒狗闪总出列！这场在大物课上口胡了前四个题，回去写了也都很顺，然后E题本来做不来的，看了眼昨天校队群里的消息就会做了F题什么东西直接弃A.SumofThree当\(n\bmod3\ne0\)时，用\((1,2,z)\)来凑；否则当\(n\bmod3=0\)时，用\((1,4,z)\)来凑#include<cst......
  • April Fools Day Contest 2021 A. Is it rated - 2
    询问若干个问题，每个问题用一段字符串表示，存在空格。每个问题一行，对于每个回答，只需要输出\(NO\)。view1#include<bits/stdc++.h>chars[1000005];voidsolve(){ while(fgets(s,1000005,stdin)!=NULL){ std::cout<<"NO"<<std::endl;//fgets从流中读取，读取失......
  • Educational Codeforces Round 156 (Rated for Div. 2)
    EducationalCodeforcesRound156(RatedforDiv.2)A.SumofThree解题思路:如果\(n\leq6或n=9\),无解。若\(n\%3==0，t=\lfloor\frac{3}{n}\rfloor\):若\(t=0\)构造\(1,4,n-5\)否则，构造\(t-3,t,t+3\)若\(n\%3==1:构造1,2，n-3\)若\(n......
  • Educational Codeforces Round 152 (Div. 2) D. Array Painting（双指针）
    EducationalCodeforcesRound152(Div.2)D.ArrayPainting//思路：双指针找连续正数段//若段中出现2，则更新两头的0的情况，若为涂色则改为true//若无2，则优先更新左侧0，若左0已经为true，则更新右侧0//数组开头结尾特判#defineintlonglong#defineldlongdoubleusingnam......
  • 练习记录-cf-Educational Codeforces Round 156 (Rated for Div. 2)(A-C)
    好久没打了还是就出了三道不过还好没掉分A.SumofThree就是问能不能把一个数拆成三个不同的且都不能被三整除的数我的思路就是拆成1+2+一个大于等于4的数如果拆了后另一个数是%3==0那么我拆成1+4它肯定就不被整除然后判下相同#include<bits/stdc++.h>#defineclose......
  • This generated password is for development use only. Your security configuration
    问题描述在我加上spring-boot-starter-security的依赖之后，启动项目报出来这样的错误：问题解决在启动类的注解上，加上这么一段代码就ok啦！启动成功：......
  • SWERC 2022-2023 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
    Preface纯纯的智商场，只能说老外的出题风格和国内的比赛差异还是挺大的这场开局被签到题H反杀后灰溜溜地下机，结果后面的题出的都还挺顺的等到最后徐神把J过掉后我们都以为D是个大分类讨论（实际上机房里的学长们都是用分类讨论过的），就不想写了挂机到结束后面看题解发现确实是分类......
  • Educational Codeforces Round 155 (Rated for Div. 2)
    \(A.Rigged!\)直接取第一个人能举起的最大重量看他是否是冠军即可。voidsolve(){intn=read();intfx=read(),ft=read();intans=fx;for(inti=1;i<n;i++){intx=read(),t=read();if(x>=fx&&t>=ft)ans=-1;}cout<<ans<......
  • Educational Codeforces Round 112 (Rated for Div. 2) A. PizzaForces
    有三种披萨：\(6\)、\(8\)、\(10\)块披萨。制作时间分别需要：\(15\)、\(20\)、\(25\)分钟。现在有\(n\)个人，每人需要一块披萨。询问使所有人能获得披萨的最快时间。观察：发现三种披萨的性价比都一样。（否则按最优性价比贪心）需要让得到的披萨数量\(m\geqn\)。不妨让\(n\)对......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99