Grakn Forces 2020 A - D

1408A - Circle Coloring

题意

给定长度n为三个数组a，b，c其中ai != bi != ci 从中选择一个收尾相连的数组是数组的第i为元素是ai ，bi 或ci 的一个，但相邻的元素不能相同

思路

很简单的一道模拟题，可以从下标为1开始找只要保证这个数和他前面的一个数不相等就可以，最后一个数特判一下，因为ai != bi != ci 所以每个数是必然满足条件的

代码

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int N = 1e3+10;
int a[N],b[N],c[N];
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]);
        for(int i = 0;i < n;i++) scanf("%d",&b[i]);
        for(int i = 0;i < n;i++) scanf("%d",&c[i]);
        int last = a[0];
        vector<int >ans;
        ans.push_back(last);
        for(int i = 1;i<n - 1;i++){
            if(a[i] != last) last = a[i];
            else if(b[i] != last) last = b[i];
            else if(c[i] != last) last = c[i];
            ans.push_back(last);
        }
        if(a[n - 1] != last && a[n - 1] != ans[0]) last = a[n - 1];
        else if(b[n - 1] != last && b[n - 1] != ans[0]) last = b[n - 1];
        else last = c[n - 1];
        ans.push_back(last);
        for(auto x : ans){
            cout<<x<<' ';
        }
        puts("");
    }
    
    return 0;
}

1408B - Arrays Sum

题意

给定一个非严格单调递增的数组a，求数组a可以由最少多少个数组b组成，其中数组b也是非严格单调递增的，但是数组b的元素个数有限，只能为k个

思路

首先先想特殊的
····当所有元素都相同的话只有一个
····当次数为1的话，如果含有不同的元素那么必然不可能
对于剩下的情况
····由于b也是单调递增的，因为最少，我能就尽可能希望每次能够多表示一些ai，不难想到每次除了第一次以外只能表示出k - 1一个a中的元素，所以就等价为 a_n - a_n-1 ,…… a₃ - a₂，a₂ - a₁ 中不为0的所有数即为c，每次选择k - 1个至少需要多少次 $\lceil \frac{c}{k-1}\rceil$，（因为第一次可以是k次，所以可以忽略a₁使第一次为k - 1次）

代码

#include<iostream>
 
using namespace std;
const int N = 110;
int a[N];
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n,k;
        scanf("%d%d",&n,&k);
        for(int i = 1;i<=n;i++) scanf("%d",&a[i]);
        if(a[1] == a[n]) {
            puts("1");
            continue;
        }
        else if(k == 1){
            puts("-1");
            continue;
        }
        int c = 0;
        for(int i = n;i > 1;i--){
            int x = a[i] - a[i - 1];
            if(x > 0) c++;
        }
        cout<<(c + k - 2)/(k - 1) <<endl;
    }
    
    return 0;
}

1408C - Discrete Acceleration

题意

给定长度为L的一条路，一个人从0出发，一个从L出发，他们相向而行，给定一个数组a（递增）每一次通过a中的一个节点，他的速度就会加1（默认速度为1），求多少秒后，他们会相遇

思路

可以使用双指针的思路，求两个人谁先到达离自己最近的点，然后这个人的速+1，另个一人也走这个时间段的路程，然后继续这个过程，直到所有的点都被用过，最后他们以各自的速度走完剩下的路程

代码

#include<iostream>
 
using namespace std;
const int N = 1e5+10;
int a[N];
 
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n,l;
        scanf("%d%d",&n,&l);
        for(int i = 1;i<=n;i++) scanf("%d",&a[i]);
        int i = 1,j = n;  // 离他们最近的点
        double s = 0,e = l; //  初始位置
        int v1 = 1,v2 = 1; // 初始速度
        double ans = 0;   // 统计答案
 
        while(i <= j){  // 遍历所有的点
            double t1 = (double)(a[i] - s)/v1;  // 向右走，走到下一个点的 时间
            double t2 = (double)(e - a[j])/v2;  // 向左走，走到下一个点的 时间
            // cout<<t1<<' '<<t2<<endl;
            // 判断谁先走到下一个点，给答案加上这个点对应的时间
            // 走到这个点的速度+1,另一个人走这段时间相应的路程
            if(t1 < t2){  
                ans += t1;  
                s = a[i];
                e = e - v2 * t1;
                v1++;
                i++;
            }
            else{
                ans += t2;
                e = a[j];
                s = v1 * t2 + s;
                v2++;
                j--;
            }
        }
        // cout<<v1<<' '<<v2<<endl;
        // cout<<e<<' '<<s<<endl;
        ans += (e - s ) / (v1 + v2);  // 剩下的路程一起走的时间
        printf("%.8lf\n",ans);
    }
    
    return 0;
}

1408D - Searchlights

题意

给定n个机器人的坐标（a_i,b_i）和m个灯光的照射范围(c_i,d_i)（每个灯光可以照射给定点的以下区域），你可以控制所有的机器人，x方向走一个或y方向走一个，询问所有机器人都逃离灯光的照射所需要的最少步数

思路

对于每个机器人走的步数，可以假设为(a_i + x, b_i + y) ，对于每个照射区域，都要满足 a_i + x <= c_j ，b_i + y <= d_j不成立，当 a_i + x <= c_j ，要满足 y >= d_j - b_i + 1，所以我们可以用一个数组f表示这种情况，该数组的下标i表示移动的步数小于等于i的情况下需要移动的步数，但是该步数并不是最直接的意思，他还需要依赖大于i的最大步数，比如：
····当 a_i <= c_j且b_i <= d_j,我们只需记录f[c_j - a_i]（c_j - a_i表示最大情况下的x满足a_i + x <= c_j ）需要的步数为 d_j - b_i + 1，比他小的点默认这个值，所以在统计答案的时候可以从后往前，依次遍历

代码

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e6 + 10,M = 2010;
#define x first
#define y second
typedef pair<int ,int >PII;
PII r[M];
PII s[M];
int f[N];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++)
        scanf("%d%d",&r[i].x,&r[i].y);
    for(int i = 1;i <= m;i++)
        scanf("%d%d",&s[i].x,&s[i].y);
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++){
            if(r[i].x <= s[j].x && r[i].y <= s[j].y)
                f[s[j].x - r[i].x] = max(f[s[j].x - r[i].x],s[j].y - r[i].y + 1);
        }
    int ans = N;
    for(int i = N - 2;i >= 0;i--){
        f[i] = max(f[i],f[i + 1]);
        ans = min(ans,f[i] + i);
        
    }
    cout<<ans<<endl;
    return 0;
}