2019杭电多校第七场

比赛记录：

1006因为智商不够卡了一年

1010lfw开场就看了这题，发现是水题，然后一直没写，最后30分钟开始写，一开始还没想清楚WA了一发，想清楚的时候已经4点52了，就不知道怎么改了

赛后发现1010 是全场最水的题，血亏，以后要是要多看看后面的题可不可做，可能是榜被带歪了。

题解：

1001 A + B = C

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int size=1e5+5;
 4 char a[size],b[size],c[size];
 5 int d[size];
 6 int main()
 7 {
 8     int t;
 9     scanf("%d",&t);
10     while(t--)
11     {
12         scanf("%s%s%s",a+1,b+1,c+1);
13         int lena=strlen(a+1),lenb=strlen(b+1),lenc=strlen(c+1);
14         int za=0,zb=0,zc=0;
15         while(a[lena]=='0') lena--,za++;
16         while(b[lenb]=='0') lenb--,zb++;
17         while(c[lenc]=='0') lenc--,zc++;
18         int lenaa=lena,lenbb=lenb,lencc=lenc;
19         bool flag=0;
20         int tmp;
21         a[0]='0',b[0]='0';
22         if(a[lena]==c[lenc])
23         {
24             flag=0;
25             while(a[lena]==c[lenc]&&lena>=0&&lenc>=1) {if(lena!=0) lena--;lenc--;}tmp=lenc;
26             while(((a[lena]-'0'+b[lenb]-'0'+flag)%10==c[lenc]-'0')&&lena>=0&&lenb>=0&&lenc>=1)
27             {
28                 flag=(a[lena]-'0'+b[lenb]-'0'+flag)/10;
29                 lenc--;
30                 if(lena!=0) lena--;
31                 if(lenb!=0) lenb--;
32             }
33             int lenmx=max({za,zb,zc});
34             if(lena==lenb&&lenb==lenc&&lenc==0)
35             {
36                 printf("%d %d %d
",lenmx-za,lenmx-zb+lencc-tmp,lenmx-zc);
37                 continue;
38             }
39         }
40         lena=lenaa,lenb=lenbb,lenc=lencc;
41         if(b[lenb]==c[lenc])
42         {
43             flag=0;
44             while(b[lenb]==c[lenc]&&lenb>=0&&lenc>=1) {if(lenb!=0) lenb--;lenc--;}tmp=lenc;
45             while(((a[lena]-'0'+b[lenb]-'0'+flag)%10==c[lenc]-'0')&&lena>=0&&lenb>=0&&lenc>=1)
46             {
47                 flag=(a[lena]-'0'+b[lenb]-'0'+flag)/10;
48                 lenc--;
49                 if(lena!=0) lena--;
50                 if(lenb!=0) lenb--;
51             }
52             int lenmx=max({za,zb,zc});
53             if(lena==lenb&&lenb==lenc&&lenc==0)
54             {
55                 printf("%d %d %d
",lenmx-za+lencc-tmp,lenmx-zb,lenmx-zc);
56                 continue;
57             }
58         }
59         lena=lenaa,lenb=lenbb,lenc=lencc;
60         int lend=max(lenb,lena);
61         flag=0;
62         for(int i=lend;i>=0;i--)
63         {
64             int an,bn;
65             an=lena==0?0:(a[lena--]-'0');
66             bn=lenb==0?0:(b[lenb--]-'0');
67             d[i]=(an+bn+flag)%10;
68             flag=(an+bn+flag)/10;
69         }
70         int zd=0;
71         while(d[lend]==0) lend--,zd++;//,cout<<d[lend]<<' '<<lend<<endl;;
72         while(lend>=0&&(d[lend]==(c[lenc]-'0'))&&lenc>=1)
73         {
74             lend--;
75             lenc--;
76         }
77         int lenab=max(za,zb);
78         int lenmx=max(max({za,zb})+zd,zc);
79         if(((lenc==0)&&(lend==0)&&(d[0]==0))||((lenc==0)&&(lend==-1)))
80         {
81             printf("%d %d %d
",lenmx-(lenab+zd)+lenab-za,lenmx-(lenab+zd)+lenab-zb,lenmx-zc);
82             continue;
83         }
84         puts("-1");
85     }
86 }

View Code

1002 Bracket Sequences on Tree

1003 Cuber Occurrence

1004 Data Structure Problem

1005 Equation

1006 Final Exam

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 
 4 using namespace std;
 5 ll m,n,k;
 6 ll check(ll x)
 7 {
 8     ll ans1=(m+1)/(x-k+1),r=(m+1)%(x-k+1);
 9     if(r==0) return ans1 * x;
10     else return m+1+(ans1+1)*(k-1);
11 }
12 int main()
13 {
14     int t;
15     scanf("%d",&t);
16     while(t--)
17     {
18         scanf("%lld%lld%lld",&n,&m,&k);
19         ll l=k,r=n;
20         ll ans=check(n);
21         while(l<=r)
22         {
23             ll mid1=(l+r)>>1;
24             ll mid2=(l+mid1)>>1;
25             ll v1=check(mid1),v2=check(mid2);
26             if(v1<v2)
27             {
28                 ans = min(ans,v1);
29                 l = mid2+1;
30             }
31             else
32             {
33                 ans = min(ans,v2);
34                 r = mid1-1;
35             }
36         }
37         printf("%lld
",ans);
38     }
39     return 0;
40 }

View Code

1007 Getting Your Money Back

1008 Halt Hater

1009 Intersection of Prisms

1010 Just Repeat

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

  1 #include<bits/stdc++.h>
  2 #define maxl 200010
  3 using namespace std;
  4 typedef unsigned long long ull;
  5  
  6 int n,m,p,cnt,tot,mod,cntc;
  7 ull k1,k2;
  8 bool ans;
  9 int a[maxl],b[maxl],f[maxl];
 10 int numa[maxl],numb[maxl];
 11 int num[maxl];
 12 struct node
 13 {
 14     int col,num;
 15 }c[maxl];
 16 bool ainb[maxl],bina[maxl];
 17  
 18 inline unsigned long long rng() 
 19 {
 20     unsigned long long k3 = k1, k4 = k2;
 21     k1 = k4;
 22     k3 ^= k3 << 23;
 23     k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
 24     return k2 + k4;
 25 }
 26  
 27 inline bool cmp(const node &x,const node &y)
 28 {
 29     return x.num<y.num;
 30 }
 31  
 32 inline void prework()
 33 {
 34     cnt=0;
 35     scanf("%d%d%d",&n,&m,&p);
 36     if(p==1)
 37     {
 38         for(register int i=1;i<=n;++i)
 39             scanf("%d",&a[i]),num[++cnt]=a[i];
 40         for(register int i=1;i<=m;++i)
 41             scanf("%d",&b[i]),num[++cnt]=b[i];
 42     }
 43     else
 44     {
 45         scanf("%llu%llu%d",&k1,&k2,&mod);
 46         for(register int i=1;i<=n;++i)
 47             a[i]=(int)(rng()%mod),num[++cnt]=a[i];
 48         scanf("%llu%llu%d",&k1,&k2,&mod);
 49         for(register int i=1;i<=m;++i)
 50             b[i]=(int)(rng()%mod),num[++cnt]=b[i];
 51     }
 52     sort(num+1,num+1+cnt);
 53     tot=unique(num+1,num+1+cnt)-num-1;
 54     for(register int i=1;i<=tot;++i)
 55         numa[i]=numb[i]=0;
 56     for(register int i=1;i<=n;++i)
 57     {
 58         a[i]=lower_bound(num+1,num+1+tot,a[i])-num;
 59         numa[a[i]]++;
 60     }
 61     for(register int i=1;i<=m;++i)
 62     {
 63         b[i]=lower_bound(num+1,num+1+tot,b[i])-num;
 64         numb[b[i]]++;
 65     }
 66     cntc=0;
 67     for(register int i=1;i<=tot;i++)
 68     {
 69         if(numa[i]>0 && numb[i]>0)
 70             c[++cntc]=node{i,numa[i]+numb[i]}; 
 71     }
 72     sort(c+1,c+1+cntc,cmp);
 73 }
 74  
 75 inline void mainwork()
 76 {
 77     int id=1,resa=n,resb=m;
 78     for(int i=cntc;i>=1;i--)
 79     {
 80         if(id&1)
 81             resa--,resb-=numb[c[i].col];
 82         else
 83             resb--,resa-=numa[c[i].col];
 84         id++;
 85     }
 86     if(id&1)
 87     {
 88         if(resa>resb)
 89             ans=true;
 90         else
 91             ans=false;
 92     }
 93     else
 94     {
 95         if(resb>resa)
 96             ans=false;
 97         else
 98             ans=true;
 99     }
100 }
101  
102 inline void print()
103 {
104     if(ans)
105         puts("Cuber QQ");
106     else
107         puts("Quber CC");
108 }
109  
110 int main()
111 {
112     int t;
113     scanf("%d",&t);
114     for(int i=1;i<=t;i++)
115     {
116         prework();
117         mainwork();
118         print();
119     }
120     return 0;
121 }

View Code

1011 Kejin Player

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

 1 #include<bits/stdc++.h>
 2 #define maxl 500010
 3 using namespace std;
 4  
 5 const int mod=1e9+7;
 6  
 7 int n,q;
 8 long long r[maxl],s[maxl],x[maxl],a[maxl];
 9 long long f[maxl],sum[maxl];
10  
11 inline long long qp(long long a,long long b)
12 {
13     long long ans=1,cnt=a;
14     while(b)
15     {
16         if(b&1)
17             ans=ans*cnt%mod;
18         cnt=cnt*cnt%mod;
19         b>>=1;
20     }
21     return ans;
22 }
23  
24 inline void prework()
25 {
26     scanf("%d%d",&n,&q);
27     for(int i=1;i<=n;i++)
28         scanf("%lld%lld%lld%lld",&r[i],&s[i],&x[i],&a[i]);
29 }
30  
31 inline void mainwork()
32 {
33     long long tmp,ss;
34     for(int i=1;i<=n;i++)
35     {
36         tmp=((s[i]-r[i])%mod+mod)%mod;
37         ss=((sum[i-1]-sum[x[i]-1])%mod+mod)%mod;
38         ss=(a[i]+ss)%mod;
39         tmp=tmp*ss%mod;
40         tmp=tmp*qp(r[i],mod-2)%mod;
41         f[i]=(a[i]+tmp)%mod;
42         sum[i]=(sum[i-1]+f[i])%mod;
43     }
44 }
45  
46 inline void print()
47 {
48     int l,r;
49     long long ans;
50     for(int i=1;i<=q;i++)
51     {
52         scanf("%d%d",&l,&r);
53         ans=((sum[r-1]-sum[l-1])%mod+mod)%mod;
54         printf("%lld
",ans);
55     }
56 }
57  
58 int main()
59 {
60     int t;
61     scanf("%d",&t);
62     for(int i=1;i<=t;i++)
63     {
64         prework();
65         mainwork();
66         print();
67     }
68     return 0;
69 }

View Code