北京信息科技大学第十一届程序设计竞赛

Problem A kotori和糖果

https://ac.nowcoder.com/acm/contest/940/A

题意：合并，求代价最小值

题解：将一个堆二分，递归求该堆合并的最小代价，用map判重。

C++版本一

/*
*@Author:   STZG
*@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
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
ll t,n,m,k,p,l,r,u,v;
ll ans,cnt,flag,temp,sum;
int a[N];
char str;
struct node{};
map<ll,ll>mp;
ll sloved(ll x){
    if(mp[x])
        return mp[x];
    if(x==0||x==1||( x & (x - 1)) == 0 )
        return mp[x]=0;
    if(x&1)
        return mp[x]=sloved(x>>1)+sloved((x>>1)+1)+1;
    else
        return mp[x]=2*sloved(x>>1);
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        cout<<sloved(n)<<endl;
    }

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem B kotori和气球

https://ac.nowcoder.com/acm/contest/940/B

题意：求满足要求的n个气球的排列种数

题解：当仅当第一个可以选择n种颜色，其他不能与前面相同，所以只能选择m-1种颜色

C++版本一

题解：快速幂+规律+数学

/*
*@Author:   STZG
*@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
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=109;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
ll t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N];
char str;
struct node{};
ll powmod(ll a,ll b=MOD-2,ll c=MOD){
    ll res=1;
    ll base=a%c;
    while(b){
        if(b&1)res=(res*base)%c;
        base=(base*base)%c;
        b>>=1;
    }
    return res;
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%lld%lld",&n,&m);
    cout<<(n*powmod(n-1,m-1,MOD))%MOD<<endl;
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

题解：dp递推，在第i个位置放颜色为x的球的方案数为在i-1处放除x以外的球的方案数之和
状态转移方程：s[i][x]=sum{s[i-1][y]，y!=x}

#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define LL long long
#define FI first
#define SE second
#define POP pop_back()
#define PII pair<LL,LL>
#define PCC pair<char,char>
#define endl '\n'
#define ls x<<1
#define rs x<<1|1
#define m(x) a[x].l+a[x].r>>1

const int N=1e3+7;
const int INF=1e8,mod=109;

LL a[N][N];
int n,m;

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        a[1][i]=1;
    }
    for(int i=2;i<=m;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                if(k==j)continue;
                a[i][j]=(a[i][j]+a[i-1][k])%mod;
            }
        }
    }
    LL ans=0;
    for(int i=1;i<=n;i++)ans+=a[m][i];
    ans%=mod;
    cout<<ans;
    return 0;
}

Problem C kotori和出道

https://ac.nowcoder.com/acm/contest/940/C

题意：约瑟夫环问题

题解：思维+规律+数学

C++版本一

题解：题目是经典的约瑟夫环问题

但是数据过大，不能用递归函数法解决

打表找规律可得，a是的最大值，则

/*
*@Author:   STZG
*@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
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
ll t,n,m,k,p,l,r,u,v;
ll ans,cnt,flag,temp,sum;
int a[N];
char str;
ll yuesefu(ll n,ll m=2){
        if(n == 1){
            return 0; //这里返回下标,从0开始，只有一个元素就是剩余的元素0
        }
        else{
            return (yuesefu(n-1,m) + m) % n; //我们传入的n是总共多少个数
        }
}
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        ans=0;
        m=n;
        while(m){
            ans++;
            m>>=1;
        }
        printf("%lld\n",(n-(1ll<<(ans-1)))*2+1);
    }

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem D kotori和迷宫

https://ac.nowcoder.com/acm/contest/940/D

题意：问出口数量和最近出口的距离

题解：BFS

C++版本一

/*
*@Author:   STZG
*@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
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int dir[4][2]={0,1,-1,0,1,0,0,-1};
int vis[50][50];
char str[50][50];
struct node{
    int x,y,step;
}x,f;
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%s",str[i]+1);
        for(int j=1;j<=m;j++){
            if(str[i][j]=='k')
                u=i,v=j;
        }
    }
    queue<node>q;
    x.x=u;
    x.y=v;
    x.step=0;
    ans=INF;
    vis[x.x][x.y]=1;
    q.push(x);
    while(!q.empty()){
        f=q.front();
        q.pop();//cout<<f.x<<" "<<f.y<<endl;
        if(str[f.x][f.y]=='e'){
            ans=min(ans,f.step);
            cnt++;
            continue;
        }
        for(int i=0;i<4;i++){
            x.x=f.x+dir[i][0];
            x.y=f.y+dir[i][1];
            x.step=f.step+1;
            if(1<=x.x&&x.x<=n&&1<=x.y&&x.y<=m&&str[x.x][x.y]!='*'&&!vis[x.x][x.y]){
                q.push(x);
                vis[x.x][x.y]=1;
            }
        }
    }
    if(ans==INF)
        cout<<-1<<endl;
    else
        cout<<cnt<<" "<<ans<<endl;
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem E kotori和素因子

https://ac.nowcoder.com/acm/contest/940/E

题意：

题解：线性筛出1-1000所有的质数，然后DFS求解最小值

C++版本一

/*
*@Author:   STZG
*@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
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=1000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int pre[M],prime[N],a[N],vis[N];
char str;
struct node{};
void dfs(int x,int now){
    if(x>n){
        ans=min(ans,now);
        return ;
    }
    for(int i=1;i<=cnt;i++){
        if(a[x]%pre[i]==0&&!vis[pre[i]]){
            vis[pre[i]]=1;
            dfs(x+1,now+pre[i]);
            vis[pre[i]]=0;
        }
    }
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    prime[0]=prime[1]=1;
    for(int i=2;i<M;i++){
        if(!prime[i]){
            pre[++cnt]=i;//cout<<i<<endl;
        }
        for(int j=1;j<=cnt&&i*pre[j]<M;j++){
            prime[i*pre[j]]=1;
            if(i%pre[j]==0)
                break;
        }
    }
    //cout<<cnt<<endl;
    //scanf("%d",&t);
    //while(t--){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    ans=INF;
    dfs(1,0);
    if(ans==INF)
        cout<<-1<<endl;
    else
        cout<<ans<<endl;
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem F kotori和n皇后

https://ac.nowcoder.com/acm/contest/940/F

题意：

题解：规律+STL

C++版本一

/*
*@Author:   STZG
*@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
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N];
char str;
struct node{
    ll x,y;
}e[N];
set<ll>sth,stl,st45,st135;
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    scanf("%d",&k);
    ans=INF;
    for(int i=1;i<=k;i++){
        scanf("%lld%lld",&e[i].x,&e[i].y);
        if(ans==INF&&(sth.count(e[i].x)||stl.count(e[i].y)||st45.count(e[i].x-e[i].y)||st135.count(e[i].x+e[i].y)))
            ans=i;
        sth.insert(e[i].x);
        stl.insert(e[i].y);
        st45.insert(e[i].x-e[i].y);
        st135.insert(e[i].x+e[i].y);
    }
    scanf("%d",&t);
    for(int i=1;i<=t;i++){
        scanf("%d",&m);
        cout<<(ans<=m?"Yes":"No")<<endl;
    }
#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem G kotori和抽卡（二）

https://ac.nowcoder.com/acm/contest/940/G

题意：

题解：组合数学

C++版本一

题解：

/*
*@Author:   STZG
*@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
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d%d",&n,&m);
    double ans=1.0;
    for(int i=m+1;i<=n;i++){
        ans*=0.2*i;
    }
    for(int i=1;i<=m;i++){
        ans*=0.8;
    }
    for(int i=1;i<=n-m;i++){
        ans/=i;
    }
    printf("%.4f\n",ans);
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem H andy和购物

https://ac.nowcoder.com/acm/contest/940/H

题意：

题解：贪心

C++版本一

/*
*@Author:   STZG
*@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
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
double ans,cnt,flag,temp,sum;
ll a[N];
double b[N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
        for(int i=1;i<=n;i++)scanf("%lf",&b[i]);
        sort(a+1,a+n+1);
        sort(b+1,b+n+1);
        ans=0;
        for(int i=1;i<=n;i++)ans+=a[i]*b[n-i+1];
        printf("%.3f\n",ans);
    }

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem I andy种树

https://ac.nowcoder.com/acm/contest/940/I

题意：

题解：差分

C++版本一

/*
*@Author:   STZG
*@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
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,q,u,v;
int ans,cnt,flag,temp,sum;
int a[N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=q;i++)scanf("%d%d",&l,&r),a[l]++,a[r+1]--;
    for(int i=1;i<=n;i++)a[i]+=a[i-1],printf("%d%c",a[i]," \n"[i==n]);
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem J andy的树被砍了

https://ac.nowcoder.com/acm/contest/940/J

题意：

题解：前缀和+二分

C++版本一

题解：对位置i，应该找i-n中cj前缀和超过hj的最小位置；

因此求出c的前缀和d；

二分查找的最小位置；

相当于所有树都种植在第一天，但是高度增加；

/*
*@Author:   STZG
*@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
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans[N],cnt,flag,temp,sum;
ll d[N],h[N],c[N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&h[i]);
    for(int i=1;i<=n;i++)scanf("%lld",&c[i]);
    for(int i=1;i<=n;i++)d[i]=c[i]+d[i-1];
    for(int i=1;i<=n;i++)printf("%lld%c",lower_bound(d+i,d+n+1,d[i-1]+h[i])-d," \n"[i==n]);
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}