CSUST 集训队选拔赛题解

时间:2022-12-20 23:21:51

选拔赛的题解,~~~

 

题目链接:请点击

A题

素数筛 + 线段树(树状数组)

先用素数筛打表,然后线段树更新,遍历求出值,O(1)查询即可

AC代码:

CSUST 集训队选拔赛题解CSUST 集训队选拔赛题解
/*num数组 是把记录 数是否存在 存在即为1。
总共有N个数,如何判断第i+1个数到最后一个
数之间有多少个数小于第i个数呢?不妨假设
有一个区间 [1,N],只需要判断区间[i+1,N]之
间有多少个数小于第i个数。如果我们把总区间初
始化为0,然后把第i个数之前出现过的数都在相应
的区间把它的值定为1,那么问题就转换成了[i+1,N]
值的总和
*/
#include <stdio.h>
#include <bits/stdc++.h>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define size 1000000 + 7
#define min(a, b) a > b ? b : a
typedef long long LL;
#define MAXN 1000005
#define MAXL 1299710
LL prime[MAXN];
LL check[MAXL];
LL PP[MAXL];
void init(){

LL tot = 0;
memset(check, 0, sizeof(check));
for (LL i = 2; i < MAXL; ++i)
{
  if (!check[i])
  {
    prime[tot++] = i;
  }
  for (LL j = 0; j < tot; ++j)
  {
    if (i * prime[j] > MAXL)
    {
      break;
    }
    check[i*prime[j]] = prime[j];
    if (i % prime[j] == 0)
    {
      break;
    }
  }
}
}

LL num[size << 2], x[size];
void pushup(LL rt)
{
    num[rt] = num[rt << 1] + num[rt << 1 | 1];
}
void build( LL l, LL r, LL rt)
{
    num[rt] = 0;
    if( l == r) return;
    LL m = (l + r) >> 1;
    build(lson);
    build(rson);
}
 
LL qurey( LL L, LL R, LL l, LL r, LL rt)
{
    if( L <= l && r <= R)
        return num[rt];
    LL m = (l + r) >> 1;
    LL ans = 0;
    if(L <= m) ans+=qurey(L, R, lson);
    if(R > m) ans+=qurey(L, R, rson);
    return ans;
}
void updata( LL p, LL l, LL r, LL rt)
{
    if( l == r)
    {
        num[rt]++;return;
    }
    LL m = ( l + r) >> 1;
    if( p <= m) updata(p, lson);
    else updata(p, rson);
    pushup(rt);
}
LL a[MAXN + 7];
int main()
{
    LL n;
        init();
    check[1] = 1;
    for(LL i = 2 ; i <= MAXN; i++ ){
        if(!check[i]) check[i] = i;
    }

        LL sum = 0;
        build(1, MAXN , 1);
        for( LL i= 1; i <= MAXN; i++)
        {
            LL sum = 0;
            //scanf("%lld", &x[i]);
           sum =  qurey(1, check[i], 1, MAXN , 1);
           
           a[i] = sum;
            updata(check[i], 1, MAXN, 1);
 
        }
        LL t;
        scanf("%lld",&t);
        while(t--){
        LL x;
        scanf("%lld",&x);
        printf("%lld\n",a[x]);
}
    return 0;
}
View Code

 

B题

并查集 

没有蘑菇的建树,求出有多少个没有蘑菇的路,然后求出有蘑菇的路就行

AC代码:

CSUST 集训队选拔赛题解CSUST 集训队选拔赛题解
/**
/*@author Victor
/*language C++
*/
//#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
//#include<map>
#include<set>
//#define DEBUG
#define RI register ll
using namespace std;
typedef long long ll;
//typedef __ll128 lll;
const ll N=100000+10;
const ll MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const ll INF = 0x3f3f3f3f;
#define pii pair<ll,ll>
#define pll pair<ll,ll>
#define pil pair<ll , ll>
#define pli pair<ll,ll>
#define pdl pair<double,ll>
#define pld pair<ll,double>
#define pdd pair<double,double>
#define iput(n) scanf("%lld",&n);
#define iiput(a,n) scanf("%lld%lld",&a,&n);
#define iiiput(a,b,c) scanf("%lld%lld%lld",&a,&b,&c);
#define dput(n) scanf("%lf",&n);
#define llput(n) scanf("%lld",&n);
#define cput(n) scanf("%s",n);
#define puti(n) prllf("%lld\n",n);
#define putll(n) prllf("%lld\n",n);
#define putd(n) prllf("%lfd\n",n);
#define _cls(n) memset(n,0,sizeof(n));
#define __cls(n) memset(n,INF,sizeof(n));
//priority_queue <ll,vector<ll>,greater<ll> > Q;//优先队列递增
//priority_queue<ll>Q;//递减
//map<ll,ll>mp;
//set<ll>st;
//stack<>st;
//queue<>Q;
/***********************************************/
//加速输入挂
# define IOS ios::sync_with_stdio(false)
# define FOR(i,a,n) for(ll i=a; i<=n; ++i)
//求二进制中1的个数
//__builtin_popcount(n);
//求2^k
//#define (ll)Pow(2,k) (1LL<<k)
#define to_1(n) __builtin_popcount(n)
//树状数组
#define lowbit(x) (x&-x)  
ll fa[333333];
ll pre[333333];
void init(ll n){
     for(ll i = 1;i <= n;i++) 
     fa[i] = i;
}

ll find(ll x) {
    if(fa[x] == x) 
    
    return x;
    
    return fa[x] = find(fa[x]);
}

void merge(ll x,ll y) {
    ll xi = find(x);
    ll yi = find(y);
    if(xi == yi) 
    return;
    else 
    fa[xi] = yi;
    return ;
}


int main(){
    ll n;
    IOS;
    cin >> n;
    init(n);
    for(ll i = 1 ; i < n ; i++){
        ll u,v,w;
        cin >> u >> v >> w;
        if(w == 1) continue;
        merge(u,v);
    }
    for(ll i = 1; i <= n;i++){
        ++pre[find(i)];
    }
    
    ll sum = 0;
    for(ll i = 1; i <= n;i++){
        if(pre[i]) 
         sum += pre[i]  * (n - pre[i]);
    }
    cout << sum << endl;
    return 0;
}
View Code

 

C题

N次最短路

AC代码:

CSUST 集训队选拔赛题解CSUST 集训队选拔赛题解
/**
/*@author Victor
/*language C++
*/
#include <cmath>
#include <cstring>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
using namespace std;
#define MAXN 200010
#define LEN 200010
#define INF 1e9+7
#define MODE 1000000
#define pi acos(-1)
#define g 9.8
typedef long long ll;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
struct edge{
    ll next,to,w;
};
 
edge G[MAXN*2];
ll root;
ll num=0;
ll cnt=0;
ll head[MAXN<<1];
ll depth[MAXN<<1];//深度
ll first[MAXN<<1];//首次出现编号
ll dir[MAXN<<1];//距离
ll que[MAXN<<1];//队列
ll par[MAXN];//并查集父节点
bool vis[MAXN];
ll dp[MAXN][20];
void init(ll n){for(ll i=0;i<=n;i++)par[i]=i;}//初始化并查集
ll _find(ll x){if(par[x]==x)return x;else return par[x]=_find(par[x]);}//查询并查集祖先
void unite(ll x,ll y){x=_find(x),y=_find(y);if(x==y)return;else par[x]=y;}//合并节点
void add(ll u,ll v,ll w){G[num].w=w;G[num].to=v;G[num].next=head[u];head[u]=num++;}//前向星建图
void dfs(ll u,ll dep)//dfs建图
{
    vis[u]=true;
    que[++cnt]=u;first[u]=cnt;depth[cnt]=dep;
    for(ll k=head[u];k!=-1;k=G[k].next)
    {
        ll v=G[k].to,w=G[k].w;
        if(!vis[v]){
        dir[v]=dir[u]+w;
        dfs(v,dep+1);
        que[++cnt]=u;depth[cnt]=dep;
        }
    }
}
//ST表求LCA
void ST(ll n)
{
    for(ll i=1;i<=n;i++)
        dp[i][0] = i;
    for(ll j=1;(1<<j)<=n;j++)
    {
        for(ll i=1;i+(1<<j)-1<=n;i++)
        {
            ll a = dp[i][j-1] , b = dp[i+(1<<(j-1))][j-1];
            dp[i][j] = depth[a]<depth[b]?a:b;
        }
    }
}
//两个节点之间的路径深度最小的就是LCA
ll RMQ(ll l,ll r)
{
    ll k=0;
    while((1<<(k+1))<=r-l+1)
        k++;
    ll a = dp[l][k], b = dp[r-(1<<k)+1][k]; //保存的是编号
    return depth[a]<depth[b]?a:b;
}
ll LCA(ll u ,ll v)
{
    ll x = first[u] , y = first[v];
    if(x > y) swap(x,y);
    ll res = RMQ(x,y);
    return que[res];
}
ll n,m,c;
int main()
{
    scanf("%lld",&n);
        m = n - 1;
    num=0,cnt=0;
    memset(head,-1,sizeof(head));
    memset(vis,0,sizeof(vis));
    init(n);
    for(ll i=0;i<m;i++)
    {
        ll u,v,w;
        scanf("%lld%lld%lld",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
        unite(u,v);
    }
    ll u1,v1,w1;
    scanf("%lld%lld%lld",&u1,&v1,&w1);
    for(ll i=1;i<=n;i++)
    {
        if(_find(i)==i){
            dir[i]=0;
            dfs(i,1);
        }
    }
    ST(2*n-1);
    scanf("%lld",&c);
    while(c--)
    {
        ll u,v;
        scanf("%lld%lld",&u,&v);
      
            ll lca=LCA(u,v);
            ll mid1 = dir[u]+dir[v]-2*dir[lca];
            ll lca1=LCA(u,u1); 
            ll lca2 = LCA(v1,v);
            ll mid2 = dir[u]+dir[u1]-2*dir[lca1] + dir[v]+dir[v1]-2*dir[lca2] + w1;
             ll lca3=LCA(u,v1); ll lca4 = LCA(u1,v);
            ll mid3 = dir[u]+dir[v1]-2*dir[lca3] + dir[v]+dir[u1]-2*dir[lca4] + w1;
           ll mine;
           if(mid1 > mid2){
               mine = mid2;
           }
           else mine = mid1;
           
            if(mine > mid3){
               mine = mid3;
           }
           //else mine = mid;
           
           
            printf("%lld\n",mine);
        
       
    }
    return 0;
}
View Code

 

D题

 gcd求最简分数

AC代码:

CSUST 集训队选拔赛题解CSUST 集训队选拔赛题解
//                .*/@@@]]``...                                                                   
//               .,@@  ,[[\@@@@]`..   .**.*]]]]/@@@@@@@\]]]]*.**.                                 
//               *@@ ,OOOO]`  .[@@@]]@@@@@@[[[[`*     *,[[[\@@@@@@]]`..    .*....*****.....       
//              .=@^ OOOOOOOOO\  @@@[`                           .[\@@@\]/@@@@@@@@@@@@@@@@@\`.    
//              .=@^,OOOOOOOOO[`                                       [@@      *]]]]]].  =@^.    
//              .@@*=OOOOOO/[`                                              \OOOOOOOOOOO^ =@^.    
//              .@@ /OOOOO/*                                                   ,,OOOOOOO^ @@*     
//              .@@.OOOO/.                                                      ,OOOOOOO^=@^.     
//              .=@^\OO`                                                          =O/OOO @@`.     
//              .=@^                                                               ,OOO*,@/.      
//               *@@`                                                                [. @@*.      
//               *@@.                                                                 @@@^.       
//              .=@^                                                                  =@^.        
//              *@@                ,].                                                .@@*        
//             .=@^               =/                               [\@\               .\@^.       
//             ./@`                                                                   */@\.       
//             *@@                                                                    *^@@*       
//             *@@                    ]]`                      ,]].                   *^@@.       
//            .,@/                  @@@@@@^                  =@@@@@@                  ,^@@.       
//            .@@                  =@@@@@@@                  @@@@@@@^                 =^@@.       
//           .=@^                   @@@@@@^                  =@@@@@@                 *o^@@*       
//           .=@^           ,ooooo^   [[`        [[[[[`        ,[[.  ./oooo^         /o=@/.       
//           .=@^           ,ooooo^                                  *oooooo.       =o/@@`.       
//            *@@                                                       **         =oo=@/.        
//            .,@\                                                                /oo\@@.         
//             .,@@                                                             ,oo//@/.          
//              .*\@\                                                         ,oo/\@@`.           
//                .,\@@]                        ]]]]]                     .]oo[]@@@`.             
//                  ..,\@@@@]]]*             *@@@OOO@@@@\.           .,]]]@@@@@/`*.               
//                      .*.*[[[@@@@@/        @@O@@@OO@@@O@@`          \@@@[*...                   
//                             ./@^         =@OOOO@@@@OOOO@@^         *o\@^.                      
//                            .=@/    ,@@@@@@@@@@@@O@O@@OOO@@^,]@@^    =^@@`.                     
//                            *@@            ,@@OO@@@@@O@OOO@@@[.      *o/@@.                     
//                           .=@^            /@@O@@@O@@@OOO@@       ].  \o\@^.                    
//                           .@@      ,]]@@@@@@OO@@@@O@@OOO@@\]]]/@@/   =o/@@*                    
//                          .,@/      ,[[*    \@@OOO@OOOOOOO@@[[[`      *o\@@^.                   
//                          .=@^                \@@OOOOOOOOO@@@\`        oo=@\.                   
//                          .@@.                  .[@@@@@OOOOOO@@`       =o^@@*                   
//                          *@@                       *@@OO@@@@@@        =o^@@.                   
//                          *@@                        ,@@@[ *`          =o^@@^.                  
//                          .*.................................................                   
//                                
/**
/*@author Victor
/*language C++
*/
//#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
//#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int , ll>
#define pli pair<ll,int>
#define pdl pair<double,ll>
#define pld pair<ll,double>
#define pdd pair<double,double>
#define iput(n) scanf("%d",&n);
#define iiput(a,n) scanf("%d%d",&a,&n);
#define iiiput(a,b,c) scanf("%d%d%d",&a,&b,&c);
#define dput(n) scanf("%lf",&n);
#define llput(n) scanf("%lld",&n);
#define cput(n) scanf("%s",n);
#define puti(n) printf("%d\n",n);
#define putll(n) printf("%lld\n",n);
#define putd(n) printf("%lfd\n",n);
#define _cls(n) memset(n,0,sizeof(n));
#define __cls(n) memset(n,INF,sizeof(n));
//priority_queue <int,vector<int>,greater<int> > Q;//优先队列递增
//priority_queue<int>Q;//递减
//map<ll,ll>mp;
//set<ll>st;
//stack<>st;
//queue<>Q;
/***********************************************/
//加速输入挂
# define IOS ios::sync_with_stdio(false)
# define FOR(i,a,n) for(int i=a; i<=n; ++i)
//求二进制中1的个数
//__builtin_popcount(n);
//求2^k
//#define (ll)Pow(2,k) (1LL<<k)
#define to_1(n) __builtin_popcount(n)
//树状数组
#define lowbit(x) (x&-x)  
ll gcd(ll a,ll b){
    return b?gcd(b,a%b):a;
}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
ll exgcd(ll l,ll r,ll &x,ll &y){if(r==0){x=1;y=0;return l;}else{ll d=exgcd(r,l%r,y,x);y-=l/r*x;return d;}}
//求a关于m的乘法逆元
ll mod_inverse(ll a,ll m){ll x,y;if(exgcd(a,m,x,y)==1)/*ax+my=1*/return (x%m+m)%m;return -1;/*不存在*/}
//快速乘
ll qmul(ll a,ll b,ll m){ll ans=0;ll k=a;ll f=1;/*f是用来存负号的*/if(k<0){f=-1;k=-k;}if(b<0){f*=-1;b=-b;}while(b){if(b&1)ans=(ans+k)%m;k=(k+k)%m;b>>=1;}return ans*f;}
//中国剩余定理CRT (x=ai mod mi)
ll china(ll n, ll *a,ll *m) {ll M=1,y,x=0,d;for(ll i = 1; i <= n; i++) M *= m[i];for(ll i = 1; i <= n; i++) {ll w = M /m[i]; exgcd(m[i], w, d, y);/*m[i]*d+w*y=1*/ x = (x + y*w*a[i]) % M;}return (x+M)%M;}
//筛素数,全局:int cnt,prime[N],p[N];
//void isprime(){cnt = 0;memset(prime,true,sizeof(prime));for(int i=2; i<N; i++){if(prime[i]){p[cnt++] = i;for(int j=i+i; j<N; j+=i)prime[j] = false;}}}
//快速求逆元
//void inverse(){inv[1] = 1;for(int i=2;i<N;i++){if(i >= M) break;inv[i] = (M-M/i)*inv[M%i]%M;}}
//组合数取模,n和m 10^5时,预处理出逆元和阶乘
/*
ll fac[N]={1,1},inv[N]={1,1},f[N]={1,1};
ll C(ll a,ll b){
    if(b>a)return 0;
    return fac[a]*inv[b]%M*inv[a-b]%M;
}
void init(){//快速计算阶乘的逆元
    for(int i=2;i<N;i++){
        fac[i]=fac[i-1]*i%M;
        f[i]=(M-M/i)*f[M%i]%M;
        inv[i]=inv[i-1]*f[i]%M;
    }
}
*/

int main(){
    int t;
    cin >> t;
    while(t--){
 ll a,b,c,d;
 cin >> a >> b >> c >> d;
 ll sum =( b - a + 1) * (d - c + 1); 
ll su;
if(a > d || c > b) su = 0;
else if(a > c) 
{
    if(b > d) 
        su = d - a + 1;
    else su = b - a + 1;
}
else if( a <= c){
    if(b > d) 
        su = d - c + 1;
    else su = b - c + 1;

}
if(su == 0) printf("0/1\n");
else {
    if(sum % su == 0){
        printf("1/%lld\n",sum / su);
    }
    else {
         printf("%lld/%lld\n",su / gcd(su,sum) , sum / gcd(su,sum));
    }
}
}
return 0;
}
View Code

 

E题

 暴力最小遍历

AC代码:

CSUST 集训队选拔赛题解CSUST 集训队选拔赛题解
/**
/*@author Victor
/*language C++
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[1000],b[1000][1000];
int main(){
ll n,k;

scanf("%lld%lld",&n,&k);
ll min = 0;
for(int j = 0 ; j < n ; j++){
    
    
for(int i = 0 ; i < k ; i++ ){
    scanf("%lld",&a[i]);
}
sort(a,a+k);

for(int z = 0 ; z < k; z++ )
{
    b[j][z] = a[z];
//    cout << a[z] << endl; 
}


}

for(int i = 0 ; i < k ; i++){
    for(int j = 0 ; j < n - 1 ; j++){
        min += abs(b[j][i] - b[j + 1][i]);
    //    cout << min << endl; 
    }
}

printf("%lld\n",min);
return 0;
}
View Code

 

F题

 枚举每点的最短路求和求最小值

AC代码:

CSUST 集训队选拔赛题解CSUST 集训队选拔赛题解
/**
/*@author Victor
/*language C++
*/
#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<map>
#include<cstring>
#include<string>
#include<set>
#include<queue>
#include<fstream>
using namespace std;
typedef pair<int,int> PII;
const int MAXN=1e4+5;
const int INF=0x3f3f3f3f;
bool vis[MAXN];
int dist[MAXN],head[MAXN],tot;
int pre[MAXN];

struct Edge
{
    int from,to,cost,nxt;
    Edge(){}
    Edge(int _from,int _to,int _cost):from(_from),to(_to),cost(_cost){}
}e[MAXN*2];

void addedge(int u,int v,int w)
{
    e[tot].from=u;e[tot].to=v;e[tot].cost=w;
    e[tot].nxt=head[u];head[u]=tot++;
}

struct qnode
{
    int c,v;
    qnode(int _c=0,int _v=0):c(_c),v(_v){}
    bool operator < (const qnode &rhs) const {return c>rhs.c;}
};

void Dijkstra(int n,int st)//点的编号从1开始
{
    memset(vis,false,sizeof(vis));
    for(int i=0;i<=n;i++) dist[i]=INF;
    priority_queue<qnode> pq;
    while(!pq.empty()) pq.pop();
    dist[st]=0;
    pq.push(qnode(0,st));
    qnode frt;
    while(!pq.empty())
    {
        frt=pq.top(); pq.pop();
        int u=frt.v;
        if(vis[u]) continue;
        vis[u]=true;
        for(int i=head[u];i!=-1;i=e[i].nxt)
        {
            int to=e[i].to;
            int cost=e[i].cost;
            if(dist[to]>dist[u]+cost)
            {
                dist[to]=dist[u]+cost;
                pre[to]=u;
                pq.push(qnode(dist[to],to));
            }
        }
    }
}

int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n==0&&m==0) break;
        tot=0;memset(head,-1,sizeof(head));
        int u,v,w;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            addedge(u,v,w);addedge(v,u,w);
        }
        int st,ed;
        int sum = 0;
        int mine = INF;
    
        for(int st = 1; st <= n;st++){
        
        Dijkstra(n,st);
     for(int i = 1 ; i <= n;i++ ) {

         sum += dist[i];
     }  
        if(sum < mine){
            ed = st;
            mine = sum ;
        }
        sum = 0;
        
    }

printf("%d %d\n",mine , ed);
    }
    return 0;
}
View Code

 

G题

 逆序对 + 线段树(归并排序

AC代码:

CSUST 集训队选拔赛题解CSUST 集训队选拔赛题解
/**
/*@author Victor
/*language C++
*/
#include <iostream>
#include <cstdio>
#include <bits/stdc++.h>
#define _cls(a) memset(a,0,sizeof(a))
typedef long long ll;
using namespace std;
 
ll n, a[200005], tmpA[200005], cnt = 0;
 ll p[200005];
 
void merge_sort(ll l, ll r, ll *A) {
    if (l >= r) return ;
    ll mid = (l + r) >> 1;
    merge_sort(l, mid, A);
    merge_sort(mid + 1, r, A);
    ll pl = l, pr = mid + 1, tmpp = 0;
    while(pl <= mid && pr <= r) {
        if (A[pl] <= A[pr]) tmpA[tmpp++] = A[pl++];
        else tmpA[tmpp++] = A[pr++], cnt += mid - pl + 1;
    }
    while(pl <= mid) tmpA[tmpp++] = A[pl++];
    while(pr <= r) tmpA[tmpp++] = A[pr++];
    for (ll i = 0; i < tmpp; i++) A[i + l] = tmpA[i];
} 

int main() {
    ll t;
    scanf("%lld",&t);
    while(t--){
    _cls(p);
    _cls(a);
    _cls(tmpA);
    cnt = 0;
    scanf("%lld", &n);
        for (ll i = 1; i <= n; i++){
         ll x;
         scanf("%lld", &x);
         p[x] = i;
}
    for (ll i = 1; i <= n; i++) {
    ll x;    
    scanf("%lld", &x);
    a[i] = p[x];
}
    merge_sort(1, n, a);
    printf("%lld\n", cnt);
}
    return 0;
}
View Code

 

H题

 二分 + 前缀和

AC代码:

CSUST 集训队选拔赛题解CSUST 集训队选拔赛题解
/**
/*@author Victor
/*language C++
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

struct name
{
ll w, v;    
};
struct name1
{
ll a, b;    
};
ll s[422222];
ll o[422222];
name p[400000 + 10];
name1 p1[400000 + 10];

int main(){

ll n,m ,S;
scanf("%lld%lld%lld",&n,&m,&S);
for(ll i = 1 ; i <= n;i ++ )
{
    ll w,v;
    scanf("%lld%lld",&p[i].w,&p[i].v);
}
ll l = 1, r = 10000000;
ll W ;
for(ll i = 1 ; i <= m; i++){

    scanf("%lld %lld",&p1[i].a,&p1[i].b);
}
ll sum = 2000000000000;
for(ll k = 1 ; k <= 100; k++){
     W = (l + r) / 2;
     memset(s,0,sizeof(s));
     memset(o,0,sizeof(o));
     for(ll j = 1; j <= n; j++ ){
             if(W <= p[j].w){
         s[j] = s[j - 1] + p[j].v;
         o[j] = 1 + o[j - 1];
     }
     else {
         s[j] = s[j - 1] ;
         o[j] = o[j - 1] ;
     }
     }
     
     ll mine = 0;
     ll H = 0;
    // ll sum = 2000000;
     for(ll i = 1;  i <= m ; i++ ){
         H += (s[p1[i].b] - s[p1[i].a - 1]) * (o[p1[i].b] - o[p1[i].a - 1]);
     }
     if(H < S) {
         r = W ;
     }
     else l = W;
     
      mine = abs(H - S);
     
     if(sum > mine) sum = mine;
}
printf("%lld\n",sum);
return 0;
}
View Code

 

I题

 完全背包 + 快速幂

AC代码:

CSUST 集训队选拔赛题解CSUST 集训队选拔赛题解
/**
/*@author Victor
/*language C++
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t;
ll dp[200000 + 7];
ll qpow(ll a,ll b,ll m){
    ll ans=1;
    ll k=a;
    while(b){
        if(b&1)ans=ans*k%m;
        k=k*k%m;
        b>>=1;
    }
    return ans;
}int main(){


scanf("%lld",&t);
while(t -- ){
    memset(dp,0,sizeof(dp));
    ll n, m;
    dp[1] = 1;
//    dp[0] = 1;
    scanf("%lld%lld",&n,&m);
    if(m==1) dp[n] = qpow(2,n,100000000 + 7);
    else{
    
    for(int i = 0;i < m;i++){
        dp[i] = 1;
    }

    for(int i = m  ; i <= n;i++){
    
        dp[i] += dp[i - 1] + dp[i - m];
        dp[i] %= (100000000 + 7); 
    }
}
//    for(int i = 0 ;  i <= n ; i++ ){
//        printf("%d\n",dp[i]);
//    }
    //printf("%d",dp[n]);
    printf("%lld\n",dp[n] % (100000000 + 7));


}
return 0;
}
View Code

 

J题

 线段树

AC代码:

CSUST 集训队选拔赛题解CSUST 集训队选拔赛题解
/**
/*@author Victor
/*language C++
*/
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <vector>
#define LL long long
using namespace std;

LL INF = 0x3f3f3f3f;
const LL MAX = 1000000 + 50;

LL Sum[MAX << 2];
LL Add[MAX << 2];

LL A[MAX];

//PushUp函数更新节点信息 ,这里是求和
void PushUp(LL rt){
    Sum[rt] = Sum[rt<<1] + Sum[rt<< 1|1];
    //prLLf("888sum[%ll] = %ll\n", rt, Sum[rt]);
}

//PushDown下推标记
void PushDown(LL rt,LL ln,LL rn){
    //ln,rn为左子树,右子树的数字数量。 
    if(Add[rt]){
        //下推标记 
        Add[rt<<1]+=Add[rt];
        Add[rt<<1|1]+=Add[rt];
        //修改子节点的Sum使之与对应的Add相对应 
        Sum[rt<<1]+=Add[rt]*ln;
        Sum[rt<<1|1]+=Add[rt]*rn;
        //清除本节点标记 
        Add[rt]=0;
    }
}
//Build函数建树 
void Build(LL l,LL r,LL rt){ //l,r表示当前节点区间,rt表示当前节点编号
    //prLLf("l = %ll r = %ll\n", l, r);
    if(l==r) {//若到达叶节点 
        Sum[rt] = A[l];//储存数组值
        //prLLf("A[%ll] = %lld\n", l, A[l]);
        //prLLf("sum[%ll] = %ll\n", rt, Sum[rt]);
        return;
    }
    LL m=(l+r)>>1;
    //左右递归 
    Build(l,m,rt<<1);
    Build(m+1,r,rt<<1|1);
    //更新信息 
    PushUp(rt);
    //prLLf("888sum[%ll] = %ll\n", rt, Sum[rt]);
}



//点修改 A[L] + C
void Update(LL L,LL C,LL l,LL r,LL rt){//l,r表示当前节点区间,rt表示当前节点编号
    if(l==r){//到叶节点,修改 
        Sum[rt] = C;
        //prLLf("sum[%ll] = %ll\n", rt, Sum[rt]);
        return;
    }
    LL m=(l+r)>>1;
    PushDown(rt,m-l+1,r-m);//下推标记
    //根据条件判断往左子树调用还是往右 
    if(L <= m) Update(L,C,l,m,rt<<1);
    else       Update(L,C,m+1,r,rt<<1|1);
    PushUp(rt);//子节点更新了,所以本节点也需要更新信息 
} 

//区间修改
void UpdateRange(LL L,LL R,LL C,LL l,LL r,LL rt){//L,R表示操作区间,l,r表示当前节点区间,rt表示当前节点编号 
    if(L <= l && r <= R){//如果本区间完全在操作区间[L,R]以内 
        Sum[rt]+=C*(r-l+1);//更新数字和,向上保持正确
        Add[rt]+=C;//增加Add标记,表示本区间的Sum正确,子区间的Sum仍需要根据Add的值来调整
        return ; 
    }
    LL m=(l+r)>>1;
    PushDown(rt,m-l+1,r-m);//下推标记
    //这里判断左右子树跟[L,R]有无交集,有交集才递归 
    if(L <= m) UpdateRange(L,R,C,l,m,rt<<1);
    if(R >  m) UpdateRange(L,R,C,m+1,r,rt<<1|1); 
    PushUp(rt);//更新本节点信息 
} 


//区间查询, 这里是求和
LL QueryRange(LL L,LL R,LL l,LL r,LL rt){//L,R表示操作区间,l,r表示当前节点区间,rt表示当前节点编号
    if(L <= l && r <= R){
        //在区间内,直接返回 
        return Sum[rt];
    }
    LL m=(l+r)>>1;
    //下推标记,否则Sum可能不正确
    PushDown(rt,m-l+1,r-m); 
    
    //累计答案
    LL ANS= 0;
    if(L <= m) ANS += QueryRange(L,R,l,m,rt<<1);
    if(R > m) ANS += QueryRange(L,R,m+1,r,rt<<1|1);
    return ANS;
}

LL Query(LL l, LL r, LL rt, LL k){
    if(l == r){
        return l;
    }

    LL m = (l + r) >> 1;

    if(Sum[(rt << 1)] >= k){
        return Query(l, m, rt << 1, k);
    } else{
        return Query(m + 1, r, rt << 1 | 1, k - Sum[rt << 1]);
    }
}

     
//建树    Build(1,n,1); 
    
//点修改   Update(L,C,1,n,1);
    
//区间修改  UpdateRange(L,R,C,1,n,1);
    
//区间查询  LL ANS=Query(L,R,1,n,1);

int main(int argc, char const *argv[])
{
    LL n, q;
    scanf("%lld%lld", &n, &q);

    for(LL i = 1; i <= n; i++){
        scanf("%lld", &A[i]);
    }

    Build(1, n, 1);
    while(q--){
        char op[3];
              LL a , b , c;
              scanf("%s",op);
              if (op[1] == '1') {
                     scanf("%lld%lld%lld",&a,&b,&c);
                    UpdateRange(a,b,c,1,n,1);
              } else if(op[1] == '2'){
                     scanf("%lld%lld%lld",&a,&b,&c);
                     UpdateRange(a , b , -c , 1 , n , 1);
              }
              else if(op[1] == '3'){
                scanf("%lld%lld",&a,&c);
                Update(a,c,1,n,1);
              }
              else if(op[1] == '4'){
                scanf("%lld%lld",&a,&b);
              printf("%lld\n",QueryRange(a , b , 1 , n , 1));

        }
    }
    return 0;
}
View Code