T1:
直接模拟，然后坐标相同的点的统计用sort来去重，用map等STL会TLE。。。
// MADE BY QT666
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=2000050;
struct data{
int x,y;
}g[N];
bool cmp(const data &a,const data &b){
if(a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
int n,flag,ans,x,y,xt,yt,cnt;
int main(){
freopen("loverfinding.in","r",stdin);
freopen("loverfinding.out","w",stdout);
scanf("%d%d%d%d%d",&n,&x,&y,&xt,&yt);
g[++cnt]=(data){x,y};
for(int i=1;i<=n;i++){
int dx,dy;scanf("%d%d",&dx,&dy);
int x1=g[cnt].x+dx,y1=g[cnt].y+dy;
g[++cnt]=(data){x1,y1};
if(x1==xt&&y1==yt){flag=1;break;}
}
if(!flag){puts("SingleDog");return 0;}
sort(g+1,g+1+cnt,cmp);g[0].x=2147483647,g[0].y=2147483647;
for(int i=1;i<=cnt;i++){
if(g[i].x==g[i-1].x&&g[i].y==g[i-1].y) continue;
ans++;
}
printf("%d\n",ans);
return 0;
}
T2:
跟洛谷的灾后重建是一样的,都是动态加点的floyd,只不过这个题要把点和询问sort一遍。。。
把点按照消费指数从小到大的加入图中，然后以当前加入的点为中转站来更新其余两点间的距离。。。
因为中转站是从小往大加入的，所以当前加入的中转站k，一定是i->k,k->j路径上的消费指数的最大值(除开起点和终点)。。。
那么我们对于每个询问，只把消费指数<=c的商店加入图中，然后查询跟一个点距离不超过d的点即可。。。
复杂度O(n^3+q*n) 或者每加入一个中转站就把所有人的f[i]数组排序，询问时二分，复杂度为O(n^3log+q*log)。。。
注意邻接矩阵的Inf要>1e9,不然可能不联通的点也被统计进了答案。。（memset(f,127/3,sizeof(f))只有40分）。。。
// MADE BY QT666
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#define RG register
using namespace std;
typedef long long ll;
const int N=2000050;
struct data{
int id,v;
}g[N];
struct Data{
int s,c,d,id;
}q[N];
int f[300][300],n,m,T,ans[N],tmp;
bool cmp(const data &a,const data &b){
if(a.v==b.v) return a.id<b.id;
return a.v<b.v;
}
bool cmp2(const Data &a,const Data &b){
return a.c<b.c;
}
int main(){
freopen("snackstore.in","r",stdin);
freopen("snackstore.out","w",stdout);
scanf("%d%d%d",&n,&m,&T);
for(RG int i=1;i<=n;i++) scanf("%d",&g[i].v),g[i].id=i;
//memset(f,127/3,sizeof(f));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
f[i][j]=1e9+1;
for(RG int i=1;i<=n;i++) f[i][i]=0;
for(RG int i=1;i<=m;i++){
int x,y,z;scanf("%d%d%d",&x,&y,&z);
f[x][y]=min(f[x][y],z);f[y][x]=min(f[y][x],z);
}
for(RG int i=1;i<=T;i++) scanf("%d%d%d",&q[i].s,&q[i].c,&q[i].d),q[i].id=i;
sort(g+1,g+1+n,cmp);sort(q+1,q+1+T,cmp2);int k=1;
for(RG int p=1;p<=T;p++){
while(g[k].v<=q[p].c&&k<=n){
for(RG int i=1;i<=n;i++)
for(RG int j=1;j<=n;j++){
f[i][j]=min(f[i][j],f[i][g[k].id]+f[g[k].id][j]);
}
k++;
}
RG int s=q[p].s,ret=0;
for(RG int i=1;i<=n;i++) if(i!=s&&f[s][i]<=q[p].d) ret++;
ans[q[p].id]=ret;
}
for(int i=1;i<=T;i++) printf("%d\n",ans[i]);
return 0;
}
T3:弃了。。。
T4:包含关系构成了一个DAG,那么可以用拓扑排序或者记忆化搜索来模拟题目的意思。
// MADE BY QT666
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
const int N=3000050;
const int Mod=1e9+7;
int head[N],to[N],nxt[N],cnt,v[N],du[N],n;
void lnk(int x,int y){
to[++cnt]=y,nxt[cnt]=head[x],head[x]=cnt;
}
queue<int> Q;
void topsort(){
while(!Q.empty()){
int x=Q.front();Q.pop();
for(int i=head[x];i;i=nxt[i]){
int y=to[i];(v[y]+=v[x])%=Mod;du[y]--;
if(du[y]==0) Q.push(y);
}
}
}
int main(){
freopen("three_squirrels.in","r",stdin);
freopen("three_squirrels.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
int k;scanf("%d",&k);
for(int j=1;j<=k;j++){int y;scanf("%d",&y);lnk(y,i);du[i]++;}
}
v[0]=1;
for(int i=0;i<=n;i++) if(!du[i]) Q.push(i);
topsort();printf("%d\n",v[n]);
return 0;
}
T5:
首先每一步跳得尽量的大答案一定会最大，因为(a+b)^2>a^2+b^2。。。
那么因为题目中相似子串的定义为前缀等于后缀，并且我们又要求一次跳得尽量的大，
所以每次跳跃其实就是在跳kmp的nxt数组(前缀等于后缀的最大长度)。。。所以先用kmp把nxt数组构出来。。。
然后我们要求两个前缀的距离最大，因为每个位置i，只会跳向nxt[i]，那么这种移动关系构成了一棵树(每个点最多一个父亲)
这就是所谓的kmp树。
那么我们要求两个前缀间的最长距离，就是树的直径。通过两边bfs求解。。
// MADE BY QT666
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
const int N=3000050;
char s[N];
int len,fail[N];
int head[N],to[N],nxt[N],cnt,vis[N];
ll v[N],dis[N];
void lnk(int x,int y,ll z){
to[++cnt]=y,nxt[cnt]=head[x],v[cnt]=z,head[x]=cnt;
to[++cnt]=x,nxt[cnt]=head[y],v[cnt]=z,head[y]=cnt;
}
void make_nxt() {
int j=0;
for(int i=2;i<=len;i++){
while(j&&s[j+1]!=s[i]) j=fail[j];
if(s[j+1]==s[i]) j++;
fail[i]=j;
}
}
queue<int> Q;
void bfs(int x){
for(int i=0;i<=len;i++) dis[i]=0,vis[i]=0;
Q.push(x);vis[x]=1;
while(!Q.empty()){
int x=Q.front();Q.pop();
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(!vis[y]) dis[y]=dis[x]+v[i],vis[y]=1,Q.push(y);
}
}
}
ll sqr(ll x){return 1ll*x*x;}
int main(){
freopen("savemzx.in","r",stdin);
freopen("savemzx.out","w",stdout);
scanf("%s",s+1);len=strlen(s+1);make_nxt();
for(int i=1;i<=len;i++) lnk(fail[i],i,sqr(1ll*i-fail[i]));
bfs(0);
int rt1=0;ll Max=0;for(int i=0;i<=len;i++) if(dis[i]>Max) rt1=i,Max=dis[i];
bfs(rt1);
int rt2=rt1;ll ans=0;for(int i=0;i<=len;i++) if(dis[i]>ans) rt2=i,ans=dis[i];
printf("%lld\n",ans);
return 0;
}
T6:
万万没有想到这竟然是两道题目强行拼起来的。。。
首先这个题要维护的就是区间积，然后第一问要%p1,第二问要%phi(p2)(降幂)。。。
然后7-10个测试点都是可以用exgcd来求逆元的(肯定是互质的)，所以可以直接用前缀积相除来实现。。。
前面的1-6个测试点直接用线段树来维护区间积，注意不能%0。。。
// MADE BY QT666
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=3000050;
int n,m,k,mod,Mod,M;
ll a[N],mul[N];
ll qpow(ll x,ll y,ll mo){ll ret=1;while(y){if(y&1) (ret*=x)%=mo;(x*=x)%=mo;y>>=1;} return ret;}
void exgcd(ll a,ll b,ll &x,ll &y){
if(!b) x=1,y=0;
else exgcd(b,(a+b)%b,y,x),y-=x*(a/b);
}
void getphi(ll P){
M=P;ll res=P;
for(ll i=2;i*i<=P;i++)
if(res%i==0) {
(M/=i)*=i-1;
while(res%i==0) res/=i;
}
if(res>1) (M/=res)*=res-1;
}
int ls[N],rs[N],rt,sz;
ll tr[N],tr2[N];
void pushup(int x){
tr[x]=(tr[ls[x]]*tr[rs[x]])%mod;
if(Mod) tr2[x]=(tr2[ls[x]]*tr2[rs[x]])%M;
}
void insert(int &x,int l,int r,int id){
if(!x) x=++sz;
if(l==r){tr[x]=tr2[x]=a[id];return;}
int mid=(l+r)>>1;
if(id<=mid) insert(ls[x],l,mid,id);
else insert(rs[x],mid+1,r,id);
pushup(x);
}
ll query1(int x,int l,int r,int xl,int xr){
if(xl<=l&&r<=xr){return tr[x];}
int mid=(l+r)>>1;
if(xr<=mid) return query1(ls[x],l,mid,xl,xr);
else if(xl>mid) return query1(rs[x],mid+1,r,xl,xr);
else return query1(ls[x],l,mid,xl,mid)*query1(rs[x],mid+1,r,mid+1,xr)%mod;
}
ll query2(int x,int l,int r,int xl,int xr){
if(xl<=l&&r<=xr){return tr2[x];}
int mid=(l+r)>>1;
if(xr<=mid) return query2(ls[x],l,mid,xl,xr);
else if(xl>mid) return query2(rs[x],mid+1,r,xl,xr);
else return query2(ls[x],l,mid,xl,mid)*query2(rs[x],mid+1,r,mid+1,xr)%M;
}
int main(){
freopen("chocolatebox.in","r",stdin);
freopen("chocolatebox.out","w",stdout);
scanf("%d%d%d%d%d",&n,&m,&k,&mod,&Mod);getphi(Mod);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
if(mod==1e9+7||mod==996919243){
mul[0]=1;
for(int i=1;i<=n;i++) (mul[i]=mul[i-1]*a[i])%=mod;
for(int i=1;i<=m;i++){
int type,l,r;scanf("%d%d%d",&type,&l,&r);
ll x,y;exgcd(mul[l-1],mod,x,y);ll inv=(x+mod)%mod;
ll ans=mul[r]*inv%mod;printf("%lld\n",ans);
}
}
else if(Mod==984359||Mod==988643){
mul[0]=1;
for(int i=1;i<=n;i++) (mul[i]=mul[i-1]*a[i])%=M;
for(int i=1;i<=m;i++){
int type,l,r;scanf("%d%d%d",&type,&l,&r);
ll x,y;exgcd(mul[l-1],M,x,y);ll inv=(x+M)%M;
ll ret=mul[r]*inv%M;ll ans=qpow(k,ret,Mod);printf("%lld\n",ans);
}
}
else if(n<=500000){
memset(tr,1,sizeof(tr));memset(tr2,1,sizeof(tr2));
for(int i=1;i<=n;i++) insert(rt,1,n,i);
for(int i=1;i<=m;i++){
int type,l,r;scanf("%d%d%d",&type,&l,&r);
if(type==1){
ll ret=query1(rt,1,n,l,r);
printf("%lld\n",ret);
}
else{
ll ret=query2(rt,1,n,l,r);
ll ans=qpow(k,ret,Mod);printf("%lld\n",ans);
}
}
}
return 0;
}
原文：http://www.cnblogs.com/qt666/p/7428472.html