不T就WA不WA也T的优化废物.jpg
- 板块AT_birthday0410_x この問題はほんとうにひどい問題であるため，できれば先に他の問題のほうをお楽しみいただければと思っておりまして，ですので他の問題を通し終えて暇になり，かつその暇を
- 楼主Gralerfics
- 当前回复7
- 已保存回复7
- 发布时间2021/7/9 22:35
- 上次更新2023/11/4 15:11:05
查看原帖
被骇客银狼阻止的越权访问保存失败
不T就WA不WA也T的优化废物.jpg
Java Remote Judge 交不上啊话说 emmm.
import java.io.*;
import java.util.*;
// 坐标类
class position {
int i, j;
position(int i, int j) {
this.i = i;
this.j = j;
}
}
// 图像类
class rect {
int w, h;
ArrayList<ArrayList<Boolean>> data = new ArrayList<>();
}
// 表达式图像
class image extends rect {
// 从控制台读入，并转化为data数组
void inputFromConsole() {
Scanner s = new Scanner(System.in);
s.nextInt();
super.w = s.nextInt();
super.h = s.nextInt();
s.nextLine();
for (int i = 0; i < h; i++) {
String l = s.nextLine();
data.add(new ArrayList<>());
for (int j = 0; j < w; j++) {
data.get(i).add(l.charAt(j) == '#');
}
}
}
// 降噪，返回降噪后的图象
image deNoise() {
image res = new image();
res.w = w;
res.h = h;
for (int i = 0; i < res.h; i++) {
res.data.add(new ArrayList<>());
for (int j = 0; j < res.w; j++) {
res.data.get(i).add(data.get(i).get(j));
}
}
for (int i = 0; i < res.h; i++) {
for (int j = 0; j < res.w; j++) {
if (i == 0 || j == 0 || i == res.h - 1 || j == res.w - 1) {
res.data.get(i).set(j, false);
continue;
}
int _n = 0;
if (this.data.get(i - 1).get(j - 1)) _n++;
if (this.data.get(i - 1).get(j)) _n++;
if (this.data.get(i - 1).get(j + 1)) _n++;
if (this.data.get(i).get(j - 1)) _n++;
if (this.data.get(i).get(j + 1)) _n++;
if (this.data.get(i + 1).get(j - 1)) _n++;
if (this.data.get(i + 1).get(j)) _n++;
if (this.data.get(i + 1).get(j + 1)) _n++;
if (_n == 4) continue;
res.data.get(i).set(j, _n > 4);
}
}
return res;
}
// 分割图像，返回单符号图像数组
ArrayList<ArrayList<Boolean>> flag = new ArrayList<>();
int l, r, t, b, cnt;
void _bfs(position p) {
Queue<position> q = new LinkedList<>();
q.add(p);
while (!q.isEmpty()) {
position now = q.poll();
if (!flag.get(now.i).get(now.j)) continue;
flag.get(now.i).set(now.j, false);
cnt++;
l = Math.min(l, now.j);
r = Math.max(r, now.j);
t = Math.min(t, now.i);
b = Math.max(b, now.i);
if (now.i > 0 && flag.get(now.i - 1).get(now.j)) q.add(new position(now.i - 1, now.j));
if (now.i < h - 1 && flag.get(now.i + 1).get(now.j)) q.add(new position(now.i + 1, now.j));
if (now.j > 0 && flag.get(now.i).get(now.j - 1)) q.add(new position(now.i, now.j - 1));
if (now.j < w - 1 && flag.get(now.i).get(now.j + 1)) q.add(new position(now.i, now.j + 1));
}
}
ArrayList<symbol> divide() {
ArrayList<symbol> res = new ArrayList<>();
final int minSize = 15;
for (int i = 0; i < h; i++) {
flag.add(new ArrayList<>());
for (int j = 0; j < w; j++) {
flag.get(i).add(data.get(i).get(j));
}
}
for (int j = 0; j < w; j++) {
for (int i = 0; i < h; i++) {
if (flag.get(i).get(j)) {
l = 9000;
r = 0;
t = 70;
b = 0;
cnt = 0;
_bfs(new position(i, j));
if (cnt >= minSize) {
res.add(new symbol());
res.get(res.size() - 1).w = r - l + 1;
res.get(res.size() - 1).h = b - t + 1;
for (int _i = t; _i <= b; _i++) {
res.get(res.size() - 1).data.add(new ArrayList<>());
for (int _j = l; _j <= r; _j++) {
res.get(res.size() - 1).data.get(_i - t).add(data.get(_i).get(_j));
}
}
}
}
}
}
return res;
}
}
// 单字符图像
class symbol extends rect {
// 匹配x，返回匹配度。默认两图大小相同，与scale配合使用
int match(symbol x) {
int res = 0;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
res += data.get(i).get(j) == x.data.get(i).get(j)?1:-2;
}
}
return res;
}
// 获取最小图
symbol getMinImage() {
symbol res = new symbol();
int l = 0, r = w - 1, t = 0, b = h - 1;
boolean flag = true;
while (flag) {
for (int i = 0; i < h; i++) {
if (data.get(i).get(l)) {
flag = false;
l--;
break;
}
}
l++;
}
flag = true;
while (flag) {
for (int i = 0; i < h; i++) {
if (data.get(i).get(r)) {
flag = false;
r++;
break;
}
}
r--;
}
flag = true;
while (flag) {
for (int i = 0; i < w; i++) {
if (data.get(t).get(i)) {
flag = false;
t--;
break;
}
}
t++;
}
flag = true;
while (flag) {
for (int i = 0; i < w; i++) {
if (data.get(b).get(i)) {
flag = false;
b++;
break;
}
}
b--;
}
res.w = r - l + 1;
res.h = b - t + 1;
for (int _i = t; _i <= b; _i++) {
res.data.add(new ArrayList<>());
for (int _j = l; _j <= r; _j++) {
res.data.get(_i - t).add(data.get(_i).get(_j));
}
}
return res;
}
// 旋转，左向右为正，中间为0°
symbol rotate(int d) {
symbol res = new symbol();
res.w = w + 70;
res.h = h + 50;
int mx0 = w / 2, my0 = h / 2;
int mx = res.w / 2, my = res.h / 2;
double r = d * Math.PI / 180.0d;
for (int i = 0; i < res.h; i++) {
res.data.add(new ArrayList<>());
for (int j = 0; j < res.w; j++) {
int tx = mx0 + (int)(1.0d * (j - mx) * Math.cos(r) + 1.0d * (i - my) * Math.sin(r));
int ty = my0 + (int)(1.0d * (mx - j) * Math.sin(r) + 1.0d * (i - my) * Math.cos(r));
if (tx < 0 || ty < 0 || tx >= w || ty >= h) {
res.data.get(i).add(false);
} else {
res.data.get(i).add(data.get(ty).get(tx));
}
}
}
return res.getMinImage();
}
// 缩放至指定大小
symbol scale(int i0, int j0) {
symbol res = new symbol();
res.w = j0;
res.h = i0;
for (int i = 0; i < i0; i++) {
res.data.add(new ArrayList<>());
for (int j = 0; j < j0; j++) {
res.data.get(i).add(data.get((int)Math.floor(h * i * 1.0d / i0)).get((int)Math.floor(w * j * 1.0d / j0)));
}
}
return res;
}
}
public class Main {
// 计算表达式
private static boolean isPri(int a, int b) {
// a优先于b则为true，同级或不优先为false
return b == 10 || (a == 14 || a == 15) && (b == 12 || b == 13);
}
private static long calculate(ArrayList<Integer> expr) {
int res;
// 中缀转后缀
ArrayList<Integer> aft = new ArrayList<>();
Stack<Integer> sta = new Stack<>();
for (int peek : expr) {
if (peek >= 0 && peek <= 9) {
aft.add(peek);
} else if (peek == 10) {
sta.push(peek);
} else if (peek == 11) {
int now = sta.pop();
while (now != 10) {
aft.add(now);
now = sta.pop();
}
} else {
while (!sta.isEmpty()) {
int tmp = sta.pop();
if (isPri(peek, tmp)) {
sta.push(tmp);
break;
} else {
aft.add(tmp);
}
}
sta.push(peek);
}
}
while (!sta.isEmpty()) {
aft.add(sta.pop());
}
// 后缀求值
// sta.clear();
for (int peek : aft) {
if (peek >= 0 && peek <= 9) {
sta.push(peek);
} else {
int right = sta.pop();
int left = sta.pop();
switch (peek) {
case 12:
sta.push(left + right);
break;
case 13:
sta.push(left - right);
break;
case 14:
sta.push(left * right);
break;
case 15:
sta.push(left / right);
break;
}
}
}
// 返回结果
res = sta.pop();
return res;
}
// 主函数入口
public static void main(String[] args) {
// 输入（img）
image img = new image();
img.inputFromConsole();
// 预处理（模板最小图）
ArrayList<symbol> minImg = new ArrayList<>();
for (int i = 0; i < 16; i++) {
minImg.add(pattern.getMinImage(i));
}
// 降噪
img = img.deNoise();
// 分割（chars）
ArrayList<symbol> chars = img.divide();
// 遍历字符（多次扰动，取最小图匹配，取最佳者加入expr）
ArrayList<Integer> expr = new ArrayList<>();
for (symbol now : chars) {
int max = Integer.MIN_VALUE;
int maxi = -1;
for (int i = 0; i < 16; i++) {
if (now.h <= 12 && i == 15) continue;
for (int k = -8; k <= 8; k += 8) {
symbol pmt = now.rotate(k);
symbol tmp = pmt.scale(minImg.get(i).h, minImg.get(i).w);
int r = tmp.match(minImg.get(i));
if (r > max) {
max = r;
maxi = i;
}
}
}
expr.add(maxi);
}
// 运算表达式
long ans = calculate(expr);
System.out.println(ans);
}
// 模式字体
private static class pattern {
// 获取n号符号的最小图
static symbol getMinImage(int n) {
symbol res = new symbol();
res.w = 38 - left[n] - right[n];
res.h = height[n];
for (int i = 0; i < height[n]; i++) {
res.data.add(new ArrayList<>());
for (int j = left[n]; j < left[n] + res.w; j++) {
res.data.get(i).add(data[n][i].charAt(j) == '#');
}
}
return res;
}
// 0123456789()+-*/
static final int[] left = new int[] {4, 6, 6, 5, 4, 5, 5, 6, 5, 5, 8, 9, 6, 5, 6, 5};
static final int[] right = new int[] {4, 5, 5, 5, 4, 5, 4, 4, 5, 5, 9, 8, 5, 5, 6, 5};
static final int[] height = new int[] {39,38,38,39,38,38,39,38,39,39,54,54,28,7,26,51};
static final String[][] data = new String[][] {
{
"...............########...............",
".............############.............",
"...........################...........",
"..........##################..........",
".........####################.........",
"........######################........",
".......########################.......",
".......##########....##########.......",
"......#########........#########......",
"......########..........########......",
".....#########..........#########.....",
".....########............########.....",
".....########............########.....",
".....########............########.....",
"....########..............########....",
"....########..............########....",
"....########..............########....",
"....########..............########....",
"....########..............########....",
"....########..............########....",
"....########..............########....",
"....########..............########....",
"....########..............########....",
"....########..............########....",
"....########..............########....",
".....########............########.....",
".....########............########.....",
".....########............########.....",
".....#########..........#########.....",
"......########..........########......",
"......#########........#########......",
".......##########....##########.......",
".......########################.......",
"........######################........",
".........####################.........",
"..........##################..........",
"...........################...........",
".............############.............",
"...............########..............."
},
{
"...................####...............",
".................#######..............",
"..............##########..............",
"...........#############..............",
"........################..............",
".......#################..............",
".......#################..............",
".......#################..............",
".......#################..............",
"........######..########..............",
"........###.....########..............",
"................########..............",
"................########..............",
"................########..............",
"................########..............",
"................########..............",
"................########..............",
"................########..............",
"................########..............",
"................########..............",
"................########..............",
"................########..............",
"................########..............",
"................########..............",
"................########..............",
"................########..............",
"................########..............",
"................########..............",
"................########..............",
"................########..............",
"................########..............",
"................########..............",
".......##########################.....",
"......###########################.....",
"......###########################.....",
"......###########################.....",
"......###########################.....",
".......##########################....."
},
{
"..............#########...............",
"...........##############.............",
"........###################...........",
".......#####################..........",
"......#######################.........",
"......#######################.........",
"......########################........",
"......#########......#########........",
"......#######.........#########.......",
"......#######..........########.......",
"......#######..........########.......",
"......#######..........########.......",
"......#######..........########.......",
".......######..........########.......",
"......................#########.......",
"......................########........",
".....................#########........",
"....................##########........",
"...................##########.........",
"..................###########.........",
".................###########..........",
"................###########...........",
"...............###########............",
"..............###########.............",
".............###########..............",
"............###########...............",
"...........###########.....#####......",
"..........###########.....#######.....",
".........###########......#######.....",
"........###########.......#######.....",
".......###########........#######.....",
"......###########.........#######.....",
".....############################.....",
".....############################.....",
".....############################.....",
".....############################.....",
".....############################.....",
"......###########################....."
},
{
"..............##########..............",
"..........################............",
"........####################..........",
".......######################.........",
".......#######################........",
".......########################.......",
".......########################.......",
".......########.......##########......",
".......#######.........#########......",
".......#######..........########......",
".......#######..........########......",
"........######..........########......",
"........................########......",
"........................########......",
".......................########.......",
"......................#########.......",
"...............###############........",
"..............###############.........",
"..............##############..........",
"..............###############.........",
"..............################........",
"...............################.......",
"......................##########......",
"........................########......",
"........................#########.....",
".........................########.....",
".........................########.....",
".........................########.....",
".........................########.....",
"........................#########.....",
".......###.............##########.....",
"......########........##########......",
"......##########################......",
"......#########################.......",
".....##########################.......",
"......########################........",
"......######################..........",
".........#################............",
"............###########..............."
},
{
".....................#####............",
"....................#######...........",
"...................########...........",
"..................#########...........",
".................##########...........",
"................###########...........",
"................###########...........",
"...............############...........",
"..............#############...........",
".............##############...........",
"............###############...........",
"...........################...........",
"...........########.#######...........",
"..........########..#######...........",
".........########...#######...........",
"........########....#######...........",
".......#########....#######...........",
".......########.....#######...........",
"......########......#######...........",
".....########.......#######...........",
"....##############################....",
"....##############################....",
"....##############################....",
"....##############################....",
"....##############################....",
"....##############################....",
"...................########...........",
"...................########...........",
"...................########...........",
"...................########...........",
"...................########...........",
"...................########...........",
".............####################.....",
"............#####################.....",
"............#####################.....",
"............#####################.....",
"............#####################.....",
".............####################....."
},
{
"........######################........",
"........#######################.......",
"........#######################.......",
"........#######################.......",
"........#######################.......",
"........######################........",
"........#######.......................",
"........#######.......................",
"........#######.......................",
"........#######.......................",
"........#######.......................",
"........#######.......................",
".......########..########.............",
".......####################...........",
".......######################.........",
".......#######################........",
".......########################.......",
".......########################.......",
".......#########################......",
".......########.......##########......",
"..........##...........#########......",
"........................#########.....",
".........................########.....",
".........................########.....",
".........................########.....",
".........................########.....",
".........................########.....",
".........................########.....",
"........#...............#########.....",
".......####............#########......",
"......########.......###########......",
"......##########################......",
"......#########################.......",
".....#########################........",
"......#######################.........",
".......#####################..........",
".........#################............",
".............##########..............."
},
{
".........................######.......",
"....................###########.......",
".................###############......",
"...............#################......",
".............###################......",
"............####################......",
"...........####################.......",
"..........################............",
".........############.................",
"........###########...................",
"........#########.....................",
".......#########......................",
".......########.......................",
"......########........................",
"......########........................",
"......#######....########.............",
"......#######..#############..........",
".....#########################........",
".....##########################.......",
".....###########################......",
".....###########################......",
".....############......##########.....",
".....##########.........#########.....",
".....#########...........#########....",
".....########.............########....",
".....########.............########....",
".....########.............########....",
"......#######.............########....",
"......#######.............########....",
"......########...........#########....",
"......#########.........#########.....",
".......##########.....###########.....",
"........#########################.....",
"........########################......",
".........######################.......",
"..........####################........",
"...........##################.........",
".............##############...........",
"................########.............."
},
{
"......###########################.....",
"......############################....",
"......############################....",
"......############################....",
"......############################....",
"......###########################.....",
"......#######...........#########.....",
"......#######...........#########.....",
"......#######..........#########......",
"......#######..........#########......",
"......#######..........########.......",
"......#######.........#########.......",
"......#######.........########........",
"......#######........#########........",
".......#####.........#########........",
".....................########.........",
"....................#########.........",
"....................########..........",
"...................#########..........",
"...................########...........",
"..................#########...........",
"..................#########...........",
"..................########............",
".................#########............",
".................########.............",
"................#########.............",
"................########..............",
"................########..............",
"...............########...............",
"...............########...............",
"..............#########...............",
"..............########................",
"..............########................",
".............########.................",
".............########.................",
".............#######..................",
".............#######..................",
"...............#####.................."
},
{
"...............#########..............",
".............#############............",
"...........#################..........",
"..........###################.........",
".........#####################........",
"........#######################.......",
"........#######################.......",
"........#########.....#########.......",
".......#########.......#########......",
".......########.........########......",
".......########.........########......",
".......########.........########......",
".......########.........########......",
".......########.........########......",
"........########.......########.......",
"........#########.....#########.......",
".........#####################........",
"..........###################.........",
"...........#################..........",
"...........#################..........",
".........#####################........",
"........#######################.......",
".......#########......##########......",
"......########..........########......",
"......########..........#########.....",
".....########............########.....",
".....########............########.....",
".....########............########.....",
".....########............########.....",
".....#########..........#########.....",
".....#########..........#########.....",
"......##########......##########......",
"......##########################......",
".......########################.......",
".......########################.......",
"........######################........",
".........####################.........",
"...........################...........",
"..............##########.............."
},
{
"..............#########...............",
"............#############.............",
"..........#################...........",
".........###################..........",
"........#####################.........",
".......#######################........",
"......########################........",
"......##########......#########.......",
"......#########........#########......",
".....#########..........########......",
".....########............#######......",
".....########............#######......",
".....########............########.....",
".....########............########.....",
".....########............########.....",
".....#########..........#########.....",
"......########.........##########.....",
"......##########......###########.....",
".......##########################.....",
".......##########################.....",
"........#########################.....",
".........########################.....",
"...........############..########.....",
".............########....#######......",
".........................#######......",
"........................########......",
"........................########......",
".......................########.......",
"......................#########.......",
"....................##########........",
"..................############........",
"..............###############.........",
".........###################..........",
"........###################...........",
"........##################............",
"........################..............",
"........##############................",
"........############..................",
".........######......................."
},
{
".......................####...........",
"......................######..........",
"....................########..........",
"...................##########.........",
"..................###########.........",
".................############.........",
"................############..........",
"...............###########............",
"..............###########.............",
".............###########..............",
".............##########...............",
"............##########................",
"............#########.................",
"...........#########..................",
"...........########...................",
"..........#########...................",
"..........########....................",
".........#########....................",
".........########.....................",
".........########.....................",
".........########.....................",
"........#########.....................",
"........########......................",
"........########......................",
"........########......................",
"........########......................",
"........########......................",
"........########......................",
"........########......................",
"........########......................",
"........########......................",
"........########......................",
".........########.....................",
".........########.....................",
".........########.....................",
".........#########....................",
"..........########....................",
"..........#########...................",
"..........#########...................",
"...........#########..................",
"...........##########.................",
"............#########.................",
".............#########................",
".............##########...............",
"..............###########.............",
"...............###########............",
"................###########...........",
".................############.........",
"..................###########.........",
"...................##########.........",
"....................#########.........",
".....................#######..........",
".......................####...........",
".........................#............"
},
{
"...........####.......................",
"..........######......................",
".........#########....................",
".........##########...................",
".........###########..................",
".........############.................",
"..........############................",
"............###########...............",
".............###########..............",
"..............##########..............",
"...............##########.............",
"................##########............",
".................#########............",
"..................#########...........",
"...................########...........",
"...................#########..........",
"....................########..........",
"....................#########.........",
".....................########.........",
".....................########.........",
".....................########.........",
".....................#########........",
"......................########........",
"......................########........",
"......................########........",
"......................########........",
"......................########........",
"......................########........",
"......................########........",
"......................########........",
"......................########........",
"......................########........",
".....................########.........",
".....................########.........",
".....................########.........",
"....................#########.........",
"....................########..........",
"...................#########..........",
"...................#########..........",
"..................#########...........",
".................##########...........",
"................##########............",
"................#########.............",
"..............###########.............",
".............###########..............",
"............###########...............",
"...........###########................",
".........############.................",
".........###########..................",
".........##########...................",
".........#########....................",
"..........#######.....................",
"...........####.......................",
"............#........................."
},
{
".................#####................",
"................#######...............",
"................#######...............",
"................#######...............",
"................#######...............",
"................#######...............",
"................#######...............",
"................#######...............",
"................#######...............",
"................#######...............",
"......###########################.....",
"......###########################.....",
"......###########################.....",
"......###########################.....",
"......###########################.....",
"......###########################.....",
"......###########################.....",
"................#######...............",
"................#######...............",
"................#######...............",
"................#######...............",
"................#######...............",
"................#######...............",
"................#######...............",
"................#######...............",
"................#######...............",
"................#######...............",
".................#####................"
},
{
"......##########################......",
".....############################.....",
".....############################.....",
".....############################.....",
".....############################.....",
".....############################.....",
"......###########################....."
},
{
".................####.................",
"................######................",
"................#######...............",
"...............########...............",
"...............########...............",
"................#######...............",
"................######................",
".......#####....######.....####.......",
".......######...######...#######......",
"......#########..#####.#########......",
"......###############.##########......",
"......##########################......",
"......##########################......",
".......########################.......",
"............##############............",
"...............########...............",
"..............###########.............",
".............#############............",
"...........########.#######...........",
"..........########..########..........",
"..........########..#########.........",
".........########....########.........",
".........########....########.........",
"..........#######.....#######.........",
"...........#####......######..........",
"............###.........##............"
},
{
"...........................####.......",
"...........................######.....",
"..........................#######.....",
"..........................#######.....",
".........................########.....",
".........................#######......",
"........................########......",
"........................#######.......",
".......................########.......",
".......................#######........",
"......................########........",
"......................#######.........",
".....................########.........",
".....................########.........",
".....................#######..........",
"....................########..........",
"....................#######...........",
"...................########...........",
"...................#######............",
"..................########............",
"..................#######.............",
".................########.............",
".................#######..............",
"................########..............",
"................#######...............",
"...............########...............",
"...............#######................",
"...............#######................",
"..............########................",
"..............#######.................",
".............########.................",
".............#######..................",
"............########..................",
"............#######...................",
"...........########...................",
"...........#######....................",
"..........########....................",
"..........#######.....................",
".........########.....................",
".........#######......................",
"........########......................",
"........########......................",
"........#######.......................",
".......########.......................",
".......#######........................",
"......########........................",
"......#######.........................",
".....########.........................",
".....#######..........................",
"......######..........................",
".......#####.........................."
}
};
}
}
Submission Time 2021-07-09 22:15:10
Task X - この問題はほんとうにひどい問題であるため，できれば先に他の問題のほうをお楽しみいただければと思っておりまして，ですので他の問題を通し終えて暇になり，かつその暇を
User Gralerfics
Language Java (OpenJDK 11.0.6)
Score 222
Code Size 38413 Byte
Status
Exec Time 2208 ms
Memory 72008 KB
混分222 跑了）
加载中...