寒假学习计划
比赛地址
[A] 欧几里得
题意
已知使用辗转相除法计算Gcd(a,b)共递归了n次,求满足a>b的a+b的最小值是多少.
题解
结论题.答案为斐波那契数列相邻的两项之和.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int n,T,i;
LL f[110];
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
inline int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
scanf("%d",&T);
f[1]=1; f[2]=2;
for (i=3;i<=100;i++)
f[i]=f[i-1]+f[i-2];
while (T--){
scanf("%d",&n);
printf("%lld\n",f[n]+f[n+1]);
}
return 0;
}
[B] 括号序列
题意
给出一个括号序列,判断是否合法
题解
签到题
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define N 1000010
#define INF 0x3f3f3f3f
using namespace std;
int n,i,top;
char c[N],z[N];
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
inline int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
scanf("%s",&c);
n=strlen(c);
for (i=0;i<n;i++){
if (c[i]=='(' || c[i]=='[' || c[i]=='{')
z[++top]=c[i];
else {
if (c[i]==')' && z[top]!='(') {puts("No"); return 0;}
if (c[i]==']' && z[top]!='[') {puts("No"); return 0;}
if (c[i]=='}' && z[top]!='{') {puts("No"); return 0;}
top--;
}
}
if (top) puts("No");
else puts("Yes");
return 0;
}
[C] 子段乘积
题意
给出一个长度为n的序列,现在要求从中取出长度为k的一个子段,求子段乘积的最大值.
题解
因为0的存在,走逆元路线并不好使.所以使用线段树维护区间乘积,然后暴力枚举区间.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define N 200010
#define MOD 998244353
#define INF 0x3f3f3f3f
using namespace std;
int n,k,i;
LL Ans;
LL a[N];
struct Tree{
int l,r;
LL d;
}t[N*4];
inline LL Max(LL a,LL b){return (a>b)?a:b;}
inline int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
inline void Maketree(int x,int low,int high){
int mid=(low+high)>>1;
t[x].l=low; t[x].r=high;
if (low==high) {t[x].d=a[low]%MOD; return;}
Maketree(l(x),low,mid); Maketree(r(x),mid+1,high);
t[x].d=(t[l(x)].d*t[r(x)].d)%MOD;
}
inline LL Query(int x,int low,int high){
int mid=(t[x].l+t[x].r)>>1;
if (t[x].l==low&&t[x].r==high) return t[x].d%MOD;
if (high<=mid) return Query(l(x),low,high)%MOD;
else if (low>mid) return Query(r(x),low,high)%MOD;
else return (Query(l(x),low,mid)*Query(r(x),mid+1,high))%MOD;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
scanf("%d%d",&n,&k);
for (i=1;i<=n;i++) scanf("%lld",&a[i]);
Maketree(1,1,n);
Ans=0;
for (i=1;i<=n-k+1;i++)
Ans=Max(Ans,Query(1,i,i+k-1));
cout<<Ans<<endl;
return 0;
}
[D] 子段异或
题意
给出一个整数序列,求其中有多少子段的异或值为0
题解
首先定义f(i)=a_{1} \ xor \ a_{2} ... \ xor \ a_{i}.则对于子段[l,r],其异或值为f(r) \ xor \ f(l-1).
若子段异或值为0,则有f(r)=f(l-1).所以把f(i)所有的取值情况都枚举一遍,组合计数计算答案即可.计数的过程可以通过map实现.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define N 200010
#define INF 0x3f3f3f3f
using namespace std;
int n,i;
LL Ans,t;
LL a[N],s[N];
map <LL,LL> M;
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
inline int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%lld",&a[i]);
s[0]=0;
for (i=1;i<=n;i++) s[i]=s[i-1]^a[i];
for (i=0;i<=n;i++) M[s[i]]+=1;
for (auto j : M){
//cout<<j.first<<" "<<j.second<<endl;
t=(LL)j.second;
Ans+=(t*(t-1))/2;
}
cout<<Ans<<endl;
return 0;
}
[E] 最小表达式
题意
给出一个只含有正整数和+的字符串,现在要求把这个字符串重新排列成一个合法的表达式,且要求这个表达式的计算结果最小.求这个表达式的值.
题解
贪心.
首先+会把表达式分割为n+1部分,n为+的数量.问题转化为如何分配这些数字.
从贪心的思路想,高位的数字要尽可能的小,所以先把1从第一段开始挨个分配,每一段分配一个;分配完毕后再分配2,接到每一段构成的数字的后面.大致效果如下:
\begin{pmatrix}1&1&1\1&1&2\2&3&4\\end{pmatrix}
然后高精度加法计算答案即可.
本来不信邪偷懒用了Python,结果T了.老老实实换回了C++.因为数字的数量不确定,所以没有使用高精板子,改用了Vector.一个优化是先把对应位先加上,到最后再进位.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define N 500010
#define INF 0x3f3f3f3f
using namespace std;
int n,i,j,k,tot;
int a[15];
char c[N];
vector <LL> sum[N];
vector <LL> ans,t,Ans;
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
inline int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
inline void Change(int x){
register int len=sum[x].size()-1;
t.clear();
while (len>=0){
t.push_back(sum[x][len]);
len--;
}
sum[x].clear();
sum[x]=t;
}
inline void Add(int x){
register int i=0,len=sum[x].size()-1,l2=ans.size()-1,up=0;
up=Max(len,l2);
t.clear();
for (i=0;i<=up;i++){
if (i>l2) t.push_back(sum[x][i]);
else if (i>len) t.push_back(ans[i]);
else t.push_back(sum[x][i]+ans[i]);
}
ans=t;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
scanf("%s",&c);
n=strlen(c);
for (i=0;i<n;i++)
if (c[i]=='+') a[0]++;
else a[c[i]-48]++;
if (!a[0]){
for (i=1;i<=9;i++)
for (j=1;j<=a[i];j++)
putchar(48+i);
return 0;
}
tot=a[0]+1;
k=0;
for (i=1;i<=9;i++)
for (j=1;j<=a[i];j++){
sum[k].push_back(i);
k=(k+1)%tot;
}
for (i=0;i<tot;i++) Change(i);
for (i=0;i<tot;i++) Add(i);
for (i=0;i<ans.size();i++){
Ans.push_back(ans[i]%10);
if (ans[i]>10){
if (i==ans.size()-1)
ans.push_back(ans[i]/10);
else ans[i+1]+=ans[i]/10;
}
}
for (i=Ans.size()-1;i>=0;i--)
printf("%d",Ans[i]);
return 0;
}
[F] 树上博弈
题意
两个人在树上做游戏.每次一个人可以从他所处的节点走到相邻的无人节点上.第一个人先走,当一个人无路可走的时候判定为负.两人均按照最优策略移动.求有多少种先手必胜的初始位置.
题解
找规律后不难发现,两个人的距离是偶数的时候先手必胜.
拿树上DP算一遍路径数量即可.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define N 1000010
#define INF 0x3f3f3f3f
using namespace std;
int n,i,x;
int f[N];
LL Ans=0;
LL a[N],b[N];
vector <int> son[N];
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
inline int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
inline void DP(int x){
for (auto i : son[x]){
DP(i);
Ans+=a[i]*b[x]; Ans+=a[x]*b[i];
a[x]+=b[i]; b[x]+=a[i];
}
Ans+=b[x]; b[x]++;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
scanf("%d",&n);
for (i=2;i<=n;i++){
scanf("%d",&f[i]);
son[f[i]].push_back(i);
}
DP(1);
cout<<Ans*2<<endl;
return 0;
}
[G] 音乐鉴赏
题意
有n个人上一门课,每个人有一个大于90的平时分.老师需要给每个人打一个期末分,分数从[0,90]随机取.如果要保证期末恰有10\%的优秀率(即总分不低于90),那么期末分的占比应该是多少.
题解
从概率统计的角度出发.设随机变量X_{i}表示第i个人的成绩是否达到了90及以上,达到了为1,否则为0.由数学期望性质可知,E(X)=\sum_{i=1}^{n}E(X_{i})=\sum_{i=1}^{n}p_{i} \geq \frac{n}{10}.其中,p_{i}为第i个人的优秀概率.
有了上面的式子之后,二分答案即可.
答案要求保留两位小数,原本的写法是把百分比扩倍成整数再计算.然后WA到自闭.最后改成实数二分一发过了......
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<cmath>
#define N 100010
#define EPS 1e-6
using namespace std;
int n,i;
double low,high,mid,Ans;
double a[N];
inline double Fabs(double x){return (x<-EPS)?-x:(x>EPS)?x:0;}
inline bool Equ(double x,double y){return (Fabs(x-y)==0);}
inline bool Check(double x){
register int i=0;
double sum=0,tot=0;
for (i=1;i<=n;i++){
sum=((100.0-x)/100.0)*a[i];
if (sum>=90 || Equ(sum,90)){tot+=1; continue;}
sum=90.0-sum;
sum=sum/(double)x*100.0;
if (sum<=90)
tot+=(90.0-sum)/90.0;
}
if (Equ(tot*10,1.0*n) || tot*10>=1.0*n) return 1;
else return 0;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%lf",&a[i]);
low=0; high=100; Ans=0;
while (!Equ(low,high)){
mid=(low+high)/2;
if (Check(mid)) Ans=mid,low=mid;
else high=mid;
}
printf("%.2lf%%",Ans);
return 0;
}
[H] 坐火车
题意
有一节长度为n的火车,每一节车厢有一个颜色col_{i}.给出两个长度为n的序列l_{i},r_{i}.现在要求对于每个x \in [1,n],统计有多少的三元组(i,j,x),满足l_{x} \leq col_{i}=col_{j} \leq r_{x},i
题解
首先上面的式子是可以化成前缀和形式的.问题转化为求一个位置两边有多少对颜色相等的车厢对,要求他们的颜色不能超过某个值.
从x=1开始计算答案.用树状数组维护每种颜色对答案的贡献.每一次x变换时,左边某种颜色会多出一个,右边会减少一个.这时动态更新一下这两种颜色对答案贡献的变化.最后计算答案的时候只需要查询两次前缀和.具体细节见代码.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define bit(x) (x&(-x))
#define LL long long
#define N 500010
#define INF 0x3f3f3f3f
using namespace std;
int n,i;
LL Ans,p,q;
LL l[N],r[N],col[N],L[N],R[N],b[N];
inline int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
inline LL Que(int x){
LL Ans=0,i=0;
for (i=x;i;i-=bit(i)) Ans+=b[i];
return Ans;
}
inline void Add(int x,LL val){
int i=0;
for (i=x;i<=n;i+=bit(i)) b[i]+=val;
}
inline LL Cal(int x){
if (!x) return 0;
return Que(x);
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
n=read();
for (i=1;i<=n;i++){
col[i]=read(); l[i]=read(); r[i]=read();
}
memset(L,0,sizeof(L));
for (i=2;i<=n;i++) R[col[i]]++;
for (i=1;i<n;i++){
if (l[i]>r[i]){
printf("0 ");
continue;
}
Ans=Cal(r[i])-Cal(l[i]-1);
printf("%lld ",Ans);
p=L[col[i]]*R[col[i]]; q=L[col[i+1]]*R[col[i+1]];
L[col[i]]++; R[col[i+1]]--;
p=L[col[i]]*R[col[i]]-p; q=L[col[i+1]]*R[col[i+1]]-q;
//cout<<p<<" "<<q<<endl;
Add(col[i],p);
if (col[i+1]!=col[i]) Add(col[i+1],q);
}
printf("0\n");
return 0;
}
[I] 匹配星星
题意
给出n个三元组,如果有两个三元组,满足x_{i}
题解
贪心.
考虑到z的取值只有0,1两种,所以只需考虑如何给z=1的三元组找匹配就行了.对所有的三元组按照x从小到大排序,按个处理.当z=0时,把对应的y扔到平衡树里.当z=1时,从平衡树里找出这个三元组的y的前驱,把他们匹配到一起,删去这个前驱,继续处理.贪心的思想就是从满足x_{i}
因为已经对x排好了序,所以平衡树中的三元组的x一定符合要求.只需要找y的前驱.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define N 100010
#define INF 0x3f3f3f3f
using namespace std;
int n,i,root=0,c=0,Ans,x;
int cnt[N*4],size[N*4],f[N*4],key[N*4];
int s[N*4][2];
struct Data{
int x,y,z;
}a[N];
inline bool cmp(const Data &a,const Data &b){return (a.x==b.x)?a.z>b.z:a.x<b.x;}
inline int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
inline bool get(int x){return s[f[x]][1]==x;}
inline void Clear(int x){size[x]=f[x]=key[x]=cnt[x]=s[x][0]=s[x][1]=0;}
inline void update(int x){
if (!x) return;
size[x]=cnt[x];
if (s[x][0]) size[x]+=size[s[x][0]];
if (s[x][1]) size[x]+=size[s[x][1]];
return;
}
inline void Rotate(int x){
int o=f[x],of=f[o],w=get(x);
s[o][w]=s[x][w^1]; f[s[o][w]]=o;
f[o]=x; s[x][w^1]=o; f[x]=of;
if (of) s[of][s[of][1]==o]=x;
update(o); update(x);
return;
}
inline void Splay(int x){
int fa=0;
for (fa;(fa=f[x]);Rotate(x))
if (f[fa]) Rotate((get(x)==get(fa))?fa:x);
root=x;
return;
}
inline void Insert(int v){
int now=root,fa=0;
if (!root){
c++; Clear(c);
key[c]=v; cnt[c]=size[c]=1; root=c; return;
}
while (1){
if (key[now]==v) {
cnt[now]++; update(now); update(fa); Splay(now); break;
}
fa=now;
now=s[now][key[now]<v];
if (!now){
key[++c]=v; size[c]=cnt[c]=1;
f[c]=fa; s[fa][key[fa]<v]=c;
update(fa); Splay(c); break;
}
}
return;
}
inline int Find(int v){
int ans=0,now=root;
while (1){
if (v<key[now]) now=s[now][0]; else {
if (s[now][0]) ans+=size[s[now][0]];
if (v==key[now]){
Splay(now); return ans+1;
}
ans+=cnt[now]; now=s[now][1];
}
}
}
inline int Pre(){
int Ans=s[root][0];
while (s[Ans][1]) Ans=s[Ans][1];
return Ans;
}
inline void Delete(int x){
int temp=Find(x);
if (cnt[root]>1){cnt[root]--; size[root]--; return;}
if (s[root][0]+s[root][1]==0) {
Clear(root); root=0; return;
}
if (!s[root][0]){
int r=root; root=s[root][1]; f[root]=0; Clear(r); return;
} else if (!s[root][1]){
int r=root; root=s[root][0]; f[root]=0; Clear(r); return;
}
int p=Pre(),r=root;
Splay(p); f[s[r][1]]=root;
s[root][1]=s[r][1];
Clear(r); update(root);
return;
}
inline int PreN(int x){
Insert(x); int ans=key[Pre()]; Delete(x);
return ans;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
n=read();
for (i=1;i<=n;i++){
a[i].x=read(); a[i].y=read(); a[i].z=read();
}
sort(a+1,a+1+n,cmp);
for (i=1;i<=n;i++){
if (!a[i].z) Insert(a[i].y);
else {
x=PreN(a[i].y);
if (x) {
Ans++; Delete(x);
}
}
}
cout<<Ans<<endl;
return 0;
}
[J] 二维跑步
题意
待填
题解
待填
代码
待填.
总结
寒假基础训练第四场,难度又双叕有所增加.
前半段打的非常顺利,没什么大的问题,只有E题拿Python莽了一发T了.结果被G题直接卡到了最后.整数二分的写法连WA25发,至今不知道错在了哪里.前一段刚写过一个实数扩成整数再二分答案的网络流,这次也按照这个思路来结果直接一条道WA到黑.
前面的题思维量都不算小,不过做的时候没有感到太大的困难,有所进步.
J题的计数很有意思,有时间慢慢推一下式子.
说好的基础训练营,结果J题放了个NTT...
声明:
本文采用
BY-NC-SA
协议进行授权，如无注明均为原创，转载请注明转自
Marvolo
本文地址: 2020寒假算法集训营 Day4题解
本文地址: 2020寒假算法集训营 Day4题解
