记 7.24 阿里巴巴机试题

题一
 

题目：

吃烧饼大赛。有n个盘子，每个盘子内有s[i]个烧饼。每次选取一个 x（1≤x≤n），可以吃到1 ～ x 号盘子里的一个烧饼。若这1～x个盘子中有空盘时无法进行该操作。

假设小明的食量是无限大，最多可以吃掉多少烧饼。

其实这题主要是n和s[i]的范围都很大，忘记用long类型了（用int会不够用），所以只ac了一部分。

思路：

    对每个盘子，最多可吃的数量为：它和它前面的盘子中最少的烧饼数。

用一个变量cur记录到目前盘子为止最少的烧饼数即可。时间复杂度O(n)

代码：

int main(){
    int n = 0;
    cin >> n;
    vector<int> nums(n, 0);
    int min_num = INT_MAX;
    long long ans = 0;
    for(int i = 0; i < n; i++){
        scanf("%d",&nums[i]);
        if (nums[i] < min_num){
            min_num = nums[i];
        }
        ans += min_num;
    }
    cout << ans << endl;
    return 0;
}

题二

题目：
 

开关灯。N行L列的灯，有L个开关，第i个开关Li可以控制第i列，打开该开关使得该列灯状态反转。

行之间可以任意交换，问给定初始灯状态s和目标灯状态t，能否从初始变到目标状态，如果能，最少要打开几个开关。

输入
第一行有一个整数T，表示有多少组测试数据。
每组测试数据包含三行。第一行为两个整数n, L。
每组数据的第二行为n个长度为L的0/1字符串，依次描述起初每行的灯的开关状态。第i个字符串的第j个字符若是’1’，表示对应位置的灯是亮的；’0’表示是灭的。
每组数据的第三行为n个长度为L的0/1字符串，描述主办方希望达到的所有灯的开关状态。格式同上。

输出
输出T行，依次为每组测试数据的答案。如果不可能达到，输出”Impossible”；否则输出最少按多少次开关。

样例输入
3
3 2
01 11 10
11 00 10
2 3
101 111
010 001
2 2
01 10
10 01

样例输出
1
Impossible
0

样例解释
第一组测试数据，按第222列开关，得到 000000 , 101010 , 111111，然后依次交换后两行和前两行即可。
第二组测试数据，可以证明不可能达到要求的方案。
第三组测试数据，只需交换两行即可。

数据范围
40% 的数据：1<=N, L<=10.
100% 的数据：1<=N<=150，1<=L<=50，1<=T<=4.

这题我完全没思路

参考了网上的思路：二进制的做法，利用异或的操作来判断。

我们可以先求出每一行的1/0数组换成十进制是多少（用long long来存），然后我们先枚举原来数组的第一行用最后对应第几行，然后异或出它们的值。这个值就是有哪些不同的地方，即若这个数在二进制下的第i位是1则表示第i列要按。
那我们就对于每一次枚举，就再枚举剩下的数，将它们配对。若不能配对，则这样按不行。若能配对，则找出能配对中所要按次数最少的那一次，就是答案了。
 

以下是参考网上的解答：

#include<cstdio>
#include<cstring>
#include<iostream>
#define ll long long

using namespace std;

ll T, n, l, a[151], b[151], ans;
bool in[151];
char c;

ll getnum(ll x) {//得到二进制
	if (!x) return 1;
	ll sum = getnum(x / 2);
	if (x % 2 == 0) return sum * sum;
	return sum * sum * 2;
}

ll getans(ll x) {//得到要按的个数
	ll sum = 0;
	while (x) {
		if (x % 2 == 1) sum++;
		x /= 2;
	}
	return sum;
}

int main() {
	scanf("%d", &T);//读入
	
	for (int t = 1; t <= T; t++) {
		memset(a, 0, sizeof(a));//初始化
		memset(b, 0, sizeof(b));
		ans = 2147483647;
		
		scanf("%lld %lld", &n, &l);
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= l; j++) {
				c = getchar();
				while (c != '1' && c != '0') c = getchar();
				if (c == '1') a[i] += getnum(l - j);//用二进制存
			}
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= l; j++) {
				c = getchar();
				while (c != '1' && c != '0') c = getchar();
				if (c == '1') b[i] += getnum(l - j);//这个也是用二进制存
			}
		
		for (int i = 1; i <= n; i++) {//找和谁匹配
			bool yes = 0;
			ll dif = a[1] ^ b[i];//异或
			memset(in, 0, sizeof(in));
			in[i] = 1;
			
			for (int j = 2; j <= n; j++) {
				yes = 1;
				for (int k = 1; k <= n; k++)
					if (!in[k] && (ll)(a[j] ^ b[k]) == dif) {//配对
						yes = 0;
						in[k] = 1;
						break;
					}
				if (yes) break;//没得配对
			}
			if (yes) continue;
			
			ans = min(ans, getans(dif));//求出最少要按多少次
		}
		
		if (ans == 2147483647) printf("Impossible\n");//一定按不出来
			else printf("%lld\n", ans);//输出
	}
	
	return 0;
}