2019牛客多校第7场

比赛记录

lfw高精度水题签一年到，还忘记清空原数组WA了一发，3个人基础的数学知识不知道，就是3次方以上的多项式全部都可以分解。

字符串最小表示法lfw的模板里没有，从高中考试的zyj代码里贴了过来。。。而且n^3可以过，不会写nlogn。。。

E题lfw太久没写离散化后点表示区间的线段树题了，导致到结束也没写完E题，而且对于到线段树中二分找临界值不熟练，赛后补题WA了。

题目链接：https://ac.nowcoder.com/acm/contest/887#question

题解

A String

111,000，连续的一定在一段中，枚举开头，然后看最远能到哪个位置，这段字符串最小表示是本身，然后这一段就作为划分的一段

  1 #include<bits/stdc++.h>
  2 #define maxl 210000
  3 using namespace std;
  4 
  5 int n;
  6 int a[maxl],b[maxl],sum[maxl];
  7 char s[maxl],ch[maxl];
  8 bool cut[maxl];
  9 
 10 inline void prework()
 11 {
 12     scanf("%s",s+1);
 13     n=strlen(s+1);
 14     for(int i=1;i<=n;i++)
 15         cut[i]=false;
 16     a[0]=0;
 17     int cnt=1;
 18     for(int i=2;i<=n;i++)
 19     if(s[i]==s[i-1])
 20         cnt++;
 21     else
 22     {
 23         a[++a[0]]=cnt;b[a[0]]=s[i-1]-'0';
 24         cnt=1;
 25     }
 26     a[++a[0]]=cnt;b[a[0]]=s[n]-'0';
 27     for(int i=1;i<=a[0];i++)
 28         sum[i]=sum[i-1]+a[i];
 29 }
 30 
 31 inline int MP(char* ch,int n)
 32 {
 33     int i=0,j=1,k=0;
 34     while(i<n && j<n && k<n){
 35         int t=ch[(i+k)%n]-ch[(j+k)%n];
 36         if(t==0) k++;
 37         else{
 38             if(t>0) i+=(k+1);
 39             else j+=(k+1);
 40             if(i==j) j++;
 41             k=0;
 42         }
 43     }
 44     return min(i,j);
 45 }
 46 
 47 inline bool jug(int st,int ed)
 48 {
 49     int n=0;
 50     for(int i=st;i<=ed;i++)
 51         for(int j=1;j<=a[i];j++)
 52             ch[n++]=b[i]+'0';
 53     if(MP(ch,n)==0)
 54         return true;
 55     else
 56         return false;
 57 }
 58 
 59 inline void mainwork()
 60 {
 61     int st,flag,i,ed;
 62     st=1;
 63     while(st<=a[0])
 64     {
 65         ed=st;
 66         for(int i=a[0];i>=st+1;i--)
 67         if(jug(st,i))
 68         {
 69             ed=i;
 70             break;
 71         }
 72         cut[sum[ed]]=true;
 73         st=ed+1;
 74     }
 75 }
 76 
 77 inline void print()
 78 {
 79     for(int i=1;i<=a[0];i++)
 80     {
 81         for(int j=1;j<=a[i];j++)
 82             putchar(b[i]+'0');
 83         if(i==a[0])
 84             puts("");
 85         else
 86         if(cut[sum[i]])
 87             putchar(' ');
 88     }
 89 }
 90 
 91 int main()
 92 {
 93     int t;
 94     scanf("%d",&t);
 95     for(int i=1;i<=t;i++)
 96     {
 97         prework();
 98         mainwork();
 99         print();
100     }
101     return 0;
102 }

View Code

B Irreducible Polynomial

n>=3全部可以分解，<=1不能分解，n=2的时候用判别式b^2-4ac判断

 1 #include<bits/stdc++.h>
 2 #define maxl 10010
 3  
 4 int n;
 5 int a[maxl];
 6 bool flag;
 7  
 8 inline void prework()
 9 {
10     scanf("%d",&n);
11     for(int i=n;i>=0;i--)
12         scanf("%d",&a[i]);
13 }
14  
15 inline void mainwork()
16 {
17     if(n>=3)
18     {
19         flag=false;
20         return;
21     }
22     if(n<=1)
23     {
24         flag=true;
25         return;
26     }
27     long long t=a[1]*a[1]-4*a[2]*a[0];
28     if(t>=0)
29         flag=false;
30     else
31         flag=true;
32 }
33  
34 inline void print()
35 {
36     if(flag)
37         puts("Yes");
38     else
39         puts("No");
40 }
41  
42 int main()
43 {
44     int t;
45     scanf("%d",&t);
46     for(int i=1;i<=t;i++)
47     {
48         prework();
49         mainwork();
50         print();
51     }
52     return 0;
53 }

View Code

C Governing sand

两个权值树状数组一个维护个数，一个维护代价，然后枚举最高高度，不断向下减

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 const int size=1e5+5;
  4 typedef long long LL;
  5 struct Tree{
  6     int h,c,p;
  7     int cid;
  8     Tree(){}
  9     Tree(int h,int c,int p):h(h),c(c),p(p){}
 10     friend bool operator<(Tree x,Tree y)
 11     {
 12         return x.h<y.h;
 13     }
 14 }tree[size];
 15 vector<int> vc;
 16 LL cc[205];LL cv[205];
 17 LL sump[size],sumv[size];
 18 int revc[205];int n;
 19 inline int lowbit(int x){return x&(-x);}
 20 void insert(int loc,LL val)
 21 {
 22     for(int i=loc;i<205;i+=lowbit(i))
 23         cc[i]+=val;
 24 }
 25 LL query(int loc)
 26 {
 27     LL ret=0;
 28     for(int i=loc;i>0;i-=lowbit(i))
 29     {
 30         ret+=cc[i];
 31     }
 32     return ret;
 33 }
 34 void insertv(int loc,LL val)
 35 {
 36     for(int i=loc;i<205;i+=lowbit(i))
 37         cv[i]+=val;
 38 }
 39 LL queryv(int loc)
 40 {
 41     LL ret=0;
 42     for(int i=loc;i>0;i-=lowbit(i))
 43         ret+=cv[i];
 44     return ret;
 45 }
 46 LL solve(int beg,int ed)
 47 {
 48     LL cnts=sump[ed]-sump[beg-1];
 49     LL up=max(sump[beg-1]-(cnts-1),0LL);
 50     int l=1,r=200;
 51     int ans=1;
 52     while(l<=r)
 53     {
 54         int mid=(l+r)/2;
 55         if(query(mid)<=up)
 56         {
 57             ans=mid;
 58             l=mid+1;
 59         }else r=mid-1;
 60     }
 61     LL ret=queryv(ans)+sumv[n]-sumv[ed];
 62     ret+=1LL*(up-query(ans))*revc[ans+1];
 63     for(int i=beg;i<=ed;i++)
 64     {
 65         insert(tree[i].cid,tree[i].p);
 66         insertv(tree[i].cid,1LL*tree[i].p*tree[i].c);
 67     }
 68     return ret;
 69 }
 70 //p is the number of tree,c is the price of tree,h is ..hight
 71 int main()
 72 {
 73     while(~scanf("%d",&n))
 74     {
 75         vc.clear();
 76         memset(cc,0,sizeof(cc));
 77         memset(cv,0,sizeof(cv));
 78         LL ans=0;
 79         sumv[0]=0;
 80         for(int i=1;i<=n;i++)
 81         {
 82             scanf("%d%d%d",&tree[i].h,&tree[i].c,&tree[i].p);
 83             vc.push_back(tree[i].c);
 84             ans=ans+1LL*tree[i].c*tree[i].p;
 85         }
 86         sort(vc.begin(),vc.end());
 87         vc.erase(unique(vc.begin(),vc.end()),vc.end());
 88         int len=vc.size();
 89         for(int i=0;i<len;i++)  revc[i+1]=vc[i];
 90         for(int i=1;i<=n;i++)
 91         {
 92             tree[i].cid=lower_bound(vc.begin(),vc.end(),tree[i].c)-vc.begin()+1;
 93         }
 94         sort(tree+1,tree+1+n);
 95         for(int i=1;i<=n;i++) sumv[i]=sumv[i-1]+1LL*tree[i].c*tree[i].p;
 96         int beg=1;
 97         tree[n+1]=Tree(-1,-1,-1);
 98         sump[0]=0;
 99         for(int i=1;i<=n;i++)
100         {
101             sump[i]=sump[i-1]+tree[i].p;
102             if(tree[i].h==tree[i+1].h) continue;
103             ans=min(ans,solve(beg,i));
104             beg=i+1;
105         }
106         printf("%lld
",ans);
107     }
108 }

View Code

D Number

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5     int n;
 6     char p[10];
 7     scanf("%d%s",&n,p);
 8     int len=strlen(p);
 9     if(len>n)
10     {
11         printf("T_T
");
12     }
13     else
14     {
15         printf("%s",p);
16         for(int i=len+1;i<=n;i++) putchar('0');
17         puts("");
18     }
19     return 0;
20 }

View Code

E Find the median

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

  1 #include<bits/stdc++.h>
  2 #define maxl 400010
  3 using namespace std;
  4  
  5 int n,cnt,tot,id,kk,nxtnum,ans;
  6 int a1,a2,b1,b2,c1,c2,mod1,mod2;
  7 int ax[maxl],ay[maxl],ll[maxl],rr[maxl];
  8 int num[maxl*4],numval[maxl*4];
  9 struct node
 10 {
 11     long long sum;
 12     int tag;
 13 }tree[maxl*4*4];
 14 long long res;
 15 long long pre[maxl*4];
 16  
 17 inline void prework()
 18 {
 19     scanf("%d",&n);
 20     scanf("%d%d",&ax[1],&ax[2]);
 21     scanf("%d%d%d%d",&a1,&b1,&c1,&mod1);
 22     scanf("%d%d",&ay[1],&ay[2]);
 23     scanf("%d%d%d%d",&a2,&b2,&c2,&mod2);
 24     ll[1]=min(ax[1],ay[1])+1;
 25     rr[1]=max(ax[1],ay[1])+1;
 26     ll[2]=min(ax[2],ay[2])+1;
 27     rr[2]=max(ax[2],ay[2])+1;
 28     for(int i=3;i<=n;i++)
 29     {
 30         ax[i]=(1ll*ax[i-1]*a1+1ll*ax[i-2]*b1+c1)%mod1;
 31         ay[i]=(1ll*ay[i-1]*a2+1ll*ay[i-2]*b2+c2)%mod2;
 32         ll[i]=min(ax[i],ay[i])+1;
 33         rr[i]=max(ax[i],ay[i])+1;
 34     }
 35     cnt=0;
 36     for(int i=1;i<=n;i++)
 37         num[++cnt]=ll[i],num[++cnt]=rr[i];
 38     sort(num+1,num+1+cnt);
 39     tot=unique(num+1,num+1+cnt)-num-1;
 40     num[tot+1]=num[tot];
 41     for(int i=1;i<=tot;i++)
 42     {
 43         numval[(i-1)*2+1]=1,numval[i*2]=num[i+1]-num[i]-1;
 44         pre[(i-1)*2+1]=pre[(i-1)*2]+1;
 45         pre[i*2]=pre[i*2-1]+numval[i*2];
 46     }
 47     for(int i=1;i<=n;i++)
 48     {
 49         id=lower_bound(num+1,num+1+tot,ll[i])-num;
 50         ll[i]=(id-1)*2+1;
 51         id=lower_bound(num+1,num+1+tot,rr[i])-num;
 52         rr[i]=(id-1)*2+1;
 53     }
 54 }
 55  
 56 inline void build(int k,int l,int r)
 57 {
 58     int mid=(l+r)>>1;
 59     tree[k].tag=0;
 60     if(l==r)
 61     {
 62         tree[k].sum=tree[k].tag=0;
 63         return;
 64     }
 65     build(k<<1,l,mid);
 66     build(k<<1|1,mid+1,r);
 67     tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;
 68 }
 69  
 70 inline void gank(int k,int l,int r)
 71 {
 72     int mid=(l+r)>>1;
 73     int d=tree[k].tag;
 74     if(d>0)
 75     {
 76         tree[k<<1].sum+=(pre[mid]-pre[l-1])*d;
 77         tree[k<<1].tag+=d;
 78         tree[k<<1|1].sum+=(pre[r]-pre[mid])*d;
 79         tree[k<<1|1].tag+=d;
 80         tree[k].tag=0;
 81     }
 82 }
 83  
 84 inline void add(int k,int l,int r,int l1,int r1)
 85 {
 86     if(l1!=r1)
 87         gank(k,l1,r1);
 88     tree[k].sum+=(pre[r]-pre[l-1]);
 89     if(l==l1 && r==r1)
 90     {
 91         tree[k].tag+=1;
 92         return;    
 93     }
 94     int mid=(l1+r1)>>1;
 95     if(r<=mid)
 96         add(k<<1,l,r,l1,mid);
 97     else if(l>mid)
 98         add(k<<1|1,l,r,mid+1,r1);
 99     else
100     {
101         add(k<<1,l,mid,l1,mid);
102         add(k<<1|1,mid+1,r,mid+1,r1);
103     }
104 }
105  
106 inline int query(int k,int l,int r)
107 {  
108     if(l!=r)
109         gank(k,l,r);
110     if(l==r)
111     {
112         nxtnum=tree[k].tag;
113         return l;
114     }
115     int mid=(l+r)>>1;
116     if(tree[k<<1].sum<res)
117     {
118         res-=tree[k<<1].sum;
119         query(k<<1|1,mid+1,r);
120     }
121     else
122         query(k<<1,l,mid);
123 }
124  
125 inline void mainwork()
126 {
127     long long sum=0,tmp,k,z,y;
128     build(1,1,tot*2);
129     for(int i=1;i<=n;i++)
130     {
131         sum+=num[(rr[i]+1)/2]-num[(ll[i]+1)/2]+1;
132         add(1,ll[i],rr[i],1,tot*2);
133         res=(sum+1)/2;
134         id=query(1,1,tot*2);
135         if(id&1)
136             ans=num[id/2+1]-1;
137         else
138             ans=num[id/2];
139         ans+=res/nxtnum;
140         if(res%nxtnum!=0)
141             ans++;
142         printf("%d
",ans);
143     }
144 }
145  
146 int main()
147 {
148     int t;
149     prework();
150     mainwork();
151     return 0;
152 }

View Code

F Energy stones

G Make Shan Happy

H Pair

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

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 int aa,bb,cc;
 5 int a[32],b[32],c[32];
 6 long long dp[32][3][3][2][2][2][2];
 7 long long ans;
 8 bool vis[32][3][3][2][2][2][2];
 9 
10 inline void prework()
11 {
12     scanf("%d%d%d",&aa,&bb,&cc);
13     for(int i=0;i<=31;i++)
14     {
15         a[i]=(aa>>i)&1;
16         b[i]=(bb>>i)&1;
17         c[i]=(cc>>i)&1;
18     }
19     memset(dp,0,sizeof(dp));
20     memset(vis,false,sizeof(vis));
21 }
22 
23 inline long long dfs(int pos,int dc,int xc,int sta,int stb,int az,int bz)
24 {
25     if(pos<0)
26     {
27         return (dc==2 || xc==0) && az==0 && bz==0;
28     }
29     if(vis[pos][dc][xc][sta][stb][az][bz])
30         return dp[pos][dc][xc][sta][stb][az][bz];
31     vis[pos][dc][xc][sta][stb][az][bz]=true;
32     int upx=!(sta && a[pos]==0);
33     int upy=!(stb && b[pos]==0);
34     int tdc,txc;
35     for(int i=0;i<=upx;i++)
36         for(int j=0;j<=upy;j++)
37         {
38             if(dc==1)
39             {
40                 if((i&j)>c[pos])
41                     tdc=2;
42                 else if((i&j)<c[pos])
43                     tdc=0;
44                 else
45                     tdc=1;
46             }
47             else
48                 tdc=dc;
49             if(xc==1)
50             {
51                 if((i^j)>c[pos])
52                     txc=2;
53                 else if((i^j)<c[pos])
54                     txc=0;
55                 else
56                     txc=1;
57             }
58             else txc=xc;
59             dp[pos][dc][xc][sta][stb][az][bz]+=
60                 dfs(pos-1,tdc,txc,sta && i==a[pos],stb && j==b[pos],az && i==0,bz && j==0);
61         }
62     return dp[pos][dc][xc][sta][stb][az][bz];
63 }
64 
65 inline void mainwork()
66 {
67     ans=dfs(31,1,1,1,1,1,1);
68 }
69 
70 inline void print()
71 {
72     printf("%lld
",ans);
73 }
74 
75 int main()
76 {
77     int t;
78     scanf("%d",&t);
79     for(int i=1;i<=t;i++)
80     {
81         prework();
82         mainwork();
83         print();
84     }
85     return 0;
86 }

View Code

I Chessboard

J A+B problem

 1 #include<bits/stdc++.h>
 2 #define maxl 100010
 3 using namespace std;
 4 
 5 int n;
 6 long long aa,bb;
 7 int a[maxl],b[maxl],c[maxl];
 8 
 9 inline void getnum(long long x,int t[])
10 {
11     long long tmp=x;
12     t[0]=0;
13     while(tmp>0)
14     {
15         t[++t[0]]=(int)(tmp%10);
16         tmp/=10;
17     }
18 }
19 
20 inline void prework()
21 {
22     for(int i=0;i<=100;i++)
23         a[i]=0;
24     for(int i=0;i<=100;i++)
25         b[i]=0;
26     scanf("%lld%lld",&aa,&bb);
27     getnum(aa,a);
28     getnum(bb,b);
29     for(int i=1;i<=a[0]/2;i++)
30         swap(a[i],a[a[0]-i+1]);
31     for(int i=1;i<=b[0]/2;i++)
32         swap(b[i],b[b[0]-i+1]);
33     for(int i=a[0];i>=1;i--)
34     if(a[i]!=0)
35     {
36         a[0]=i;
37         break;
38     }
39     for(int i=b[0];i>=1;i--)
40     if(b[i]!=0)
41     {
42         b[0]=i;
43         break;
44     }
45 }
46 
47 inline void mainwork()
48 {
49     c[0]=0;int len=max(a[0],b[0]);
50     for(int i=1;i<=len+1;i++)
51         c[i]=0;
52     for(int i=1;i<=len;i++)
53     {
54         c[i]+=a[i]+b[i];
55         if(c[i]>=10)
56             c[i]-=10,c[i+1]+=1;
57     }
58     if(c[len+1]>0)
59         c[0]=len+1;
60     else
61         c[0]=len;
62     for(int i=1;i<=c[0]/2;i++)
63         swap(c[i],c[c[0]-i+1]);
64     for(int i=c[0];i>=1;i--)
65     if(c[i]!=0)
66     {
67         c[0]=i;
68         break;
69     }
70 }
71 
72 inline void print()
73 {
74     for(int i=c[0];i>=1;i--)
75         printf("%d",c[i]);
76     puts("");
77 }
78 
79 int main()
80 {
81     int t;
82     scanf("%d",&t);
83     for(int i=1;i<=t;i++)
84     {
85         prework();
86         mainwork();
87         print();
88     }
89     return 0;
90 }

View Code

K Function

https://blog.csdn.net/baiyifeifei/article/details/98894560

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long LL;
int s,n;
const int size=1e5+5;
int pre[size][4],p[size];
bool prime[size];
int tot;
int num[size];
int h[size][4];
int tol;
inline int ID(int x){return x<=s?x:tol-n/x+1;}
inline int f(int p,int e)
{
    if(p%4==1) return 3*e+1;
    return 1;
}
LL get_g(int x,int k)
{
    if(x<=1||p[k]>x) return 0;
    LL ans=h[ID(x)][3]-pre[k-1][3]+(h[ID(x)][1]-pre[k-1][1])*4;
    if(k==1) ans++;//'2' is specil
    while(1LL*p[k]*p[k]<=x&&k<=tot)
    {
        int pk=p[k],t=p[k];
        for(int e=1;t*pk<=x;e++,t=t*pk)
            ans=ans+f(pk,e)*(get_g(x/t,k+1))+f(pk,e+1);
        k++;
    }
    return ans;
}  
void get_h(int n)
{
    s=sqrt(n);
    tot=0;
    while(s*s<=n) s++;
    while(s*s>n) s--;
    for(int j=0;j<4;j++) pre[0][j]=0;
    for(int i=1;i<=s;i++) prime[i]=true;
    for(int i=2;i<=s;i++)
    {
        if(prime[i])
        {
            p[++tot]=i;
            for(int j=0;j<4;j++) pre[tot][j]=pre[tot-1][j]+(i%4==j);
        }
        for(int j=1;j<=tot&&p[j]*i<=s;j++)
        {
            prime[i*p[j]]=false;
            if(i%p[j]==0) break;
        }
    }
    tol=0;
    for(int i=1;i<=s;i++) num[++tol]=i;
    for(int i=s;i>=1;i--) if(n/i>s) num[++tol]=n/i;
    for(int i=1;i<=tol;i++)
    {
        h[i][1]=num[i]/4+(num[i]%4>=1)-1;
        h[i][3]=num[i]/4+(num[i]%4>=3);
        h[i][2]=num[i]/4+(num[i]%4>=2);
        h[i][0]=num[i]/4;
    }
    int x=1;
    for(int j=1;j<=tot;j++)
    {
        while(num[x]<p[j]*p[j]) x++;
        for(int i=tol;i>=x;i--)
        {
            for(int r=0;r<4;r++)
            {
                h[i][r*p[j]%4]=h[i][r*p[j]%4]-(h[ID(num[i]/p[j])][r]-pre[j-1][r]);
            }
        }
    }
}
int32_t main()
{
    int t;
    //freopen("k.in","r",stdin);
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld",&n);
        get_h(n);
        printf("%lld
",get_g(n,1)+1);
    }
}

View Code