2019 杭电多校第六场 题解

比赛记录

注意随机数据 ，1-n排列这种，一般都有啥暴力重构之类的方法，期望重构次数很少之类的

1005也是这样，因为n^2但只有n个值有数，所以就可以n^2logn

题解

1001 Salty Fish

unsolved.

1002 Nonsense Time 

 https://blog.csdn.net/liufengwei1/article/details/98785302

代码：

#include<bits/stdc++.h>
#define maxl 50010
using namespace std;
 
int n,mxid,mxval;
int a[maxl],kk[maxl],dy[maxl],ans[maxl];
int b[maxl],dp[maxl],frm[maxl];
bool in[maxl],froz[maxl];
 
inline void prework()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),dy[a[i]]=i;
    for(int i=1;i<=n;i++)
        scanf("%d",&kk[i]),froz[i]=false;
}
 
inline void upd(int i,int x)
{
    while(i<=n)
    {
        if(dp[b[i]]<dp[x])
            b[i]=x;
        i+=i&-i;
    }
}
 
inline int qry(int i)
{
    int res=0;
    while(i)
    {
        if(dp[res]<dp[b[i]])
            res=b[i];
        i-=i&-i;
    }
    return res;
}
 
inline void lis()
{
    for(int i=1;i<=n;i++)
        in[i]=false,frm[i]=0,b[i]=0,dp[i]=0;
    int id;mxval=0;mxid=0;
    for(int i=1;i<=n;i++)
    if(!froz[i])
    {
        id=qry(a[i]);
        dp[i]=dp[id]+1;frm[i]=id;
        if(dp[i]>mxval)
            mxval=dp[i],mxid=i;
        upd(a[i],i);
    }
    int u=mxid;
    while(u!=0)
        in[u]=true,u=frm[u];
}
 
inline void mainwork()
{
    lis();
    for(int i=n;i>=1;i--)
    {
        ans[i]=mxval;
        froz[kk[i]]=true;
        if(in[kk[i]])
            lis();
    }
}
 
inline void print()
{
    for(int i=1;i<=n;i++)
        printf("%d%c",ans[i],(i==n)?'
':' ');
}
 
int main()
{
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
        prework();
        mainwork();
        print();
    }
    return 0;
}
View Code

1003 Milk Candy

unsolved.

 1004 Speed Dog

unsolved.

1005 Snowy Smile

 https://blog.csdn.net/liufengwei1/article/details/98762357

代码：

#include<bits/stdc++.h>
#define maxl 2010
using namespace std;
 
int n,totx,toty;
int ax[maxl],ay[maxl],w[maxl];
long long ans;
long long a[maxl];
int numx[maxl],numy[maxl];
struct node
{
    int l,r;
    long long sum,lrmx;
    long long rmx,lmx;
}tree[maxl*4];
vector <int> tmpy[maxl];
 
inline void prework()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&ax[i],&ay[i],&w[i]);
        numx[i]=ax[i];numy[i]=ay[i];
    }
    sort(numx+1,numx+1+n);
    totx=unique(numx+1,numx+1+n)-numx-1;
    for(int i=1;i<=totx;i++)
        tmpy[i].clear();
    for(int i=1;i<=n;i++)
    {    
        ax[i]=lower_bound(numx+1,numx+1+totx,ax[i])-numx;
        tmpy[ax[i]].push_back(i);
    }
    sort(numy+1,numy+1+n);
    toty=unique(numy+1,numy+1+n)-numy-1;
    for(int i=1;i<=n;i++)
        ay[i]=lower_bound(numy+1,numy+1+toty,ay[i])-numy;
}
 
inline void pushup(int k)
{
    int ls=k<<1,rs=k<<1|1;
    tree[k].sum=tree[ls].sum+tree[rs].sum;
    tree[k].lrmx=max(tree[ls].lrmx,tree[rs].lrmx);
    tree[k].lrmx=max(tree[k].lrmx,tree[ls].rmx+tree[rs].lmx);
    tree[k].lmx=max(tree[ls].lmx,tree[rs].lmx+tree[ls].sum);
    tree[k].rmx=max(tree[rs].rmx,tree[ls].rmx+tree[rs].sum);
}
 
inline void build(int k,int l,int r)
{
    tree[k].l=l;tree[k].r=r;
    if(l==r)
    {
        tree[k].sum=a[l];
        tree[k].lrmx=tree[k].lmx=tree[k].rmx=max(0ll,a[l]);
        return;
    }
    int mid=(l+r)>>1,ls=k<<1,rs=k<<1|1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup(k);
}
 
inline void upd(int k,int l)
{
    if(tree[k].l==tree[k].r)
    {
        tree[k].sum=a[l];
        tree[k].lrmx=tree[k].lmx=tree[k].rmx=max(0ll,a[l]);
        return;        
    }
    int mid=(tree[k].l+tree[k].r)>>1;
    if(l<=mid)
        upd(k<<1,l);
    else
        upd(k<<1|1,l);
    pushup(k);
}
 
inline void mainwork()
{
    ans=0;int l,id;
    for(int lowx=1;lowx<=totx;lowx++)
    {
        for(int i=1;i<=toty;i++)
            a[i]=0;
        build(1,1,toty);
        for(int upx=lowx;upx<=totx;upx++)
        {
            l=tmpy[upx].size();
            for(int i=0;i<l;i++)
            {
                id=tmpy[upx][i];
                a[ay[id]]+=w[id];
                upd(1,ay[id]);
            }
            ans=max(tree[1].lrmx,ans);
        }
    }
}
 
inline void print()
{
    printf("%lld
",ans);
}
 
int main()
{
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
        prework();
        mainwork();
        print();
    }
    return 0;
}
View Code

1006 Faraway

unsolved.

1007 Support or Not

unsolved.

1008 TDL

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int up=1005;
const LL INF=2e18;//!
int m;
bool check(long long n,long long kn)
{
    int cnt=0; 
    if(n==0)
        return false; 
    for(long long i=n+1;;i++)
    if(__gcd(n,i)==1)
    {
        cnt++;
        if(cnt==m) 
            return kn==i;
    }
    return false;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
         LL k,n;
         scanf("%lld%d",&k,&m);
         LL ans=INF;
         for(int i=1;i<=up;i++)
        {
            n=i^k;
            if(check(n,i+n)) 
                ans=min(ans,n);
        }
        if(ans==INF)
        {
            puts("-1");
        }
        else
        {
            printf("%lld
",ans);
        }
    }
    return 0;
}
View Code

1009 Three Investigators

unsolved.

1010 Ridiculous Netizens

unsolved.

1011 11 Dimensions

题解：https://blog.csdn.net/liufengwei1/article/details/98962651

  1 #include<bits/stdc++.h>
  2 #define maxl 50010
  3 using namespace std;
  4  
  5 const long long inf=1e18;
  6 const int mod=1e9+7;
  7  
  8 int n,m,q,up=17;
  9 int mi[maxl];
 10 int g[21][21];
 11 int go[20][maxl][21],val[20][maxl][21];
 12 long long f[maxl][21];
 13 long long st[20][maxl][21],en[20][maxl][21];
 14 bool can[maxl][10];
 15 char s[maxl];
 16  
 17 inline long long fix(long long x)
 18 {
 19     return x<inf?x:inf;
 20 }
 21  
 22 inline void prework()
 23 {
 24     scanf("%d%d%d",&n,&m,&q);
 25     scanf("%s",s+1);
 26     for(int i=0;i<m;i++)
 27         for(int j=0;j<10;j++)
 28             g[i][j]=(i*10+j)%m;
 29     for(int i=1;i<=n;i++)
 30     if(s[i]=='?')
 31         for(int j=0;j<10;j++)
 32             can[i][j]=true;
 33     else
 34     {
 35         for(int j=0;j<10;j++)
 36             can[i][j]=false;
 37         can[i][s[i]-'0']=true;
 38     }
 39     f[n+1][0]=1;
 40     for(int j=1;j<m;j++)
 41         f[n+1][j]=0;
 42     long long tmp,sz,now,sum;int nxt;
 43     for(int i=n;i>=1;i--)
 44         for(int j=0;j<m;j++)
 45         {
 46             tmp=0;sz=-1;nxt=-1;
 47             for(int k=0;k<10;k++)
 48             if(can[i][k])
 49             {
 50                 now=f[i+1][g[j][k]];
 51                 tmp=fix(tmp+now);
 52                 if(now>sz) nxt=k,sz=now;
 53             }
 54             f[i][j]=tmp;
 55             go[0][i][j]=g[j][nxt];
 56             val[0][i][j]=nxt;
 57             sum=0;
 58             for(int k=0;k<nxt;k++)
 59             if(can[i][k])
 60                 sum=fix(sum+f[i+1][g[j][k]]);
 61             st[0][i][j]=sum;
 62             en[0][i][j]=fix(sum+f[i+1][g[j][nxt]]);
 63         }
 64     for(int k=1;k<up;k++)
 65         for(int i=1;i+(1<<k)<=n+1;i++)
 66             for(int j=0;j<m;j++)
 67             {
 68                 int x=go[k-1][i][j],len=1<<(k-1);
 69                 go[k][i][j]=go[k-1][i+len][x];
 70                 val[k][i][j]=(1ll*val[k-1][i][j]*mi[len]+val[k-1][i+len][x])%mod;
 71                 st[k][i][j]=fix(st[k-1][i][j]+st[k-1][i+len][x]);
 72                 en[k][i][j]=fix(st[k-1][i][j]+en[k-1][i+len][x]);
 73             }
 74 }
 75  
 76 inline int query(long long k)
 77 {
 78     if(k>f[1][0]) return -1;
 79     int id=1,res=0,ret=0;
 80     long long tmp;
 81     while(id<=n)
 82     {
 83         for(int i=up-1;i>=0;i--)
 84         if(id+(1<<i)<=n+1 && st[i][id][res]<k && k<=en[i][id][res])
 85         {
 86             ret=(1ll*ret*mi[1<<i]+val[i][id][res])%mod;
 87             k-=st[i][id][res];
 88             res=go[i][id][res];
 89             id+=1<<i;
 90         }
 91         if(id>n) break;
 92         for(int i=0;i<10;i++)
 93         if(can[id][i])
 94         {
 95             tmp=f[id+1][g[res][i]];
 96             if(k>tmp) 
 97                 k-=tmp;
 98             else
 99             {
100                 ret=(10LL*ret+i)%mod;
101                 id++;
102                 res=g[res][i];
103                 break;
104             }
105         }
106     }
107     return ret;
108 }
109  
110 inline void mainwork()
111 {
112     long long x;
113     for(int i=1;i<=q;i++)
114     {
115         scanf("%lld",&x);
116         printf("%d
",query(x));
117     }
118 } 
119  
120 int main()
121 {
122     mi[0]=1;
123     for(int i=1;i<maxl;i++)
124         mi[i]=1ll*10*mi[i-1]%mod;
125     int t;
126     scanf("%d",&t);
127     for(int i=1;i<=t;i++)
128     {
129         prework();
130         mainwork();
131 //        print();
132     }
133     return 0;
134 }
View Code

1012 Stay real

#include<bits/stdc++.h>
#define maxl 100010
#define mp make_pair
using namespace std;

int n;
int a[maxl];
long long ans1,ans2;
typedef pair<int,int> p;
priority_queue<p> q;
bool in[maxl];

inline void prework()
{
    while(!q.empty()) q.pop();
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]),in[i]=true;
        if(i*2>n)
            q.push(mp(a[i],i));
    }
}

inline void mainwork()
{
    p d;ans1=0,ans2=0;
    for(int i=1;i<=n;i++)
    {
        d=q.top();q.pop();
        in[d.second]=false;
        if(!in[d.second] && !in[d.second^1])
            q.push(mp(a[d.second/2],d.second/2));
        if(i&1)
            ans1+=d.first;
        else
            ans2+=d.first;
    }
}

inline void print()
{
    printf("%lld %lld
",ans1,ans2);
}

int main()
{
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
        prework();
        mainwork();
        print();
    }
    return 0;
}
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/csushl/p/11319262.html