河南萌新联赛2024第（六）场：郑州大学

评价：题适中难度，区分度较明显，个人题解不包含E题、J题（理论上，能想明白但是说不清J）。

J 理论上来说是中档题，不至于3 / 81

L 经典原题

A. 装备二选一（一）

题意：

已知A属性为 0% 暴击率，普通攻击伤害为 x （a ≠ 0）值。

手中的武器会为他增加 a% 的暴击率，发生暴击时会使他本次普通攻击伤害变为原来的 b 倍。
boss 掉落的武器会为他增加 c% 的暴击率，发生暴击时会使他本次普通攻击伤害变为原来的 d 倍。

题解：数学、期望

其实就是比较两把武器能在无限次攻击的情况下能造成的伤害有多大：

手中的武器伤害期望为 ( 没暴击打的伤害 + 暴击打的伤害 ) ：

$$(100 - a)*x + a * bx$$

更换武器后的伤害期望为：

$$(100 - c)*x + c * dx$$

通过对比两个伤害期望能发现：最开始的普通攻击伤害在里面是不受影响的，因此只用比较：

$$(100 - a) + a * b 和 (100 - c) + c * d$$

的大小就可以确定答案了。

代码：

void JiuCherish(){
    int a,b,c,d;
    std::cin >> a >> b >> c >> d;
    if(a * b + (100 - a) >= c * d + (100 - c)) {
        std::cout << "NO" << endl;
    } else {
        std::cout << "YES" << endl;
    }
}

B.百变吗喽

题意：

有两个字符串 s、t ，保证均为小写字母并且 **len(s) = len(t) - 1 **, 你可以让任意一个字母插入到任意位置（某个字母的后面或者整个单词的最前面）。问有多少种插入的方案能够使得插入字母后 s 和 t 相同，并给出每种方案的插入位置和变化的字母。

数据范围：

$$1 \leq len(s) < 10^6$$

题解：模拟

考虑s,t的公共前缀pre和公共后缀suf，那么我们可以在[pre,suf]的区间里面插入字符使得 s 与 t相等。

代码：

void JiuCherish(){
    std::string s,t;
    std::cin >> s >> t;
    int n = t.length();
    int index = 0;
    std::vector<int> idxx;
    std::vector<char> anss;
    for(int i=0;i<n;i++) {
        if(s[i] == t[i]) pre[i] = true;
        else break;
    }
    for(int i=n-1;i>=1;i--) {
        if(s[i - 1] == t[i]) last[i] = true;
        else break;
    }
    while(index < n) {
        bool ok1 = false,ok2 = false;
        if(index and !pre[index - 1]) ok1 = true;
        if(index < n - 1 and !last[index + 1]) ok2 = true;
        if(!ok1 and !ok2) {
            idxx.pb(index);
            anss.pb(t[index]);
        }
        index++;
    }
    std::cout << idxx.size() << endl;
    for(int i=0;i<idxx.size();i++) {
        std::cout << idxx[i] << ' ' << anss[i] << endl;
    }
}

C.16进制世界

题意：

每个月饼有饱食度和幸福度两个属性。

现在Bob有n个月饼，对于每个月饼i，饱食度为v_i，幸福度为w_iw。

Bob现在有m饱食度，意味着他吃的月饼的饱食度之和不大于m。

但是由于Bob身处16进制的世界，他吃的月饼的幸福度之和必须是16的倍数。

请帮Bob算一下他最多吃的月饼的数量。

数据范围：

$$1 \leq n * m \leq 10^5 , 1 \leq v_i \leq 10^5 , 1 \leq w_i \leq 10^9$$

题解：背包

背包板子题，约定 dp[i] [j] 为饱食度为 i ,幸福度为 j mod 16 能吃的最多月饼个数。转移状态为：

$$dp[i + v][(j + w) mod 16] = max(dp[i + v][j + w] mod 16,dp[i][j] + 1)$$

代码：

void JiuCherish(){
    int n,m;
    std::cin >> n >> m;
    std::vector<std::pair<int, int>> mm(n);

    for (int i = 0; i < n; ++i) {
        std::cin >> mm[i].fi >> mm[i].se;
    }

    std::vector<std::vector<int>> dp(m + 1,std::vector<int>(16,-1));
    dp[0][0] = 0;
    for(int i=0;i<n;i++) {
        for(int j=m;j>=mm[i].fi;j--) {
            for(int k=0;k<16;k++) {
                if(dp[j - mm[i].fi][k] != -1)
                dp[j][(k + mm[i].se) % 16] = std::max(dp[j][(k + mm[i].se) % 16],dp[j - mm[i].fi][k] + 1);
            }
        }
    }
    int ans = 0;
    for(int i=0;i<=m;i++) {
        ans = std::max(ans,dp[i][0]);
    }
    std::cout << ans << endl;
}

D. 四散而逃

思维较不错的一个题，可惜数据弱了，hack数据：1 3 1 1 实际上应该是3次不是-1，

(1 3 1 1) ->(2 1 2 1) -> (2 2 0 2) -> (3 0 0 3)

题意：

n 个格子，起初 i 个格子有 a_i 个人，每次操作可以选三个下标 i , j ,k ，其中满足 1 <= i < j < k <= n** 并且 **a_j >= 2 ，从 j 号格子中选择两个人分别逃到 i 号格子和 k 号格子。

问最少需要多少次才能让所有人达到 1 号格子或者 n 号格子，若无论多少次操作都做不到，输出**-1**

数据范围：

$$3 \leq n \leq 2\times 10^5$$

$$1 \leq a_i \leq 10^9$$

题解：模拟

无解的情况只会是：一共三个数且中间是奇数或者中间的数都是1。

那么剩下除去1和n位置，其他位置每个数的奔逃贡献是如果是奇数那么就是 (x + 1) / 2,偶数是 x / 2。

代码：

void JiuCherish(){
    int n,m;
    std::cin >> n;
    for(int i=1;i<=n;i++) std::cin >> a[i];
    if(n == 3) {
        if(a[2] & 1) {
            std::cout << -1 << endl;
        } else {
            std::cout << a[2] / 2;
        }
    } else {
        i64 ans = 0;
        bool f = 0;
        for(int i=2;i<=n-1;i++) {
            if(a[i] > 1) f = 1;
            ans += (a[i] + 1) / 2;
        }
        if(f) std::cout << ans << endl;
        else std::cout << -1 << endl;
    }
}

E. 铃兰小姐是我们的光

题意：

Alear 为了让铃兰不感到孤单，送给了铃兰小姐一棵神奇的小树。
这棵树每个节点都带有一种颜色，并且会随着时间不断生长。有些日子里，铃兰小姐想知道树上会有多少种颜色呢？当然，把整棵树都数一遍很辛苦的，她每次只会问以某个节点 u 为根的子树内有多少种不同的颜色。
Alear 需要立刻回答铃兰的问题，因此需要你的帮助。

数据范围：

$$1 \leq n \leq 2\times 10^5 , 1 \leq q \leq 4\times 10^5$$

有 n 个节点，一共有 q 个操作。
接下来 q 行，每行为：
1. 0 u f c：表示一个新长出的节点，其父节点为 f ，颜色为 c ，特别的，第一行 0 1 0 c 表示节点 1 是颜色为 c 根节点。
2. 1 u ：表示询问以节点 u 为根的子树内颜色数。

题解：替罪羊树、lca

参考：陈立杰的 IOI 2013 集训队论文《重量平衡树和后缀平衡树在信息学奥赛中的应用》

不会

代码：

#include<bits/stdc++.h>
#define next nxt
using namespace std;
int read(){
    int c=0,nx,sign=1;
    while(!isdigit(nx = getchar()))
        if(nx=='-')
            sign=-1;
    while(isdigit(nx))
        c=c*10+nx-'0',nx=getchar();
    return sign*c;
}
 
const int N=2e6 + 20,M=N*2;
int head[N],next[M],ver[M];
inline void addEdge(int u,int v){
    static int now = 0;
    next[++now]=head[u],head[u]=now,ver[now]=v;
    next[++now]=head[v],head[v]=now,ver[now]=u;
}
 
const int K = N * 2;
double alpha = 0.7;
int n, m, root;
int sum[K], dat[K];
int ls[K], rs[K], sz[K];
double val[K];
int k;

class cmp {
    public:
        bool operator() (const int& lc, const int& rc)const {
                return val[lc] < val[rc];
        }
};
set<int, cmp> col[N];
 
int *to_build;
double tol, tor;
 
inline int New(int x){
    static int now = 0;
    dat[++now] = x;
    return now;
}
inline void pushup(int s){
    sz[s] = sz[ls[s]] + sz[rs[s]] + 1;
    sum[s] = sum[ls[s]] + sum[rs[s]] + dat[s];
}
inline bool is(int s){
    return sz[s] * alpha < max(sz[ls[s]], sz[rs[s]]);
}
 
 
void add(double p, int u, int x, int &s = root, double l=0, double r=1){
    if(!s){
        s = u;
        val[s] = (l + r) / 2;
        dat[s] = x;
        sz[s] = 1;
        return ;
    }
    if(p < val[s])
        add(p, u, x, ls[s], l, val[s]);
    else
        add(p, u, x, rs[s], val[s], r);
    pushup(s);
    if(is(s))
        to_build = &s, tol = l, tor = r;
}
 
void modify(double p, int x, int s = root){
    if(p < val[s])
        modify(p, x, ls[s]);
    else if(p > val[s])
        modify(p, x, rs[s]);
    else
        dat[s] += x;
    pushup(s);
}
 
int query(double ql, double qr, int s = root, double l=0, double r=1){
    if(!s)
        return 0;
    if(ql <= l and r <= qr){
        return sum[s];
    }
    int ans = 0;
    if(ql < val[s])
        ans = query(ql, qr, ls[s], l, val[s]);
    if(qr > val[s])
        ans += query(ql, qr, rs[s], val[s], r);
    if(ql <= val[s] and qr >= val[s])
        ans += dat[s];
    return ans;
}
 
int stk[K], top;
void dfs(int s){
    if(!s)
        return ;
    dfs(ls[s]);
    stk[++top] = s;
    dfs(rs[s]);
}
void build(int &s, int l=1, int r=top, double vl=tol, double vr=tor){
    if(l > r){
        s = 0;
        return ;
    }
    int mid = (l + r) >> 1;
    s = stk[mid];
    val[s] = (vl + vr) / 2;
    build(ls[s], l, mid - 1, vl, val[s]);
    build(rs[s], mid + 1, r, val[s], vr);
    pushup(s);
}
 
inline void insert(double p, int u, int x){
    add(p, u, x);
    if(to_build){
        top = 0;
        dfs(*to_build);
        build(*to_build);
        to_build = 0;
    }
}
 
namespace lca_bz{
    int lg[N];
    int fa[21][N],d[N];
     
    int lca(int u,int v){
        if(d[u] < d[v])
            swap(u,v);
        while(d[u] > d[v])
            u = fa[lg[d[u] - d[v]]][u];
        if(u==v)
            return u;
        for(int i=lg[d[u]];i>=0;i--)
            if(fa[i][u] != fa[i][v])
                u = fa[i][u], v = fa[i][v];
        return fa[0][u];
    }
}
using namespace lca_bz;
 
 
int main(){
    // 强制在线版标程
    // fclose(stderr);
    n = read(), m = read();
     
    d[0] = -1;
    int cntt = 0;
     
    for(int i=1;i<=n;i++)
        lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
    for(int i=0;i<=n;i++)
        --lg[i];
     
    int pre = 0;
    while(m--){
        int op = read(), u = read() ^ pre, f, c;
        if(op == 0){
            cntt++;
            f = read() ^ pre, c = read() ^ pre;
            d[u] = d[f] + 1;
            fa[0][u] = f;
            for(int i=1, tt = lg[d[u]];i<=tt;i++)
                fa[i][u] = fa[i - 1][fa[i - 1][u]];
            insert(val[f], u, 1);
            insert(val[u], u + n, 0);
             
             
            auto &cc = col[c];
            auto lp = cc.lower_bound(u), rp = cc.upper_bound(u);
            auto lt = lp != cc.begin(), rt = rp != cc.end();
            if(lt){
                lp--;
                f = lca(u, *lp);
                modify(val[f], -1);
            }
            if(rt){
                f = lca(u, *rp);
                modify(val[f], -1);
            }
            if(lt and rt){
                f = lca(*lp, *rp);
                modify(val[f], 1);
            }
            cc.insert(u);
        }else{
            printf("%d\n", pre = query(val[u], val[u + n]));
            pre = query(val[u], val[u + n]);
        }
    }
}

F. 追寻光的方向

题意：

小G在的道路上有 n 个路灯，每个路灯发光光亮为 l_i ，如果前方有亮灯，比当前所在的灯光亮大，那么小G会优先跑到最近更亮的灯，然后进行休息，问小G要跑到第 n 个路灯，需要休息几次？

数据范围：

$$1 \leq n \leq 10^5 ,1\leq l_i \leq 10^9$$

题解：前缀和，st表，模拟

查询到后面的数比当前的数大即可。

st表代码：

int Max[MAXN][21];
int Query(int l,int r)
{
    int k=log2(r-l+1); 
    return std::max(Max[l][k],Max[r-(1<<k)+1][k]);
}
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
void JiuCherish(){
    int N=read();
    for(int i=0;i<N;i++) {
        Max[i][0]=read();
        a[i] = Max[i][0];
    }
    for(int j=1;j<=21;j++)
        for(int i=1;i+(1<<j)-1<=N;i++)
            Max[i][j]=std::max(Max[i][j-1],Max[i+(1<<(j-1))][j-1]);
    int ans = 0;
    int now = 0;
    while(now < N - 1){
        int m = Query(now + 1,N - 1);
        now += 1;
        // std::cout << m << endl;
        while(a[now] < m) now++;
        ans++;
    } 
    ans -= 1;
    std::cout << ans << endl;
}

前缀和代码：

void JiuCherish(){
    int n;
    std::cin >> n;
    for(int i=1;i<=n;i++) std::cin >> a[i];
    
    suf[n] = n;
    for(int i=n-1;i>=1;i--) {
        if(a[i] >= a[suf[i + 1]]) {
            suf[i] = i;
        } else {
            suf[i] = suf[i + 1];
        }
    }
    int ans = 0;
    int p = 2;
    while(p <= n) {
        p = suf[p] + 1;
        ans += 1;
    }
    std::cout << ans - 1 << endl;
}

现已知每天都会发出 m 辆公交车，在手机上它可以查出这 m 辆公交车的发车时刻第 t_i 分钟，并且他还知道所有的站点信息，总共有 n 个公交车站点，第 i 个站点距离发车点的距离为 d_i 米。已知公交车的速度为 1 米/分钟，发车点和所有的站点都在一条直线上, 每次公交车从发车点出发后，依次经过每个站点。他想知道能否设计一个程序，当每次一个乘客在某个时刻时到达某个站点时，可以直接告诉他需要等待的时间？

数据范围：

$$1 \leq n,m,q < 10^5 , 1 \leq l_i ,t_i \leq 2\times 10^9$$

题解：二分

我们在距离为 d 的车站在 t 时刻开始等候，其实就相当于我们在距离为 0 的车站在 t~d 时刻开始等候。因为一辆车在某个时间到距离为 d 的车站，那么在 d 分钟前一定到距离为 0 的车站，所以两者的到站顺序是完全一致的。这样就不需要给每个公交车的发车时刻都加上一个 d，而只需要在二分查找的时候找 t~d 的时刻后第一辆发的车就可以了。

代码：

void JiuCherish(){
    int n,m;
    std::cin >> n >> m;
    for(int i=1;i<=n;i++) std::cin >> d[i];
    for(int i=1;i<=m;i++) std::cin >> t[i];
    int q;
    std::cin >> q;
    while(q--) {
        i64 tt,x;
        std::cin >> tt >> x;
        int l = std::lower_bound(t + 1,t + m + 1,std::max((i64)0,tt - d[x])) - t;
        if(t[m] + d[x] < tt) {
            std::cout << "TNT" << endl;
        } else {
            std::cout << (t[l] - tt + d[x]) << endl;
        }
    }
}

H. 24点

洛谷较容易版24点：https://www.luogu.com.cn/problem/P1236

7 7 3 3 如何凑成24点 ： (3 + 3 / 7) * 7 = 24 / 7 * 7 = 24

题意：

扑克牌游戏24点：

四张牌，每张牌只能用一次，可任意更改顺序，可加括号，进行加减乘除运算最终得到 24。

数据范围：

$$1 \leq T \leq 1000$$

题解：模拟，dfs

通过全排列枚举

1.((a?b)?c)?d

2.(a?(b?c))?d

3.a?((b?c)?d)

4.(a?b)?(c?d)

5.a?(b?(c?d))

五种情况即可。

代码：

double a[5];
char ops[4]= {'+','-','*','/'};

double operate(double a, double b, char op) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return b != 0 ? a / b : 0;
    }
    return 0;
}

bool check(double a,double b,double c,double d) {
	for(int i=0;i<4;i++) {
		for(int j=0;j<4;j++) {
			for(int k=0;k<4;k++){
				if (std::fabs(operate(operate(operate(a, b, ops[i]), c, ops[j]), d, ops[k]) - 24) < 1e-6) {
                    return true;
                }
                if (std::fabs(operate(operate(a, operate(b, c, ops[j]), ops[i]), d, ops[k]) - 24) < 1e-6) {
                    return true;
                }
                if (std::fabs(operate(operate(a, b, ops[i]), operate(c, d, ops[k]), ops[j]) - 24) < 1e-6) {
                    return true;
                }
                if (std::fabs(operate(a, operate(operate(b, c, ops[j]), d, ops[k]), ops[i]) - 24) < 1e-6) {
                    return true;
                }
                if (std::fabs(operate(a, operate(b, operate(c, d, ops[k]), ops[j]), ops[i]) - 24) < 1e-6) {
                    return true;
                }
			}
		}
	}
	return false;
}

double change(std::string x) {
    if(x == "J") {
        return 11;
    }
    if(x == "Q") {
       return 12;
    }
    if(x == "K") {
        return 13;
    }
    if(x == "A") {
        return 1;
    }
    return std::stoi(x);
}
void JiuCherish(){
    for(int i=0;i<4;i++) {
		std::string x;
		std::cin >> x;
		a[i] = change(x);
	}
    sort(a,a + 4);
	bool ok = false;
	// std::cout << a[1] << ' ' << a[2] << ' ' << a[3] << ' ' << a[4] << endl;
 	do {
        if (check(a[0], a[1], a[2], a[3])) {
            ok = true;
			break;
        }
    } while (std::next_permutation(a,a + 4)); 
	if(ok) {
		puts("YES");
	} else {
		puts("NO");
	}
}

I.正义从不打背身

题意：

小x 面前有 n 个点位，从左往右顺序为1~n，每个点位都有一个敌人，每个敌人要么正面面对小x，要么背面面对小x，其中(P表示正面面对小x，B表示背面面对小x)。

小x 强迫 n 个敌人玩 m 轮小游戏之后在对每个人开枪。

规则如下：

在第 i 轮小游戏中，依次执行以下所有操作：

序列号为 1~i 的敌人翻转一次，即变为 i ~ 1 。

序列号为 [1,i] 的点位上的敌人原地旋转180°。

所有小游戏过后，小x想知道。目前在每个点位的敌人是否被击败。

数据范围：

$$1 \leq m \leq n \leq 2\times 10^6,|s| = n$$

题解：打表

由于敌人每一轮游戏不是正就是反，因此只有两种可能，但是考虑到模拟的复杂度会炸，因此考虑暴力打表观察结果。

打表代码：

void JiuCherish(){
    // int n,m;
    // std::cin >> n >> m;
    // std::string s;
    // std::cin >> s;
    int n,m;
    std::cin >> n >> m;
    for(int i=1;i<=n;i++) a[i] = i;
    for(int i=1;i<=m;i++) {
        for(int j=1;j<=i / 2;j++) {
            std::swap(a[i],a[i - j + 1]);
        }
        for(int j=1;j<=i;j++)vis[a[j]]^=1;

        std::cout << "i: " << i << endl;
        for(int j=1;j<=i;j++)
            std::cout<<(vis[a[j]]?"D":"L")<<" ";
        std::cout<<endl;
        for(int j=1;j<=i;j++) {
            std::cout << a[j] << ' ';
        }
        std::cout << endl;
    }
}

规律：

i: 1
D 
1 
i: 2
L D 
1 2 
i: 3
D L D 
1 2 3 
i: 4
L D D L 
1 2 4 3 
i: 5
D L L D D 
1 2 4 5 3 
i: 6
L D D L D L 
1 2 4 3 6 5 
i: 7
D L L D D D L 
1 2 4 3 5 7 6 
i: 8
L D D L L D D L 
1 2 4 3 7 6 8 5 
i: 9
D L L D D L D D L 
1 2 4 3 7 8 5 9 6 
i: 10
L D D L L L L D D D 
1 2 4 3 7 5 9 6 10 8 
i: 11
D L L D D D L L L D D 
1 2 4 3 7 5 6 10 8 11 9 
i: 12
L D D L L L D D L L D D 
1 2 4 3 7 5 10 8 11 9 12 6 
i: 13
D L L D D D L D D L L D L 
1 2 4 3 7 5 10 11 9 12 6 13 8 
i: 14
L D D L L L D L D D L D D L 
1 2 4 3 7 5 10 9 12 6 13 8 14 11 
i: 15
D L L D D D L D L D L L D D L 
1 2 4 3 7 5 10 9 6 13 8 14 11 15 12 
i: 16
L D D L L L D L L D D L L D D D 
1 2 4 3 7 5 10 9 13 8 14 11 15 12 16 6 
i: 17
D L L D D D L D D L D D L L L D L 
1 2 4 3 7 5 10 9 13 14 11 15 12 16 6 17 8 
i: 18
L D D L L L D L L L L D D D L D D D 
1 2 4 3 7 5 10 9 13 11 15 12 16 6 17 8 18 14 
其中L 表示 LIVE， D表示DIE

通过表规律不难发现：

对于 m + 1,n 这个区间是没有操作的，因此前 m 个数的前半部分是以 m 开头，2 为公差递减到 1 或者 2 的等差数列，后半部分以 1,2 中剩余的那个开头，以 2 为公差递增到 **m − 1 **

前半部分长度为 (m + 1) / 2,后半长度为 m / 2

代码：

void JiuCherish(){
    int n,m;
    std::cin >> n >> m;
    std::string s;
    std::cin >> s;
    for(int i=0;i<n;i++) {
        if(s[i] == 'P') a[i + 1] = 1;
        else a[i + 1] = 0;
    }
    for(int i=m;i>=1;i-=2) {
        std::cout << 1 - a[i] << ' ';
    }
    if(m & 1) {
        for(int i=2;i<=std::min(m + 1,n);i+=2) {
            std::cout << a[i] << ' ';
        }
        for(int i=m+2;i<=n;i++) {
            std::cout << a[i] << ' ';
        }
    } else {
        for(int i=1;i<=m;i+=2) {
            std::cout << a[i] << ' ';
        }
        for(int i=m+1;i<=n;i++) {
            std::cout << a[i] << ' ';
        }
    }
}

J. 临场发挥

题意：

小x和室友一共 n 人玩电脑，总共有 n 台电脑供他们使用，一人一台，最开始，第 i 个人使用第 i 台电脑。

第 i 个人的能力值是 a_i ，小x和室友喜欢换来换去玩。

他们发现一个规律第 i 个人从第 x 台电脑换到了第 y 台电脑，那么第 i 个人的临场发挥值会增加 |x - y| * a_i 。现在他们可以重新任意分配一次电脑。问临场发挥值最多会增加多少？

数据范围：

$$2 \leq n \leq 2000 , 1 \leq a_i \leq 10^9$$

题解：区间dp

首先从贪心的角度来考虑，能力值大的应该往最两边放，能力值小的应该往中间放。

考虑到不是每次取的结果能使得结果达到最优的情况，通过从小到大排序，约定 dp[l] [r] 用 r - l + 1 个数填满了区间 [l,r] 的最大贡献，再考虑贪心的思想，可以得出转移方程。

$$dp[l][r] = max([dp[l + 1][r] + abs(l - a[i].id) * a[i].val],dp[l][r - 1] + abs(a[i].id - r) * a[i].val)$$

代码：

void JiuCherish(){
    int n;
    std::cin >> n;
    for(int i=1;i<=n;i++) {
        i64 val;
        std::cin >> val;
        a[i] = std::pair<i64,i64>(val,i);
    }

    std::sort(a + 1,a + n + 1);
    for(int len=1;len<=n;len++) {
        for(int l=1,r=l+len-1;r<=n;l++,r++) {
            dp[l][r] = std::max(dp[l + 1][r] + std::abs(l - a[len].se) * a[len].fi,dp[l][r - 1] + std::abs(r - a[len].se) * a[len].fi);
        }
    }

    std::cout << dp[1][n] << endl;
}

K.BanG Dream! It’s MyGO!!!!!

不玩邦邦，也不看Mygo，不会这题是不是也正常（x

题意：

koala想为最喜欢的乐团设计一个独特的徽章，这个徽章需要从网络图中找出一些特别的图案来代表乐团，比如选三条边连接到一起，具体来说，他对以下三种图案感兴趣：
三角形：由三条边构成的连通子图，这是一种经典的图案。
三芒星：四个点形成的图案，一个点连向其他三个点。
闪电折线：一种特别的折线，由四个点按顺序连接，即一条链。
koala想知道有多少种情况满足，你能帮帮他吗？

即给定一个无向图，你需要给出三条边的导出子图是连通的情况数量。

数据范围：

$$1 \leq n \leq 10^5,1 \leq m \leq 2\times 10^5$$

题解：图论，计数

三角形的计数是三元环计数问题。
三芒星简单，统计一下每个点的度数 du，然后用组合数就能算了。总个数是C（du,3）再求和。
闪电折线不能直接算出来。我们可以枚举中间那条边，然后两个端点的度数-1乘起来就是闪电折线和三角形*3的总个数。因为三角形个数可以算出来，那这个也就可以算了。

说实话，还是不懂。

代码：

int head[MAXN],ent;
struct edge{
    int v,nxt;
}e[MAXN<<2];
void add(int u,int v){
    e[++ent]={v,head[u]};
    head[u]=ent;
}
 
i64 cnt1,cnt2,cnt3;
bool vis[MAXN];
void triangle(){
    for(int u=1;u<=n;u++){
        for(int i=head[u];i;i=e[i].nxt)
            vis[e[i].v]=true;
        for(int i=head[u],v;i;i=e[i].nxt){
            v=e[i].v;
            for(int j=head[v],w;j;j=e[j].nxt){
                w=e[j].v;
                if(vis[w])cnt1++;
            }
        }
        for(int i=head[u];i;i=e[i].nxt)
            vis[e[i].v]=false;
    }
}
void JiuCherish(){
    std::cin >> n >> m;
    for(int i=1;i<=m;i++) {
        std::cin >> u[i] >> v[i];
        deg[u[i]]++;
        deg[v[i]]++;
    }
    for(int i=1;i<=m;i++) {
        cnt3 += (i64)(deg[u[i]] - 1) * (deg[v[i]] - 1);
        if(deg[u[i]] > deg[v[i]] || (deg[u[i]] == deg[v[i]] and u[i] > v[i])) std::swap(u[i],v[i]);
        add(u[i],v[i]);
    }
    for(int i=1;i<=n;i++) {
        cnt2 += (i64)deg[i] * (deg[i] - 1) * (deg[i] - 2) / 6;
    }
    triangle();
    cnt3 -= 3 * cnt1;
    std::cout << cnt1 + cnt2 + cnt3 << endl;
}

L.koala的程序

题意：

约瑟夫环问题(从输入输出不难看出)。

数据范围：

$$2 \leq n \leq 3 * 10^5,1 \leq k \leq 3 * 10^5$$

题解：线段树，树状数组，二分

原题，贴两个链接。

约瑟夫问题

oi-wiki约瑟夫问题

代码：

int bit[MAXN];  
int n,k;  
int sum(int i){  
    int s=0;  
    while (i>0){  
        s+=bit[i];  
        i-=(i&(-i));  
    }  
    return s;  
}  
void add(int i,int x){  
    while (i<=n){  
        bit[i]+=x;  
        i+=(i&(-i));  
    }  
}  
int binary_search(int id){  
    int l=0,r=n+1;  
    while (l<r){  
        int mid=(l+r)>>1;  
        if (sum(mid)<id)l=mid+1;  
            else r=mid;  
    }  
    return l;  
}  
void JiuCherish(){
    while (std::cin >> n >> k){  
        int id=1;  
        memset(bit,0,sizeof(bit));  
        for (int i=1;i<=n;i++)  
            add(i,1);  
        for (int i=1;i<=n-1;i++){  
            id=(id+k-2)%(n-i+1)+1;  
            int newid=binary_search(id);  
            printf("%d ",newid);  
            add(newid,-1);  
        }  
    }  
}

A. 装备二选一（一）

题意：

题解：数学、期望

代码：

B.百变吗喽

题意：

数据范围：

题解：模拟

代码：

C.16进制世界

题意：

数据范围：

题解：背包

代码：

D. 四散而逃

题意：

数据范围：

题解：模拟

代码：

E. 铃兰小姐是我们的光

题意：

数据范围：

题解：替罪羊树、lca

代码：

F. 追寻光的方向

题意：

数据范围：

题解：前缀和，st表，模拟

st表代码：

前缀和代码：

G.等公交车

题意：

数据范围：

题解：二分

代码：

H. 24点

题意：

数据范围：

题解：模拟，dfs

代码：

I.正义从不打背身

题意：

数据范围：

题解：打表

打表代码：

规律：

代码：

J. 临场发挥

题意：

数据范围：

题解：区间dp

代码：

K.BanG Dream! It’s MyGO!!!!!

题意：

数据范围：

题解：图论，计数

代码：

L.koala的程序

题意：

数据范围：

题解：线段树，树状数组，二分

代码：