引言
非常友好的一次新生赛，我能写出来的都不是什么难题，主要考查平常算法的积累，熟练度。
A 王子公主请做此题
一个经典的染色题，注意到题目说某个格子相邻的格子颜色不一样，对应到树的结构应该是.
代码:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define i64 long long
#define pf push_front
#define pb push_back
#define lowbit(x) (x & (-x))
const int inf = 1e9, N = 2e5 + 10, mod = 998244353;
const long long INF = 1e18;
const double pi = 3.1415926535;
vector<vector<int>>g(N), t(N);
int a[N], col[N], c[N];
bool f = true;
void dfs(int u, int fa) {
for (int v : g[u]) {
if (v == fa)
continue;
if (col[v] and col[v] != 3 - col[u]) {
f = false;
}
if (c[a[v]] != 0 and c[a[v]] != 3 - col[u]) {
f = false;
}
col[v] = 3 - col[u];
c[a[v]] = 3 - col[u];
dfs(v, u);
}
}
void solve() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
if (a[i] == a[1]) {
col[i] = 1;
}
}
c[a[1]] = 1;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
dfs(1, 1);
cout << (f ? "Yes" : "No") << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int _ = 1; //cin >> _;
while (_--)
solve();
return 0;
}
这里我的思路是先把所有编号为的节点染色为1，然后以1为根节点遍历一遍树，根据要求，节点u与其子节点v颜色必然不一致，在dfs过程中判断一下染色是否发生冲突，只要冲突让
即可
B 育成马娘选择中！
签到题没什么好说的
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define i64 long long
#define pf push_front
#define pb push_back
#define lowbit(x) (x & (-x))
const int inf = 1e9, N = 2e5, mod = 998244353;
const long long INF = 1e18;
const double pi = 3.1415926535;
void solve() {
int n, m;
cin >> n >> m;
int p = 0;
while (m > n) {
m -= n;
}
cout << m << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int _ = 1; //cin >> _;
while (_--)
solve();
return 0;
}
C 杜教筛与min_25筛求莫比乌斯函数与个数函数的狄利克雷卷积——??函数的前缀和
诈骗题，题面太长了，懒得看了直接看后面一句话,奈何本人英语不好，wa了一发
代码:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define i64 long long
#define pf push_front
#define pb push_back
#define lowbit(x) (x & (-x))
const int inf = 1e9, N = 2e5, mod = 998244353;
const long long INF = 1e18;
const double pi = 3.1415926535;
void solve() {
cout << "euler";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int _ = 1; //cin >> _;
while (_--)
solve();
return 0;
}
D 糖完了
真的糖完了，看到这题我一眼就是求缩点，然后在求入度为0的点的个数就解决了，于是.....我忘记了
模板，比赛时wa了2发才写出来，背模板还是太难了
代码:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define i64 long long
#define pf push_front
#define pb push_back
#define lowbit(x) (x & (-x))
const int inf = 1e9, N = 2e5, mod = 998244353;
const long long INF = 1e18;
const double pi = 3.1415926535;
int n, tim, vis[250], scc;
vector<vector<int>>g(250), gra(250);
int dfn[250], low[250], col[250], deg[250];
stack<int>st;
void tarjan(int u) {
dfn[u] = low[u] = ++tim;
vis[u] = 1;
st.push(u);
for (int v : g[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (vis[v]) {
low[u] = min(low[u], low[v]);
}
}
if (dfn[u] == low[u]) {
scc++;
int t = 0;
do {
t = st.top();
st.pop();
vis[t] = 0;
col[t] = scc;
} while (t != u);
}
}
void solve() {
cin >> n;
for (int i = 1; i <= n; ++i) {
int k;
vector<int>tx(n + 1);
cin >> k;
for (int j = 0; j < k; j++) {
int x;
cin >> x;
if (tx[x])
continue;
tx[x] = 1;
g[i].pb(x);
}
}
for (int i = 1; i <= n; i++) {
if (!dfn[i]) {
tarjan(i);
}
}
for (int u = 1; u <= n; u++) {
for (int v : g[u]) {
if (col[v] != col[u]) {
gra[col[u]].pb(col[v]);
// cout << "q\n";
deg[col[v]]++;
}
}
}
// cout << "q" << scc << "\n";
int ans = 0;
for (int i = 1; i <= scc; i++) {
if (!deg[i]) {
ans++;
}
}
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int _ = 1;
//cin >> _;
while (_--)
solve();
return 0;
}
E 是非常暴力dfs求解
F 文化推演
简单讲解一下题意，这里给你个物品，每个物品有个数量
,我们要求从中任选
个物品的贡献之和，贡献定义为将这
个物品放在展台上所需要的最少展台数。关于展台有两个约束,一个展台最多只能放两个，且放两个物品时，这两个物品的种类不能一样。我们先思考这个最少展台数怎么求。假定你选了
个物品，物品总和为
,这
个物品中最大值是mx。首先由于展台上的物品必须各不相同，所以至少需要mx个展台，考虑剩下展台怎么放,
显然，就只需要mx个就搞定了。如果
呢，手玩一组样例发现我们，结果是
.这是一个很经典的贪心思想，感兴趣的同学可以写这个气球题
考虑数据范围
,定义一个状态
,表示前
种物品,总和为
的方案数
显然可以推出状态转移方程,
+=
,求解过程中我们始终让
为方案中的
,所以先对a数组排序
初始状态为
= 1
代码:
#include <bits/stdc++.h>
#define lowbit(x) (x & - (x))
#define pii pair<int,int>
#define pil pair<int,long long>
#define pli pair<long long,int>
#define pss pair<string,string>
#define pll pair<long long,long long>
#define pdd pair<double,double>
#define fir first
#define sec second
#define MP make_pair
#define pb push_back
#define pf push_front
#define i64 long long
#define i128 __int128_t
#define ull unsigned long long
#define ld long double
#define ll long long
using namespace std;
const int N = 3e5+100,M = 1e9,inf = 1e9,MOD=1e9+7,mod=998244353;
const long long INF = 1e18;
const double pi = 3.1415926535897932385,eps = 1e-9;
i64 dp[5005][5005];
int a[5005];
void solve(){
int n; cin >> n;
int sum = 0, mx = 0;
for (int i=1; i<=n; i++){
cin >> a[i];
sum += a[i];
}
sort(a+1,a+1+n);
dp[0][0] = 1; i64 ans = 0;
for (int i=1; i<=n; i++){
for (int j=0; j<=sum; j++){
dp[i][j] = dp[i-1][j];
if (j >= a[i]){
ans = (ans + (j+a[i]+1)/2*dp[i][j]+mod)%mod;
}
else {
ans = (ans + a[i]*dp[i][j]+mod)%mod;
}
if (j >= a[i]){
dp[i][j] = (dp[i][j] + dp[i-1][j-a[i]]+mod)%mod;
}
}
}
cout << ans << "\n";
}
int main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int _ = 1; //cin >> _;
while(_--) solve();
return 0;
}
注意运算过程要取模
G 竞技场参赛中！
模拟题没什么好说的，总体思路是模拟题目求解敌我速度，算是中等偏下的模拟吧,不豪赤
代码:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define i64 long long
#define pf push_front
#define pb push_back
#define lowbit(x) (x & (-x))
const int inf = 1e9, N = 2e5, mod = 998244353;
const long long INF = 1e18;
const double pi = 3.1415926535;
bool check(string s, string ty1, int x, int Len, int m, int l, int cnt) {
if (x == 1)
return true;
if (x == 2 and s == "Classic")
return true;
if (x == 3 and (ty1 == "Qian" or ty1 == "Zhong") and Len - l >= 800)
return true;
if (x == 4 and ty1 == "Qian" and s == "Mile")
return true;
if (x == 5 and ty1 == "Hou")
return true;
if (x == 6 and ty1 == "Hou" and s == "Long")
return true;
if (x == 7 and ty1 == "Zhong")
return true;
if (x == 8 and cnt >= 3)
return true;
if (x == 9 and s == "Classic")
return true;
if (x == 10 and s == "Mile")
return true;
if (x == 11 and s == "Hou")
return true;
return false;
}
int get(int x) {
if (x == 1)
return 500;
else if (x == 2)
return 800;
else if (x == 3)
return 2000;
else if (x == 4)
return 1200;
else if (x == 5)
return 800;
else if (x == 6)
return 1200;
else if (x == 7)
return 800;
else if (x == 8)
return 1000;
else
return -800;
}
void solve() {
string type;
cin >> type; // 赛道类型
int B = 0, M, L, Len;
if (type == "Mile") {
M = 267;
L = 1067;
Len = 1600;
} else if (type == "Classic") {
M = 333;
L = 1333;
Len = 2000;
} else {
M = 533;
L = 2133;
Len = 3200;
}
vector<int>veca(5), vecb(5);
for (int i = 0; i < 5; i++)
cin >> veca[i]; // a属性
// 速度0 耐力1 力量2 意志3 智力4 0-4
string sa, sb;
cin >> sa; // a跑法
int n, t;
cin >> n; // a技能数
vector<int>a(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i]; // 技能编号
for (int i = 0; i < 5; i++)
cin >> vecb[i];
cin >> sb;
cin >> t;
vector<int>b(t + 1);
for (int i = 1; i <= t; i++) {
cin >> b[i];
}
i64 va = veca[0], vb = vecb[0]; // a b初始速度
// cout << va << " " << vb << "\n";
if (type == "Mile") {
if (veca[1] < 600) {
va -= 500;
}
if (vecb[1] < 600)
vb -= 500;
} else if (type == "Classic") {
if (veca[1] < 800)
va -= 500;
if (vecb[1] < 800)
vb -= 500;
} else {
if (veca[1] < 1000)
va -= 500;
if (vecb[1] < 1000)
vb -= 500;
}
// cout << va << " " << vb << "\n";
if (sb == "Qian") {
if (vecb[2] < 800)
vb -= 500;
} else if (sb == "Zhong") {
if (vecb[2] < 1000)
vb -= 500;
} else {
if (vecb[2] < 1200)
vb -= 500;
}
if (sa == "Qian") {
if (veca[2] < 800) {
va -= 500;
// cout << "q\n";
}
} else if (sa == "Zhong") {
if (veca[2] < 1000)
va -= 500;
} else {
if (veca[2] < 1200)
va -= 500;
}
// cout << va << " " << vb << "\n";
for (int i = 1; i <= n; i++) {
if (check(type, sa, a[i], Len, M, L, n)) {
if (a[i] >= 1 and a[i] <= 8) {
va += get(a[i]);
// cout << a[i] << "q\n";
if (veca[3] >= 1100) {
// cout << "ttt\n";
va += 500;
}
}
}
}
// cout << va << "\n";
for (int i = 1; i <= t; i++) {
if (check(type, sb, b[i], Len, M, L, t)) {
if (b[i] >= 1 and b[i] <= 8) {
vb += get(b[i]);
// cout << b[i] << "w\n";
if (vecb[3] >= 1100) {
vb += 500;
}
}
}
}
for (int i = 1; i <= n; i++) {
if (check(type, sa, a[i], Len, M, L, n)) {
if (a[i] >= 9 and a[i] <= 11) {
vb += get(a[i]);
if (veca[4] >= 1100) {
vb -= 500;
}
}
}
}
for (int i = 1; i <= t; i++) {
if (check(type, sb, b[i], Len, M, L, t)) {
if (b[i] >= 9 and b[i] <= 11) {
// cout << b[i] << "w\n";
va += get(b[i]);
if (vecb[4] >= 1100) {
va -= 500;
}
}
}
}
// cout << va << " " << vb << "\n";
cout << (va > vb ? "Manbo" : "Muri") << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int _ = 1; //cin >> _;
while (_--)
solve();
return 0;
}
H 银牌之梦
没什么好说的构造一个9行5列的矩阵就好了，特解还是比较好想的，在纸上画个图玩一玩填数字游戏就搞定了。注意到3个要求1.0 1 2数量相同(赛时没看到wa了一发) 2.不存在>=3个连续的相同的数字出现 3.每个数字在八联通的基础下是一个连通块
代码:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define i64 long long
#define pf push_front
#define pb push_back
#define lowbit(x) (x & (-x))
const int inf = 1e9,N =2e5,mod = 998244353;
const long long INF = 1e18;
const double pi = 3.1415926535;
void solve(){
cout << "01012\n";
cout << "10121\n";
cout << "10012\n";
cout << "01121\n";
cout << "10212\n";
cout << "02021\n";
cout << "20212\n";
cout << "02021\n";
cout << "20200";
}
int main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int _ = 1; //cin >> _;
while(_--)solve();
return 0;
}
I 白垩之子
遗憾题，赛后多加一个特判就过了
总结一下题意,给你个点，每个点有个对应的符文
，在给你
条边,u v相连如果
!=
的话，对于集合
就应该包含
,对于v也是如此。所以问题就变成了:枚举每一个符文c,把所有
的点i相连的点v的符文即
加入到
中，当然保证
,这里直接用set处理。其实这样看是一个简单题，纯粹的枚举，奈何我赛时没想到
为0的情况，导致枚举到了不存在的符文。
代码:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define i64 long long
#define pf push_front
#define pb push_back
#define lowbit(x) (x & (-x))
const int inf = 1e9, N = 1e6 + 100, mod = 998244353;
const long long INF = 1e18;
const double pi = 3.1415926535;
int k[N];
vector<vector<int>>g(N), gra(N);
void solve() {
int n, m;
cin >> n >> m;
int tmx = 0;
for (int i = 1; i <= n; i++) {
cin >> k[i];
tmx = max(tmx, k[i]);
g[k[i]].pb(i);
}
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
gra[u].pb(v);
gra[v].pb(u);
}
int ans = inf, mx = -1;
for (int c = 1; c <= tmx; c++) {
set<int>se;
if (g[c].size() == 0)continue;
for (int u : g[c]) {
for (int v : gra[u]) {
if (k[v] == c)
continue;
se.insert(k[v]);
}
}
int cnt = se.size();
if (cnt > mx) {
ans = c;
mx = cnt;
}
}
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int _ = 1; //cin >> _;
while (_--)
solve();
return 0;
}
注意特判的情况,复杂度是
J 嘉豪的爱希批希
模拟题意即可，这题因为赛时数据有问题，可能卡掉了一部分同学。
记录一个值表示当前天数应该的训练量，如果
就变成
否则就
代码:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define i64 long long
#define pf push_front
#define pb push_back
#define lowbit(x) (x & (-x))
const int inf = 1e9, N = 2e5, mod = 998244353;
const long long INF = 1e18;
const double pi = 3.1415926535;
void solve() {
i64 n, x, y, k;
cin >> n >> x >> y >> k;
i64 now = 1, day = 0;
i64 sum = 0;
bool f = false;
while (sum < n) {
day++;
if (now >= x) {
f = true;
}
if (f) {
sum += y;
continue;
}
sum += now;
now *= k;
}
cout << day << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int _ = 1; //cin >> _;
while (_--)
solve();
return 0;
}
K 小果的数组
为数不多的思维题，这个题觉得还是非常有趣的，首先要明白是什么。观察到如果我们选择
个数去用
改变数组，那就可以把这
个数都变成
，此时产生的和为
。题目让我们选一个子序列，很容易发现其实你可以随便选，基于贪心原则，我们肯定选前
个最小的数求把这
个数操作，再把剩下的数求和。对原数组去排序枚举选择前
个数操作能产生的和，即求
,用前缀和预处理一下排序后的数组
代码:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define i64 long long
#define pf push_front
#define pb push_back
#define lowbit(x) (x & (-x))
const int inf = 1e9, N = 2e5, mod = 998244353;
const long long INF = 1e18;
const double pi = 3.1415926535;
void solve() {
int n;
cin >> n;
vector<i64>a(n + 1), pre(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i];
sort(a.begin() + 1, a.end());
for (int i = 1; i <= n; i++)
pre[i] = pre[i - 1] + a[i];
i64 ans = 0;
for (int i = 0; i <= n; i++) {
i64 res = 1ll * i * i + pre[n] - pre[i];
ans = max(ans, res);
}
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int _ = 1;
cin >> _;
while (_--)
solve();
return 0;
}
注意i要从0开始枚举，还有会超出爆
L 博弈暂时没想到
M 四叠半印刷厂
题目背景太长了，我压根没看，直接读题目描述，抓住两个关键点，有区间修改，区间查询，线段树直接秒了。这里严肃批评24现役ACM学长，竟然不会默写一个最简单的区间修改，区间和查询的线段树板子。
知道线段树后，就常规模拟天数从0开始枚举，如果就特判一下区间
和
带下关系就好了。
涉及到区间修改的只有b数组，a数组的区间和用前缀和预处理就行了
当然这题其实有不用线段树的做法，但学长是一个善于利用工具偷懒的人，直接套线段树模板就好了,值得一提的是我码线段树只用了12min,超级大脑！
代码:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define i64 long long
#define pf push_front
#define pb push_back
#define lowbit(x) (x & (-x))
const int inf = 1e9, N = 2e6 + 10, mod = 998244353;
const long long INF = 1e18;
const double pi = 3.1415926535;
int n, m, k;
i64 a[N], b[N], pre[N];
i64 tag[N << 2], tr[N << 2];
void push_up(int i) {
tr[i] = tr[i << 1] + tr[i << 1 | 1];
}
void build(int i, int l, int r) {
if (l == r) {
tr[i] = b[l];
return;
}
int mid = (l + r) >> 1;
build(i << 1, l, mid);
build(i << 1 | 1, mid + 1, r);
push_up(i);
}
void lazy(int i, int l, int r, int d) {
tr[i] += (r - l + 1) * d;
tag[i] += d;
}
void push_down(int i, int l, int r) {
if (tag[i]) {
int mid = (l + r) >> 1;
lazy(i << 1, l, mid, tag[i]);
lazy(i << 1 | 1, mid + 1, r, tag[i]);
tag[i] = 0;
}
}
void updata(int l, int r, int i, int pl, int pr, int d) {
if (l <= pl and pr <= r) {
tr[i] += (pr - pl + 1) * d;
tag[i] += d;
return;
}
push_down(i, pl, pr);
int mid = (pl + pr) >> 1;
if (l <= mid) {
updata(l, r, i << 1, pl, mid, d);
}
if (r > mid) {
updata(l, r, i << 1 | 1, mid + 1, pr, d);
}
push_up(i);
}
i64 query(int l, int r, int i, int pl, int pr) {
if (l <= pl and pr <= r) {
return tr[i];
}
push_down(i, pl, pr);
i64 res = 0;
int mid = (pl + pr) >> 1;
if (l <= mid) {
res += query(l, r, i << 1, pl, mid);
}
if (r > mid) {
res += query(l, r, i << 1 | 1, mid + 1, pr);
}
return res;
}
void solve() {
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i] >> b[i];
pre[i] = pre[i - 1] + a[i];
}
build(1, 1, n);
i64 ans = 0;
for (int i = 0; i < m; i++) {
int l, r;
cin >> l >> r;
if (i % k == 0) {
if (query(l, r, 1, 1, n) >= pre[r] - pre[l - 1]) {
continue;
}
}
ans += (r - l + 1);
updata(l, r, 1, 1, n, 1);
}
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int _ = 1; //cin >> _;
while (_--)
solve();
return 0;
}
惩罚24级ACM学长没码出线段树模板的罚抄十遍线段树代码，最后默写并背诵!!!
N 赛时没来得及看
O 四叠半算命
题目很简单，给你一个数不断把这个数变成他的数位和，直到长度为1，当然最后还要对9取模，赛时没看到wa了一发。实现方法有多种，这里贴一下我的代码参考。
代码:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define i64 long long
#define pf push_front
#define pb push_back
#define lowbit(x) (x & (-x))
const int inf = 1e9, N = 2e5, mod = 998244353;
const long long INF = 1e18;
const double pi = 3.1415926535;
void solve() {
string t;
cin >> t;
while (t.size() > 1) {
int res = 0;
for (char i : t) {
res += i - '0';
}
t = to_string(res);
}
int res = 0;
for (char i : t) {
res += i - '0';
}
res %= 9;
cout << res << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int _ = 1; //cin >> _;
while (_--)
solve();
return 0;
}
总结
总体来说，感觉题目非常不错，考虑本次参赛是全院要求，学长们出题还是比较仁慈的，给了4题签到题。做出4题以上的都是不错的。
京公网安备 11010502036488号