新疆大学2025年新生赛

预计难度排名：G、L、I、E、K、J、D、B、F、H、A、C

G 签到题

思路：

标准输出。

std:

#include <bits/stdc++.h>
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout << "\"(某某某) 到此一游!\"" << "\n";
    return 0;
}

L 死亡圣器

思路：

化简公式可得：。

std:

#include <bits/stdc++.h>
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T;
    std::cin >> T;
    std::cout << std::fixed << std::setprecision(2);
    while (T--) {
        double r;
        std::cin >> r;
        std::cout << r * r * (sqrt(3.0) * 3 - M_PI) << "\n";
    }
    return 0;
}

I 走开，别做我

思路：

可以看出，最后变化成的字符串只有两种，要么 开头，要么 开头。那可以直接枚举出这两个字符串，然后依次遍历出结果，两种情况取最小值即可。如果两种情况都无法得到答案，输出 。

std:

#include <bits/stdc++.h>
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, ans1 = 0, ans2 = 0;
    std::cin >> n;
    std::string s, a, b;
    std::cin >> s;
    for (int i = 0; i < n; i++) {
        a += '0' + (i & 1);
        b += '0' + 1 - (i & 1);
    }
    for (int i = 0; i <= n - 1 - i; i++) {
        int j = n - 1 - i;
        if (s[i] != a[i] && s[j] != a[j]) {
            ans1++;
        } else if (!(s[i] == a[i] && s[j] == a[j])) {
            ans1 = 1e9;
        }
        if (s[i] != b[i] && s[j] != b[j]) {
            ans2++;
        } else if (!(s[i] == b[i] && s[j] == b[j])) {
            ans2 = 1e9;
        }
    }
    int ans = std::min(ans1, ans2);
    if (ans >= 1e9) {
        ans = -1;
    }
    std::cout << ans << "\n";
    return 0;
}

E 追猎光明的拈花佛陀

思路：

二维差分板子。

std:

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n + 2, vector<int>(n + 2, 0));
    for (int i = 0; i < m; i++) {
        int e, x1, y1, x2, y2;
        cin >> e >> x1 >> y1 >> x2 >> y2;
        a[x1][y1] += e;
        a[x1][y2 + 1] -= e;
        a[x2 + 1][y1] -= e;
        a[x2 + 1][y2 + 1] += e;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << a[i][j] << " \n"[j == n];
        }
    }
    return 0;
}

K 勇气是人类的赞歌

思路：

题中给出的数组其实是一个前缀和数组，从给出的数组中，我们拆一下前缀和，可以知道每个元素对 取余的模数，我们可以先整理一下 的数字，分为除三余零、除三余一、除三余二，然后遍历给每个位置上分数字。如果轮到某个位置上时，应该放的种类里面没有剩下的，就输出 。

std:

#include <bits/stdc++.h>
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n;
    std::cin >> n;
    std::vector<int> a, b(n);
    std::vector<std::vector<int>> c(3);
    for (int i = 0; i < n; i++) {
        std::cin >> b[i];
        c[(i + 1) % 3].push_back(i + 1);
    }
    int x = 0;
    for (int i = 0; i < n; i++) {
        x = (b[i] + 3 - x) % 3;
        if (!c[x].size()) {
            std::cout << -1 << "\n";
            return 0;
        }
        a.push_back(c[x].back());
        c[x].pop_back();
        x = b[i];
    }
    for (int i = 0; i < n; i++) {
        std::cout << a[i] << " \n"[i == n - 1];
    }
    return 0;
}

J 伊菲的数据结构

思路：

初始时每个间隔长度为 ，我们需要找到一个最高的间隔，令其长度变成 。

不难发现每个间隔高度为其左边最高的隔板和其右边最高的隔板中较小的一个的高度。

预处理一个最大后缀和即可。

std:

#include <bits/stdc++.h>
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, mx = 0, mxx = 0;
    long long ans = 0;
    std::cin >> n;
    std::vector<int> a(n), b(n), c(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    b[n - 1] = a[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        b[i] = std::max(b[i + 1], a[i]);
    }
    for (int i = 0; i < n; i++) {
        int x = std::min(mx, b[i]);
        ans += x;
        mxx = std::max(mxx, x);
        mx = std::max(mx, a[i]);
    }
    ans += mxx;
    std::cout << ans << "\n";
    return 0;
}

D 苦肉浊林的蠕动霸主

思路：

模拟。

std:

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<pair<int, int>> b(10, make_pair(-1, -1)); 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            char c = a[i][j];
            if (c >= '0' && c <= '9') {
                int num = c - '0';
                b[num] = make_pair(i, j);
            }
        }
    }
    string ops;
    cin >> ops;
    int x = 0, y = 0;
    bool ok = false; 
    for (char c : ops) {
        if (ok) break; 
        int nx = x, ny = y;
        if (c == 'L') ny--;
        else if (c == 'R') ny++;
        else if (c == 'U') nx--;
        else if (c == 'D') nx++;
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
            continue; 
        }
        if (a[nx][ny] == '#') {
            x = nx; y = ny;
            ok = true; 
            break;
        } else if (a[nx][ny] == '.') {
            x = nx; y = ny; 
        } else { 
            x = nx; y = ny; 
            int p = a[x][y] - '0';
            int q = p + 1;
            if (q > 9) {
                continue; 
            }
            if (b[q].first == -1) {
                continue;
            }
            x = b[q].first;
            y = b[q].second;
        }
    }
    cout << x + 1 << " " << y + 1 << endl;
    return 0;
}

B 爱恨此消彼长

思路：

不难发现数据范围很小，可以借助二进制暴力枚举所有情况。取所有情况的最大值即可。

std:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ll n, ans = 0;
    cin >> n;
    vector<pair<ll, ll>> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].first >> a[i].second;
    }
    for (int i = 0; i < (1 << n); i++) {
        vector<ll> b;
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) {
                b.push_back(a[j].second);
            } else {
                b.push_back(a[j].first);
            }
        }
        ll cur = 0, cnt = 0;
        for (ll val : b) {
            if (val > cur) {
                cnt++;
                cur = val;
            }
        }
        ans = max(ans, cnt);
    }
    cout << ans << "\n";
    return 0;
}

F 伊菲的飞船设计

思路：

我们假定 ，想象 是这个长方形的高度。

，可以发现，两边的格子必须选，中间要选 个格子，也就是说 至少为 。现在，选中两端两个格子之后，只剩下了 个格子，先选上面，有 种情况，下面可以在剩下的 个格子中选一个 ，有 种情况，也就是说，答案为 。

，现在 ，方案一定存在，讨论：

选择 条边：

选择 条边，但恰好只有一个角落冲突： （确定 个角落冲突，会占用两条相邻边，选择另外的两条边共有 种方案，其中有 种方案会导致另外的两条边选择同一个格子，所以是 。这样的角落有 个，所以是 ）

选择 条边，但恰好有两个角落冲突： （这两个角落必须相对，那么只有两种情况）

选择 条边，有三个及以上的角落冲突：0

答案就是：

懒得求二次剩余，所以 没取余也算你过啦（

std:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve() {
	ll n, m, mod = 998244353;
	cin >> n >> m;
	if (n == 1 && m == 1) {
		cout << 0 << "\n";
	} else if (n == 1 || m == 1) {
		cout << (max(n, m) - 2) * (max(n, m) - 3) % mod << "\n";
	} else {
		cout << ((n * m - 4) % mod * n % mod * m % mod + 2) % mod << "\n";
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int _ = 1;
	cin >> _;
	while (_--) {
		solve();
	}

	return 0;
}

H AFPS

思路：

注意到这是一个正权图，考虑这个算法的反松弛过程：

一旦存在一条某个点出发回到自己的路径（即环路），注意到这条路径的权值（其上所有边的权值和）一定为正，因此沿着这条路径一定会发生一次反松弛，而再次到达之后又会走到这条环路上，结果就是算法无法停机。

因此，如果 号结点能够到达一个环（也就是其所在的连通分量中存在环），答案一定是 。

否则， 号结点所在连通分量一定是树，此时距离数组分为两部分：和 号结点在同一连通分量的点，其值为以 为根的树的深度（到 号结点的距离）；其他点由于未被访问到，值为 。

因此找环后验证即可。一种简单的方式是直接 DFS，时间复杂度线性。

也可以在打访问标记的基础上直接使用题目给出的伪代码，注意当有解时这个算法退化为一般树上 BFS，时间复杂度也是线性。

std:

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+11;
using ll=long long;
void solve()
{
    int n,m;
    cin>>n>>m;
    vector<vector<pair<int,int> > > G(n+3);
    vector<ll> evs(m+3,0);
    vector<int> vis(n+3,0);
    vector<ll> d1(n+3,-1),d2(n+3,0);
    d1[1]=0;
    auto dfs=[&](auto &&self,int u,int eid)->bool
    {
        if(vis[u]) return 0;
        vis[u]=1;
        for(auto [v,nxid]:G[u]) if(eid!=nxid)
        {
            if(vis[v]) return 0;
            d1[v]=d1[u]+evs[nxid];
            if(!self(self,v,nxid)) return 0;
        }
        return 1;
    };
    for(int i=1,iu,iv;i<=m;++i)
    {
        ll ival;
        cin>>iu>>iv>>ival;evs[i]=ival;
        G[iu].push_back({iv,i});
        G[iv].push_back({iu,i});
    }
    bool ok=dfs(dfs,1,-1);
    for(int i=1;i<=n;++i) cin>>d2[i];
    if(ok) for(int i=1;i<=n;++i) if(d1[i]^d2[i])
    {
        ok=0;break;
    }
    if(!ok) cout<<0<<'\n';else cout<<1<<'\n';
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int t;
    cin>>t;
    while(t--) solve();
    return 0;
}

A 余命六十日

思路：

注意到题目给出的限制十分恶心（至少有一对的处理很麻烦，需要容斥），考虑计算补集，然后用全集减去补集。

全集很容易计算，每个位置只有选和不选两种，数量为 。

考虑计算补集，也就是不存在两个下标 满足前缀 是前缀 的后缀的下标集合数量。

注意如果要满足前缀 是前缀 的后缀，首先需要满足 ，也就是前缀 是前缀 的前缀。

因此，如果满足这一条件， 一定是 的相等真前后缀，也就是 Border。

问题转化为：求有多少个下标集合满足其中不存在两个下标 满足 是 的 Border。

注意到 Border 性质：一个字符串的最长 Border 的最长 Border 是其次长 Border（证明可以使用反证法，这也是 KMP 算法的重要性质），字符串的所有前缀按最长 Border 关系可以构成一棵 个结点的有根树。

方法为：通过 KMP 等算法求出每个前缀 的最长 Border 记为 ，每个结点 将 作为父亲，即可得到一棵以 号结点为根的有根树，结点 的所有祖先都是它的 Border。该树也被称为 KMP Fail 树。

那么，问题转化为：在一棵有根树上选出一个点集使得任意两点都没有祖先后代关系，求方案数量。

考虑动态规划：设 为结点 的子树中，强制不选结点 的答案。

初始状态为 ，转移为 ，答案即为 。

实际上，我们并不需要显式地建树：倒序地从 到 枚举 ，按 转移即可，原因留给读者自行考虑。

答案为 ，注意取模。

时间复杂度 。

std:

#include<bits/stdc++.h>

using i64 = long long;
const int mod = 998244353;

std::vector<int> Get(std::string s) {
	int n = s.length();
	std::vector<int> a(n + 1, 0);
	for (int i = 2; i <= n; i++) {
		int j = a[i - 1];
		while (j && s[j] != s[i - 1]) {
			j = a[j];
		}
		if (s[i - 1] == s[j]) {
			j++;
		}
		a[i] = j;
	}
	return a;
}

void solve() {
	std::string s;
	std::cin >> s;
	int n = s.size();
	int ans = 1;
	std::vector a = Get(s);
	std::vector<i64> dp(n + 1, 1);
	for (int i = n; i > 0; i--) {
		ans = ans * 2 % mod;
		dp[a[i]] = (dp[a[i]] * (dp[i] + 1) % mod) % mod;
	}
	ans = (ans - dp[0] + mod) % mod;
	std::cout << ans << "\n";
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	
	int _ = 1;
	std::cin >> _;
	while (_--) {
		solve();
	}
	
	return 0;
}

C 伊菲的复习

思路：

题意概括： 个点，每个点有权值 ，选择一个点有 的贡献，最后减去选择点乘积质因子和的代价，使贡献最大。

最大权闭合子图板子，桶排去重，源点往每个点建容量为 该点数量 的正权边，然后，对于每个点，往它们的每个质因子建容量无限的边，最后，每个质因子往汇点建容量为质因子大小的负权边（图意义上值还是正的）。用 减去最大流即是答案。

把一个选点方案与它们影响到的质因子还有源点记为一个闭合子图 ，那么 的权值 就是 的正权减去负权。

到除 以外的所有点构成的子图 的割 就是 的负权加上 的正权（具体为 里面的负权点与汇点，源点与 的正权点）。

的正权加上 的正权，也就是说 正权和减去 。要使 最大，因为正权和不变，所以让 最小，也就是最小割。

根据最大流最小割原理，最大流等于最小割，也就是上面那玩意。

题外话：这道题本来 是 的，不知道是因为每个左部点连右部点的边很少还是什么，在自己出的任何样例下跑的飞快，但证明不了正确性改成了 ，有没有佬会证QAQ。

std:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int M = 1e6 + 10;
template<class T>
struct MaxFlow {
	struct Edge {
		int nxt, to, cap, ycap, sta, cost;
	};
	int n, cnt, s, t;
	vector<Edge>e;
	vector<int>h, head;
	MaxFlow();
	MaxFlow(int n) {
		init(n);
	}
	MaxFlow(int n, int m) {
		init(n, m);
	}
	void init(int n) {
		this->n = n;
		e = vector<Edge>((this->n + 1) << 1);
		head = vector<int>((this->n + 1) << 1, -1);
		cnt = -1;
	}
	void init(int n, int m) {
		this->n = n;
		e = vector<Edge>((m + 1) << 1);
		head = vector<int>((m + 1) << 1, -1);
		cnt = -1;
	}
	void add(int u, int v, int w) {
		e[++cnt] = {head[u], v, w, w, u, 0};
		head[u] = cnt;
		e[++cnt] = {head[v], u, 0, 0, v, 0};
		head[v] = cnt;
	}
	bool bfs() {
		h = vector<int>(n + 2, -1);
		h[s] = 0;
		queue<int>qu;
		qu.push(s);
		while (!qu.empty()) {
			int u = qu.front();
			qu.pop();
			for (int i = head[u]; i != -1; i = e[i].nxt) {
				int v = e[i].to;
				if (h[v] == -1 && e[i].cap) {
					h[v] = h[u] + 1;
					qu.push(v);
				}
			}
		}
		return h[t] != -1;
	}
	int dfs(int u, int f) {
		if (u == t)return f;
		int w, used = 0;
		for (int i = head[u]; i != -1; i = e[i].nxt) {
			int v = e[i].to;
			if (h[v] == h[u] + 1 && e[i].cap) {
				w = dfs(v, min(f - used, e[i].cap));
				e[i].cap -= w;
				e[i ^ 1].cap += w;
				if ((used += w) == f)return f;
			}
		}
		if (!used)h[u] = -1;
		return used;
	}
	int max_flow(int s, int t) {
		for (int i = 0; i <= cnt; i++)e[i].cap = e[i].ycap;
		int ans = 0;
		this->s = s;
		this->t = t;
		while (bfs())ans += dfs(s, 0x3f3f3f3f3f3f);
		return ans;
	}
};
int n, d = 0, js = 0, p[M], cnt = 0, kc = 0, a[M], sl[M], v, dd[M];
bool e[M];
MaxFlow<int>mf(1);
void pr(int n) {
	cnt = 0;
	for (int i = 1; i <= n; i++)e[i] = 0;
	for (int i = 2; i <= n; i++)if (!e[i]) {
			p[++cnt] = i;
			bool fl = 0;
			for (int j = 1; j * i <= n; j++) {
				e[i * j] = 1;
				if (a[i * j]) {
					fl = 1;
					mf.add(kc + a[i * j], dd[cnt], 1e12);
				}
			}
			if (fl)mf.add(dd[cnt], kc + d + 1, i);
		}
}
void pr1(int n) {
	cnt = 0;
	for (int i = 1; i <= n; i++)e[i] = 0;
	for (int i = 2; i <= n; i++)if (!e[i]) {
			cnt++;
			bool fl = 0;
			for (int j = 1; j * i <= n; j++) {
				e[i * j] = 1;
				if (a[i * j]) {
					fl = 1;
					js++;
				}
			}
			if (fl)dd[cnt] = ++kc;
		}
}
void solve() {
	cin >> n >> v;
	int si0 = 0;
	for (int i = 1; i <= n; i++) {
		int k;
		cin >> k;
		if (a[k] == 0 && k > 1)a[k] = ++d;
		if (k > 1)sl[k]++;
		if (k == 0)si0 = 1;
	}
	if (si0) {
		cout << n*v << "\n";
		return;
	}
	pr1(1e6);
	mf.init(kc + d + 2, js + kc + d + 10);
	for (int i = 2; i <= 1e6; i++)if (a[i])mf.add(0, kc + a[i], sl[i]*v);
	pr(1e6);
	cout << v*n - mf.max_flow(0, kc + d + 1) << "\n";
}
signed main() {
	ios::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
	solve();
}