【补】2022.7.22———多校联测【2022年多校冲刺NOIP联训测试4】

#include <iostream>
#include <iomanip>
#include <algorithm>
#define GMY (520&1314)
#define FBI_OPENTHEDOOR(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout);
#define re register int
#define char_phi signed
#define MARK cout << "###"
#define _MARK "@@@"
#define LMARK "!!!~~~"
#define ZY " qwq "
#define _ " "
#define Endl cout << '/n'
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define CASE 12
#define N 100005
#define MAXNUM 1000000002
using namespace std;
inline void Fastio_setup(){ios::sync_with_stdio(false);cin.tie(NULL), cout.tie(NULL);}
long long T, n, final_ans, now;
struct node{
    long long die, need, derta;
}a[N];
inline bool comp(node A, node B){
    if(A.derta != B.derta) return A.derta > B.derta;
    else if(A.die != B.die) return A.die > B.die;// 这应该没影响
    else return A.need > B.need;
}
inline void Clean(){now = final_ans = 0;}
inline void work(){
    Clean();
    // T1 额
    // 这个就是derta是吗
    // die <= need
    cin >> n;
    for(re i = 1 ; i <= n ; ++ i){
        cin >> a[i].die >> a[i].need;
        a[i].derta = a[i].need-a[i].die;
    }
    sort(a+1, a+n+1, comp);
    for(re i = 1 ; i <= n ; ++ i){
        if(now >= a[i].need){
            now -= a[i].die;
            continue;
        }
        final_ans += (a[i].need-now), now = a[i].need;
        now -= a[i].die;
    }
    cout << final_ans << '/n';
}
// #define IXINGMY
char_phi main(){
    #ifdef IXINGMY
        FBI_OPENTHEDOOR(a);
    #endif
    Fastio_setup();
    cin >> T;
    while(T --){
        work();
    }
    return GMY;
}

 

#include <iostream>
#include <iomanip>
#include <cmath>
#include <random>
#include <ctime>
#define GMY (520&1314)
#define FBI_OPENTHEDOOR(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout);
#define re register int
#define char_phi signed
#define MARK cout << "###"
#define _MARK "@@@"
#define LMARK "!!!~~~"
#define ZY " qwq "
#define _ " "
#define Endl cout << '/n'
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define eps 0.000000000001
#define N 200005
#define MAXNUM 10005
#define mod %
using namespace std;
inline void Fastio_setup(){ios::sync_with_stdio(false);cin.tie(NULL), cout.tie(NULL);}
int n, ner;
long long tim;
double final_ans(11451419.0);
double a[N], kl[N];
inline bool check(double number){
    for (re i = 1 ; i <= n ; ++ i)
        kl[i] = a[i] + number;// 注意是加 因为有负数
    double mn(kl[1]), mx(kl[1]), now_min(0), now_max(0);
    for (re i = 1 ; i <= n ; ++ i){
        now_min += kl[i], now_max += kl[i];
        mn = MIN(mn, now_min), mx = MAX(mx, now_max);
        if (now_min > 0) 
            now_min = 0;// 前面的不要了开另一个区间，因为前面的加起来已经大于0，后面咋变小都没有重新开一个区间、now_min=0更优，所以重新开一个区间
        if (now_max < 0) 
            now_max = 0;
    }
    double harmony = MAX(abs(mn), abs(mx));
    if (harmony < final_ans) final_ans = harmony;
    if (mx < 0) return false;
    // mx >= 0 了
    if (mn > 0) return true;// 最小的都大于0，那么根本不够小，应该减得更小
    // mn <= 0 了
    if (abs(mn) < abs(mx)) return true;// 应该更小一些以使得abs(mn)更大，也就是x更大
    // abs(mn) >= abs(mx);
    return false;
}
inline void work(){
    random_device rd;// 来吧！随机化！！！
    mt19937 myrand(rd());
    // 既然虎哥都说惹。。那么我就先改题吧
    // 模拟退火先放一下)
    // T2
    // sum为前缀和数组，那么题意：
    // 找到一个最小的ans，使得任意的1 <= j <= i <= n, sum[i]-sum[j] - (i-j)*x <= ans
    // 所以拆开
    // sum[i]-i*x - (sum[j]-j*x) <= ans
    // 所以要找的ans：
    // ans = MAX{sum[i]-i*x} - MIN(sum[j]-j*x)
    // 注意到      ↑                   ↑   各是关于x的两个一次函数
    // 这本来是一个单谷函数，可以用爬山算法，模拟退火额也行
    // 然而可以三分。但是蒟蒻不会三分
    // 所以考虑二分(考虑陈钩R(划掉))
    // 考虑两个极值(最初时)。一个是最大的记为mxx，一个是最小的记为mnn
    // 两种情况。
    // Case 1： mxx > 0 && mnn > 0
    // 这种情况下我们会希望让mnn一直减小到0之后接着减小，同时mxx当然也会减小，但是abs()是个单谷的，所以过了0这个界限之后abs(mnn)有朝一日会再减一点点点就会比比 abs(mxx)大，这里就是我们想要的谷点
    // 所以二分减去多少x， 找到那个谷点
    // 这种情况启示我们二分的时候要边界应该包括正数
    // Case 2: mxx > 0 && mnn < 0
    // 这种情况下也是，和上面差不多，这个可以再分成两种情况，即 ↓
    // 这种情况启示我们二分的时候边界应该包括负数。因为初始时可能abs(mnn) > abs(mxx)，也可能【 < 】。【 > 】 的话就肯定是要让mnn增加也就是让abs(mnn)减小，让abs(mxx)增大，然后看拐点
    // 然后剩下的就是代码实现了 代码实现还是比较ex的。。。(对于本蒟蒻而言)
    // 那个“y”图像，一个是mx，一个是abs(mn)
    cout.setf(ios::fixed), cout.precision(6);
    cin >> n; ner = (sqrt(sqrt(n))+1) * 100000;
    for (re i = 1 ; i <= n ; ++ i)
        cin >> a[i];
    double l = -10000.0, r= 10000.0, mid;
    // int times(0);
    // long long tim = clock();
    // while (r-l >= eps) {
    //     mid = ((l + r) / 2.0) + (SQ(SQ(SQ(SQ(SQ(SQ(SQ(SQ((double)myrand())))))))));// -x, 过去后是+x
    //     mid -= SQ(SQ(SQ(SQ(SQ(SQ(SQ(SQ((double)myrand()))))))));
    //     cout << l << _ << mid << _ << r << '/n';
    //     if(check(mid) == true) r = mid;// 值应当更小，x应当更大
    //     else l = mid;
    //     times ++;
    //     if(times == 50000) break;
    // }
    
    while (r-l >= eps) {
        // mid = ((l + r) / 2.0) + myrand()*1e-9;// -x, 过去后是+x
        // mid -= myrand()*1e-8;
        // cout << l << _ << mid << _ << r << '/n';
        mid = ((l + r) / 2.0);
        if(check(mid) == true) r = mid;// 值应当更小，x应当更大
        else l = mid;
        // times ++;
        // if(times == 1000) break;
        if((double)(clock()-tim) * 1000 / CLOCKS_PER_SEC >= 2995) break;
    }
    // cout << clock() - tim << endl;
    cout << final_ans << '/n';
}
// #define IXINGMY
char_phi main(){
    tim = clock();
    #ifdef IXINGMY
        FBI_OPENTHEDOOR(a);
    #endif
    Fastio_setup();
    work();
    return GMY;
}

 

#include <iostream>
#include <iomanip>
#include <queue>
#include <cstring>
#define GMY (520&1314)
#define FBI_OPENTHEDOOR(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout);
#define re register int
#define char_phi signed
#define MARK cout << "###"
#define _MARK "@@@"
#define LMARK "!!!~~~"
#define ZY " qwq "
#define _ " "
#define Endl cout << '/n'
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define N 100005
using namespace std;
inline void Fastio_setup(){ios::sync_with_stdio(false);cin.tie(NULL), cout.tie(NULL);}
int n, R, mid, star_cnt;
char sr[N];
bool inq[N];// inside_queue
int p[N<<1], f[N], dis[N], head[N];
struct star{
    int v, w, nxt;
}e[N<<1];
queue<int> q;
string a;
// T3 萨鲁曼的半兽人
// joke的SPFA，真的diao
// 所以用joke 的SPFA来了
inline void star_add(int u, int v, int w){e[++ star_cnt].v=v, e[star_cnt].w=w, e[star_cnt].nxt=head[u], head[u]=star_cnt;}
inline void Clean(){
    star_cnt = mid = R = 0; a.clear();
    for (re i = 1 ; i <= n+3 ; ++ i)
        sr[i] = head[i] = f[i] = p[i] = inq[i] = 0, dis[i] = 1145141919;
}
inline void spfa(int x){
    q.push(x), dis[x] = 0, inq[x] = true;
    while (q.empty() == false){
        x = q.front(), q.pop();// 一x多用(doge)
        inq[x] = false;
        for (re i = head[x] ; i ; i = e[i].nxt){
            if (dis[e[i].v] > dis[x]+e[i].w){
                dis[e[i].v] = dis[x]+e[i].w;
                if (inq[e[i].v] == false)
                    q.push(e[i].v), inq[e[i].v]=true;
            }
        }
    }
}
inline void work(){
    a += '(';
    for (re i = 1 ; i <= n ; ++ i)
        a += '#', a += sr[i];
    a += '#', a+= ')';
    for (re i = 1 ; i <= a.size()-2 ; ++ i){
        p[i] = ( (R > i) ? (MIN(p[(mid<<1)-i], R-i)) : (1));
        while(a[i+p[i]] == a[i-p[i]]) p[i] ++;
        if (i+p[i] > R)
            R = i+p[i], mid = i;
    }
    for (re i = 1 ; i <= a.size()-2 ; ++ i){
        if ( ((i-1) & 1) == 1 )
            f[(i>>1) - (p[i]>>1) + 1] = MAX(f[(i>>1) - (p[i]>>1) + 1], (i>>1) + (p[i]>>1) - 1);
        else if (p[i] > 1)
            f[((i-1)>>1) - ((p[i]-1)>>1) + 1] = MAX(f[(i-1)>>1 - ((p[i]-1)>>1) + 1], ((i+1)>>1) + ((p[i]-1)>>1) - 1);
    }
    star_add(1, f[1]+1, 1);
    for (re i = 2 ; i <= n ; ++ i)
        star_add(i, f[i]+1, 1), star_add(i, i-1, 0);// joke/
                                    “一直往前莽可能到不了”
    spfa(1);
    // MARK;
    cout << dis[n+1]-1 << '/n';///
           字符之间建边，点会多一个(手模) 减一很简单，他问的是“连接”，表明过了dis[n+1]个边dis[n+1]+1个点，其中每两个点是一个“子回文串”so有dis[n+1]个，把他们连接起来要有dis[n+1]-1
}
/*
obocodo
abcdef
abcdcba
*/
// #define IXINGMY
char_phi main(){
    #ifdef IXINGMY
        FBI_OPENTHEDOOR(a);
    #endif
    Fastio_setup();
    for (re i = 1 ; i <= 100000 ; ++ i) dis[i] = 1145141919;
    while (true){
        Clean();
        cin >> sr+1; n = strlen(sr+1);
        // cout << n << _ << strlen(sr+1) << '/n';
        if(n == 0) break;
        work();
    }
    return GMY;
}