알 리 바 바 기 시험 문제

문제 1 
제목:
호떡 먹 기 대회.n 개의 접시 가 있 고 접시 마다 s [i] 개의 호떡 이 있 습 니 다.매번 x (1 ≤ x ≤ n) 를 선택 하면 1 ～ x 호 접시 에 있 는 호떡 하 나 를 먹 을 수 있다.이 1 ~ x 개의 접시 에 빈 접시 가 있 을 때 이 조작 을 할 수 없습니다.
샤 오 밍 의 식사량 이 무한 하 다 고 가정 하면 구 운 떡 을 얼마나 먹 을 수 있 습 니까?
사실 이 문 제 는 주로 n 과 s [i] 의 범위 가 매우 넓 어서 log 유형 을 사용 하 는 것 을 잊 어 버 렸 기 때문에 ac 의 일부분 만 사용 했다.
 
생각:
    모든 접시 에 가장 많이 먹 을 수 있 는 수량 은 그것 과 그 앞의 접시 에서 가장 적은 호떡 수 이다.
하나의 변수 cur 로 지금까지 접시 에서 가장 적은 호떡 수 를 기록 하면 됩 니 다.시간 복잡 도 O (n)
코드:

int main(){
    int n = 0;
    cin >> n;
    vector 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;
}

 
 
문제 2
 
제목: 
스위치 를 켜다.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";그렇지 않 으 면 출력 은 최소 몇 번 스위치 를 눌 러 야 합 니까?
샘플 은 332 01 11 00 102 3 101 111 010 001 222 01 10 01 샘플 을 입력 하여 1 조 테스트 데 이 터 를 설명 하고 222 열 스위치 에 따라 000000, 101010, 111111 을 얻 은 다음 두 줄 과 앞 두 줄 을 순서대로 교환 하면 된다.2 조 테스트 데 이 터 는 요구 에 도달 할 수 없 는 방안 을 증명 할 수 있다.3 조 테스트 데 이 터 는 두 줄 만 교환 하면 된다.
데이터 범위 40% 의 데이터: 1 < = N, L < = 10. 100% 의 데이터: 1 < = N < = 150, 1 < = L < = 50, 1 < = T < = 4.
이 문 제 는 나 는 전혀 생각 이 없다.
인터넷 의 사고방식 을 참고 했다. 바 이 너 리 방법 은 다른 조작 을 이용 하여 판단 한다.
우 리 는 먼저 각 줄 의 1 / 0 배열 을 10 진법 으로 바 꾸 는 것 이 얼마 인지 구 할 수 있다. long 저장) 그 다음 에 우 리 는 원래 배열 의 첫 줄 을 마지막 으로 몇 줄 에 대응 한 다음 에 다른 값 을 내 거나 합 니 다.이 값 은 어떤 차이 점 이 있 습 니까? 즉, 이 숫자 가 2 진법 에서 i 위 가 1 이면 i 열 이 눌 러 야 한 다 는 것 을 표시 합 니 다.그러면 우 리 는 매번 매 거 진 것 에 대해 남 은 숫자 를 다시 매 거 하여 그것들 을 맞 추 었 다.만약 짝 을 맞 출 수 없다 면, 이렇게 누 르 면 안 된다.맞 출 수 있다 면 맞 출 수 있 는 횟수 가 가장 적은 것 을 찾 는 것 이 답 이다. 
 
다음은 인터넷 을 참고 한 해답 이다.

#include
#include
#include
#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
");//      
			else printf("%lld
", ans);//  
	}
	
	return 0;
}