Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

终于AC了。一次CE一次WA。(附代妈)

Posted by KatrineYang at 2016-07-08 21:38:06 on Problem 1058
CE是忘记include string了。
//============================================================================
// Name        : main1058.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <vector>
#include <string>
#include <set>
using namespace std;
bool state[16][16] = {false};

bool ok(int i1, int i2, int i3, int i4){
	return !state[i1][i2] && !state[i1][i3] && !state[i1][i4] && !state[i2][i3] && !state[i2][i4] && !state[i3][i4];
}

bool ok(string s[]){
	for(int i = 0; i < 8; i++){
		if(s[i].length() != 4) return false;
	}
	set<int> chong1, chong2;
	for(int i = 0; i < 4; i++){
		for(int j = 0; j < 4; j++){
			chong1.insert(s[i][j]-'A');
		}
	}
	for(int i = 4; i < 8; i++){
		for(int j = 0; j < 4; j++){
			chong2.insert(s[i][j]-'A');
		}
	}
	return chong1.size()==16 && chong2.size()==16;
}

void setTrue(int i1, int i2, int i3, int i4){
	state[i1][i2] = true;
	state[i1][i3] = true;
	state[i1][i4] = true;
	state[i2][i3] = true;
	state[i2][i4] = true;
	state[i3][i4] = true;
	state[i2][i1] = true;
	state[i3][i1] = true;
	state[i4][i1] = true;
	state[i3][i2] = true;
	state[i4][i2] = true;
	state[i4][i3] = true;
}

void setFalse(int i1, int i2, int i3, int i4){
	state[i1][i2] = false;
	state[i1][i3] = false;
	state[i1][i4] = false;
	state[i2][i3] = false;
	state[i2][i4] = false;
	state[i3][i4] = false;
	state[i2][i1] = false;
	state[i3][i1] = false;
	state[i4][i1] = false;
	state[i3][i2] = false;
	state[i4][i2] = false;
	state[i4][i3] = false;
}

string getStr(int i1, int i2, int i3, int i4){
	string res = "";
	res += (char)(i1+'A');
	res += (char)(i2+'A');
	res += (char)(i3+'A');
	res += (char)(i4+'A');
	return res;
}

string getStr(int i){
	string res = "";
	res += (char)(i+'A');
	for(int j = 0; j < 16; j++){
		if(!state[i][j]){
			res += (char)(j+'A');
		}
	}
	return res;
}

int main() {
	string stemp;
	while(cin >> stemp){
	for(int i = 0; i < 16; i++){
		for(int j = 0; j < 16; j++){
			state[i][j] = false;
		}
	}
	vector<string> res;
	for(int i = 0; i < 16; i++) state[i][i] = true;
	for(int i = 0; i < 12; i++){
		string temp;
		if(i != 0) cin >> temp;
		else temp = stemp;
		res.push_back(temp);
		for(int j = 0; j < 3; j++){
			for(int k = j+1; k < 4; k++){
				state[temp[j]-'A'][temp[k]-'A'] = true;
				state[temp[k]-'A'][temp[j]-'A'] = true;
			}
		}
	}
	/*
	for(int i = 0; i < 16; i++){
		for(int j = 0; j < 16; j++){
			if(!state[i][j]) cout << (char)(j+'A') << " ";
		}
		cout << endl;
	}
	*/
	int mk;
	for(int i = 1; i < 16; i++){
		if(!state[0][i]){
			mk = i;
			break;
		}
	}
	//cout << (char)(mk+'A') << endl;
	//bool ok = false;
	for(int i = mk+1; i < 15; i++){
		for(int j = i+1; j < 16; j++){
			if(!ok(0, mk, i, j)) continue;
			setTrue(0, mk, i, j);
			int temp[3];
			int cnt = 0;
			for(int k = 1; k < 16; k++){
				if(!state[0][k]){
					temp[cnt] = k;
					cnt++;
				}
			}
			if(!ok(0, temp[0], temp[1], temp[2])){
				setFalse(0, mk, i, j);
				continue;
			}
			setTrue(0, temp[0], temp[1], temp[2]);
			string s[8];
			s[0] = getStr(0, mk, i, j);
			s[4] = getStr(0, temp[0], temp[1], temp[2]);
			s[1] = getStr(temp[0]); s[2] = getStr(temp[1]); s[3] = getStr(temp[2]);
			s[5] = getStr(mk); s[6] = getStr(i); s[7] = getStr(j);
			//for(int ii = 0; ii < 8; ii++) cout << s[ii] << " ";
			//cout << endl;
			if(ok(s)){
				for(int k = 0; k < 12; k++){
					cout << res[k];
					if(k%4 == 3) cout << endl;
					else cout << " ";
				}
				for(int k = 0; k < 8; k++){
					cout << s[k];
					if(k%4 == 3) cout << endl;
					else cout << " ";
				}
				goto rubbish;
			}
			setFalse(0, temp[0], temp[1], temp[2]);
			setFalse(0, mk, i, j);
		}
	}
	cout << "It is not possible to complete this schedule." << endl;
	rubbish:
	continue;
	}
	//cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!!
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator