ACGO挑战赛#13题解
2025-01-02 19:59:43
发布于：浙江
45阅读
0回复
0点赞
ACGO挑战赛#13题解
T1
思路
求出两个旅行者的位置再计算他们之间的距离即可。
参考代码
#include <bits/stdc++.h>
#include <cstdio>
#define int long long
#define ull unsigned long long
#define mod 988444333
#define MOD 1000000007
using namespace std;
const int N = 2e6 + 5,maxn = 5e3 + 5;
int a [maxn] [maxn];
inline int read ()
{
int x = 0;
bool f = 1;
char c = getchar ();
while (c < '0' || c > '9') f = (c == '-' ? !f : f),c = getchar ();
while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48),c = getchar ();
return (f ? x : -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 h,w;
cin >> h >> w;
int x = -1,y = -1,X,Y;
for (int i = 1;i <= h;i ++)
{
for (int j = 1;j <= w;j ++)
{
char c;
cin >> c;
if (c == 'o')
{
if (x == -1)
{
x = i;
y = j;
}
else
{
X = i;
Y = j;
}
}
}
}
cout << abs (x - X) + abs (y - Y);
return 0;
}
时间复杂度分析
循环，。
T2
思路
考虑使用 std::map 模拟数组。
对于操作1，模拟即可，即 mp [x] ++。
对于操作2，如果当前 不够 ，则将 减去 ，否则直接将当前的 提出 ，即 if (c < mp [x]) mp [x] -= c;else mp.erase (x);。
对于操作3，用当前 中的最大值减去最小值即可，即 cout << mp.rbegin () -> first - mp.begin () -> first << endl;。
参考代码
#include <bits/stdc++.h>
#include <cstdio>
#define int long long
#define ull unsigned long long
#define mod 988444333
#define MOD 1000000007
using namespace std;
const int N = 2e6 + 5,maxn = 5e3 + 5;
int a [maxn] [maxn];
map <int,int> mp;
inline int read ()
{
int x = 0;
bool f = 1;
char c = getchar ();
while (c < '0' || c > '9') f = (c == '-' ? !f : f),c = getchar ();
while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48),c = getchar ();
return (f ? x : -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 Q;
cin >> Q;
while (Q --)
{
int opt;
cin >> opt;
if (opt == 1)
{
int x;
cin >> x;
mp [x] ++;
}
if (opt == 2)
{
int x,c;
cin >> x >> c;
if (c < mp [x]) mp [x] -= c;
else mp.erase (x);
}
if (opt == 3) cout << mp.rbegin () -> first - mp.begin () -> first << endl;
}
return 0;
}
时间复杂度分析
访问 rbegin，其余 ，最终 。
T3
思路
考虑使用 std::vector 建图，再枚举从一个点相邻的点数量及哪些点进行枚举。
参考代码
#include <bits/stdc++.h>
#include <cstdio>
#define int long long
#define ull unsigned long long
#define mod 988444333
#define MOD 1000000007
using namespace std;
const int N = 1e5 + 5;
inline int read ()
{
int x = 0;
bool f = 1;
char c = getchar ();
while (c < '0' || c > '9') f = (c == '-' ? !f : f),c = getchar ();
while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48),c = getchar ();
return (f ? x : -x);
}
inline void write (int x)
{
if (x < 0) putchar ('-'),x = -x;
if (x > 9) write (x / 10);
putchar (x % 10 + '0');
return ;
}
vector <int> G [N];
signed main ()
{
int n,m;
cin >> n >> m;
while (m --)
{
int u,v;
cin >> u >> v;
G [u].push_back (v);
G [v].push_back (u);
}
for (int i = 1;i <= n;i ++)
{
sort (G [i].begin (),G [i].end ());
int q = 0;
for (auto j : G [i]) q ++;
cout << q << ' ';
for (auto j : G [i]) cout << j << ' ';
cout << endl;
}
return 0;
}
时间复杂度分析
循环中访问了 次（即每条边），但 sort 是 的，所以综合时间 。
T4
思路
数学题。
设首项为 ，共有 项，则序列为 ，算术级数之和为 ，设 ，则若知道 ，可以通过 得到，发现若 ，则 大约为 ，则 时 一定大于题目给定的 ，因此可以暴枚 算 是否为0求当前的 满不满足要求。
另外，当 时，定有序列 也满足要求；当 时，序列 也一定满足要求（因为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 = 3e3 + 5;
int x [N],y [N],z [N];
inline int read ()
{
int x = 0;
bool f = 1;
char c = getchar ();
while (c < '0' || c > '9') f = (c == '-' ? !f : f),c = getchar ();
while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48),c = getchar ();
return (f ? x : -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;
cin >> n;
int ans = 0;
for (int i = 1;i <= 2e6;i ++)
{
if (n < i * (i - 1) / 2) break;
if ((n - (i * (i - 1) / 2)) % i == 0)
{
ans += 2;
if ((n - (i * (i - 1) / 2)) / i <= 1) ans --;
}
}
cout << ans;
return 0;
}
时间复杂度分析
根据思路，时间复杂度为 ，省略 后为 。
T5
思路 by复仇者_Erika
预处理 表示 开头 结尾的子串个数，这个东西倒着做一遍前缀和就行，然后考虑一次询问的答案就是 ，再考虑修改会造成什么影响，不难发现就是减少修改前的字母，增加修改后的字母，于是对于所有26个字母，用线段树统计他前面有多少个，后面有多少个然后把贡献减掉，(注意如果 会多减一次，所以要再加回来)然后修改完的字母再做一次逆操作就行。
T6
思路
对于操作一，如果是全部赋值成0，就相当于取消前面的全部操作，那么可以通过记录有哪些位置被操作过的方式撤回。而如果是全部赋成 就再用个变量记录一下输出答案时需要加多少变化量。
操作2，3可以用数组模拟。
当然也存在线段树写法，就不贴了。
参考代码
#include <bits/stdc++.h>
#include <cstdio>
#define int long long
#define ull unsigned long long
#define mod 988444333
#define MOD 1000000007
using namespace std;
const int N = 2e6 + 5;
int a [N];
inline int read ()
{
int x = 0;
bool f = 1;
char c = getchar ();
while (c < '0' || c > '9') f = (c == '-' ? !f : f),c = getchar ();
while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48),c = getchar ();
return (f ? x : -x);
}
inline void write (int x)
{
if (x < 0) putchar ('-'),x = -x;
if (x > 9) write (x / 10);
putchar (x % 10 + '0');
return ;
}
vector <int> did;
signed main ()
{
int n;
cin >> n;
for (int i = 1;i <= n;i ++) cin >> a [i];
int q;
cin >> q;
bool flag = 0;
int tag = 0;
while (q --)
{
int opt;
cin >> opt;
if (opt == 1)
{
int x;
cin >> x;
if (! flag)
{
flag = 1;
for (int i = 1;i <= n;i ++) a [i] = 0;
}
else for (int &i : did) a [i] = 0;
tag = x;
did.clear ();
}
if (opt == 2)
{
int x,y;
cin >> x >> y;
a [x] += y;
did.push_back (x);
}
if (opt == 3)
{
int x;
cin >> x;
cout << a [x] + tag << endl;
}
}
return 0;
}
时间复杂度分析
。
有帮助，赞一个