ABC223

B

题意：给你一个长为N的串（只包括小写字母），可以对他循环左移或右移，求能够获得的最小/大字典序串

方法：左移一次相当于右移N - 1次，左移两次相当于右移N - 2次...所以只需要模拟左移0~N - 1次，就包括了右移的所有情况...

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int main(){
    string s;
    cin >> s;
    
    vector<string> v;
    for(int i = 0; i < s.size(); i ++){
        v.push_back(s);
        s = s.substr(1) + s[0];
    }
    
    cout << *min_element(v.begin(), v.end()) << endl;
    cout << *max_element(v.begin(), v.end()) << endl;
}

C

题意：一堆不同的保险丝前后连在一起，每一个保险丝有一个长度和燃烧速度，现在把左右都点燃，求两个火相遇时相对于最左边的位置

方法：两者相遇时间固定为\(T / 2\)，T为总时间，所以只需要求出\(T / 2\)时第一个火走到哪就是答案了...

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 100010;

double a[N], b[N], t[N];
int n;

int main(){
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i] >> b[i];
    for(int i = 1; i <= n; i ++) t[i] = t[i - 1] + a[i] / b[i];
    double T = t[n] / 2;
    int l = 1, r = n;
    while(l < r){
        int mid = l + r >> 1;
        if(t[mid] >= T) r = mid;
        else l = mid + 1;
    }
    T -= t[l - 1];
    double res = 0;
    for(int i = 1; i < l; i ++) res += a[i];
    res += T * b[l];
    cout << res << endl;
}

D

题意：给你一堆顺序关系，求出字典序最小的排列

方法：拓扑排序...

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;

const int N = 200010;

int n, m;
vector<int> h[N];
int in[N];

vector<int> topsort(){
    priority_queue<int, vector<int>, greater<int>> q;
    vector<int> res;
    for(int i = 1; i <= n; i ++)
        if(!in[i]) q.push(i);
        
    while(q.size()){
        int hh = q.top();
        res.push_back(hh);
        q.pop();
        for(int i = 0; i < h[hh].size(); i ++){
            int j = h[hh][i];
            in[j] --;
            if(in[j] == 0) q.push(j);
        }
    }
    
    return res;
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < m; i ++){
        int a, b;
        cin >> a >> b;
        h[a].push_back(b);
        in[b] ++;
    }   
    
    auto res = topsort();
    if(res.size() == n){
        for(auto t : res) cout << t << ' ';
        return 0;
    } 
    
    puts("-1");
}