2020.3.28-ICPC训练联盟周赛，选用试题：UCF Local Programming Contest 2016
2024-08-31 06:42:07
A.Majestic 10
签到题。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<deque>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include <string>
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(false);
int n,a,b,c;
cin>>n;
while(n--)
{
int sum=0;
cin>>a>>b>>c;
cout<<a<<" "<<b<<" "<<c<<endl;
if(a%10==0&&a)sum++;
if(b%10==0&&b)sum++;
if(c%10==0&&c)sum++;
if(sum==0)cout<<"zilch"<<endl;
else if(sum==1)cout<<"double"<<endl;
else if(sum==2)cout<<"double-double"<<endl;
else cout<<"triple-double"<<endl;
cout<<endl;
}
}
B.Phoneme Palindromes
将所有可以相互替换的字母都统一替换成相同字母，然后判断回文即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<deque>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include <string>
using namespace std;
typedef long long ll;
string str[110];
int main()
{
ios::sync_with_stdio(false);
int T,n,i,cas=0,j;
char s,s1;
cin>>T;
while(T--)
{
map<char,char>mp;
cin>>n;
for(i=0;i<26;i++)
{
char c='a'+i;
mp[c]=c;
}
for(i=0;i<n;i++)
{
cin>>s>>s1;
mp[s]=mp[s1]=s;
}
cin>>n;
for(i=0;i<n;i++)
cin>>str[i];
cout<<"Test case #"<<++cas<<":"<<endl;
for(i=0;i<n;i++)
{
cout<<str[i]<<" ";
int fl=0;
int len=str[i].length();
for(j=0;j<len;j++)str[i][j]=mp[str[i][j]];
for(j=0;j<len/2;j++)
if(str[i][j]!=str[i][len-j-1])
{
fl=1;
break;
}
if(fl==0)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
cout<<endl;
}
}
C.Don’t Break the Ice
每敲掉一个冰块，改变其状态后判断与之相关的行列上的所有冰块，若有掉落的冰块（加入队列）继续改变判断即可。
#include<iostream>
#include<cstdio>
#include<set>
#include<queue>
#include<stack>
#include<vector>
#include<bitset>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=1e5+10;
inline int read(){
int x=0,y=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-'){
y=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*y;
}
int a[52][52];//表示第[i][j]冰块状态
int b[52][52];//表示第[i][j]冰块行上冰块数
int c[52][52];//表示第[i][j]冰块列上冰块数
queue<int> p,q;
void bfs(int x,int y,int n){
p.push(x),q.push(y);
while(!p.empty()){
x=p.front();
y=q.front();
p.pop(),q.pop();
a[x][y]=1;//标记冰块掉落 //接着对该冰块掉落后所影响的其他冰块进行判断
for(int i=1;i<=n;i++){
b[i][y]++;
if(c[i][y]&&!a[i][y]){
p.push(i),q.push(y);
}
c[x][i]++;
if(b[x][i]&&!a[x][i]){
p.push(x),q.push(i);
}
}
}
return;
}
int main(){
int T=read();
for(int t=1;t<=T;t++){
int ans=0;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
int n=read(),m=read();
for(int i=0;i<m;i++){
int x=read(),y=read(); if(a[x][y]){
ans++;
//倘若冰块已掉落则答案加1
}
else{
bfs(x,y,n);
//未掉落则标记其掉落
}
}
printf("Strategy #%d: ",t);
printf("%d\n",ans);
printf("\n");
}
return 0;
}
D.Loopy Word Search
存放每一个大写字母开头的位置，对每一串直接暴力搜索匹配即可（注意字符串可循环匹配，见样例2第2个字符串）
#include<iostream>
#include<cstdio>
#include<set>
#include<queue>
#include<stack>
#include<vector>
#include<bitset>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=1e5+10;
inline int read(){
int x=0,y=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-'){
y=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*y;
}
string s[110];
typedef struct NODE{
int x,y;
}N;
vector<N> a[26];//存储每个字母的位置
int main(){
int T=read();
for(int t=1;t<=T;t++){
for(int i=0;i<26;i++){
a[i].clear();
}
int n=read(),m=read();
for(int i=0;i<n;i++){
cin>>s[i];
for(int j=0;j<m;j++){
N tmp;
tmp.x=i,tmp.y=j;
a[s[i][j]-'A'].push_back(tmp);
}
}
printf("Word search puzzle #%d:\n",t);
int p=read();
string q;
for(int i=0;i<p;i++){
cin>>q;
int cnt=a[q[0]-'A'].size(); //从所需查询字符串的开头字母开始循环
for(int j=0;j<cnt;j++){ N tmp=a[q[0]-'A'][j];
int len=q.length();
int flag2=1;
//查询字母向上方向匹配情况
for(int e=(tmp.x+2*n-1)%n,f=1;f<len;f++,e=(e+2*n-1)%n){
if(q[f]!=s[e][tmp.y]){
flag2=0;
break;
}
}
if(flag2){
printf("U %d %d ",tmp.x+1,tmp.y+1);
cout<<q<<endl;
break;
}
flag2=1;
//查询字母向下方向匹配情况
for(int e=(tmp.x+1)%n,f=1;f<len;f++,e=(e+1)%n){
if(q[f]!=s[e][tmp.y]){
flag2=0;break;
}
}
if(flag2){
printf("D %d %d ",tmp.x+1,tmp.y+1);
cout<<q<<endl;
break;
}
flag2=1;
//查询字母向左方向匹配情况
for(int e=(tmp.y+2*m-1)%m,f=1;f<len;f++,e=(e+2*m-1)%m){
if(q[f]!=s[tmp.x][e]){
flag2=0;break;
}
}
if(flag2){
printf("L %d %d ",tmp.x+1,tmp.y+1);
cout<<q<<endl;
break;
}
//查询字母向右方向匹配情况
flag2=1;
for(int e=(tmp.y+1)%m,f=1;f<len;f++,e=(e+1)%m){
if(q[f]!=s[tmp.x][e]){
flag2=0;break;
}
}
if(flag2){
printf("R %d %d ",tmp.x+1,tmp.y+1);
cout<<q<<endl;
break;
}
}
}
printf("\n");
}
return 0;
}
E.Wildest Dreams
按照题目意思直接模拟即可（注意路段时间结束，女儿刚好离开时，歌曲按顺序播放，而不会到开头重复）
#include<iostream>
#include<cstdio>
#include<set>
#include<queue>
#include<stack>
#include<vector>
#include<bitset>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=1e5+10;
inline int read(){
int x=0,y=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-'){
y=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*y;
}
int a[110];//代表每首歌曲播放时间
int main(){
int T=read();
for(int t=1;t<=T;t++){
int n=read(),m=read();
int it1=0,it2=0,sum=0;
//it1为女儿喜欢歌曲开始时间
//it2为女儿喜欢歌曲结束时间
//sum为cd所有歌曲播放总时间
for(int i=1;i<=n;i++){
a[i]=read();
sum+=a[i];
if(i<m) {
it1+=a[i];
}
}
it2=it1+a[m];
printf("CD #%d:\n",t); int p=read();
for(int k=1;k<=p;k++){
int ans=0,it=0;
//it表示当前时间
int q=read();
for(int i=1;i<=q;i++){
int cnt=read();
if(cnt==0){
continue;
}
//当女儿在车上时答案直接加上当前路段时间
if(i%2==1){
ans+=cnt;
if(cnt%(it2-it1)==0){
it=it2;
}
else{
it=it1+cnt%(it2-it1);
}
}
//计算女儿不再车上时所听歌曲时间
else{
ans+=(it2-it1)*(cnt/sum);
cnt%=sum;
if(cnt<=it2-it){
ans+=cnt;
}
else{
ans+=it2-it;
if(cnt>=sum-it+it1){
ans+=cnt-(sum-it+it1);
}
}
it=(it+cnt)%sum;
}
}
printf("%d\n",ans);
}
printf("\n");
}
return 0;
}
F.Dot the i’s and Cross the T’s
这是一道普通的计算几何题，一种可行的思路如下：
二重循环枚举任意两个点构成的线段，把该线段作为线段
AB。
枚举所有的点，判断该点是否是线段
AB 的中点，如果是，则该点作为点
M。(由
于没有重合的点，所以对于每条线段
AB，点 M 最多只有一个)
如果找到了点 M，再次枚举所有的点，寻找点
C 是否存在。判断条件：|AB| = |CM|
且 AB ⊥ CM
注：
1. 判断中点的条件，点
M 在线段 AB 上且 |AM| = |BM|
2. 判断垂直可以用向量的点积等于 0 判断
3. 枚举任意两点构成的线段时间复杂度为
O(N2)，由于点 M 最多只有一个，所
以枚举点 C 最多只会执行一次，总体时间100×503=12,500,000
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
const double inf = 1e20;
const double pi = acos(-1.0);
const int maxp = 1010;
// 精度三态函数
int sgn(double x) {
if(fabs(x) < eps) return 0;
if(x < 0) return -1;
else return 1;
}
struct Point {
double x, y;
Point() {}
Point(double _x,double _y) {
x = _x;
y = _y;
}
void input() {
scanf("%lf%lf", &x, &y);
}
void output() {
printf("%.2f %.2f\n", x, y);
}
bool operator == (Point b)const {
return sgn(x-b.x) == 0 && sgn(y-b.y) == 0;
}
bool operator < (Point b)const {
return sgn(x-b.x)== 0?sgn(y-b.y)<0:x<b.x;
}
Point operator -(const Point &b)const {
return Point(x-b.x,y-b.y);
} // 向量叉积
double operator ^(const Point &b)const {
return x*b.y - y*b.x;
} // 向量点积
double operator *(const Point &b)const {
return x*b.x + y*b.y;
} double len() {
return hypot(x,y);
}
double len2() {
return x*x + y*y;
} // 当前点到点 p 的距离
double distance(Point p) {
return hypot(x-p.x,y-p.y);
}
Point operator +(const Point &b)const{
return Point(x+b.x,y+b.y);
}
Point operator *(const double &k)const{
return Point(x*k,y*k);
}
Point operator /(const double &k)const{
return Point(x/k,y/k);
} };
typedef Point Vector; // 向量
Point p[maxp]; // 输入的点
struct Line{
Point s,e;
Line(){}
Line(Point _s,Point _e){
s = _s;
e = _e;
}
bool operator ==(Line v){
return (s == v.s)&&(e == v.e);
}
void input(){
s.input();
e.input();
}
// 线段长度
double length(){
return s.distance(e);
}
// 点 p 是否在当前线段上
bool pointonseg(Point p){
return sgn((p-s)^(e-s)) == 0 && sgn((p-s)*(p-e)) <= 0;
} };
int main() {
int T;
scanf("%d", &T);
int kase = 0;
while(T--) {
int n;
scanf("%d", &n);
for(int i = 0; i < n; ++i) {
p[i].input();
}
int ans = 0; for(int i = 0; i < n; ++i) {
for(int j = i + 1; j < n; ++j) {
Line tmp = Line(p[i], p[j]); // 点 p[i] 和点 p[j] 构成线段 AB
for(int k = 0; k < n; ++k) { // 寻找中点 M
if(k == j || k == i) continue;
// 点 p[k] 在线段上，且点 p[k] 到点 p[i] 的距离与点 p[k] 到点 p[j] 的距离相等
if(tmp.pointonseg(p[k]) && sgn(p[k].distance(p[i]) - p[k].distance(p[j])) == 0) {
for(int l = 0; l < n; ++l) { // 寻找点 C
if(l == k || l == j || l == i) continue;
Line l1 = Line(p[i], p[j]); // 点 p[i] 与点p[j] 构成的线段，也就是线段 AB
Line l2 = Line(p[k], p[l]); // 点 p[k] 与点p[l] 构成的线段，也就是线段 MC
Vector v1 = p[i] - p[j]; // 点 p[i] 指向点 p[j] 的向量，也就是向量 AB
Vector v2 = p[k] - p[l]; // 点 p[k] 指向点 p[l] 的向量，也就是向量 MC
// l1 与 l2 的长度相等，向量 v1 与 v2 的点积为 0 (代表垂直)
if(sgn(l1.length() - l2.length()) == 0 && sgn(v1 * v2) == 0) {
++ans;
}
}
}
}
}
}
printf("Set #%d: %d\n\n", ++kase, ans);
}
return 0;
}
J.Jedi and the Galactic Empire
动态规划，对于每一颗子弹分为用武士1挡或者用武士2挡，同时记录下抵挡时已经抵挡的子弹颗数，以及武士1和武士2下一次可以抵挡的时间。
假设武士1的时间间隔为10，武士2的时间间隔为7
|
子弹到达的时间 |
0 |
2 |
4 |
8 |
13 |
13 |
|
|
武士1 抵挡 |
已抵挡子弹数az[0] |
0 |
1 |
2 |
2 |
3 |
4 |
|
武士1下一次抵挡时刻az[1] |
0 |
12 |
14 |
18 |
23 |
23 |
|
|
武士2下一次抵挡时刻az[2] |
0 |
0 |
9 |
9 |
11 |
20 |
|
|
武士2 抵挡 |
已抵挡子弹数az[3] |
0 |
1 |
2 |
2 |
3 |
4 |
|
武士1下一次抵挡时刻az[4] |
0 |
0 |
12 |
12 |
12 |
23 |
|
|
武士2下一次抵挡时刻az[5] |
0 |
9 |
11 |
15 |
20 |
20 |
每次往前找寻最优的上一次抵挡时刻时，满足当前时刻大于对应的武士的下一次抵挡时刻，已抵挡的子弹数最多，且另一个武士的抵挡时刻最小作为当前的数值。
例如第一次的13时刻的武士2抵挡，当前时刻为13也就是时刻4的两次抵挡以及时刻8的武士1抵挡，都满足当前时刻大于武士2下一次抵挡时刻，且子弹数最大为2，在此基础上时刻4的武士2抵挡的武士1下一次抵挡时刻最小，因此选择这一项作为上一次的抵挡，此项的已抵挡的子弹数加一，武士一的下一次抵挡时刻不变，武士2的下一次抵挡时刻更新为当前时刻加上武士2的时间间隔为最优。
最后记录下抵挡子弹数的最大数即可
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<stdlib.h>
#include<cmath>
#include<string>
#include<vector>
#define ll long long int
#define lll unsigned long long
const int INF=0x7fffffff;
const ll LNF=0x7fffffffffffffff;
const int MAX = 6005;
using namespace std;
ll ac[1005],ax[2],az[6][1005];//ac记录子弹到达时间，ax记录武士的格挡的时间差，az为dp的表格，具体见上表
int main(){
ll nn,kk=0,k,n,m,x,l,i,v,mx,mm,ma;
scanf("%lld",&nn);
while(kk<nn){
scanf("%lld",&n);
k=1;ma=0;
while(k<=n){
scanf("%lld",&ac[k]);
k++;
}
sort(ac+1,ac+n+1);//对子弹到达时间排序
k=0;
scanf("%lld",&m);
while(k<m){
scanf("%lld",&ax[k]);
k++;
}
k=0;
while(k<6){
az[k][0]=0;//对于0时刻各项均为0
k++;
}
k=1;
while(k<=n){//遍历每一个子弹到达的时刻
x=ac[k];
l=0;
while(l<m){//遍历这颗子弹由武士1还是武士2格挡
v=0;mx=0;
while(v<m){
i=0; //遍历之前的每一种情况
while(i<k){
if(az[3*v+l+1][i]<=x&&az[3*v][i]>mx){//找到满足对应的武士下一次抵挡时刻小于当前时刻，并且已抵挡子弹数最多的子弹数的数量
mx=az[3*v][i];
}
i++;
}
v++;
}
v=0;mm=LNF;
while(v<m){
i=0; //再次遍历之前的每一种情况
while(i<k){
if(az[3*v][i]==mx&&az[3*v+l+1][i]<=x&&mm>az[3*v-l+2][i]){//找到满足对应的武士下一次抵挡时刻小于当前时刻，并且已抵挡子弹数等于最多的子弹数，同时另一个武士的下一次抵挡时刻最小的情况
mm=az[3*v-l+2][i];
}
i++;
}
v++;
}
az[3*l][k]=mx+1;//当前已抵挡子弹数为之前已抵挡最多子弹数加1
ma=max(ma,az[3*l][k]);//ma记录下所有情况中已抵挡的最多的子弹数数量
if(l==0){//如果为武士1抵挡，武士1的下一次抵挡时刻为当前时刻加上武士1时间间隔，武士2下一次抵挡时刻不变
az[1][k]=x+ax[0];
az[2][k]=mm;
}
else{//如果为武士2抵挡，武士2的下一次抵挡时刻为当前时刻加上武士2时间间隔，武士1下一次抵挡时刻不变
az[4][k]=mm;
az[5][k]=x+ax[1];
}
l++;
}
k++;
}
kk++;
printf("Mission #%lld: %lld\n\n",kk,n-ma);//结果为所有子弹数减去已抵挡的最多的子弹数
}
return 0;
}
H.Count the Dividing Pairs
由于整数的重复出现，若A出现了x次，而B出现了y次，且(A,B)为整除对，可以发现形如（A,B）这样的整除对共有x*y对，用数组来记录数字出现的次数，数组记为count。暴力得到所有整除对(A,B) count[A]*count[B]的累加和即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int vis[10000001];
int main()
{ int T,cas=0;
ll n,a,i,j;
scanf("%d",&T);
while(T--)
{
ll ma=0;
memset(vis,0,sizeof(vis));
scanf("%lld",&n);
for(i=0;i<n;i++)
{
scanf("%lld",&a);
vis[a]++;
ma=max(ma,a);
}
printf("Test case #%d: ",++cas);
ll ans=0; //0是所有数的倍数，所有数都是1的倍数
ans=(ll)vis[0]*(n-vis[0])+(ll)vis[1]*(n-vis[0]-vis[1]); //循环找出所有的倍数关系
for(i=2;i<=ma/2;i++)
{
if(vis[i])
{
for(j=i+i;j<=ma;j+=i)
if(vis[j])ans+=(ll)vis[i]*(ll)vis[j];
}
}
printf("%lld\n\n",ans); }
}
I.Lineup the Dominoes
动态规划。dp[mask][last][orientation]，表示使用mask指示的子数组，以第last个多米诺骨牌为结尾的合法排列的方法，orientation多米诺骨牌的状态，0表示原来的方向，1表示翻转。如果mask使用二进制表示为01010101，表示使用第0,2,4,6个多米诺骨牌排列而成，即二进制的每一位代表原数组的一个位置，1代表使用这个位置上的数组，0代表不使用。
如果i和last都是原来的方向：
dp[mask][last][0] =sum
(dp[mask][last][0],dp[premask][i][0])。
如果i是翻转的，last是原来的方向：
dp[mask][last][0] =sum
(dp[mask][last][0],dp[premask][i][1])。
如果i是原来的方向，last是翻转的方向：
dp[mask][last][1] =sum (dp[mask][last][1],dp[premask][i][0])。
如果i和last都是翻转的方向：
dp[mask][last][1] =sum (dp[mask][last][1],dp[premask][i][1])。
last表示mask所代表的的子集合法排列的最后一个骨牌，premask是mask除去第last个骨牌之后的子集，i表示premask所代表的的子集合法排列的最后一个骨牌。最后只要将所有dp[1<<n-1][i][0]和dp[1<<n-1][i][1]累加所得即可（当s[i]==t[i]时不用加dp[1<<n-1][i][1]）。
特殊情况——如果所有的多米诺骨牌都是一样的，那么所有的顺序都是有效的，即全排列。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
int s[20],t[20];
ll p[25];
ll dp[70000][20][2];
int main()
{ int T,i,mask,last,n;
p[0]=1;
for(i=1;i<=20;i++)p[i]=p[i-1]*i%mod;
scanf("%d",&T);
while(T--)
{
int fl=0;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d%d",&s[i],&t[i]);
for(i=1;i<n;i++)
if((s[i]==s[0]&&t[i]==t[0])||(s[i]==t[0]&&t[i]==s[0])){}
else {fl=1;break;} // 特殊情况——如果所有的多米诺骨牌都是一样的，那么所有的顺序都是有效的。
if(fl==0)
{
printf("%lld\n",p[n]);
continue;
} memset(dp,0,sizeof dp); //初始化，表示每个骨牌都有一个初始状态
for(i=0;i<n;i++)
dp[1<<i][i][0]=dp[1<<i][i][1]=1; for(mask=3;mask<(1<<n);mask++)
{
for(last=0;last<n;last++)
{
if((mask&(1<<last))==0)continue;
int premask=mask-(1<<last); for(i=0;i<n;i++)
{
if((premask&(1<<i))==0)continue; //i和last都是原来的方向
if(t[i]==s[last])
dp[mask][last][0] = (dp[mask][last][0]+dp[premask][i][0])%mod;
//i是翻转的，last是原来的方向
else if(s[i]==s[last])
dp[mask][last][0] = (dp[mask][last][0]+dp[premask][i][1])%mod; //i是原来的方向，last是翻转的方向
if(t[i]==t[last])
dp[mask][last][1] = (dp[mask][last][1]+dp[premask][i][0])%mod;
//i和last都是翻转的方向
else if(s[i]==t[last])
dp[mask][last][1] = (dp[mask][last][1]+dp[premask][i][1])%mod;
}
}
} //计算所有可能的情况
ll ans=0;
for(i=0;i<n;i++)
{
ans=(ans+dp[(1<<n)-1][i][0])%mod;
if(s[i]!=t[i])//特殊情况不再统计
ans=(ans+dp[(1<<n)-1][i][1])%mod;
}
printf("%lld\n",ans);
}
}
J.Rising Tides
显然我们要采用二分的方法来寻找答案，给定一个高度如果能确定在这个高度时是否可以安全到达终点，那我们就可以很快二分出最大可行的高度。在判断一个高度是否可行时，搜索从起点开始，在限制的高度下所有可以到达的坐标位置，检验是否经过终点即可。
#include<bits/stdc++.h>
using namespace std;
int t,n,m,a[511][511];
int dr[4]={1,0,-1,0};
int dc[4]={0,1,0,-1};
int inf = 1000000000;
bool visited[511][511];
bool check(int height)//检查当前高度是否能到达终点
{
for(int i=0;i<n;i++)//将所有点设置成未访问过
for(int j=0;j<m;j++)
visited[i][j]=0;
queue <int> q;
q.push(0);
q.push(0);
q.push(0);
visited[0][0]=1;
while(q.size()>0)
{
int row=q.front();//用队列记录行列坐标和当前的高度
q.pop();
int col=q.front();
q.pop();
int dist =q.front();
q.pop();
if(a[row][col]-dist>=height)
{
if(row==n-1&&col==m-1)//如果可以到达终点则返回true
{
return 1;
}
for(int i = 0; i < 4; i++)//否则往四个方向上尝试
{
int nr = row + dr[i];
int nc = col + dc[i]; if(nr>=0&&nr<n&&nc>=0&&nc<m&&!visited[nr][nc])//当位置没有超出范围并且没有访问过时说明下个点可行 压入队列
{
visited[nr][nc] = 1;
q.push(nr);
q.push(nc);
q.push(dist + 1);
}
}
}
}
return 0;
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
scanf("%d",&a[i][j]);
int low=0,high=inf;//二分法查找答案
while(low < high)
{
int mid=(low+high+1)/2;
if(check(mid))
low = mid;
else
high = mid - 1;
}
if(low>0)
printf("%d\n",low);
else
printf("impossible\n"); }
return 0;
}
K.Bouncing Bunnies
Connie和Ronnie可以在 |TA - TB|=|HA - HB|的山峰之间跳跃，可以转化为可以在TA - HA= TB - HB或TA + HA=TB + HB之间的山峰跳跃，构建一个图，节点是(T + H)的值和(T - H)的值(每个不同的值对应一个节点)，将山丘视为其和(T + H)值与差(T - H)值之间的边，运行宽度优先搜索(或其他最短路径算法)，从第一个山的和和差值开始，当我们到达最后一座山的和或差值时，我们离最后一座山只有一跳，所以答案是1 + min(最后一个和的最短路径，最后一个差的最短路径)。
#include<bits/stdc++.h>
using namespace std;
const int INF=987654321;
const int MAXN=500005;
int t[500005],h[500005];
struct qnode
{
int v;
int c;
qnode(int _v=0,int _c=0):v(_v),c(_c){}
bool operator <(const qnode &r)const
{
return c>r.c;
}
};
struct Edge
{
int v,cost;
Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}
};
vector<Edge>E[MAXN];
bool vis[MAXN];
int dist[MAXN];
void Dijkstra(int n,int start1,int start2)//最短路，初始化到点start1和点start2的距离为0
{
memset(vis,false,sizeof(vis));
for(int i=1;i<=n;i++)dist[i]=INF;
priority_queue<qnode>que;
while(!que.empty())que.pop();
dist[start1]=0;
que.push(qnode(start1,0));
dist[start2]=0;
que.push(qnode(start2,0));
qnode tmp;
while(!que.empty())
{
tmp=que.top();que.pop();
int u=tmp.v;
if(vis[u])continue;
vis[u]=true;
for(int i=0;i<E[u].size();i++)
{
int v=E[tmp.v][i].v;
int cost=E[u][i].cost;
if(!vis[v]&&dist[v]>dist[u]+cost)
{
dist[v]=dist[u]+cost;
que.push(qnode(v,dist[v]));
}
}
}
}
void addedge(int u,int v,int w)//加边
{
E[u].push_back(Edge(v,w));
}
int main()
{
int n,m,i,u,v,w,T;
int kk=0;
scanf("%d",&T);
while(T--)
{
map<int,int>mp;
m=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&t[i]);
for(int i=1;i<=n;i++)
scanf("%d",&h[i]);
for(int i=1;i<=n;i++)//给所有不同的T+H和T-H加序号
{
if(mp[t[i]+h[i]]==0)
mp[t[i]+h[i]]=++m;
if(mp[t[i]-h[i]]==0)
mp[t[i]-h[i]]=++m;
}
for(int i=1;i<=m;i++)E[i].clear();
for(int i=1;i<=n;i++)//给每一个山的T+H和T-H值对应的点加边
{
addedge(mp[t[i]+h[i]],mp[t[i]-h[i]],1);
addedge(mp[t[i]-h[i]],mp[t[i]+h[i]],1);
}
Dijkstra(m,mp[t[1]+h[1]],mp[t[1]-h[1]]);
int ans=min(dist[mp[t[n]+h[n]]],dist[mp[t[n]-h[n]]]);//选取到最后一座山的T-H和T+H中较小的距离
if(ans>=987654321)
printf("Field #%d: -1\n\n",++kk);//跳不到最后一座山
else
printf("Field #%d: %d\n\n",++kk,ans+1);//加1跳到最后一座山
}
}
最新文章
- 设计向 20款优秀免费的Icons图标合集 (转)
- HIVE 创建外部分区表--利用HUE不能创建外部表
- iOS解析JSON字符串报错Error Domain=NSCocoaErrorDomain Code=3840 "Invalid escape sequence around character 586."
- Linux下使用popen()执行shell命令
- 动态SQL语句：定义（一）
- JavaScript 基本语法 -- 数据类型 & 变量
- 局域网下访问其他计算机搭建的django网页
- 部署Chart应用并使用.net core读取Kubernetes中的configMap
- 文件实时同步（rsync+inotify）
- 微信小程序之回调函数
- JavaScript面向对象之创建类和方法
- GENIL_BOL_BROWSER 中显示的Object Name 是root object的名字
- split与re.split/捕获分组和非捕获分组/startswith和endswith和fnmatch/finditer 笔记
- MWeb 生成静态网站&博客
- 解决maven项目 maven install失败 错误 Failed to execute goal org.apache.maven.plugins
- Linux博客系统服务器搭建
- smart基础
- Apache2.4.34 + php 7.28 + MySQL8.0.12 安装及配置
- CSS的flex布局(转载)
- Velodyne线性激光雷达pcap文件格式及写入、数据解析 Lebal：激光雷达