codevs 搜索题汇总（黄金级）
众所周知，LOL这款伟大的游戏，有个叫盖伦的英雄。他的伟大之处在于他特别喜欢蹲草丛阴人（XL：蹲草阴人也算英雄？！CZQ：没办法，个个都是这么玩的）。某日，德玛西亚与诺克萨斯之间又发生了一场战斗，嘉文四世希望盖伦能带领一支K人的德玛西亚军队出战。
战斗发生在召唤师峡谷。整个召唤师峡谷被分割成M行N列的一个矩阵，矩阵中有空地和几片草丛。这几片草丛中有些很大、有些很小。一个1×1的草丛能容纳3个士兵，盖伦坚信蹲草偷袭战术能战胜诺克萨斯军队，所以他希望他的军队能全部蹲进草丛里。当然，为了不影响盖伦的作战，盖伦需要单独霸占连起来的一片草丛（不管草丛有多大）。
第一行M、N、K，表示矩阵的行数、列数和士兵数量。
接下来M行，输入矩阵，'.'代表平地，'*'代表草丛。
如果德玛西亚军队和盖伦都能躲进草丛里，则输出“Demacia Win!”，否则输出“Demacia Lose!”
3 3 6
.**
...
.*.
Demacia Win!
1<=m、n<=1500
1<=k<=1500
P.S：这里对于两个1×1的草丛是否连在一起的定义是：对于每个1×1的草从，它与周围（上下左右）的草丛是连在一起的。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int m,n,k;
int a[+][+];
int dis[];
int s[];
int head=,tail=;
int x[+],y[+],qian[+];
int x0[]={,,,,-},y0[]={,,-,,};
int p=;
bool f=false;
void init()
{
scanf("%d%d%d",&m,&n,&k);
getchar();
for(int i=;i<=m;i++)
{
for(int j=;j<=n;j++)
{
char c;
scanf("%c",&c);
if(c=='.') a[i][j]=;
else a[i][j]=;
}
getchar();
}
}
void ss()
{
for(int i=;i<=m;i++)
for(int j=;j<=n;j++)
if(a[i][j]==)
{
p++;
memset(x,,sizeof(x));
memset(y,,sizeof(y));
memset(qian,,sizeof(qian));
head=;
tail=;
qian[]=;
x[]=i;
y[]=j;
a[i][j]=;
dis[p]++;
while(head!=tail)
{
head++;
for(int k=;k<=;k++)
{
int xx=x[head]+x0[k],yy=y[head]+y0[k];
if(a[xx][yy]==)
{
tail++;
x[tail]=xx;
y[tail]=yy;
qian[tail]=head;
a[xx][yy]=;
dis[p]++;
}
}
}
}
}
void sss()
{
sort(dis+,dis+p+);
int q=;
for(int i=;i<=p;i++)
q+=dis[i];
if(*q>=k)
{
f=true;
return;
}
}
int main()
{
init();
ss();
// for(int i=1;i<=p;i++) printf("%d ",dis[i]);
sss();
if(f==true) printf("Demacia Win!\n");
else printf("Demacia Lose!\n");
return ;
}
在一个4*4的棋盘上摆放了14颗棋子，其中有7颗白色棋子，7颗黑色棋子，有两个空白地带，任何一颗黑白棋子都可以向上下左右四个方向移动到相邻的空格，这叫行棋一步，黑白双方交替走棋，任意一方可以先走，如果某个时刻使得任意一种颜色的棋子形成四个一线（包括斜线），这样的状态为目标棋局。
| ● | ○ | ● | |
| ○ | ● | ○ | ● |
| ● | ○ | ● | ○ |
| ○ | ● | ○ |
从文件中读入一个4*4的初始棋局，黑棋子用B表示，白棋子用W表示，空格地带用O表示。
用最少的步数移动到目标棋局的步数。
BWBO
WBWB
BWBW
WBWO
5
hi
#include <iostream>
#include <algorithm>
#include<cstdio> using namespace std; const int dx[]={,,,-},dy[]={,,-,};
int a[][],minn=; void dfs(int x,int y,int num,int yes)
{
int m=;
if(num>=minn) return;
for(int i=;i<=;i++)
{
if (a[i][]==a[i][]&&a[i][]==a[i][]&&a[i][]==a[i][]&&(a[i][]==||a[i][]==))
m=num;
if (a[][i]==a[][i]&&a[][i]==a[][i]&&a[][i]==a[][i]&&(a[][i]==||a[][i]==))
m=num;
}
if (a[][]==a[][]&&a[][]==a[][]&&a[][]==a[][]&&(a[][]==||a[][]==))
m=num;
if (a[][]==a[][]&&a[][]==a[][]&&a[][]==a[][]&&(a[][]==||a[][]==))
m=num;
if (m<minn)
{
minn=m;
return;
}
for(int i=;i>=;i--)
{
int xx=x+dx[i],yy=dy[i]+y;
if(xx>&&xx<&&yy>&&yy<&&yes==a[xx][yy])
{
a[x][y]=a[xx][yy];
a[xx][yy]=;
if(yes==) yes=;
else yes=;
for(int j=;j<=;j++)
for(int k=;k<=;k++)
if(!a[j][k]) dfs(j,k,num+,yes);
if(yes==) yes=;
else yes=;
a[xx][yy]=a[x][y];
a[x][y]=;
}
}
} int main()
{
for(int i=;i<=;i++)
for(int j=;j<=;j++)
{
char tmp;
cin>>tmp;
if (tmp=='W') a[i][j]=;
else if (tmp=='B') a[i][j]=;
}
for(int i=;i<=;i++)
for(int j=;j<=;j++)
if(!a[i][j])
{
dfs(i,j,,);
dfs(i,j,,);
}
printf("%d",minn);
return ;
}
计算乘法时，我们可以添加括号，来改变相乘的顺序，比如计算X1, X2, X3, X4, …, XN的积，可以
(X1(X2(X3(X4(...(XN-1*XN)...)))))
:::
:::
(((...(((X1*X2)X3)X4)...)XN-1)XN)
你的任务是编程求出所有这样的添括号的方案。
输入文件第一行是一个数n（1<=n<=10），表示有n个变量，之后N行每行一个变量的名字。
输出所有的添加括号的方案。注意：单个字符不要加括号，两个字符相乘中间要有乘号。
4
North
South
East
West
(North(South(East*West)))
(North((South*East)West))
((North*South)(East*West))
((North(South*East))West)
(((North*South)East)West)
#include <iostream>
#include <string>
#include <vector> using namespace std; vector<string> ans[][];
string str[];
int n; void dfs(int l,int r)
{
if (ans[l][r].size())
{
return;
}
if (l==r)
{
ans[l][l].push_back(str[l]);
}
else
{
for(int i=l;i<r;i++)
{
dfs(l,i);
dfs(i+,r);
int sl=ans[l][i].size(),
sr=ans[i+][r].size();
for(int j=;j<sl;j++)
{
for(int k=;k<sr;k++)
{
string s;
s="("+ans[l][i][j];
if(r-l==)
{
s+="*";
}
s+=(ans[i+][r][k]+")");
ans[l][r].push_back(s);
}
}
}
}
} int main(int argc, char** argv)
{
cin>>n;
for(int i=;i<=n;i++)
{
cin>>str[i];
}
dfs(,n);
int m=ans[][n].size();
for(int i=;i<m;i++)
{
cout<<ans[][n][i] << endl;
}
return ;
}
Abstinence（戒酒）岛的居民们酷爱一种无酒精啤酒。以前这种啤酒都是从波兰进口，但今年居民们想建一个自己的啤酒厂。岛上所有的城市都坐落在海边，并且由一条沿海岸线的环岛高速路连接。酒厂的投资者收集了关于啤酒需求量的信息，即每天各城市消费的啤酒桶数。另外还知道相邻城市之间的距离。每桶啤酒每英里的运费是1元。日运费是将所需要的啤酒从酒厂运到所有城市所必需的运费之和。日运费的多少和酒厂的选址有关。投资者想找到一个合适的城市来修建酒厂，以使得日运费最小。
请设计一个程序：从文件bre.in 读入城市的数目、相邻两城市间的距离以及每个城市消费的啤酒桶数，计算最小的日运费，将结果写到输出文件bre.out中。
第一行是一个整数n（5 <= n <= 10000） ，表示城市的数目。 城市沿高速路编号，使得相邻的城市的编号也相邻（城市1和n也被认为是相邻）。 以下的n行，每行有两个非负整数。第I+1行的数 zi、di分别是城市I每日的啤酒消费量（桶）和从城市I沿高速路到下一个城市的距离（英里）。高速路的总长不会超过65535 英里。每座城市的日消费量不会超过255桶。
一个整数，表示所需的最小日运费（元）。
6
1 2
2 3
1 2
5 2
1 10
2 3
41
#include<cstdio>
#include<iostream> #define M 20010
#define INF 9223372036854775807LL using namespace std; int a[M],b[M],n;
long long c[M];
int sum=; int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d%d",&a[i],&b[i]);
for(int i=;i<=n;i++)
{
a[i+n]=a[i];
b[i+n]=b[i];
}
for(int i=;i<=n;i++)
sum+=b[i];
for(int i=;i<=n;i++)
{
int t=;
for(int j=i-+n;j>=i+;j--)
{
t+=b[j];
c[i]+=min(t,sum-t)*a[j];
}
}
long long m=INF;
for(int i=;i<=n;i++)
m=min(m,c[i]);
cout<<m;
return ;
}
某同学考试，在N*M的答题卡上写了A,B,C,D四种答案。
他做完了，又不能交，一看表，离打铃还有N久。
他开始玩一个游戏：选一个格子X,Y，从这个格子出发向4个方向找相同的选项，找到的再如此。
求形成的图形的面积。（一个选项占一个单位面积）
N M X Y
答题卡（矩阵）
面积
3 3 1 2
A C B
C C C
D C A
5
N,M<=15.
对于33%数据，只有A。
#include<cstdio>
#include<iostream>
#include<cstring> using namespace std; int n,m,x,y;
int a[][];
int ans;
int dx[]={,,,,-};
int dy[]={,,-,,}; void dfs(int x,int y,int k)
{
ans++;
for(int i=;i<=;i++)
{
int xx=x+dx[i],yy=y+dy[i];
if(a[xx][yy]==k)
{
a[xx][yy]=;
dfs(xx,yy,k);
}
}
} int main()
{
scanf("%d%d%d%d",&n,&m,&x,&y);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
char c;
cin>>c;
switch(c)
{
case 'A':a[i][j]=;break;
case 'B':a[i][j]=;break;
case 'C':a[i][j]=;break;
case 'D':a[i][j]=;break;
}
}
int p=a[x][y];
a[x][y]=;
dfs(x,y,p);
printf("%d",ans);
return ;
}
从1900年1月1日（星期一）开始经过的n年当中，每个月的13号这一天是星期一、星期二、星期三、......、星期日的次数分别是多少？
一行，一个整数（1<=n<=400)
一行7个整数，以空格相隔，（依次是星期一、星期二、星期三、......星期日的次数）
1
1 3 1 2 2 2 1
1<=n<=500
#include<cstdio> int n;
int year;
int a[]; int main()
{
scanf("%d",&year);
for(int i=;i<+year;i++)
for(int j=;j<=;j++)
{
a[(n+)%]+=;
switch(j)
{
case :
case :
case :
case :
case :
case :
case :n+=;break;
case :
if((i%!= && i%==)||(i%== && i%==)) n+=;
else n+=;
break;
default:n+=;break;
}
}
for(int i=;i<;i++)
printf("%d ",a[i]);
printf("%d",a[]);
return ;
}
9月12日是小松的朋友小寒的生日。小松知道小寒特别喜欢蝴蝶，所以决定折蝴蝶作为给小寒的生日礼物。他来到了PK大学最大的一家地下超市，在超市里，小松找到了n种可以用来折纸的本子。每种类型的本子里有若干不同颜色的纸若干张，当然同种类型的本子一定是完全一样的，而不同种类型的本子不一定完全不一样。他统计了一下，这里总共有n种不同类型的可以用来折纸的本子，每种本子各有bi本，所有的纸中有m种颜色是小寒所喜欢的颜色。小松希望他折的每种颜色的蝴蝶的数目是一样的。换句话说，小松必须折m*k只蝴蝶，其中k代表每种颜色蝴蝶的数目，这个数由小松自己来决定。但是小松又不能浪费纸，也就是说他买的本子中，只要是小寒喜欢的颜色的纸都要被折成蝴蝶。于是问题来了，每种类型的本子应该各买多少本，才能折出这m*k只蝴蝶呢？当然，由于小松是个很懒的人，他希望折的蝴蝶数目越少越好，只要表达了心意就可以了（也就是不能1只也不折）。而如果小松总共必须折1000只以上的蝴蝶才能满足要求，那么他就宁愿换一种礼物的方案了。
输入的第一行包含2个整数n（1≤n≤8），m（1≤m≤10）。表示有n种不同类型的本子和m种小寒喜欢的颜色。接下来一个n*m的矩阵。第i行第j列的整数aij表示在第i种类型的本子中包含小寒喜欢的颜色j的纸有aij（1≤aij≤100）张。再接下来的一排n个整数b1到bn，表示每种颜色的本子在超市中有多少本（1≤bi≤5）。
输出包含一个整数，表示小松最少需要折的蝴蝶数目，如果该数目超过1000，则输出”alternative!”。（由于可能存在多种买本子的方案，所以这里就不要求输出具体方案了）
2 3
2 1 2
4 8 4
5 5
36
#include<cstdio>
#include<iostream>
#include<cstring> using namespace std; int n,m,a[][],b[];
int mon[],ans=; void init();
void work(int); int main()
{
init();
work();
if(ans>)
{
printf("alternative!");
return ;
}
else
printf("%d",ans);
return ;
} void init()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("%d",&a[i][j]);
for(int i=;i<=n;i++)
scanf("%d",&b[i]);
} void work(int k)
{
if(k>n)
return;
int pp=;
for(int i=;i<=m;i++)
if(mon[i]>pp)
pp=mon[i];
if(pp*m>ans)
return;
for(int i=;i<=b[k];i++)
{
for(int j=;j<=m;j++)
mon[j]+=(i*a[k][j]);
bool p=false;
for(int s=;s<m;s++)
if(mon[s]!=mon[s+])
p=true;
if(!p&&m*mon[]<ans&&mon[]!=)
{
ans=mon[]*m;
for(int j=;j<=m;j++)
mon[j]-=(i*a[k][j]);
return;
}
work(k+);
for(int j=;j<=m;j++)
mon[j]-=(i*a[k][j]);
}
}
最新文章
- 【转载】给那些想多学习，多进步的Domino初学者
- 如何启动或关闭oracle的归档(ARCHIVELOG)模式
- 网络包处理工具NetBee
- js实现网站导航的二级下拉菜单
- P44、面试题4：替换空格
- Android 内存管理（二）
- Coursera 机器学习笔记（三）
- 关于GPUImage的导入
- 批量运维SQl生成，可以用EXCEl，也可以SQL查询生成
- WPF窗体程序入口 自定义窗体启动页面
- Display Hibernate SQL to console – show_sql , format_sql and use_sql_comments
- 电脑连接树莓派Pi Zero W
- vue 中使用better-scroll 遇到的问题
- Mac 提交代码到Github
- UOJ#172. 【WC2016】论战捆竹竿
- selenium处理table表格
- 数据存储到MySQL并返回新插入的id值
- Python入门笔记——（1）数字与表达式
- 使用 yield生成迭代对象函数
- 第一篇 Postman的初级使用之设置环境快速切换生成环境与测试环境