[关闭]
@suixinhita 2017-10-24T09:41:43.000000Z 字数 4915 阅读 1179

10.21周六例行测试

反正...一旦开始了挂挂挂系列，就一时半会停不下来吧...

T1

此处输入图片的描述

没谁是傻的吧...所以我们很清楚要用循环节了。
找出循环节之后，我们就可以搞事情了。
我们首先明确地知道，中间的循环节里面，每一个循环节显然都是出一个数的。
然后我们把最前面和最后面的摘出来跑一下。
中间循环节直接补上就可以了。

  1. //有的数据可以卡掉这个程序。
  2. #include<map>
  3. #include<cstdio>
  4. #include<algorithm>
  5. #define ll long long 
  6. using namespace std;
  7. const int N=1e5+5;
  8. int a[N],A,B,C,D;
  9. int q[N],dp[N],cnt;
  10. ll n,ans,an[N];
  11. map<int,int> M;
  13. void solve()
  14. {
  15.     int len=1,i=1;
  16.     ll p=min((ll)N-1,n);
  17.     for(i=1;i<=p;++i)
  18.     {
  19.         if(i!=1)    a[i]=(A*a[i-1]*a[i-1]%D+B*a[i-1]+C)%D;
  20.         if(M[a[i]]!=0)  
  21.         {
  22.             len=i-M[a[i]];break;
  23.         }
  24.         else    M[a[i]]=i;
  25.     }
  26.     for(int j=i+1;j<=i+len-1;++j)
  27.         a[j]=(A*a[j-1]*a[j-1]%D+B*a[j-1]+C)%D;
  28.     ll k=n-(ll)i+1-(((n-(ll)i+1)/(ll)len))*(ll)len;
  29.     int cnt=i+len-1;
  30.     for(int j=1;j<=k;++j)
  31.     {
  32.         int f=i+j-1;
  33.         a[++cnt]=a[f];
  34.     }
  35.     for(int j=1;j<=cnt;++j)
  36.     {
  37.         dp[j]=1;
  38.         for(int k=1;k<j;++k)
  39.             if(a[k]<=a[j])  dp[j]=max(dp[j],dp[k]+1);
  40.         an[j]=max(an[j-1],(ll)dp[j]);
  41.     }
  42.     int maxx=0;
  43.     ans=(n-(ll)cnt)/(ll)len+(ll)dp[cnt];
  44.     if(p==n)    ans=an[i];
  45.     printf("%lld\n",ans);
  46. }
  48. int main()
  49. {
  50.     freopen("lis.in","r",stdin);
  51.     freopen("lis.out","w",stdout);
  52.     scanf("%lld",&n);
  53.     scanf("%d%d%d%d%d",&a[1],&A,&B,&C,&D);
  54.     solve();
  55.     return 0;
  56. }

T2

此处输入图片的描述

这道题是我这段时间最尴尬的题，毕竟考场就知道该怎么写，结果剩下10min没调出来，gg.

其实看看数据返回很容易猜到，直接对于最小的取模，算出每一个模数需要的最小的地方就可以了。
这个就是个最短路。
注意：对于 的情况，我们直接苟一波bfs

  1. #include<queue>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. #define ll long long
  6. using namespace std;
  7. const ll N=1e5+5;
  8. const ll inf=0x3f3f3f3f;
  9. struct data{
  10.     int c,u;
  11. };
  12. ll V[N],dis[55][N],dist[N*30];
  13. bool ind[55][N];
  14. int L,C,ret[N],m,n,Q;
  16. void bfs()
  17. {
  18.     memset(dist,0x7f,sizeof(dist));
  19.     queue<int> q;
  20.     dist[0]=0;
  21.     q.push(0);
  22.     while(!q.empty())
  23.     {
  24.         int u=q.front();q.pop();
  25.         if(dist[u]>=C)  continue;
  26.         for(int i=1;i<=n;++i)
  27.         {
  28.             ll v=u+V[i];
  29.             if((dist[v]<dist[u]+1))
  30.             {
  31.                 dist[v]=dist[u]+1;
  32.                 q.push(v);
  33.             }
  34.         }
  35.     }
  36.     for(int i=1;i<=n;++i)   if(dist[i]>C)   dist[i]=inf;
  37. }
  40. void spfa()
  41. {
  42.     queue<data> q;
  43.     memset(dis,0x7f,sizeof(dis));
  44.     dis[0][0]=0,ind[0][0]=1;
  45.     data k;k.u=0,k.c=0;
  46.     q.push(k);
  47.     while(!q.empty())
  48.     {
  49.         data x=q.front();q.pop();
  50.         int u=x.u,c=x.c;data f;f=x;
  51.         for(int i=1;i<=n;++i)
  52.         {
  53.             //printf("L  %lld\n",L);
  54.             int v=(u+ret[i])%Q;
  55.         //  printf("%lld %lld\n",V[i],L);
  56.             if(V[i]>=L) f.c=c+1;
  57.         /*  if(u==6&&(i==2||i==3))
  58.             {
  59.                 puts("GG"),printf("%lld %lld\n",v,f.c),printf("%lld L  %lld\n",V[i],L);
  60.             }
  61.             printf("%lld %lld\n",V[i],L);
  62.         */  if(f.c>C)   continue;
  63.             if(dis[f.c][v]>dis[c][u]+V[i])
  64.             {
  65.                 f.u=v;
  66.                 dis[f.c][v]=dis[c][u]+V[i];
  67.                 if(!ind[f.c][v])    q.push(f),ind[f.c][v]=1;
  68.             }
  69.         }
  70.         ind[c][u]=0;
  71.     }
  72.     for(int i=0;i<Q;++i)
  73.         for(int c=0;c<=C;++c)
  74.             dis[0][i]=min(dis[0][i],dis[c][i]);
  75. }
  77. bool query(ll w)
  78. {
  79.     ll p=w%Q;
  80.     if(dis[0][p]>w) return 0;
  81.     return 1;
  82. }
  84. int main()
  85. {
  86. //  freopen("1.txt","r",stdin);
  87. //  freopen("11.txt","w",stdout);
  88.     ll k;
  89.     scanf("%d%d",&n,&m);
  90.     for(int i=1;i<=n;++i)   scanf("%lld",&V[i]);
  91.     sort(V+1,V+1+n);
  92.     Q=V[1];
  93.     for(int i=1;i<=n;++i)   ret[i]=V[i]%Q;
  94.     scanf("%d%d",&L,&C);
  95.     //printf("------------------------\n%lld\n",L);
  96.     if(V[1]>L)  bfs();
  97.     else    spfa();
  98.     for(int i=1;i<=m;++i)
  99.     {
  100.         scanf("%lld",&k);
  101.         if(query(k))    puts("Yes");
  102.         else    puts("No");
  103.     }
  104.     return 0;
  105. }

T3

此处输入图片的描述

裸树剖，于是开心的没写对...

就是，一旦修改了一个节点，就可以直接修改一个子树和他上面的所有其他值（见图）
此处输入图片的描述

所以我就不多说了。

  1. #include<cstdio>
  2. #include<algorithm>
  3. using namespace std;
  4. const int N=1e6+5;
  5. struct data{
  6.     int to,next;
  7. }e[N];
  8. int head[N],gs;
  9. void add(int fr,int to)
  10. {
  11.     e[++gs].to=to,e[gs].next=head[fr],head[fr]=gs;
  12. }
  14. int num[N],n,m,v[N];
  16. struct node{
  17.     int mx,tag;
  18. };
  19. class st
  20. {
  21.     private:
  22.         node    t[N<<3];
  23.         int a,b,delt;
  24.         void update(int x)
  25.         {
  26.             int ls=x<<1,rs=x<<1^1;
  27.             if(t[ls].mx<t[rs].mx)   t[x].mx=t[rs].mx;
  28.             else    t[x].mx=t[ls].mx;
  29.         }
  30.         void pushdown(int x)
  31.         {
  32.             int ls=x<<1,rs=x<<1^1;
  33.             if(t[ls].tag<t[x].tag)  t[ls].tag=t[x].tag;
  34.             if(t[rs].tag<t[x].tag)  t[rs].tag=t[x].tag;
  35.             if(t[ls].mx<t[ls].tag)  t[ls].mx=t[ls].tag;
  36.             if(t[rs].mx<t[rs].tag)  t[rs].mx=t[rs].tag;
  37.         //  t[x].tag=t[x].tagp=0;
  38.         }
  39.         void change(int now,int l,int r)
  40.         {
  41.             pushdown(now);
  42.             if(a<=l&&r<=b)
  43.             {
  44.                 t[now].mx=max(t[now].mx,delt);
  45.                 t[now].tag=max(t[now].tag,delt);
  46.                 return ;
  47.             }
  48.             int mid=l+r>>1;
  49.             if(a<=mid)  change(now<<1,l,mid);
  50.             if(mid<b)   change(now<<1^1,mid+1,r);
  51.             update(now);
  52.         }
  53.         int query(int now,int l,int r)
  54.         {
  55.             pushdown(now);
  56.             if(a<=l&&r<=b)
  57.                 return  t[now].mx;
  58.             int mid=l+r>>1;
  59.             int an=-1;
  60.             if(a<=mid)  an=max(an,query(now<<1,l,mid));
  61.             if(mid<b)   an=max(an,query(now<<1^1,mid+1,r));
  62.             return an;
  63.         }
  64.     public:
  66.         void CHANGE(int l,int r,int x)
  67.         {
  68.             a=l,b=r,delt=x;
  69.             change(1,1,n);
  70.         }
  71.         int QUERY(int l,int r)
  72.         {
  73.             a=l,b=r;
  74.             return query(1,1,n);
  75.         }
  76. }T;
  79. int size[N],fa[N],dep[N],son[N],top[N],pos[N],ed[N],cnt;
  80. bool once[N],used[N];
  82. void dfs1(int u)
  83. {
  84.     size[u]=1;
  85.     for(int i=head[u];i;i=e[i].next)
  86.     {
  87.         int v=e[i].to;
  88.         if(v==fa[u])    continue;
  89.         fa[v]=u,dep[v]=dep[u]+1;
  90.         dfs1(v);size[u]+=size[v];
  91.         if(size[v]>size[son[u]])    son[u]=v;
  92.     }
  93. }
  94. void dfs2(int u,int tp)
  95. {
  96.     top[u]=tp;pos[u]=++cnt,num[cnt]=v[u];
  97.     if(son[u])  dfs2(son[u],tp);
  98.     for(int i=head[u];i;i=e[i].next)
  99.     {
  100.         int v=e[i].to;
  101.         if(v!=son[u]&&v!=fa[u]) dfs2(v,v);
  102.     }
  103.     ed[u]=cnt;
  104. }
  106. int query(int p)
  107. {
  108.     return T.QUERY(pos[p],pos[p]);
  109. }
  110. void change(int x)
  111. {
  112.     if(once[x]) return ;
  113.     once[x]=1;
  114.     T.CHANGE(pos[x],ed[x],v[x]);
  115.     while(x)
  116.     {
  117.         if(fa[x])
  118.         {
  119.             if(pos[fa[x]]<=pos[x]-1)    T.CHANGE(pos[fa[x]],pos[x]-1,v[fa[x]]);
  120.             if(ed[fa[x]]>=ed[x]+1)  T.CHANGE(ed[x]+1,ed[fa[x]],v[fa[x]]);
  121.         }
  122.         if(used[x]) break;
  123.         used[x]=1;
  124.         x=fa[x];
  125.     }
  126. }
  128. int main()
  129. {
  130. //  freopen("lca.in","r",stdin);
  131. //  freopen("lca.out","w",stdout);
  132.     int x,y,k;
  133.     char s[10];
  134.     scanf("%d%d",&n,&m);
  135.     for(int i=1;i<=n;++i)   scanf("%d",&v[i]);
  136.     for(int i=1;i<n;++i)
  137.     {
  138.         scanf("%d%d",&x,&y);
  139.         add(x,y),add(y,x);
  140.     }
  141.     dfs1(1);
  142.     dfs2(1,1);
  143.     for(int i=1;i<=m;++i)
  144.     {
  145.         scanf("%s%d",s+1,&x);
  146.         if(s[1]=='Q')   
  147.         {
  148.             int ans=query(x);
  149.             printf("%d\n",ans==0?-1:ans);
  150.         }
  151.         else    change(x);
  152.     }
  153.     return 0;
  154. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注