RC-u1 智能红绿灯
为了最大化通行效率同时照顾老年人穿行马路，在某养老社区前，某科技公司设置了一个智能红绿灯。
这个红绿灯是这样设计的：
- 路的两旁设置了一个按钮，老年人希望通行马路时会按下按钮；
- 在没有人按按钮的时候，红绿灯一直为绿灯；
- 当红绿灯为绿灯时，有人按下按钮，第一次按下按钮的 15 秒后绿灯会转红；
- 转红后，红灯会持续 30 秒，方便老年人穿行马路；
- 在 30 秒的红灯期间，假如有人再次按下按钮，则红灯会再延续 15 秒；
- 延续一次后不会再次延续。
现在给定按钮被按下的时间点，请你输出这个智能红绿灯的红灯时间区间。
注意：我们假设同一秒内，红绿灯先变化，然后按钮再被按下。每 1 秒理解为一个时间点。例如：在第 1 秒按下按钮，则第 16 秒开始变红；如果没有人在第 16 - 45 秒这个闭区间内按下按钮，则到第 46 秒开始变绿。而在第 46 秒按下按钮的人，需要等 15 秒后才有红灯。
输入格式
输入第一行为 N (1≤N≤1000)，表示按钮被按下的次数。
接下来一行 N 个非负整数，表示按钮被按下的时间点。一个时间点按钮有可能会被多次按下，给出的时间点保证是不递减的。
时间点的范围不超过 104。
输出格式
输出若干行，按起始时间从小到大输出互不相交的红灯的时间区间。
输入样例
10
3 4 5 6 33 45 49 70 90 100
输出样例
18 62
85 129
解法
用l,r两个变量维护一个红灯区间，每次输入判断一下。
注意：这里红灯区间只能叠加一次15s，需要用f记录一下。
代码
#include<bits/stdc++.h>
using namespace std;
int n,t,l,r; //[l,r-1]红灯区间
bool f;//保证红灯范围内最多加一次15s
vector<pair<int,int> > ans;
int main(void){
cin>>n;
cin>>t;
l = t+15;
r = t+45;
for(int i = 1 ; i < n ; i ++){
cin>>t;
if(!f && t >= l && t < r){
r += 15;
f = true;
}else if(t >= r){
ans.push_back(make_pair(l,r-1));
l = t+15;
r = t+45;
f = false;
}
}
ans.push_back(make_pair(l,r-1));
for(auto it : ans){
cout<<it.first<<" "<<it.second<<endl;
}
return 0;
}
RC-u2 女王的大敕令
副本是游戏里的一个特色玩法，主要为玩家带来装备、道具、游戏资源的产出，满足玩家的游戏进程。
在 MMORPG《最终幻想14》里，有一个攻略人数最大达到 48 人的副本“零式贡希尔德神庙”，其中守关 BOSS “天佑女王”有一个很有趣的技能：“女王的大敕令”。
技能在一个 5×5 的棋盘上展开。每位玩家根据给定的两个步长，从某个方格出发，在棋盘上先走 D1 步，再走 D2 步。其中“步长”指的是曼哈顿距离，即：设两个方格的坐标分别为 (X**i,Y**i) 以及 (X**j,Y**j)，则这两个方格的曼哈顿距离 D=∣X**i−X**j∣+∣Y**i−Y**j∣。
例如下图中的 A 点与 B 点的曼哈顿距离为 5：
技能开始时，场地外围会出现 4 只小怪，东南西北（即棋盘的右、下、左、上）方向各出现一只小怪，且小怪一定出现在某行或某列对应的位置上。第 i 只小怪会顺时针朝固定方向移动 n**i 步（题目保证不会移出界，即移动后仍然在对应着某行/某列的位置上），且：
- 北边的小怪固定向右移动；
- 东边的小怪固定向下移动；
- 南边的小怪固定向左移动；
- 西边的小怪固定向上移动。
小怪出现后，棋盘上还会出现一个发光的格子，这是玩家移动的目标点，如图所示：
玩家必须在不被小怪杀死的前提下，按规定步长，用两个回合到达目标点。技能流程如下：
1、玩家先选择一个起始方格；
2、东、西两侧的小怪开始按照固定方向移动，移动完毕后 4 只小怪会同时开展攻击，其中东、西两侧的小怪攻击自己所对应的一整行，南、北两侧的小怪攻击自己所对应的一整列。玩家若处在攻击区内则任务失败。
3、玩家移动 D1 步，到达某个方格；
4、南、北两侧的小怪开始按照固定方向移动，移动完毕后 4 只小怪会同时开展攻击，同第 2 步；
5、玩家移动 D2 步，此时必须到达目标点，否则任务失败。
以下是上面的 4 只小怪都移动后的攻击范围的示意图：
给定小怪起始位置以及移动步数 n**i 和目标点位置，请输出所有安全的移动方案，包括起始点以及第一次移动的目的地。
输入格式
输入第一行是四个数 C1,C2,R1,R2，分别表示：
- 北边（上面）的小怪 1 在第 C1 列的位置上；
- 南边（下面）的小怪 2 在第 C2 列的位置上；
- 西边（左边）的小怪 3 在第 R1 行的位置上；
- 东边（右边）的小怪 4 在第 R2 行的位置上。
输入第二行是四个数 n**i（i=1,⋯,4），按照上面的顺序给出小怪移动的步数，保证小怪移动后仍然处于某行或某列对应的位置上。
输入第三行是四个数 ro**w,co**l,D1,D2，依次表示目标点的位置，以及玩家要走的两个步长。这里某方格的“位置” (ro**w,co**l) 指的是该方格的行号、列号组成的二元组。
我们假设左上角的方格位置为 (1, 1)。
输出格式
输出安全移动的方案，方案由两个位置共四个数组成，前两个数为初始选择的方格的位置，后两个数为第一次停留的位置。
对于多个方案的情况，先按初始方格位置从小到大输出，初始方格相同时按第一次停留位置从小到大输出。一个坐标 (r**i,c**i) 比另一个坐标 (r**j,c**j) 小，当且仅当 r**i<r**j，或 r**i=r**j 的同时有 c**i<c**j。
输入样例
2 4 4 2
1 2 3 2
5 3 3 4
输出样例
2 1 2 4
2 3 3 1
2 3 3 5
解法
我这里用了一个两步的DFS：
第一步：按曼哈顿距离D1，遍历一下中间节点
第二步：判断能不能从中间节点，以D2的距离，走到终点
除了DFS，也可以用四重循环遍历两个点坐标，再判断曼哈顿距离，更简便。
代码
#include<bits/stdc++.h>
using namespace std;
int c1,c2,r1,r2;//北，南，西，东
int t1,t2,t3,t4;
int fx,fy,d1,d2;
int sx,sy,mx,my;
int dirx[4] = {1,-1,-1,1};
int diry[4] = {1,-1,1,-1};
struct res{
int x1,y1,x2,y2;
res(int x1_,int y1_,int x2_,int y2_){
x1 = x1_;
y1 = y1_;
x2 = x2_;
y2 = y2_;
}
bool operator<(const res & rhs){
if(x1 != rhs.x1) return x1 < rhs.x1;
if(y1 != rhs.y1) return y1 < rhs.y1;
if(x2 != rhs.x2) return x2 < rhs.x2;
if(y2 != rhs.y2) return y2 < rhs.y2;
}
};
vector<res> ans;
void dfs(int dep){
if(dep == 2){
ans.push_back(res(sx,sy,mx,my));
return;
}
if(dep == 0){
if(sx == r1 - t3 || sx == r2 + t4 || sy == c1 || sy == c2){
return;
}
for(int i = 0 ; i <= d1 ; i ++){
int j = d1 - i;
int s = 4; //如果i,j为0，有重复的情况，用s去重。
if(i == 0 || j == 0) s = 2;
for(int k = 0 ; k < s ; k ++){ //遍历中间节点
mx = sx + i*dirx[k];
my = sy + j*diry[k];
if(mx >= 1 && mx <= 5 && my >= 1 && my <= 5) dfs(1);
}
}
return;
}
if(dep == 1){
if(mx == r1 - t3 || mx == r2 + t4 || my == c1 + t1 || my == c2 - t2){
return;
}
bool arv = false;
for(int i = 0 ; i <= d2 ; i ++){
int j = d2 - i;
int s = 4;
if(i == 0 || j == 0) s = 2;
for(int k = 0 ; k < s ; k ++){ //判断能不能走到终点
if(mx + i*dirx[k] == fx && my + j*diry[k] == fy){
arv = true;
}
}
}
if(arv) dfs(2);
return;
}
}
int main(void){
cin>>c1>>c2>>r1>>r2;
cin>>t1>>t2>>t3>>t4;
cin>>fx>>fy>>d1>>d2;
for(int i = 1 ; i <= 5 ; i ++){
for(int j = 1 ; j <= 5 ; j ++){
sx = i;
sy = j;
dfs(0);
}
}
sort(ans.begin(),ans.end());
for(res it : ans){
cout<<it.x1<<" "<<it.y1<<" "<<it.x2<<" "<<it.y2<<endl;
}
return 0;
}
RC-u3 战利品分配
在某个战争游戏中，多个玩家组成一个大型军团，攻下若干城池，并获得战利品。
具体而言，游戏中有 N 个城市，并以 M 条长度为 1 的无向道路连接，玩家们组成的军团从 S 号城市开始进攻，目的地是 T 号城市，每个城市攻下后的战利品价值为 p**i。
为了合理地分配战利品，军团们定下了规矩：假设军团里有 K 位玩家，那么从 S 号城市开始，第 1 个攻下的城市分配给第 1 位玩家，第 2 个攻下的分配给第 2 位玩家，……，第 K 个攻下的分配给第 K 位玩家，第 K+1 个攻下的则重新开始计算，分配给第 1 位玩家，以此类推。
军团很强，路上所有的城市都可以轻松进攻下来。你作为军团的指挥，可以指定玩家的进攻路线。但玩家们都希望尽快结束游戏，因此 S 到 T 的距离必须是最短的。你需要做的是在最短距离的限制下选择对自己最好的线路，获得尽可能高的战利品价值。请输出你的答案。
输入格式
输入第一行是四个数 N,M,K,P (1≤N,M≤105,1≤K≤104,1≤P≤K)，表示城市数量（于是城市从 1 到 N 编号）、连接道路数量以及你在军团中的 K 位玩家中排第 P 位（即你战利品分配在第 P 位）。
第二行是 N 个被空格隔开的非负整数，第 i 个数对应 p**i (0≤p**i≤104)，表示编号为 i 的城市的战利品价值（i=1,⋯,N）。
然后的 M 行，每行给出两个用空格分隔的正整数 U 和 V，表示编号为 U 和 V 的城市之间有道路连接。
最后的一行是两个正整数 S,T，表示开始的城市编号与目的地的城市编号。开始和目的地的城市也是可以进攻并获取战利品的。
输出格式
输出一行，表示你可以取得的最大价值。
输入样例
9 11 2 2
100 150 130 50 30 20 200 0 70
1 2
1 3
2 3
2 4
2 5
3 6
4 7
5 7
6 8
7 9
8 9
1 9
输出样例
350
解法
无权图的单源最短路问题，考虑使用BFS来做。
在层序遍历时，维护路径的价值sum，从多条最短路中选择一条价值最高的，即为答案。
代码
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1e6;
int n,m,k,p,s,t,ans;
int val[MAX];
bool visited[MAX];
vector<int > edge[MAX];
struct step{
int x;
int dep;
int sum;
step(int x_,int dep_,int sum_){
x = x_;
dep = dep_;
sum = sum_;
}
};
void bfs(){
queue<step> q;
q.push(step(s,1,0));
int min_ = INT_MAX;
int ans = 0;
while(!q.empty()){
int x = q.front().x;
int dep = q.front().dep;
int sum = q.front().sum;
q.pop();
if(dep > min_) break;
if(dep % k == 0 && k == p) sum += val[x]; //k==p需要特判
else if(dep%k == p) sum += val[x];
if(x == t && dep <= min_){
ans = max(sum,ans);
min_ = dep;
}
visited[x] = true;
for(auto it : edge[x]){
if(!visited[it]) q.push(step(it,dep+1,sum));
}
}
cout<<ans<<endl;
}
int main(void){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m>>k>>p;
for(int i = 1 ; i <= n ; i ++){
cin>>val[i];
}
for(int i = 1 ; i <= m ; i ++){
int a,b;cin>>a>>b;
edge[a].push_back(b);
edge[b].push_back(a);
}
cin>>s>>t;
bfs();
return 0;
}
RC-u4 变牛的最快方法
这里问的是把任意一种动物的图像变成牛的方法…… 比如把一只鼠的图像变换成牛的图像。方法如下：
- 首先把屏幕上的像素点进行编号；
- 然后把两只动物的外轮廓像素点编号按顺时针记录下来；
- 用最少的变换次数将鼠的轮廓变成牛的 —— 这里仅允许对鼠的轮廓进行 3 钟操作：
- 插入一个像素编号
- 删除一个像素编号
- 更改一个像素编号
输入格式
输入分别在两行中给出两种动物的轮廓像素点编号，编号为 (0,106] 区间内的整数，允许重复。轮廓以编号 −1 结尾，这个编号不算在轮廓内。题目保证每种动物的轮廓包含不超过 1000 个像素点。
输出格式
在第一行中输出从第一只动物变换成第二只动物需要的最少变换次数。
在第二行中顺次描述对第一只动物轮廓的每个像素所作的操作：
- 如果这个像素被删除，则在对应位置输出 0
- 如果这个像素被改变，则在对应位置输出 1
- 如果这个像素不变，则在对应位置输出 2
- 如果这个像素前面或者后面插入了一个像素，则在插入的位置输出 3
答案可能不唯一，输出任何一种可能的解都可以。行首尾和数字间均无空格。
输入样例
13 5 6 20 2 20 1 13 9 20 3 28 3 34 6 25 233 -1
3 5 6 20 6 20 3 5 9 3 9 20 3 6 6 25 233 -1
输出样例
8
122212112023121222
样例解释
1、13 更改为 3，随后 5、6、20 不变
2、2 更改为 6，下一个 20 不变
3、1 更改为 3
4、第二个 13 更改为 5，随后 9 不变
5、删除下一个 20，后面的 3 不变
6、在 28 的前面插入 9
7、28 更改为 20，后面的 3 不变
8、34 更改为 6，后面的 6、25、233 不变
解法
动态规划经典 之 最短编辑距离+路径回溯
状态转移： d p [ i ] [ j ] = m i n ( d p [ i − 1 ] [ j ] + 1 , d p [ i ] [ j − 1 ] + 1 , d p [ i − 1 ] [ j − 1 ] + ( a 1 [ i ] ! = a 2 [ j ] ) ) dp[i][j] = min(dp[i-1][j] + 1,dp[i][j-1] + 1,dp[i-1][j-1] + (a1[i] != a2[j])) dp[i][j]=min(dp[i−1][j]+1,dp[i][j−1]+1,dp[i−1][j−1]+(a1[i]!=a2[j]))
当前最优的状态 = 删除/插入/不变/变换 这四种操作执行后，耗费次数最小的。
路径回溯需要在dp数组生成过程中维护pre（路径）数组和op（操作）数组。
代码
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1050;
int l1,l2;
int a1[MAX],a2[MAX];
pair<int,int> pre[MAX][MAX];
int op[MAX][MAX],dp[MAX][MAX];
//删除 0 改变 1 不变 2 插入 3
int main(void){
while(cin>>a1[++l1]){
if(a1[l1] == -1) break;
}l1--;
while(cin>>a2[++l2]){
if(a2[l2] == -1) break;
}l2--;
for(int i = 0 ; i <= l1 ; i ++){
pre[i][0] = make_pair(i-1,0);
dp[i][0] = i;
op[i][0] = 0;
}
for(int i = 0 ; i <= l2 ; i ++){
pre[0][i] = make_pair(0,i-1);
dp[0][i] = i;
op[0][i] = 3;
}
for(int i = 1 ; i <= l1 ; i ++){
for(int j = 1 ; j <= l2 ; j ++){
int add = dp[i][j-1] + 1; // 3
int del = dp[i-1][j] + 1; // 0
int rpl = dp[i-1][j-1] + (a1[i] != a2[j]); //1 ; 2
int min_ = min(add,min(del,rpl));
if(min_ == add){
dp[i][j] = add;
pre[i][j] = make_pair(i,j-1);
op[i][j] = 3;
}else if(min_ == del){
dp[i][j] = del;
pre[i][j] = make_pair(i-1,j);
op[i][j] = 0;
}else{
dp[i][j] = rpl;
pre[i][j] = make_pair(i-1,j-1);
op[i][j] = a1[i] == a2[j] ? 2:1;
}
}
}
cout<<dp[l1][l2]<<endl;
//路径回溯
int x = l1;
int y = l2;
stack<int> ans;
while(x||y){
ans.push(op[x][y]);
auto back = pre[x][y];
x = back.first;
y = back.second;
}
while(!ans.empty()){
cout<<ans.top();
ans.pop();
}
return 0;
}
RC-u5 养老社区
作为智能看护的一部分，你需要评估某个养老社区是否适合开展智能看护的服务。
这个养老社区有若干幢住宅楼，每个住宅楼有一个种类，住宅楼之间由长度为 1 的道路连接，道路都是双向道路且没有构成环 —— 你可以简单地认为养老社区的路构成了一棵树。
假设我们能找到三个住宅楼，这三个住宅楼两两之间的最短距离相等，并且三个住宅楼的种类不一样，那么我们称这三个住宅楼组成的三元组为适合智能看护的，指的是为了服务这三个住宅楼，我们可能可以方便地找到适合建设服务中心的地方。一个社区的适合度指的是能够找到多少本质不同的适合智能看护的住宅楼三元组。
本质不同两个的三元组指的是：三元组内元素任意排列后，两个三元组仍然不相等。
给定这个养老社区的情况，请你求出这个社区的适合度。
输入格式
输入第一行是一个正整数 N (1≤N≤2×103)，表示养老社区里住宅楼的数量（于是住宅楼从 1 到 N 编号）。
接下来 N−1 行，每行给出空格分隔的两个正整数 U 和 V，表示编号为 U 和 V 的住宅楼之间有一条长度为 1 的道路。
最后一行给出 N 个数，第 i 个数表示编号为 i 的住宅楼的种类为 T**i（1≤T**i≤N）。
保证给定的数据会将所有住宅楼连接成一棵完整的树。
输出格式
输出一行一个正整数，表示社区的适合度。
输入样例
11
1 2
1 3
1 4
2 5
2 6
3 7
3 8
4 9
4 10
1 11
1 2 3 4 5 6 7 8 9 9 10
输出样例
14
解法
多源无权图最短路问题（n <= 2000），考虑使用n次的BFS。
首先，使用n次BFS，得到每个点的最短路径数组。
然后，三重循环遍历每个三元组，判断是否符合条件即可。
一次写的时候，用Floyd去做:），实测能过 5/8个样例。
代码
#include<bits/stdc++.h>
using namespace std;
const int MAX = 2e3 + 10;
const int INF = 0x3f3f3f3f;
int n;
int type[MAX];
int dist[MAX][MAX];//dist[i][j]:i->j的最短路
bool visited[MAX];
vector<int> edge[MAX];
void bfs(int st){
queue<pair<int,int> > q;
memset(visited,0,sizeof(visited));
q.push({st,0});
while(!q.empty()){
int x = q.front().first;int dep = q.front().second;q.pop();
dist[st][x] = min(dist[st][x],dep);
visited[x] = true;
for(auto it : edge[x]){
if(!visited[it]) q.push({it,dep+1});
}
}
}
int main(void){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n;
memset(dist,INF,sizeof(dist));
for(int i = 1 ; i <= n-1 ; i ++){
int x,y;
cin>>x>>y;
edge[x].push_back(y);
edge[y].push_back(x);
}
for(int i = 1 ; i <= n ; i ++){
cin>>type[i];
}
for(int i = 1 ; i <= n ; i ++){
bfs(i);
}
int ans = 0;
for(int i = 1 ; i <= n ; i ++){
for(int j = i+1 ; j <= n ; j ++){
if(type[i] == type[j] || dist[i][j] == INF) continue;//这里必须优化，不然过不了
for(int u = j+1 ; u <= n ; u ++){
if(type[i] != type[j] && type[j] != type[u] && type[i] != type[u]
&& dist[i][j] != INF && dist[i][j] == dist[j][u] && dist[i][j] == dist[i][u]){
ans++;
}
}
}
}
cout<<ans<<endl;
}