A. Prison Break
题意：就是在一个n*m的矩阵中，以(1,1)为起点(n,m)为终点，每个点以每个单位1s的速度移动，问总共至少需要多少秒，所有的矩阵点就能够全部移动到(r,c)中
思路：直接计算横坐标中最大需要多少秒，用最左边的点和最右边的点到r比较，纵坐标也是如此，然后算两者最大的加和
代码：
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cmath> 5 #include<cstring> 6 using namespace std;//15.23 7 int main(){ 8 int n; 9 scanf("%d",&n); 10 while(n--){ 11 int a,b,c,d; 12 scanf("%d %d %d %d",&a,&b,&c,&d); 13 int maxx1=max(abs(a-c),abs(c-1)); 14 int maxx2=max(abs(b-d),abs(d-1)); 15 printf("%d\n",maxx1+maxx2); 16 } 17 }
B. Repainting Street
题意：给出n个数，可以每次从这组数中连续选k个，选中的k个数可以变化也可以不变化，问最少多少次，才能把这n个数全部变为1个数
思路：暴力模拟，模拟的应该是以这100个数为基准，因为这些元素的范围是从1-100，然后再去遍历数组，如果数组中存在这个数，那么就直接进行下标+k，到下一个位置，循环遍历，直到n结束（学会从已知多的方面入手，并且所知道的范围就比较小，直接跳跃式遍历，进行数组元素的修改）
代码：
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cmath> 5 #include<cstring> 6 using namespace std;//15.23 7 int main(){ 8 int n; 9 scanf("%d",&n); 10 while(n--){ 11 int n,k; 12 scanf("%d %d",&n,&k); 13 int a[n],sign[110]={0}; 14 for(int i=0;i<n;i++){ 15 scanf("%d",&a[i]); 16 sign[a[i]]=1; 17 } 18 int sum=1e5+10; 19 for(int i=0;i<=100;i++){ 20 if(sign[i]){ 21 int temp=0; 22 for(int j=0;j<n;j++){ 23 if(a[j]!=i){ 24 temp++; 25 j+=k-1; 26 } 27 } 28 if(temp<sum){ 29 sum=temp; 30 } 31 } 32 } 33 printf("%d\n",sum); 34 } 35 }
C.Bouncing Ball
题意：给出一个长度为n的字符串，只有0和1构成，然后从第p个位置开始，p+k,p+2k,....,一直到n，所在的位置必须全部都是1，现在有两个操作，一个是把相对第一个去掉花费x，二是把指定位置的0变成1花费y，问满足题目中的条件时至少需要花费多少钱
思路：后缀和的思想，有点偏一维的dp，从最后一个位置开始统计0的个数，当i+k<=n时，花费的前就是当前位置和第i+k个位置总共多少，因为只要是一个位置定了，它在此操作中的所有位置就都定了
代码：
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cmath> 5 #include<cstring> 6 using namespace std; 7 const int maxx=1e5+10; 8 9 int main(){ 10 int nn; 11 scanf("%d",&nn); 12 while(nn--){ 13 int x,n,y,p,k;//n总数，p最初的位置，k跳跃的格数 14 scanf("%d %d %d",&n,&p,&k); 15 char a[maxx]; 16 int b[maxx]={0}; 17 getchar(); 18 for(int i=1;i<=n;i++){ 19 scanf("%c",&a[i]); 20 } 21 scanf("%d %d",&x,&y); 22 for(int i=n;i>=1;i--){ 23 if(a[i]==‘0‘){ 24 if(i+k<=n){ 25 b[i]+=b[i+k]+x; 26 }else{ 27 b[i]=x; 28 } 29 }else{ 30 if(i+k>n){ 31 b[i]=0; 32 }else{ 33 b[i]=b[i+k]; 34 } 35 } 36 37 } 38 long long int sum=1e30; 39 for(int i=p;i<=n;i++){//按1算实在是太复杂，还得推算出具体有多少步的1 40 long long int temp=0; 41 temp=b[i]; 42 sum=min(sum,temp+(i-p)*y); 43 } 44 long long int s=(n-p+1)*x; 45 sum=min(s,sum); 46 printf("%d\n",sum); 47 } 48 }
Codeforces Round #687 (Div. 2, based on Technocup 2021 Elimination Round 2)
原文：https://www.cnblogs.com/bonel/p/14109227.html
