巅峰赛 #23 两个作弊者的代码
2025-07-23 14:55:48
发布于：湖南
249阅读
0回复
0点赞
// T1
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long s = 0;
long long a[100005];
for (int i = 0; i < n; i++) {
cin >> a[i];
s += a[i];
}
if (s % n != 0) {
cout << -1 << endl;
return 0;
}
long long x = s / n;
long long ans = 0;
for (int i = 0; i < n; i++) {
if (a[i] > x) {
ans += a[i] - x;
}
}
cout << ans << endl;
return 0;
}
// T2
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100010;
ll a[N],d[N],s[N],n,bv,bs,ans;
int main(){
cin>>n;
for(int i=0;i<n;++i)cin>>a[i];
sort(a,a+n,greater<ll>());
d[0]=s[0]=a[0];
bv=d[0]+s[0];
bs=s[0];
ans=d[0];
for(int i=1;i<n;++i){
if(bv>0){
d[i]=bv+a[i];
s[i]=bs+a[i];
}else{
d[i]=a[i];
s[i]=a[i];
}
ll f=d[i]+s[i];
if(f>bv){
bv=f;
bs=s[i];
}
if(d[i]>ans)ans=d[i];
}
cout<<ans;
return 0;
}
// T3
#include <bits/stdc++.h>
using namespace std;
struct S {
int l, r, c;
bool operator==(const S& o) const {
return l == o.l && r == o.r && c == o.c;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
string s;
cin >> s;
vector<int> co(n + 1);
for (int i = 1; i <= n; ++i) {
co[i] = s[i - 1] - '0';
}
vector<int> nb(n + 1);
vector<int> nw(n + 1);
for (int i = 1; i <= n; ++i) {
nb[i] = (i - 1 < 1) ? n : i - 1;
nw[i] = (i + 1 > n) ? 1 : i + 1;
}
for (int j = 0; j < m; ++j) {
int p, l, r;
cin >> p >> l >> r;
if (p == l && p == r) {
cout << 0 << endl;
continue;
}
auto nx = [&](S st) {
if (st.c == 0) {
int nl = nb[st.l];
return S{nl, st.r, co[nl]};
} else {
int nr = nw[st.r];
return S{st.l, nr, co[nr]};
}
};
S sl = {p, p, co[p]};
S fs = nx(sl);
long long t1 = 0;
long long t2 = 1;
while (true) {
if (sl.l == l && sl.r == r) {
cout << t1 << '\n';
break;
}
if (fs.l == l && fs.r == r) {
cout << t2 << '\n';
break;
}
if (sl == fs) {
cout << -1 << '\n';
break;
}
sl = nx(sl);
t1++;
fs = nx(nx(fs));
t2 += 2;
if (t2 > 9000000LL) {
cout << -1 << '\n';
break;
}
}
}
return 0;
}
// T4
#include<bits/stdc++.h>
using namespace std;
const int N=5000;
const int mod=998244353;
int p[N];
void iii(){
p[0]=1;
for(int i=1;i<N;i++){
long long t=0;
for(int j=1;;j++){
int g1=j*(3*j-1)/2;
if(g1>i) break;
int s=(j&1)?1:-1;
t=(t+s*p[i-g1])%mod;
int g2=j*(3*j+1)/2;
if(g2<=i) t=(t+s*p[i-g2])%mod;
}
p[i]=t%mod;
if(p[i]<0) p[i]+=mod;
}
}
int main(){
iii();
int T;
cin>>T;
while(T--){
int k;
cin>>k;
cout<<p[k-1]<<endl;
}
return 0;
}
// T5
#include <bits/stdc++.h>
using namespace std;
const int N = 20010;
int n, m, idx, cnt;
int h[N], e[40010], ne[40010];
int d[N], f[N], sz[N], sn[N], tp[N], dfn[N];
int tr[80010];
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs1(int u, int p) {
f[u] = p, d[u] = d[p] + 1, sz[u] = 1;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == p) continue;
dfs1(v, u);
sz[u] += sz[v];
if (sz[v] > sz[sn[u]]) sn[u] = v;
}
}
void dfs2(int u, int t) {
tp[u] = t, dfn[u] = ++cnt;
if (!sn[u]) return;
dfs2(sn[u], t);
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == f[u] || v == sn[u]) continue;
dfs2(v, v);
}
}
int lca(int a, int b) {
while (tp[a] != tp[b]) {
if (d[tp[a]] < d[tp[b]]) swap(a, b);
a = f[tp[a]];
}
if (d[a] > d[b]) swap(a, b);
return a;
}
void upd(int u, int l, int r, int p) {
if (l == r) {
tr[u]++;
return;
}
int mid = (l + r) >> 1;
if (p <= mid) upd(u << 1, l, mid, p);
else upd(u << 1 | 1, mid + 1, r, p);
tr[u] = tr[u << 1] + tr[u << 1 | 1];
}
int qry(int u, int l, int r, int L, int R) {
if (L <= l && r <= R) return tr[u];
int mid = (l + r) >> 1, s = 0;
if (L <= mid) s += qry(u << 1, l, mid, L, R);
if (R > mid) s += qry(u << 1 | 1, mid + 1, r, L, R);
return s;
}
int qp(int a, int b) {
int s = 0;
while (tp[a] != tp[b]) {
if (d[tp[a]] < d[tp[b]]) swap(a, b);
s += qry(1, 1, n, dfn[tp[a]], dfn[a]);
a = f[tp[a]];
}
if (d[a] > d[b]) swap(a, b);
s += qry(1, 1, n, dfn[a], dfn[b]);
return s;
}
int main() {
memset(h, -1, sizeof h);
scanf("%d%d", &n, &m);
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
add(u, v), add(v, u);
}
dfs1(1, 0);
dfs2(1, 1);
while (m--) {
int op, x, y;
scanf("%d", &op);
if (op == 1) {
scanf("%d", &x);
upd(1, 1, n, dfn[x]);
} else {
scanf("%d%d", &x, &y);
int a = lca(x, y);
int L = d[x] + d[y] - 2 * d[a];
int k = qp(x, y);
printf("%d\n", L - k);
}
}
return 0;
}
// T1
#include<iostream>
using namespace std;
int n;
long long a[100005];
int main(){
cin >> n;
for(int i = 0; i < n; i++){
cin >> a[i];
}
long long s = 0;
for(int i = 0; i < n; i++){
s += a[i];
}
if(s % n){
cout << -1;
return 0;
}
long long t = s / n;
long long ans = 0;
for(int i = 0; i < n; i++){
if(a[i] > t){
ans += a[i] - t;
}
}
cout << ans;
return 0;
}
// T2
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = LLONG_MIN;
ll n;
vector<ll> a;
int main() {
cin >> n;
a.resize(n);
for (int i = 0; i < n; i++) cin >> a[i];
sort(a.rbegin(), a.rend());
ll bF = INF, bS = 0, ans = INF;
for (int i = 0; i < n; i++) {
ll dp = a[i], s = a[i];
if (bF != INF) {
ll t = bF + a[i];
if (t > dp) {
dp = t;
s = bS + a[i];
}
}
if (dp > ans) ans = dp;
ll f = dp + s;
if (bF == INF) {
bF = f;
bS = s;
} else {
if (f > bF) {
bF = f;
bS = s;
} else if (f == bF) {
if (s > bS) bS = s;
}
}
}
cout << ans;
return 0;
}
// T3
#include<bits/stdc++.h>
using namespace std;
const int N = 3005;
short Lpos[N][N];
int nxt[N];
int col[N];
int n,m;
inline int pre(int x){ return x==1 ? n : x-1; }
inline int nxtc(int x){ return x==n ? 1 : x+1; }
int main(){
while(cin>>n>>m){
string s; cin>>s;
for(int i=1;i<=n;++i) col[i]=s[i-1]-'0';
for(int st=1; st<=n; ++st){
int x=st, y=st, z=col[st];
Lpos[st][0]=x;
for(int d=1; d<=n; ++d){
if(z==0){
x = pre(x);
z = col[x];
}else{
y = nxtc(y);
z = col[y];
}
if(d<n) Lpos[st][d]=x;
}
nxt[st]=x;
}
for(int i=0;i<m;++i){
int p,l,r; cin>>p>>l>>r;
int d = (r-l+n)%n;
int pos = p;
int ans = -1;
for(int k=0; ; ++k){
if(Lpos[pos][d]==l){
ans = k*n + d;
break;
}
pos = nxt[pos];
if(pos==p) break;
}
cout<<ans<<"\n";
}
}
return 0;
}
// T4
#include<iostream>
#include<vector>
using namespace std;
const int mod = 998244353;
const int max_n = 5000;
int main() {
vector<long long> dp(max_n + 1, 0);
dp[0] = 1;
for (int n = 1; n <= max_n; n++) {
long long total = 0;
int j = 1;
while (true) {
int pent1 = j * (3 * j - 1) / 2;
if (pent1 > n) break;
long long sign = (j % 2 == 1) ? 1 : -1;
total = (total + sign * dp[n - pent1]) % mod;
int pent2 = j * (3 * j + 1) / 2;
if (pent2 <= n) {
total = (total + sign * dp[n - pent2]) % mod;
}
j++;
}
dp[n] = total % mod;
if (dp[n] < 0) dp[n] += mod;
}
int T;
cin >> T;
while (T--) {
int k;
cin >> k;
cout << dp[k - 1] << endl;
}
return 0;
}
// T5
#include<bits/stdc++.h>
using namespace std;
const int N = 500010;
int n, m;
vector<int> g[N];
int f[N], d[N], sz[N], sn[N], tp[N], dfn[N], cnt;
int c[N];
void ad(int x, int v) {
for (; x <= n; x += x & -x) c[x] += v;
}
int qr(int x) {
int s = 0;
for (; x; x -= x & -x) s += c[x];
return s;
}
int qr(int l, int r) {
return qr(r) - qr(l - 1);
}
void d1(int u, int fa) {
f[u] = fa;
d[u] = d[fa] + 1;
sz[u] = 1;
sn[u] = 0;
for (int v : g[u]) {
if (v == fa) continue;
d1(v, u);
sz[u] += sz[v];
if (sz[v] > sz[sn[u]]) sn[u] = v;
}
}
void d2(int u, int t) {
tp[u] = t;
dfn[u] = ++cnt;
if (!sn[u]) return;
d2(sn[u], t);
for (int v : g[u]) {
if (v == f[u] || v == sn[u]) continue;
d2(v, v);
}
}
int lca(int u, int v) {
while (tp[u] != tp[v]) {
if (d[tp[u]] < d[tp[v]]) swap(u, v);
u = f[tp[u]];
}
return d[u] < d[v] ? u : v;
}
int ps(int u, int v) {
int s = 0;
while (tp[u] != tp[v]) {
if (d[tp[u]] < d[tp[v]]) swap(u, v);
s += qr(dfn[tp[u]], dfn[u]);
u = f[tp[u]];
}
if (d[u] > d[v]) swap(u, v);
s += qr(dfn[u], dfn[v]);
return s;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
d1(1, 0);
d2(1, 1);
while (m--) {
int op, x, y;
scanf("%d", &op);
if (op == 1) {
scanf("%d", &x);
ad(dfn[x], 1);
} else {
scanf("%d%d", &x, &y);
int a = lca(x, y);
int dis = d[x] + d[y] - 2 * d[a];
int k = ps(x, y);
printf("%d\n", dis - k);
}
}
return 0;
}
// T6
#include<bits/stdc++.h>
using namespace std;
int n, m;
string c;
vector<int> s, w, b;
vector<long long> l, r;
long long inf = 1LL << 60;
int main() {
cin >> n >> m >> c;
s.resize(n);
for (int i = 0; i < n; i++) {
s[i] = c[i] - '0';
(s[i] ? w : b).push_back(i);
}
l.assign(n, inf);
if (!w.empty()) {
int k = w.size();
for (int i = 0; i < k; i++) {
int p = w[i], v = i ? w[i - 1] : w[k - 1];
l[p] = (p - v + n) % n;
}
for (int i = 0; i < k; i++) {
int p = w[i], x = (i + 1 < k ? w[i + 1] : w[0] + n);
for (int j = p + 1; j < x; j++) l[j % n] = j - p;
}
}
r.assign(n, inf);
if (!b.empty()) {
int k = b.size();
for (int i = 0; i < k; i++) {
int p = b[i], x = (i + 1 < k ? b[i + 1] : b[0] + n);
r[p] = x - p;
for (int j = p + 1; j < x; j++) r[j % n] = x - j;
}
}
while (m--) {
int p, a, b;
cin >> p >> a >> b;
int x = p - 1, y = x, gl = a - 1, gr = b - 1, f = s[x];
long long t = 0;
if (x == gl && y == gr) {
cout << 0 << '\n';
continue;
}
unordered_set<long long> st;
bool z = (f == 0);
while (1) {
long long h = (z ? 1LL * n * n : 0) + 1LL * x * n + y;
if (st.count(h)) {
cout << -1 << '\n';
break;
}
st.insert(h);
bool ok = 0;
long long d;
if (z) {
d = l[x];
if (d == inf) {
if (y == gr) {
long long q = (x - gl + n) % n;
if (q > 0) {
t += q;
cout << t << '\n';
ok = 1;
}
} else {
cout << -1 << '\n';
ok = 1;
}
} else {
if (y == gr) {
long long q = (x - gl + n) % n;
if (q > 0 && d >= q) {
t += q;
cout << t << '\n';
ok = 1;
} else {
t += d;
x = (x - d + n) % n;
}
} else {
t += d;
x = (x - d + n) % n;
}
}
if (ok) break;
z = 0;
} else {
d = r[y];
if (d == inf) {
if (x == gl) {
long long q = (gr - y + n) % n;
if (q > 0) {
t += q;
cout << t << '\n';
ok = 1;
}
} else {
cout << -1 << '\n';
ok = 1;
}
} else {
if (x == gl) {
long long q = (gr - y + n) % n;
if (q > 0 && d >= q) {
t += q;
cout << t << '\n';
ok = 1;
} else {
t += d;
y = (y + d) % n;
}
} else {
t += d;
y = (y + d) % n;
}
}
if (ok) break;
z = 1;
}
if (x == gl && y == gr) {
cout << t << '\n';
break;
}
}
}
return 0;
}
全部评论 3
大家可以看看最终的xt事件处理结果，算是支持支持吧，感谢ac君的捧场
https://www.acgo.cn/discuss/post/48480（点击链接即可查看）1周前 来自 辽宁
1xt分扣太多受不了，开始乱喷，见人就喷，喷官方给ta扣太多分，喷那些说ta用AI的，反正就是急眼了，然后cjdst出来和ta对线，结果都被禁言了
1周前 来自 浙江
0
有帮助，赞一个