L1-7 拼接梯子
本来一个挺简单的题……本菜写半天发现最小是 竟然特判的是等于等于1，输出no……我也不知道当初脑子怎么瓦特这么久，好在是IOI，最后还是发现了奇数直接出no，其余我是通过位运算一个个推到第一个1。
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
inline ll read() {
ll s = 0, w = 1; char ch = getchar();
while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * w;
}
int main() {
ll n = read(), m = read();
if ((1ll << n + 1) - 1 < m || m &1)
puts("No");
else {
puts("Yes");
int st = -1, cnt = 0;
while (m) {
if (m & 1) st = cnt;
m >>= 1;
++cnt;
}
printf("%lld\n", 1ll << st);
}
return 0;
} L1-8 幻想乡炼金学
……悔恨！没看题目的模拟题，哪怕补题也是这样，现在看一下题目不就是个模拟么，小心谨慎一点，考虑到每种情况即可。
我选择开个二维vector保存全部的原子与原子团，吧（）中间看成原子团保存在一维vector中，最后遍历全部原子中的全部字母，输入时计数。
有关计数新开一个int数组即可。
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
inline int read() {
int s = 0, w = 1; char ch = getchar();
while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * w;
}
const int N = 155;
vector<string> v[N];
int pos[N];
int main() {
js; //关了同步，就不能用getchar()等全部的C OI函数了
int cnt = 0;
bool ok = false;
string s = "";
char ch;
while ((ch = cin.get()) && ch != EOF) {
if (ch == ' ') continue; //空格没有用
if (!islower(ch) && s.size()) { //现在不是小写字母，并且s里面有东西
v[cnt].push_back(s);
if (!ok) ++cnt; //不在一个（）中
s.clear();
}
if (isupper(ch)) s = ch;
else if (islower(ch)) s += ch;
else if (ch == '(') ok = true;
else if (ch == ')') ok = false, ++cnt;
else if (ch == '{') {
int sum = 0;
while (ch = cin.get()) {
if (ch == ' ') continue;
if (ch == '}') break;
sum = sum * 10 + ch - '0';
}
pos[cnt - 1] = sum; //先更新了cnt
}
}
for (int i = 0; i < cnt; ++i)
if (!pos[i]) pos[i] = 1; //Fe(OH){2} ->防止 OOHH 没带括号的情况
for (int i = 0; i < cnt; ++i) //每个原子
for (int j = 0; j < v[i].size(); ++j) //每个原子的每个字母
for (int k = 0; k < pos[i]; ++k) //次数
cout << v[i][j];
cout << endl;
return 0;
}
L2-1 特殊的沉重球
……亏了，这么简单的题目没看，这要是什么大型比赛都会气死，果然还是要先去吧全部题目看完，在思考，大部分时间花在下一题栈里面了，还是0分。
哎！好吧，回归正题，这道题就算是一个比较裸的dfs题目吧，搜索，回溯，记得按体重降序排个序，不会找的那么死，（说人话就是减枝）
代码注释的比较详细了，应该不难理解……
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
inline int read() {
int s = 0, w = 1; char ch = getchar();
while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * w;
}
const int N = 25;
int a[N], b[N]; //精灵体重，每个宝贝球已经装备的精灵重量
int ans;
int n, w;
void dfs(int x, int now) { //当前编号，当前用掉的宝贝球数目
if (now >= ans) return; //最优性剪枝
if (x > n) {
ans = min(ans, now);
return;
}
for (int i = 1; i <= now; ++i) {
if (a[x] + b[i] <= w) //如果存在一个之前的宝贝球可以放进a[x]去
b[i] += a[x], dfs(x + 1, now), b[i] -= a[x]; //宝贝球不增加
}
// 为这个人单独开一个宝贝球
b[now + 1] = a[x];
dfs(x + 1, now + 1);
b[now + 1] = 0;
}
int main() {
n = read(), w = read();
for (int i = 1; i <= n; ++i) a[i] = read();
sort(a + 1, a + 1 + n, greater<int>());
ans = n;
dfs(1, 0);
printf("%d\n", ans);
return 0;
} L2-2 又见火车入栈
因为存在查询前y项记录用STL的stack肯定是不行的，只能手写一个栈，并且可以发现，查询和我进出栈没关系，考虑离线。
对于每个输入的查询，用一个数组a保存，在模拟进出栈的情况，模拟到第k条记录时，停止，这里要考虑输入不是递增，需要将查询数组按照记录升序先排序在查询，将答案更新为当前入栈的第y辆火车
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
inline int read() {
int s = 0, w = 1; char ch = getchar();
while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * w;
}
const int N = 1e6 + 7;
struct Node { //离线数组
int l, r;
int id;
bool operator < (const Node& a)const {
if (l == a.l) return id < a.id;
return l < a.l;
}
}a[N];
int ans[N], vis[N];
int st[N], top; //手动模拟栈
int main() {
int n = read();
for (int i = 1; i <= n; ++i) {
char s[5];
scanf("%s", s);
if (s[0] == 'i') vis[i] = 1; //1入0出
}
int m = read();
for (int i = 1; i <= m; ++i) {
int l = read(), r = read();
a[i] = { l,r,i }; //离线查询
}
sort(a + 1, a + 1 + m); //按记录排序
int k = 0, num = 0; //k记录第几条指令，num记录当前最后一次入栈火车序号
for (int i = 1; i <= m; ++i) {
while (a[i].l != k) { //模拟栈
if (vis[++k]) st[++top] = ++num;
else --top;
}
ans[a[i].id] = st[a[i].r];
}
for (int i = 1; i <= m; ++i)
printf("%d\n", ans[i]);
return 0;
} L2-3 新旷野地带
啊啊啊！本来可以快A的，因为取模忘记了最后拿了个10分，心累……
第一步：预处理组合数的阶乘以及费马小定理处理阶乘的逆元。
第二步：对于每个给定的K，选定k行k列存在 种选择方式，填涂一行一列一个士兵很显然是k的阶乘种方案。
那么只需要枚举从1到k的全部取值组合，如果大于n或者大于m，说明有一个行或列一定存在2个士兵。
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
inline int read() {
int s = 0, w = 1; char ch = getchar();
while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * w;
}
const int N = 1e6 + 7;
const int MOD = 1e9 + 7;
ll jc[N], inv[N];
ll qpow(ll a, ll b) {
ll ans = 1;
while (b) {
if (b & 1) (ans *= a) %= MOD;
b >>= 1;
(a *= a) %= MOD;
}
return ans;
}
void init() {
jc[0] = 1;
for (int i = 1; i <= 1000000; ++i) jc[i] = jc[i - 1] * i % MOD;
inv[1000000] = qpow(jc[1000000], MOD - 2);
for (int i = 999999; i >= 0; --i)
inv[i] = inv[i + 1] * (i + 1) % MOD;
}
ll C(int n, int m) {
return jc[n] * inv[n - m] % MOD * inv[m] % MOD;
}
ll A(int n, int m) {
return jc[n] * inv[n - m] % MOD;
}
int main() {
init();
int n = read(), m = read(), k = read();
ll ans = 0;
for (int i = 1; i <= k; ++i){
if(i>n || i>m) break;
(ans += C(n, i) * C(m, i) % MOD * jc[i] % MOD)%=MOD;
}
printf("%lld\n", ans);
return 0;
} L2-4 缘之空
穹妹这么可爱，虽然她在最后一个，也必须把她给肝出来）我说的是题目，你以为是啥。
虽然这个在最后一题，不过难度也不算很大，给我感觉就是LCA（树上最近公共祖先）的模板题……但是因为本菜的一系列魔幻操作，在WA了很多遍后才找到正确答案。
第一步：这题不是以1为根！！划重点，是需要你去找根的，我直接用1是根稳定0分……好狠，直接开个数组，统计入度，入度为0的点就是根节点。
第二步：从根节点开始dfs，预处理倍增数组，以及求解深度。具体LCA的倍增方法这里就不展开了，不懂的同学可以去网上自行百度。
第三步：对于每次查询，如果LCA找到的是自己，说明一个是一个祖先直接输出NO（这里一开始没看到也WA了几发），否则就是树上距离的公式 再去和4比较就行了。虽然好像是祖先也要求距离！不过这个距离是一个根节点一个子节点，直接deep相减一下。
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
inline int read() {
int s = 0, w = 1; char ch = getchar();
while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * w;
}
const int N = 1e5 + 7;
vector<int> e[N];
int deep[N];
int vis[N];
int fa[N][20]; //log2(100000) = 16.
void dfs(int x, int y) { //dfs求到深度以及预处理x的倍增数组
fa[x][0] = y;
deep[x] = deep[y] + 1;
for (int i = 1; i < 20; ++i)
fa[x][i] = fa[fa[x][i - 1]][i - 1];
for (int i = 0; i < e[x].size(); ++i) {
int tmp = e[x][i];
if (tmp != y)
dfs(tmp, x);
}
}
int lca(int x, int y) {
if (deep[x] < deep[y]) swap(x, y);
for (int i = 19; i >= 0; --i)
if (deep[fa[x][i]] >= deep[y])
x = fa[x][i]; //调整到同一深度
if (x == y) return x;
for (int i = 19; i >= 0; --i)
if (fa[x][i] != fa[y][i])
x = fa[x][i], y = fa[y][i];
return fa[x][0];
}
int main() {
int n = read(), m = read(), rt = 0;
for (int i = 1; i < n; ++i) {
int u = read(), v = read();
e[u].push_back(v);
++vis[v];
}
for(int i=1;i<=n;++i)
if(!vis[i]) {
rt=i;
break;
}
dfs(rt, 0);
while (m--) {
int u = read(), v = read();
int ans;
int tmp = lca(u, v);
if (tmp == u || tmp == v) ans = abs(deep[u] - deep[v]); //虽然好像有点多余……请别在意
else
ans = deep[u] + deep[v] - 2 * deep[tmp];
if (ans <= 4 || tmp == u || tmp == v) puts("NO");
else puts("YES");
printf("%d\n", ans);
}
return 0;
}
京公网安备 11010502036488号