ACGO挑战赛#17题解
2025-04-21 18:49:13
发布于:浙江
ACGO挑战赛#17题解
T1
根据题意判断即可,这里用了三目运算。
#include <bits/stdc++.h>
#include <cstdio>
#define int long long
#define ull unsigned long long
#define mod 998244353
#define MOD 1000000007
using namespace std;
const int N = 3e6 + 5,maxn = 5e3 + 5;
int a [N],b [N];
inline int read ()
{
int x = 0;
char c = getchar ();
while (c < '0' || c > '9') c = getchar ();
while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48),c = getchar ();
return x;
}
inline void write (int x)
{
if (x < 0) putchar ('-'),x = -x;
if (x > 9) write (x / 10);
putchar (x % 10 + '0');
return ;
}
signed main ()
{
int a,b;
cin >> a >> b;
cout << (a >= 50 && b >= 30 ? 1 : a >= 50 && b >= 15 ? 2 : 3);
return 0;
}
T2
将输入的数转为字符串进行判断是否回文,然后倒过来判断是否满足 的要求。
#include <bits/stdc++.h>
#include <cstdio>
#define int long long
#define ull unsigned long long
#define mod 998244353
#define MOD 1000000007
using namespace std;
const int N = 3e6 + 5,maxn = 5e3 + 5;
int a [N],b [N];
inline int read ()
{
int x = 0;
char c = getchar ();
while (c < '0' || c > '9') c = getchar ();
while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48),c = getchar ();
return x;
}
inline void write (int x)
{
if (x < 0) putchar ('-'),x = -x;
if (x > 9) write (x / 10);
putchar (x % 10 + '0');
return ;
}
bool check (string s)
{
string t = s;
reverse (s.begin (),s.end ());
return s == t;
}
signed main ()
{
int n;
cin >> n;
int ans = 0;
while (n --)
{
string s;
cin >> s;
int sum = 0,p = 0;
for (int i = s.size () - 1;i >= 0;i --) sum += (s [i] - '0') * pow (10,p ++);
if (sum >= 500 && sum <= 10000 && check (s)) ans ++;
}
cout << ans;
return 0;
}
T3
关于每天只要有一个人没来就不行,因此标记数组即可。
#include <bits/stdc++.h>
#include <cstdio>
#define int long long
#define ull unsigned long long
#define mod 998244353
#define MOD 1000000007
using namespace std;
const int N = 3e6 + 5,maxn = 5e3 + 5;
int a [N],b [N];
inline int read ()
{
int x = 0;
char c = getchar ();
while (c < '0' || c > '9') c = getchar ();
while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48),c = getchar ();
return x;
}
inline void write (int x)
{
if (x < 0) putchar ('-'),x = -x;
if (x > 9) write (x / 10);
putchar (x % 10 + '0');
return ;
}
signed main ()
{
int n,m;
cin >> n >> m;
for (int i = 1;i <= n;i ++)
{
for (int j = 1;j <= m;j ++)
{
int x;
cin >> x;
if (x == 0) a [j] = -1;
}
}
for (int i = 1;i <= m;i ++) a [i] = (a [i] == -1 ? 0 : 1);
int ans = 0,cnt = 0;
for (int i = 1;i <= m;i ++)
{
cnt = (a [i] == 0 ? 0 : cnt + 1);
ans = max (ans,cnt);
}
cout << ans;
return 0;
}
T4
统计每次空闲的时间能摸几次,除以 向下取整即可。
第一次空闲 。
第二次空闲 。
第 次空闲 。
第 次空闲 。
#include <bits/stdc++.h>
#include <cstdio>
#define int long long
#define ull unsigned long long
#define mod 998244353
#define MOD 1000000007
using namespace std;
const int N = 3e6 + 5,maxn = 5e3 + 5;
struct Node
{
int l,r;
} a [N];
bool cmp (Node x,Node y) {return x.l < y.l;}
inline int read ()
{
int x = 0;
char c = getchar ();
while (c < '0' || c > '9') c = getchar ();
while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48),c = getchar ();
return x;
}
inline void write (int x)
{
if (x < 0) putchar ('-'),x = -x;
if (x > 9) write (x / 10);
putchar (x % 10 + '0');
return ;
}
signed main ()
{
int n,L,m;
cin >> n >> L >> m;
for (int i = 1;i <= n;i ++) cin >> a [i].l >> a [i].r;
int ans = 0;
sort (a + 1,a + n + 1,cmp);
a [n + 1].l = L + 1;
a [0].r = 0;
for (int i = 1;i <= n + 1;i ++) ans += (a [i].l - a [i - 1].r - 1) / m;
cout << ans;
return 0;
}
T5
统计前缀和,进一步求出第 个行不行,通过前缀和减一下即可。
#include <bits/stdc++.h>
#include <cstdio>
#define int long long
#define ull unsigned long long
#define mod 998244353
#define MOD 1000000007
using namespace std;
const int N = 2e5 + 5,maxn = 5e3 + 5;
int diff [N],sum [N],pre [N],cnt [N];
inline int read ()
{
int x = 0;
char c = getchar ();
while (c < '0' || c > '9') c = getchar ();
while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48),c = getchar ();
return x;
}
inline void write (int x)
{
if (x < 0) putchar ('-'),x = -x;
if (x > 9) write (x / 10);
putchar (x % 10 + '0');
return ;
}
signed main ()
{
int n,k,q;
cin >> n >> k >> q;
for (int i = 0;i < n;i ++)
{
int l,r;
cin >> l >> r;
diff [l] ++;
diff [r + 1] --;
}
for (int i = 1;i < N;i ++) sum [i] = sum [i - 1] + diff [i];
for (int i = 1;i < N;i ++)
{
cnt [i] = (sum [i] >= k) ? 1 : 0;
pre [i] = pre [i - 1] + cnt [i];
}
while (q --)
{
int l, r;
cin >> l >> r;
cout << pre [r] - pre [l - 1] << endl;
}
return 0;
}
T6
写了个线段树,然后写挂了。
#include <bits/stdc++.h>
#include <cstdio>
#define int long long
#define ull unsigned long long
#define mod 998244353
#define MOD 1000000007
using namespace std;
const int N = 1e6 + 5,maxn = 5e3 + 5,INF = LLONG_MAX;
int a [N];
struct Tree
{
int l,r;
int mv;
int mi;
} tree [4 * N];
void build (int node,int l,int r)
{
tree [node].l = l;
tree [node].r = r;
tree [node].mv = -INF;
tree [node].mi = -1;
if (l == r) return ;
int mid = (l + r) / 2;
build (2 * node + 1,l,mid);
build (2 * node + 2,mid + 1,r);
}
void update (int node,int pos,int v)
{
if (tree [node].l == tree [node].r)
{
tree [node].mv = v;
tree [node].mi = pos;
return;
}
int mid = (tree [node].l + tree [node].r) / 2;
if (pos <= mid) update (2 * node + 1,pos,v);
else update (2 * node + 2,pos,v);
int left = 2 * node + 1;
int right = 2 * node + 2;
if (tree [left].mv > tree [right].mv)
{
tree [node].mv = tree [left].mv;
tree [node].mi = tree [left].mi;
}
else if (tree [right].mv > tree [left].mv)
{
tree [node].mv = tree [right].mv;
tree [node].mi = tree [right].mi;
}
else
{
tree [node].mv = tree [left].mv;
tree [node].mi = max (tree [left].mi,tree [right].mi);
}
}
int query (int node,int ql,int qr,int t)
{
if (tree [node].r < ql || tree [node].l > qr) return -1;
if (tree [node].mv < t) return -1;
if (tree [node].l == tree [node].r) return tree [node].mi;
int s = query (2 * node + 2,ql,qr,t);
if (s != -1) return s;
return query (2 * node + 1,ql,qr,t);
}
inline int read ()
{
int x = 0;
char c = getchar ();
while (c < '0' || c > '9') c = getchar ();
while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48),c = getchar ();
return x;
}
inline void write (int x)
{
if (x < 0) putchar ('-'),x = -x;
if (x > 9) write (x / 10);
putchar (x % 10 + '0');
return ;
}
signed main ()
{
int n,k;
cin >> n >> k;
for (int i = 0;i < n;i ++) cin >> a [i];
build (0,0,n - 1);
int ans = 0;
for (int r = 0;r < n;r ++)
{
int t = a [r] + k;
int i = -1;
if (r > 0) i = query (0, 0,r - 1,t);
if (i != -1) ans += (i + 1);
update (0,r,a[r]);
}
cout << ans;
return 0;
}
然后想到滑动窗口,可以使用双端队列 维护可能的元素下标, 记录不满足条件的子序列数, 表示当前窗口的左边界。
然后移除队列中不在当前窗口的元素,并调整左边界以排除所有满足 的元素。
可以维护单调队列实现。
#include <bits/stdc++.h>
#include <cstdio>
#define int long long
#define ull unsigned long long
#define mod 998244353
#define MOD 1000000007
using namespace std;
const int N = 2e6 + 5,maxn = 5e3 + 5,INF = 2e9;
int a [N];
inline int read ()
{
int x = 0;
char c = getchar ();
while (c < '0' || c > '9') c = getchar ();
while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48),c = getchar ();
return x;
}
inline void write (int x)
{
if (x < 0) putchar ('-'),x = -x;
if (x > 9) write (x / 10);
putchar (x % 10 + '0');
return ;
}
signed main ()
{
int n,k;
cin >> n >> k;
for (int i = 0;i < n;i ++) cin >> a [i];
deque <int> dq;
int sum = 0;
int l = 0;
for (int r = 0;r < n;r ++)
{
int x = a [r] + k;
while (! dq.empty () && dq.front () < l) dq.pop_front ();
while (! dq.empty () && a [dq.front ()] >= x)
{
l = max (l,dq.front () + 1);
dq.pop_front ();
}
sum += r - l + 1;
while (! dq.empty () && a [dq.back ()] <= a [r]) dq.pop_back ();
dq.push_back (r);
}
cout << n * (n + 1) / 2 - sum;
return 0;
}
全部评论 2
https://www.acgo.cn/application/1870763133040070656
谢谢!1周前 来自 浙江
0还是线段树大佬%%%%%%
1周前 来自 广东
0都写挂了
1周前 来自 浙江
0能帮忙调一下吗大佬
1周前 来自 浙江
0没事,还是大佬
1周前 来自 广东
0
有帮助,赞一个