ACOI #1 全题解
2025-06-04 22:57:22
发布于：广东
146阅读
0回复
0点赞
T1
个人难度：红 中
按题意模拟即可，平均值就是所有 的总和除以 。
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin >> t;
while(t--){
int n,m,a[11]{},f = 0;
cin>>n>>m;
double sum = 0.0;//注意求平均值需要用double保留小数位
for(int i = 1;i<=n;++i){
cin>>a[i];//输入
if(a[i]>=m) f = 1;//如果
sum+=a[i];//加上a[i]
}
cout<<(f?"OPPOA5\n":"OK!\n");//三目运算符，不会的可以用if - else代替
printf("%.3lf\n",sum/n);//计算平均值，用printf保留3位小数
}
}
时间复杂度 。
T2
个人难度：橙 下
当 为偶数时，由平方差公式得：
奇数同理，结果为 。
因为套了一层绝对值，所以输出 即可。
注意答案可能会超过 ，所以应开 long long。
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
long long n;
cin>>n;
cout<<(n*(n+1))/2<<'\n';//计算
}
}
时间复杂度 。
T3
个人难度：橙 中
注意到本题可以通过 的算法，所以我们使用深度优先搜索完成。
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,a[30],ans = 0;
void dfs(int k,int sum){
if(k == n)return;//枚举完所有状态了
dfs(k+1,sum);//不吃这桶泡面，枚举之后的状态
sum^=a[k];//异或，表示吃这桶泡面
ans = max(ans,sum);//记录最大值
dfs(k+1,sum);//枚举之后的状态
sum^=a[k];//异或回来，回溯
}
signed main(){
cin>>n;
for(int i = 0;i<n;++i) cin>>a[i];
dfs(0,0);
cout<<ans;
}
时间复杂度 。
T4
个人难度：橙 上/黄 下
可以发现分组的个数满足单调性，即体力和最小的小组体力和越大，组的数量越少。
所以我们可以二分答案，贪心计算当体力和最小的小组体力和大于等于 时，分组的最少数量是否小于 。
#include<bits/stdc++.h>
using namespace std;
int n,k,a[30009],ans;
bool check(int mid){//贪心
int sum = 0,ssum = 0;
for(int i = 1;i<=n;++i){
sum+=a[i];
if(sum>mid) ssum++,sum = 0;//如果超过了，就新开一组
if(sum<mid&&ssum>=k) return 0;//如果大于等于k，就说明答案大于等于当前的mid
}
return 1;//否则就说明答案小于当前的mid
}
int main(){
cin>>n>>k;
int l = 0,r = 0;
for(int i = 1;i<=n;++i){
cin>>a[i];
r+=a[i];//答案最大可能为所有a[i]的总和
}
while(l<=r){
int mid = (l+r)/2;
if(check(mid)){//二分答案
ans = mid;
r = mid-1;
}else l = mid+1;
}
cout<<ans;
}
时间复杂度 。
T5
个人难度：黄 下
我们可以参考不同的路径_信奥算法普及/提高-_官方-ACGO题库，运用动态规划的思想求得最大值。
注意特殊情况：
2 2
1 1
4 5
1 2
2 1
这种情况虽然没直接告诉你 被封死了，但你也不能到达了。
所以我们应该判断它的左边和上面是否都是 0（即到达不了）。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 9;
long long dp[maxn][maxn];
int a[maxn][maxn];
bool vis[maxn][maxn];
int main() {
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) cin >> a[i][j];
}
for (int i = 0; i < k; i++) {
int x, y;
cin >> x >> y;
vis[x][y] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (vis[i][j]) continue;
if (i == 1 && j == 1) {
dp[1][1] = a[1][1];
continue;
}
if (dp[i - 1][j] || dp[i][j - 1]) {//如果有一个能走到才能加
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + a[i][j];
}
}
}
cout << (dp[n][n] ? dp[n][n] : -1);
return 0;
}
时间复杂度 。
T6
个人难度：黄 上/绿 下
50pts
按题意模拟即可。
#include <iostream>
#include <cstdio>
using namespace std;
int a[200005], b[200005];
const int mod = 1e9 + 7;
int main(){
cin.tie(nullptr) -> sync_with_stdio(0);
cout.tie(nullptr) -> sync_with_stdio(0);
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) cin >> b[i];
int ct = 0, cur = 1;
while(m--){
cur = (cur + b[cur] - 1) % n + 1;//移动
ct = (ct + a[cur]) % mod;//加分
}
cout << ct;
return 0;
}
时间复杂度：。
100pts
由于在一个点内移动到的点相同，所以在 步内必定走进一个环，然后就会一直在这个环内循环，如图所示。
构成了一个环。
而找环也很简单，只需要看看当前的点之前有没有遍历到就行了。
所以答案就是 到达环之前链部分得的分数+遍历整个环得到的分数+剩下的步数获得的分数。
#include <iostream>
#include <cstdio>
#include <memory.h>
#define int long long
using namespace std;
int a[1000005], b[1000005], vis[1000005];
const int mod = 1e9 + 7;
int n, m;
int ans;
int tmp = 1, ct, len;
inline int next(int idx){return (idx + b[idx] - 1) % n + 1;}//获取下一步
void init_circle(){//找环
memset(vis, -1, sizeof(vis));
while(vis[tmp] == -1){
vis[tmp] = ct;
tmp = next(tmp);
ct++;
}
len = ct - vis[tmp];//计算环长
}
void get_chain(){//预处理链部分
m -= vis[tmp];
for(int i = 1; i != tmp;){
i = next(i);
ans = (ans + a[i]) % mod;
}
}
void calc_circle(){//计算遍历整环的次数以及获得的分数
int count = m / len % mod;//计算绕环的次数，根据取模乘法的性质我们可以提前取模
int score = 0;
for(int i = next(tmp); i != tmp;){//计算遍历一次环获得的分数
score = (score + a[i]) % mod;
i = next(i);
}
score = (score + a[tmp]) % mod;
cout << score << '\n';
ans = (ans + count * score) % mod;
}
void end_circle(){//计算最后不到一个环获得的分数
int last = m % len;//剩下的次数
int i = tmp;
while(last--){
i = next(i);
ans = (ans + a[i]) % mod;
}
}
signed main(){
cin.tie(nullptr) -> sync_with_stdio(0);
cout.tie(nullptr) -> sync_with_stdio(0);
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) cin >> b[i];
init_circle();
if(m >= vis[tmp]) get_chain();
calc_circle();
end_circle();
cout << ans % mod;
return 0;
}
时间复杂度：。
适用范围：。
100pts+
我们也可以使用倍增实现。
记 为在点 跳 格后到达的点， 为在点 跳 格后获得的分数，然后位运算累加即可。由于不是正解，故不多讲解。
//倍增自测
#include <iostream>
#include <cstdio>
using namespace std;
int a[200005], b[200005];
int cur[65][200005], ct[65][200005];
//cur表示在第j个点跳2^i次后到达的点，ct表示此时的得分
int n;
unsigned long long m;
const int mod = 1000000007;
int main(){
cin.tie(nullptr) -> sync_with_stdio(0);
cout.tie(nullptr) -> sync_with_stdio(0);
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) cin >> b[i];
for(int i = 1; i <= n; i++){
cur[0][i] = (i + b[i] - 1) % n + 1;
ct[0][i] = a[cur[0][i]];
}
for(int i = 1; i < 64; i++){
for(int j = 1; j <= n; j++){
cur[i][j] = cur[i - 1][cur[i - 1][j]];
ct[i][j] = (ct[i - 1][j] + ct[i - 1][cur[i - 1][j]]) % mod;
//合并两个小块
}
}
int ans = 0, curx = 1;
for(int i = 0; i < 64; i++){
if(m >> i & 1){
ans = (ans + ct[i][curx]) % mod;
curx = cur[i][curx];
}
}
cout << ans;
return 0;
}
时间复杂度：。
适用范围：。
150pts
这部分也很简单，只需要把 转换成高精，编写高精比较，减，除，模低精即可。
#include <iostream>
#include <cstdio>
#include <memory.h>
#define int long long
using namespace std;
struct bigInt{
int a[200005];
int len;
bigInt(){
memset(a, 0, sizeof(a));
len = 1;
}
friend istream &operator >> (istream &cin, bigInt &n){//初始化
string s;
cin >> s;
n.len = s.length();
for(int i = 0; i < s.length(); i++){
n.a[n.len - i] = s[i] - '0';
}
return cin;
}
const bool operator >= (const int n) const{//高精和低精比较大小
if(len > 6) return 1;
int tmp = 0;
for(int i = len; i >= 1; i--) tmp = tmp * 10 + a[i];
return (tmp >= n);
}
const void operator -= (const int n){//高精减低精
a[1] -= n;
for(int i = 1; i <= len; i++){
if(a[i] >= 0) return;
int tmp = -a[i] / 10;
a[i] %= 10;
if(a[i] < 0) tmp++, a[i] += 10;
a[i + 1] -= tmp;
}
while(len >= 1 && !a[len]) len--;
}
const bigInt operator / (const int n) const{//高精除低精
bigInt tmp;
tmp.len = len;
int mod = 0;
for(int i = len; i >= 1; i--){
mod = mod * 10 + a[i];
tmp.a[i] = mod / n;
mod %= n;
}
while(tmp.len >= 1 && !tmp.a[tmp.len]) tmp.len--;
return tmp;
}
const int operator % (const int n) const{//高精对低精取模
int mod = 0;
for(int i = len; i >= 1; i--) mod = (mod * 10 + a[i]) % n;
return mod;
}
}m;
int a[1000005], b[1000005], vis[1000005];
const int mod = 1e9 + 7;
int n;
int ans;
int tmp = 1, ct, len;
inline int next(int idx){return (idx + b[idx] - 1) % n + 1;}//获取下一步
void init_circle(){//找环
memset(vis, -1, sizeof(vis));
while(vis[tmp] == -1){
vis[tmp] = ct;
tmp = next(tmp);
ct++;
}
len = ct - vis[tmp];//计算环长
}
void get_chain(){//预处理链部分
m -= vis[tmp];
for(int i = 1; i != tmp;){
i = next(i);
ans = (ans + a[i]) % mod;
}
}
void calc_circle(){//计算遍历整环的次数以及获得的分数
int count = m / len % mod;
int score = 0;
for(int i = next(tmp); i != tmp;){//计算遍历一次环获得的分数
score = (score + a[i]) % mod;
i = next(i);
}
score = (score + a[tmp]) % mod;
ans = (ans + count * score) % mod;
}
void end_circle(){//计算最后不到一个环获得的分数
int last = m % len;//剩下的次数
int i = tmp;
while(last--){
i = next(i);
ans = (ans + a[i]) % mod;
}
}
signed main(){
cin.tie(nullptr) -> sync_with_stdio(0);
cout.tie(nullptr) -> sync_with_stdio(0);
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) cin >> b[i];
init_circle();
if(m >= vis[tmp]) get_chain();
calc_circle();
end_circle();
cout << ans % mod;
return 0;
}
时间复杂度：。
T7
个人难度：绿 中/绿 上
默写一遍zkw线段树模板：
int sum[2197157], lazytag[2197157];
int size, depth;
void build(){//给出最后一层，O(n)建树
for(int i = size - 1; i; i--){
sum[i] = sum[i * 2] + sum[i * 2 + 1];
}
}
void modify(int l, int r, int val){//O(logn)区间加
int len = 1;
for(l += size - 1, r += size + 1; l ^ 1 ^ r;){
if(~l & 1) sum[l ^ 1] += len * val, lazytag[l ^ 1] += val;
if(r & 1) sum[r ^ 1] += len * val, lazytag[r ^ 1] += val;
l >>= 1, r >>= 1, len <<= 1;
sum[l] = sum[l * 2] + sum[l * 2 + 1] + lazytag[l] * len;
sum[r] = sum[r * 2] + sum[r * 2 + 1] + lazytag[r] * len;
}
for(l >>= 1, len <<= 1; l; l >>= 1, len <<= 1){
sum[l] = sum[l * 2] + sum[l * 2 + 1] + lazytag[l] * len;
}
}
int query(int l, int r){//O(logn)区间求值
int ct1 = 0, ct2 = 0, ans = 0, len = 1;
for(l += size - 1, r += size + 1; l ^ 1 ^ r;){
if(~l & 1) ans += sum[l ^ 1], ct1 += len;
if(r & 1) ans += sum[r ^ 1], ct2 += len;
l >>= 1, r >>= 1, len <<= 1;
ans += lazytag[l] * ct1 + lazytag[r] * ct2;
}
for(l >>= 1, ct1 += ct2; l; l >>= 1){
ans += lazytag[l] * ct1;
}
return ans;
}
//size = 1 << (depth = ceil(log2(n)) + 1e-5);
其中这个修改中的len是干什么用的？
没错，计算长度！
我们可以另外开一个线段树，表示每个权值，然后把len改成权值就好了。
我们还可以使用差分数组 区间查找权值之和，减小查询时间。
注意开快读快写
#include <iostream>
#include <cstdio>
#include <cmath>
#define int long long
using namespace std;
int sum[2197157], lazytag[2197157], weights[2197157];
int w[1000005];
int size, depth;
void build(int *sum){//给出最后一层，O(n)建树
for(int i = size - 1; i; i--){
sum[i] = sum[i * 2] + sum[i * 2 + 1];
}
}
void modify(int l, int r, int val){//O(logn)区间加
for(l += size - 1, r += size + 1; l ^ 1 ^ r;){
if(~l & 1) sum[l ^ 1] += weights[l ^ 1] * val, lazytag[l ^ 1] += val;
if(r & 1) sum[r ^ 1] += weights[r ^ 1] * val, lazytag[r ^ 1] += val;
l >>= 1, r >>= 1;
sum[l] = sum[l * 2] + sum[l * 2 + 1] + lazytag[l] * weights[l];
sum[r] = sum[r * 2] + sum[r * 2 + 1] + lazytag[r] * weights[r];
}
for(l >>= 1; l; l >>= 1){
sum[l] = sum[l * 2] + sum[l * 2 + 1] + lazytag[l] * weights[l];
}
}
int query(int l, int r){//O(logn)区间求值
int ct1 = 0, ct2 = 0, ans = 0;
for(l += size - 1, r += size + 1; l ^ 1 ^ r;){
if(~l & 1) ans += sum[l ^ 1], ct1 += weights[l ^ 1];
if(r & 1) ans += sum[r ^ 1], ct2 += weights[r ^ 1];
l >>= 1, r >>= 1;
ans += lazytag[l] * ct1 + lazytag[r] * ct2;
}
for(l >>= 1, ct1 += ct2; l; l >>= 1){
ans += lazytag[l] * ct1;
}
return ans;
}
char *p1, *p2, buf[(1 << 25)];
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, (1 << 24) + (1 << 23), stdin), p1 == p2)? EOF : *p1++)
int read(){
char c = getchar();
int x = 0, f = 1;
while(!isdigit(c)){
if(c == '-') f = -f;
c = getchar();
}
while(isdigit(c)){
x = (x << 3) + (x << 1) + c - '0';
c = getchar();
}
return x * f;
}
void _write(int n){//快写
if(n == 0) return;
_write(n / 10);
putchar(n % 10 + '0');
}
void write(int n, bool end = 0){//快写，增加了输出0和负数并附带换行
if(n < 0) putchar('-'), _write(-n);
else if(n == 0) putchar('0');
else _write(n);
putchar('\n');//判断是否要空格
}
signed main(){
int n = read(), m = read();
size = 1 << (depth = ceil(log2(n)) + 1e-5);
for(int i = 0; i < n; i++){
sum[i + size] = read();
}
for(int i = 0; i < n; i++){
weights[i + size] = read();
if(i) w[i] = w[i - 1] + weights[i + size];
else w[i] = weights[i + size];
sum[i + size] *= weights[i + size];
}
build(sum), build(weights);
while(m--){
int tmp = read();
if(tmp == 1){
int l = read(), r = read(), val = read();
modify(l - 1, r - 1, val);
}else{
int l = read(), r = read();
write(query(l - 1, r - 1) / (w[r - 1] - w[l - 2]));
}
}
return 0;
}
T8
个人难度：绿 中
根据题意，我们得知：在激活传送点的同时传送至下一个地方是最优的。
因为，如果在路途中传送，对传送点的激活没有贡献，还多花费了时间。
现在，怎么做呢？
例如这张地图：
##.*......
...*......
...*......
...*.#....
...*......
..........
..........
...#...#..
..........
........#.
聪明的你一定可以想到：我们可以构建一个图，如下：
手动构造最优解：
。
按上面的最优解连边：
可以看出这是这个图的一棵生成树，并且如果这个图中每条边的权值是这两个点对应的传送门之间的距离，那么最优解就是这个图的最小生成树。
接下来就 bfs 出最短路径，接着求最小生成树即可。
#include <iostream>
#include <cstdio>
#include <string>
#include <memory.h>
#include <queue>
using namespace std;
struct node{
int len;
string s;
}edge[55][55];
struct port{
int x, y;
port(){}
port(int _x, int _y){
x = _x, y = _y;
}
}portal[55];
char c[55][55];
bool vis[55][55];
bool vis2[55];
int dis[55];
int from[55];
int dir[4][2]{-1, 0, 0, -1, 0, 1, 1, 0};
string dir2[4]{"W\n", "A\n", "D\n", "S\n"};
int ct;
int n, m;
void bfs(int idx){//bfs建边
memset(vis, 0, sizeof(vis));
vis[portal[idx].x][portal[idx].y] = 1;
queue <pair <pair <int, int>, pair <int, string>>> q;
q.push({{portal[idx].x, portal[idx].y}, {0, ""}});
while(!q.empty()){
auto head = q.front();
q.pop();
if(c[head.first.first][head.first.second] == '#'){
for(int i = 1; i <= ct; i++){
if(portal[i].x == head.first.first && portal[i].y == head.first.second){
edge[idx][i].len = head.second.first;
edge[idx][i].s += head.second.second;
break;
}
}
}
for(int i = 0; i < 4; i++){
int xx = head.first.first + dir[i][0];
int yy = head.first.second + dir[i][1];
if(xx >= 1 && xx <= n && yy >= 1 && yy <= m && !vis[xx][yy] && c[xx][yy] != '*'){
vis[xx][yy] = 1;
q.push({{xx, yy}, {head.second.first + 1, head.second.second + dir2[i]}});
}
}
}
}
void prim(){//prim算法求解最小生成树
string curs = "";
int cur = 0;
memset(dis, 63, sizeof(dis));
dis[1] = 0;
for(int i = 1; i <= ct; i++){
int mx = 0x3f3f3f3f, idx;
for(int j = 1; j <= ct; j++){
if(!vis2[j] && dis[j] < mx){
mx = dis[j], idx = j;
}
}
cur += mx;
curs += edge[from[idx]][idx].s;
vis2[idx] = 1;
for(int j = 1; j <= ct; j++){
if(!vis2[j] && edge[idx][j].len < dis[j]){
from[j] = idx;
dis[j] = edge[idx][j].len;
}
}
}
cout << cur << ' ' << cur + ct - 1 << '\n' << curs;
}
int main(){
cin.tie(nullptr) -> sync_with_stdio(0);
cout.tie(nullptr) -> sync_with_stdio(0);
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> c[i] + 1;
for(int j = 1; j <= m; j++){
if(c[i][j] == '#'){
portal[++ct] = port(i, j);
for(int k = 1; k <= 50; k++){
edge[ct][k].s = "GOTO " + to_string(i) + ' ' + to_string(j) + '\n';
}
}
}
}
for(int i = 1; i <= ct; i++) bfs(i);
prim();
return 0;
}
时间复杂度：。
有帮助，赞一个