BZOJ3522: [Poi2014]Hotel
Aug 18, 2015 08:01:14 PM
题解:
考虑三个点在树上的形态:
(1)成一条链(其实就是中心是三个点中的一个点)
(2)存在一个唯一中心连接三个点，且中心到三个点的路径除了中心之外不相交
(定义自己脑补一下吧...)
显然只有在(2)情况下,并且唯一中心到三个点的路径长度相等才能满足条件.
我们直接枚举唯一中心,以其为根做有根树,则三个点必须分布在不同的子树中,且深度相同.
这个就很容易搞了,看代码搞搞就行了.
代码:
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
#define N 5010
int head[N],next[N<<1],end[N<<1];
inline void addedge(int a,int b){
static int q=1;
end[q]=b;
next[q]=head[a];
head[a]=q++;
}
inline void make(int a,int b){
addedge(a,b);
addedge(b,a);
}
int sum1[N];
ll sum2[N];
struct Array{
int a[N],t[N],tclock;
inline int operator[](int x){
if(t[x]!=tclock){
t[x]=tclock;
a[x]=0;
}
return a[x];
}
inline void add(int x){
if(t[x]!=tclock){
t[x]=tclock;
a[x]=0;
}
++a[x];
}
}temp;
int max_dep;
inline void dfs(int x,int fa,int dep){
temp.add(dep);
max_dep=max(max_dep,dep);
for(int j=head[x];j;j=next[j])
if(end[j]!=fa)
dfs(end[j],x,dep+1);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("tt.in","r",stdin);
#endif
int n;
scanf("%d",&n);
int i,j,k,a,b;
for(i=1;i<n;++i){
scanf("%d%d",&a,&b);
make(a,b);
}
ll ans=0;
int son;
for(i=1;i<=n;++i){
memset(sum1,0,sizeof sum1);
memset(sum2,0,sizeof sum2);
for(son=1,j=head[i];j;j=next[j],++son){
++temp.tclock;
max_dep=0;
dfs(end[j],i,1);
for(k=1;k<=max_dep;++k){
if(son>=3)
ans+=sum2[k]*temp[k];
sum2[k]+=temp[k]*sum1[k];
sum1[k]+=temp[k];
}
}
}
cout<<ans<<endl;
return 0;
}
BZOJ1704: [Usaco2007 Mar]Face The Right Way 自动转身机
Aug 18, 2015 07:53:41 PM
题解:
首先枚举$k$,那我们需要知道给定$k$,最少进行多少次操作.
显然应该从小到大进行扫描,考虑当前位置$i$,若颜色不对,则反转$[i,i+k-1]$.
然后再判定剩下的位置颜色对不对.
这个过程可以利用单调队列轻松实现,详情见代码.
代码:
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 5010
bool a[N];
int q[N],fr,ta;
int main(){
int n;
scanf("%d",&n);
int i,j;
char s[10];
for(i=1;i<=n;++i){
scanf("%s",s);
a[i]=(s[0]=='F');
}
int ans=0x3f3f3f3f,temp,k;
for(i=1;i<=n;++i){
fr=ta=0;
for(temp=0,j=1;j+i-1<=n;++j){
while(fr!=ta&&q[fr]+i-1<j)
++fr;
if((((ta-fr)&1)^a[j])==0){
q[ta++]=j;
++temp;
}
}
bool ok=1;
for(j=n+2-i;j<=n;++j){
while(fr!=ta&&q[fr]+i-1<j)
++fr;
if((((ta-fr)&1)^a[j])==0)
ok=0;
}
if(ok){
if(temp<ans){
ans=temp;
k=i;
}
}
}
cout<<k<<" "<<ans<<endl;
return 0;
}
BZOJ1819: [JSOI]Word Query电子字典 暴力+Trie树
Mar 06, 2015 03:11:42 PM
思路:
对于每次询问,暴力枚举所有编辑距离为1的串,然后用Trie判断存不存在并判重.
妈呀这是\(O(10000*26*20*20)=10^8\),居然也能过.
其实用Hash感觉就好多了.
有没有更好的方法?目前没想出来.
#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
int ch[200010][26],end[200010],vis[200010],cnt;
char s[21],ss[22];
int tclock;
inline bool judge(int len){
int p=0;
for(int i=0;i<len;++i){
if(!ch[p][ss[i]-'a'])return 0;
p=ch[p][ss[i]-'a'];
}
if(!end[p])return 0;
if(vis[p]!=tclock)return vis[p]=tclock,1;else return 0;
}
int main(){
int n,m;scanf("%d%d",&n,&m);
register int i,j,k;
int len,p,y;
while(n--){
scanf("%s",s);
len=strlen(s),p=0;
for(i=0;i<len;++i){
y=s[i]-'a';
if(!ch[p][y])ch[p][y]=++cnt;
p=ch[p][y];
}
end[p]=1;
}
int id;
while(m--){
scanf("%s",s);
len=strlen(s);
p=0;
bool find=1;
for(i=0;i<len;++i){
y=s[i]-'a';
if(!ch[p][y]){find=0;break;}
else p=ch[p][y];
}
if(find&&end[p]){puts("-1");continue;}
int re=0;
++tclock;
if(len>1){
for(i=0;i<len;++i){
id=0;
for(j=0;j<i;++j)ss[id++]=s[j];
for(j=i+1;j<len;++j)ss[id++]=s[j];
re+=judge(len-1);
}
}
for(i=0;i<len;++i)for(j=0;j<26;++j)if(j!=s[i]-'a'){
memcpy(ss,s,sizeof s),ss[i]='a'+j;
re+=judge(len);
}
for(i=0;i<=len;++i)for(j=0;j<26;++j){
id=0;
for(k=0;k<i;++k)ss[id++]=s[k];
ss[id++]='a'+j;
for(k=i;k<len;++k)ss[id++]=s[k];
re+=judge(len+1);
}
printf("%d\n",re);
}
return 0;
}
BZOJ1570:[JSOI2008]Blue Mary的旅行 暴力+网络流
Mar 06, 2015 02:05:50 PM
思路:
暴力枚举答案,然后将点分层,边总是从该层连向下一层.
然后判断最大流是不是满足题意.
具体连边看代码.
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF ~0U>>1
struct Solver{
static const int V=50*100;
static const int E=2450*100*2;
int head[V],next[E],end[E],flow[E],ind;
int d[V],gap[V],stk[V],top,cur[V];
inline void reset(){
ind=top=0,memset(head,-1,sizeof head);
}
inline void addedge(int a,int b,int f){
int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;
}
inline void make(int a,int b,int f){
/*printf("%d %d %d\n",a,b,f);*/addedge(a,b,f),addedge(b,a,0);
}
inline void bfs(int T){
static int q[V];int fr=0,ta=0;
memset(gap,0,sizeof gap),memset(d,-1,sizeof d),++gap[d[T]=0],q[ta++]=T;
while(fr^ta){
int i=q[fr++];
for(int j=head[i];j!=-1;j=next[j])if(d[end[j]]==-1)
++gap[d[end[j]]=d[i]+1],q[ta++]=end[j];
}
}
inline int Maxflow(int S,int T){
bfs(T),memcpy(cur,head,sizeof cur);
int re=0,Min,ins,i,u=S;
while(d[S]<T-S+1){
if(u==T){
for(Min=INF,i=0;i<top;++i)if(Min>flow[stk[i]])ins=i,Min=flow[stk[i]];
for(re+=Min,i=0;i<top;++i)flow[stk[i]]-=Min,flow[stk[i]^1]+=Min;
u=end[stk[top=ins]^1];
}
if(u!=T&&!gap[d[u]-1])break;
bool find=0;
for(int&j=cur[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]+1==d[u]){
find=1,ins=j;break;
}
if(find){stk[top++]=cur[u]=ins,u=end[ins];}
else{
Min=T-S+1;
for(int j=head[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]<Min)
cur[u]=j,Min=d[end[j]];
if(!--gap[d[u]])break;
++gap[d[u]=Min+1];
if(u!=S)u=end[stk[--top]^1];
}
}
return re;
}
}Stg;
struct Edge{
int u,v,f;
}E[2510];
#define get(x,dep) ((dep-1)*n+x)
int main(){
int n,m,T;scanf("%d%d%d",&n,&m,&T);
register int i,j;
for(i=1;i<=m;++i)scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].f);
int re;
for(re=1;;++re){
Stg.reset();
for(i=1;i<=m;++i)for(j=1;j<=re;++j)Stg.make(get(E[i].u,j),get(E[i].v,j+1),E[i].f);
for(j=1;j<=re;++j)Stg.make(0,get(1,j),INF);
for(j=2;j<=re+1;++j)Stg.make(get(n,j),n*(re+1)+1,INF);
int now=Stg.Maxflow(0,n*(re+1)+1);
//printf("%d\n",now);
if(now>=T)break;
}
printf("%d\n",re);
return 0;
}
BZOJ2338:[HNOI2011]数矩形 暴力+计算几何
Feb 03, 2015 08:58:01 AM
思路:
首先搞出所有的线段,然后中点相同的放在一起,并且长度相同的放在一起.
那么,中点相同并且长度相同,这两个线段就能够构成一个矩形.
这样的线段不会超过\(O(n)\)条,所以我们可以直接暴力枚举.
(其实我觉得可以把所有的线段以中点为原点进行极角序排序,然后我们就是要找出两条线段使得它们之间的夹角尽可能接近90,这大概就可以线性扫描了.)
本代码完全避免了精度问题!速来点赞!
#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
struct Point{
int x,y;
Point(){}
Point(int _x,int _y):x(_x),y(_y){}
bool operator<(const Point&B)const{return(x!=B.x)?x<B.x:y<B.y;}
bool operator!=(const Point&B)const{return(x!=B.x)||(y!=B.y);}
Point operator+(const Point&B)const{return Point(x+B.x,y+B.y);}
Point operator-(const Point&B)const{return Point(B.x-x,B.y-y);}
};
LL Cross(const Point&a,const Point&b){return(LL)a.x*b.y-(LL)a.y*b.x;}
LL Getans(Point p1,Point p2,Point q1,Point q2){
LL res=Cross(p1-q1,p1-q2);
return res<0?-res:res;
}
int gcd(int a,int b){return(!b)?a:gcd(b,a%b);}
struct Double{
int x,y;
Double(){}
Double(int _x,int _y):x(_x),y(_y){}
bool operator<(const Double&B)const{return(LL)x*B.y<(LL)y*B.x;}
};
#define N 1510
struct Segment{
Point P1,P2;LL dis;
bool insequal(const Segment&B)const{
if(P1.x+P2.x!=B.P1.x+B.P2.x)return 0;
if(P1.y+P2.y!=B.P1.y+B.P2.y)return 0;
return 1;
}
bool operator<(const Segment&B)const{
if(P1.x+P2.x!=B.P1.x+B.P2.x)return P1.x+P2.x<B.P1.x+B.P2.x;
if(P1.y+P2.y!=B.P1.y+B.P2.y)return P1.y+P2.y<B.P1.y+B.P2.y;
return dis<B.dis;
}
bool operator==(const Segment&B)const{return insequal(B)&&dis==B.dis;}
}S[N*N>>1];int id;
int x[N],y[N],n;
inline LL sqr(int x){
return(LL)x*x;
}
int main(){
scanf("%d",&n);register int i,j,k,p;for(i=1;i<=n;++i)scanf("%d%d",&x[i],&y[i]);
for(i=1;i<=n;++i)for(j=i+1;j<=n;++j)++id,S[id].P1=Point(x[i],y[i]),S[id].P2=Point(x[j],y[j]),S[id].dis=sqr(x[i]-x[j])+sqr(y[i]-y[j]);
sort(S+1,S+id+1);
LL res=0;
for(i=1;i<=id;i=j+1){
for(j=i;j!=id&&S[j]==S[j+1];++j);
for(k=i;k<=j;++k)for(p=k+1;p<=j;++p)res=max(res,Getans(S[k].P1,S[k].P2,S[p].P1,S[p].P2));
}
cout<<res<<endl;
return 0;
}
BZOJ3251:树上三角形 数学+暴力
Feb 02, 2015 08:00:15 AM
思路:
考虑不存在三角形的情况:也就是说,任意选择三个数,总有一个最大的数不小于剩下两个数的总和.
我们想到一个的数列:斐波那契数列.
那么权值均在题目给定数据范围内的数列有多长?至多有\(log(Max)\)项.
如果超过这些项,就会在两个数之间插入某一个数,那么这三个数就是必定满足三角形条件的.(有点意识流)
总之如果总共有不超过\(log(Max)\)个数暴力判定,否则直接输出\(Y\).
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 100010
int head[N],next[N<<1],end[N<<1];
inline void addedge(int a,int b){static int q=1;end[q]=b,next[q]=head[a],head[a]=q++;}
inline void make(int a,int b){addedge(a,b),addedge(b,a);}
int w[N];
int pa[N][16],dep[N];
inline void dfs(int x,int fa){
for(int j=head[x];j;j=next[j])if(end[j]!=fa)dep[end[j]]=dep[x]+1,pa[end[j]][0]=x,dfs(end[j],x);
}
int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int i=15;i>=0;--i)if(dep[pa[x][i]]>=dep[y])x=pa[x][i];
if(x==y)return x;
for(int i=15;i>=0;--i)if(pa[x][i]!=pa[y][i])x=pa[x][i],y=pa[y][i];
return pa[x][0];
}
int seq[51],id;
inline bool judge(int a,int b,int c){
long long A=a,B=b,C=c;
return A+B>C&&B+C>A&&A+C>B;
}
int main(){
int n,m;scanf("%d%d",&n,&m);register int i,j,k;for(i=1;i<=n;++i)scanf("%d",&w[i]);
int a,b;for(i=1;i<n;++i)scanf("%d%d",&a,&b),make(a,b);
dep[1]=1,dfs(1,-1);
for(j=1;j<=15;++j)for(i=1;i<=n;++i)pa[i][j]=pa[pa[i][j-1]][j-1];
int t;
while(m--){
scanf("%d%d%d",&t,&a,&b);
if(t==0){
int Lca=lca(a,b),nums=dep[a]+dep[b]-2*dep[Lca]+1;
if(nums<=40){
for(id=0;a!=Lca;a=pa[a][0])seq[++id]=w[a];
for(;b!=Lca;b=pa[b][0])seq[++id]=w[b];
seq[++id]=w[Lca];
bool ok=0;
for(i=1;i<=id;++i)for(j=i+1;j<=id;++j)for(k=j+1;k<=id;++k)if(judge(seq[i],seq[j],seq[k]))ok=1;
if(ok)puts("Y");else puts("N");
}else puts("Y");
}else w[a]=b;
}
return 0;
}
BZOJ1406:[AHOI2007]密码箱 数学+暴力
Feb 02, 2015 07:52:40 AM
思路:
令\(x\)是一个可行答案,有\(x^2\%n=1\),即\((x-1)(x+1)=kn(k\in{Z})\).
显然我们可以令\(x-1=k_1n_1,x+1=k_2n_2,k=k_1k_2,n=n_1n_2\).(交换一下也是可以的)
那么我们就可以枚举所有的\(n_1\),看一看他能够表达出的\(x+1\)或是\(x-1\)是不是一个合法答案.我们用一个哈希表来支持插入.最后输出即可.
但是我们发现枚举所有的\(n_1\)(n的约数)显然是要超时的.因此我们只枚举\(n_1\geq{\sqrt{n}}\)的\(n_1\).这样单次枚举的复杂度为\(\sqrt{n}\),而且这样的约数非常少,这样就可以通过了.
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
static const int mod=(1e5)+7;
struct HashSet{
int head[mod],v[200010],next[200010],ind;
void reset(){ind=0,memset(head,-1,sizeof head);}
void insert(int x){
int ins=x%mod;
for(int j=head[ins];j!=-1;j=next[j])if(v[j]==x)return;
v[ind]=x,next[ind]=head[ins],head[ins]=ind++;
}
}S;
int n;
void Solve(int x){
for(int d=x;d<n-1;d+=x)if((long long)d*(d+2)%n==0)S.insert(d+1);
for(int d=x;d<=n;d+=x)if(d-2>=1&&(long long)d*(d-2)%n==0)S.insert(d-1);
}
int main(){
scanf("%d",&n);
if(n==1)puts("NONE");
else{
S.reset(),S.insert(1);
for(int i=1;i*i<=n;++i)if(n%i==0)Solve(max(i,n/i));
sort(S.v,S.v+S.ind);
for(int i=0;i<S.ind;++i)printf("%d\n",S.v[i]);
}
return 0;
}