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中的元素，所以就等价为 an - an-1 ,…… a3 - a2，a2 - a1 中不为0的所有数即为c，每次选择k - 1个至少需要多少次
⌈
c
k
−
1
⌉
\lceil \frac{c}{k-1} \rceil
⌈k−1c⌉，（因为第一次可以是k次，所以可以忽略a1使第一次为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个机器人的坐标（ai,bi）和m个灯光的照射范围(ci,di)（每个灯光可以照射给定点的以下区域），你可以控制所有的机器人，x方向走一个或y方向走一个，询问所有机器人都逃离灯光的照射所需要的最少步数
思路
对于每个机器人走的步数，可以假设为(ai + x, bi + y) ，对于每个照射区域，都要满足 ai + x <= cj ，bi + y <= dj不成立，当 ai + x <= cj ，要满足 y >= dj - bi + 1，所以我们可以用一个数组f表示这种情况，该数组的下标i表示移动的步数小于等于i的情况下需要移动的步数，但是该步数并不是最直接的意思，他还需要依赖大于i的最大步数，比如： ····当 ai <= cj且bi <= dj,我们只需记录f[cj - ai]（cj - ai表示最大情况下的x满足ai + x <= cj ）需要的步数为 dj - bi + 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;
}
