刚刚通关, A级题目的翻译以及我做法的代码在文末. 感兴趣的知友可以去看一看…
————————————-
刚又优化了一下做法, 上传等结果了…
好像除了排行榜以外没有获取自己得分的途径, 而排行榜15分钟才更新一次…让人等得有点难受呢orz…
————————————
唔姆, 出来了…分数确实高了一点…文末代码已更新.
我的做法应该这样就到头了…
除了遍历想不出来更好的做法了…然而遍历的代码又不会写…判断是否有路径什么的简直emmm….orz
————————————
又优化了一下…成功突破2w分大关
把建筑物的四周都空出来的方案改成了根据门口朝向只空出门口和一个侧边的方案.
代码复杂了不止四倍…总共有四百多行. 我只把最能体现核心思路的部分补充到了文末.
—————————————
又又优化了一下…文末代码已更新.
受 @徐亦轲 回答里的思路的启发加上了从大到小依次放置来提高空间利用率.
不过得分还是没有他的高…应该因为是我没有管地图边缘吧.
他在回答里还另外给出了暴力判断是否联通的代码, 目前23591分. 有兴趣的知友们可以去看一下.
可惜我看不懂C++QAQ.
—————————————
以下为原回答
大一萌新
因为下学期准备修java所以这个寒假开始自学java…正好看到这个游戏, 立马就去玩了一下
开始界面有挺精良的2Dlive
进入游戏以后有说明背景设定的OP动画, 第一次打开每个界面也都有说明动画…并且全部可以跳过.
换装也挺好看的…唔姆…
题库很薄, 一共就5道D级, 三道C, 三道B和一道A. 不知道后续会不会更新地图追加活动什么的.
A级我还没仔细看, 不过B级及以下的题是真的挺简单的, 我这种刚学三天java的萌新都能做得出来…当然代码好不好看效率高不高那是另一回事…
不过就游戏界面所展现的信息来说, 她好像对效率完全没有要求, 输入的数据最大也就是1至100这样, 所以无脑写遍历就行了…
比如我昨晚做的高層タワー
就是输入N个单词, 让你把它们首尾顺次相连, 并合并重复的部分.
需要注意的是, 这里重复的部分指的是下一个单词跟前面所有单词合并后得到的单词的重复部分…比如输入paiza apple paizappletter, 输出依旧是paizappletter.
我一开始没注意到这点, 单纯的把相邻的单词两两比较然后输出…本地AC了但传上去老是不对, 弄了好久才发现问题…
这是修改以后传上去终于对了的代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
String[] in = new String[n];
int[] k = new int[n];
int sum=0;
char a[][] = new char[n][];
for (int i = 0; i < n; i++) {
in[i] = input.next();
k[i] = in[i].length();
sum+=k[i];
}
int b[]=new int[sum];
for (int i = 0; i < n; i++) {
a[i] = new char[k[i]];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < k[i]; j++) {
a[i][j] = in[i].charAt(j);
}
}
for (int i = 0; i < k[0]; i++) {
b[i]=a[0][i];
}
int min[]=new int[n-1];
int max=0;
int t=0;
sum=k[0];
for (int i = 0; i < k[0]; i++) {
System.out.print(a[0][i]);
}
for (int i = 0; i < n - 1; i++) {
if(sum<k[i+1]) min[i]=sum;
else min[i]=k[i+1];
for (int j = 0; j < min[i]; j++) {
for (int l = 0; l < j+1; l++) {
if(b[sum-l-1]!= a[i+1][j-l]) t+=1;
}
if(t==0) max=j+1;
t=0;
}
for (int j = 0; max+j<k[i+1] ; j++) {
System.out.printf("%c", a[i+1][max+j]);
b[sum+j]=a[i+1][max+j];
}
sum+=k[i+1];
sum=sum-max;
max=0;
}
System.out.println();
}
}
目前就说这些…等我做完A级以外的题以后一定再来更新.jpg
啊刚说完就有新进展了…
达成度到了50%以后取回的RIN的记忆…交代了RIN在崩坏前的世界里是一个在研究所和IT设施间巡回调查的机器人. 由于E病毒的爆发导致工程师不足, 其他机器人一个接一个出故障倒下, 而我们的RIN是由活着的最后一个工程师亲手操作进入休眠状态才得以幸存的. 现在因为重拾编程的人的活跃行动, RIN再启动了.
紧接着解锁了”伤心”表情.
唔姆, 看来可以期待一下达成度100%以后的ED动画了（
(通关后注: 并没有ED动画QAQ)
把C级及以下问题全部做完, 加上一道B, 达成度到了75%, 解锁了”笑容”表情.
かわええ~
除了A级题以外全部做完了…
确实很简单…没什么说头…
等我做完这道A级题我就去学面向对象.jpg
更新一下A级题目的翻译…萌新已经看懵了..完全不知道怎么做orz
您被委任设计一个新城镇. 该城镇南北纵长为H, 东西横长为W, 面积共计H×W.
建筑物占地为矩形, 并含有一个门. 你要设计一个程序来决定他们的摆放位置. 他们的摆放位置应遵守以下三个原则:
- 任意两个建筑物均不重叠.
- 不可改变建筑物的朝向.(不能旋转)
- 对于任意两个建筑物, 他们的门一定要由在小镇内部且不经过任何建筑物的空白路径相连.
(比如图中的灰色建筑和绿色建筑之间就是符合原则3的, 而灰色建筑和蓝色建筑之间就不符合原则3.)
(接着他给出了原则3的数学表达…没什么意思而且挺啰嗦的, 我就略去不译了.)
每个占地面积为X的建筑物能够产生X万円的利益.
请写一个程序, 给出建筑物的摆放位置, 并尽可能地使建筑物产生的利益总额较大.
只需给出正确放置了至少一个建筑物的方案即可被视为正解. 建筑物的总面积将计为得分.
输入的数据格式如图.
其中H为城镇的南北纵长, W为城镇的东西横长. N为可供放置的建筑物的数目.
h_i表示第i个建筑物的纵长, wi表示其横长. r_i表示门相对于该建筑的横坐标, c_i表示门的纵坐标. 如图所示.
输入数据的限制条件.
只翻译有文字的最后三个条件.
· 坐标(r_i, c_i)一定落在建筑物外围. (即, r_i = 1或r_i = h_i或c_i = 1或c_i = w_i至少有一个成立)
· 坐标(r_i, c_i)不会落在建筑物的四个角落. (即（r_i，c_i）既不是（1,1），也不是（1,1，w_i）,（h_i，1）或（h_i，w_i))
· 可以保证能至少配置一个建筑物.
输出格式.
· 输出一个有H行, 每行包含W个由半角空格字符隔开的整数的点阵.
· 每个整数表示对应的建筑物的编号. 如此处没有建筑物, 则应为0.
· 在最后一行的末尾插入一个新行, 而不包含任何额外字符或空行.
输入输出的范例:
姑且写了一个最最最简单的做法把题给过了…
单纯过题还是很简单的…我是完全放弃考虑门的方向, 直接在每个建筑物周围都留了一圈空来保证门一定能连通的做法…最后加了个补丁保证了即使所有建筑物的长或宽都有跟小镇相同也会放一个面积最大的建筑物上去.
最后把代码放上来给大家看看乐呵乐呵. 如果有知友有更好的算法请务必告知.
(注: 这是19305分的代码. 删去中间将把门在右侧的建筑放到左侧的那一部分以后就是最初的19046分的代码. 20039分的代码在后面. )
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner input=new Scanner(System.in);
int H=input.nextInt();
int W=input.nextInt();//取得小镇的长宽
int N=input.nextInt();//建筑物的个数
int town[][]=new int[H][W];
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
town[i][j]=0;
}
}//初始化小镇
int[] h=new int[N],
w=new int[N],
r=new int[N],
c=new int[N];
int judge=0;//判断用参数
int x[]=new int[N];//位置参数 for h
int y[]=new int[N];//位置参数 for w
for (int i = 0; i < N; i++) {
h[i]=input.nextInt();
w[i]=input.nextInt();
r[i]=input.nextInt();
c[i]=input.nextInt();
x[i]=1;
y[i]=1;
}//取得所有建筑的参数并初始化x和y
int[] h_l=new int[N],
w_l=new int[N];//门在最右侧,将要放于最左侧的建筑物群
int H_l=0;//其竖直总长
for (int i = 0; i < N; i++) {
if(c[i]==w[i] && H_l+h[i]<H ){
H_l+=h[i];
h_l[i]=h[i];
w_l[i]=w[i];
h[i]=0;
w[i]=0;//转移数据
x[i]=0;//将位置坐标移动至最左上
while(x[i]<H) {
for (int j = 0; j < h_l[i]; j++) {
if (x[i] + j< H) {
if (town[x[i] + j][0] != 0) judge += 1;
} else {
judge += 1;
}
}//遍历建筑物即将摆放的竖直方向检查是否有建筑物
if (judge == 0) {
for (int j = 0; j < h_l[i]; j++) {
for (int k = 0; k < w_l[i]; k++) {
town[x[i] + j][k] = i + 1;
}
}//若没有建筑物,则对town坐标赋值并跳出while循环
break;
} else if (x[i] < H) {
x[i] += 1;
judge = 0;//初始化judge
}//若有, 则使x+=1, 继续while循环.
}
x[i]=1;//初始化x[i]
}
}
for (int i = 0; i < N; i++) {
//对编号为i的建筑进行操作
while(x[i]<H&&y[i]<W)
{
for (int j = 0; j < h[i] + 2; j++) {
for (int k = 0; k < w[i] + 2; k++) {
if (x[i] + j -2< H - 1 && y[i] + k -2< W - 1) {
//减1留出地图周边位置
if (town[x[i] + j - 1][y[i] + k - 1] != 0) judge += 1;
} else {
judge += 1;
}
}
}//遍历建筑物即将摆放的位置及其周边检查是否有建筑物
if (judge == 0) {
for (int j = 0; j < h[i]; j++) {
for (int k = 0; k < w[i]; k++) {
town[x[i] + j][y[i] + k] = i + 1;
}
}//若没有建筑物,则对town坐标赋值并跳出while循环
break;
} else if (x[i] < H - 1) {
x[i] += 1;
judge = 0;//初始化judge
} else {
x[i] = 1;
y[i] += 1;
judge = 0;//初始化judge
}//若有, 则改变x和y以遍历坐标, 并循环遍历
}
judge=0;//初始化judge
}//遍历N个建筑物结束
judge=0;//循环结束,初始化judge
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
if(town[i][j]==0) judge+=1;
}
}//判断空白的个数
if(judge==H*W){
int square[]=new int[N];//各建筑的面积
int the_max=0;//最大面积建筑对应的编号
for (int i = 0; i <N; i++) {
square[i]=h[i]*w[i];
if(square[the_max]<=square[i]) the_max=i;
}//计算编号为i的建筑物的面积并找出最大面积的建筑物
for (int i = 0; i < h[the_max]; i++) {
for (int j = 0; j < w[the_max]; j++) {
town[i][j]=the_max+1;
}
}//对town坐标赋值
}//若所有town均为空白, 则找出面积最大的建筑物并放置于town中
for (int i = 0; i < H; i++) {
for (int q = 0; q < W; q++) {
System.out.print(town[i][q]);
if (q!=W-1) System.out.print(" ");
}
System.out.println();
}//输出结果
}
}
以下是222648分的代码的节选. 去掉把建筑从小到大顺次排列的部分就是20039分的代码了.
import java.util.Scanner;
public class Main {
public static void main(String[] args){
//...该部分跟上文代码完全一样,故略去
for (int i = 0; i < N; i++) {
h[i]=input.nextInt();
w[i]=input.nextInt();
r[i]=input.nextInt();
c[i]=input.nextInt();
s[i]=h[i]*w[i];
s_b[i]=s[i];
x[i]=0;
y[i]=0;
}//取得所有建筑的参数并初始化x和y
Arrays.sort(s_b);
for (int i = 0; i < N; i++) {
s_a[i]=s_b[N-1-i];
}
int S[][]=new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
S[i][j]=0;
}
}
for (int n = 0; n < N; n++) {
for (int i = 0; i < N; i++) {
if(s_a[n]==s[i]){
S[n][i]=s[i];
s[i]=0;
break;
}
}
}
for (int n = 0; n < N; n++) {
for (int i = 0; i < N; i++) {
//对编号为i的建筑进行操作
if (S[n][i] != 0) {
while(x[i]<H && y[i]<W)
{ if(r[i]==1) {//门开在上方的情况. 留出上方和右侧
if(x[i]>0 && y[i]>0)
{
if(town[x[i]-1][y[i]-1]>0) judge+=1;
}
if(x[i] +h[i] < H && y[i]+w[i]< W )
{
if (town[x[i]+h[i]][y[i]+w[i]]>0) judge+=1;
}//检查顶角处是否有建筑物
for (int j = -1 ; j < h[i] ; j++) {
for (int k = 0; k < w[i] + 1; k++) {
if (x[i]>0 && x[i] + j < H && y[i] + k < W ) {
if (town[x[i] + j][y[i] + k] != 0) judge += 1;
} else {
judge += 1;
}
}
}//遍历建筑物即将摆放的位置及其周边检查是否有建筑物
for (int j = 0; j < w[i] + 1; j++) {
if(x[i]>0 && x[i]+h[i]-1< H && y[i]+j <W){
if(town[x[i]-1][y[i]+j] == -1){
judge=judge-1;
}
}
}
for (int j = 0; j < h[i]; j++) {
if( x[i]>0 && x[i]+j<H && y[i]+ w[i]<W){
if( town[x[i]+j][y[i]+w[i]] == -1){
judge = judge -1;
}
}
}//排除-1的影响
if (judge == 0) {
for (int j = 0; j < w[i] + 1; j++) {
town[x[i]-1][y[i]+j] = -1;
}
for (int j = 0; j < h[i]; j++) {
town[x[i]+j][y[i]+w[i]] = -1;
}//用-1标记将要空出来的道路
for (int j = 0; j < h[i]; j++) {
for (int k = 0; k < w[i]; k++) {
town[x[i] + j][y[i] + k] = i + 1;
}
}//若没有建筑物,则对town坐标赋值并跳出while循环
break;
} else if (x[i] < H - 1) {
x[i] += 1;
judge = 0;//初始化judge
} else {
x[i] = 0;
y[i] += 1;
judge = 0;//初始化judge
}//若有, 则改变x和y以遍历坐标, 并循环遍历
}else if(...){...}else if(...){...}else if(...){...}
//对门分别开在左右下侧情况的分类讨论.略去..
}
}
judge=0;//初始化judge
}//遍历N个建筑物结束
}
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
if(town[i][j]<0) town[i][j]=0;
}
}//将用-1标记的道路重置为0
//...略去检查空白以防万一的部分
for (int i = 0; i < H; i++) {
for (int q = 0; q < W; q++) {
System.out.print(town[i][q]);
if (q!=W-1) System.out.print(" ");
}
System.out.println();
}//输出结果
}
}
来源：知乎 www.zhihu.com
作者：夏娜
【知乎日报】千万用户的选择，做朋友圈里的新鲜事分享大牛。
点击下载
此问题还有 35 个回答，查看全部。