组队训练赛问题B
题目描述
You’re probably familiar with regular word searches, where you’re presented with a grid of letters and a word to find. The word can be in a straight line horizontally, vertically, or diagonally (and perhaps backwards in any of those directions). For example, here is a grid of letters:
imgFigure 1: A word search grid The word “JAVA” can be found going from the bottom right corner diagonally upwards.
In a kinky word search the path that spells out the word can have one or more “kinks” – places where the path changes direction. For example, in the given grid you can spell the word “PYTHON” with 3 kinks (one each at the T, H and O):
imgFigure 2: A kinky spelling of “PYTHON”Adding kinks allows letters to be reused – the word “CPLUSPLUS” can be found in the upper right corner of the grid (with 5 kinks). However you cannot stay on a letter twice in a row, so you cannot spell the word “HASKELL” in this grid (though you can find at least 11 more common programming languages). Your task is to see if the spelling of a word with a certain number of kinks is possible or not.
输入
Input begins with a line containing two positive integers r and c (r,c≤10), the number of rows and columns in the grid. After this are r rows of c uppercase characters. Letters are separated by a space. After the grid are two lines: The first line is an integer k, the number of kinks. The second line contains an uppercase word to look for, with maximum length 100.
输出
Output either the word YES if it is possible to spell the given word with exactly k kinks on the grid provided, or NO if it is not.
样例输入
【样例1】
5 5
L M E L C
C A K U P
D O V S Y
R N L A T
P G O H J
0
JAVA
【样例2】
5 5
L M E L C
C A K U P
D O V S Y
R N L A T
P G O H J
3
PYTHON
【样例3】
5 5
L M E L C
C A K U P
D O V S Y
R N L A T
P G O H J
4
PYTHON样例输出
【样例1】
YES
【样例2】
YES
【样例3】
NO题解
DFS+记忆化搜索，其中记忆化需要五个参数，分别为当前位置横坐标，当前位置纵坐标，走到当前位置所需步数，总到当前位置剩余的拐弯次数以及总到当前位置的方向。其中最后一个参数方向是必须的，由于在同一个点方向不同，结果也会不同。记忆化的内容为当前位置经过指定的拐弯次数和方向能否到达终点。
代码
#include <bits/stdc++.h>
using namespace std;
char a[200][200]={0};
char b[2000]={0};
int dy[]={0,-1,-1,-1,0,0,1,1,1};
int dx[]={0,-1,0,1,-1,1,-1,0,1};
int n,m,k;
int vis[21][21][210][210]={0};
int dfs(int x,int y,int sum,int sum1,int last)
{
if(vis[x][y][sum][sum1]==-1)
return 0;
if(sum1>k+1)
return 0;
if(b[sum+1]=='\0'&&sum1==k+1)
{
cout<<"YES"<<endl;
exit(0);
}
for(int i=1;i<=8;i++)
{
int xx=x+dx[i];
int yy=y+dy[i];
if(xx<=0||xx>n||yy<=0||yy>m)
continue;
if(a[xx][yy]==b[sum+1])
dfs(xx,yy,sum+1,sum1+(i!=last),i);
}
vis[x][y][sum][sum1]=-1;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
cin>>k;
cin>>b+1;
if(strlen(b+1)==0)
{
if(k==0)
{
cout<<"YES"<<endl;
}
else
{
cout<<"NO"<<endl;
}
return 0;
}
if(strlen(b+1)<k)
{
cout<<"NO"<<endl;
return 0;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i][j]==b[1]&&strlen(b+1)==1&&k==0)
{
cout<<"YES"<<endl;
exit(0);
}
if(a[i][j]==b[1])
{
dfs(i,j,1,0,0);
}
}
}
cout<<"NO"<<endl;
}个人训练赛问题A
题目描述
LazyLie是一个路痴，不幸的是，他一个人被困在了实验楼里。实验楼的构造复杂，但可以抽象成n个节点，从1到n编号，节点之间有一些单向的道路。LazyLie在1号节点，出口在n号节点。
为了走出实验楼，他采取如下策略，每次选择有路相连的编号最小的节点，并走过去。需要注意的是，即使编号最小的节点的编号，比他目前所在位置的编号大，他仍然会走向那个节点。
wzk为了让LazyLie请他吃饭，决定帮助LazyLie走出实验楼。他可以选择一些道路，用小鸡腿将它堵住。wzk自然非常珍惜小鸡腿，请问wzk至少要堵住多少道路，LazyLie才能成功走出实验楼。
输入
第一行，两个整数n和m，表示n个节点m条单向道路；
之后m行，每行两个整数x和y，表示x到y有一条单向道路；
保证没有重边，没有自环。
输出
输出一行一个整数，表示最少堵住的道路数，无解输出-1。
样例输入
3 3
1 2
2 1
2 3样例输出
1提示
对于60%的数据 n<=50
对于100%的数据 n,m<=200000
题解
BFS搜索得出答案，但是直接BFS用队列时间会超限，可以用优先队列来进行优化。
代码
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
vector<int>v[200500];
struct node
{
int now,val;
bool operator< (const node& a)const
{
return val>a.val;
}
};
priority_queue<node>que;
int dis[200500]={0};
int main()
{
int n,m,from,to;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
dis[i]=inf;
}
for(int i=1;i<=m;i++){
scanf("%d%d",&from,&to);
v[from].push_back(to);
}
for(int i=1;i<=n;i++){
sort(v[i].begin(),v[i].end());
}
dis[1]=0;
que.push({1,0});
while(!que.empty()){
int now=que.top().now;
int val=que.top().val;
que.pop();
if(now==n)
{
printf("%d\n",val);
return 0;
}
for(int j=0;j<v[now].size();j++){
if(dis[v[now][j]]>val+j){
dis[v[now][j]]=val+j;
que.push({v[now][j],dis[v[now][j]]});
}
}
}
printf("-1\n");
}个人训练赛问题B
题目描述
阿Q收到了来自WTY的礼物，一个巨大的棒棒糖。这个棒棒糖是由n个糖果和n-1根短棒连接在一起形成的。糖果从1到n标号。阿Q觉得它太大了不够美观，于是决定拆掉一根短棒，把它分成两个小棒棒糖。 阿Q希望拆开之后，两个小棒棒糖的直径之和最大。 阿Q把棒棒糖的直径定义为最远的两个糖直接的距离。
输入
第一行，一个整数n，表示大棒棒糖有n个糖果； 之后n-1行，每行三个整数x,y,z，表示糖果x与糖果y由长度为z的短棒连接；
输出
一行一个整数，表示直径和的最大值。
样例输入
10
2 1 982
3 1 169
4 1 934
5 1 325
6 1 735
7 1 675
8 2 302
9 3 450
10 5 173样例输出
2668提示
对于30%的数据 N<=2000
对于100%的数据 N<=100000，z<=1000
题解
树的直径问题，采用树形DP来进行维护最大直径，详情请见：
https://blog.csdn.net/weixin_30528371/article/details/101151224
https://blog.csdn.net/qq_42211531/article/details/86579310
代码
#include <bits/stdc++.h>
using namespace std;
struct node
{
int to,val,next;
};
node edge[200500]={0};
int head[200500]={0};
int cnt=0;
int add_edge(int from,int to,int val)
{
edge[++cnt].next=head[from];
edge[cnt].to=to;
edge[cnt].val=val;
head[from]=cnt;
}
int dp[200500][4]={0};
int down[200500]={0};
int up[200500]={0};
int len[200500][3]={0};
int dfs1(int now,int fa)
{
for(int i=head[now];i;i=edge[i].next)
{
int to=edge[i].to,val=edge[i].val;
if(to==fa)
continue;
dfs1(to,now);
int tmp=dp[to][0]+val;
if(tmp>dp[now][0])swap(dp[now][0],tmp);
if(tmp>dp[now][1])swap(dp[now][1],tmp);
if(tmp>dp[now][2])swap(dp[now][2],tmp);
down[now]=max(down[now],down[to]);
}
down[now]=max(down[now],dp[now][0]+dp[now][1]);
}
int dfs2(int now,int fa)
{
for(int i=head[now];i;i=edge[i].next)
{
if(edge[i].to==fa)
continue;
int tem=down[edge[i].to];
if(tem>len[now][0])
swap(tem,len[now][0]);
if(tem>len[now][1])
swap(tem,len[now][1]);
}
for(int i=head[now];i;i=edge[i].next)
{
int to=edge[i].to,val=edge[i].val;
if(to==fa)
continue;
if(dp[now][0]==dp[to][0]+val)
{
dp[to][3]=max(dp[now][1],dp[now][3])+val;
up[to]=max(dp[now][2],dp[now][3])+dp[now][1];
}
else if(dp[now][1]==dp[to][0]+val)
{
dp[to][3]=max(dp[now][0],dp[now][3])+val;
up[to]=max(dp[now][2],dp[now][3])+dp[now][0];
}
else
{
dp[to][3]=max(dp[now][0],dp[now][3])+val;
up[to]=max(dp[now][1],dp[now][3])+dp[now][0];
}
if(len[now][0]==down[to])
up[to]=max(up[to],len[now][1]);
else
up[to]=max(up[to],len[now][0]);
dfs2(to,now);
}
}
int main()
{
int n,from,to,val;
scanf("%d",&n);
for(int i=1;i<=n-1;i++)
{
scanf("%d%d%d",&from,&to,&val);
add_edge(from,to,val);
add_edge(to,from,val);
}
dfs1(1,-1);
dfs2(1,-1);
int ans=0;
for(int i=1;i<=n;i++)
ans=max(ans,up[i]+down[i]);
cout<<ans<<endl;
}
组队训练赛J题
题目描述
Sudoku puzzles come in all different shapes and difficulty levels. Traditionally a Sudoku puzzle is a 9×9 grid. Initially, some of the cells are filled in with numbers and some are empty. The goal is to fill in each cell with a number in the range 1 – 9 subject to the following restrictions:
Each digit 1 – 9 must appear once in each row
Each digit 1 – 9 must appear once in each column
Each digit 1 – 9 must appear once in each 3×3 sub-grid
The difficulty of a Sudoku puzzle can vary widely. The easiest puzzles can be solved with the following two simple techniques:
Single Value Rule:
search for squares which only have one possible value that can be put there.
Unique Location Rule:
within any row, column or sub-grid search for a value that can only be placed in one of the nine locations.
Consider the partially solved Sudoku puzzle shown in Figure 1. The Single Value Rule applies to grid square A7 where 8 is the only value that can be placed there. The Unique Location Rule can be used to put a 5 in square B3 as it is the only location in row 3 where a 5 can be placed.
imgFigure 1: Sample Input 1The easiest Sudoku puzzles can be solved with only these two rules; harder puzzles use techniques like swordfish, x-wings and BUGs.
For this problem you will be given a Sudoku puzzle and must determine if it is an easy puzzle, i.e., whether it can be solved by just using the Single Value and Unique Location rules.
输入
Input consists of a single Sudoku puzzle given over nine lines. Each line contains 9 values in the range 0 to 9, where a 0 indicates a blank in the puzzle.
输出
Output the word Easy followed by the solved Sudoku puzzle if it is an easy puzzle. The puzzle should be printed on nine lines with a single space separating values on a line. If the puzzle is not easy output Not easy followed by as much of the Sudoku puzzle as can be solved using the two rules described above. Use the same format for the partial solution as for the complete solution using a ‘.’ instead of a digit for a unfilled square.
样例输入
【样例1】
2 6 0 5 1 0 3 0 0
3 0 0 0 6 0 0 0 2
0 1 5 0 7 3 9 0 4
0 0 9 0 0 0 5 0 0
0 0 2 6 0 1 4 0 0
0 0 6 0 0 0 7 0 0
6 0 1 9 4 0 2 3 0
9 0 0 0 2 0 0 0 5
0 0 8 0 3 5 0 4 9
【样例2】
0 0 0 0 0 0 7 0 1
0 0 0 0 0 1 2 3 5
0 0 1 8 0 0 0 0 6
0 0 0 0 2 5 0 9 3
9 0 0 0 0 0 0 0 2
3 1 0 6 7 0 0 0 0
2 0 0 0 0 3 8 0 0
1 3 8 9 0 0 0 0 0
4 0 6 0 0 0 0 0 0样例输出
【样例1】
Easy
2 6 4 5 1 9 3 7 8
3 9 7 8 6 4 1 5 2
8 1 5 2 7 3 9 6 4
1 3 9 4 8 7 5 2 6
5 7 2 6 9 1 4 8 3
4 8 6 3 5 2 7 9 1
6 5 1 9 4 8 2 3 7
9 4 3 7 2 6 8 1 5
7 2 8 1 3 5 6 4 9
【样例2】
Not easy
. . 3 . . . 7 8 1
. . . . . 1 2 3 5
. . 1 8 3 . 9 4 6
. . . . 2 5 . 9 3
9 . . 3 . . . 7 2
3 1 2 6 7 9 4 5 8
2 . . . . 3 8 . .
1 3 8 9 . . 5 . .
4 . 6 . . . 3 . .题解
直接根据题意暴力标记模拟即可。
代码
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int a[10][10]= {0};
map<int,int>mp[10][10]; ///表示在i,j点上k是否被使用过
int get_k(int i,int j)
{
if(i<=3&&j<=3)
return 1;
else if(i<=6&&i>3&&j<=3)
return 4;
else if(i<=9&&i>6&&j<=3)
return 7;
else if(i<=3&&j<=6&&j>3)
return 2;
else if(i<=6&&i>3&&j<=6&&j>3)
return 5;
else if(i<=9&&i>6&&j<=6&&j>3)
return 8;
else if(i<=3&&j<=9&&j>6)
return 3;
else if(i<=6&&i>3&&j<=9&&j>6)
return 6;
else if(i<=9&&i>6&&j<=9&&j>6)
return 9;
}
void update()
{
for(int i=1; i<=9; i++)
{
for(int j=1; j<=9; j++)
{
if(a[i][j]!=0)
{
mp[i][j].clear();
continue;
}
for(int ii=1; ii<=9; ii++)
mp[i][j][a[ii][j]]=1;
for(int jj=1; jj<=9; jj++)
mp[i][j][a[i][jj]]=1;
int minj=0,maxj=0,mini=0,maxi=0;
int l=get_k(i,j);
if(l==1||l==4||l==7)
minj=1,maxj=3;
else if(l==2||l==5||l==8)
minj=4,maxj=6;
else if(l==3||l==6||l==9)
minj=7,maxj=9;
if(l==1||l==2||l==3)
mini=1,maxi=3;
else if(l==4||l==5||l==6)
mini=4,maxi=6;
else if(l==7||l==8||l==9)
mini=7,maxi=9;
for(int ii=mini; ii<=maxi; ii++)
for(int jj=minj; jj<=maxj; jj++)
mp[i][j][a[ii][jj]]=1;
}
}
}
int main()
{
for(int i=1; i<=9; i++)
for(int j=1; j<=9; j++)
scanf("%d",&a[i][j]);
update();
while(1)
{
int flagg=0;
for(int i=1; i<=9; i++)
{
for(int j=1; j<=9; j++)
{
if(a[i][j]!=0)
continue;
update();
int tem=-1; ///代表i,j上其他点都不能填，则填该数
for(int k=1; k<=9; k++)
{
if(!mp[i][j][k])
{
if(tem==-1)
tem=k;
else
{
tem=-2;
break;
}
}
}
if(tem!=-1&&tem!=-2)
{
flagg=1;
a[i][j]=tem;
mp[i][j].clear();
continue;
}
for(int k=1; k<=9; k++)
{
if(mp[i][j][k])
continue;
int sum=0; ///判断这一列上其他点能否填该数
for(int ii=1; ii<=9; ii++)
{
if(a[ii][j]!=0)
sum++;
else
sum+=mp[ii][j][k];
}
if(sum==8)
{
flagg=1;
a[i][j]=k;
mp[i][j].clear();
break;
}
sum=0; ///判断这一行上其他点能否填该数
for(int jj=1; jj<=9; jj++)
{
if(a[i][jj]!=0)
sum++;
else
sum+=mp[i][jj][k];
}
if(sum==8)
{
flagg=1;
a[i][j]=k;
mp[i][j].clear();
break;
}
sum=0; ///判断这一块上其他点能否填该数
int minj=0,maxj=0,mini=0,maxi=0;
int l=get_k(i,j);
if(l==1||l==4||l==7)
minj=1,maxj=3;
else if(l==2||l==5||l==8)
minj=4,maxj=6;
else if(l==3||l==6||l==9)
minj=7,maxj=9;
if(l==1||l==2||l==3)
mini=1,maxi=3;
else if(l==4||l==5||l==6)
mini=4,maxi=6;
else if(l==7||l==8||l==9)
mini=7,maxi=9;
for(int ii=mini; ii<=maxi; ii++)
for(int jj=minj; jj<=maxj; jj++)
{
if(a[ii][jj]!=0)
sum++;
else
sum+=mp[ii][jj][k];
}
if(sum==8)
{
flagg=1;
a[i][j]=k;
mp[i][j].clear();
break;
}
}
}
}
if(!flagg)
break;
}
int flag=1;
for(int i=1; i<=9&&flag; i++)
{
for(int j=1; j<=9&&flag; j++)
{
if(a[i][j]==0)
flag=0;
}
}
if(flag)
printf("Easy\n");
else
printf("Not easy\n");
for(int i=1; i<=9; i++)
{
for(int j=1; j<=9; j++)
{
if(a[i][j]==0)
printf(". ");
else
printf("%d ",a[i][j]);
}
printf("\n");
}
return 0;
}