补题链接：http://oj.eriktse.com/contest.php?cid=1001
比赛信息
ETOJ的第一场周赛，整体难度偏低，适合基础薄弱的同学。
奖励：第一名一个月大会员。
出题人：eriktse
验题人：Jakon
QQ交流群：600240150
A 带余除法
签到语法题。
#include<iostream>
using namespace std;
int main()
{
int a,b;
cin>>a>>b;
cout<<a/b<<" "<<a%b<<endl;
return 0;
}
B 这也能随机？
把每一个数字分解后计算数位出现次数即可，注意特判$0$。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 9, inf = 8e18;
int a[N], cnt[12];
void f(int x)
{
while(x)cnt[x % 10] ++, x /= 10;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m, x;cin >> n >> m >> x;
mt19937 rng(x);
for(int i = 1;i <= n; ++ i)a[i] = rng() % m;
//for(int i = 1;i <= n; ++ i)cout << a[i] << ' ';
//cout << '\n';
for(int i = 1;i <= n; ++ i)
{
f(a[i]);
}
int ans = 0;
for(int i = 0;i <= 9; ++ i)if(cnt[i] > cnt[ans])ans = i;
cout << ans << '\n';
return 0;
}
C 最大子段和
模板题，dp。
dp[i]表示到i为止，且以i结尾的最大子段和，可以从dp[i - 1]转移过来，当转移过来比0还小，就单独成为一个子段。
因为这个转移过于简单，所以可以直接用一个变量保存。
下面用两种写法：
写法一：
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 9, inf = 8e18;
int a[N], dp[N];
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;cin >> n;
for(int i = 1;i <= n; ++ i)cin >> a[i];
int ans = -inf;
for(int i = 1;i <= n; ++ i)
{
//重新开始一个子段，或和上一个子段连接起来
dp[i] = max(a[i], dp[i - 1] + a[i]);
}
for(int i = 1;i <= n; ++ i)ans = max(ans, dp[i]);
cout << ans << '\n';
return 0;
}
写法二：
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 9, inf = 8e18;
int a[N];
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;cin >> n;
for(int i = 1;i <= n; ++ i)cin >> a[i];
int ans = -inf;
for(int i = 1, tmp = 0;i <= n; ++ i)
{
tmp += a[i];
ans = max(ans, tmp);
if(tmp < 0)tmp = 0;
}
cout << ans << '\n';
return 0;
}
D 联通块问题（1）
并查集模板，计算每个点对祖先的贡献即可。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 9;
int a[N], pre[N], w[N];
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;cin >> n;
for(int i = 1;i <= n; ++ i)cin >> a[i];
for(int i = 1;i <= n; ++ i)pre[i] = i;
int m;cin >> m;
function<int(int)> root = [&root](int x) -> int
{
return pre[x] = (pre[x] == x ? x : root(pre[x]));
};
for(int i = 1;i <= m; ++ i)
{
int u, v;cin >> u >> v;
pre[root(u)] = root(v);
}
int ans = 0;
for(int i = 1;i <= n; ++ i)w[root(i)] ^= a[i];
for(int i = 1;i <= n; ++ i)ans = max(ans, w[i]);
cout << ans << '\n';
return 0;
}
E 小e的书架
有两种思路来做这题。
思路一：根据贪心选择性质，显然应该优先横着放，最后一部分选择竖着放或横着放。特判“只能横着放”的情况。对于每种情况，可以直接计算出所需的最小书架长度。
当$h > t$时，只能横着放，假设有$x$个长度为$h$的空间，则有：
$$x \times t \ge n$$
$$x \ge \lceil \frac{n}{t} \rceil$$
故总长度需要满足：
$$ans = x \times h \ge \lceil \frac{n}{t} \rceil \times h$$
当$h <= t$时，可以选择全部横着放，也可以选择将最后一部分竖着放，类似的分析即可，具体看代码。
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n, h, t;
cin >> n >> h >> t;
if (h > t) {//只能横着放
long long ans = (n + t - 1ll) / t * h;
cout << ans << '\n';
return;
}
long long num = n / t;//num表示前面横着放满的块数
long long ans = min((n + t - 1ll) / t * h, num * h + n - num * t);
cout << ans << '\n';
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
int test;
cin >> test;
while (test--) {
solve();
}
return 0;
}
思路二：
二分，确定一个长度后，判断是否能够放得下$n$本书。虽然复杂度不如前一种方法，但是思想值得学习。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 9;
int a[N], p[N];
void solve()
{
int n, h, t;cin >> n >> h >> t;
int l = 0, r = 1e15;
while(l + 1 != r)
{
int mid = (l + r) >> 1;
int cnt = (mid / h) * t;
//如果可以竖着放，就加上这部分
if(t >= h)cnt += mid % h;
if(cnt >= n)r = mid;
else l = mid;
}
cout << r << '\n';
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int _;cin >> _;
while(_ --)solve();
return 0;
}
Comments NOTHING