复制鸡

连续一段相同数字可以被视为一个数连续复制
	for(int i=1;i<=n;++i)
    {
        cin>>a[i];
        if(a[i] != a[i - 1]) cnt++;
    }
    cout<<cnt<<'\n';

好伙计猜拳

二维DP，类似最长上升子序列，用dp[i][j]表示处理了1~i，第i位不变，删除，交换三种操作
    dp[1][0] = 0, dp[1][1] = c1, dp[1][2] = c2;
    for(int i=2;i<=n;++i)
    {
        //若保留第i项，枚举上一项
        for(int j=0;j<i;++j)
        {
            if(a[j]<=a[i] && b[j]<=b[i]) dp[i][0] = min(dp[i][0], dp[j][0] + (i-j-1)*c1);
            if(b[j]<=a[i] && a[j]<=b[i]) dp[i][0] = min(dp[i][0], dp[j][2] + (i-j-1)*c1);
        }
        //若删除第i项
        dp[i][1] = min(dp[i][1],min({dp[i-1][0],dp[i-1][1],dp[i-1][2]}) + c1);
        //若交换第i项，枚举上一项
        for(int j=0;j<i;++j)
        {
            if(a[j]<=b[i] && b[j]<=a[i]) dp[i][2] = min(dp[i][2], dp[j][0] + (i-j-1)*c1 + c2);
            if(b[j]<=b[i] && a[j]<=a[i]) dp[i][2] = min(dp[i][2], dp[j][2] + (i-j-1)*c1 + c2);
        }
    }

数列之和

数学推导：设选择的子段是[l,r]则子段和是，因为要求子段长度大于1，故除了l = 1 and r = 2的子段和一定可以写成一个大于1的奇数乘以偶数的形式，可以发现2的幂次不能满足。故写一个二分查找即可
	auto check = [&](ll x)->ll
	{
		return x - __lg(2*x) + 1;
	};
	ll L = 0, R = 2*k;
	while(L + 1 < R)
	{
		ll M = (L + R)/2;
		if(check(M) < k) L = M;
		else R = M;
	}
	cout<<2*R<<'\n';

Viva La Vida(Fried-Chicken's Version)

可以证明除了重边没有其它环存在，设由<a,b,c>三点构成一环，若<a,b>边是a选择的，<b,c>边是由b选择的，<c,a>边是由c选择的，可以发现矛盾即边<a,b> < 边<a,c>，边<b,c> < 边<b,a> ,边<c,a> < 边<c,b>。故对于每一条边单独考虑若是重边导致最终的连通块数目加一，该边同时是a点，b点所连边里最短的概率是，共条边
	n = II()
    C = n * (n - 1) % MOD * inv2 % MOD 
    INV = inv(2 * n - 3)
    ans = C * INV % MOD
    print(ans)

任造化落骰

本题基于结论：随机分布时前缀最大值的变化次数期望为，利用单调栈处理出每个数的下一个更大值的位置和更小值的位置，枚举左端点，将区间切分成至多段分别统计不同最大最小值乘积的段数，最后将询问离线倒叙求前缀和即可
	for(int i=1;i<=n;++i)
    {
        int maxn = a[i], minn = a[i];
        int MAX_idx = nxt_max[i], MIN_idx = nxt_min[i];
        int limit = min(MAX_idx, MIN_idx) - i;
        cnt[(ll)maxn * minn] += limit;
        int j = min(MAX_idx, MIN_idx);
        maxn = max(maxn, a[j]), minn = min(minn, a[j]);
        while(MAX_idx <= n || MIN_idx <= n)
        {
            if(MAX_idx == MIN_idx) MAX_idx = nxt_max[MAX_idx], MIN_idx = nxt_min[MIN_idx];
            else if(MAX_idx > MIN_idx) MIN_idx = nxt_min[MIN_idx];
            else MAX_idx = nxt_max[MAX_idx];
            limit = min(MAX_idx, MIN_idx) - j;
            cnt[(ll)maxn * minn] += limit;
            j = min(MAX_idx, MIN_idx);
            maxn = max(maxn, a[j]), minn = min(minn, a[j]);
        }
    }

薪得体会

先按照由小到大排序，目标是取到最大的，假设已经处理完前n - 1个offer，最大薪水为ans[n-1]，若ans[n-1] >= a[n]则ans[n] = a[n] + b[n]，否则ans[n] = max(a[n], a[n-1] + b[n-1])
	for i in range(n):
        a[i], b[i] = MI()
        c.append((a[i], b[i]))
    c.sort(key = lambda x: x[0] + x[1])
    ans = 0
    ans = c[0][0]
    # 注意python的i-1可能访问到最后一个元素
    for i in range(1,n):
        if ans >= c[i][0]:
            ans = c[i][0] + c[i][1]
        else:
            ans = max({c[i][0], ans, c[i-1][0] + c[i-1][1]})
    print(ans)

目标是【L2】传说高手

设使用率表示为可以发现x至多枚举到1000，一定会出现落在[pi - 0.05, pi + 0.05)的区间内。故枚举x，看对于x是否所有的i都有对应的ci满足。将不等式变化形式使得用整数做所有运算可以发现check是O(1)的
	auto check = [&](int x,int j)->bool
    {
        if(!p[j]) return true;
        int L = (p[j] - 5) * x, R = (p[j] + 5) * x;
        if((R - 1)/10000 - (L - 1)/10000 >= 1) return true;
        return false;
    };
    for(int i=0;i<=1000;++i)
    {
        int j = 0;
        while(j < n && check(i,j)) j ++;
        if(j == n) {ans2 = i;break;}
    }
对于胜率也是类似的道理，但胜率需要保证有赢的场次也有输的场次。

故ans = + 

	int max_w = 0, max_l = 0;
    //因为[L,R)至多有10000个数不可能有超过一个的10000倍数
    auto update = [&](int x,int j)->bool
    {
        int L = (p[j] - 5) * x, R = (p[j] + 5) * x;
        if((R - 1)/10000 - (L - 1)/10000 >= 1)
        {
            int c = (R - 1) / 10000;
            max_w = max(max_w, c);
            max_l = max(max_l, x - c);
            return true;
        }
        return false;
    };
    //关于有多个x取到相同胜率区间a/b ~~ c/d
    //a < c，b < d 则选c/d的max_w和max_l一定不会优于选a/b
    for(int i=0;i<n;++i)
    {
        if(!p[i]) continue;
        for(int j = 1;j<=1000;++j)
        {
            if(update(j, i)) break;
        }
    }
    ans1 = max_w + max_l;

小鸡的排列构造

易发现若查询区间的长度为偶数，直接反序即可，若为奇数，可以先构造限制最强的即任意长度为三的连续子区间，观察排列可以发现构造规律
    if flag :
        for j in range(0, n - 1, 2):
            a[j], a[j + 1] = a[j + 1], a[j]
            # print(a)        
    for i in range(n):
        print(a[i], end = " " if i != n - 1 else "\n")

小鸡的排列构造的checker

离线查询使用树状数组即可
    for(int i=1;i<=n;++i)
    {
        //当op是1是先查询[0,val-1]后插入
        //当op是2时先插入查询a[i]再查询
        bool flag = false;
        for(auto [op,val,idx] : query[i])
        {
            if(op == 1) 
            {
                ans[idx] = A.sum(val - 1);
                //cout<<"L "<<val<<' '<<idx<<' '<<ans[idx]<<'\n';
            }
            else 
            {
                if(!flag) {A.update(a[i], 1);flag = true;}
                int tmp = A.sum(val - 1);
                ans[idx] = tmp - ans[idx];
                //cout<<"R "<<val<<' '<<idx<<' '<<ans[idx]<<'\n';
            }
        }
        if(!flag) A.update(a[i], 1);
    }

铁刀磨成针

枚举开始砍的日期即可
	ll ans = 0;
    for(int i=1;i<=y;++i)
    {
        //可以保持y-i+1天的x+i战斗力
        if(y >= n) ans = max(ans, (ll)(n - i + 1) * (x + i));
        else
        {
            ll tmp = (ll)(y - i + 1)*(x + i);
            if(n - y >= x + i - 1) tmp += (x + i) * (x + i - 1) / 2;
            else tmp += (x + i - 1 + x + i - (n - y)) * (n - y) / 2;
            ans = max(ans, tmp);
        }
        //cout<<i<<' '<<ans<<'\n';
    }
    cout<<ans<<'\n';

鸡翻题

判断奇偶性即可

变鸡器

判断有没有某一项大于sum的一半即可