比赛链接：https://www.nowcoder.com/acm/contest/27#question
A：
小Z的体型实在是太胖了，每次和小D一起出门都跟不上小D的脚步，这让小Z很气馁，于是小Z跋山涉水，仿名山，遍古迹，终于找到了逍遥派。掌门看小Z求师虔诚，决定传小Z一套《凌波微步》。
这种腿法可以无视距离的行进，但缺点是只能走向高处，否则强行发功极易走火入魔。
一天，练习《林波微步》的小Z来到一处练武场，这里从左到右，共有n个木桩，这些木桩有高有低，在这里小Z勤奋的练习着凌波微步，你知道小Z在这处练武场最多能练习多少次么？
#include <bits/stdc++.h>
using namespace std;
int a[100010];
int main(){
int T,n,x,last;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
last=0;
for(int i=1; i<=n; i++) scanf("%d",&a[i]);
sort(a+1, a+n+1);
int ans = 0;
for(int i=1; i<=n; i++){
if(a[i]>last){
ans++;
last=a[i];
}
}
printf("%d\n", ans);
}
}B：
在珠宝店，小Z终于发现一种既便宜又大气的手链。
手链的价格是看手链上的宝石决定的，每一种宝石的价值不一样。
具体规则如下：
宝石A的价值是1、宝石B的价值是2、宝石C的价值是3·····宝石Z的价值是26。
为了防止被销售员虚报价格，小Z决定请你帮忙计算一下手链的价值。
解法：模拟。
#include <bits/stdc++.h>
using namespace std;
char s[100010];
int main(){
int T;
scanf("%d", &T);
while(T--){
scanf("%s", s);
int ans = 0;
int len = strlen(s);
for(int i=0; i<len; i++) ans += s[i]-'A'+1;
printf("%d\n", ans);
}
}#include <bits/stdc++.h>
using namespace std;
int main(){
for(int i=1; i<=9; i++){
for(int j=0; j<=9; j++){
for(int k=0; k<=9; k++){
for(int l=0; l<=9; l++){
printf("%d%d%d%d%d%d%d%d\n",i,j,k,l,l,k,j,i);
}
}
}
}
}D：
小d是一个搞房地产的土豪。每个人经商都有每个人经商的手段，当然人际关系是需要放在首位的。
小d每一个月都需要列出来一个人际关系表，表示他们搞房地产的人的一个人际关系网，但是他的精力有限，对应他只能和能够接触到的人交际。比如1认识2,2认识3，那么1就可以接触3进行交际，当然1和2也可以交际。
小d还很精明，他知道他和谁交际的深获得的利益大，接下来他根据自己的想法又列出来一个利益表，表示他和这些人交际需要耗用多少精力，能够获得的利益值为多少。
小d想知道，他在精力范围内，能够获得的利益值到底是多少。
设定小d自己的编号为1.并且对应一个人的交际次数限定为1.
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10002;
int a[maxn], b[maxn];
int T, n, m, c;
int fa[maxn];
int dp[maxn][502];
int find_set(int x){
if(x==fa[x]) return x;
else return fa[x] = find_set(fa[x]);
}
void union_set(int x, int y){
int fx = find_set(x);
int fy = find_set(y);
if(fx!=fy) fa[fx] = fy;
}
vector <int> v;
int main(){
scanf("%d", &T);
while(T--){
scanf("%d%d%d",&n,&m,&c);
v.clear();
for(int i=1; i<=n; i++) fa[i] = i;
a[1] = 0, b[1] = 0;
for(int i=2; i<=n; i++) scanf("%d%d", &a[i],&b[i]);
for(int i=1; i<=m; i++){
int x, y;
scanf("%d%d", &x,&y);
union_set(x,y);
}
v.push_back(0);
for(int i=1; i<=n; i++){
if(find_set(i)==find_set(1)) v.push_back(i);
}
memset(dp, 0, sizeof(dp));
for(int i=1; i<v.size(); i++){
for(int j=0; j<=c; j++){
dp[i][j] = max(dp[i][j], dp[i-1][j]);
if(j>=a[v[i]]){
dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[v[i]]]+b[v[i]]);
}
}
}
printf("%d\n", dp[v.size()-1][c]);
}
}H：
小d接到了一个布置会场的任务。
他需要将贵宾观众席的椅子排成一排，一共需要N个。
上级领导指示，他只能使用两种椅子。（A类型和B类型）并且假设每种椅子的数量都是无限的。
而其如果想要摆置一个B类型的椅子，对应就需要必须有连续两个一起布置。换句话说，就是如果出现了B类型的椅子，其必须且只有两个连着B类型的椅子。
小d突然想知道对应N个椅子排成一列，他能够有多少种布置的方式.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 1000000007;
struct Matrix{
LL a[2][2];
void init1(){
memset(a, 0, sizeof(a));
}
void init2(){
memset(a, 0, sizeof(a));
a[0][0] = a[1][1] = 1;
}
void init3(){
a[0][0] = a[0][1] = 1;
a[1][0] = 1; a[1][1] = 0;
}
void init4(){
a[0][0] = 2;
a[1][0] = 1;
a[0][1] = 0;
a[1][1] = 0;
}
};
Matrix operator*(const Matrix &a, const Matrix &b){
Matrix res;
res.init1();
for(int i=0; i<2; i++){
for(int j=0; j<2; j++){
for(int k=0; k<2; k++){
res.a[i][j] = (res.a[i][j]+a.a[i][k]*b.a[k][j])%mod;
}
}
}
return res;
}
Matrix qsm(Matrix a, LL n){
Matrix res;
res.init2();
while(n){
if(n&1) res=res*a;
a=a*a;
n>>=1;
}
return res;
}
int main(){
int T;
scanf("%d", &T);
while(T--){
LL n;
scanf("%lld", &n);
Matrix A,B;
A.init3();
B.init4();
if(n==1) printf("1\n");
else if(n==2) printf("2\n");
else{
Matrix res = qsm(A, n-2);
res = res*B;
printf("%lld\n", res.a[0][0]);
}
}
}G：
这是mengxiang000和Tabris来到幼儿园的第四天，幼儿园老师在值班的时候突然发现幼儿园某处发生火灾，而且火势蔓延极快，老师在第一时间就发出了警报，位于幼儿园某处的mengxiang000和Tabris听到了火灾警报声的同时拔腿就跑，不知道两人是否能够逃脱险境？
幼儿园可以看成是一个N*M的图，在图中一共包含以下几种元素：
“.”:表示这是一块空地，是可以随意穿梭的。
“#”：表示这是一块墙，是不可以走到这上边来的，但是可以被火烧毁。
“S”：表示mengxiang000和Tabris所在位子。
“E”：表示幼儿园的出口。
“*”表示火灾发源地（保证输入只有一个火灾发源地）。
已知每秒有火的地方都会向周围八个格子（上下左右、左上、右上、左下、右下）蔓延火势.mengxiang000和Tabris每秒都可以选择周围四个格子（上下左右）进行移动。（假设两人这一秒行动完之后，火势才蔓延开）
解法：简单的BFS，注意细节，预处理每个点被火蔓延到的时间，第二次BFS可以直接判断，注意特判'E'的状态。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 30;
int T,n,m,sx,ex,sy,ey,Fx,Fy;
char maze[maxn][maxn];
bool vis[maxn][maxn];
int dis[maxn][maxn];
const int dir[8][2]={{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;
struct node{
int x,y,step;
};
void bfs1(int x,int y){
queue<P>q;
q.push(P(x,y));
vis[x][y]=1;
while(!q.empty()){
P now=q.front(); q.pop();
for(int i=0;i<8;i++){
int nx=now.first+dir[i][0],ny=now.second+dir[i][1];
if(nx>=0&&nx<n&&ny>=0&&ny<m&&!vis[nx][ny]){
dis[nx][ny]=dis[now.first][now.second]+1;
vis[nx][ny]=1;
q.push(P(nx,ny));
}
}
}
}
void bfs(int x,int y){
queue<node>q;
q.push(node{x,y,0});
vis[x][y]=1;
while(!q.empty()){
node now=q.front(); q.pop();
if(maze[now.x][now.y]=='E'&&now.step<=dis[now.x][now.y]){
printf("%d\n", now.step);
return;
}
for(int i=0;i<4;i++){
node nxt;
nxt.x=now.x+dx[i];
nxt.y=now.y+dy[i];
nxt.step=now.step+1;
if(nxt.x>=0&&nxt.x<n&&nxt.y>=0&&nxt.y<m&&!vis[nxt.x][nxt.y]&&maze[nxt.x][nxt.y]!='*'){
if(maze[nxt.x][nxt.y]=='.'){
if(nxt.step>=dis[nxt.x][nxt.y]) continue;
else{
q.push(node{nxt.x,nxt.y,nxt.step});
vis[nxt.x][nxt.y]=1;
}
}
if(maze[nxt.x][nxt.y]=='E'){
if(nxt.step>dis[nxt.x][nxt.y]) continue;
else{
q.push(node{nxt.x,nxt.y,nxt.step});
vis[nxt.x][nxt.y]=1;
}
}
}
}
}
puts("T_T");
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++){
scanf("%s", maze[i]);
for(int j=0;j<m;j++){
if(maze[i][j]=='*'){
Fx=i,Fy=j;
}
else if(maze[i][j]=='S'){
sx=i,sy=j;
}else if(maze[i][j]=='E'){
ex=i,ey=j;
}
}
}
memset(dis,0,sizeof(dis));
memset(vis,false,sizeof(vis));
bfs1(Fx,Fy);
memset(vis,false,sizeof(vis));
bfs(sx,sy);
}
}F：
双11又到了，小Z依然只是一只单身狗，对此他是如此的苦恼又无可奈何。
为了在这一天脱单小Z决定向女神表白，但性格腼腆的小Z决定隐晦一点，截取一段包含'L'、'O'、'V'、'E'的英文。（顺序不限）
小Z想起之前小D送给他一本英文书，决定在这里面截取一段话，小Z发现有好多种方案来截取这段话。
你能知道小Z能有多少种方案截取这段话么？
为了简化问题，英文文本讲不会出现空格、换行、标点符号及只有大写的情况。
解法：统计贡献，用Two pointers扫一遍。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 100010;
int num[5];
char s[maxn];
unordered_map <char,int> mp;
int main(){
mp['L']=1;
mp['O']=2;
mp['V']=3;
mp['E']=4;
int T;
scanf("%d", &T);
while(T--){
LL ans = 0;
scanf("%s", s);
int len = strlen(s);
memset(num, 0, sizeof(num));
int r=0, cnt=0;
for(int l=0;l<len;l++){
while(cnt!=4&&r!=len){
if(mp[s[r]]!=0){
if(num[mp[s[r]]]==0) cnt++;
num[mp[s[r]]]++;
}
r++;
}
if(r==len&&cnt!=4) break;
ans+=len-r+1;
if(mp[s[l]]!=0){
num[mp[s[l]]]--;
if(num[mp[s[l]]]==0) cnt--;
}
}
printf("%lld\n", ans);
}
}I：
小z放假了，准备到RRR城市旅行，其中这个城市有N个旅游景点。小z时间有限，只能在三个旅行景点进行游玩。小明租了辆车，司机很善良，说咱不计路程，只要你一次性缴费足够，我就带你走遍RRR城。
小z很开心，直接就把钱一次性缴足了。然而小z心机很重，他想选择的路程尽量长。
然而司机也很聪明，他每次从一个点走到另外一个点的时候都走最短路径。
你能帮帮小z吗？
需要保证这三个旅行景点一个作为起点，一个作为中转点一个作为终点。（一共三个景点，并且需要保证这三个景点不能重复）.
解法：预处理每个点到其他店的最短路，枚举3个点的中间点，然后选离它距离最大的两个点的和，取最大即可。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;
const int inf = 0x3f3f3f3f;
typedef pair<int,int> pii;
int head[maxn],edgecnt;
struct edge{
int to,len,next;
}E[maxn*2];
void init(){
memset(head,-1,sizeof(head));
edgecnt=0;
}
void add(int u,int v,int w){
E[edgecnt].to=v,E[edgecnt].next=head[u],E[edgecnt].len=w,head[u]=edgecnt++;
}
int T, n, m;
int dis[maxn][maxn], vis[maxn];
void Dij(int st){
priority_queue <pii,vector<pii>,greater<pii> >q;
dis[st][st]=0;
memset(vis, 0, sizeof(vis));
q.push(make_pair(dis[st][st],st));
while(q.size()){
pii tmp = q.top(); q.pop();
int x=tmp.second;
if(vis[x]) continue;
vis[x]=1;
for(int i=head[x];i+1;i=E[i].next){
int v=E[i].to;
if(dis[st][v]>dis[st][x]+E[i].len){
dis[st][v]=dis[st][x]+E[i].len;
q.push(make_pair(dis[st][v],v));
}
}
}
}
int main(){
scanf("%d", &T);
while(T--){
scanf("%d%d", &n,&m);
init();
memset(dis,inf,sizeof(dis));
for(int i=1;i<=m;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
for(int i=1;i<=n;i++) Dij(i);
int ans=-1;
for(int i=1;i<=n;i++){
int pos1=-1,pos2=-1,maxx=0;
for(int j=1;j<=n;j++){
if(dis[i][j]!=inf&&dis[i][j]>maxx){
maxx=dis[i][j];
pos1=j;
}
}
maxx=0;
for(int j=1;j<=n;j++){
if(j!=pos1&&dis[i][j]!=inf&&dis[i][j]>maxx){
maxx=dis[i][j];
pos2=j;
}
}if(pos1!=-1&&pos2!=-1)
ans = max(ans, dis[pos1][i]+dis[i][pos2]);
}
printf("%d\n",ans);
}
}E：l留坑
京公网安备 11010502036488号