【题目大意】
寻找最小字典序循环串起始位置
【算法分析】
围观了周源的论文。还是不懂，于是又来围观了某牛的blog，知道怎样做，但是感觉不能保证正确？
【CODE】
#include
int n;
char s[33333];
int minishow(){
int i=1,j=2,k=0;
while (i<=n && j<=n && k<=n){
if (s[i+k]==s[j+k]) k++;
else{
if (s[i+k]>s[j+k]) i+=k+1;
else j+=k+1;
if (i==j) i++;
k=0;
}
}
return min(i,j);
}
int main(){
int Tc;
scanf("%d",&Tc);
for (int i=0;i
n=strlen(s+1);
for (int j=n+1;j<=n*2;j++) s[j]=s[j-n];
cout << minishow() << endl;
}
}
这次我们比较水。。。
我们队一共A了3题。
A:http://hi.baidu.com/edwardmj/blog/item/9e475eec782c01252df53431.html
C:http://hi.baidu.com/edwardmj/blog/item/370c5fc87d889c8ac9176806.html
F:http://hi.baidu.com/edwardmj/blog/item/6ae33d344481423d0a55a901.html
这次没啥好说的。。。我把这3题AC了以后，我们队就没有再出题。。。
其实那个三国杀可以搞一下，但是CZM搞了将近3个小时。。。没有AC。
然后记录一下YY其它题的经历。
D：题的话第一反应是后缀数组，但是N太大了，可能令人垂涎的3xian大神的模板可以过吧。。。
然后pass掉这个想法以后，就YY一下类似自动机那种。
由于只含小写字母，字典序最小的话，每次从’a’开始尝试加入字母。然后判定这个小串是否在主串中出现。
然后加到小串长度为N的时候就结束。然后次数的话，就KMP一次就可以知道了。实现这个算法的前提是:能在O(1)或者平摊O(1)的时间复杂度内判定一个串是否在主串中出现。
很遗憾，我做不到。。。于是挂掉。。。
E：就是要将图旋转45°，然后并差集或者说BFS填连通块应该都可以。但是那个旋转不会搞= =。。。
G：几乎可以肯定是插头DP了。。。但是转移爆难。。。无人AC。
H：我没看过题。。。CZM一直在搞，没搞出来。。。
哎，比较餐具。果然我们太弱了。
rank：18
http://acm.hdu.edu.cn/vip/contest_ranklist.php?cid=276&page=1
【题目大意】
参见NOIP的传纸条。
【算法分析】
直接费用流~
对于时间复杂度分析一下：由于只增广两次，所以复杂度是O(2*SPFA)。
不需要担心点太多了~
【CODE】
#include
const int E=2160111;
const int INF=1000000000;
struct gtp{int x,y,next,op,w,c;}g[E];
int n,e,S,T,cost;
int pos[622][622],ls[N],d[N],v[N],list[N],fa[N];
inline void addedge(int x,int y,int c,int w){
e++;
g[e].x=x; g[e].y=y; g[e].c=c; g[e].w=w;
g[e].next=ls[x]; ls[x]=e; g[e].op=e+1;
e++;
g[e].x=y; g[e].y=x; g[e].c=0; g[e].w=-w;
g[e].next=ls[y]; ls[y]=e; g[e].op=e-1;
}
void init(){
int i,j,tmp=0,w;
e=0;
for (i=1;i<=2*n*n+2;i++) ls[i]=0;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
pos[i][j]=++tmp;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++){
scanf("%d",&w);
addedge(pos[i][j],pos[i][j]+n*n,1,w);
if (i
S=n*n*2+1; T=S+1;
addedge(S,1,2,0);
addedge(n*n*2,T,2,0);
addedge(1,n*n+1,1,0);
addedge(n*n,n*n*2,1,0);
}
void spfa(){
for (int i=1;i<=T;i++){
d[i]=-INF;
v[i]=0;
}
int head=0,tail=1,t;
list[1]=S; v[S]=1; d[S]=0;
while (head!=tail){
head++; if (head>=N) head=0;
for (t=ls[list[head]];t;t=g[t].next)
if (g[t].c && d[g[t].x]+g[t].w>d[g[t].y]){
d[g[t].y]=d[g[t].x]+g[t].w;
fa[g[t].y]=t;
if (!v[g[t].y]){
v[g[t].y]=1;
tail++; if (tail>=N) tail=0;
list[tail]=g[t].y;
}
}
v[list[head]]=0;
}
}
void change(){
cost+=d[T];
for (int i=T;i!=S;i=g[fa[i]].x){
g[fa[i]].c–;
g[g[fa[i]].op].c++;
}
}
void work(){
cost=0;
spfa();
change();
spfa();
change();
}
int main(){
while (scanf("%d",&n)!=EOF){
init();
work();
printf("%dn",cost);
}
}
【题目大意】
定义点与点之间的距离为max(|Xi-Xj|,|Yi-Yj|)
给定N个点，将这N个点中每个点与最近点的距离加起来，输出SUM。
【算法分析】
算法1：
算了下复杂度O(N^2)的话加些优化应该可以卡过。
于是我把他们按x排序，x相等的按y排序。
然后枚举当前点i，并向前和向后枚举点j，如果出现abs(X[j]-X[i])>=now （其它now为当前答案），那么可以break退出循环。（最优化剪枝）
然后这样就可以9000MS左右AC了。
算法2：
同算法1那样排序。
再按X坐标离散化。
然后枚举当前点i，并二分答案（当前最短距离）。
问题转化为看是否存在点(X[j],Y[j])，使得abs(X[j]-X[i])<=ANS 且 abs(Y[j]-Y[i])<=ANS
于是就可以以X轴为线段树所划分的区间建立一棵线段树，线段树上再建立一棵以Y坐标为key值的平衡树。
然后在上面进行查找。每次查找的复杂度是O((lgN)^2)。
加上二分答案，每个点的处理复杂度为O((lgN)^3)。
所以总时间复杂度为O(N (lgN)^3 )。
空间复杂度为O(NlgN)。
因为最同一深度的线段树区间下，一个点只能出现在一个区间内。所以一个点最多出现lgN次。所以空间复杂度不是问题。
但是这个算法编程复杂度可能比较高。如果用STL的 【其它】由于我不会STL，所以算法2就不写了。。。 【CODE】 #include inline bool cmp(type x,type y){ void input(){ void work(){ j=i+1; int main(){
const int N=101111;
const int INF=0x7FFFFFFF;
int n;
struct type{int x,y;}L[N];
long long ans;
if (x.x
if (x.y
}
for (int i=1;i<=n;i++)
scanf("%d%d",&L[i].x,&L[i].y);
sort(&L[1],&L[n+1],cmp);
}
ans=0;
int i,j,now;
for (i=1;i<=n;i++){
now=INF;
j=i-1;
while (j){
if (L[i].x-L[j].x>=now) break;
now j–;
}
while (j<=n){
if (L[j].x-L[i].x>=now) break;
now j++;
}
ans+=now;
}
cout << ans << endl;
}
while (scanf("%d",&n)!=EOF){
input();
work();
}
}
【题目大意】
有点已经成一个块了，让你加最少费用的边，使得它整个图成为一个连通块。
【算法分析】
经典最小生成树。
用并差集处理块，然后排序一下搞个kruskal。
但是很容易TLE。于是我加了那个启发式合并。
【其它】
尽管如此，我用G++交还是TLE,C++500多MS。
可能并差集写成非递归会好点。
【CODE】
#include
const int N=1000000;
int Tc,n,m,k,done,ans;
int f[N],d[N][3];
int num[N];
int gf(int p){
if (f[p]==p) return p;
f[p]=gf(f[p]);
return f[p];
}
void input(){
done=0; ans=0;
int i,j,t,one,x;
scanf("%d%d%d",&n,&m,&k);
for (i=1;i<=n;i++){
f[i]=i;
num[i]=1;
}
for (i=1;i<=m;i++)
scanf("%d%d%d",&d[i][0],&d[i][1],&d[i][2]);
for (i=1;i<=k;i++){
scanf("%d%d",&t,&one);
for (j=1;j
if (gf(x)!=gf(one)){
if (num[f[x]]
f[f[x]]=f[one];
}
else{
num[f[x]]+=num[f[one]];
f[f[one]]=f[x];
}
done++;
}
}
}
}
int cmp(const void *x,const void *y){
return ((int *)x)[2]-((int *)y)[2];
}
void work(){
if (done==n-1) return;
qsort(d[1],m,sizeof(int)*3,cmp);
for (int i=1;i<=m;i++){
int &x=d[i][0],&y=d[i][1];
if (gf(x)!=gf(y)){
if (num[f[x]]
f[f[x]]=f[y];
}
else{
num[f[x]]+=num[f[y]];
f[f[y]]=f[x];
}
done++;
ans+=d[i][2];
if (done==n-1) return;
}
}
}
void output(){
if (done==n-1) printf("%dn",ans);
else printf("-1n");
}
int main(){
cin >> Tc;
for (int i=1;i<=Tc;i++){
input();
work();
output();
}
}