不解释，很简单，直接按照题目的方法构造就行了
Code
#include<iostream>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
typedef bool boolean;
template<typename T>
inline void readInteger(T& u){
char x;
while(!isdigit((x = getchar())));
for(u = x - ''; isdigit((x = getchar())); u = (u << ) + (u << ) + x - '');
ungetc(x, stdin);
} template<typename T>class Matrix{
public:
T* p;
int width;
int height;
Matrix():width(), height(){}
Matrix(int width, int height):width(width), height(height){
p = new T[width * height];
}
T* operator [](int pos){
return p + pos * width;
}
}; int n;
Matrix<int> hf;
int lx, ly; inline void init(){
readInteger(n);
hf = Matrix<int>(n + , n + );
} inline void solve(){
memset(hf.p, , sizeof(int) * (n + ) * (n + ));
hf[][n / + ] = ;
lx = , ly = n / + ;
for(int k = ; k <= n * n; k++){
if(lx == && ly != n){
lx = n;
ly++;
}else if(ly == n && lx != ){
ly = ;
lx--;
}else if(ly == n && lx == ){
lx++;
}else if(hf[lx - ][ly + ] == ){
lx--;
ly++;
}else{
lx++;
}
hf[lx][ly] = k;
}
for(int i = ; i <= n; i++){
for(int j = ; j <= n; j++){
printf("%d ", hf[i][j]);
}
putchar('\n');
}
} int main(){
freopen("magic.in", "r", stdin);
freopen("magic.out", "w", stdout);
init();
solve();
return ;
}
直接Tarjan，当然也可以直接用深搜（貌似要比Tarjan快一点，其实思路还是差不多的）
Code(Tarjan)
#include<iostream>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
typedef bool boolean;
template<typename T>
inline void readInteger(T& u){
char x;
while(!isdigit((x = getchar())));
for(u = x - ''; isdigit((x = getchar())); u = (u << ) + (u << ) + x - '');
ungetc(x, stdin);
}
#define smin(a, b) a = min(a, b) typedef class Edge{
public:
int next;
int end;
Edge(const int next = , const int end = ):next(next), end(end){}
}Edge; typedef class MapManager{
public:
int *h;
Edge *edge;
int ce;
MapManager():h(NULL), edge(NULL), ce(){}
MapManager(int points, int edges):ce(){
h = new int[(const int)(points + )];
edge = new Edge[(const int)(edges + )];
memset(h, , sizeof(int) * (points + ));
}
inline void addEdge(int from, int end){
edge[++ce] = Edge(h[from], end);
h[from] = ce;
}
}MapManager; #define m_begin(g, i) (g).h[(i)]
#define m_next(g, i) (g).edge[(i)].next
#define m_end(g, i) (g).edge[(i)].end int *uf;
int cn;
stack<int> s;
int *visitID;
int *exitID;
boolean* visited;
boolean* inStack;
MapManager g;
int result; inline void getSonMap(int end){
int counter = ;
int buf = s.top();
int first = buf;
s.pop();
inStack[buf] = false;
while(buf != end){
buf = s.top();
s.pop();
inStack[buf] = false;
uf[buf] = first;
counter++;
}
if(counter > )
smin(result, counter);
} void Tarjan(int node){
visitID[node] = exitID[node] = ++cn;
visited[node] = true;
inStack[node] = true;
s.push(node);
for(int i = m_begin(g, node); i != ; i = m_next(g, i)){
int& e = m_end(g, i);
if(!visited[e]){
Tarjan(e);
exitID[node] = min(exitID[node], exitID[e]);
}else if(inStack[e]){
exitID[node] = min(exitID[node], visitID[e]);
}
}
if(exitID[node] == visitID[node]){
getSonMap(node);
}
} int n; inline void init(){
readInteger(n);
g = MapManager(n, n);
uf = new int[(const int)(n + )];
visitID = new int[(const int)(n + )];
exitID = new int[(const int)(n + )];
inStack = new boolean[(const int)(n + )];
visited = new boolean[(const int)(n + )];
memset(visited, false, sizeof(boolean) * (n + ));
memset(inStack, false, sizeof(boolean) * (n + ));
for(int i = , a; i <= n; i++){
readInteger(a);
uf[i] = i;
g.addEdge(i, a);
}
} inline void solve(){
result = 0xfffffff;
for(int i = ; i <= n; i++)
if(!visited[i])
Tarjan(i);
delete[] visitID;
delete[] exitID;
printf("%d", result);
} int main(){
freopen("message.in", "r", stdin);
freopen("message.out", "w", stdout);
init();
solve();
return ;
}
Tarjan
dfs的话就记一个访问的时间戳，还要即一个是否在栈中，当时间戳不为初值并且在栈中才说明是环
Code(Dfs)
#include<iostream>
#include<cstdio>
#include<cctype>
#include<cstring>
#define smin(a, b) a = min(a, b)
using namespace std;
typedef bool boolean;
template<typename T>
inline void readInteger(T& u){
char x;
while(!isdigit((x = getchar())));
for(u = x - ''; isdigit((x = getchar())); u = (u << ) + (u << ) + x - '');
ungetc(x, stdin);
}
int n;
int timec;
int* next;
int* rank;
boolean* inStack;
int result = 0xfffffff;
void find(int node){
if(rank[node] != - && inStack[node]){
smin(result, ++timec - rank[node]);
return;
}
if(rank[node] != - ) return;
inStack[node] = true;
rank[node] = ++timec;
find(next[node]);
inStack[node] = false;
}
int main(){
freopen("message.in", "r", stdin);
freopen("message.out", "w", stdout);
readInteger(n);
next = new int[(const int)(n + )];
rank = new int[(const int)(n + )];
inStack = new boolean[(const int)(n + )];
memset(rank, -, sizeof(int) * (n + ));
for(int i = ; i <= n; i++){
readInteger(next[i]);
inStack[i] = false;
}
for(int i = ; i <= n; i++){
if(rank[i] == -)
find(i);
}
printf("%d", result);
return ;
}
Dfs
思路很简单，搜！不过如果对子、三带一都去搜的话很耗时间，也很耗代码，而且它们是可以直接算出来的
稍微贪一下心，把能带走的都带走，而且从多的开始带。但是双王要记住特殊处理
搜的内容就只包括顺子，只不过注意所有情况都要搜到，因为某些数据顺子即使搜得长，并不是最优的，反
而导致单牌过多。其他都还是没有什么特别坑的细节。
Code
#include<iostream>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<algorithm>
#define smin(a, b) a = min(a, b)
using namespace std;
typedef bool boolean;
template<typename T>
inline void readInteger(T& u){
char x;
while(!isdigit((x = getchar())));
for(u = x - ''; isdigit((x = getchar())); u = (u << ) + (u << ) + x - '');
ungetc(x, stdin);
} int n;
int kase;
int key[] = {, , , , , , , , , , , , , };
int had[]; inline void init(){
memset(had, , sizeof(had));
for(int i = , a, b; i <= n; i++){
readInteger(a);
readInteger(b);
if(a == ) had[ + b]++;
else had[key[a]]++;
}
} int calc(){
int counter[] = {, , , , };
for(int i = ; i <= ; i++){
if(had[i] > ){
counter[had[i]]++;
}
}
int reter = ;
boolean aFlag = ;
if(had[] == && had[] == ){
aFlag = ;
}
while(counter[] && counter[] >= ) reter++, counter[] -= , counter[] -= ;
while(counter[] && counter[] >= ) reter++, counter[] -= , counter[] -= ;
while(counter[] && counter[]) reter++, counter[] -= , counter[] -= ;
while(counter[] && counter[]) reter++, counter[] -= , counter[] -= ;
while(counter[] && counter[]) reter++, counter[] -= , counter[] -= ;
if(counter[] >= && aFlag) counter[] -= ;
return reter + counter[] + counter[] + counter[] + counter[];
} int result;
void search(int last, int times){
if(last == ){
smin(result, times);
return;
}
smin(result, times + calc());
if(times >= result) return;
//顺子
if(last >= ){
for(int p = ; p >= ; p--){
for(int i = ; i <= ; i++){
int k = i;
while(had[k] >= p && k < ) k++;
if((k - i) * p >= ){
for(int j = i; j < k; j++){
had[j] -= p;
}
for(int j = k - ; j >= i; j--){
if((j - i + ) * p >= )
search(last - (j - i + ) * p, times + );
had[j] += p;
}
}
}
}
}
} int main(){
freopen("landlords.in", "r", stdin);
freopen("landlords.out", "w", stdout);
readInteger(kase);
readInteger(n);
while(kase--){
init();
result = n;
search(n, );
printf("%d\n", result);
}
return ;
}