526互联

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

发布时间 2023-10-12 19:54:59作者: Vellichor_zht

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';
    }

}