比赛链接: https://vjudge.net/contest/573064#problem/A
B - Balloon Darts
题目大意
一个二维平面上有n个气球, 给出所有气球的坐标; 你现在有3个飞镖, 你可以在任意位置朝任意方向射出, 并且距离是无限远; 请问能否用这3个飞镖射爆所有气球;
解题思路
如果要用3条线遍历所有点, 那么对于任意的4个点, 其中至少有2个点在一条直线上; 我们可以先从所有点中任选2个点形成一条直线, 然后把所有在这条线上的点去掉; 接下来我们要用2条线遍历所有点, 那么对于任意的3个点, 其中至少有2个点在一条直线上; 于是我们可以再从剩下的点中任选2个点形成一条直线, 然后把所有在这条线上的点去掉; 接下来再判断一下剩下所有点是否在同一条直线上即可;
上述操作可以用递归实现, 用飞镖数k表示我们要从多少点里面选2个点, 既然在是任意的(k+1)个点, 至少有2个点在一条直线上, 那么我们就选v[1]~v[k+1]即可; 在这之前我们先判断一下, 如果当v中的点数小于等于2*k时一定可以遍历所有点, 所以这时候直接return true即可, 这也防止了遍历时越界; 因为选的两个点不分先后, 所以遍历时j从i+1开始以防重复; check函数用于检查三点共线, 具体方法就是两两斜率是否相同, 高中方法不多赘述;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
struct str {
int x, y;
};
int n;
bool check(str c, str a, str b) {
int d1 = (a.x - b.x) * (b.y - c.y);
int d2 = (b.x - c.x) * (a.y - b.y);
if (d1 == d2) return true;
else return false;
}
vector<str> modify(vector<str> v, str a, str b) {
vector<str> v2;
for (int i = 0; i < v.size(); i++) {
str t = v[i];
if (!check(t, a, b)) v2.push_back(t);
}
return v2;
}
bool solve(vector<str>& v, int k) {
if (v.size() <= 2 * k) return true;
for (int i = 1; i <= k + 1; i++) {
for (int j = i + 1; j <= k + 1; j++) {
auto v2 = modify(v, v[i], v[j]);
if (solve(v2, k - 1)) return true;
}
}
return false;
}
signed main() {
cin >> n;
vector<str> v;
for (int i = 1; i <= n; i++) {
int a, b;
cin >> a >> b;
v.push_back({ a,b });
}
if (solve(v, 3)) cout << "possible";
else cout << "impossible";
return 0;
}
C - Cosmic Commute
题目大意
给定一个权值均为1的图, 要求从1点走到n点, 图上有k个点配有传送装置, 但是该传送装置会随机传送到其他有传送装置的点, 并且传送装置最多用一次; 问从1到n的路程最小值是多少, 答案以最简分数表示;
解题思路
如果不用传送装置, 最短路程就1~n的最短路; 如果要用就会发生概率问题, 因为有(k-1)个可能的目的地, 所以要把所有可能的路程长度加起来除以(k-1); 因为本题权值均为1所以直接用bfs求距离即可, 用两次bfs求出所有点到1点和n点的距离, 我们设为dst和ded; 当我们在点x使用传送装置时, 假设到达了点y, 那么该次路程长度为dst[x]+ded[y]; 因为点y有(k-1)种可能, 所以总的路程就是dst[x]*(k-1) + (ded[y1]+ded[y2]+...ded[yk-1]); 然后从所有可能中找出最小值即可;
还有就是用邻接表时数组可以适当的放大点, 本题数据范围最大1e6, 我开1e6+10结果会tle, 用了各种方法都是tle, 结果最后改成2e6+10就过了;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e6 + 10;
int n, m, k, idx;
int h[N], ne[N], e[N];
int dst[N], ded[N];
vector<int> v;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
void bfs(int u, int d[]) {
for (int i = 1; i <= n; i++) d[i] = -1;
queue<int> q;
q.push(u);
d[u] = 0;
while (q.size()) {
int t = q.front();
q.pop();
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (d[j] == -1) {
d[j] = d[t] + 1;
q.push(j);
}
}
}
}
signed main() {
cin >> n >> m >> k;
memset(h, -1, sizeof h);
for (int i = 1; i <= k; i++) {
int a;
cin >> a;
v.push_back(a);
}
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
bfs(1, dst), bfs(n, ded);
int minn = ded[1] * (k - 1);
int sum = 0;
for (int i = 0; i < v.size(); i++) sum += ded[v[i]];
for (int i = 0; i < v.size(); i++) {
int ans = dst[v[i]] * (k - 1) + sum - ded[v[i]];
minn = min(minn, ans);
}
int x = gcd(minn, k-1);
int fz = minn / x, fm = (k - 1) / x;
cout << fz << '/' << fm;
return 0;
}
D - DnD Dice
题目大意
现有5种骰子, 最大点数分别为4,6,8,12,20; 现在给出这五种骰子各自的数量, 掷出后把所有骰子的点数相加得到一个总点数, 按概率从大到小输出所有可能的总点数;
解题思路
一道非常像dp的找规律, 当然dp也能做, 但是统计的数量数值太大爆unsigned LL, 必须要用double存才能过, 当时以为是状态计算出错了, 没想到是爆unsigned LL... 正解的做法是用正态分布来做; 满足正态分布的条件为: 概率受到若干独立因素共同影响, 其每个因素不能产生支配性作用; 本题的点数由若干的骰子点数组成所以满足该条件;正太分布一定是对称的, 所以可以先判断一下区间长度, 找出概率最大的一个或者两个数, 然后向左右发散即可;
神秘代码
//正态分布做法
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<double, int> PII;
const int N = 1e3 + 10;
int a, b, c, d, e;
int l, r;
signed main() {
cin >> a >> b >> c >> d >> e;
int minn = a + b + c + d + e;
int maxn = a * 4 + b * 6 + c * 8 + d * 12 + e * 20;
int len = maxn - minn + 1;
if (len % 2==0) {
l = (minn + maxn) / 2;
r = (minn + maxn) / 2 + 1;
cout << l << ' ' << r << ' ';
}
else {
l = r = (minn + maxn) / 2;
cout << l << ' ';
}
while (1) {
if (l<minn && r>maxn)break;
if (--l >= minn) cout << l << ' ';
if (++r <= maxn) cout << r << ' ';
}
return 0;
}
//dp做法
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<double, int> PII;
const int N = 1e3 + 10;
int a, b, c, d, e;
int s[N], cnt, sum;
double dp[N][N];
PII res[N];
bool cmp(PII a, PII b) {
return a.first > b.first;
}
signed main() {
cin >> a >> b >> c >> d >> e;
sum = a * 4 + b * 6 + c * 8 + d * 12 + e * 20;
for (int i = 0; i < a; i++) s[++cnt] = 4;
for (int i = 0; i < b; i++) s[++cnt] = 6;
for (int i = 0; i < c; i++) s[++cnt] = 8;
for (int i = 0; i < d; i++) s[++cnt] = 12;
for (int i = 0; i < e; i++) s[++cnt] = 20;
dp[0][0] = 1;
for (int i = 1; i <= cnt; i++) {
for (int j = 1; j <= s[i]; j++) {
for (int k = j; k <= sum; k++) {
if (dp[i - 1][k - j]) {
dp[i][k] += dp[i - 1][k - j];
}
}
}
}
int num = 0;
for (int i = cnt; i <= sum; i++) res[++num] = { dp[cnt][i],i };
sort(res + 1, res + 1 + num, cmp);
for (int i = 1; i <= num; i++) cout << res[i].second << ' ';
return 0;
}
E - Eszett
题目大意
给定一个由大写字母组成的字符串, 将其转化成小写字母输出, 然后在转换后我们可以将"ss"转化为B, 并且保证字符串中最多只有3个s; 输出所有可能的字符串, 无论顺序;
解题思路
签到题, 可以记一下string的replace函数: replace(下标, 长度, 字符串); 作用是用该字符串替换从下标开始的某长度的字符串; 返回值是修改后的字符串;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5;
signed main() {
string s;
string res;
cin >> s;
for (int i = 0; i < s.size(); i++) s[i] = s[i] + 32;
cout << s << endl;
if (s.find("sss")!=-1) {
cout << s.replace(s.find("sss"), 3, "Bs") << endl;
cout << s.replace(s.find("Bs"), 2, "sB") << endl;
}
else if (s.find("ss") != -1) {
cout << s.replace(s.find("ss"), 2, "B") << endl;
}
return 0;
}
F - Freestyle Masonry
题目大意
给定一个n*m的矩形墙面, 其中最底层已经砌好了一部分大小为1x1的砖, 给出每一列已经砌好的砖块高度, 问能否用大小为1x2的砖块恰好砌好剩余的墙面;
解题思路
刚读完题以为是状压dp, 但是数据范围高达1e6, 自然只能想其他办法; 并且我们也能从中得知遍历n*m的矩形也一定会超时; 要用O(n)的复杂度解决问题就只能找规律或者找公式了; 所以可以猜测这是一个贪心问题; 既然要砌好所以墙面, 我们不妨从左侧开始, 因为要找局部最优解, 所以我们要尽可能不能不去干涉其他列, 所有应该优先竖着砌, 如果空不够了再横着砌;
在纸上模拟多种情况后发现, 只有两种情况我们必须横着砌, 一是还有一格就到顶, 二是还有一格就到上一列横着砌的砖; 第一种情况最好处理, 直接让下一列的高度上限减一即可; 而第一种情况我们可以再往前推, 上一列的这个位置之所以会横着砌无非也是那两种情况, 如果是第一种情况说明当前这一列往上就没有空位了直接考虑下一列即可; 如果是第二种情况就说明当前这一列在高度上限的上面还有空着的地方, 并且高度最大为1, 所有这个地方也要砌一个横放的砖; 于是下一列如果可以恰好到达高度上限, 那么他会要么直接到顶, 要么就是空一格后又到达一个新的高度上限, 所以下下列的高度上限就是min(maxn+1, m);
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
int n, m;
int h[N];
signed main() {
cin >> n >> m;
bool f = true;
for (int i = 1; i <= n; i++) {
cin >> h[i];
if (h[i] > m) f = false;
}
if (!f) {
cout << "impossible";
return 0;
}
int maxn = m;
for (int i = 1; i <= n; i++) {
int d = maxn - h[i];
if (d < 0) break;
if (d % 2) maxn--;
else {
maxn = min(maxn + 1, m);
}
}
if (maxn == m) cout << "possible";
else cout << "impossible";
return 0;
}
G - German Conference for Public Counting
题目大意
现在有很多个牌子, 牌子上有一个0~9之间的一个数字; 现在给定一个数n, 问我们至少需要多少个牌子可以把0~n中
任意一个数表示出来;
解题思路
签到题, 对于n(n>1)位数的数, 一定存在一个n-1位的数是由同一个数组组成; eg: 0~23213中一定存在1111, 2222...10000; 所有0~9中每个数字的牌子都要至少准备n-1个; 而0~23213中还存在11111和22222, 所有再根据第n位的数特判一下就行;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5;
signed main() {
string s;
cin >> s;
if (s.size() == 1) cout << s[0] - '0' + 1;
else {
int res = 10 * (s.size() - 1);
res = res + (s[0] - '0') - 1;
if (s[1] - '0' > s[0] - '0') res++;
else if (s[1] - '0' == s[0] - '0') {
bool f = true;
for (int i = 1; i < s.size(); i++) {
if (s[i] < s[0]) {
f = false;
break;
}
}
if (f) res++;
}
cout << res;
}
return 0;
}
I - Investigating Frog Behaviour on Lily Pad Patterns
题目大意
在一排荷叶上有n只青蛙, 给出每只青蛙的下标; 给出m次操作, 让最初的第x只青蛙往前跳到距离它最近的空着的荷叶上, 输出每次操作后该青蛙的落地荷叶坐标;
解题思路
一道比较的简单的模拟题, 用变量maxn表示当前最远的荷叶坐标, 用set维护空着的荷叶, 每次操作用二分找出距离它最近的空着的荷叶, 然后更新set序列; 如果找不到就跳到maxn+1上, 然后更新maxn即可; 比赛时还担心进行1e6次set的插入删除已经二分查找会超时, 结果说明本题还是比较仁慈的;
神秘代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, m;
set<int> st;
map<int, int> mp;
int f[N];
signed main() {
cin >> n;
int maxn = 0;
for (int i = 1; i <= n; i++) {
cin >> f[i];
mp[f[i]]++;
maxn = max(maxn, f[i]);
}
for (int i = 1; i <= maxn; i++) {
if (!mp[i]) st.insert(i);
}
cin >> m;
for (int i = 1; i <= m; i++) {
int x;
cin >> x;
auto t = st.upper_bound(f[x]);
if (t == st.end()) {
st.insert(f[x]);
maxn++;
f[x] = maxn;
cout << f[x] << endl;
}
else {
int a = *t;
st.erase(t);
st.insert(f[x]);
f[x] = a;
cout << f[x] << endl;
}
}
return 0;
}
K - Kaldorian Knights
题目大意
现在有n个骑士和m个家族, 按照家族实力从大到小输入每个家族的骑士数量ki, 可能存在骑士不属于任何家族; 国王会对骑士进行排名; 如果最强家族的k1名骑士被排在最后k1名, 那么该家族就会叛乱; 第二强的家族实力较弱, 即使他的k2名骑士被排在最后k2位也不会叛乱, 但是, 如果最强和第二强两个家族的(k1+k2)名骑士被排在最后(k1+k2)位, 那个这两家会联合叛乱, 相应的如果(k1+k2...ki)名骑士被排在最后(k1+k2...ki)位, 那么前i家家族就会联合叛乱; 问国王有多少种排序方式可以不引发叛乱, 结果对1e9+7取模;
解题思路
一道数学排列问题, 难点在于找到不同排列之间的重合部分; 我们设di表示前i个家族的骑士排在末尾的情况, 并且di与前面的d(1~i-1)没有重复情况;
当我们只考虑第一家族时: d1就是A(k1);
考虑前两个家族时: 设f=k1+k2, d2不能单纯的用A(f)表示, 因为A(f)和d1一定存在重合的情况, 即A(f)中k1全部排在最后的情况, 这种情况下k2的排序一共有A(f-k1)种, 而k1则是d1种, 所以d2=A(f)-A(f-k1)d1;
考虑前三个家族时: 设f=k1+k2+k3, A(f)既和d1有重合, 也与d2有重合; 与d1的重合就是A(f)中k1全部排在最后的情况, 所以A(f)要减去A(f-k1)d1; 与d2的重合就是A(f)中k1和k2全部排在最后. 并且最后全是k1的情况, 所以A(f)要减去A(f-k1-k2)*d2;
注意我们最后都是乘的是d2而不是A(k1+k2), 因为d2是因为去重后的情况, 如果是A(k1+k2)就减多了; 之后也都同理, 用一个循环遍历i之前的所有情况即可, 并且为了便于计算, 我们可以把k表示为前缀和;
最后的结果就是用A(n)减去所有的A(n - ki) * di; 注意问题有个坑点在于取模上, 因为大部分运算都是减法, 为了防止减的数过大, 我们可以在乘完后先取模在做减法, 然后再加模取模即可;
_____332221111
_______2221111
__________1111
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<double, int> PII;
const int N = 1e6 + 10, mod = 1e9 + 7;
int n, m;
int k[N], A[N], d[N];
signed main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> k[i];
k[i] += k[i - 1];
}
A[0] = 1;
for (int i = 1; i <= n; i++) {
A[i] = A[i - 1] * i % mod;
}
for (int i = 1; i <= m; i++) {
d[i] = A[k[i]];
for (int j = 1; j < i; j++) {
d[i] = ((d[i] - A[k[i] - k[j]] * d[j] % mod) + mod) % mod;
}
}
int ans = A[n];
for (int i = 1; i <= m; i++) {
ans = ((ans - A[n - k[i]] * d[i] % mod) + mod) % mod;
}
cout << ans;
return 0;
}
L - Loop Invariant
题目大意
给定一个由括号组成的序列, 将该序列首尾相连形成一个环, 问我们能否找到一个切割点, 使得在这个位置切开后形成的序列和原序列不同; 切割点不能处于任何一个括号内部, 也就是说要在两个独立的括号之间切;
解题思路
本题模拟并不算难, 但是如果你遍历所有可行的切割点来找不同的序列, 那么恭喜你tle了; 本题其实只需要找到第一个可行的切割点就可以了, 如果切开后发现与原序列相同, 你再往后找切割点就相当于重复前面的过程, 你会陷入一个循环; 所以只要第一个切割点生产的序列相同就输出no, 否则输出当前序列即可;
处理环状时一般都是把序列延长一倍来模拟;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
int n, m;
string s, ds;
vector<int> v;
signed main() {
cin >> s;
ds = s + s;
int len = s.size();
for (int i = 0; i < len; i++) {
if (ds[i] == '(') v.push_back(i);
else if (ds[i] == ')') v.pop_back();
if (v.size() == 0) {
string str = ds.substr(i + 1, len);
if (str == s) cout << "no";
else cout << str;
break;
}
}
return 0;
}
M - Mischievous Math
题目大意
给定一个数d; 需要我们找出三个数a,b,c; a,b,c三个数之间可以用加减乘除已经括号进行运算, 要求无论怎么运算都不能得到d; 其中a,b,c,d互不相等且a,b,c在运算时都最多使用一次;
解题思路
找特殊值就行, 最简单的逻辑就是对于一个数d, 我们要么让a,b,c运算的最大值小于d, 要么就让运算的最小值大于d; 因此我们最容易想到1,2,3, 其运算的最大值就是9, 因此如果d>9就输出1,2,3;
d<=9时自己找一组相互差值大于9的且比较怪的三个数就大概率可以过, 据题解说一共有16170种组合;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5;
int n, m;
signed main() {
cin >> n;
if (n > 9) cout << "1 2 3 ";
else cout << "49 60 82";
return 0;
}