2020-05-24 17:23 字节跳动_客户端_iOS开发

关注

第十五届中北大学算法与程序设计竞赛（公开赛）题解

B.真的是签到题

题意：
$输出三遍NUC2020!!!$
题解：
$确实是真！签到题，puts输出$
AC代码

/*
    Author:zzugzx
    Lang:C++
    Blog:blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//const int mod=1e9+7;
const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};


int main()
{
    //ios::sync_with_stdio(false);
    //cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    puts("NUC2020!!!");
    puts("NUC2020!!!");
    puts("NUC2020!!!");
    return 0;
}

A.俄罗斯方块

题意：
$10*10的图$
$给四种俄罗斯的图形，按俄罗斯的游戏规则，下降遇到即停$
$但是如果遇到整行满的情况不消除$
$给出n次下降的图形和最左块的坐标$
题解：
$n<=10并且图还很小$
$直接模拟下降过程即可$
$对每个方块的下落，判断每个点下个位置是否会碰到东西$
$如果没有碰到就继续下落，碰到了就停止，把图绘上去即可$
AC代码

/*
    Author:zzugzx
    Lang:C++
    Blog:blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//const int mod=1e9+7;
const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

int a[20][20];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n;
    cin>>n;
    for(int i=1,x,y;i<=n;i++){
        cin>>y>>x;
        if(y==1){
            int z=1;
            while(!a[z+1][x]&&!a[z+1][x+1]&&z<10)z++;
            a[z][x]=a[z-1][x]=a[z][x+1]=a[z-1][x+1]=1;
        }
        else if(y==2){
            int z=1;
            while(!a[z+1][x]&&!a[z+1][x+1]&&!a[z+1][x+2]&&z<10)z++;
            a[z][x]=a[z][x+1]=a[z][x+2]=a[z-1][x]=1;
        }
        else if(y==3){
            int z=1;
            while(!a[z+1][x]&&!a[z+1][x+1]&&!a[z+1][x+2]&&!a[z+1][x+3]&&z<10)z++;
            a[z][x]=a[z][x+1]=a[z][x+2]=a[z][x+3]=1;
        }
        else{
            int z=1;
            while(!a[z+1][x]&&!a[z+1][x+1]&&!a[z+1][x+2]&&z<10)z++;
            a[z][x]=a[z][x+1]=a[z][x+2]=a[z-1][x+1]=1;
        }
    }
    for(int i=1;i<=10;i++,cout<<endl)
        for(int j=1;j<=10;j++)
            cout<<a[i][j]<<' ';
    return 0;
}

K.签个到

题意：
$给n个数，进行m次操作$
$每次操作可以使得任意一个数加或减他的下标$
$问m次操作后这个数列的极差最大是多少$
题解：
$想让极差最大肯定是只修改一个数，把他修改成最大或最小$
$记录一下数列的最大值最小值$
$对于每一个数，找他和最小值或最大值的最大差$
$通过对该位的值加减下标可以扩大这个差值$
$看修改哪一个能使得极差最大$
AC代码

/*
    Author:zzugzx
    Lang:C++
    Blog:blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//const int mod=1e9+7;
const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

ll a[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ll n,m;cin>>n>>m;
    ll mi=inf,mx=-inf;
    for(int i=1;i<=n;i++)cin>>a[i],mi=min(mi,a[i]),mx=max(mx,a[i]);
    if(n==1){cout<<0;return 0;}
    ll ans=0;
    for(int i=1;i<=n;i++){
        ll k=max(abs(a[i]-mi),abs(a[i]-mx));
        ans=max(ans,k+i*m);
    }
    cout<<ans;
    return 0;
}

E.简单的线性代数

题意：
$给一个矩阵A和整数k，已知A^k=0$
$求E+A^1+……+A^k-1的逆$
题解：
$矩阵和整数其实是可以类比的$
$所以完全可以类比成等比数列$
$然后用一下等比数列的求和公式$
$即\frac{E-A^k}{E-A} \quad$
$然后题目要求的是这个式子的逆$
$A*B=E，其中B是A的逆$
$所以\frac{E-A^k}{E-A} \quad*B=E$
$B就是最终结果，并且A^k=0$
$化简式子最后B=E-A$
$就是对矩阵全体取负，对角线加1即可$
AC代码

/*
    Author:zzugzx
    Lang:C++
    Blog:blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//const int mod=1e9+7;
const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

ll a[1010][1010];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ll n,k;cin>>n>>k;
    for(int i=1;i<=n;i++,cout<<endl)
        for(int j=1;j<=n;j++)
            {
                ll x;
                cin>>x;
                if(i==j)cout<<1ll-x<<' ';
                else cout<<-x<<' ';
            }
    return 0;
}

G. 数位操作1

题意：
$给一个整数n(n<=1e10)$
$找到一个最小的数ans(ans>9)$
$ans需要满足他的每一位上数的乘积等于n$
题解：
$首先ans>9，如果n小于10的话$
$那么可以直接确定结果是(1n)$
$乘积能组成n的数，肯定是n的因子$
$所以进行对n的2到9因子分解，如果发现大于9的因子，说明不可行$
$但是会发现有的因子可以和自己或和别的因子相乘$
$我们需要留下的是最小值尽量小的几个小于10的因子$
$所以我们干脆直接倒着(从9到2)找因子$
$这样会尽量让多出来的不会被乘走的因子留下，并且解决了因子相乘还是在10以内的问题$
$然后找到所有因子倒序输出即可$
AC代码

/*
    Author:zzugzx
    Lang:C++
    Blog:blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//const int mod=1e9+7;
const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

int cnt[10];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ll n;
    while(cin>>n){
        vector<int> v;        
        if(n<10){cout<<1<<n<<endl;continue;}
        for(int i=9;i>1;i--)
            while(n%i==0)v.pb(i),n/=i;
        if(n>9){cout<<-1<<endl;continue;}
        reverse(all(v));
        for(auto i:v)cout<<i;
        cout<<endl;
    }
    return 0;
}

C. 港口

题意：
$有n件货物，第i件质量为w_i$
$可以对从第i件到第j件的质量进行加一或减一$
$问至少多少次能让全部货物质量相等$
题解：
$纯原题$
原题链接

$这个是运用了差分$
$对于每一件货物求出他和上一个货物的差值$
$如果想让全部相等，就是让这些差值都变为0$
$对于每次区间加操作，区间内部的差值不会改变$
$会改变的就是两端和外部的$
$比如差分数组为b，区间L到R加1$
$那么b_L++,b_{R+1}--$
$如果是进行减操作同理，b_L--,b_{R+1}++$
$所以问题转化，对差分数组进行多少次如下操作让数列全部变成0$
$对于2<=i,j<=n,b_i++,b_j--$
$所以我们只需要统计数组中有多少正数和负数$
$然后同时消除两种数，直到一种为0$
$剩余多出来的数全部和1进行操作，使得全部为0即可$
$另x为正数和，y为负数和$
$列出式子就是min(x，y)+abs(x-y)=max(x，y)$
AC代码

/*
    Author:zzugzx
    Lang:C++
    Blog:blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//const int mod=1e9+7;
const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

ll b[maxn],a[maxn];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    ll x=0,y=0;
    for(int i=1;i<=n;i++)b[i]=a[i]-a[i-1];
    for(int i=2;i<=n;i++){
        if(b[i]<0)y+=-b[i];
        else x+=b[i];
    }
    cout<<max(x,y);
    return 0;
}

F. 集合操作

题意：
$有n次操作，操作分为3种$
$1.如果集合中无x，插入x$
$2.如果集合有有x，删除x$
$找到>=x的最小的集合中没有的数$
题解：
$n<=1e6,x<=1e9$
$由于是要找一个没有的数$
$如果暴力找，n过大，如果已经插入很多连续数，会tle$
$但是如果想用一个set维护不存在集合里的数$
$x又是1e9，会mle$

$然后我就想到了可以用二分找一下不存在的数$
$但不存在的数又不是单调的，不能用二分找$
$所以就需要维护个数，看x到mid的集合存在个数是否等于mid-x+1$
$但是x很大，维护这个个数仍然会mle$
$所以我们就需要对这些x进行离散$
$将每个x和他的下一个点放入数组，由于需要表示中间的间隔$
$然后进行离散，离散完中间的个数就可以用树状数组维护$
$然后按刚才的思路进行二分查找即可$
AC代码

/*
    Author:zzugzx
    Lang:C++
    Blog:blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//const int mod=1e9+7;
const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=2e6+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

struct node{
    int id,x;
}p[maxn];
int a[maxn],c[maxn];
int lowbit(int x){
    return x&(-x);
}
void add(int x,int v){
    while(x<maxn){
        c[x]+=v;
        x+=lowbit(x);
    }
}
int query(int x){
    int res=0;
    while(x){
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n;cin>>n;
    for(int i=1;i<=n;i++)
        cin>>p[i].id>>p[i].x,a[2*i-1]=p[i].x,a[2*i]=p[i].x+1;
    int len=2*n;
    sort(a+1,a+1+len);
    len=unique(a+1,a+1+len)-a-1;
    for(int i=1;i<=n;i++){
        int op=p[i].id;
        int x=lower_bound(a+1,a+1+len,p[i].x)-a;
        if(op==1){
            if(!(query(x)-query(x-1)))add(x,1);
        }
        if(op==2){
            if(query(x)-query(x-1))add(x,-1);
        }
        if(op==3){
            int l=x,r=len,ans=-1;
            while(l<=r){
                int mid=l+r>>1;
                if(query(mid)-query(x-1)>=mid-x+1)ans=mid,l=mid+1;
                else r=mid-1;
            }
            if(ans!=-1)cout<<a[ans]+1<<endl;
            else cout<<a[x]<<endl;
        }
    }
    return 0;
}