0 10
-10
题意：
a,b两个球a的速度我va。
b的速度为vb。va>vb.va,vb同向且a在b的后面。
b的质量远大于a。
思路：
a肯定会撞b的。
正规的思路应该是动量守恒。机械能守恒。
然后blabla。我的思路是既然b的质量远大于a。那么b能够看做是一堵墙。而a撞墙的速度就是va-vb咯。因为弹性碰撞。撞墙后速度肯定是反向啦。所以速度就变为-(va-vb)
可是这个速度是相对墙的。所以转化为绝对速度就为-(va-vb)+vb。
具体见代码：
#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=100010;
typedef long long ll;
int main()
{
int v1,v2;
while(~scanf("%d%d",&v1,&v2))
{
printf("%d\n",2*v1-v2);
}
return 0;
}
3 3 0 0 0 0 100 0 0 0 0 2 2 1 1 1 1
4 4
哈利珀特学挖掘机了。那么问题来了。。
。。--||。一个n*m(50*50)的格子。一些格子数字大于0个数不超过10(看到这就懂了).你開始在左上角。
然后你要经过全部这些数字大于0的格子然后回到左上角。
然后问你最少须要多少步完毕这个目标。每步能够往四个方向走一步。
思路：
因为数字大于0的格子不超过10所以能够壮压。
这就是经典的TSP问题啦。
先对特殊格子编号然后bfs计算两两特殊格子的距离(步数).然后就TSP了。dp[i][s]表示眼下在i走到的格子状态为s。
具体见代码:
#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<queue>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=100010;
typedef long long ll;
int maze[55][55],hs[55][55],vis[55][55];
int dp[13][1<<12],dis[15][15],base[15];
int sx[55],sy[55],cnt,n,m;
int dx[]={0,-1,0,1};
int dy[]={-1,0,1,0};
struct node
{
int x,y,d;
};
queue<node> q;
void bfs(int id)
{
while(!q.empty())
q.pop();
node tt,nt;
memset(vis,0,sizeof vis);
tt.x=sx[id],tt.y=sy[id];
dis[id][id]=tt.d=0;
vis[tt.x][tt.y]=1;
q.push(tt);
int nx,ny,i;
while(!q.empty())
{
tt=q.front();
q.pop();
for(i=0;i<4;i++)
{
nx=tt.x+dx[i];
ny=tt.y+dy[i];
if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&!vis[nx][ny])
{
vis[nx][ny]=1;
nt.x=nx,nt.y=ny,nt.d=tt.d+1;
if(hs[nx][ny]!=-1)
dis[id][hs[nx][ny]]=nt.d;
q.push(nt);
}
}
}
}
int main()
{
int i,j,k,lim;
base[0]=1;
for(i=1;i<15;i++)
base[i]=base[i-1]<<1;
while(~scanf("%d%d",&n,&m))
{
cnt=0;
memset(hs,-1,sizeof hs);
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
scanf("%d",&maze[i][j]);
if(maze[i][j]||(i==1&&j==1))
{
sx[cnt]=i,sy[cnt]=j;
hs[i][j]=cnt++;
}
}
}
for(i=0;i<cnt;i++)
bfs(i);
memset(dp,0x3f,sizeof dp);
dp[0][0]=0;
lim=1<<cnt;
for(i=0;i<lim;i++)
{
for(j=0;j<cnt;j++)
{
if(dp[j][i]==INF)
continue;
for(k=0;k<cnt;k++)
{
if(i&base[k])
continue;
dp[k][i|base[k]]=min(dp[k][i|base[k]],dp[j][i]+dis[j][k]);
}
}
}
printf("%d\n",dp[0][lim-1]);
}
return 0;
}
3 1 0 1 3 3 2 1 2 1 1 0 1 3
8 6
题意：
有一栋楼。
每层楼有两扇门。
每扇门后面都有两条通向上一层楼的楼梯。楼的层数为n(5e4)。然后m个操作。
0 a b 询问a楼到b楼有多少种走法。
a<b。
1 x y z 改变x层楼y们到x+1层楼z门的楼梯状态(能够走。不能够走)。
思路：
c题赛后。读了下题。发现是大水题。
我们能够用一个2*2的矩阵来表示x层楼到x+1层楼的楼梯状态。1表示能够走。
0表示不能走。然后线段树维护区间乘积即可了。
仅仅是如今的线段树的结点为一个2*2的矩阵罢了。
单点更新区间查询。
具体见代码：
#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=50050;
const int mod=1e9+7;
typedef long long ll;
#define lson L,mid,ls
#define rson mid+1,R,rs
struct Matrix
{
int val[3][3];
Matrix(){ memset(val,0,sizeof val);}
inline Matrix operator *(const Matrix &op)
{
Matrix tt;
int i,j,k;
for(i=1;i<=2;i++)
for(j=1;j<=2;j++)
for(k=1;k<=2;k++)
tt.val[i][j]=(tt.val[i][j]+(ll)val[i][k]*op.val[k][j]%mod)%mod;
return tt;
}
} yb[maxn<<2];
void build(int L,int R,int rt)
{
if(L==R)
{
yb[rt].val[1][1]=1;
yb[rt].val[1][2]=1;
yb[rt].val[2][1]=1;
yb[rt].val[2][2]=1;
return;
}
int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
build(lson);
build(rson);
yb[rt]=yb[ls]*yb[rs];
}
void update(int L,int R,int rt,int p,int u,int v)
{
if(L==R)
{
yb[rt].val[u][v]^=1;
return;
}
int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
if(p<=mid)
update(lson,p,u,v);
else
update(rson,p,u,v);
yb[rt]=yb[ls]*yb[rs];
}
Matrix qu(int L,int R,int rt,int l,int r)
{
if(l<=L&&R<=r)
return yb[rt];
int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
Matrix tt;
tt.val[1][1]=tt.val[2][2]=1;
if(l<=mid)
tt=tt*qu(lson,l,r);
if(r>mid)
tt=tt*qu(rson,l,r);
return tt;
}
int main()
{
int n,m,x,y,z,i,op,ans;
while(~scanf("%d%d",&n,&m))
{
n--;
build(1,n,1);
for(i=1;i<=m;i++)
{
scanf("%d",&op);
if(!op)
{
scanf("%d%d",&x,&y);
Matrix tt=qu(1,n,1,x,y-1);
ans=0;
for(int j=1;j<=2;j++)
for(int k=1;k<=2;k++)
ans=(ans+tt.val[j][k])%mod;
printf("%d\n",ans);
}
else
{
scanf("%d%d%d",&x,&y,&z);
update(1,n,1,x,y,z);
}
}
}
return 0;
}
2 1 ACCGT TTT 1 2 4 4 AAATTT TTTCCC CCCGGG GGGAAA 1 2 2 3 3 4 4 1
1 3 3 3 3
给你n个由A,G,C,T构成的字符串。n个字符串的总长度不超过1e5.然后m个询问。
n。m<=1e5.每次询问a,b两个字符串。找到一个最长的串使得它是a的后缀。然后也是b的前缀。输出它的长度即可了。
思路：
第一想法就是后缀自己主动机。然后就开搞了。离线处理全部询问。把全部第一个串是a的b建个邻接表。然后依次处理每一个a。先对a建后缀自己主动机。然后对于串b在自己主动机上匹配就是了。匹配的最大长度的可接受态就是答案。然后一A。甚欢。比赛结束后才发现忘了记忆化。就是对每一个a链里的每一个b仅仅须要跑一遍即可了。哎。可惜发现的太晚了。还是无情的T了。
就上后再就200ms过了。。
。真是冤死了。时间复杂度。因为顶多对n各字符串都建一次后缀自己主动机。然后每次询问最多也仅仅能匹配a串那么长。
所以复杂度为2*总串长。
就O(n)咯。
具体见代码:
#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<map>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=100010;
typedef long long ll;
char txt[maxn<<1];
int st[maxn],ans[maxn];
map<int,int> mp;
struct node
{
node *f,*ch[30];
int len,ac;
void init()
{
ac=0;
memset(ch,0,sizeof ch);
}
}*root,*tail,sam[maxn<<1];
int tot,len,cnt;
struct qnode
{
qnode *next;
int v,id;
} ed[maxn<<1],*head[maxn];
void adde(int u,int v,int id)
{
ed[cnt].v=v;
ed[cnt].id=id;
ed[cnt].next=head[u];
head[u]=&ed[cnt++];
}
void init()
{
tot=0;
root=tail=&sam[tot++];
root->init();
root->len=0;
}
void Insert(int c)
{
node *p=tail,*np=&sam[tot++];
np->init(),np->len=p->len+1;
while(p&&!p->ch[c])
p->ch[c]=np,p=p->f;
tail=np;
if(!p)
np->f=root;
else
{
if(p->ch[c]->len==p->len+1)
np->f=p->ch[c];
else
{
node *q=p->ch[c],*nq=&sam[tot++];
*nq=*q;
nq->len=p->len+1;
q->f=np->f=nq;
while(p&&p->ch[c]==q)
p->ch[c]=nq,p=p->f;
}
}
}
int main()
{
int i,j,n,m,len,tl,u,v;
while(~scanf("%d%d",&n,&m))
{
len=cnt=0;
for(i=1;i<=n;i++)
{
st[i]=len;
scanf("%s",txt+len);
tl=strlen(txt+len);
len=len+tl+1;
}
memset(head,0,sizeof head);
for(i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
adde(u,v,i);
}
for(i=1;i<=n;i++)
{
init();
for(j=st[i];txt[j];j++)
Insert(txt[j]-'A');
for(node *p=tail;p!=NULL;p=p->f)
p->ac=1;
mp.clear();
for(qnode *q=head[i];q!=NULL;q=q->next)
{
if(mp.count(q->v))
{
ans[q->id]=mp[q->v];
continue;
}
node *p=root;
int ct=0,aa=0;
for(j=st[q->v];txt[j];j++)
if(p->ch[txt[j]-'A']!=NULL)
{
ct++,p=p->ch[txt[j]-'A'];
if(p->ac)
aa=max(aa,ct);
}
else
break;
ans[q->id]=aa;
mp[q->v]=aa;
}
}
for(i=1;i<=m;i++)
printf("%d\n",ans[i]);
}
return 0;
}
原文：http://www.cnblogs.com/mengfanrong/p/5213894.html