2023年10月13日
昨天出去玩了，没做题，真罪恶。哎
Div.3 Round883 A Rudolph and Cut the Rope
题目大意
每个绳子有个钉子的高度和绳子的长度，糖果和每一个绳子的末尾相连，问我需要剪掉多少根绳子才能让糖果落地。
题目理解
其实就是统计a > b的个数即可
代码实现
void solve()
{
int n;
cin >> n;
int res = 0;
for(int i = 1;i <= n; i++)
{
int a, b;
cin >> a >> b;
if(a > b)
res++;
}
cout << res << endl;
return;
}
Div.3 Round883 B Rudolph and Tic-Tac-Toe
题目大意
三人井字棋游戏，看谁赢，没人赢就输出DRAW。
题目理解
就暴力枚举，每一个不是.的点即可。
代码实现
bool ok(int i, int j)
{
if(i < 0 || i >= 3 || j < 0 || j >= 3)
return false;
return true;
}
bool check(int i, int j, vector<string> vec)
{
if(ok(i - 1, j) && ok(i + 1, j))
if(vec[i][j] == vec[i - 1][j] && vec[i - 1][j] == vec[i + 1][j])
return true;
if(ok(i, j - 1) && ok(i, j + 1))
if(vec[i][j] == vec[i][j - 1] && vec[i][j + 1] == vec[i][j - 1])
return true;
if(ok(i - 1, j - 1) && ok(i + 1, j + 1))
if(vec[i][j] == vec[i - 1][j - 1] && vec[i - 1][j - 1] == vec[i + 1][j + 1])
return true;
if(ok(i - 1, j + 1) && ok(i + 1, j - 1))
if(vec[i][j] == vec[i - 1][j + 1] && vec[i - 1][j + 1] == vec[i + 1][j - 1])
return true;
return false;
}
void solve()
{
vector<string> vec;
for(int i = 1; i <= 3;i++)
{
string a;
cin >> a;
vec.push_back(a);
}
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
{
if(check(i, j, vec) && vec[i][j] != '.')
{
cout << vec[i][j] << endl;
return;
}
}
cout << "DRAW" << endl;
return;
}
Div.3 Round883 C Rudolf and the Another Competition
题目大意
每个人的icpc比赛，会有积分、罚时，问排名下来，我们的主角是第几名。
题目理解
因为n * m是\(≤ 2* 10^5\),那么我们每次排个序，然后只做时间段的题，即可。
需要注意的是，罚时的计算方式:now += p[i] t += now
代码实现
void solve()
{
ll n, m, k;
scanf("%lld%lld%lld", &n, &m, &k);
ll res = 1;
ll time = 0, score = 0, total = 0;
ll p;
vector<ll> q;
for(ll i = 1; i <= m; i++)
{
scanf("%lld", &p);
q.push_back(p);
}
sort(q.begin(), q.end());
for(ll i = 0; i < m; i++)
{
total += q[i];
if(total > k) break;
score++, time += total;
}
for(ll i = 2; i <= n; i++)
{
vector<ll> qq;
for(ll j = 0; j < m; j++)
{
scanf("%lld", &p);
qq.push_back(p);
}
sort(qq.begin(), qq.end());
ll timet = 0, scoret = 0;
total = 0;
for(ll j = 0; j < m; j++)
{
total += qq[j];
if(total > k) break;
timet += total, scoret++;
}
if(scoret > score) res++;
else if(score == scoret && timet < time)
res++;
}
printf("%lld\n", res);
return;
}
Div.4 Round883 D Rudolph and Christmas Tree
题目大意
计算，给出的图形的面积和。
题目理解
需要注意的是，下一个三角形可能和上一个三角形重叠，我们要做的就是用中学的知识，用比例把上底算出来就行。
\(l = d * (dif / h)\), dif是被遮住的高
代码实现
const int N = 2e5 + 10;
double a[N];
void solve()
{
double sum = 0;
int n;
double d, h;
cin >> n >> d >> h;
for(int i = 1; i <= n; i++) cin >> a[i];
sum += d * h / 2;
for(int i = n - 1; i >= 1; i--)
{
if(a[i] + h > a[i + 1])
{
double dif = a[i] + h - a[i + 1];
double l = d * (dif / h);
sum += (l + d) * (a[i + 1] - a[i]) / 2;
}else{
sum += d * h / 2;
}
}
printf("%.8lf\n", sum);
return;
}
ICPC 2023 第一场网络赛 L
。。。。只能做签到题的垃圾。。。。希望以后争取不看解析，也能做好D和J难度的题
题目理解
答案就是
\[max(2, \frac{T_{max}}{k}向上取整) \]代码实现
void solve()
{
ll n, T;
cin >> n >> T;
ll res = 0;
for(int i = 1; i <= n; i++)
{
ll b;
cin >> b;
res = max(res, b);
}
cout << max((int)ceil(1. * res / T), 2);
return;
}
ICPC 2023 第一场网络赛 A
题目理解
根据题目要求，对一场和第二场的排名进行去重，然后按照顺序，加入答案vec即可。
代码实现
void solve()
{
string a[N], b[N];
vector<string> res, t1, t2;
map<string, int> mp, mp1, mp2;
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= m; i++) cin >> b[i];
for(int i = 1, j = 1; i <= n || j <= m; i++, j++)
{
if(i <= n)
{
if(!mp1.count(a[i]))
{
mp1[a[i]] = 1;
t1.push_back(a[i]);
}
}
if(j <= m)
{
if(!mp2.count(b[j]))
{
mp2[b[j]] = 1;
t2.push_back(b[j]);
}
}
}
n = (int)t1.size(), m = (int)t2.size();
for(int i = 0, j = 0; i < n || j < m; i++, j++)
{
if(i < n)
{
if(!mp.count(t1[i]))
{
mp[t1[i]] = 2;
res.push_back(t1[i]);
}
}
if(j < m)
{
if(!mp.count(t2[i]))
{
mp[t2[j]] = 2;
res.push_back(t2[j]);
}
}
}
for(int i = 0; i < (int)res.size(); i++)
cout << res[i] << endl;
return;
}
Acwing4956 冶炼金属
题目理解
蓝桥杯原题，直接二分两次即可，分别找到最小值和最大值。
代码实现
pair<ll, ll> q[N];
ll n;
bool check(int u)
{
for(int i = 1; i <= n; i++)
if(q[i].x / u > q[i].y)
return false;
return true;
}
bool check2(int u)
{
for(int i = 1; i <= n; i++)
if(q[i].x / u < q[i].y)
return false;
return true;
}
void solve()
{
cin >> n;
for(int i = 1; i <= n; i++)
cin >> q[i].x >> q[i].y;
ll l = 1, r = 1e9;
while(l < r)
{
ll mid = (l + r) >>1;
if(check(mid)) r = mid;
else l = mid + 1;
}
cout << l <<" ";
l = 1, r = 1e9;
while(l < r)
{
ll mid = (l + r + 1) >> 1;
if(check2(mid)) l = mid;
else r = mid - 1;
}
cout << l;
return;
}
Acwing4957 飞机降落
题目理解
数据范围很小，dfs可以解决。需要注意、剪枝的条件如下：
- 如果是在起飞的时刻之后，就要加上等待的时间间隔
- 如果是之前就要直接加飞落的时间。
代码实现
const int N = 15;
int t[N], d[N], l[N];
bool flag = false;
bool st[N];
ll n;
void dfs(int u, int now)
{
if(flag) return;
if(u >= n)
{
flag = true;
return;
}
for(int i = 1; i <= n; i++)
{
if(!st[i] && now <= t[i] + d[i]) //可以飞的条件
{
st[i] = true;
if(t[i] >= now)
dfs(u + 1, now + (t[i] - now) + l[i]); // 中间有空隙
else
dfs(u + 1, now + l[i]); // 直接降落
st[i] = false;
}
}
}
void solve()
{
memset(st, 0, sizeof st);
flag = false;
cin >> n;
for(int i = 1; i <= n; i++)
cin >> t[i] >> d[i] >> l[i];
dfs(0, 0);
if(flag) cout << "YES" << endl;
else cout << "NO" << endl;
return;
}
int main()
{
int T;
cin >> T;
while(T--) solve();
return 0;
}