Задача на 250 баллов
Условие: http://www.topcoder.com/stat?c=problem_ … p;rd=13694
Дана матрица единиц и нулей (vector <string>) Размер 50х50.
И К (до 1000) - количество переключений. Переключение заключается в инвертировании всех элементов любого столбца. Нужно определить,
какое максимальное количество строк, состоящих только из единиц после ровно К переключений.
Пример:
01
10
10
К = 173
Ответ: 2
Решение
Строка может попасть в ответ, если количество нулей в ней <= К и имеет одинаковую с К чётность.
Для каждой подходящей под это условие строки нужно посчитать, сколько раз она встречается в векторе и вернуть максимальное количество.
Моя реализация:
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
#define VS vector <string>
map <string, int> nm;
map <string, int> ke;
void fnd(VS &vs){
int key=0;
int num=1;
for(int i=0;i<vs.size();++i){
for(int j=0;j<vs[i].size();++j){
if(vs[i][j]=='0')key++;
}
for(int j=i+1;j<vs.size();++j){
if(vs[i]==vs[j]){
num++;
}
}
if(nm[vs[i]]<num){
nm[vs[i]]=num;
ke[vs[i]]=key;
}
key=0;
num=1;
}
}
class LampsGrid {
public:
int mostLit(vector <string>, int);
};
int LampsGrid::mostLit(vector <string> initial, int K) {
fnd(initial);
int ans=0;
for(int i=0;i<initial.size();++i){
if(ke[initial[i]]<=K && (K%2 == ke[initial[i]]%2) ){
if(nm[initial[i]]>ans){
ans=nm[initial[i]];
}
}
}
return ans;
}Задача на 500 баллов
Условие: http://www.topcoder.com/stat?c=problem_ … p;rd=13694
Строка называется "сгруппированная", если между любыми двумя одинаковыми буквами нед буквы другого типа.
Например "aaabbbccc", "hhhffffrtty" , "ab" - "сгруппированные"
"aba", "cbadb" -"несгруппированная"
Дан набор строк. Требуется определить, мог ли он быть получен путём разрезания "сгруппированной" строки на части.
Если мог быть получен из единственной строки - вернуть её.
Если из нескольких - вернуть MANY
Если не мог - IMPOSSIBLE
Решение - жадина 
1) Переместить все простые строки (из одинаковых символов) в начало вектора
2) Циклично проводить объединения строк, пока они возможны. (объединение двух строк возможно, если первый символ одной совпадает с
последним символом второй)
3) Если получилась одна строка, и она "сгруппированная" то вернуть её
4) Если осталось несколько строк и все они "сгруппированные" то вернуть MANY
5) Иначе вернуть IMPOSSIBLE
Эту задачу я решал во время контеста, как показало вскрытие, подвела реализация. Переписал почерпнув идеи с форума топкодера.
Реализация:
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
#define VS vector<string>
void srt(VS &vs){
VS tmp;
for(int i=0;i<vs.size();++i){
if(vs[i][0]==vs[i][vs[i].size()-1]){
tmp.push_back(vs[i]);
}
}
for(int i=0;i<vs.size();++i){
if(vs[i][0]!=vs[i][vs[i].size()-1]){
tmp.push_back(vs[i]);
}
}
vs=tmp;
}
bool good(string &st){
for(int i=0;i<st.size();++i){
for(int j=i+1;j<st.size();++j){
if(st[i]==st[j]){
for(int k=i+1;k<j;++k){
if(st[k]!=st[i])return false;
}
}
}
}
return true;
}
bool join1 (VS &vs){
for(int i=0;i<vs.size();++i){
for(int j=i+1;j<vs.size();++j){
if(vs[i][vs[i].size()-1]==vs[j][0]){
vs[i]+=vs[j];
vs.erase(vs.begin()+j);
return true;
}
}
}
return false;
}
bool join2 (VS &vs){
for(int i=0;i<vs.size();++i){
for(int j=i+1;j<vs.size();++j){
if(vs[j][vs[j].size()-1]==vs[i][0]){
vs[i]=vs[j]+vs[i];
vs.erase(vs.begin()+j);
return true;
}
}
}
return false;
}
bool prov (string &s1, string &s2){
for(int i=0;i<s1.size();++i){
for(int j=0;j<s2.size();++j){
if(s1[i] == s2[j])return false;
}
}
return true;
}
class GroupedWord {
public:
string restore(vector <string>);
};
string GroupedWord::restore(vector <string> parts) {
for(int i=0;i<parts.size();++i){
if(!good(parts[i]))return "IMPOSSIBLE";
}
srt(parts);
while(join1(parts));
while(join2(parts));
for(int i=0;i<parts.size();++i){
if(!good(parts[i]))return "IMPOSSIBLE";
}
if(parts.size()>1){
for(int i=0;i<parts.size();++i){
for(int j=i+1;j<parts.size();++j){
if(!prov(parts[i], parts[j])){
return "IMPOSSIBLE";
}
}
}
return "MANY";
}
if(!good(parts[0]))return "IMPOSSIBLE";
return parts[0];
}