预备知识：
对于一个n*n的拉丁方总数为N(k)。
当第一行为 1，2，……，n；第一列为1，2，……，n时， 拉丁方数为L(K)
存在如下公式：
N(K) = L(K) * N! * (N-1)!
说明：当L(k)确定后，第2到第你行的排列组成复合题意的拉丁方，所以乘以(n-1)!，第一到第N列的排列又是拉丁方，所以乘以 n!.
言归正传， 本题是第一行固定为1，2，……，n，第一列为1，2，……，n。所以求得L(K)乘以(n-1)!即可。
优化一：
置换群(by Maigo). 以5为例，
1 2 3 4 5
2 1 4 5 3 置换圈(1,2) , (3,4,5) 最长长度为3
和
1 2 3 4 5
2 3 1 5 4 置换圈(4,5), (1,2,3) 最长长度为3
他们是等价的，只是数字先后顺序有变化，他们产生的结果是一致（要多多思考）。
参考 cmykrgb1 ，利用最长长度作为索引进行hash，即枚举到第二行最后一列后，计算置换圈的最长长度，若已计算出这个长度的拉丁方总数，则返回该长度的所有可能数。
优化二：都可以想到，枚举到第n-1行即可， 直接ans++。
/**//*
ID: lorelei3
TASK: latin
LANG: C++
*/
#include <fstream>
#include <memory.h>
using namespace std;
const int fact[] = 
{1,1,2,6,24,120,720};
const int MAXN = 10;
ifstream fin("latin.in");
ofstream fout("latin.out");
int n, id, cnt[MAXN], a[MAXN];
long long ans;
bool row[MAXN][MAXN], col[MAXN][MAXN], v[MAXN];
void find(){
id=2;
int l,t;
memset(v, false, sizeof(v));
for(int i=1; i<=n; ++i)
if(!v[i]){
t=i; l=0;
do{
v[t]=true;
t = a[t];
l++;
}while(!v[t]);
if(l>id)
id=l;
}
}
void dfs(int x, int y){
for(int i=1; i<=n; ++i)
if(row[x][i] && col[y][i]){
if(x==2){
a[y]=i;
if(y==n){
find();
if(cnt[id]>0){
ans += cnt[id];
return;
}
}
}
row[x][i]=false;
col[y][i]=false;
if(y==n){
if(x==n-1){
cnt[id]++;
ans++;
}else
dfs(x+1, 2);
}else
dfs(x, y+1);
row[x][i]=true;
col[y][i]=true;
}
}
int main(){
fin>>n;
if(n==2)
ans=1;
else{
int i;
memset(row, true, sizeof(row));
memset(col, true, sizeof(col));
memset(cnt, 0, sizeof(cnt));
for(i=2; i<n; ++i) row[i][i]=false;
for(i=1; i<=n; ++i) col[i][i]=false;
ans=0;
a[1]=2;
dfs(2,2);
ans *= fact[n-1];
}
fout<<ans<<endl;
return 0;
}posted @
2011-02-14 15:09 小阮 阅读(977) |
评论 (0) |
编辑 收藏比较简单的DP。和3.3的Home on the Range差不多. 还简单些。
初始状态
f(i,n) = 1， (i,n)没树；f(i,n)=0，(i,n)有树。
f(n,i) = 1， (i,n)没树；f(i,n)=0，(i,n)有树。
状态转移方程：
i->n-1...1
j->n-1...1
若(i,j)没树
f[i,j] = min3(f[i+1][j], f[i][j+1], f[i+1][j+1])+1
记录最大的f[i,j]即可。
/**//*
ID: lorelei3
TASK: bigbrn
LANG: C++
*/
#include <fstream>
using namespace std;
const int MAXN = 1005;
ifstream fin("bigbrn.in");
ofstream fout("bigbrn.out");
int f[MAXN][MAXN];
inline int min3(int a, int b, int c){
int t=a<b?a:b;
return c<t?c:t;
}
int main(){
int i,j,n, t, ans=1;
fin>>n>>t;
for(i=1; i<=n; ++i)
for(j=1; j<=n; ++j)
f[i][j]=-1;
for(i=0; i<t; ++i){
int a,b;
fin>>a>>b;
f[a][b]=0;
}
for(i=1; i<=n; ++i){
if(f[i][n]!=0)
f[i][n]=1;
if(f[n][i]!=0)
f[n][i]=1;
}
for(i=n-1; i>=1; --i)
for(j=n-1; j>=1; --j)
if(f[i][j]!=0){
f[i][j]=min3(f[i+1][j], f[i][j+1], f[i+1][j+1])+1;
if(f[i][j]>ans)
ans=f[i][j];
}
fout<<ans<<endl;
return 0;
}
posted @
2011-02-11 21:56 小阮 阅读(238) |
评论 (0) |
编辑 收藏第一问是求最小基点，采用两点DFS的kosaraju算法，对每个点进行DFS，标记visited为true，然后对反图再进行DFS，能遍历到的点属于一个强连通分量。 （强连通分量上的边，求反之后，是仍然可以遍历到的，反图其实是过滤了非强连通的边）
然后把强连通分量收缩成一个点，构造新图。新图中，入度为0的点的个数就是最小基点。
第二问，若一个顶点入度为0或者出度为0的时候，该图一定不是强连通的。为了使添加的边最少，则应该把入度为0顶点和出度为0的顶点每个顶点添加1条边，使图中不存在入度为0顶点和出度为0的顶点。新图中，入度为0的点的个数为s1，出度为0的点的个数s2，求max(s1,s2)。
/**//*
ID: lorelei3
TASK: schlnet
LANG: C++
*/
#include <fstream>
#include <memory.h>
using namespace std;
const int MAXN = 105;
ifstream fin("schlnet.in");
ofstream fout("schlnet.out");
int adj[MAXN][MAXN], fadj[MAXN][MAXN], dist[MAXN][MAXN];
int belong[MAXN], ind[MAXN], outd[MAXN];
bool visited[MAXN];
int M,id,od;
void dfs(int k){
visited[k]=true;
for(int i=1; i<=adj[k][0]; ++i){
int j=adj[k][i];
if(!visited[j])
dfs(j);
}
}
void fdfs(int k){
belong[k]=M;
for(int i=1; i<=fadj[k][0]; ++i){
int j=fadj[k][i];
if(visited[j]&&!belong[j])
fdfs(j);
}
}
int n;
void solve(){
int i,j,k;
//kosaraju
for(i=1; i<=n; ++i){
if(!belong[i]){
dfs(i);
M++;
fdfs(i);
memset(visited, false, sizeof(visited));
}
}
for(i=1; i<=n; ++i)
for(k=1; k<=adj[i][0]; ++k){
int j=adj[i][k];
dist[belong[i]][belong[j]]=true;
}
for(i=1; i<=M; ++i)
for(j=1; j<=M; ++j)
if(i!=j&&dist[i][j]){
outd[i]++;
ind[j]++;
}
for(i=1; i<=M; ++i){
if(ind[i]==0)
id++;
if(outd[i]==0)
od++;
}
}
void input(){
fin>>n;
for(int i=1; i<=n; ++i){
int a;
fin>>a;
while(a!=0){
adj[i][++adj[i][0]]=a;
fadj[a][++fadj[a][0]]=i;
fin>>a;
}
}
}
void output(){
if(M==1)
fout<<1<<endl<<0<<endl;
else{
fout<<id<<endl;
fout<<(id>od?id:od)<<endl;
}
}
int main(){
input();
solve();
output();
return 0;
}
posted @
2011-02-11 19:40 小阮 阅读(333) |
评论 (0) |
编辑 收藏
摘要: 用一个表保存矩阵的先后顺序，w,t,b,d都对表进行操作，同时维护一个hash表查找标识符对应的下标。s时，采用上浮法得到矩阵面积。
/**//*ID: lorelei3TASK: windowLANG: C++*/#include <fstream>#include <iostream>using namesp...
阅读全文
posted @
2011-02-10 23:14 小阮 阅读(293) |
评论 (0) |
编辑 收藏本题我采用DFS+DP的方法，题意是找使用最少的桶，所有先用1个桶进行DFS枚举，再用2个，3个，等等。
枚举出使用的桶之后，DP的环节就是完全背包问题。
初始化：f[i* v[第一个桶]]=true (我试过仅f[0]也能过，就是慢点）
状态转移方程：f[j] = f[j] | f[j-v[第i个桶]；
目标状态：f[Q]
/**//*
ID: lorelei3
TASK: milk4
LANG: C++
*/
#include <fstream>
#include <algorithm>
#include <memory.h>
using namespace std;
const int MAXP = 105;
const int MAXQ = 20000;
int Q,P,v[MAXP];
int ans, use[MAXP];
ifstream fin("milk4.in");
ofstream fout("milk4.out");
void input(){
fin>>Q;
fin>>P;
for(int i=1; i<=P; ++i)
fin>>v[i];
sort(v+1, v+1+P);
}
void output(){
fout<<ans;
for(int i=1; i<=ans; ++i)
fout<<" "<<v[use[i]];
fout<<endl;
exit(0);
}
bool f[MAXQ];
void dp(){
int i,j;
memset(f, false, sizeof(f));
for(i=1; i<=Q/v[use[1]]; ++i)
f[i*v[use[1]]]=true;
for(i=2; i<=ans; i++)
for(j=v[use[i]]; j<=Q; ++j)
f[j] |= f[j-v[use[i]]];
if(f[Q])
output();
}
void dfs(int k){
for(int i=use[k-1]+1; i<=P-ans+k; ++i){
use[k]=i;
if(k==ans)
dp();
else
dfs(k+1);
}
}
void DFSID(){
for(ans=1; ans<=P; ++ans)
dfs(1);
}
int main(){
input();
DFSID();
return 0;
}
posted @
2011-02-10 14:18 小阮 阅读(314) |
评论 (0) |
编辑 收藏
暴力搜索, 加上限制条件.
能过样例就可以了.
/**//*
ID: lorelei3
TASK: wissqu
LANG: C++
*/
#include <fstream>
#include <memory.h>
using namespace std;
struct Move{
int ch,c,r;
};
ifstream fin("wissqu.in");
ofstream fout("wissqu.out");
int map[6][6], cnt[6], tot;
bool used[6][6];
Move ans[20],tmp[20];
void input(){
char ch;
for(int i=1; i<=4; ++i){
for(int j=1; j<=4; ++j){
fin>>ch;
map[i][j]=ch-'A'+1;
cnt[map[i][j]]++;
}
fin.get();
}
cnt[3]--;
cnt[4]++;
}
void dfs(int d, int ch){
if(d>=16){
if(tot==0)
memcpy(ans, tmp, sizeof(ans));
tot++;
return;
}
for(int i=1; i<=4; ++i)
for(int j=1; j<=4; ++j)
if(!used[i][j] && map[i+1][j+1]!=ch && map[i+1][j]!=ch && map[i+1][j-1]!=ch &&
map[i][j+1]!=ch && map[i][j]!=ch &&map[i][j-1]!=ch &&
map[i-1][j+1]!=ch && map[i-1][j]!=ch && map[i-1][j-1]!=ch){
int t = map[i][j];
map[i][j]=ch;
cnt[ch]--;
used[i][j]=true;
tmp[d].ch = ch;
tmp[d].r = i;
tmp[d].c = j;
if(d==15)
dfs(d+1, 0);
else{
for(int k=1; k<=5; ++k)
if(cnt[k])
dfs(d+1, k);
}
map[i][j]=t;
cnt[ch]++;
used[i][j]=false;
}
}
void output(){
for(int i=0; i<16; ++i)
fout<<(char)(ans[i].ch-1+'A')<<" "<<ans[i].r<<" "<<ans[i].c<<endl;
fout<<tot<<endl;
}
int main(){
input();
dfs(0, 4);
output();
return 0;
}
posted @
2011-02-10 11:11 小阮 阅读(247) |
评论 (0) |
编辑 收藏
摘要: 此题就是是求费马点，可以用到模拟退火算法模拟退火的主要思想是一开始现在一个大范围内游走，逐渐减小搜索范围，最后找到解我的程序是令马尔科夫链为200（即每次循环进行200次探索），初始温度为40（随机走若干个t步），衰减量为1（每次t--），则当温度降为0时，即找到答案
/**//*ID: lorelei3TASK: fence3LANG: C++*/#include...
阅读全文
posted @
2011-02-09 13:44 小阮 阅读(734) |
评论 (3) |
编辑 收藏
朴素搜索即刻, 注意终止条件和行走路线的模拟.
/**//*
ID: lorelei3
TASK: snail
LANG: C++
*/
#include <fstream>
#include <cmath>
#include <memory.h>
using namespace std;
const int MAXN = 125;
const int dx[] = {1, 0,-1, 0};
const int dy[] = {0, 1, 0,-1};
ifstream fin("snail.in");
ofstream fout("snail.out");
char board[MAXN][MAXN];
int n,b;
void input(){
memset(board, '.', sizeof(board));
fin>>n>>b;
for(int i=0; i<b; ++i){
fin.get();
char ch; int a;
fin>>ch>>a;
board[a][ch-'A'+1]='#';
}
}
int ans;
bool bound(int x, int y){
if(x<1 || x>n) return true;
if(y<1 || y>n) return true;
if(board[x][y]=='#') return true;
if(board[x][y]=='0') return true;
return false;
}
bool terminal(int x, int y, int dir){
if(board[x+dx[dir]][y+dy[dir]]=='0')
return true;
for(int i=0; i<4; ++i){
if(abs(i-dir)==2) continue;
int tx=x+dx[i];
int ty=y+dy[i];
if(tx<1||tx>n) continue;
if(ty<1||ty>n) continue;
if(board[tx][ty]=='.')
return false;
}
return true;
}
void dfs(int x, int y, int dir,int cnt){
if(terminal(x,y,dir)){
if(cnt>ans)
ans=cnt;
return;
}
else{
board[x][y]='0';
int tx=x+dx[dir];
int ty=y+dy[dir];
int dt;
if(bound(tx,ty)){
dt=dir+1>3?0:dir+1;
tx=x+dx[dt];
ty=y+dy[dt];
if(!bound(tx,ty))
dfs(tx, ty, dt, cnt+1);
dt=dir-1<0?3:dir-1;
tx=x+dx[dt];
ty=y+dy[dt];
if(!bound(tx,ty))
dfs(tx, ty, dt, cnt+1);
}else
dfs(tx, ty, dir, cnt+1);
board[x][y]='.';
}
}
void output(){
fout<<ans<<endl;
}
int main(){
input();
dfs(1,1,0,1);
dfs(1,1,1,1);
output();
return 0;
}
posted @
2011-02-09 01:24 小阮 阅读(218) |
评论 (0) |
编辑 收藏
将相邻的数做差之后，转换为求最长重复子序列。
/**//*
ID: lorelei
TASK: theme
LANG: C++
*/
#include <fstream>
using namespace std;
const int MAXN = 5005;
const int INF = 0x7FFFFFFF;
ifstream fin("theme.in");
ofstream fout("theme.out");
int a[MAXN];
int n, ans;
void input(){
int p,q;
fin>>n>>p;
for(int i=1; i<n; ++i){
fin>>q;
a[i]=q-p;
p=q;
}
}
void solve(){
for(int i=1; i<n-ans; ++i)
for(int j=i+ans; j<n-ans; ++j)
if(a[i]==a[j]){
int len=1, k=j;
while(a[i+len] == a[j+len] && i+len+1<k) len++;
if(len>ans)
ans=len;
}
}
void output(){
if(ans<4) ans = -1;
fout<<ans+1<<endl;
}
int main(){
input();
solve();
output();
return 0;
}
posted @
2011-02-08 19:09 小阮 阅读(271) |
评论 (0) |
编辑 收藏
摘要: FloodFill遍历，对于个每个图形，分别进行旋转、对称total7种操作，然后在hash table中找是否存在。
/**//*ID: lorelei3TASK: starryLANG: C++*/#include <fstream>#include <queue>#include <memory.h&...
阅读全文
posted @
2011-02-08 13:01 小阮 阅读(304) |
评论 (0) |
编辑 收藏