网安学院编程比赛(2025/3/29)

Not built in a day.

10.ezxor

题目代码实现了一个二进制流加密算法，其核心逻辑分为三个部分：

• 字符到二进制展开
• 差分编码处理
• 输出加密后的二进制流

Crux

• 时间复杂度问题，要识别并根据亦或和的性质算，将O(n^2)=>O(n)
• bit[0]赋值的问题，要识别出密文的最后一位是无用的(x^x=0),但是0亦或1或0对它都没有影响。

这道题我觉得是个错题，因为原文第0位信息丢失了。
eg:cipher[0] = m[0]^m[0] ^ XorSum[m[1~n-1]]
而密文最后一位：cipher[length-1]一定是0，可以说它没携带任何信息，但是它对我们计算也没有影响。

▶

code1

这份代码时间复杂度不合格。

#include<bits/stdc++.h>
using namespace std;
int ini[8];
int d;
void init() {
	ini[0] = 1;
	for (int i = 1; i < 8; i ++ ) {
		ini[i] = ini[i - 1] << 1;
//		cout << ini[i] << " ";
	}
}
int main() {
	string input;
	cin >> input;
	input[input.length()] = 0;
	for(int i = input.length()-1;i >=0;i --)
	{
		bool x = input[i] - '0';
//		cout << x <<endl;
//		break;
//		bool y = input[i+1] - '0';
		for(int j = input.length()-1;j > i ;j --)
		{
			bool y = input[j] - '0';
			x = x ^ y;
//			cout << x << " = " << x << " ^ " << y << endl;
		}
//		x = x ^ y;
		if(x)
		{
			input[i] = '1';
		}else{
			input[i] = '0';
		}
	}
	bool xorsum = 0;
	for(int i = input.length()-1;i > 0 ;i -- )
	{ 
		input[i] = input[i-1];
		xorsum ^= input[i] - '0';
	}
	if(xorsum)
	{
		input[0] = '1';
	}else{
		input[0] = '0';
	}
//	cout << input;
	
	string s = "";
	init();
	int T = input.length() / 8;
	for (int k = 1; k <= T; ++ k) {
		d = 0;
		for (int j = 8 * (k - 1); j < 8 * k; j ++ ) {
			char c = input[j];
			int x = c - '0';
//			cout << x;
			int m = j - 8*(k-1) + 1;
			if (x) {
				d += x*ini[8-m] ;
			}

		}
		s += char(d);
	}
	cout << s ;
	return 0;
}

▶

Wu's-ACcode

这份代码将bit[0]赋值为0了，但实际上不一定是0。
注意这种for循环的方式，简练地将二进制按位权还原成十进制数。

#include<bits/stdc++.h>
using namespace std;
char s[100005]; 
int bit[800005];
int main(){
	scanf("%s",s);
	int len=strlen(s),cnt=0,sum=0; 
	for(int i=len-1;i>0;i--){
		bit[i]=(s[i-1]-'0')^(s[i]-'0'); 
	}
	bit[0]=0;
	for(int i=0;i<len;i+=8){
		int ans=0;
		for(int j=0;j<8;j++){
			ans=ans*2+bit[i+j];
		}
		putchar(char(ans));
	} 
	return 0;
} 

//011000100111110110011001100000100110011110000100010100100101100001001111101100011010001001101010010011100101110110010101101111100110101001000100010000011011001001000110011010100100010001001000010000011011101001010110
//SCUCTF{this_is_a_fake_flag}

Q: 关于 bool 改用 int 的影响?

▶

A

正确性影响

在这题的代码中将bool改为int不会影响结果的正确性，因为：

• C++中bool本质是整型（true=1，false=0），与int兼容
• 仅用于存储二进制0/1时，int完全能表示这两个值。

需注意的边界情况

情况	bool行为	int行为
输入超出0/1	强制截断为true/false	保留原值
编译器优化	可能更高效（如位存储）	标准整型处理

最佳实践

优先bool：当只需表示真假状态时
使用int：当需要：

• 位操作

• 多状态值

• 与C代码交互

7.内存排序

▶

mycode

#include<bits/stdc++.h>
using namespace std;
unsigned int n;
int ini[8];
void init() {
	ini[0] = 1;
	for (int i = 1; i < 8; i ++ ) {
		ini[i] = ini[i - 1] << 1;
//		cout << ini[i] << " ";
	}
}
unsigned int d[4];
int d1,d2,d3,d4;
int main()
{
	init(); 
	scanf("%u",&n);
	for(int i = 1;i <= 8;i ++ )
	{
		if(n & 1)
		{
//			cout << "1" ;
			d[0] += ini[i-1];
		}else{
//			cout << "0" ;
		}
		n >>= 1;
	}
	for(int i = 1;i <= 8;i ++ )
	{
		if(n & 1)
		{
//			cout << "1" ;
			d[1] += ini[i-1];
		}else{
//			cout << "0" ;
		}
		n >>= 1;
	}
	for(int i = 1;i <= 8;i ++ )
	{
		if(n & 1)
		{
//			cout << "1" ;
			d[2] += ini[i-1];
		}else{
//			cout << "0" ;
		}
		n >>= 1;
	}
	
	for(int i = 1;i <= 8;i ++ )
	{
		if(n & 1)
		{
//			cout << "1" ;
			d[3] += ini[i-1];
		}else{
//			cout << "0" ;
		}
		n >>= 1;
	}
	
	sort(d,d+4);
	for(int i = 0;i < 4;++ i)
	{
		cout << d[i] << " ";
	}
	cout << endl;
	unsigned int ans = 0;
	cout << "ans + " << "d[0]        : " << d[0] << endl;
	cout << "ans + " << "(d[1] << 8):  "<< (d[1] << 8) << endl;
	cout << "ans + " << "(d[2] << 16): " << (d[2] << 16) << endl;
	cout << "ans + " << "(d[3] << 24): " << (d[3] << 24) << endl;
	ans += d[3] + (d[2] << 8) + (d[1] << 16) + (d[0] << 24);
	cout << ans ;
	return 0;
}

这样取数太笨了：
Better Solution:

while(t){
	a[++cnt]=t%256;
	t/=256; 
}

小z在CS

注意：998244353是个质数，所以可以用费马小定理求逆元。
费马小定理用快速幂实现。