第一届ACC(AcWing Cup)全国高校联赛（决赛）
两个闹钟合并石子翻转树边
第一届ACC(AcWing Cup)全国高校联赛（决赛）大赛简介：
ACC(AcWing Cup)高校联赛是由AcWing举办的算法比赛，难度与蓝桥杯省赛持平，比赛设立高校团体排行榜和丰厚奖金。
2021年，北京大学AcWing杯程序设计竞赛圆满举行；2022年，AcWing将与更多高校一起培养更多算法人才。
赛制：
ACM赛制，共90分钟，3道题目，每道题目记1分。
每道题目的罚时为AC时刻与比赛开始时刻所经过的时间。
通过题目的非AC提交每次罚时5分钟。
通过题目数相同时，总罚时短的同学排名靠前。
有两个闹钟。 第一个闹钟会在 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
第一题做的时候就没想什么，就直接暴力, 没想到直接过了
#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; }
这里再附上JAVA代码：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
long a=sc.nextInt();
long b=sc.nextInt();
long c=sc.nextInt();
long d=sc.nextInt();//输入四个数
long arr[]=new long[103];
long arr2[]=new long[103];//开两个较大的数组
int n=102;
for(int i=1;i<=n;i++){
arr[i]=b;
arr2[i]=d;
b+=a;
d+=c;//将b+a*i和d+c*i分别放进两个数组中
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(arr[i]==arr2[j]){
System.out.println(arr[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
这道题最开始没读懂题，也就没有思路，后来静下来又慢慢地一个一个字的读题，才发现应该是前缀和和双指针，然后就试了一下。
#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; }
也附上JAVA代码
import java.util.Scanner;
public class Main{
public static void main(String[] args){
int res = 0;
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[]a = new int[n + 1];
int[]b = new int[m + 1];
for(int i = 0; i < n; i++) a[i] = sc.nextInt();
for(int i = 0; i < m; i++) b[i] = sc.nextInt();
int i = 0;
int j = 0;
int c1 = a[0];
int c2 = b[0];
while(i < n || j < m){
if(c1 == c2){
res++;
i++;
j++;
c1 = a[i];
c2 = b[j];
//如果c1小于c2就把c1后面加进来
}else if(c1 < c2){
i++;
c1 += a[i];
//同理就行
}else{
j++;
c2 += b[j];
}
}
System.out.println(res);
}
}
翻转树边
给定一个 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
第三题我是真的没读懂题，然后看了y总的直播到现在也没明白，先附上y总的代码吧。
#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) { for (int i = h[u]; ~i; i = ne[i]) { if (i == (from ^ 1)) continue; 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); } dfs_down(1, -1); 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; } 作者：yxc 链接：https://www.acwing.com/activity/content/code/content/3032110/ 来源：AcWing 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
小羊还是差得远呢，小羊加油吧。
