赛后叨逼叨，这场校赛难度适中，适合编程能力适中的同学，一些常见的知识点就可以AK。没有专门的难题
可能是第一次出题，之前校内也没组织过，导致题面大多数据范围缺失，题意不明……
A、不一样的食物链
第一行给出一个整数N，代表下面存在N对关系。每对关系前为A，后为B，代表A吃B。
问N对关系输入完成之后是否每个人都有吃它的人。
使用一个set吧全部的B插入即可，再遍历出全部的字符串。一一模拟判断即可。
#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op) putchar(op); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); if (op) putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 7;
unordered_set<string> st;
string s1[N], s2[N];
int main() {
js;
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> s1[i] >> s2[i];
st.insert(s2[i]);
}
for (int i = 1; i <= n; ++i) {
if (st.count(s1[i]) and st.count(s2[i]))
continue;
else
return cout << 0 << endl, 0;
}
cout << 1 << endl;
return 0;
} B、有趣的求和
给出M个数，。问只用加法和减法填充到前M - 1前个数的M - 2间隙中，是否可以等于第M个数
二进制枚举操作方法，每一位中1代表加法，0代表减法，依次计算即可，如果等于第M个数保存答案。
#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op) putchar(op); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); if (op) putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 7;
string ans[N];
ll a[N];
int main() {
js;
int cnt = 0;
int n;
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i];
for (int i = 0; i < 1 << (n - 2); ++i) {
string tmp = "";
ll v = a[1];
for (int j = 0; j < n - 2; ++j) {
if (i & (1 << j)) {
v = v + a[n - j - 1];
tmp = '+' + tmp;
}
else {
v = v - a[n - j - 1];
tmp = '-' + tmp;
}
}
if (v == a[n])
ans[++cnt] = tmp;
}
cout << cnt << endl;
for (int i = 1; i <= cnt; ++i)
cout << ans[i] << endl;
return 0;
} C、统计患病人数
一个公司存在N个员工，st号是初代患病者，一共M个部门。
下面给出M个部门的员工人数以及成员编号，一个人可能存在多个部门。感染者会感染同部门的全部人
问最终多少人会被感染，以及被感染的人编号是什么。
对M层关系，直接两两相邻建立边权关系，DFS跑一遍，走过节点打上标记，最后对走过的节点排个序即可。
#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op) putchar(op); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); if (op) putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int N = 2e6 + 7; //节点数
const int M = 2e6 + 7; //路径数
const int INF = 0x3f3f3f3f;
int head[N], tot = 0;//前向星变量
struct Node {
//int u; //起点
//int w; //权值
int v, next;
} edge[M << 1];
void add(int u, int v) {
tot++;
//edge[tot].u = u;
edge[tot].v = v;
//edge[tot].w = w;
edge[tot].next = head[u];
head[u] = tot;
}
int a[N], vis[N], cnt = 1;
vector<int> ans;
void dfs(int u, int fa) {
vis[u] = true;
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].v;
if (vis[v]) continue;
ans.push_back(v);
++cnt;
dfs(v, u);
}
}
int main() {
int n = read(), st = read(), m = read();
for (int i = 1; i <= m; ++i) {
int tmp = read();
for (int i = 1; i <= tmp; ++i)
a[i] = read();
for (int i = 2; i <= tmp; ++i) {
add(a[i - 1], a[i]);
add(a[i], a[i - 1]);
}
}
ans.push_back(st);
dfs(st, -1);
sort(all(ans));
print(cnt, 32);
for (auto it : ans)
print(it, 32);
return 0;
} D、皮皮想拜师
给你最高1e5的树，你起始在n米处，每次可以跳到n + 1, n - 1, n * 2,三种地方，前提不超过1e5。
问你走到第m米处最短的跳跃次数是多少次？
暴力BFS跑一遍，第一次到达m处即可退出。
#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op) putchar(op); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); if (op) putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 100000;
int vis[N + 7];
queue<pai> q;
int main() {
int m = read(), n = read();
q.push({ n,0 });
while (q.size()) {
int now = q.front().first, step = q.front().second;
q.pop();
if (vis[now] or now > N) continue;
vis[now] = true;
if (now == m) return print(step), 0;
q.push({ now + 1,step + 1 });
q.push({ now - 1,step + 1 });
q.push({ now << 1,step + 1 });
}
return 0;
} E、爱玩游戏的Tom
你有N < 100，个游戏，每个游戏有对应的花费和价值。问你在有限金钱M < 1e4 下的最大获取价值是多少。
01背包处理。
#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op) putchar(op); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); if (op) putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 100 + 7;
const int M = 1e4 + 7;
int v[N], w[N];
int dp[M];
int main() {
int n = read(), m = read();
for (int i = 1; i <= n; ++i)
v[i] = read(), w[i] = read();
for (int i = 1; i <= n; ++i)
for (int j = m; j >= v[i]; --j)
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
print(dp[m]);
return 0;
} F、天选子
共有n名同学，编号从1到n，n < 5001
现在开始从开头1 2报数，每次报道2的同学出列，出列完成后，在把剩余同学压缩紧密一点。
接着又从开头1 2 3报数，每次报道3的同学出列，之后和前面一样压缩。
又回到1 2报数，2出列，
1 2 3报数，3出列，依次反复进行，最后剩下三人时停止。
如果剩下三人的编号大于m，直接从小到大输出三人编号，如果小于m，输出m减掉剩余玩家编号的值。
直接模拟题，使用异或处理2人和3人批次，打上vis标记，当人数低于3人时退出循环。
#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op) putchar(op); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); if (op) putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 5e3 + 7;
bool vis[N];
int main() {
int n = read(), m = read();
int flag = 0;
for (int k = n; k > 3;) {
for (int i = 1, j = 0; i <= n; ++i) {
if (vis[i]) continue;
++j;
if (j % (2 + flag) == 0) vis[i] = 1, --k;
}
flag ^= 1;
}
int s = 0;
vector<int> ans;
for (int i = 1; i <= n; ++i)
if (vis[i] == 0)
s += i, ans.push_back(i);
if (s > m)
for (auto it : ans)
print(it, 32);
else
print(abs(m - s));
return 0;
}
G、团日活动
给出团队总人数 n < 1e9, 以及男生人数 m < n。
女生过桥时间都是1S，男生过桥时间依次是 1, 2, 3, 4, ……，m秒，每次两人一起过桥，两人花费的过桥时间是较短那位人的时间。
问n人全部过桥时间花费最短是多少。
简单数学题，每次让时间相邻的男生一起过桥，可用等差数列求得偶数男生过桥时间，如果男生是奇数个，就把女生人数加一。
最后把女生人数 / 2，向上取整累加到过桥时间即可。
#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op) putchar(op); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); if (op) putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
int main() {
int T = read();
while (T--) {
ll N = read(), n = read();
N -= n;
ll m = n >> 1;
if (n % 2) ++N;
ll ans = 0;
if (m > 0)
ans = n * m - m * (m - 1); // S(n) = n * a1 + n * (n-1) * d / 2
ans += (N + 1) >> 1;
print(ans);
}
return 0;
} H、标准签到题
输入一串字符串，如果没有出现过ora的子串，就输出对应字符串，否则输出ora出现的次数。
Python处理，str的count成员函数，直接计数即可。
s = input()
if 'ora' in s:
print(s.count('ora'))
else:
print('yare yare daze') I、炎炎消防队
#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op) putchar(op); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); if (op) putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 7;
const double eps = 1e-4;
double calc(double x) { //F'(x)
return 49 * pow(x, 6) + 36 * pow(x, 5) + 6 * x * x + 16 * x;
}
int main() {
int T = read();
while (T--) {
double y;
scanf("%lf", &y);
int cnt = 0;
double l = 0.0, r = 100.0, ans = -1;
for(int i=1; i<=60; ++i){
double mid = (l + r) / 2;
if (fabs(calc(mid) - y) < eps) {
ans = mid;
break;
}
else if (calc(mid) > y)
r = mid;
else
l = mid;
}
if (fabs(ans + 1) < eps) ans = 0;
printf("%.4f\n", 7 * pow(ans, 7) + 6 * pow(ans, 6) + 2 * pow(ans, 3) + 8 * pow(ans, 2) - y * ans);
}
return 0;
} 
京公网安备 11010502036488号