//初赛第1题
#include <iostream>
#include <cstdio>
#include <utility>
#include <algorithm>
#include <cmath>
using namespace std;
int N, M;
pair<int, int> List[65536];
int main(int argc, char* args[])
{
int I, J, Max, A, B;
if (argc <= 1) return 0;
sscanf(args[1], "%d", &N);
M = 0;
Max = (int)sqrt((double)N) * 2;
for (I = 2; I <= Max; I++)
if (I & 1)
{
if (N % I == 0)
{
J = N / I;
A = J - I / 2;
B = J + I / 2;
if (A >= 1) List[M++] = make_pair(A, B);
}
}
else
{
if (N % I != 0 && N % (I / 2) == 0)
{
J = N / I;
A = J - I / 2 + 1;
B = J + I / 2;
if (A >= 1) List[M++] = make_pair(A, B);
}
}
if (M == 0)
printf("NONE\n");
else
{
sort(List, List + M);
for (I = 0; I < M; I++)
{
printf("%d", List[I].first);
for (J = List[I].first + 1; J <= List[I].second; J++)
printf(" %d", J);
printf("\n");
}
}
return 0;
}
////////////////////////////////////////////////////////////////////////
//初赛第2题
#include <iostream>
#include <cstdio>
#include <utility>
#include <algorithm>
using namespace std;
struct pair_less
{
bool operator()(const pair<int, int>& A, const pair<int, int>& B) const
{
return A.first < B.first;
}
};
int N;
pair<int, int> List[2000000];
int MaxResult;
int main()
{
int I, J, Last, A, B;
freopen("input.txt", "r", stdin);
N = 0;
while (scanf("%d%d", &A, &B) > 0)
{
if (A > B) I = A, A = B, B = I;
List[N] = make_pair(A, B);
N++;
}
sort(List, List + N, pair_less());
Last = 0x80000000;
MaxResult = 0;
for (I = 0; I < N; I++)
{
if (List[I].first <= Last)
{
if (List[I].second <= Last)
J = List[I].second - List[I].first + 1;
else
J = Last - List[I].first + 1;
if (J > MaxResult) MaxResult = J;
}
if (List[I].second > Last) Last = List[I].second;
}
printf("%d\n", MaxResult);
return 0;
}
////////////////////////////////////////////////////////////////////////
//初赛第3题
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
struct word_less
{
bool operator()(const pair<char*, char*>& A, const pair<char*, char*>& B) const
{
return strcmp(A.first, B.first) < 0;
}
};
int N, M;
pair<char*, char*> List[100000];
char Word[100001];
char* get_word()
{
char* P;
int Len;
Len = (int)strlen(Word);
P = new char[Len + 1];
strcpy(P, Word);
return P;
}
int main()
{
freopen("dict.txt", "r", stdin);
N = 0;
while (scanf("%s", Word) > 0)
{
List[N].first = get_word();
scanf("%s", Word);
List[N].second = get_word();
N++;
}
stable_sort(List, List + N, word_less());
freopen("text.txt", "r", stdin);
M = 0;
while (scanf("%s", Word) > 0)
{
if (M > 0) printf(" ");
M++;
pair<char*, char*>* It = upper_bound(List, List + N, make_pair((char*)Word,(char*) 0), word_less());
if (It > List && strcmp(It[-1].first, Word) == 0)
printf("%s", It[-1].second);
else
printf("%s", Word);
}
printf("\n");
return 0;
}
////////////////////////////////////////////////////////////////////////
//初赛第4题
#include <iostream>
#include <cstdio>
#include <cstring>
#include <utility>
#include <map>
using namespace std;
struct word_less
{
bool operator()(char* A, char* B) const
{
return strcmp(A, B) < 0;
}
};
typedef map<char*, int, word_less> my_map;
my_map Map;
int N, Min;
char Word[100001];
char* get_word()
{
char* P;
int Len;
Len = (int)strlen(Word);
P = new char[Len + 1];
strcpy(P, Word);
return P;
}
int main()
{
my_map::iterator It;
freopen("corpus.txt", "r", stdin);
Map.clear();
while (scanf("%s", Word) > 0)
{
It = Map.find(Word);
if (It == Map.end())
Map.insert(make_pair(get_word(), 1));
else
It->second++;
}
Min = 0x7fffffff;
for (It = Map.begin(); It != Map.end(); ++It) if (It->second < Min) Min = It->second;
N = 0;
freopen("corpus.txt", "r", stdin);
while (scanf("%s", Word) > 0)
if (Map[Word] > Min)
{
if (N > 0) printf(" ");
N++;
printf("%s", Word);
}
printf("\n");
return 0;
}
////////////////////////////////////////////////////////////////////////
//网上决赛第1题
#include <iostream>
#include <cstdio>
#include <memory>
#include <map>
#include <utility>
using namespace std;
const int MaxN = 100000;
int N, M;
int IDs[MaxN];
map<int, int> IDMarks;
int FilePos[MaxN];
int DSet[MaxN];
int Len, Limit;
int Queue[MaxN * 2];
int InDegs[MaxN * 2];
int* InEdges[MaxN * 2];
int* InValues[MaxN * 2];
int Sours[MaxN * 2];
int Belongs[MaxN * 2];
int Choices[MaxN * 2];
int ChoiceValues[MaxN * 2];
int Wastes[MaxN * 2];
int Result;
int* Subsets[MaxN];
int SetSizes[MaxN];
int Results[MaxN];
int find_father(int P[], int V)
{
int F = V;
while (P[F] != F) F = P[F];
while (P[V] != F)
{
int Temp = P[V];
P[V] = F;
V = Temp;
}
return F;
}
void join_to(int P[], int V1, int V2)
{
P[find_father(P, V1)] = find_father(P, V2);
}
template<class type>
type* clone(const type* Sour, size_t Size)
{
type* P = new type[Size];
memcpy(P, Sour, Size * sizeof(type));
return P;
}
void input()
{
int I, J, A, B;
char Ch;
fseek(stdin, 0, SEEK_SET);
J = 0;
for (;;)
{
Ch = getchar();
if (Ch == '\n') break;
if (Ch <= ' ') J = 0;
else if (J == 0) N++, J = 1;
}
N--;
fseek(stdin, 0, SEEK_SET);
for (I = 0; I < N; I++) DSet[I] = I, InDegs[I] = 0;
scanf(" %*s");
IDMarks.clear();
for (I = 0; I < N; I++)
{
scanf("%d", &IDs[I]);
IDMarks[IDs[I]] = I;
}
for (I = 0; I < N; I++)
{
scanf("%d", &J);
A = IDMarks[J];
FilePos[A] = ftell(stdin);
for (B = 0; B < N; B++)
if (A != B)
{
scanf("%d", &J);
if (J != 0)
{
join_to(DSet, A, B);
InDegs[B]++;
}
}
else
scanf(" %*s");
}
}
void init_tree()
{
int I, J, A, B;
for (I = 0; I < Len; I++)
{
A = Queue[I];
InEdges[A] = new int[InDegs[A]];
InValues[A] = new int[InDegs[A]];
InDegs[A] = 0;
Sours[A] = A;
Belongs[A] = A;
Choices[A] = -1;
Wastes[A] = 0;
}
for (I = 0; I < Len; I++)
{
A = Queue[I];
fseek(stdin, FilePos[A], SEEK_SET);
for (B = 0; B < N; B++)
if (B != A)
{
scanf("%d", &J);
if (J != 0)
{
InEdges[B][InDegs[B]] = A;
InValues[B][InDegs[B]++] = J;
}
}
else
scanf(" %*s");
}
}
void done_tree()
{
int I;
for (I = 0; I < Len; I++)
{
delete[] InEdges[Queue[I]];
delete[] InValues[Queue[I]];
}
}
bool perform_point(int Index, int V)
{
int I, J, U, Temp;
int Deg;
static int Edges[MaxN * 2];
static int Values[MaxN * 2];
Temp = 0x7fffffff;
U = -1;
for (I = 0; I < InDegs[V]; I++)
if (InValues[V][I] < Temp)
Temp = InValues[V][I], U = I;
if (U < 0) return false;
U = InEdges[V][U];
Result += Temp;
if (Index >= Limit) Wastes[V] += Temp;
ChoiceValues[V] = Temp;
U = find_father(Belongs, U);
if (find_father(Sours, U) != V)
{
Choices[V] = U;
join_to(Sours, V, U);
}
else
{
Sours[M] = M;
Belongs[M] = M;
Choices[M] = -1;
Wastes[M] = 0;
for (V = U; V >= 0; V = Choices[V])
{
V = find_father(Belongs, V);
Sours[V] = M;
if (Wastes[V] > Wastes[M]) Wastes[M] = Wastes[V];
}
Deg = 0;
for (V = U; V >= 0; V = Choices[V])
{
V = find_father(Belongs, V);
join_to(Belongs, V, M);
for (I = 0; I < InDegs[V]; I++)
{
J = InEdges[V][I];
J = find_father(Belongs, J);
if (Sours[J] != M)
{
Edges[Deg] = J;
Values[Deg++] = InValues[V][I] - ChoiceValues[V];
}
}
delete[] InEdges[V];
delete[] InValues[V];
InEdges[V] = 0;
InValues[V] = 0;
}
InDegs[M] = Deg;
InEdges[M] = clone(Edges, Deg);
InValues[M] = clone(Values, Deg);
Queue[Len++] = M;
M++;
}
return true;
}
int perform_tree()
{
int I;
if (Len == 1) return 0;
init_tree();
Limit = Len;
M = N;
Result = 0;
for (I = 0; I < Len; I++)
if (!perform_point(I, Queue[I])) break;
if (I < Len - 1 || Len == Limit) return -1;
Result -= Wastes[Queue[Len - 1]];
done_tree();
return Result;
}
void perform()
{
int I, J, F;
static int Lasts[MaxN];
static int Nexts[MaxN];
static bool Marks[MaxN];
memset(Lasts, -1, sizeof Lasts);
memset(Nexts, -1, sizeof Nexts);
memset(Marks, false, sizeof Marks);
for (I = 0; I < N; I++)
{
F = find_father(DSet, I);
if (Lasts[F] >= 0) Nexts[Lasts[F]] = I;
else Marks[I] = true;
Lasts[F] = I;
Subsets[I] = 0;
}
for (I = 0; I < N; I++)
if (Marks[I])
{
Len = 0;
J = I;
while (J >= 0)
{
Queue[Len++] = J;
J = Nexts[J];
}
SetSizes[I] = Len;
Subsets[I] = clone(Queue, Len);
Results[I] = perform_tree();
if (Results[I] < 0)
{
printf("NONE\n");
return;
}
}
for (I = 0; I < N; I++)
if (Marks[I])
{
for (J = 0; J < SetSizes[I]; J++)
printf("%d ", IDs[Subsets[I][J]]);
printf("%d\n", Results[I]);
}
}
int main()
{
freopen("sites.txt", "rb", stdin);
input();
perform();
return 0;
}
////////////////////////////////////////////////////////////////////////
//网上决赛第2题
#include <iostream>
#include <cstdio>
#include <memory>
#include <cstring>
using namespace std;
struct rule
{
char* Name;
int* Vars;
int Len;
int Result;
int Unknown;
};
struct variable
{
char* Name;
int Len;
int* Involves;
bool Deded;
int DedBy;
};
int RuleN, VarN, FactN, DedN;
rule Rules[300000];
variable Vars[300000];
int Facts[300000];
int Deds[300000];
int Goal;
template<class type>
type* clone(const type* Sour, size_t Size)
{
type* P = (type*)malloc(Size * sizeof(type));
memcpy(P, Sour, Size * sizeof(type));
return P;
}
int new_var(const char* Name)
{
const int Size = 499979;
static int Hash[Size];
static bool Mark = false;
if (!Mark)
{
Mark = true;
memset(Hash, -1, sizeof Hash);
}
int I, Key, Pos, Delta;
Key = 0;
for (I = 0; Name[I] != 0; I++) Key = (Key * 256 + (unsigned char)Name[I]) % Size;
Pos = Key;
Delta = 0;
for (; Hash[Pos] >= 0; Pos = (Pos + (Delta = (Delta + Key) % Size) + 1) % Size)
if (strcmp(Vars[Hash[Pos]].Name, Name) == 0) return Hash[Pos];
Vars[VarN].Name = clone(Name, strlen(Name) + 1);
Hash[Pos] = VarN;
return VarN++;
}
bool name_char(char Ch)
{
return Ch > ' ' && Ch != '&' && Ch != '-' && Ch != '>';
}
bool read_name(char* Name)
{
static char Next = 0;
while (Next <= ' '&& Next != EOF) Next = getchar();
if (Next == EOF) return false;
if (!name_char(Next))
{
*Name++ = Next;
*Name = 0;
Next = getchar();
return true;
}
while (name_char(Next))
{
*Name++ = Next;
Next = getchar();
}
*Name = 0;
return true;
}
void input(const char* GoalName)
{
int I, J, K;
static char Name[1001];
static int Array[300000];
VarN = 0;
sscanf(GoalName, "%s", Name);
Goal = new_var(Name);
freopen("facts.txt", "r", stdin);
FactN = 0;
while (scanf("%s", Name) > 0) Facts[FactN++] = new_var(Name);
freopen("rules.txt", "r", stdin);
RuleN = 0;
while (read_name(Name))
{
Rules[RuleN].Name = clone(Name, strlen(Name) + 1);
I = 0;
for (;;)
{
read_name(Name);
if (Name[0] == '-') break;
if (Name[0] == '&') continue;
Array[I++] = new_var(Name);
}
Rules[RuleN].Len = I;
Rules[RuleN].Vars = clone(Array, I);
read_name(Name);
read_name(Name);
Rules[RuleN].Result = new_var(Name);
RuleN++;
}
for (I = 0; I < VarN; I++) Vars[I].Len = 0;
for (I = 0; I < RuleN; I++)
{
Rules[I].Unknown = Rules[I].Len;
for (J = 0; J < Rules[I].Len; J++) Vars[Rules[I].Vars[J]].Len++;
}
for (I = 0; I < VarN; I++)
{
Vars[I].Involves = new int[Vars[I].Len];
Vars[I].Len = 0;
}
for (I = 0; I < RuleN; I++)
for (J = 0; J < Rules[I].Len; J++)
{
K = Rules[I].Vars[J];
Vars[K].Involves[Vars[K].Len++] = I;
}
}
bool search_data(int Var, int DedBy)
{
int I, J;
if (Var == Goal)
{
Vars[Var].Deded = true;
Vars[Var].DedBy = DedBy;
return true;
}
if (Vars[Var].Deded) return false;
Vars[Var].Deded = true;
Vars[Var].DedBy = DedBy;
for (I = 0; I < Vars[Var].Len; I++)
{
J = Vars[Var].Involves[I];
Rules[J].Unknown--;
if (Rules[J].Unknown == 0 && !Vars[Rules[J].Result].Deded)
{
Deds[DedN++] = J;
if (search_data(Rules[J].Result, J)) return true;
}
}
return false;
}
void perform()
{
int I;
for (I = 0; I < VarN; I++) Vars[I].Deded = false, Vars[I].DedBy = -1;
DedN = 0;
for (I = 0; I < FactN; I++)
if (search_data(Facts[I], -1)) break;
}
void output_data(int Var)
{
int I, Rule;
if (Vars[Var].DedBy < 0) return;
Rule = Vars[Var].DedBy;
Vars[Var].DedBy = -1;
for (I = 0; I < Rules[Rule].Len; I++)
output_data(Rules[Rule].Vars[I]);
printf(" %s", Rules[Rule].Name);
}
void output_data()
{
if (Vars[Goal].Deded)
{
printf("TRUE data");
output_data(Goal);
printf("\n");
}
else
printf("UNCERTAIN\n");
}
void output_goal(int Var)
{
int I, Rule;
if (Vars[Var].DedBy < 0) return;
Rule = Vars[Var].DedBy;
printf(" %s", Rules[Rule].Name);
Vars[Var].DedBy = -1;
for (I = 0; I < Rules[Rule].Len; I++)
output_goal(Rules[Rule].Vars[I]);
}
void output_goal()
{
if (Vars[Goal].Deded)
{
printf("TRUE goal");
output_goal(Goal);
printf("\n");
}
else
printf("UNCERTAIN\n");
}
int main(int argc, char* argv[])
{
static char Name[1001];
if (argc < 3) return 0;
input(argv[2]);
perform();
if (argv[1][0] == 'd') output_data();
else if (argv[1][0] == 'g') output_goal();
return 0;
}
////////////////////////////////////////////////////////////////////////
//总决赛
#include <iostream>
#include <cstdio>
#include <memory>
using namespace std;
struct map
{
int Gap;
int Board[9];
};
const int max_len = 20000;
const int hash_size = 59999;
int SLen, DLen, SCursor, DCursor, SStep, DStep;
int SQ[max_len], DQ[max_len];
char SGaps[max_len], DGaps[max_len];
char Hash[hash_size];
int HashKeys[hash_size];
map SMap, DMap;
int SKey, DKey;
inline char& hash(int V)
{
int Key = V * 4 % hash_size;
V++;
while (HashKeys[Key] != 0 && HashKeys[Key] != V)
{
Key++;
if (Key == hash_size) Key = 0;
}
HashKeys[Key] = V;
return Hash[Key];
}
inline int convert(int P[])
{
int I;
int Key = 0;
for (I = 8; I >= 0; I--)
if (P[I] != 0)
{
Key <<= 3;
Key |= P[I] - 1;
}
return Key;
}
bool search(int& FCursor, int& FLen, int Q[], char Gaps[], int Dir)
{
int Cursor = FCursor;
int Len = FLen;
int Limit = Len;
while (Cursor < Limit)
{
int Key = Q[Cursor];
char Gap = Gaps[Cursor];
int Delta = Gap + Gap + Gap;
if (Gap < 6)
{
int Key2 = Key & ~(511 << Delta) | ((Key & (63 << Delta)) << 3) | ((Key & (7 << (Delta + 6))) >> 6);
char Gap2 = Gap + 3;
char& H = hash(Key2 * 9 + Gap2);
if ((H & Dir) != Dir)
if ((H |= Dir) == 3) return true;
else
{
Q[Len] = Key2;
Gaps[Len++] = Gap2;
}
}
if (Gap >= 3)
{
int Key2 = Key & ~(511 << (Delta - 9)) | ((Key & (63 << (Delta - 6))) >> 3) | ((Key & (7 << (Delta - 9))) << 6);
char Gap2 = Gap - 3;
char& H = hash(Key2 * 9 + Gap2);
if ((H & Dir) != Dir)
if ((H |= Dir) == 3) return true;
else
{
Q[Len] = Key2;
Gaps[Len++] = Gap2;
}
}
if (Gap != 0 && Gap != 3 && Gap != 6)
{
int Key2 = Key;
char Gap2 = Gap - 1;
char& H = hash(Key2 * 9 + Gap2);
if ((H & Dir) != Dir)
if ((H |= Dir) == 3) return true;
else
{
Q[Len] = Key2;
Gaps[Len++] = Gap2;
}
}
if (Gap != 2 && Gap != 5 && Gap != 8)
{
int Key2 = Key;
char Gap2 = Gap + 1;
char& H = hash(Key2 * 9 + Gap2);
if ((H & Dir) != Dir)
if ((H |= Dir) == 3) return true;
else
{
Q[Len] = Key2;
Gaps[Len++] = Gap2;
}
}
Cursor++;
}
FCursor = Cursor;
FLen = Len;
return false;
}
void read_map(map& Map)
{
int I;
for (I = 0; I < 9; I++)
{
scanf(" %d", &Map.Board[I]);
if (Map.Board[I] == 0) Map.Gap = I;
}
}
void perform()
{
freopen("start.txt", "r", stdin);
read_map(SMap);
freopen("goal.txt", "r", stdin);
read_map(DMap);
SKey = convert(SMap.Board);
DKey = convert(DMap.Board);
if (SMap.Gap == DMap.Gap && SKey == DKey)
{
printf("0\n");
return;
}
hash(SKey * 9 + SMap.Gap) |= 1;
hash(DKey * 9 + DMap.Gap) |= 2;
SLen = SCursor = DLen = DCursor = 0;
SQ[SLen] = SKey;
SGaps[SLen++] = SMap.Gap;
DQ[DLen] = DKey;
DGaps[DLen++] = DMap.Gap;
SStep = 0;
DStep = 0;
while (SStep < 16 || DStep < 16)
{
if (SCursor < SLen && DCursor < DLen && SStep <= DStep ||
DCursor >= DLen && SCursor < SLen)
if (search(SCursor, SLen, SQ, SGaps, 1))
{
printf("%d\n", SStep + DStep + 1);
return;
}
else
SStep++;
else if (DCursor < DLen)
if (search(DCursor, DLen, DQ, DGaps, 2))
{
printf("%d\n", SStep + DStep + 1);
return;
}
else
DStep++;
else
break;
}
printf("-1\n");
}
int main()
{
perform();
return 0;
}