题解
A 三连-签到！
using namespace std;
using i64 = longlong;
#define all(t) t.begin(), t.end()
voidsolve()
{
intn;
cin >> n;
intans = 0;
map<int, int> cnt;
for (inti = 0; i < n; i++)
{
intx;
cin >> x;
cnt[x]++;
}
for (auto [k, v] : cnt)
{
ans += v / 3;
}
cout << ans;
}
signed main()
{
std::ios_base::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);
int_ = 1; // std::cin >> _;
while (_--)
solve();
return0;
}
B 会长的牌子呢？
#include <bits/stdc++.h>
using namespace std;
#define ll longlong
#define mod 1000000007
inttt, n, m;
string s;
voidsolve()
{
intx1, x2, x3, y1, y2, y3;
cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
intxx1 = x2 - x1, yy1 = y2 - y1, xx2 = x3 - x1, yy2 = y3 - y1;
cout << fixed << setprecision(1) << abs(1.0 * (xx1 * yy2 - xx2 * yy1)) / 2;
}
intmain()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
tt = 1;
// cin>>tt;
while (tt--)
solve();
}
C 走迷宫
#include <bits/stdc++.h>
using namespace std;
using i64 = longlong;
#define all(t) t.begin(), t.end()
using PII = pair<int, int>;
constintINF = 0x3f3f3f3f;
voidsolve()
{
intn, m;
cin >> n >> m;
vector<string> s(n + 1);
vector<vector<int>> dis(n + 1, vector<int>(m + 1, 0x3f3f3f3f));
for (inti = 1; i <= n; i++)
{
cin >> s[i];
s[i] = ' ' + s[i];
}
PII S, T;
for (inti = 1; i <= n; i++)
for (intj = 1; j <= m; j++)
{
if (s[i][j] == 'S')
S = {i, j};
if (s[i][j] == 'E')
T = {i, j};
}
dis[S.first][S.second] = 0;
queue<PII> q;
q.push(S);
while (q.size())
{
auto [x, y] = q.front();
q.pop();
intdx[] = {0, 1, 0, -1};
intdy[] = {1, 0, -1, 0};
for (inti = 0; i < 4; i++)
{
inttx = x + dx[i], ty = y + dy[i];
if (tx < 1 || tx > n || ty < 1 || ty > m)
continue;
if (s[tx][ty] == '@')
continue;
if (dis[tx][ty] != INF)
continue;
dis[tx][ty] = dis[x][y] + 1;
q.push({tx, ty});
}
}
cout << (dis[T.first][T.second] == INF ? -1 : dis[T.first][T.second]);
}
signed main()
{
// std::ios_base::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);
int_ = 1; // std::cin >> _;
while (_--)
solve();
return0;
}
D 顺时针的正方形
#include <bits/stdc++.h>
using namespace std;
#define ll longlong
#define mod 1000000007
inttt, n, m;
string s[1005];
voidsolve()
{
cin >> n;
ll ans = 0;
for (inti = 1; i <= n; i++)
cin >> s[i], s[i] = ' ' + s[i];
for (inti = 1; i <= n / 2; i++)
{
for (intk = 1; k <= n / 2; k++)
{
intx1 = i, y1 = k;
intx2 = k, y2 = n - i + 1;
intx3 = n - i + 1, y3 = n - k + 1;
intx4 = n - k + 1, y4 = i;
intmxch = max(s[x1][y1], max(s[x2][y2], max(s[x3][y3], s[x4][y4])));
ans += mxch * 4 - s[x1][y1] - s[x2][y2] - s[x3][y3] - s[x4][y4];
}
}
cout << ans << '\n';
}
intmain()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// tt=1;
cin >> tt;
while (tt--)
solve();
}
E 据说XCPC每题首杀的气球不一样哦
#include <bits/stdc++.h>
using namespace std;
#define ll longlong
#define mod 1000000007
inttt, n, m, t1[200005], t2[200005];
string s;
bool ck(intt)
{
intsm = 0;
for (inti = 1; i <= n; i++)
{
intns = t / (t1[i] + t2[i]);
if (t - ns * (t1[i] + t2[i]) >= t1[i])
ns++;
sm += ns;
}
returnsm >= m;
}
voidsolve()
{
cin >> n >> m;
for (inti = 1; i <= n; i++)
{
cin >> t1[i] >> t2[i];
}
intl = 0, r = mod, mid, ans = mod;
while (l <= r)
{
mid = l + r >> 1;
if (ck(mid))
ans = mid, r = mid - 1;
else
l = mid + 1;
}
cout << ans;
/*intsm=0;
for(inti=1;i<=n;i++){
intns=ans/(t1[i]+t2[i]);
if(ans-ns*(t1[i]+t2[i])>=t1[i])ns++;
cout<<ns<<' ';sm+=ns;
}
cout<<sm;*/
}
intmain()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
tt = 1;
// cin>>tt;
while (tt--)
solve();
}
F 最大子区间
#include <bits/stdc++.h>
using namespace std;
#define ll longlong
#define mod 1000000007
inttt, n, m, a[200005], b[200005];
string s;
voidsolve()
{
cin >> n >> m;
intmx = 0;
for (inti = 1; i <= n; i++)
{
cin >> a[i];
b[i] = b[i - 1] + a[i] - a[max(0, i - m)];
if (b[i] > mx)
{
mx = b[i];
}
}
// for (int i = 1; i <= 100; i++)cout << b[i] << ' ';
// cout << '\n';
// cout<<mx<<'\n';
for (inti = 1; i <= n; i++)
{
if (b[i] == mx)
{
intr = i, l = max(1, i - m + 1);
cout << l << ' ' << r << '\n';
while (a[l] == 0 && l + 1 <= r)
{
cout << ++l << ' ' << r << '\n';
}
}
}
}
intmain()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
tt = 1;
// cin>>tt;
while (tt--)
solve();
}
G 最大最长子区间
#include <bits/stdc++.h>
using namespace std;
#define ll longlong
#define mod 1000000007
inttt, n, m, a[200005], dp[200005], l[200005];
string s;
vector<pair<int, int>> vt;
voidsolve()
{
cin >> n;
intmx = 0, mx_len = 0;
l[0] = 1;
for (inti = 1; i <= n; i++)
{
cin >> a[i];
if (dp[i - 1] + a[i] >= 0)
{
dp[i] = dp[i - 1] + a[i];
l[i] = l[i - 1];
}
else
{
dp[i] = 0;
l[i] = i + 1;
}
mx = max(mx, dp[i]);
}
// for(int i=1;i<=n;i++)cout<<dp[i]<<' ';cout<<'\n';
// for(int i=1;i<=n;i++)cout<<l[i]<<' ';cout<<'\n';
for (inti = 1; i <= n; i++)
{
if (dp[i] == mx)
{
intlen = i - l[i] + 1;
if (len > mx_len)
{
vt.clear();
mx_len = len;
}
if (mx_len == len)
vt.push_back({l[i], i});
}
}
for (auto it : vt)
cout << it.first << ' ' << it.second << '\n';
}
intmain()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
tt = 1;
// cin>>tt;
while (tt--)
solve();
}
H 团建前的准备
#include <bits/stdc++.h>
using namespace std;
#define ll longlong
#define mod 1000000007
inttt, n, m;
string s;
map<int, map<int, int>> mp;
set<int> st[200005];
priority_queue<pair<int, int>> q;
priority_queue<pair<double, int>> q2;
voidsolve()
{
cin >> n >> m;
intx, y, z;
for (inti = 1; i <= m; i++)
{
cin >> x >> y >> z;
mp[x][y] = max(mp[x][y], z);
st[x].insert(y);
}
for (inti = 1; i <= n; i++)
{
intw = 0;
for (auto it : st[i])
w += mp[i][it];
q.push({w, i});
if (w)
q2.push({1.0 * w / st[i].size(), i});
}
cout << q.top().second << ' ';
// 总评分最高
cout
<< q2.top().second << '\n';
// 防止踩雷
}
intmain()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
tt = 1;
// cin>>tt;
while (tt--)
solve();
}
I 赶不上团建啦
这里我用的是深搜回去找状态的方法 因为一开始是想把每条最短路径详细输出的 后来还是降低了点难度 不过没人在比赛的时候做出来 也许不该减的？
#include <bits/stdc++.h>
using namespace std;
#define ll longlong
#define mod 1000000007
inttt, n, m, dis[200005], ans, cnt, lu[200005];
string s;
struct node
{
intv, w;
};
vector<node> vt[200005];
set<int> e[200005];
queue<int> q;
voiddfs(intu)
{
if (u == 1)
{
// for(int i=cnt;i;i--)cout<<lu[i]<<' ';cout<<'\n';
ans++;
return;
}
for (auto it : e[u])
{
lu[++cnt] = it;
dfs(it);
cnt--;
}
}
voidsolve()
{
cin >> n >> m;
intu, v, w;
memset(dis, 0x7f, sizeof(dis));
dis[1] = 0;
for (inti = 1; i <= m; i++)
{
cin >> u >> v >> w;
vt[u].push_back({v, w});
vt[v].push_back({u, w});
}
q.push(1);
while (!q.empty())
{
intu = q.front();
q.pop();
for (auto it : vt[u])
{
intv = it.v, w = it.w + dis[u];
if (w < dis[v])
{
dis[v] = w;
q.push(v);
e[v].clear();
e[v].insert(u);
}
elseif(w == dis[v])
{
e[v].insert(u);
}
}
}
if (dis[n] == int(0x7f7f7f7f))
cout << "-1\n";
else
cout << dis[n] << '\n';
lu[++cnt] = n;
dfs(n);
cout << ans << '\n';
// for(int i=1;i<=n;i++)cout<<dis[i]<<' ';
}
intmain()
{
// ios::sync_with_stdio(false);
// cin.tie(0);cout.tie(0);
tt = 1;
// cin>>tt;
while (tt--)
solve();
}
J 终于团建上了
这个题本意是想让挑战者用线段树做的，但其实通过前缀差分的方法也可以 不过数据当时没捏好，有人偷偷蒙混过关了！现在数据已修正
#include <bits/stdc++.h>
using namespace std;
#define ll longlong
#define mod 1000000007
inttt, n, m, a[150000], k;
// 10Ěě144000ˇÖÖÓ
intlowbit(intx)
{
returnx & -x;
}
voidadd(intid, intx)
{
for (inti = id; i <= 144000; i += lowbit(i))
a[i] += x;
}
inttk(intid)
{
intans = 0;
for (inti = id; i; i -= lowbit(i))
ans += a[i];
returnans;
}
voidsolve()
{
cin >> n >> m >> k;
intid, l, r;
for (inti = 1; i <= k; i++)
{
cin >> id >> l >> r;
add(l, 1);
add(r + 1, -1);
// for(int i=1;i<=10;i++)cout<<tk(i)<<' ';cout<<'\n';
}
for (inti = 1; i <= 144000; i++)
{
if (n <= m - tk(i))
{
cout << i;
return;
}
}
cout << "-1";
}
intmain()
{
// ios::sync_with_stdio(false);
// cin.tie(0);cout.tie(0);
tt = 1;
// cin>>tt;
while (tt--)
solve();
}
K 最简数
应该是很简单的一个模拟 每次压缩一下再回退一下就ok了 再考虑“22”的情况，会不会一直陷入死循环
#include <bits/stdc++.h>
using namespace std;
#define ll longlong
#define mod 1000000007
inttt, n, m, a[200005], b[200005];
string s;
voidsolve()
{
cin >> n >> s;
for (inti = 0; i < n; i++)
{
intns = 1;
while (i < n - 1 && s[i] == s[i + 1])
i++, ns++;
if (ns == 1)
{
continue;
}
if (ns == 2 && s[i] == '2')
continue;
string sr = s[i] + to_string(ns);
n = n - (ns - sr.size());
i = i - ns;
s.replace(i + 1, ns, sr);
// cout<<s<<'\n';
}
cout << s;
}
intmain()
{
// ios::sync_with_stdio(false);
// cin.tie(0);cout.tie(0);
tt = 1;
// cin>>tt;
while (tt--)
solve();
}
但是每次通过replace()操作时间复杂度最坏为O(n^2),在数据足够强的话也会被卡掉 加上很多人喜欢在for(inti=0;i<s.size();i++)里面使用replace()，去看看c++的书，想想为什么不能这么干 下面是O(n)的做法
#include <bits/stdc++.h>
using namespace std;
#define ll longlong
#define mod 998244353
inttt, n, m, ns;
string s, ss;
voidsolve()
{
cin >> n >> s;
for (inti = 0; i < n; i++)
{
if (i == n - 1 || s[i] != s[i + 1])
{
cout << s[i];
continue;
} //
ns = 1;
while (s[i] == s[i + 1])
i++, ns++;
ss = s[i] + to_string(ns);
if (ss == "22")
{
cout << "22";
continue;
}
for (intk = ss.size() - 1; k >= 0; k--, i--)
s[i] = ss[k];
}
}
intmain()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
// cin>>tt;
tt = 1;
while (tt--)
solve();
return0;
}
L 梦不可及的ak
这个题就非常有意思了 总体考虑三种情况，答案分别为n,2~n-1,1 其中n的情况只有在所有数字相同的情况下得到 1的话是万能答案，但是我们求得是最大值，答案可能不是1 那么我们在排除n的情况下，只需要考虑2~n-1的情况，最后无脑输出1即可 我们从答案出发，假设n个数不断选取m个数-1，剩下的数都为x，一共选取了y次，可以发现x*n+y*m=sm,其中sm为原数组的总和 限制条件为 0<=x<=mi(mi为原数组的最小值),y>=0(非负即可)
#include <bits/stdc++.h>
using namespace std;
#define ll longlong
#define mod 1000000007
inttt, n, m, a[200005];
string s;
voidexgcd(ll a, ll b, ll &x, ll &y)
{
if (b == 0)
{
x = 1, y = 0;
return;
}
exgcd(b, a % b, y, x);
y -= (a / b) * x;
}
voidsolve()
{
cin >> n;
intmi = mod, sm = 0, mx = 0;
for (inti = 1; i <= n; i++)
{
cin >> a[i];
mi = min(mi, a[i]);
mx = max(mx, a[i]);
sm = sm + a[i];
}
if (mi == mx)
{
cout << n << '\n';
return;
}
for (inti = n - 1; i > 1; i--)
{
ll x, y, aa = n, bb = i, c = sm, gd = __gcd(aa, bb);
if (sm % gd != 0)
continue;
aa /= gd;
bb /= gd;
c /= gd;
exgcd(aa, bb, x, y);
ll xx = x * sm, yy = y * sm;
intns = xx / bb;
xx -= ns * bb, yy += ns * aa;
if (x < 0)
xx += bb, yy -= aa;
if (xx > mi || yy < 0)
continue;
cout << i << '\n';
return;
}
cout << "1\n";
}
intmain()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// tt=1;
cin >> tt;
while (tt--)
solve();
}