lov sharp () 关系 floyd head mat long
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;
- }
8.24-8.25 联赛模拟 解题报告
来源: http://www.bubuko.com/infodetail-2278277.html