题面：

I - Left Shifting

签到题，从左往右检查字符串中有没有相邻两个一样的位置，注意有可能一开始就已经是首尾相同的。

1
2
3
4
5
6
7
8
void solve() {
    string s;
    cin>>s;
    if(s.front() == s.back()) return cout<<0<<endl,void();
    for(int i = 1;i<si(s);++i)
        if(s[i] == s[i-1]) return cout<<i<<endl,void();
    cout<<-1<<endl;
}

A - Printer

一道很明显的二分题，二分最后的时间，固定时间根据能产生多少的试题来左移或者右移mid，注意直接统计能产生的试题个数的时候可能会爆longlong，可以写int128或者check的时候如果大于k就直接返回true。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
using i128 = __int128;
// 自定义int128输出，这道题不需要
// std::ostream &operator<<(std::ostream &os, i128 n) {
// 	std::string s;
// 	while (n) {
// 		s += '0' + n % 10;
// 		n /= 10;
// 	}
// 	std::reverse(s.begin(), s.end());
// 	return os << s;
// }


/*
第 i 台打印机将重复进行以下工作计划：持续工作
ti × li 秒，然后停机 wi 秒
*/

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> t(n), l(n), w(n);
    for (int i = 0; i < n; ++i) {
        cin >> t[i] >> l[i] >> w[i];
    }
    int left = 0, r = 2e18+5;

    auto check = [&](int x)->bool{
        i128 cnt = 0;
        for (int i = 0; i < n; ++i) {
            int temp = x / (t[i] * l[i] + w[i]);
            int rest = x - temp * (t[i] * l[i] + w[i]);
            if (rest > t[i]*l[i]) {
                cnt +=  (temp + 1) * l[i];
            } else {
                cnt += temp * l[i] + rest / t[i];
            }
        }
        return cnt >= k;
    };

    while (left + 1 < r) {
        int mid = (left + r) >> 1ll;
        if (check(mid)) r = mid;
        else left = mid;
    }
    cout << left + 1 << endl;
}

F - Divide the Sequence

观察式子$ \sum i\times S_i $可以理解为越靠后的区间累积的越多，设最后m段的元素总和为$ p_m $，则变形一下原式可以得到$ \sum p_i $, 所以实际上就是按顺序从大到小选后缀和累加就行，注意第一个位置的后缀和（即所有数的和）不能参与排序因为是只有一个区间必须要一开始就先选。

1
2
3
4
5
6
7
8
9
10
11
12
13
void solve() {
    int n,ans = 0;
    cin>>n;
    vector<int> a(n+1,0ll),suf(n+1);
    for(int i = 0;i<n;++i) cin>>a[i];
    for(int i = n-1;i>=0;--i)
        suf[i] += suf[i+1] + a[i];
    sort(suf.begin() + 1,suf.end() - 1,greater());
    for(int i = 0;i<n;++i){
        ans += suf[i];
        cout<<ans<<" \n"[i==n-1];
    }
}

K - Matrix

因为提供了2n个数，对于一个矩阵来说很难不想到是一行一列或者是一斜行，构造的时候可以主对角线从1到n依次填进去，然后左上角弄一个2*2的矩阵，这个矩阵的四个元素都不一样，其他每一行每一列除主对角线上的都是一样的数，这样就能保证除了左上角那个矩阵是对角四个元素都不一样其他子矩阵的右上和左下一定是一样的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 比如长这样的
// 1 5 7 8
// 6 2 7 8
// 7 7 3 8
// 8 8 8 4

int a[55][55];

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) a[i][i] = i;
    a[2][1] = n + 1, a[1][2] = n + 2;
    for (int i = 3; i <= n; ++i) {
        for (int j = 1; j < i; ++j)
            a[i][j] = n + i;
        for (int j = 1; j < i; ++j)
            a[j][i] = n + i;
    }
    cout << "Yes" << endl;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            cout << a[i][j] << " \n"[j == n];
}

C - Colorful Segments 2

因为和顺序无关，先想到排序。

按左端点从大到小排序，枚举每条线段然后用小根堆贪心，找前面有几个是包含当前这条线段的。因为已经按照左端点排序了所以如果前面有右端点在这条线段的左端点之前一定是不干扰的，如果右端点在这条线段左端点之后那么一定是被干扰的，并且因为是排了序所以直接弹出不干扰这条线的右端点对后面的线段也不会有影响，最后留在堆里的一定是和这条线段有重叠的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const int mod = 998244353;

void solve() {
    int n,k;
    cin>>n>>k;
    vector<PII> line(n);
    for(int i = 0;i<n;++i)
        cin>>line[i].fi>>line[i].se;
    sort(all(line));
    priority_queue<int,vector<int>,greater<int>> r;
    int ans = 1;
    for(int i = 0;i<n;++i){
        while(!r.empty() && r.top()<line[i].fi){
            r.pop();
        }
        (ans *= (k - si(r)))%=mod;
        r.push(line[i].se);
    }
    cout<<ans<<endl;
}

J - Colorful Spanning Tree

可以这样理解相同颜色的点：选出k-1（k为相同颜色点的个数）个找和这个颜色组合权值最小的一个点链接，全部连这一个点，这样就算最小的是自身也没有问题，就相当于那一个点是附带了这k-1个点的点集，对所有的点集跑一遍最小生成树即可保证得到的生成树是最小的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
void solve() {
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i = 0;i<n;++i) cin>>a[i];
    vector<vector<int>> mat(n);
    int ans = 0;
    // 输入，找最小的
    for(int i = 0;i<n;++i){
        int minn = 1e9;
        for(int j = 0,t;j<n;++j){
            cin>>t;
            mat[i].push_back(t);
            minn = min(minn,t);
        }
        ans += minn*(a[i]-1);
    }
    // 连边
    vector<array<int,3>> edge;
    for(int i = 0;i<n;++i){
        for(int j = i;j<n;++j){
            edge.push_back({mat[i][j],i,j});
        }
    }
    // kruskal
    vector<int> par(n);
    for(int i = 0;i<n;++i) par[i] = i;
    function<int(int x)> find = [&](int x)->int{
        return par[x] == x ? par[x] : par[x] = find(par[x]);
    };

    function<int()> krus = [&]()->int{
        sort(all(edge));
        int ret = 0;
        for(auto [w,u,v] : edge){
            int pa = find(u),pb = find(v);
            if(pa == pb) continue;
            par[pa] = pb;
            ret += w;
        }
        return ret;
    };

    ans += krus();
    cout<<ans<<endl;

}

D - Hero of the Kingdom

看范围T是500，其他都是1e9的范围，那么如果每轮能在根号范围内处理那么就是一个比较合理的处理，所以要考虑在暴力枚举的时候优化一些不必要重复的操作。注意到如果当前是买x袋面粉，那么如果想要买x+1袋面粉则可能需要跑好几轮，所以如果能计算出购买x袋面粉的轮次一定是一种优化，考虑极端情况是进行k种交易，那么假设买一次物品最少是2s，则有$ (1+2+…+k)\times2 \le t $，得出k大概是根号级别的，可以通过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void solve() {
	int p, a, b;
	int q, c, d;
	int m, t;
	cin >> p >> a >> b;
	cin >> q >> c >> d;
	cin >> m >> t;
	int rest = t;
	// 特判一次都不行的时候
    if(m<p) return cout<<m<<endl,void();
	
	while (true) {
		int x = m / p;
		int epo = ((x + 1) * p - m - 1) / ((q - p) * x) + 1;
		// 处理买m/p袋一共会跑几轮
        epo = min(rest / (a*x + b + c*x + d), epo);
		m += epo*x*(q-p);
		rest -= epo*(a*x + b + c*x + d);
        // 一次都买不了就先结束
		if(rest < (a*(x+1) + b + c*(x + 1) + d))break;
	}
//	特判最后一轮
	int maxn = (rest - b - d)/(a+c);
	m += max(maxn*(q-p),0ll);		
	cout<<m<<endl;
}