USST新生训练赛div2+div3题解

目录

  • 前言
  • 题解部分
    • B Ichihime and Triangle(800)
      • 题目大意
      • 题解
      • 代码实现
    • C Kana and Dragon Quest game(900)
      • 题目大意
      • 题解
      • 代码实现
    • J Squares and Cubes(800)
      • 题目大意
      • 题解
      • 代码实现
    • F Double Sort(1200)
      • 题目大意
      • 题解
      • 代码实现
    • I Minimize the Thickness(1100)
      • 题目大意
      • 题解
      • 代码实现
    • K Find the Spruce(1400)
      • 题目大意
      • 题解
      • 代码实现
    • E Xenia and Colorful Gems(1700)
      • 题目大意
      • 题解
      • 代码实现
    • L Floor and Mod(1700)
      • 题目大意
      • 题解
      • 代码实现
    • M Divide and Summarize(1600)
      • 题目大意
      • 题解
      • 代码实现
    • D Linova and Kingdom(1600)
      • 题目大意
      • 题解
      • 代码实现
    • G Permutation Restoration(1900)
      • 题目大意
      • 题解
      • 代码实现
    • A Card Game(1500)
      • 题目大意
      • 题解
      • 代码实现
    • H Maximum AND(1800)
      • 题目大意
      • 题解
      • 代码实现

前言

感谢 shstyle 为本场训练赛挑选题目
以笔者作为参与者的个人视角,本场题目难度如下(题目颜色采用luogu分级,数字为cf题目评分)
Easy:BCJ
Mid:FIK
Mid hard:ELMD
Hard:GAH

题解部分

B Ichihime and Triangle(800)

原题链接:https://codeforces.com/problemset/problem/1337/A

题目大意

给定四个数 a a a, b b b, c c c, d d d,输出三个数 x x x, y y y, z z z使
a ≤ x ≤ b , b ≤ y ≤ c , c ≤ z ≤ d a \leq x \leq b,b \leq y \leq c,c \leq z \leq d axb,byc,czd且能组成以 x x x, y y y, z z z为边的三角形,保证一定有解

题解

#include<bits/stdc++.h>
#define INF 2147483647LL
#define int long long
#define MAXN 300005
#define mod 1000000007
#define PI 3.14
#define eps 1e-10
#define pa pair<int,int>
#define ms(a,x) memset(a,x,sizeof(a))
#define mc(ar1,ar2) memcpy(ar1,ar2,sizeof(ar2))
#define mkp(a,b) make_pair(a,b)
#define ls (p<<1)
#define rs (p<<1|1)
#define fn(i,st,ed) for(int i=st;i<=ed;++i)
#define fd(i,st,ed) for(int i=st;i>=ed;--i)
#define fg(i,x,head,e) for(int i=head[x];~i;i=e[i].nxt)
using namespace std;
inline int read(){int x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f;}
void solve(){
    int a,b,c,d;cin>>a>>b>>c>>d;
    cout<<b<<' '<<c<<' '<<c<<endl;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--){solve();}
    return 0;
}

代码实现

关键点在于保证一定有解,又因为三角形两边之和大于第三边,两边之差小于第三边,所以较小的 x x x y y y取上边界,较大的 z z z取下边界即是正解
时间复杂度 O ( 1 ) O(1) O(1)

C Kana and Dragon Quest game(900)

原题链接:https://codeforces.com/problemset/problem/1337/B

题目大意

给定数字 x x x, n n n, m m m,现在有两种操作,一种是使 x = ⌊ x 2 ⌋ + 10 x= \left\lfloor\dfrac{x}{2}\right\rfloor+10 x=2x+10,最多能进行 n n n次该操作,一种是使 x = x − 10 x=x-10 x=x10,最多能进行 m m m次该操作,问是否能通过上述操作使得 x ≤ 0 x\leq0 x0

题解

显然对于操作 1 1 1 x x x先减后增,不难求出阈值点是 x = 20 x=20 x=20,而操作 2 2 2是单调减的,所以可以先将操作 1 1 1尽量做,达到阈值之后进行操作 2 2 2,模拟上述过程,最后判断即可
时间复杂度 O ( n + m ) O(n+m) O(n+m)

代码实现

#include<bits/stdc++.h>
#define INF 2147483647LL
#define int long long
#define MAXN 300005
#define mod 1000000007
#define PI 3.14
#define eps 1e-10
#define pa pair<int,int>
#define ms(a,x) memset(a,x,sizeof(a))
#define mc(ar1,ar2) memcpy(ar1,ar2,sizeof(ar2))
#define mkp(a,b) make_pair(a,b)
#define ls (p<<1)
#define rs (p<<1|1)
#define fn(i,st,ed) for(int i=st;i<=ed;++i)
#define fd(i,st,ed) for(int i=st;i>=ed;--i)
#define fg(i,x,head,e) for(int i=head[x];~i;i=e[i].nxt)
using namespace std;
inline int read(){int x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f;}
void solve(){
    int x,n,m;cin>>x>>n>>m;
    while(x>=20&&n)x=(x>>1)+10,n--;
    while(x>=0&&m)x-=10,m--;
    if(x<=0)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--){solve();}
    return 0;
}

J Squares and Cubes(800)

原题链接:https://codeforces.com/problemset/problem/1619/B

题目大意

输出小于等于 n n n的完全平方数和完全立方数的数量和

题解

容斥原理,答案输出 n + n 3 − n 6 \sqrt{n}+\sqrt[3]{n}-\sqrt[6]{n} n +3n 6n ,立方根可以用 n 3 \sqrt[3]{n} 3n 预处理,也可以使用pow函数,且pow函数更为简洁,但是会需要自行调整精度
时间复杂度 O ( n 3 ) O(\sqrt[3]{n}) O(3n ) O ( 1 ) O(1) O(1)

代码实现

#include<bits/stdc++.h>
#define INF 2147483647LL
#define int long long
#define MAXN 300005
#define mod 1000000007
#define PI 3.14
#define eps 1e-10
#define pa pair<int,int>
#define ms(a,x) memset(a,x,sizeof(a))
#define mc(ar1,ar2) memcpy(ar1,ar2,sizeof(ar2))
#define mkp(a,b) make_pair(a,b)
#define ls (p<<1)
#define rs (p<<1|1)
#define fn(i,st,ed) for(int i=st;i<=ed;++i)
#define fd(i,st,ed) for(int i=st;i>=ed;--i)
#define fg(i,x,head,e) for(int i=head[x];~i;i=e[i].nxt)
using namespace std;
inline int read(){int x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f;}
void solve(){
    double n;cin>>n;n+=0.00001;
    cout<<(int)pow(n,1.0/2)+(int)pow(n,1.0/3)-(int)pow(n,1.0/6)<<endl;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--){solve();}
    return 0;
}

F Double Sort(1200)

原题链接:https://codeforces.com/problemset/problem/1681/C

题目大意

给定两个长度均为 n n n的序列 a a a b b b,可以对任意 a i a_i ai a j a_j aj ( i ≠ j ) (i\neq j) (i=j) 进行交换,同时交换 b i b_i bi b j b_j bj,询问是否能通过不超过 1 0 4 10^4 104次交换使得 a a a b b b全部从小到大排列,输出需要进行的操作数量以及需要进行的操作,若有多组答案,输出任意一组,若无法达到,则输出 − 1 -1 1

题解

先考虑若必定有答案时的答案方案,由 n ≤ 100 n\leq100 n100可知 n 2 ≤ 1 0 4 n^2\leq10^4 n2104,而冒泡排序的操作次数最多为 n ( n − 1 ) 2 \frac{n(n-1)}{2} 2n(n1)次,所以只要输出冒泡排序的交换次数和双方即可
再考虑什么情况下无法达到,由冒泡排序过程可知,若任意一次交换中 a a a b b b对应数对大小关系不相同,则无法达到要求,输出 − 1 -1 1
最终时间复杂度 O ( n 2 ) O(n^2) O(n2)

代码实现

#include<bits/stdc++.h>
#define INF 2147483647LL
#define int long long
#define MAXN 300005
#define mod 1000000007
#define PI 3.14
#define eps 1e-10
#define pa pair<int,int>
#define ms(a,x) memset(a,x,sizeof(a))
#define mc(ar1,ar2) memcpy(ar1,ar2,sizeof(ar2))
#define mkp(a,b) make_pair(a,b)
#define ls (p<<1)
#define rs (p<<1|1)
#define fn(i,st,ed) for(int i=st;i<=ed;++i)
#define fd(i,st,ed) for(int i=st;i>=ed;--i)
#define fg(i,x,head,e) for(int i=head[x];~i;i=e[i].nxt)
using namespace std;
inline int read(){int x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f;}
struct node{int a,b,id;}a[MAXN],stp[MAXN];
bool cmp(node x,node y){return x.a==y.a?x.b<y.b:x.a<y.a;}
void solve(){
    int n,ans=0;cin>>n;
    fn(i,1,n)cin>>a[i].a,a[i].id=i;
    fn(i,1,n)cin>>a[i].b;
    sort(a+1,a+1+n,cmp);
    fn(i,1,n-1)if(a[i].a>a[i+1].a||a[i].b>a[i+1].b){cout<<-1<<endl;return;}
    fn(i,1,n-1)fn(j,i+1,n){
        if(a[i].id>a[j].id){
            swap(a[i],a[j]);
            stp[++ans]={i,j};
        }
    }
    if(ans>10000){cout<<-1<<endl;return;}
    cout<<ans<<endl;
    fd(i,ans,1)cout<<stp[i].a<<" "<<stp[i].b<<endl;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--){solve();}
    return 0;
}

I Minimize the Thickness(1100)

原题链接:https://codeforces.com/problemset/problem/1741/C

题目大意

给定长度为 n n n的序列 a a a,将 a a a分为若干个和相同的连续子序列,求最大子序列的最小值

题解

显然,对于任意分割状态,第一个连续子序列必定以 a 1 a_1 a1为第一个元素,可以枚举第一个子序列的长度 l e n len len,然后向后延伸,检查后面是否能恰好分割出若干个和为 s u m [ l e n ] sum[len] sum[len]的子序列( s u m sum sum为前缀和),若能则与答案取最小值
时间复杂度 O ( n ) O(n) O(n)

代码实现

#include<bits/stdc++.h>
#define INF 2147483647LL
#define int long long
#define MAXN 300005
#define mod 1000000007
#define PI 3.14
#define eps 1e-10
#define pa pair<int,int>
#define ms(a,x) memset(a,x,sizeof(a))
#define mc(ar1,ar2) memcpy(ar1,ar2,sizeof(ar2))
#define mkp(a,b) make_pair(a,b)
#define ls (p<<1)
#define rs (p<<1|1)
#define fn(i,st,ed) for(int i=st;i<=ed;++i)
#define fd(i,st,ed) for(int i=st;i>=ed;--i)
#define fg(i,x,head,e) for(int i=head[x];~i;i=e[i].nxt)
using namespace std;
inline int read(){int x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f;}
int a[MAXN],sum[MAXN];
void solve(){
    int n,now=0,ans;cin>>n;ans=n;
    fn(i,1,n)cin>>a[i],sum[i]=sum[i-1]+a[i];
    fn(i,1,n){
        int tmp=i,nowsum=0,len=0;
        fn(j,i+1,n){
            nowsum+=a[j],len++;
            if(nowsum==sum[i]){
                //cerr<<now<<endl;
                tmp=max(tmp,len),nowsum=0,len=0;
                continue;
            }
            if(nowsum>sum[i]){nowsum=-1;break;}
        }
        if(nowsum<sum[i]&&nowsum!=0)continue;
        if(nowsum!=-1)ans=min(ans,tmp);
    }
    cout<<ans<<endl;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--){solve();}
    return 0;
}

K Find the Spruce(1400)

原题链接:https://codeforces.com/problemset/problem/1461/B

题目大意

查询一张 n × m n\times m n×m大小的图上有多少由“ * ”组成的如下图的等腰三角形,可以重叠,“ * ”也是一个答案
在这里插入图片描述

题解

观察图像可知所有等腰三角形都是由一个“ * ”向下向外延伸,纵向向下一格,横向向两个方向各扩展一格,所以可以 n m nm nm枚举每个点,对每个点进行延伸,每延伸一次答案就+1,对于横行是否合法可以维护前缀和来判断
时间复杂度 O ( n 2 m ) O(n^2m) O(n2m)

代码实现

#include<bits/stdc++.h>
#define INF 2147483647LL
#define int long long
#define MAXN 300005
#define mod 1000000007
#define PI 3.14
#define eps 1e-10
#define pa pair<int,int>
#define ms(a,x) memset(a,x,sizeof(a))
#define mc(ar1,ar2) memcpy(ar1,ar2,sizeof(ar2))
#define mkp(a,b) make_pair(a,b)
#define ls (p<<1)
#define rs (p<<1|1)
#define fn(i,st,ed) for(int i=st;i<=ed;++i)
#define fd(i,st,ed) for(int i=st;i>=ed;--i)
#define fg(i,x,head,e) for(int i=head[x];~i;i=e[i].nxt)
using namespace std;
inline int read(){int x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f;}
string mp[505];
int sum[505][505];
bool check(int x,int l,int r){
    if(sum[x][r]-sum[x][l-1]!=(r-l+1))return 0;
    return 1;
}
void solve(){
    int n,m;cin>>n>>m;
    fn(i,1,n)cin>>mp[i];
    fn(i,1,n)fn(j,0,m-1)sum[i][j]=sum[i][j-1]+(mp[i][j]=='*');
    int ans=0;
    fn(i,1,n)fn(j,0,m-1)if(mp[i][j]=='*'){
        ans++;
        int maxx=1,maxy=1;
        while(i+maxx<=n&&j-maxy>=0&&j+maxy<m&&check(i+maxx,j-maxy,j+maxy))ans++,maxx++,maxy++;
    }
    cout<<ans<<endl;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--){solve();}
    return 0;
}

E Xenia and Colorful Gems(1700)

原题链接:https://codeforces.com/problemset/problem/1336/B

题目大意

现在有三堆石头,分别有 n r n_r nr n g n_g ng n b n_b nb个,每个石头有自己的价值,从每一堆中拿出一个石头,记价值分别为 x x x y y y z z z,求 ( x − y ) 2 + ( x − z ) 2 + ( y − z ) 2 (x-y)^2+(x-z)^2+(y-z)^2 (xy)2+(xz)2+(yz)2的最小值

题解

不妨设 x ≤ y ≤ z x\leq y\leq z xyz,若已知中间值 y y y,则可以通过lowerbound轻松求出 x x x所在数组小于等于 y y y的最大值 x x x y y y所在数组大于等于 y y y的最小值 z z z,所以只需要确定数组顺序和中间值,这里可以对序列的顺序进行排列,然后对中间序列进行遍历,对每个 y y y求出答案取最小值,值得思考的是怎么优化代码长度,这里推荐使用指针参数或者数组参数缩短代码
时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)

代码实现

#include<bits/stdc++.h>
#define INF 9223372036854775807LL
#define int long long
#define MAXN 300005
#define mod 1000000007
#define PI 3.14
#define eps 1e-10
#define pa pair<int,int>
#define ms(a,x) memset(a,x,sizeof(a))
#define mc(ar1,ar2) memcpy(ar1,ar2,sizeof(ar2))
#define mkp(a,b) make_pair(a,b)
#define ls (p<<1)
#define rs (p<<1|1)
#define fn(i,st,ed) for(int i=st;i<=ed;++i)
#define fd(i,st,ed) for(int i=st;i>=ed;--i)
#define fg(i,x,head,e) for(int i=head[x];~i;i=e[i].nxt)
using namespace std;
inline int read(){int x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f;}
bool cmp(int x,int y){return x<y;}
int r[MAXN],g[MAXN],b[MAXN],ans;
int val(int x,int y,int z){return (x-y)*(x-y)+(x-z)*(x-z)+(y-z)*(y-z);}
int find(int *rr,int *gg,int *bb,int nrr,int ngg,int nbb){
    int res=INF,l=0,r=0;
    fn(i,1,nrr){
        while(l<=ngg&&gg[l]<=rr[i])l++;
        while(r<=nbb&&bb[r]<rr[i])r++;
        if(l!=1&&r!=nbb+1)res=min(res,val(rr[i],gg[l-1],bb[r]));
    }
    return res;
}
void solve(){
    ans=INF;
    int nr,ng,nb;cin>>nr>>ng>>nb;
    fn(i,1,nr)cin>>r[i];sort(r+1,r+nr+1,cmp);
    fn(i,1,ng)cin>>g[i];sort(g+1,g+ng+1,cmp);
    fn(i,1,nb)cin>>b[i];sort(b+1,b+nb+1,cmp);
    ans=min(ans,find(r,g,b,nr,ng,nb));
    ans=min(ans,find(r,b,g,nr,nb,ng));
    ans=min(ans,find(g,r,b,ng,nr,nb));
    ans=min(ans,find(g,b,r,ng,nb,nr));
    ans=min(ans,find(b,r,g,nb,nr,ng));
    ans=min(ans,find(b,g,r,nb,ng,nr));
    cout<<ans<<endl;
    return;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--){solve();}
    return 0;
}

L Floor and Mod(1700)

原题链接:https://codeforces.com/problemset/problem/1485/C

题目大意

给定 x x x y y y,问满足 1 ≤ a ≤ x 1\leq a\leq x 1ax 1 ≤ b ≤ y 1\leq b\leq y 1by ⌊ a b ⌋ = a   m o d   b \left\lfloor\dfrac{a}{b}\right\rfloor=a \bmod b ba=amodb ( a , b ) (a,b) (a,b)对数

题解

本题解法很多,这里只叙述我的做法,根据 ⌊ a b ⌋ = a   m o d   b \left\lfloor\dfrac{a}{b}\right\rfloor=a \bmod b ba=amodb可知,若设 k = ⌊ a b ⌋ = a   m o d   b k=\left\lfloor\dfrac{a}{b}\right\rfloor=a \bmod b k=ba=amodb,则有 a = k b + k a=kb+k a=kb+k,且 k ≤ a k\leq \sqrt{a} ka ,所以可以枚举 k k k,对于每个 k k k答案就是与此时对应的最大对数,即 a a a b b b的最小值再去掉 k k k对,用数学语言表达就是
a n s = Σ k = 1 a m a x ( 0 , m i n ( x − k k , y ) − k ) ans=\Sigma_{k=1}^{\sqrt{a}}max(0,min(\frac{x-k}{k},y)-k) ans=Σk=1a max(0,min(kxk,y)k)
时间复杂度 O ( a ) O(\sqrt{a}) O(a )

代码实现

#include<bits/stdc++.h>
#define INF 2147483647LL
#define int long long
#define MAXN 300005
#define mod 1000000007
#define PI 3.14
#define eps 1e-10
#define pa pair<int,int>
#define ms(a,x) memset(a,x,sizeof(a))
#define mc(ar1,ar2) memcpy(ar1,ar2,sizeof(ar2))
#define mkp(a,b) make_pair(a,b)
#define ls (p<<1)
#define rs (p<<1|1)
#define fn(i,st,ed) for(int i=st;i<=ed;++i)
#define fd(i,st,ed) for(int i=st;i>=ed;--i)
#define fg(i,x,head,e) for(int i=head[x];~i;i=e[i].nxt)
using namespace std;
inline int read(){int x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f;}
void solve(){
    int x,y,ans=0;cin>>x>>y;
    fn(i,1,sqrt(x))ans+=max(0LL,min(y,(x-i)/i)-i);
    cout<<ans<<endl;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--){solve();}
    return 0;
}

M Divide and Summarize(1600)

原题链接:https://codeforces.com/problemset/problem/1461/D

题目大意

给定一长度为 n n n的序列 a a a,进行以下操作:
1. 1. 1.找到序列最大值 M M M和最小值 m m m,记 m i d = ⌊ M + m 2 ⌋ mid=\left\lfloor\dfrac{M+m}{2}\right\rfloor mid=2M+m
2. 2. 2.将原序列中小于等于 m i d mid mid的元素放入左序列,,大于 m i d mid mid的题放入右序列,任意舍弃其中之一,并对留下的序列继续进行上述操作
询问对于每个输入的 x x x,是否在上述操作中有可能有序列和为 x x x

题解

不难发现,题目操作实际是在模拟快排的过程,但是题目解法和快排原理关系不大,可以发现, 1 ≤ a i ≤ 1 0 6 1\leq a_i\leq 10^6 1ai106,因此序列数量最多不会超过 1 0 6 l o g ( 1 0 6 ) 10^6log(10^6) 106log(106)个,并且递归次数不会超过 l o g ( 1 0 5 ) log(10^5) log(105)次,所以从时间和空间角度不会超时或者爆空间,那么我们只需要模拟题目中的操作分治,每次对当前序列求和并记入map或set等数据结构,最后对每次询问进行判断即可
时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)

代码实现

#include<bits/stdc++.h>
#define INF 2147483647LL
#define int long long
#define MAXN 300005
#define mod 1000000007
#define PI 3.14
#define eps 1e-10
#define pa pair<int,int>
#define ms(a,x) memset(a,x,sizeof(a))
#define mc(ar1,ar2) memcpy(ar1,ar2,sizeof(ar2))
#define mkp(a,b) make_pair(a,b)
#define ls (p<<1)
#define rs (p<<1|1)
#define fn(i,st,ed) for(int i=st;i<=ed;++i)
#define fd(i,st,ed) for(int i=st;i>=ed;--i)
#define fg(i,x,head,e) for(int i=head[x];~i;i=e[i].nxt)
using namespace std;
inline int read(){int x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f;}
int a[MAXN],sum[MAXN];
set<int>ans;
void dfs(int l,int r){
	if(l>r)return;
	ans.insert(sum[r]-sum[l-1]);
	int mid=a[r]+a[l]>>1;
	int id=upper_bound(a+l,a+r+1,mid)-a;
	if(id>r)return;
	dfs(l,id-1);
	dfs(id,r);
}
void solve(){
    int n,q;cin>>n>>q;ans.clear();
    fn(i,1,n)cin>>a[i];
	sort(a+1,a+1+n);
    fn(i,1,n)sum[i]=sum[i-1]+a[i];
	ans.insert(sum[n]);
	dfs(1,n);
	while(q--){
        int x;cin>>x;
		if(*ans.lower_bound(x)==x)cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--){solve();}
    return 0;
}

D Linova and Kingdom(1600)

原题链接:https://codeforces.com/problemset/problem/1336/A

题目大意

给定一棵有 n n n个点的树,标记树上任意 k k k个点,价值为每个被标记点到根路径上标记点数量之和,求价值的最大值

题解

对于树上某点,到达根的路径唯一,不难想出,若一个点被选,则他子树上的所有点都会被选,以下为证明

若某点被选,但子树中有点未被选,因为子树中点的深度一定比字数的根大,因此选择子树中的点不可能比选择子树的根更劣,所以若一个点被选,那么他子树上所有点都已经被选

得出该结论后不难得出对于一个点,若选择这个点,则会产生的 d e p i dep_i depi的贡献,但是由于会侵占子树一个为标记点,所以子树每个点贡献 − 1 -1 1,所以对于一个点 i i i,其产生的贡献就是 d e p i − s i z i dep_i-siz_i depisizi,将得到的所有答案存入堆,取前k个求和即可

代码实现

#include<bits/stdc++.h>
#define INF 2147483647LL
#define int long long
#define MAXN 300005
#define mod 1000000007
#define PI 3.14
#define eps 1e-10
#define pa pair<int,int>
#define ms(a,x) memset(a,x,sizeof(a))
#define mc(ar1,ar2) memcpy(ar1,ar2,sizeof(ar2))
#define mkp(a,b) make_pair(a,b)
#define ls (p<<1)
#define rs (p<<1|1)
#define fn(i,st,ed) for(int i=st;i<=ed;++i)
#define fd(i,st,ed) for(int i=st;i>=ed;--i)
#define fg(i,x,head,e) for(int i=head[x];~i;i=e[i].nxt)
using namespace std;
inline int read(){int x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f;}
struct edge{int to,nxt;}e[MAXN<<1];
int head[MAXN],ecnt=-1,dep[MAXN],siz[MAXN];
void insert(int x,int y){e[++ecnt]={y,head[x]};head[x]=ecnt;}
priority_queue<int,vector<int>,less<int> >heap;
void dfs(int x,int fa){
    dep[x]=dep[fa]+1,siz[x]=1;
    fg(i,x,head,e){
        int to=e[i].to;
        if(to==fa)continue;
        dfs(to,x);
        siz[x]+=siz[to];
    }
    heap.push(dep[x]-siz[x]);
}
void solve(){
    ms(head,-1);
    int n,k,ans=0;cin>>n>>k;
    fn(i,1,n-1){
        int x,y;cin>>x>>y;
        insert(x,y);insert(y,x);
    }
    dfs(1,0);
    fn(i,1,k){ans+=heap.top();heap.pop();}
    cout<<ans<<endl;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T=1;
    while(T--){solve();}
    return 0;
}

G Permutation Restoration(1900)

原题链接:https://codeforces.com/problemset/problem/1701/D

题目大意

给定序列长度为 n n n b i b_i bi,要求还原原排列 a i a_i ai,满足 b i = ⌊ i a i ⌋ b_i=\left\lfloor\dfrac{i}{a_i}\right\rfloor bi=aii

题解

由题目中所给式子,可以推出 a i a_i ai的取值范围,即 b i ≤ i a i b_i\leq \frac{i}{a_i} biaii ⇒ a i ≤ i b i \Rightarrow a_i\leq\frac{i}{b_i} aibii b i + 1 > i a i b_i+1>\frac{i}{a_i} bi+1>aii ⇒ a i > i b i + 1 \Rightarrow a_i>\frac{i}{b_i+1} ai>bi+1i ∴ i b i + 1 < a i ≤ i b i \therefore \frac{i}{b_i+1}<a_i\leq \frac{i}{b_i} bi+1i<aibii
由此,题目转换为尝试求出不相同且满足所有 a i a_i ai条件的 a i a_i ai,不难发现,题目已经转换为经典的线段覆盖问题,我们可以对左端点进行排序,然后按照右端点从小到大塞入堆中,依次取出合法 a i a_i ai即可

代码实现

#include<bits/stdc++.h>
#define INF 2147483647LL
#define int long long
#define MAXN 500005
#define mod 1000000007
#define PI 3.14
#define eps 1e-10
#define pa pair<int,int>
#define ms(a,x) memset(a,x,sizeof(a))
#define mc(ar1,ar2) memcpy(ar1,ar2,sizeof(ar2))
#define mkp(a,b) make_pair(a,b)
#define ls (p<<1)
#define rs (p<<1|1)
#define fn(i,st,ed) for(int i=st;i<=ed;++i)
#define fd(i,st,ed) for(int i=st;i>=ed;--i)
#define fg(i,x,head,e) for(int i=head[x];~i;i=e[i].nxt)
using namespace std;
inline int read(){int x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f;}
struct seg{int l,r,id;}s[MAXN];
bool cmp(seg a,seg b){return a.l<b.l;}
int a[MAXN],ans[MAXN];
void solve(){
    priority_queue<pa,vector<pa>,greater<pa> >heap;
    int n,num=1;cin>>n;
    fn(i,1,n){
        cin>>a[i];
        s[i]={i/(a[i]+1)+1,a[i]==0?(n+1):i/a[i],i};
    }
    sort(s+1,s+n+1,cmp);
    fn(i,1,n){
        while(num<=n&&s[num].l==i){
            heap.push({(s[num].r==n+1)?n:s[num].r,s[num].id});
            num++;
        }
        ans[heap.top().second]=i;
        heap.pop();
    }
    fn(i,1,n)cout<<ans[i]<<' ';cout<<endl;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--){solve();}
    return 0;
}

A Card Game(1500)

原题链接:https://codeforces.com/problemset/problem/1739/C

题目大意

游戏牌堆中含偶数 n n n张牌,每张牌上的数字不同,且大小在 1 1 1 n n n之间(即给定 1 1 1 n n n的全排列牌,又称 permutation)。两名玩家 A、B 都会在开局分得牌堆中的 n 2 \frac{n}{2} 2n张牌,手牌互异,点数随机。 首先玩家 A 出牌,对手 B 应牌(对手应牌点数需比出牌者大,且丢弃),然后玩家 B 出牌,对手 A 应牌,依次轮转,直至一人无法应牌判定其为输(无更大牌可应),或双方手牌为空判定平局(双方皆空手无牌可出)。 给定牌的张数 n n n,求能使 A 获胜的发牌方式数、能使 B 获胜的发牌方式数、能使双方平局的发牌方式数。

题解

首先考虑平局方案,若是A拿到点数为 n n n的牌,则A可以打出该牌并直接获得胜利,所以B必须获得 n n n,而如果B同时获得了点数为 n − 1 n-1 n1的牌,则B此时打出该牌会直接获得胜利,因此A必须获得 n − 1 n-1 n1,以此类推,平局方案只有一种,两人交错获得
然后考虑先手必胜态从 i − 2 i-2 i2张牌向 i i i张牌转移的方案转换,当这样转移的时候牌堆中会多两张牌 i − 1 i-1 i1 i i i,讨论A和B对牌的获得情况
若A同时获得 i − 1 i-1 i1 i i i,则可以直接打出 i i i获得胜利,转移方案数为 C i i 2 − 2 C_{i}^{\frac{i}{2}-2} Ci2i2
若A获得 i i i,B获得 i − 1 i-1 i1,A仍然可以直接打出 i i i获得胜利,转移方案为 C i i 2 − 1 C_{i}^{\frac{i}{2}-1} Ci2i1
若A获得 i − 1 i-1 i1,B获得 i i i,则A打出 i − 1 i-1 i1,B打出 i i i应牌,此时状态转移为有 i − 2 i-2 i2张牌时的后手必胜态
若B获得两张牌,则此时A必败
综上所述,先手必胜态转移方程如下 a i = C i i 2 − 2 + C i i 2 − 1 + b i − 2 a_i=C_{i}^{\frac{i}{2}-2}+C_{i}^{\frac{i}{2}-1}+b_{i-2} ai=Ci2i2+Ci2i1+bi2
再考虑后手必胜态,因为发牌总方案数为 C i i 2 C_{i}^{\frac{i}{2}} Ci2i种,所以后手必胜态转移方程就是 b i = C i i 2 − a i − 1 b_i=C_{i}^{\frac{i}{2}}-a_i-1 bi=Ci2iai1

代码实现

#include<bits/stdc++.h>
#define INF 2147483647LL
#define int long long
#define MAXN 300005
#define mod 998244353
#define PI 3.14
#define eps 1e-10
#define pa pair<int,int>
#define ms(a,x) memset(a,x,sizeof(a))
#define mc(ar1,ar2) memcpy(ar1,ar2,sizeof(ar2))
#define mkp(a,b) make_pair(a,b)
#define ls (p<<1)
#define rs (p<<1|1)
#define fn(i,st,ed) for(int i=st;i<=ed;++i)
#define fd(i,st,ed) for(int i=st;i>=ed;--i)
#define fg(i,x,head,e) for(int i=head[x];~i;i=e[i].nxt)
using namespace std;
//inline int read(){int =0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f;}
int a[MAXN],b[MAXN],d[MAXN],c[105][105];
void init(){
    fn(i,0,60){
        c[i][0]=c[i][i]=1;
        fn(j,1,i-1)c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
    }
    a[2]=1,b[2]=0,d[2]=1;
    for(int i=4;i<=60;i+=2){
        d[i]=1;
        a[i]=c[i-2][(i>>1)-2]+c[i-2][(i-2)>>1]+b[i-2];
        a[i]%=mod;
        b[i]=mod+c[i][i>>1]-a[i]-1;
        b[i]%=mod;
    }
}
void solve(){
    int n;cin>>n;
    cout<<a[n]<<' '<<b[n]<<' '<<d[n]<<endl;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    init();
    int T;cin>>T;
    while(T--){solve();}
    return 0;
}

H Maximum AND(1800)

原题链接:https://codeforces.com/problemset/problem/1721/D

题目大意

给定两个序列 a a a b b b,定义 f ( a , b ) f(a,b) f(a,b)
1. 1. 1.对所有 1 ≤ i ≤ n 1\leq i \leq n 1in,求 c i = a i ⊕ b i c_i=a_i \oplus b_i ci=aibi ⊕ \oplus 为按位异或)
2. 2. 2.对所有 1 ≤ i ≤ n 1\leq i \leq n 1in,求与和,即 f ( a , b ) = c 1 & c 2 & c 3 . . . & c n f(a,b)=c_1\&c_2\&c_3...\&c_n f(a,b)=c1&c2&c3...&cn
对于 b i b_i bi的任意排列,求最大的 f ( a , b ) f(a,b) f(a,b)

题解

对于 f ( a , b ) f(a,b) f(a,b)的二进制分解,若想让某一位是 1 1 1,则需要所有 c i c_i ci的该位都是 1 1 1,即所有 a i a_i ai b i b_i bi在该位上都是不同的,而对于已经确定的某位是 1 1 1,需要确保后续交换顺序时该位数字和原来相同
所以对于已经确定的某位是 1 1 1,我们可以对所有 a i a_i ai b i b_i bi按照该位上的 ( 0 / 1 ) (0/1) (0/1)分开,递归进入子集,若子集合答案都能取到,则整体答案能取到

代码实现

#include<bits/stdc++.h>
#define INF 2147483647LL
#define int long long
#define MAXN 300005
#define mod 1000000007
#define PI 3.14
#define eps 1e-10
#define pa pair<int,int>
#define ms(a,x) memset(a,x,sizeof(a))
#define mc(ar1,ar2) memcpy(ar1,ar2,sizeof(ar2))
#define mkp(a,b) make_pair(a,b)
#define ls (p<<1)
#define rs (p<<1|1)
#define fn(i,st,ed) for(int i=st;i<=ed;++i)
#define fd(i,st,ed) for(int i=st;i>=ed;--i)
#define fg(i,x,head,e) for(int i=head[x];~i;i=e[i].nxt)
using namespace std;
inline int read(){int x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f;}
bool cmp(int x,int y){return x<y;}
bool cmp1(int x,int y){return x>y;}
int a[MAXN],b[MAXN];
void solve(){
    int n,ans=0;cin>>n;
    fn(i,1,n)cin>>a[i];
    fn(i,1,n)cin>>b[i];
    sort(a+1,a+n+1,cmp);
    sort(b+1,b+n+1,cmp1);
    fd(i,30,0){
        int tmp=n+1;
        fn(j,1,n)if((a[j]&(1<<i))==(b[j]&(1<<i))){tmp=j;break;}
        if(tmp>n)ans|=(1<<i);
        else {
            fn(j,1,n)a[j]|=(1<<i),b[j]|=(1<<i);
            sort(a+1,a+n+1,cmp);
            sort(b+1,b+n+1,cmp1);
        }
    }
    cout<<ans<<endl;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--){solve();}
    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/654825.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

华为CE6851-48S6Q-HI升级设备版本及补丁

文章目录 升级前准备工作笔记本和交换机设备配置互联地址启用FTP设备访问FTP设备升级系统版本及补丁 升级前准备工作 使用MobaXterm远程工具连接设备&#xff0c;并作为FTP服务器准备升级所需的版本文件及补丁文件 笔记本和交换机设备配置互联地址 在交换机接口配置IP&#…

LAMP源码编译安装——CentOS7

文章目录 LAMP是什么LAMP软件组件LinuxApacheMySQLPHP 源码安装Apache一、准备工作二、安装环境依赖包三、配置软件模块四、编译及安装五、优化配置文件路径六、添加httpd系统服务&#xff08;有两种方法&#xff09;方法一&#xff1a;方法二&#xff1a; 七、修改httpd 服务配…

LabVIEW软件需求分析文档内容和编写指南

编写LabVIEW软件需求分析文档&#xff08;Software Requirements Specification, SRS&#xff09;是软件开发的关键步骤之一。以下是详细的内容结构、编写指南和注意事项&#xff1a; 内容结构 引言 项目背景&#xff1a;简要介绍项目背景和目的。 文档目的&#xff1a;说明需…

利用NewGIS平台将FME模板发布为接口

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 前言 一、模板编写 二、发布模板 三、接口获取 四、移动端调用 ​​​​​ 前言 在实际的应用生产过程中&#xff0c;尤其是移动端GIS软件的开发&#xff0c;针对一些闭…

C++学习笔记(21)——继承

目录 1. 继承的概念及定义1.1 继承的概念1.2 继承定义1.2.1 定义格式1.2.2 继承关系和访问限定符1.2.3 继承基类成员访问方式的变化 继承的概念总结&#xff1a; 2. 基类和派生类对象赋值转换3.继承中的作用域4.派生类的默认成员函数知识点&#xff1a;派生类中6个默认成员函数…

头文件大小写引发的报错

jenkins下打包编译报错如下&#xff0c;提示编译zynqCan.c时找不到“syscfgpll/sysCfgpll.h”文件。 但IDE下编译是没有报错也没有警告的&#xff0c;工程中也存在文件“syscfgpll/sysCfgPll.h”。 仔细观察发现&#xff0c;报错说的是找不到头文件“syscfgpll/sysCfgpll.h”…

蓝桥杯物联网竞赛_STM32L071_18_长短按键检测

长短按键的检测是国赛题里面遇到的&#xff0c;省赛没出过有两种实方法 定时器配置&#xff1a; 定时器的话要比delay准确&#xff0c;其中tim7定时器的准度最高 定时器预分配配置32 - 1&#xff0c;计数周期是10000 - 1这样做那么32MHZ/32也就是一秒钟记录10^6的数&#xf…

c++ vector实现出现的一些问题

目录 前言&#xff1a; 浅拷贝问题: typename指定类型&#xff1a; 前言&#xff1a; 最近学习了c vector的使用&#xff0c;然后也自己实现了一下vector的部分重要的功能。然后在其中出现了一些问题&#xff0c;在这就主要记录一下我解决哪些bug。 浅拷贝问题: 在实现res…

Weblogic SSRF漏洞 [CVE-2014-4210]

漏洞复现环境搭建请参考 http://t.csdnimg.cn/svKal docker未能成功启动redis请参考 http://t.csdnimg.cn/5osP3 漏洞原理 Weblogic的uddi组件提供了从其他服务器应用获取数据的功能并且没有对目标地址做过滤和限制&#xff0c;造成了SSRF漏洞&#xff0c;利用该漏洞可以向内…

若依跳转(新增)页面,在菜单中不显示的页面

在router.js文件中 跳转方式 this.$router.push(/monitor/b/b)

路由引入实验(思科)

华为设备参考&#xff1a;路由引入实验&#xff08;华为&#xff09; 技术简介 路由引入技术在网络通信中起着重要的作用&#xff0c;能够实现不同路由协议之间的路由传递&#xff0c;并在路由引入时部署路由控制&#xff0c;实现路径或策略的控制 实验目的 不同的路由协议之…

二十三篇:未来数据库革新:AI与云原生的融合之旅

未来数据库革新&#xff1a;AI与云原生的融合之旅 1. 智能数据库管理&#xff1a;AI的魔法 在数字化时代&#xff0c;数据库技术作为信息管理的核心&#xff0c;正经历着前所未有的变革。AI&#xff08;人工智能&#xff09;和云原生技术的融合&#xff0c;正在重新定义数据库…

力扣刷题--2965. 找出缺失和重复的数字【简单】

题目描述 给你一个下标从 0 开始的二维整数矩阵 grid&#xff0c;大小为 n * n &#xff0c;其中的值在 [1, n2] 范围内。除了 a 出现 两次&#xff0c;b 缺失 之外&#xff0c;每个整数都 恰好出现一次 。 任务是找出重复的数字a 和缺失的数字 b 。 返回一个下标从 0 开始、…

蓝桥杯Web开发【大学组:国赛】2022年真题

1.分一分 如果给你一个数组&#xff0c;你能很快将它分割成指定长度的若干份吗&#xff1f; 1.1 题目问题 请在 js/index.js 文件中补全函数 splitArray 中的代码&#xff0c;最终返回按指定长度分割的数组。 具体要求如下&#xff1a; 将待分割的&#xff08;一维&#x…

web前端之vue动态访问静态资源、静态资源的动态访问、打包、public、import、URL、Vite

MENU 静态资源与打包规则动态访问静态资源直接导入将静态资存放在public目录中动态导入URL构造函数结束语实践与坑附文 静态资源与打包规则 介绍 Vite脚手架在打包代码的时候&#xff0c;会把源代码里对于静态资源的访问路径转换为打包后静态资源文件的路径。主要的区别是文件指…

Vue中使用Vue-scroll做表格使得在x轴滑动

页面效果 首先 npm i vuescroll 在main.js中挂载到全局 页面代码 <template><div class"app-container"><Header :titletitle gobackgoBack><template v-slot:icon><van-icon clickgoHome classicon namewap-home-o /></templat…

深度解析Java 11核心新特性

码到三十五 &#xff1a; 个人主页 < 免责声明 > 避免对文章进行过度解读&#xff0c;因为每个人的知识结构和认知背景都不同&#xff0c;没有一种通用的解决方案。对于文章观点&#xff0c;不必急于评判。融入其中&#xff0c;审视自我&#xff0c;尝试从旁观者角度认清…

爬虫实战教程:深入解析配乐网站爬取1000首MP3

新书上架~&#x1f447;全国包邮奥~ python实用小工具开发教程http://pythontoolsteach.com/3 欢迎关注我&#x1f446;&#xff0c;收藏下次不迷路┗|&#xff40;O′|┛ 嗷~~ 目录 一、引言 二、实战前准备 1. 选择目标网站 2. 分析网页结构 三、爬虫工作流程详解 1. 发…

内网穿透入门使用(frp和natapp)

内网穿透入门使用 简单介绍穿透工具推荐FrpFrp下载安装服务端配置启动服务端配置客户端启动客户端效果查看 NATAppNATApp下载安装NATApp配置启动NATApp 使用途径 我的博客&#xff1a;Lichg&#xff0c;欢迎大家访问留言。 简单介绍 什么是内网穿透&#xff1a; 首先我们对内网…

lvm概述和配额

lvm概述和配额 文章目录 lvm概述和配额LVM概述1、逻辑卷的作用&#xff1a;2、lvm主要命令和实操磁盘配额创建data目录&#xff0c;进入data目录限制创建文件数 LVM概述 逻辑卷管理liunx系统下对硬盘分区的一种管理机制 lvm机制特别适合管理大储存设备&#xff0c;可以动态的…