2020 Petrozavodsk Winter Camp, Jagiellonian U Contest 做题记录

B.

考虑Lucas定理的结论,\( \binom{n}{m} \bmod p \neq 0 \)等价于在\(p\)进制下\(m\)的每一位都小于等于\(n\)的对应位

因此放到二进制下就是子集关系

高维前缀和

2020 Petrozavodsk Winter Camp, Jagiellonian U Contest 做题记录
 1 #include<bits/stdc++.h>
 2 #define maxn 2000005
 3 using namespace std;
 4 int T,n;
 5 int a[maxn];
 6 int dp[maxn];
 7 int main()
 8 {
 9     scanf("%d",&T);
10     while(T--)
11     {
12         memset(dp,0,sizeof(dp));
13         scanf("%d",&n);
14         for(int i=1;i<=n;++i)scanf("%d",&a[i]),dp[a[i]]++;
15         for(int i=0;i<20;++i)
16             for(int j=0;j<(1<<20);++j)if(j&(1<<i))dp[j]+=dp[j^(1<<i)];
17         long long ans=0;
18         for(int i=1;i<=n;++i)ans+=dp[a[i]];
19         cout<<ans<<endl;
20     }
21 }
View Code

E.

考虑离线,从下朝上扫描线,线段树维护最大值

把圆和询问都挂在\(y_{min}\)处

遇到圆就更新圆心对应的最值为\(c_y+r\)

遇到询问就查询两个\(x\)坐标之间是否有一个\(x\)的值超过\(y_{max}\)

2020 Petrozavodsk Winter Camp, Jagiellonian U Contest 做题记录
 1 #include<bits/stdc++.h>
 2 #define maxn 3000005
 3 using namespace std;
 4 int n,q;
 5 struct Opt
 6 {
 7     int tp,id;
 8     int ymn,ymx,l,r;
 9 }a[maxn];
10 int b[maxn],cnt;
11 bool operator < (Opt A,Opt B)
12 {
13     if(A.ymn==B.ymn)return A.tp<B.tp;
14     return A.ymn<B.ymn;
15 }
16 int maxv[maxn<<2];
17 void pushup(int rt)
18 {
19     maxv[rt]=max(maxv[rt<<1],maxv[rt<<1|1]);
20 }
21 void update(int rt,int l,int r,int pos,int v)
22 {
23     if(l==r){maxv[rt]=max(maxv[rt],v);return;}
24     int mid=(l+r)>>1;
25     if(pos<=mid)update(rt<<1,l,mid,pos,v);
26     else update(rt<<1|1,mid+1,r,pos,v);
27     pushup(rt);
28 }
29 int query(int rt,int l,int r,int ql,int qr)
30 {
31     int ans=-(int)(2e9+7);
32     if(ql<=l&&r<=qr)return maxv[rt];
33     int mid=(l+r)>>1;
34     if(ql<=mid)ans=max(ans,query(rt<<1,l,mid,ql,qr));
35     if(qr>mid)ans=max(ans,query(rt<<1|1,mid+1,r,ql,qr));
36     return ans;
37 }
38 int Ans[maxn];
39 int main()
40 {
41     scanf("%d%d",&n,&q);
42     for(int i=1;i<=n;++i)
43     {
44         a[i].tp=1;
45         int cx,cy,r;
46         scanf("%d%d%d",&cx,&cy,&r);
47         a[i].l=cx;
48         a[i].ymn=cy-r;a[i].ymx=cy+r;
49         b[++cnt]=cx;
50     }
51     for(int i=1;i<=q;++i)
52     {
53         a[n+i].tp=2;
54         int y,yy;
55         scanf("%d%d%d%d%d%d",&a[n+i].l,&y,&a[n+i].r,&yy,&a[n+i].ymn,&a[n+i].ymx);
56         if(a[n+i].l>a[n+i].r)swap(a[n+i].l,a[n+i].r);
57         b[++cnt]=a[n+i].l;
58         b[++cnt]=a[n+i].r;
59         a[i+n].id=i;
60     }
61     n+=q; 
62     sort(b+1,b+cnt+1);
63     cnt=unique(b+1,b+cnt+1)-b-1;
64     sort(a+1,a+n+1);
65     for(int i=1;i<=cnt*4;++i)maxv[i]=-(int)(2e9+7);
66     for(int i=1;i<=n;++i)
67     {
68         if(a[i].tp==1)
69         {
70             update(1,1,cnt,lower_bound(b+1,b+cnt+1,a[i].l)-b,a[i].ymx);
71         }
72         else
73         {
74             if(query(1,1,cnt,lower_bound(b+1,b+cnt+1,a[i].l)-b,lower_bound(b+1,b+cnt+1,a[i].r)-b)>=a[i].ymx)Ans[a[i].id]=0;
75             else Ans[a[i].id]=1;
76         }
77     }
78     for(int i=1;i<=q;++i)
79     {
80         if(Ans[i])puts("YES");
81         else puts("NO");
82     }
83 }
View Code

G.

发现能用的坐标远大于给定的坐标范围

随便构造一下

2020 Petrozavodsk Winter Camp, Jagiellonian U Contest 做题记录
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 struct Point
 4 {
 5     int x,y;
 6 }a[10],b[10];
 7 bool usea[10],useb[10];
 8 int T,n;
 9 int main()
10 {
11     scanf("%d",&T);
12     while(T--)
13     {
14         memset(usea,0,sizeof(usea));
15         memset(useb,0,sizeof(useb));
16         scanf("%d",&n);
17         for(int i=1;i<=n;++i)scanf("%d%d",&a[i].x,&a[i].y);
18         for(int i=1;i<=n;++i)scanf("%d%d",&b[i].x,&b[i].y);
19         for(int k=1;k<=n;++k)
20         {
21             int mnx=200;
22             for(int i=1;i<=n;++i)if(!usea[i])
23                 for(int j=1;j<=n;++j)if(!useb[j])mnx=min(mnx,abs(a[i].x-b[j].x));
24             bool yes=0;
25             for(int i=1;i<=n;++i)if(!usea[i])
26             {
27                 for(int j=1;j<=n;++j)if(!useb[j])if(abs(a[i].x-b[j].x)==mnx)
28                 {
29                     puts("4");
30                     printf("%d %d\n",a[i].x,a[i].y);
31                     printf("%d %d\n",a[i].x,100+k);
32                     printf("%d %d\n",b[j].x,100+k);
33                     printf("%d %d\n",b[j].x,b[j].y);
34                     usea[i]=1;useb[j]=1;
35                     yes=1;break;
36                 }
37                 if(yes)break;
38             }
39         }
40     }
41 }
View Code

H.

在凸包上做区间DP

\(f[l][r]\)表示\([l,r]\)已经被完全覆盖的最大值,且最后一笔停在\(l\)处

\(g[l][r]\)表示\([l,r]\)已经被完全覆盖的最大值,且最后一笔停在\(r\)处

互相转移一下

2020 Petrozavodsk Winter Camp, Jagiellonian U Contest 做题记录
 1 #include<bits/stdc++.h>
 2 #define maxn 305
 3 using namespace std;
 4 int T,n,m;
 5 struct Point
 6 {
 7     double x,y;
 8 }p[maxn];
 9 double sqr(double x){return x*x;}
10 double dis(Point A,Point B)
11 {
12     return sqrt(sqr(A.x-B.x)+sqr(A.y-B.y));
13 }
14 int a[maxn][maxn];
15 double f[maxn][maxn],g[maxn][maxn];
16 int main()
17 {
18     scanf("%d",&T);
19     while(T--)
20     {
21         scanf("%d",&n);
22         for(int i=0;i<n;++i)
23             for(int j=0;j<n;++j)a[i][j]=0; 
24         double ans=0;
25         for(int i=0;i<n;++i)scanf("%lf%lf",&p[i].x,&p[i].y);
26         scanf("%d",&m);
27         for(int i=1;i<=m;++i)
28         {
29             int u,v;
30             scanf("%d%d",&u,&v);
31             u--;v--;a[u][v]=a[v][u]=1;
32         }
33         for(int i=0;i<n;++i)
34             for(int j=0;j<n;++j)f[i][j]=g[i][j]=-1e18;
35         for(int i=0;i<n;++i)f[i][i]=g[i][i]=0;
36         for(int d=0;d<n;++d)
37         {
38             for(int l=0;l<n;++l)
39             {
40                 int r=(l+d)%n;
41                 for(int k=(r+1)%n;k!=l;k=(k+1)%n)
42                 {
43                     if(a[l][k])
44                     {
45                         g[l][k]=max(g[l][k],f[l][r]+dis(p[l],p[k]));
46                         f[k][r]=max(f[k][r],f[l][r]+dis(p[l],p[k]));
47                     }
48                     if(a[r][k])
49                     {
50                         g[l][k]=max(g[l][k],g[l][r]+dis(p[r],p[k]));
51                         f[k][r]=max(f[k][r],g[l][r]+dis(p[r],p[k]));
52                     }
53                 }
54                 ans=max(ans,max(f[l][r],g[l][r]));
55             }
56         }
57         printf("%.10f\n",ans);
58     }
59 }
View Code

I.

每次搞个比他小一点的回文,大概让规模减半就行了

2020 Petrozavodsk Winter Camp, Jagiellonian U Contest 做题记录
  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 struct Wint:vector<int>
  4 {
  5     Wint(int n=0)
  6     {
  7         push_back(n);
  8         check();
  9     }
 10     Wint& check()
 11     {
 12         while(!empty()&&!back())pop_back();
 13         if(empty())return *this;
 14         for(int i=1;i<size();++i)
 15         {
 16             (*this)[i]+=(*this)[i-1]/10;
 17             (*this)[i-1]%=10;
 18         }
 19         while(back()>=10)
 20         {
 21             push_back(back()/10);
 22             (*this)[size()-2]%=10;
 23         }
 24         return *this;
 25     }
 26 };
 27 istream& operator>>(istream &is,Wint &n)
 28 {
 29     string s;
 30     is>>s;
 31     n.clear();
 32     for(int i=s.size()-1;i>=0;--i)n.push_back(s[i]-0);
 33     return is;
 34 }
 35 ostream& operator<<(ostream &os,const Wint &n)
 36 {
 37     if(n.empty())os<<0;
 38     for(int i=n.size()-1;i>=0;--i)os<<n[i];
 39     return os;
 40 }
 41 bool operator!=(const Wint &a,const Wint &b)
 42 {
 43     if(a.size()!=b.size())return 1;
 44     for(int i=a.size()-1; i>=0; --i)
 45         if(a[i]!=b[i])return 1;
 46     return 0;
 47 }
 48 bool operator==(const Wint &a,const Wint &b)
 49 {
 50     return !(a!=b);
 51 }
 52 bool operator<(const Wint &a,const Wint &b)
 53 {
 54     if(a.size()!=b.size())return a.size()<b.size();
 55     for(int i=a.size()-1; i>=0; --i)
 56         if(a[i]!=b[i])return a[i]<b[i];
 57     return 0;
 58 }
 59 bool operator>(const Wint &a,const Wint &b)
 60 {
 61     return b<a;
 62 }
 63 bool operator<=(const Wint &a,const Wint &b)
 64 {
 65     return !(a>b);
 66 }
 67 bool operator>=(const Wint &a,const Wint &b)
 68 {
 69     return !(a<b);
 70 }
 71 Wint& operator+=(Wint &a,const Wint &b)
 72 {
 73     if(a.size()<b.size())a.resize(b.size());
 74     for(int i=0; i!=b.size(); ++i)a[i]+=b[i];
 75     return a.check();
 76 }
 77 Wint operator+(Wint a,const Wint &b)
 78 {
 79     return a+=b;
 80 }
 81 Wint& operator-=(Wint &a,Wint b)
 82 {
 83     if(a<b)swap(a,b);
 84     for(int i=0; i!=b.size(); a[i]-=b[i],++i)
 85         if(a[i]<b[i])
 86         {
 87             int j=i+1;
 88             while(!a[j])++j;
 89             while(j>i)
 90             {
 91                 --a[j];
 92                 a[--j]+=10;
 93             }
 94         }
 95     return a.check();
 96 }
 97 Wint operator-(Wint a,const Wint &b)
 98 {
 99     return a-=b;
100 }
101 Wint operator*(const Wint &a,const Wint &b)
102 {
103     Wint n;
104     n.assign(a.size()+b.size()-1,0);
105     for(int i=0; i!=a.size(); ++i)
106         for(int j=0; j!=b.size(); ++j)
107             n[i+j]+=a[i]*b[j];
108     return n.check();
109 }
110 Wint& operator*=(Wint &a,const Wint &b)
111 {
112     return a=a*b;
113 }
114 Wint divmod(Wint &a,const Wint &b)
115 {
116     Wint ans;
117     for(int t=a.size()-b.size(); a>=b; --t)
118     {
119         Wint d;
120         d.assign(t+1,0);
121         d.back()=1;
122         Wint c=b*d;
123         while(a>=c)
124         {
125             a-=c;
126             ans+=d;
127         }
128     }
129     return ans;
130 }
131 Wint operator/(Wint a,const Wint &b)
132 {
133     return divmod(a,b);
134 }
135 Wint& operator/=(Wint &a,const Wint &b)
136 {
137     return a=a/b;
138 }
139 Wint& operator%=(Wint &a,const Wint &b)
140 {
141     divmod(a,b);
142     return a;
143 }
144 Wint operator%(Wint a,const Wint &b)
145 {
146     return a%=b;
147 }
148 Wint pow(const Wint &n,const Wint &k)
149 {
150     if(k.empty())return 1;
151     if(k==2)return n*n;
152     if(k.back()%2)return n*pow(n,k-1);
153     return pow(pow(n,k/2),2);
154 }
155 Wint A;
156 int T;
157 vector<Wint> Ans;
158 int main()
159 {
160     cin>>T;
161     while(T--)
162     {
163         cin>>A;
164         Ans.clear();
165         while(A!=Wint(0))
166         {
167             int sz=A.size();
168             Wint B=A;
169             for(int i=0;i<sz;++i)B[i]=A[i];
170             if(sz>1)
171             {
172                 B[sz/2]--;
173                 for(int j=sz/2-1;j>=0;--j)B[j]=9;
174                 for(int i=sz/2;i<sz;++i) 
175                 {
176                     if(B[i]<0)B[i]=9,B[i+1]--;
177                     else break;
178                 }
179                 if(!B[sz-1])B.resize(sz-1);
180                 sz=B.size();
181                 for(int j=sz/2-1;j>=0;--j)B[j]=B[sz-j-1];
182             }
183             A-=B;
184             Ans.push_back(B);
185         }
186         cout<<Ans.size()<<"\n";
187         for(Wint x:Ans)cout<<x<<"\n";
188     }
189 }
View Code

 

2020 Petrozavodsk Winter Camp, Jagiellonian U Contest 做题记录

上一篇:windows下filezilla server的安装配置


下一篇:C#在类外部实现对私有字段的值的修改