第一届ACC(AcWing Cup)全国高校联赛（决赛）
两个闹钟合并石子翻转树边
第一届ACC(AcWing Cup)全国高校联赛（决赛）昨天因为刚打完比赛，然后再看了y总直播就很晚了，中间的题解都写得比较敷衍，现在重新写一份详解的。
两个闹钟有两个闹钟。 第一个闹钟会在 b,b+a,b+2a,b+3a,… 时刻响铃。 第二个闹钟会在 d,d+c,d+2c,d+3c,… 时刻响铃。 请计算两个闹钟第一次同时响铃的具体时刻。 输入格式 第一行包含两个整数 a,b。 第二行包含两个整数 c,d。 输出格式 一个整数，表示第一次同时响铃的具体时刻。 如果永远都不可能同时响铃，则输出 −1。 数据范围 所有测试点满足 1≤a,b,c,d≤100。 输入样例1： 20 2 9 19 输出样例1： 82 输入样例2： 2 1 16 12 输出样例2： -1
解题思路
这道题刚做的时候想的是开两个数组，然后分别存b+a*i，d+c*i；
s1[i] = b + a * i; s2[j] = d + c * j;
然后再遍历两个数组，如果两个数组中能找到相同的两个数就return true；
for(int i = 0 ; i < N ; i ++)
{
for(int j = 0 ; j < N ; j ++)
{
if(s1[i] == s2[j])
{
t = i;
return true;
}
}
}
最后请看总的代码：
#includeusing namespace std; const int N = 1000; int a,b,c,d,t; int s1[N],s2[N]; bool YES(int s1[N],int s2[N]) { for(int i = 0 ; i < N ; i ++) { for(int j = 0 ; j < N ; j ++) { if(s1[i] == s2[j]) { t = i; return true; } } } return false; } int main() { cin >> a >> b; cin >> c >> d; for(int i = 0; i < N ; i++) { s1[i] = b + a * i; s2[i] = d + c * i; } if(YES(s1 ,s2)) { cout << s1[t]; }else { cout << -1; } return 0; }
后来又想了一下，不需要用数组来存也可以呀，就两个for循环去找有没有两个相同的数，有就break。
for(int i = 0; i < 1000 && res == -1; i++) {
for(int j = 0; j < 1000; j++) {
if(b - d == i * c - j * a) {
res = d + c * i;//或者res = b + a * j
break;
}
}
}
下面请看总的代码：
#includeusing namespace std; int a, b, c, d; int main() { cin >> a >> b >> c >> d; int res = -1; for(int i = 0; i < 1000 && res == -1; i++) { for(int j = 0; j < 1000; j++) { if(b - d == i * c - j * a) { res = d + c * i; break; } } } cout << res << endl; return 0; }
最后看了y总直播，发现了更快的做法，只需要一个for循环就可以了。
for (int i = max(b, d); i <= 10100; i ++ )//先比较b和d，从较大的数开始枚举，枚举到10000个数就差不多了。
if ((i - b) % a == 0 && (i - d) % c == 0)//然后再用i分别减去b、d再分别取余，如果余数为0就表示能被整除。
//i = b + a * x,i = d + c * x ;这里x根本不需要算出来。
{
cout << i << endl;
return 0;
}
最后还有一种写法是用欧几里得算法 求最大公约数
先简单说一下什么是欧几里得算法：
欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。 计算公式gcd(a,b) = gcd(b,a mod b)。
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
最后请看总的代码：
#includeusing namespace std; int gcd(int n,int m){ //最大公约数 return m?gcd(m,n%m):n; } int main(){ int a,b,c,d; int x=0,y=0; //x为a的倍数 y为c的倍数 cin >> a >> b >> c >> d; int n=gcd(a , c); //n为a与c的最小公倍数 int g=max((b - d),(d - b)); //求出b与d的差值 if(g % n == 0){ //如果b与d的差值是n的倍数则说明可以找到 while((a * x + b) != ( c * y + d)){ //利用循环找到那个时刻 if((a * x + b) < ( c * y + d)) x ++; else y ++; } cout << a * x + b; } else //否则返回-1 cout << -1; return 0; }
最后是这四种写法分别需要的时间
欧几里得算法用的时间要少一点，其他的几种都差不多，不过也和测试所给的数据有关。
再分别附上Java代码：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int a=sc.nextInt();
int b=sc.nextInt();
int c=sc.nextInt();
int d=sc.nextInt();
int x=Math.max(b,d);
for(int i = x ; i <= 10100 ; i ++){
if((i - b) % a == 0 && (i - d) % c == 0){
System.out.println(i);
return;
}
}
System.out.println(-1);
}
}
合并石子
小 A 面前有 n 堆石子排成一排，每堆石子的数量从左到右依次为 a1,a2,…,an。 小 B 面前有 m 堆石子排成一排，每堆石子的数量从左到右依次为 b1,b2,…,bm。 两人面前的石子总数相同，即 a1+a2+…+an=b1+b2+…+bm。 每个人都可以对自己面前的石子堆进行任意次合并操作，两个人的操作次数可以不同。 合并操作指将连续的若干堆相邻石子合并为一堆。 请你确定一个最大的整数 k，满足： 小 A 停止所有操作后，面前恰好有 k 堆石子，每堆石子的数量从左到右依次为 a′1,a′2,…,a′k。 小 B 停止所有操作后，面前恰好有 k 堆石子，每堆石子的数量从左到右依次为 b′1,b′2,…,b′k。 对于 1≤i≤k，a′i=b′i 均成立。 输出这个 k 的最大可能值。 输入格式 第一行包含两个整数 n,m。 第二行包含 n 个整数 a1,a2,…,an。 第三行包含 m 个整数 b1,b2,…,bm。 输出格式 一个整数，表示 k 的最大可能值。 数据范围 前三个测试点满足 1≤n,m≤10。 所有测试点满足 1≤n,m≤105，1≤ai,bi≤106，a1+a2+…+an=b1+b2+…+bm≤106。 输入样例1： 7 6 2 5 3 1 11 4 4 7 8 2 4 1 8 输出样例1： 3 输入样例2： 3 3 1 10 100 1 100 10 输出样例2： 2 输入样例3： 1 4 4 1 1 1 1 输出样例3： 1
这道题题目有点长，做这道题的时候我们一定要先把题目读懂。
题目意思：
1、A和B的石子总数一定相等。
2、A和B石子的堆数和每一堆石子的数量可能不相等。
3、合并操作只能将连续的若干堆相邻石子合并为一堆。
4、重新分成k堆后，A和B的堆数和每一堆石子的数量都相等。
好，现在我们再来看一下怎么做吧，可以发现的是将前后相邻的石子合并为一堆，就有点像前缀和，之前更新过前缀和的算法：这里是前缀和算法链接，但是只有前缀和是不够的，因为是A和B两堆石子的比较，所以我们还需要用到我们还需要用到双指针，这里是双指针算法链接，好，有了思路，那么就可以写代码了。
前缀和代码：
for(int i = 1 ; i <= n ; i ++)
{
cin >> a[i]; s1[i] = s1[i-1] + a[i];//s1[i]存的就是A前i项的和
}
for(int j = 1 ; j <= m ; j ++)
{
cin >> b[j]; s2[j] = s2[j-1] + b[j];//s2[j]存的就是B前j项的和
}
双指针：
这是最开始我再比赛的时候写的，当时想的就是要求每一堆都相等，那么我就每一堆最判断。
int res = 0,i = 1 , j = 1, k = 1 , l = 1;
while(i <= n && j <= m)
{
if(s1[i] - s1[j-1] == s2[k] - s2[l-1])
{
res ++;//如果A和B的石子数相等，res++
i ++ , k ++ ;//i和k分别往后走
j = i;//再把i赋给j
l = k;//再把k赋给l
}
else
{
if(s1[i] - s1[j-1] < s2[k] - s2[l-1]) i++;//或者A前面的石子数比B的少，那么i就往后走
else k++;//同理，如果或者A前面的石子数比B的多，那么k就往后走
}
}
这是我看y总直播的时候写的
for (int i = 1, j = 1; i <= n; i ++ )
{
while (s2[j] < s1[i]) j ++ ;
if (s2[j] == s1[i]) res ++ ;
}
我已经用s1和s2分别来保存A和B的前i项的和了，就可以直接比较了呀，前面堆的石子数相同，中间堆的石子数也相同，那么前面的加上中间的石子数也肯定是相同的啊。
最后请看代码：
//我写得的代码 #includeusing namespace std; const int N = 1e6 + 10; int a[N],b[N],s1[N],s2[N]; int n , m; int main() { cin >> n >> m; for(int i = 1 ; i <= n ; i ++) { cin >> a[i]; s1[i] = s1[i-1] + a[i]; } for(int j = 1 ; j <= m ; j ++) { cin >> b[j]; s2[j] = s2[j-1] + b[j]; } int res = 0,i = 1 , j = 1, k = 1 , l = 1; while(i <= n && j <= m) { if(s1[i] - s1[j-1] == s2[k] - s2[l-1]) { res ++; i ++ , k ++ ; j = i; l = k; } else { if(s1[i] - s1[j-1] < s2[k] - s2[l-1]) i++; else k++; } } cout << res ; return 0; }
//y总写的代码 #include#include #include using namespace std; const int N = 100010; int n, m; int s1[N], s2[N]; int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i ++ ) { int x; scanf("%d", &x); s1[i] = s1[i - 1] + x; } for (int i = 1; i <= m; i ++ ) { int x; scanf("%d", &x); s2[i] = s2[i - 1] + x; } int res = 0; for (int i = 1, j = 1; i <= n; i ++ ) { while (s2[j] < s1[i]) j ++ ; if (s2[j] == s1[i]) res ++ ; } printf("%dn", res); return 0; }
5秒前的是我的方法所用的时间，29秒前的是y总方法所用的时间，不得不说，y总的代码是真的美啊。
最后再附上Java代码：
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[]s1 = new int[n + 1];
int[]s2 = new int[m + 1];
for(int i = 1; i <= n; i++) {
int x;
x = sc.nextInt();
s1[i] = s1[i - 1] + x;
}
for(int i = 1; i <= m; i++) {
int x;
x = sc.nextInt();
s2[i] = s2[i - 1] + x;
}
int cnt = 0;
for (int i = 1, j = 1; i <= n; i ++ )
{
while (s2[j] < s1[i]) j ++ ;
if (s2[j] == s1[i]) cnt ++ ;
}
System.out.println(cnt);
}
}
Java太慢了，可以来看一下Java运行的时间
给定一个 n 个节点的树。 节点编号为 1∼n。 树中的 n−1 条边均为单向边。 现在，我们需要选取一个节点作为中心点，并希望从中心点出发可以到达其他所有节点。 但是，由于树中的边均为单向边，所以在选定中心点后，可能无法从中心点出发到达其他所有节点。 为此，我们需要翻转一些边的方向，从而使得所选中心点可以到达其他所有节点。 我们希望选定中心点后，所需翻转方向的边的数量尽可能少。 请你确定哪些点可以选定为中心点，并输出所需的最少翻转边数量。 输入格式 第一行包含整数 n。 接下来 n−1 行，每行包含两个整数 a,b，表示存在一条从 a 到 b 的单向边。 输出格式 第一行输出一个整数，表示所需的最少翻转边数量。 第二行以升序顺序输出所有可选中心点（即所需翻转边数量最少的中心点）的编号。 数据范围 前三个测试点满足 2≤n≤5。 所有测试点满足 2≤n≤2×105，1≤a,b≤n，a≠b。 输入样例1： 3 2 1 2 3 输出样例1： 0 2 输入样例2： 4 1 4 2 4 3 4 输出样例2： 2 1 2 3
当时比赛的时候是怎么都没读懂题，现在明白了。
先来看图解
这题是一道树形DP/换根DP的题。
思路
考虑树形dp, 状态表示dp[u]以u为中心点的最小翻转次数
如果当前点为中心点 , 考虑两个方面 向上走 和 向下走
再来看代码：
#include#include #include using namespace std; const int N = 200010, M = N * 2; int n; int h[N], e[M], w[M], ne[M], idx; int down[N], up[N]; void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ; } void dfs_down(int u, int from)// from是来的边 { for (int i = h[u]; ~i; i = ne[i]) { if (i == (from ^ 1)) continue;// 搜到反向边 // from ^ 1 偶数和下一位奇数, 奇数和上一位偶数 01,23,45 int j = e[i]; dfs_down(j, i); down[u] += down[j] + w[i]; } } void dfs_up(int u, int from) { if (from != -1) { int fa = e[from ^ 1]; up[u] = up[fa] + down[fa] - down[u] - w[from] + w[from ^ 1]; } for (int i = h[u]; ~i; i = ne[i]) { if (i == (from ^ 1)) continue; int j = e[i]; dfs_up(j, i); } } int main() { scanf("%d", &n); memset(h, -1, sizeof h); for (int i = 0; i < n - 1; i ++ ) { int a, b; scanf("%d%d", &a, &b); add(a, b, 0);//用权值来表示是否要反转当前边 ，权值记录的就是反转次数 add(b, a, 1);//如果正向说明不需要反转权值为0，反向需要反转权值为1 } dfs_down(1, -1);//先向下搜记录down数组 dfs_up(1, -1);.//再向上搜索 int res = N; for (int i = 1; i <= n; i ++ )//寻找需要反转最少的次数 res = min(res, down[i] + up[i]); printf("%dn", res); for (int i = 1; i <= n; i ++ )//与最少反转次数相等的节点就是中心点 if (down[i] + up[i] == res) printf("%d ", i); return 0; }
看完代码可能会有这么几个问题：
问题1：dfs函数的变量from记录的是什么？ 答：在一般的树形dp中我们通常记录的两个变量是当前节点u和父节点fa，但此题需要计算反转次数，为了方便计算边的权值，我们存储的是边;当我们需要获得父节点时可以用fa=e[from ^ 1];,也就是过来的这条边的反向边的目标节点就是父节点 问题2：from^1是神马意思？ 答：当我们用邻接表存储树的时候是把正向边反向边成对存储的，如(0,1)(4,5),这样的一对数我们正好可以用异或来转换。所以为了在向下搜索的时候避免回头当当前边是反向边的时候我们直接跳过; 问题3：up[u]=up[fa]+down[fa]-down[u]-w[f]+w[f^1]是怎么来的 答：u点向上走的权值等于父节点向上走的权值加上父节点向下走的权值总和减去u节点向下走的权值(因为u本身是父节点fa向下走的一条路)减去父节点到u节点的权值再加上u节点走向父节点这条边的权值
Java和C++还是有很多不同，试了一些，好多bug。。。这里就不附上Java代码了。
