AcWing 5083. 解压缩--运行时间1s以内的写法
原题链接
中等
运行时间1s以内的写法(输出部分本来可以写成函数这样代码更精炼,但是我太懒了,就没这样做)
//202305-3
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int s;//带解压的长度
string input = "";
char output [10000000];
int sout = 0;
int scnt = 0;
int outcnt = 0;
short to_h(char& a){
if(a <='9' && a >= '0'){
return a - '0';
}
else{
return a - 'a' + 10;
}
}
int yindao(){
//y为字符串继续解压的位置
int y = 0;
int st = 0;
int pp = 1;
for(st = 0; st < input.length(); st += 2){
// abcdefg
char a;
a = input[st];
short na;
short nb = to_h(input[st+1]);
//cout << "b = " << input[st+1] << endl;
//cout << "nb = " << nb << endl;
na = to_h(a);
if((na & 8) == 0){
//lens += (((na & 7) << 4) + to_h(input[st+1]))*pp;
//cout << "lens = " << lens << endl;
break;//引导区结束
}
else{
//lens += (((na & 7) << 4) + to_h(input[st+1]) )*pp;
//cout << "lens = " << lens << endl;
pp *= 128;
}
}
y = st + 2;
return y;
}
short check_type(short& nb){
return (nb & 3);
}
void huisu(int& O, int& L){
O *= 2;
L *= 2;
//cout << "outcnt = " << outcnt << endl;
int start = outcnt - O;
if(O >= L){
for(int i = 0; i < L; i++, start++){
cout << output[start];
output[outcnt++] = output[start];
sout++;
if(sout % 16 == 0){
printf("\n");
}
}
}
else{
// O < L,反复输出O个字节
int shang = L/O;
int yushu = L%O;
for(int i = 0; i < shang; i++){
start = outcnt - O;
for(int j = 0; j < O; j++, start++){
cout <<output[start];
output[outcnt++] = output[start];
sout++;
if(sout % 16 == 0){
printf("\n");
}
}
}
start = outcnt - O;
for(int i = 0; i < yushu; i++, start++){
cout <<output[start];
output[outcnt++] = output[start];
sout++;
if(sout % 16 == 0){
printf("\n");
}
}
}
}
int main(){
cin >> s;
int n = s/8;
if(s%8 != 0)
n++;
for(int i = 0; i < n; i++){
string str;
cin >> str;
input += str;
}
scnt = yindao();
//cout << "开始:" << scnt << endl;
while(scnt < input.length()){
char a = input[scnt];
char b = input[scnt+1];
short na, nb;
na = to_h(a);
nb = to_h(b);
short type = check_type(nb);
//cout << "type is : " << type << endl;
//cout << "na,nb = " << na << "," << nb << endl;
if(type == 0){//全是字面量
short ans = 0;
//cout << "na,nb = " << na << "," << nb << endl;
na *= 4;
nb >>= 2;
ans = na + nb;
scnt += 2;
//cout << "高六位为:" << ans << endl;
if(ans < 60){
ans++;
for(int i = 0; i< ans*2; i++, scnt++){
cout <<input[scnt];
output[outcnt++] = input[scnt];
sout++;
if(sout % 16 == 0){
printf("\n");
}
//cout << "output[cnt] = " << output[outcnt-1] << endl;
}
}
else{
ans -= 59;
int true_long = 0;
for(int i = 0; i < ans; i++, scnt += 2){
short na = to_h(input[scnt]);
short nb = to_h(input[scnt+1]);
int tmp = (na<<4) + nb;
for(int j = 0; j < i; j++)
tmp <<= 8;
true_long += tmp;
}
true_long++;
//cout << "true_long = " << true_long << endl;
for(int i = 0; i < true_long*2; i++, scnt++){
cout << input[scnt];
output[outcnt++] = input[scnt];
sout++;
if(sout % 16 == 0){
printf("\n");
}
}
//cout << "input[scnt] :" << input[scnt] << endl;
}
}
else if(type == 1){
int O = 0;
int L = 0;
scnt += 2;
short nc = to_h(input[scnt]);
short nd = to_h(input[scnt+1]);
//short ne = to_h(input[scnt+2]);
//short nf = to_h(input[scnt+3]);
L = (na & 1) << 2;
L += (nb & 12) >> 2;
O = (na & 14) << 7;
O += (nc << 4) + nd;
L += 4;
//cout << "type == 1" << ", O = " << O << "," << "L = " << L << endl;
huisu(O,L);
scnt += 2;
}
else if(type == 2){
int O = 0;
int L = 0;
scnt += 2;
short nc = to_h(input[scnt]);
short nd = to_h(input[scnt+1]);
short ne = to_h(input[scnt+2]);
short nf = to_h(input[scnt+3]);
L = (na << 2);
L += (nb & 12) >> 2;
L += 1;
O = nd;
O += (nc<<4);
O += (nf + (ne <<4)) << 8;
//cout << "type == 2" << ", O = " << O << "," << "L = " << L << endl;
huisu(O,L);
scnt += 4;
}
}
//cout << scnt << endl;
//cout << "outcnt = ";
//cout << outcnt << endl;
//cout << "lens = " << lens << endl;
// for(ll i = 0; i < scnt; i++){
// if(i && i % 16 == 0)
// printf("\n");
// printf("%c", output[i]);
// }
return 0;
}
- 1ms内ac!
- 解压缩.png
光是ac这一道题我就做了近4个小时,难绷,总结了以下几个问题:
- 全局变量局部定义导致永远为0
- O L 搞反
- L忘记 + 4, +1
- 自己想出来的例子都有错,迷惑了自己
- nc nd nf ng:如果使用小端方法,(nf<<4 + ng) << 8最后是移动8位,因为ncnd一共8位(1字节)