ACM 2016级新生赛题解

377

本次比赛共 9
主要目的是为了明确大家的实力,可以找到大家的短板,同时熟悉各种题型
主要对象是自学过CC++的同学,开学后会有正式的比赛选拔

题解比较详细,前几题应该零基础的同学也能看懂

序号题目名称OJ编号考察点
AA+B ProblemPOJ 1000基本的输入输出
B素数判定HDU 2012素数判定、循环、函数
CAs Easy As A+BHDU 1040给定组数的输入、排序算法
DLaunch of ColliderCodeforces 699A思维
EKing MovesCodeforces 710A判断、循环
F最小公倍数HDU 1108EOF结束的输入、欧几里得算法
GCatch That CowHDU 2717BFS
H命运HDU 2571动态规划
I狼抓兔子BZOJ 1001网络流



如何读题



Description
Calculate a+b
Input
Two integer a,b (0<=a,b<=10)
Output
Output a+b
Sample Input
1 2
Sample Output
3


这是一个标准的 ACM题目,题目首先有一些信息:
Time Limit: 1000MS
Memory Limit: 10000KB
64bit IO Format: %lld & %llu


这些信息告诉了,运算这道题我们所拥有的运算资源: 共有 1s 的时间,并且内存被限制在 10M 以内

  • 时间限制,要求我们不要进行无用的运算,并且尽可能选取时间复杂度较低的算法
  • 内存限制,要求我们不要随便大范围申请内存,尽可能重复使用变量,并且舍弃不需要保存的信息

接下来是题面
(容易出现问题的地方使用 粗体 显示)

  • 题目背景(Description)
    这里会有题目的一些介绍,可能有废话,也有可能有运算方法
  • 输入说明(Input)
    这里会讲解输入的格式
    • 是否是多组数据
    • 数据的类型是整数还是浮点数(小数)
    • 整数可能达到的最值
      • 如果最大是100000,一些时间复杂度比较高的算法可能就不能用了
      • 如果最大值超过 231, int 就不能正常存储数据了
  • 输出说明(Output)
    这里会说明输出的格式
    • 如果有多组数据,两组数据间是不是输出空行
    • 输出前是否要加类似 "#Case 1:" 的前缀
    • 输出字符串是 yes 还是 Yes 还是 YES
  • 样例输入(Sample Input)
    这里会给出几组符合题意的输入样例
    • 输入重定向到文件输入,也即最后会有一个隐藏的 EOF (文件尾),在多组数据输入时,可以用来判断是否读入结束
  • 样例输出(Sample Output)
    这里给出上面样例输入对应的结果,你的程序运算的结果必须与此处完全相同
    • 输出不能有任何多余字符、空行、空格
    • 即使输出与样例一样,也不证明你的程序能够 Accepted !!!
  • 提示(Hint)
    如果题目比较难以理解,这里可能会有一些提示与样例数据的解释

如何理解OJ的返回信息


对于所有OJ可能返回的信息有以下几种(经常出现的已 加粗)

  • Accepted
    • 含义: 通过
    • 解释: 这个代表你的程序通过了所有测试数据
      这是苦逼一天、一周甚至更久后,最让人激动的字符
      (即使通过了所有数据,仍然有可能不是最完美)
  • Pretest Passed
    • 含义: 暂时通过
    • 解释: 这个只出现在 Codeforces 上,证明你的程序通过了当前所有的数据,但是可能会死在终测时的极端数据上
  • Wrong Answer
    • 含义: 答案错误
    • 解释: 你的程序输出和测试数据的输出不同
    • 解决办法: 重新读题,重新考虑输出的格式、算法、是否有没有考虑到的情况
  • Presentation Error
    • 含义: 输出格式错误
    • 解释: 你的程序输出格式与测试数据不一样
    • 解决办法: 仔细检查空格、换行,重新读题,离成功只差一步
  • Compilation Error
    • 含义: 编译错误
    • 解释: 语法问题,自己反思吧
    • 解决办法: 对照返回的信息改下
  • Runtime Error
    • 含义: 程序运行时出错
    • 解释: 可能是由于数组溢出,栈溢出,除以0等情况造成
    • 解决办法:
      • 检查数组是否开的过小
      • 检查是否有意料外的数组访问
      • 检查在最坏情况下的递归层次
      • 检查除法的除数有没有可能是0
  • Time Limit Exceeded
    • 含义: 超过时间限制
    • 解释: 程序没有在规定的时间内运行完毕(不代表输出结果是对的)
    • 解决办法:
      • 查找是否存在死循环
      • 换用更好的算法
      • 删去一些不必要的操作
      • 检查数组是否开的太小(个别OJ不报 RE 报 TLE )
  • Memory Limit Exceeded
    • 含义: 超过内存限制
    • 解释: 程序申请的内存过多
    • 解决办法:
      • 压缩使用的数组,尽量重复数组
      • 不要保存没必要存下来的数据

A+B Problem




Description
计算 a+b 的值
Input
两个整数 a 和 b a,b∈[1,10]
Output
输出 a+b 的值
Sample Input
1 2
Sample Output
3


这是ACM的经典入门题目,计算两个数的和
这道题一般学过编程的都能过

直接读入两个数字,然后输出和即可
不牵扯大数,多组数据等任何问题

#include <stdio.h>
int main(){
    int a,b;
    scanf("%d%d",&a,&b);
    printf("%d\n",a+b);
    return 0;
}


#include <cstdio>
#include <iostream>
using namespace std;
int main(){
    int a,b;
    cin >> a >> b;
    cout << a + b;
    return 0;
}


素数判定


题目中文,略

首先先看输入输出,样例中有两行
0 1
0 0


这两行代表的意思分别是
  • 数据输入 0 1,计算 n ∈ [0,1] 是否表达式的所有值都为素数
  • 数据输入 0 0,表示输入结束,不处理该组数据,结束程序

输入有一行
OK


输出说明中有每组输出占一行,这句的意思是,每组数据都要占据单独的一行,也即每次输出完,要换行
对于样例的输出,应该是 printf("OKn"); 而不是 printf("OK"); 虽然看上去,两组结果一样,但是对于电脑来说,文件的行数是不一样的

其他需要注意的就是 OKSorry 的拼法,注意大小写,注意没有 .

明白输入输出后,就可以开始做题了

题目要求的是 n^2+n+41[-39,50] 的某个子集中是否结果全部是素数
画图像可以得知,在这个区域里,表达式的值域为 [41,2591]
也即我们需要判断 [41,2591] 里的一些数是否为整数

首先写一个函数 int isPrime(int n) 判断一个数是否位素数,如果是返回 1 ,如果不是返回 0
(如果是 C++ ,可以使用 bool )

然后我们来看程序主体,由于题目是多组输入,因此我们需要不断读入数据,可以使用 while
每次我们读入 xy , 然后判断他们是否 都为0,如果是,跳出
则可以使用逗号表达式,从左向右运算,返回最后一个表达式的结果
while(scanf("%d%d",&x,&y),!(x==0&&y==0))

这样只要输入的是需要运算的数据,程序就会进行 while 的操作

对于这道题,需要的操作就是一个一个算 n^2+n+41 的值是不是素数
如果发现有一个不是素数,就已经确定答案了,因此可以直接跳出循环(节省时间)

int AllPrime = 1;
for(int i=x;i<=y;i++)
    if(isPrime(i*i+i+41)==0){
        AllPrime = 0;
        break;
    }


函数主体部分已经完成,然后是 isPrime() 函数的写法
在这里有两种方法

以下是能够AC的代码
#include <stdio.h>
#include <math.h>
int isPrime(int n){
    int Prime = 1;
    for(int i=2;i<=sqrt(n);i++){
        if(n%i==0){//能整除,存在因子
            Prime = 0;
            break;
        }
    }
    return Prime;
}
int main(){
    int x,y;
    while(scanf("%d%d",&x,&y),!(x==0&&y==0)){
        int AllPrime = 1;
        for(int i=x;i<=y;i++)
            if(isPrime(i*i+i+41)==0){
                AllPrime = 0;
                break;
            }
        if(AllPrime==1)
            printf("OK\n");
        else
            printf("Sorry\n");
    }
    return 0;
}


As Easy As A+B


给出题目翻译


Description
这几天,我一直在想一个问题,如何出一道像 A+B 一样简单的题目
很显然,这是非常难的,不过熬了几夜后,我最终解决了
给你一些整数,你的任务是对这些数按照升序排序
很简单吧,加油!
Input
输入包括多组数据
第一行有一个整数 T 代表数据组数
接下来有 T 组数据
每组数据开始是一个整数 N (1<=N<=1000 需要排序的数的数目)
紧接着是 N 个整数
可以确定所有数都在 32位系统下 int 能够存储的范围内
Output
对于每组数据,在一行内输出排序后的结果
Sample Input
2
3 2 1 3
9 1 4 7 2 5 8 3 6 9
Sample Output
1 2 3
1 2 3 4 5 6 7 8 9


排序问题,你要做的是对 N 个数排序
排序使用任意一种排序算法都行
**排序算法 http://www.oyohyee.com/post/Algorithm/Sort.html**
这里的除了睡眠排序外的任何一种都能满足你的要求

当然,STL自带的 sort 是最好的选择

如果想要自己写排序函数,上面的链接中有详细的代码

这道题的输入是ACM中的一种新的读入方式,先给出题目组数
很直观,读入后直接循环T遍即可

int T;
scanf("%d",&T);
while(T--){
    ……
}


当然是可以用C语言写的,不过为了更方便调用sort使用了C++
因为两种语言混合是一种很不好的习惯

另外,在比赛中开数组的时候,通常会开稍微大一点,一般为需要的数组 +5 +10
由于数组的长度必须是常数,因此应该用常数变量来输入

#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 1000 + 5;

int a[maxn];

int main() {
    int T;
    scanf("%d",&T);
    while(T--) {
        int n;
        scanf("%d",&n);
        for(int i = 0;i<n;i++)
            scanf("%d",&a[i]);
        sort(a,a + n);
        for(int i = 0;i<n;i++) {
            if(i)
                printf(" ");
            printf("%d",a[i]);
        }
        printf("\n");
    }
    return 0;
}


Launch of Collider



Description
新的粒子碰撞机快要建成了,有 n 个粒子在碰撞机的直线轨道上
每两个粒子的位置都不重合,坐标表示的是粒子到碰撞机的中心的距离,并且全部都是偶数
你已经知道了每个粒子的运动方向——开启机器后会向左或向右以 `1m/ms` 的速度运动
碰撞机足够大,保证粒子不会跑出机器
写一个程序判断粒子第一次碰撞的时间
Input
第一行包括一个数 n (1 ≤ n ≤ 200 000) —— 粒子的数目
第二行有 n 个字符(L 或 R)表示粒子的方向向左或向右 第三行有 n 个递增的整数(0 ≤ xi ≤ 109),表示粒子的初始位置
Output
在一行中输出粒子第一次碰撞的时间,如果不会碰撞,输出 -1


由于每个粒子的速度都一样,因此想要碰撞必须有两个粒子向对而行

要算出来所有最近的向右粒子和它右边第一个向左的粒子的最短距离

因此每次找到 R 记录下它的位置,找到 L 算与上一个 R 的距离
将距离最小的记录下来,答案就是这个距离除以 2 (相对运动,相对速度为 2)

下面代码

#include <cstdio>

const int maxn = 200005;

int x[maxn];
char d[maxn];

int min(int a,int b) {
    return a < b ? a : b;
}

int main() {
    int n;
    scanf("%d",&n);
    scanf("%s",d);
    int last = -1;
    int dis = -1;
    for(int i = 0;i < n;i++) {
        scanf("%d",&x[i]);
        if(d[i] == 'L')
            if(last != -1)
                if(dis == -1)
                    dis = x[i] - x[last];
                else
                    dis = min(dis,x[i] - x[last]);
        if(d[i] == 'R')
            last = i;
    }
    if(dis == -1)
        printf("-1\n");
    else
    printf("%d\n",dis / 2);
    return 0;
}


King Moves



题目不多翻译,就是求国际象棋里王在当前位置能走的方案数
(王能向周围八方向移动)

也即判断八方向在棋盘内的方格数

#include <cstdio>
const int delta[8][2] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
int main() {
    char s[2+5];
    scanf("%s",s);
    int num = 0;
    for(int i = 0;i < 8;i++) {
        char xx = s[0] + delta[i][0];
        char yy = s[1] + delta[i][1];
        if(xx >= 'a'&&xx <= 'h'&&yy >= '1'&&yy <= '8')
            num++;
    }
    printf("%d\n",num);
    return 0;
}


最小公倍数


求两个数的最小公倍数

也即求两个数的乘积除以最大公约数

求最大公约数使用 欧几里得算法

具体算法说明参照
**欧几里得算法 http://www.oyohyee.com/post/Algorithm/Euclid.html**

本题的输入为 EOF 结束
这是一种非常常见的输入方式,可以循环读入数据,如果读入失败则证明文件结束
scanf() 的返回值表示读入成功的数据个数
读入失败, scanf() 会返回 EOF (-1)
因此只需要 while(~scanf()) 即可

代码
#include <cstdio>
int gcd(int a,int b) {
    return b == 0 ? a : gcd(b,a%b);
}
int main() {
    int a,b;
    while(~scanf("%d%d",&a,&b)) {
        printf("%d\n",a / gcd(a,b) * b);
    }
    return 0;
}


Catch That Cow



Description
FJ 家的牛跑了,需要立即抓回来,他开始站在点 N (0 ≤ N ≤ 100,000) ,而牛停留在点 K (0 ≤ K ≤ 100,000)
FJ 有两种移动方式 - 移动到当前位置(X)的上一位置(X-1)和下一位置(X+1) - 移动道当前位置(X)乘2(2X) 如果牛不动,FJ需要移动多少次才能抓住牛呢?
Input
两个整数 N K
Output
输出最少移动的距离


BFS求最短路问题,两种拓展结点的方式,第一次到达K时移动的距离就是最短距离

由于移动方式只有 +1 -1 *2 因此如果 起点大于终点,直接相减即可

直接贴之前自己写的代码了,哪看不懂可以直接问

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
using namespace std;
//DEBUG MODE
#define debug 0
//循环
#define REP(n) for(int o=0;o<n;o++)
const int maxn = 100005;
int BFS(int s,int v) {
    if(s == v)
        return 0;
    if(s > v)
        return s - v;
    queue<int> Q;
    bool visited[maxn];
    memset(visited,false,sizeof(visited));
    int dis[maxn];
    memset(dis,0,sizeof(dis));
    Q.push(s);
    visited[s] = true;
    while(!Q.empty()) {
        int th = Q.front();
        Q.pop();
        //达到终点
        if(th == v)
            break;
        //拓展节点
       define push \
        if(next > maxn || next <= 0) \
            continue;\
        if(!visited[next]) {\
            Q.push(next);\
            visited[next] = true;\
            dis[next] = dis[th] + 1;\
        }\
        int next;
        next = th + 1;
        push;
        next = th - 1;
        push;
        next = th * 2;
        push;
    }
    if(dis[v])
        return dis[v];
    else
        return -1;
}
bool Do() {
    int s,v;
    if(scanf("%d%d",&s,&v)==EOF)
        return false;
    printf("%d\n",BFS(s,v));
    return true;
}
int main() {
    while(Do());
    return 0;
}


命运



动态规划问题
对于 (x,y) 可以由以下点到达
  • (x-1,y)
  • (x,y-1)
  • (x,k) 其中 ky 的因数

那么,有
dp[i][j] = max{ dp[i-1][j] , dp[i][j-1] , dp[i][k] } + Map[i][j]
( ky 的因数, Map[i][j](i,j) 的权值)

对于 i == 1 的情况需要特别处理
3 5
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1


应该输出 -4 而不是 -3

for(int i = 1;i <= n;i++)
    for(int j = 1;j <= m;j++) {
        if(i == 1)
            if(j == 1)
                dp[i][j] = Map[i][j];
            else
                dp[i][j] = dp[1][1] + Map[i][j];
        else
            dp[i][j] = dp[i - 1][j] + Map[i][j];
        for(int k = 1;k < j;k++)
            if(j % k == 0 || k == j - 1)
                dp[i][j] = max(dp[i][j],dp[i][k] + Map[i][j]);
    }


之前写过直接贴代码,哪看不懂可以直接问

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
using namespace std;
const int maxn = 25;
const int maxm = 1005;
int Map[maxn][maxm];
int dp[maxn][maxm];
void  Do() {
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++)
            scanf("%d",&Map[i][j]);
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++) {
            if(i == 1)
                if(j == 1)
                    dp[i][j] = Map[i][j];
                else
                    dp[i][j] = dp[1][1] + Map[i][j];
            else
                dp[i][j] = dp[i - 1][j] + Map[i][j];
            for(int k = 1;k < j;k++)
                if(j % k == 0 || k == j - 1)
                    dp[i][j] = max(dp[i][j],dp[i][k] + Map[i][j]);
        }
    printf("%d\n",dp[n][m]);
}
int main() {
    int T;
    scanf("%d",&T);
    while(T--)
        Do();
    return 0;
}


狼抓兔子 


题目中文的没有什么好说。
这道题目是关于最小割的一道题目。

最小割的经典算法是根据最大流最小割定理,将最小割化成最大流然后用 dinic 算法求解
不过这题比较特殊,即使转换成最大流求最小割依旧不可能通过。
因为时间和空间的双重限制,所以这道题的解法需要利用这个图的特殊性质。
给出的图是一个平面图无疑,那么利用平面图的特殊性质解决这个问题会简单很多。 将
平面图转换成其对偶图,然后计算新的源点到新的汇点的最短路径即可得出结果。

以下是代码:
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef struct node {
    int v,cap,nxt;

    node(int a = 0,int b = 0,int c = 0) {
        v = a;
        cap = b;
        nxt = c;
    }
}Edge;

const int maxn = 2100005;
const int maxm = 6100005;
const int inf = 0x3f3f3f3f;

Edge edge[maxm];

int tot,head[maxn];
int vis[maxn],dis[maxn];

void add(int u,int v,int cap) {
    edge[tot] = Edge(v,cap,head[u]);
    head[u] = tot++;
    edge[tot] = Edge(u,cap,head[v]);
    head[v] = tot++;
}

int spfa(int s,int t) {
    int x;
    Edge e;
    queue<int> q;
    while(!q.empty()) q.pop();
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    dis[s] = 0;
    vis[s] = 1;
    q.push(s);
    while(!q.empty()) {
        x = q.front();
        q.pop();
        vis[x] = 0;
        for(int i = head[x];~i;i = edge[i].nxt) {
            e = edge[i];
            if(dis[x] + e.cap < dis[e.v]) {
                dis[e.v] = dis[x] + e.cap;
                if(!vis[e.v]) {
                    vis[e.v] = 1;
                    q.push(e.v);
                }
            }
        }
    } return dis[t];
}
int main() {
    int n,m,u,v,cap;
    while(~scanf("%d%d",&n,&m)) {
        if(n == 1 || m == 1) {
            if(n > m) swap(n,m);
            int ans = inf;
            for(int i = 1,a;i < m;++i) {
                scanf("%d",&a);
                ans = min(ans,a);
            } 
            printf("%d\n",ans == inf ? 0 : ans);
            continue;
        } 
        int s = 0,t = (m - 1) * 2 * (n - 1) + 1;
        tot = 0;
        memset(head,-1,sizeof(head));
        for(int i = 1;i <= n;++i) {
            for(int j = 1;j <= m - 1;++j) {
                scanf("%d",&cap);
                if(i == 1) {
                    u = s;
                    v = 2 * j;
                } else if(i == n) {
                    u = (m - 1) * (n - 2) * 2 + 2 * j - 1;
                    v = t;
                } else {
                    v = (m - 1) * 2 * (i - 2) + 2 * j - 1;
                    u = (m - 1) * 2 * (i - 1) + 2 * j;
                } 
                add(u,v,cap);
            }
        }
        for(int i = 1;i < n;++i) {
            for(int j = 1;j <= m;++j) {
                scanf("%d",&cap);
                if(j == 1) {
                    v = t;
                    u = (m - 1)*(i - 1) * 2 + 1;
                } else if(j == m) {
                    u = s;
                    v = (m - 1) * i * 2;
                } else {
                    u = (m - 1) * (i - 1) * 2 + 2 * (j - 1);
                    v = u + 1;
                }
                add(u,v,cap);
            }
        } 
        for(int i = 1;i < n;++i) {
            for(int j = 1;j < m;++j) {
                scanf("%d",&cap);
                u = (m - 1) * 2 * (i - 1) + 2 * j - 1;
                v = u + 1;
                add(u,v,cap);
            }
        } 
        printf("%d\n",spfa(s,t));
    } 
    return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论