[POJ 2446]Chessboard
很容易看出是二分图最大匹配，可是怎么建图呢……
我们可以考虑把一个点的横纵坐标相加，和为偶数者称之为偶数点，反之为奇数点。我们发现，每个骨牌都正好覆盖了一个奇数点和一个偶数点。于是乎就能把点分为两个集合了，建图就很方便了。
代码：
#include <cstdio>
#include <cstring>
const int maxn=35,maxm=520;
bool G[maxm][maxm];
// Hungray
int odd_cnt=0,even_cnt=0;
bool vis[maxm];
int GirlFriend[maxm];
bool DFS(int x){
int i;
for(i=1;i<=even_cnt;i++)
if(G[x][i] && !vis[i]){
vis[i]=true;
if(!GirlFriend[i] || DFS(GirlFriend[i])){
GirlFriend[i]=x;
return true;
}
}
return false;
}
inline int Hungray(){
register int i,ans=0;
for(i=1;i<=odd_cnt;i++){
memset(vis,0,sizeof(vis));
if(DFS(i))
ans++;
}
return ans;
}
int n,m;
bool isHole[maxn][maxn];
int ct[maxn][maxn];
inline int AddPoint(int a,int b,int x,int y){
if(ct[x][y])
if(!isHole[x][y])
G[ct[a][b]][ct[x][y]]=true;
}
int main(){
int k,x,y;
register int i,j,tot;
scanf("%d%d%d",&m,&n,&k);
tot=m*n-k;
if(1&tot){
puts("NO");
return 0;
}
for(i=1;i<=k;i++){
scanf("%d%d",&x,&y);
isHole[y][x]=true;
}
for(i=1;i<=m;i++)
for(j=1;j<=n;j++){
if(isHole[i][j])
continue;
if(1&(i+j)){
ct[i][j]=++odd_cnt;
}else{
ct[i][j]=++even_cnt;
}
}
for(i=1;i<=m;i++)
for(j=1;j<=n;j++){
if(!isHole[i][j] && 1&(i+j)){
AddPoint(i,j,i-1,j);
AddPoint(i,j,i+1,j);
AddPoint(i,j,i,j-1);
AddPoint(i,j,i,j+1);
}
}
if(Hungray()==(tot/2)){
puts("YES");
}else{
puts("NO");
}
return 0;
}
[POJ 2406]Power Strings
循环节又一题……用KMP性质搞搞即可。
注意特判（好像是句废话），再就没啥了……
代码：
#include <cstdio>
#include <cstring>
const int maxn=1e6+5;
char P[maxn];
int f[maxn];
int main(){
register int i,j,xhj,n;
while(scanf("%s",P)){
if(P[0]=='.')
break;
n=strlen(P);
f[0]=f[1]=0;
for(i=1;i<n;i++){
j=f[i];
while(j && P[j]!=P[i])
j=f[j];
f[i+1]=(P[j]==P[i]?j+1:0);
}
xhj=n-f[n];
if(!(n%xhj)){
printf("%d\n",n/xhj);
}else{
puts("1");
}
}
return 0;
}
[UVa 11549]Calculator Conundrum
很有趣的一个题。
很明显，求出的结果一定会循环，形成一个环。然后呢？假如有一只乌龟和一只兔子在这个赛道上赛跑（同起点），兔子的速度是乌龟的两倍，那么最后兔子一定会“追上”乌龟，然后接下来的情况就是以前的循环了。
这种神奇的算法叫做Floyd判圈算法。话说还有一种Brent判圈算法……常数比它还要小。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
char buf[25];
int n;
inline ull next(ull x){
register ull res=0;
register int i,length;
memset(buf,0,sizeof(buf));
length=sprintf(buf,"%llu",x*x);
length=min(length,n);
for(i=0;i<length;i++){
res=res*10+buf[i]-'0';
}
return res;
}
int main(){
ull k1,k2,ans;
int T;
scanf("%d",&T);
while(T--){
scanf("%d%llu",&n,&k1);
ans=k1;
k2=k1;
do{
k1=next(k1);
k2=next(k2);
if(k2>ans)
ans=k2;
k2=next(k2);
if(k2>ans)
ans=k2;
}while(k1!=k2);
printf("%llu\n",ans);
}
return 0;
}
[BZOJ 3172]单词
首先……出题人语文不太好……估计和我这种语文很差的人还有差距……
这个提的意思是，给你若干个单词，输出每个单词在所有单词（而不是把所有单词连起来）中出现的次数。
然后肯定要AC自动机上失配函数搞一波辣……把BFS序倒过来搜，传递出现次数即可。还有这个题的数据范围好像也比给出的小很多……
代码：
/**************************************************************
Problem: 3172
User: danihao123
Language: C++
Result: Accepted
Time:232 ms
Memory:115080 kb
****************************************************************/
#include <cstdio>
#include <cstring>
const int maxn=205;
const int maxnode=1*1e6+5;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
int cnt[maxnode];
namespace ACAutomate{
// Trie
const int sigma_size=26;
int Tree[maxnode][sigma_size];
int siz;
inline int idx(char c){
return c-'a';
}
void InitAC(){
siz=0;
CL_ARR(Tree[0],0);
}
int Insert(char *s){
register int i,n=strlen(s);
register int u=0,c;
REP(i,n){
c=idx(s[i]);
if(!Tree[u][c]){
siz++;
Tree[u][c]=siz;
CL_ARR(Tree[siz],0);
}
u=Tree[u][c];
cnt[u]++;
}
return u;
}
// AC Automate
int f[maxnode];
int Q[maxnode];
void InitFail(){
register int i,u,x,v,head=0,tail=0;
f[0]=0;
REP(i,sigma_size){
u=Tree[0][i];
if(u){
f[u]=0;
Q[tail++]=u;
}
}
while(head<tail){
u=Q[head];
head++;
REP(i,sigma_size){
x=Tree[u][i];
if(!x){
continue;
}
Q[tail++]=x;
v=f[u];
while(v && !Tree[v][i])
v=f[v];
f[x]=Tree[v][i];
}
}
for(i=tail-1;i>=0;i--)
cnt[f[Q[i]]]+=cnt[Q[i]];
}
};
char buf[maxnode];
int pos[maxn];
int main(){
int n;
register int i;
scanf("%d",&n);
ACAutomate::InitAC();
REP_B(i,n){
scanf("%s",buf);
pos[i]=ACAutomate::Insert(buf);
}
ACAutomate::InitFail();
REP_B(i,n){
printf("%d\n",cnt[pos[i]]);
}
return 0;
}
[CodeVS 3729]飞扬的小鸟
论如何把一个完全背包出的高大上……
这个题啊……细节特别多……
首先，不建议开滚动数组，细节处理就会疯。
然后呢……真的不太好说了……还是看代码吧（尽管代码还是有明显的滚动数组痕迹）。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=10005,maxm=1005;
const int INF=0x7f7f7f7f;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
int GZ[maxn][2];
bool haveGZ[maxn];
int A[maxn][2];
int d[maxn][maxm];
int main(){
int n,m,k,temp;
register int i,j,v,now,pre,ans=INF,cnt;
scanf("%d%d%d",&n,&m,&k);
cnt=k;
REP(i,n){
scanf("%d%d",&A[i][0],&A[i][1]);
}
for(i=0;i<=n;i++){
GZ[i][0]=0;
GZ[i][1]=m+1;
}
REP_B(i,k){
scanf("%d",&temp);
haveGZ[temp]=true;
scanf("%d%d",&GZ[temp][0],&GZ[temp][1]);
}
memset(d,0x7f,sizeof(d));
memset(d[0],0,sizeof(d[0]));
d[0][0]=INF;
REP_B(i,n){
now=i;
pre=i-1;
d[now][0]=INF;
int& X=A[i-1][0];
int& Y=A[i-1][1];
REP_B(j,m){
if(j-X>0 && d[pre][j-X]<INF)
d[now][j]=min(d[now][j],d[pre][j-X]+1);
if(j-X>0 && d[now][j-X]<INF)
d[now][j]=min(d[now][j],d[now][j-X]+1);
if(j==m)
for(v=j-X;v<=m;v++){
if(d[pre][v]<INF)
d[now][j]=min(d[now][j],d[pre][v]+1);
if(d[now][v]<INF)
d[now][j]=min(d[now][j],d[now][v]+1);
}
}
for(j=GZ[i][0]+1;j<GZ[i][1];j++){
if(j+Y<=m && d[pre][j+Y]<INF)
d[now][j]=min(d[now][j],d[pre][j+Y]);
}
if(haveGZ[i]){
REP_B(j,GZ[i][0])
if(d[now][j]<INF){
d[now][j]=INF;
}
for(j=GZ[i][1];j<=m;j++)
if(d[now][j]<INF){
d[now][j]=INF;
}
}
}
for(i=n;i>=1;i--){
for(j=m;j>=1;j--){
ans=min(ans,d[i][j]);
}
if(ans<INF)
break;
if(haveGZ[i])
cnt--;
}
if(cnt==k){
printf("1\n%d\n",ans);
}else{
printf("0\n%d\n",cnt);
}
return 0;
}
[UVa 10635]Prince and Princess
这个名字真有童话风味哎……
直接LCS肯定会TLE。注意每个序列都是不重复序列，所以可以将A映射到[tex][1,p+1][/tex]，然后再把B映射一下（有的可能A里面没有？反正既然A里没有就和LCS没关系了），就相当于求B的LIS。LIS可以在[tex]O(nlogn)[/tex]时间内完成。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=62510;
#define CL_ARR(x,v) memset(x,v,sizeof(x))
int B[maxn];
int Hash[maxn];
int d[maxn],g[maxn];
int main(){
int T,n,p,q,x;
register int i,ans,k,Case=0;
scanf("%d",&T);
while(T--){
Case++;
scanf("%d%d%d",&n,&p,&q);
CL_ARR(Hash,0);
for(i=1;i<=(p+1);i++){
scanf("%d",&x);
Hash[x]=i;
}
for(i=1;i<=(q+1);i++){
scanf("%d",&x);
B[i]=Hash[x];
}
CL_ARR(g,0x7f);
ans=0;
for(i=1;i<=(q+1);i++){
k=lower_bound(g+1,g+2+q,B[i])-g;
d[i]=k;
g[k]=B[i];
ans=max(ans,d[i]);
}
printf("Case %d: %d\n",Case,ans);
}
return 0;
}
[BZOJ 1511]Periods of Words
很妙的一道题啊。
这个题可以先求一遍KMP的失配函数，然后对于每个失配函数沿着失配边往前一直走（不能走到0）。然后对于每个前缀[tex]i[/tex]，答案就是[tex]i-f[i][/tex]（要求[tex]f[i][/tex]不为0，反之无解）。
为什么这样可以呢？
首先建议大家看一下Matrix67关于KMP的解释。对于一个前缀，如果整个弄上去肯定不行。所以说需要前面和后面重叠一个字串，这个子串是不考虑的。当然，我们希望在这个被删除的子串最短辣。
代码：
/**************************************************************
Problem: 1511
User: danihao123
Language: C++
Result: Accepted
Time:148 ms
Memory:5704 kb
****************************************************************/
#include <cstdio>
const int maxn=1000005;
char buf[maxn];
int f[maxn];
int main(){
register int i,j;
register long long ans=0;
int n;
scanf("%d%s",&n,buf);
f[0]=f[1]=0;
for(i=1;i<n;i++){
j=f[i];
while(j && buf[i]!=buf[j])
j=f[j];
f[i+1]=(buf[i]==buf[j]?j+1:0);
}
for(i=2;i<=n;i++){
if(f[i]){
while(f[f[i]]){
f[i]=f[f[i]];
}
}
}
for(i=1;i<=n;i++){
if(f[i]){
ans+=i-f[i];
}
}
printf("%lld\n",ans);
return 0;
}
[BZOJ 1212]L语言
这个感觉本质上和那个Remember a Word很像吧……
不过这个只是求最长可行前缀，递推即可。
代码：
/**************************************************************
Problem: 1212
User: danihao123
Language: C++
Result: Accepted
Time:660 ms
Memory:45072 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=1048581;
const int maxW=4005,maxL=105;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define DREP(i,n) for(i=(n)-1;i>=0;i--)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
vector<int> AnsList;
namespace Trie{
const int maxnode=400005;
const int sigma_siz=26;
int Tree[maxnode][sigma_siz];
int val[maxnode];
int siz;
inline int idx(char c){
return c-'a';
}
inline void InitTrie(){
siz=0;
val[0]=0;
CL_ARR(Tree[0],0);
}
void Insert(char *s,int v){
register int u=0,n=strlen(s);
register int i,c;
REP(i,n){
c=idx(s[i]);
if(!Tree[u][c]){
siz++;
Tree[u][c]=siz;
val[siz]=0;
CL_ARR(Tree[siz],0);
}
u=Tree[u][c];
}
val[u]=v;
}
void Query(char *s,int len){
register int i,c,u=0;
AnsList.clear();
REP(i,len){
if(!s[i])
break;
c=idx(s[i]);
if(!Tree[u][c])
break;
u=Tree[u][c];
if(val[u])
AnsList.push_back(val[u]);
}
}
};
char Text[maxn];
int len[maxW];
char buf[maxL];
bool d[maxn];
int main(){
int n,m;
int length;
register int i,j,k;
bool flag;
Trie::InitTrie();
scanf("%d%d",&n,&m);
REP_B(i,n){
scanf("%s",buf);
len[i]=strlen(buf);
Trie::Insert(buf,i);
}
REP_B(i,m){
scanf("%s",Text);
length=strlen(Text);
CL_ARR(d,0);
d[0]=true;
for(j=0;j<=length;j++){
if(d[j]){
Trie::Query(Text+j,length-j);
REP(k,AnsList.size()){
d[j+len[AnsList[k]]]=true;
}
}
}
flag=false;
for(j=length;j>=0;j--){
if(d[j]){
flag=true;
printf("%d\n",j);
break;
}
}
if(!flag)
puts("0");
}
return 0;
}
[POJ 2784]Buy or Build
啊这题竟然在POJ上有……
枚举套餐子集是肯定的啦，但接下来呢？有的同学或许会想直接Kruskal求MST。但是估计会T。
有一个很有效的优化：先求一遍不加套餐的MST，然后接下来每次求MST的时候都只考虑这[tex]n-1[/tex]条边，这样就很快了。
需要注意的是，这[tex]n-1[/tex]以外的边就算加入了套餐也不会被考虑。因为无论加不加套餐，这些更大的边所能连接的连通分量总是可以被以前更小的边连接，所以这条边无论如何也不会被考虑啦……
代码写起来容易让人崩溃……所以说这个题很能锻炼代码能力和Debug能力。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=1005,maxq=8;
int n;
int p[maxn],rank[maxn];
int find_set(int x){
if(p[x]==x)
return x;
else
return p[x]=find_set(p[x]);
}
inline void link_set(int x,int y){
if(rank[x]>rank[y]){
p[y]=x;
}else{
p[x]=y;
if(rank[x]==rank[y])
rank[y]++;
}
}
inline void union_set(int x,int y){
link_set(find_set(x),find_set(y));
}
inline bool is_same(int x,int y){
return find_set(x)==find_set(y);
}
inline void init_set(){
register int i;
for(i=1;i<=n;i++)
p[i]=i;
memset(rank,0,sizeof(rank));
}
int Cost[maxq];
vector<int> V[maxq];
struct Edge{
int u,v,d;
bool operator <(const Edge& x) const{
return d<x.d;
}
};
vector<Edge> bj;
vector<Edge> E;
vector<Edge> garbage;
int MST(int cnt,vector<Edge>& E,vector<Edge>& to){
if(!cnt)
return 0;
register int i,ans=0;
to.clear();
for(i=0;i<E.size();i++){
if(!is_same(E[i].u,E[i].v)){
union_set(E[i].u,E[i].v);
ans+=E[i].d;
to.push_back(E[i]);
if(!(--cnt))
break;
}
}
return ans;
}
int zb[maxn][2];
inline int EucSqr(int x,int y){
int t1=zb[x][0]-zb[y][0],t2=zb[x][1]-zb[y][1];
t1*=t1;
t2*=t2;
return t1+t2;
}
int main(){
int T,q,num,u;
register int i,j,k,cnt,temp,ans;
scanf("%d%d",&n,&q);
for(i=0;i<q;i++){
scanf("%d%d",&num,&Cost[i]);
V[i].clear();
while(num--){
scanf("%d",&u);
V[i].push_back(u);
}
}
for(i=1;i<=n;i++){
scanf("%d%d",&zb[i][0],&zb[i][1]);
}
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++){
bj.push_back((Edge){i,j,EucSqr(i,j)});
}
init_set();
sort(bj.begin(),bj.end());
ans=MST(n-1,bj,E);
for(i=0;i<(1<<q);i++){
init_set();
temp=0;
cnt=n-1;
for(j=0;j<q;j++)
if(i&(1<<j)){
temp+=Cost[j];
for(k=1;k<V[j].size();k++){
if(!is_same(V[j][k],V[j][0])){
union_set(V[j][k],V[j][0]);
cnt--;
}
}
}
ans=min(ans,temp+MST(cnt,E,garbage));
}
printf("%d\n",ans);
return 0;
}
[LA 3942]Remember the Word
Trie第一题……
首先，容我吐槽一下UVa这个OJ，速度特别感人（同学们可以实践一下）。
这个题最容易想到的是[tex]O(n^2)[/tex]的DP——对于[tex]S[i\ldots n][/tex]，枚举其前缀查是否为单词，然后转移。但是啊……对于[tex]n\le 300000[/tex]这种方法肯定会T飞。
然后我们可以考虑使用Trie优化DP。对于每个[tex]S[i\ldots n][/tex]，在前缀树中查找之，就能找到所有可以作为其前缀的单词。由于每个单词最大长度也只是100，所以查找会很快辣~
代码：
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=300005;
const int maxW=4005,maxL=105;
const int MOD=20071027;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define DREP(i,n) for(i=(n)-1;i>=0;i--)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
int n;
vector<int> AnsList;
namespace Trie{
const int maxnode=400005;
const int sigma_siz=26;
int Tree[maxnode][sigma_siz];
int val[maxnode];
int siz;
inline int idx(char c){
return c-'a';
}
inline void InitTrie(){
siz=0;
val[0]=0;
CL_ARR(Tree[0],0);
}
void Insert(char *s,int v){
register int u=0,n=strlen(s);
register int i,c;
REP(i,n){
c=idx(s[i]);
if(!Tree[u][c]){
siz++;
Tree[u][c]=siz;
val[siz]=0;
CL_ARR(Tree[siz],0);
}
u=Tree[u][c];
}
val[u]=v;
}
void Query(char *s,int len){
register int i,c,u=0;
AnsList.clear();
REP(i,len){
if(!s[i])
break;
c=idx(s[i]);
if(!Tree[u][c])
break;
u=Tree[u][c];
if(val[u])
AnsList.push_back(val[u]);
}
}
};
char Text[maxn];
int len[maxW];
char buf[maxL];
int d[maxn];
int main(){
register int i,j,Case=0;
int m;
while(scanf("%s%d",Text,&m)==2){
Case++;
n=strlen(Text);
Trie::InitTrie();
REP_B(i,m){
scanf("%s",buf);
len[i]=strlen(buf);
Trie::Insert(buf,i);
}
d[n]=1;
DREP(i,n){
d[i]=0;
Trie::Query(Text+i,n-i);
REP(j,AnsList.size()){
d[i]=(d[i]+d[i+len[AnsList[j]]])%MOD;
}
}
printf("Case %d: %d\n",Case,d[0]);
}
return 0;
}
