2020牛客寒假算法基础集训营1题解

A

solution:

题意和icpc-final签到题相似呀
可将面积等于一的三角形分为下面五种情况：
1.两条边均平行x或y轴的；
2.一条边平行x轴，底为2、高为1
3.一条边平行x轴，底为1、高为2
4.一条边平行y轴，底为2、高为1
5.一条边平行y轴，底为1、高为2
第一种即以2*3点阵为最小单位，每个点阵中有四个好三角形
第二种即求出2 * m点阵中的底为2、高为1的好三角形，再乘上n - 1行
第三种即求出3 * m点阵中的底为1、高为2的好三角形，再乘上n - 2行
第四、五种。。。。

std:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9+7;
int main()
{
    ll n , m;
    cin>>n>>m;
    if(n == 2 && m == 2){
        printf("0");
        return 0;
    }
    ll ans = 0;
    ans = (n-1)*(m-2)*4%mod+(n-2)*(m-1)*4%mod;
    ans = (ans+2*(m-2)*(n-1)%mod*(m-2)%mod + 2*(n-2)*(m-1)%mod*(n-2)%mod)%mod;
    ans = (ans+2*(m-1)*(n-2)%mod*(m-2)%mod + 2*(n-1)*(m-2)%mod*(n-2)%mod)%mod;
    cout<<ans<< endl;
    return 0;
}

B

solution:

签到题之一

std:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    double n,x,a,b;
    cin>>n>>x>>a>>b;
    double ans1 = n*a;
    double ans2 = n*b;
    double ans = ans1*(x/100) + ans2*((100-x)/100);
    printf("%.2lf\n",ans);
    return 0;
}

C

solution:

计算几何，没写出来，赛后补的
首先同一个象限的肯定无法阻挡，剩下的点分别找到和x，y轴的交点，存到两个数组
记得用double，然后只需要用双指针移动窗口维护一个区间最短长度即可

std:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector< double > vx,vy;
int main()
{
    int n,k;
    double x,y,x1,y1,x2,y2;
    cin>>x1>>y1>>n>>k;
    k = n - k;
    for(int i=1;i<=n;i++){
        cin>>x>>y;
        if(x*x1 < 0){
            vy.push_back(y1 - x1*(y-y1)/(x-x1));
        }
        if(y*y1 < 0){
            vx.push_back(x1 - y1*(x-x1)/(y-y1));
        }
    }
    double ans = 1e18;
    sort(vx.begin(),vx.end()),sort(vy.begin(),vy.end());
    if(vx.size() >= k)
    {
        double l = 0,r = k-1;
        while(r < vx.size()){
            ans = min(ans , vx[r] - vx[l]);
            l++,r++;
        }
    }
    if(vy.size() >= k){
        double l = 0,r = k-1;
        while(r < vy.size()){
            ans = min(ans , vy[r] - vy[l]);
            l++,r++;
        }
    }
    if(ans == 1e18)
        printf("-1\n");
    else
        printf("%.8lf\n",ans);
    return 0;
}

D

solution:

直接用数组或者map存一下每一碗米饭数量，遍历一遍即可

std:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    int n,x;
    map<int , int> mp;
    cin>>n;
    for(int i=1;i<n;i++){
        cin>>x;
        mp[x] = 1;
    }
    int ans = 0;
    for(int i=1;i<=n;i++){
        if(mp[i] == 0){
            ans = i;
            break ;
        }
    }
    cout<<ans<<endl;
    return 0;
}

E

solution:

直接O(sqrt(n))遍历一遍即可，迭代次数很少，我还傻傻的判了个大素数

std:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll mod_exp(ll a,ll b,ll n)//快速幂取模
{
   ll m=1;
   while(b)
   {
      if(b&1) m=(m%n)*(a%n)%n;
      b>>=1;
      a=(a%n)*(a%n)%n;
   }
   return m;
}
bool miller_rabbin(ll n)
{
    ll i,a;
    for(i=0;i<50;i++)
    {
      a=rand()%(n-2)+2;
      if(mod_exp(a,n-1,n)!=1)
          return false;
    }
    return true;
}
int main()
{
    ll n ;
    cin>>n;
    if(miller_rabbin(n)){
        printf("1\n");
        return 0;
    }
    int ans = 0;
    while(1)
    {
        ll cnt = 2;
        ans++;
        for(ll i=2;i*i<=n;i++)
        {
            if(n%i == 0){
                if(n/i == i)
                    cnt++;
                else{
                    cnt+=2;
                }
            }
        }
        n = cnt ;
        if(n == 2){
            break;
        }
    }
    printf("%d\n",ans);
    return 0;
}

F

solution:

多么好的一道并查集，第一眼看成了树上dp
先说明一下我的思路，上图：

图片说明
我们首先将所有相邻的白色节点归入并查集，即1，2，3，4四个不同的集合
然后我们只需要遍历所有的黑色节点，找到他们相邻的所有白色节点的集合
我们看最中间的那个黑色节点，找到所有和它相连的白色集合，即1，2，3，4
这个节点对答案做出的贡献 = 分别和1，2，3，4相连 + 1和2相连 + 1和3相连 + 1和4相连 + 2和3相连 + 2和4相连 + 3和4相连
再不理解我可真没办法了

std:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 100005;
int f[maxn];
vector<int> v[maxn];
char s[maxn];
int a[maxn],b[maxn];
int find(int x)
{
    return x == f[x] ? x : f[x] = find(f[x]);
}
void unite(int x,int y)
{

    x = find(x);
    y = find(y);
    if(x != y){
        f[x] = y;
    }
    return ;
}
map<int , int> mp;
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        f[i] = i;
    }
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)
    {
        if(s[i] == 'B')
            a[i] = 1;
    }
    int x,y;
    for(int i=1;i<n;i++){
        scanf("%d %d",&x,&y);
        if(a[x] == 0 && a[y] == 0){
            unite(x,y);
        }
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i=1;i<=n;i++){
        int x = find(i);
        mp[x]++;
    }
    ll ans = 0;
    for(int i=1;i<=n;i++)
    {
        if(a[i] == 1){
            int cnt = 0;
            int siz = v[i].size();
            for(int j=0;j<siz;j++)
            {
                int x = v[i][j];
                if(a[x] == 1){
                    continue ;
                }
                b[++cnt] = mp[find(x)];
            }

            ans += b[cnt];
            for(int j=1;j<cnt;j++){
                ans += 1ll*(b[j]);
                for(int k=j+1;k<=cnt;k++){
                    ans += 1ll*(b[j]*b[k]);
                }
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}

G

solution:

尺举连续的k个相同字母的距离即可，先存一下每个字母的位置，然后遍历26个字母

std:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 200005;
int n,k;
char s[maxn];
vector<int> v[50];
int main()
{
    scanf("%d %d",&n,&k);
    scanf("%s",s+1);
    for(int i=1;i<=n;i++){
        v[s[i]-'a'].push_back(i);
    }
    int maxx = 0;
    for(int i=0;i<26;i++){
        int z = v[i].size();
        maxx = max(maxx , z);
    }
    if(maxx < k){
        printf("-1");
        return 0;
    }
    int ans = 1e9;
    for(int i=0;i<26;i++){
        if(v[i].size() < k){
            continue ;
        }
        int minn = v[i][k-1] - v[i][0] + 1;
        for(int j=k;j<v[i].size();j++){
            minn = min( minn , v[i][j] - v[i][j-k+1] + 1);
        }
        ans = min(ans , minn);
        if(ans == k){
            break ;
        }
    }
    printf("%d",ans);
    return 0;
}

H

solution:

分别处理两种操作即可。对于1变0的情况，可以分别统计每个1的前缀1和后缀1的位置（第一个1的前缀为 0 ，最后一个1的后缀为n+1 ），k 次操作，即变换连续k个1，最终的字符串长度就是第i个1的前缀1到第i+k个后缀1之间的距离。0的情况也是这样

std:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 200005;
char s[maxn];
int a[maxn][2],b[maxn][2];
vector<int> v[3];

int main()
{
    int n,k,cnt1 = 0,cnt0 = 0;
    scanf("%d %d",&n,&k);
    scanf("%s",s+1);
    int sum1 = 0,sum2 = 0;
    for(int i=1;i<=n;i++)
    {
        if(s[i] == '1'){
            sum1++;
        }else{
            sum2++;
        }
        v[s[i]-'0'].push_back(i);
        if(s[i] == '1'){
            a[i][0] = cnt0;
            a[i][1] = cnt1;
            cnt1++;cnt0 = 0;
        }
        else{
            a[i][0] = cnt0;
            a[i][1] = cnt1;
            cnt0++;cnt1 = 0;
        }
    }
    if(min(sum1 ,sum2) <= k){
        printf("%d",n);
        return 0;
    }
    cnt1 = cnt0 = 0;
    for(int i=n;i>=1;i--)
    {
        if(s[i] == '1'){
            b[i][0] = cnt0;
            b[i][1] = cnt1;
            cnt1++;cnt0 = 0;
        }
        else{
            b[i][0] = cnt0;
            b[i][1] = cnt1;
            cnt0++;cnt1 = 0;
        }
    }
    int ans = 1;
    int ans1 = v[0][k-1] - v[0][0] + 1 + b[v[0][k-1]][1] + a[v[0][0]][1];
    for(int i=k;i<v[0].size();i++)
    {
        int cnt = v[0][i] - v[0][i-k+1] + 1 + b[v[0][i]][1] + a[v[0][i-k+1]][1];
        ans1 = max(ans1 , cnt);
    }
    int ans2 = v[1][k-1] - v[1][0] + 1 + b[v[1][k-1]][0] + a[v[1][0]][0];
    for(int i=k;i<v[1].size();i++)
    {
        int cnt = v[1][i] - v[1][i-k+1] + 1 + b[v[1][i]][0] + a[v[1][i-k+1]][0];
        ans2 = max(ans2 , cnt);
    }
    ans = max(ans , max(ans1 , ans2));
    cout<<ans<<endl;
    return 0;
}

I

solution:

明显这是个dp，状态转移方程看公式，记得数组开long long

std:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[300005];
int main()
{
    ll n,x,y,z;
    string s;
    cin>>n>>x>>y>>z;
    cin>>s;
    for(int i=0;i<n;i++){
        if(i > 0)
            dp[i] = dp[i-1];
        if(i >= 3 && s[i-3] == 'n' && s[i-2] == 'i' && s[i-1] == 'c' && s[i] == 'o')
            dp[i] = max(dp[i] , dp[i-3] + x);
        if(i >= 5 && s[i-5] == 'n' && s[i-4] == 'i' && s[i-3] == 'c' && s[i-2] == 'o' && s[i-1] =='n' && s[i] == 'i')
            dp[i] = max(dp[i] , dp[i-5] + y);
        if(i >= 9 && s[i-9]=='n'&&s[i-8]=='i'&&s[i-7]=='c'&&s[i-6]=='o'&&s[i-5]=='n'&&s[i-4]=='i'&&s[i-3]=='c'&&s[i-2]=='o'&&s[i-1]=='n'&&s[i]=='i')
            dp[i] = max(dp[i] , dp[i-9] + z);
    }
    printf("%lld\n",dp[n-1]);
    return 0;
}

J

solution:

这一题需要用到的数论知识包括：费马小定理and矩阵快速幂
费马小定理可以简单理解为：
对于计算a^b%p ，而且p为素数，则有a^b%p = a^(b%(p-1))%p
矩阵快速幂：
矩阵快速幂和快速幂实质都是简化时间复杂度，时间复杂度都是log(n)
如果对矩阵快速幂还不熟悉，建议先学习一下如何使用矩阵快速幂，学过线性代数掌握起来会快一点。
如果对矩阵快速幂还不熟悉，建议先学习一下如何使用矩阵快速幂，学过线性代数掌握起来会快一点。

显然 f(n) 可以用 x , y 和 a 这三个因子表达出来。每一项a的幂次分别是 0、0、b、2b、4b、7b、12b……从第三项开始每一项为前两项之和加1。而x和y的幂次构成斐波那契数列：x的幂次第一项是1，第二项是0；y的幂次第一项是0，第二项是1。之后每一项均为前两项之和。

具体看代码，这道题目，无非是需要多写几个矩阵快速幂，但是一定要记得如果费马小定理和矩阵快速幂一起用的时候取模的哪些部分应该取mod-1，哪些应该取mod！

std:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll pow_mod(ll a,ll b,ll mod)
{
    ll ans = 1;
    while(b){
        if(b&1)
           ans = ans*a%mod;
        a = a*a%mod;
        b>>=1;
    }
    return ans;
}
const ll mod = 1e9 + 7;
struct node{
    ll m[2][2];
    node(){
        memset(m,0,sizeof(m));
    }
    friend node operator *(node a,node b){
          node ans;
          for(int i=0;i<2;i++)
              for(int j=0;j<2;j++)
                  for(int k=0;k<2;k++)
                      ans.m[i][j] = (a.m[i][k]*b.m[k][j] + ans.m[i][j])%(mod-1);
          return ans;
    }
    friend node pow(node a,ll k){
        node ans;
        ans.m[0][0] = ans.m[1][1] = 1,ans.m[0][1] = ans.m[1][0] = 0;
        while(k){
            if(k&1)
                ans = ans*a;
            a = a*a;
            k >>= 1;
        }
        return ans;
    }
};

struct node2{
    ll m[3][3];
    node2(){
        memset(m,0,sizeof(m));
    }
    friend node2 operator *(node2 a,node2 b){
          node2 ans;
          for(int i=0;i<3;i++)
              for(int j=0;j<3;j++)
                  for(int k=0;k<3;k++)
                      ans.m[i][j] = (a.m[i][k]*b.m[k][j] + ans.m[i][j])%(mod-1);
          return ans;
    }
    friend node2 pow(node2 a,ll k){
        node2 ans;
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                if(i == j)
                    ans.m[i][j] = 1;
                else
                    ans.m[i][j] = 0;
            }
        }
        while(k){
            if(k&1)
                ans = ans*a;
            a = a*a;
            k >>= 1;
        }
        return ans;
    }
};
ll solve1(ll x)
{
    node a,ans;
    a.m[0][0] = a.m[0][1] = a.m[1][0] = 1 ,a.m[1][1] = 0;
    ans = pow(a , x);
    return ans.m[0][1];
}
ll solve2(ll x)
{
    node a,ans;
    a.m[0][0] = a.m[0][1] = a.m[1][0] = 1 ,a.m[1][1] = 0;
    ans = pow(a , x);
    return ans.m[0][0];
}
ll solve3(ll x)
{
    node2 a,ans;
    a.m[0][0] = a.m[0][1] = a.m[0][2] = a.m[1][0] = a.m[2][2] = 1;
    a.m[1][1] = a.m[1][2] = a.m[2][0] = a.m[2][1] = 0;
    ans = pow(a , x);
    return ans.m[0][2];
}
int main()
{
    ll n , x , y , a, b;
    cin>>n>>x>>y>>a>>b;
    if(n == 1){
        printf("%lld\n",x%mod);
        return 0;
    }
    if(n == 2){
        printf("%lld\n",y%mod);
        return 0;
    }
    if(x%mod == 0 || y%mod == 0 || a%mod == 0){
        printf("0\n");
        return 0;
    }
    a = pow_mod(a%mod , b , mod);
    ll ans = pow_mod(x%mod , solve1(n-2) , mod)%mod*pow_mod(y%mod , solve2(n-2) , mod)%mod*pow_mod(a%mod , solve3(n-2)%(mod-1) , mod)%mod;
    cout<<ans<<endl;
    return 0;
}
全部评论

相关推荐

头像
梦屿千寻a
昨天 21:37
华南理工大学 机械类
点赞 评论 收藏
转发
头像
落落下个offer
05-11 11:06
深圳市睿联技术股份有限公司_研发中心_人工智能算法工程师(准入职员工)
睿联技术内推
5月还有大量HC，不限学校，不限学历，抓紧投递！今年校招包括暑期实习竞争特别激烈！大部分企业岗位HC在缩减，大家抓紧投递！越早投成功率越高！百分之70的岗位收获offer的人都是第一个月投递的！！深圳睿联技术股份有限公司2024届春招正式启动！【招聘对象】2024届海内外毕业生【招聘岗位】人工智能算法工程师、嵌入式/C语言软件开发工程师、web后端开发工程师、web前端开发工程师、测试工程师、运维工程师、电商运营、广告运营、海外销售、海外技术支持、编辑（西语/葡语）、米哈游海外推广、视频后期、平面设计等【公司福利】具有竞争力的薪资、礼包礼金、休闲活动应有尽有【内推码】DS8MVRSc【投递链接...
投递米哈游等公司10个岗位 >
点赞 评论 收藏
转发
头像
我不是麻瓜
04-22 17:12
南京理工大学 计算机类
点赞 评论 收藏
转发
头像
牛客汤汤
05-09 22:34
研发工程师
华为OD面经-C++开发
个人情况：1年半测开1年底被裁，双非渣硕；过年回来就开始投简历，刷题，想找开发结果无人问津，抱着试试看的心态去投递了华为od，最开始遇到的HR对我都不是上心，就问我要了身份证号就不管我了；后来偶然的机会在牛客上刷到了栗栗姐的面经，就联系了她，栗栗姐很热情，积极主动的给我聊了很多，那时候就知道自己是找对人了，所以果断切到栗栗姐这边，专心备战华为od的开发岗。备战心得：一定要听劝！一定要听劝！一定要听劝！！！一开始我备战就是只刷牛客上的题目，那时候天真的觉得好简单！然鹅，做了两个真题一下子打回了原形！！！多亏了栗栗姐，联系上她之后，先发我的经典题30多个，又找了专门的题库，并且给出了合理的刷题建议...
华为开奖95人在聊
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议
# 牛客帮帮团来啦！有问必答 #
665429次浏览 10984人参与
# 无实习如何秋招上岸 #
214797次浏览 3361人参与
# 如何写一份好简历 #
253316次浏览 3838人参与
# 毕业后不工作的日子里我在做什么 #
50685次浏览 681人参与
# 你的简历改到第几版了 #
296407次浏览 4481人参与
# 租房前辈的忠告 #
31260次浏览 2034人参与
# 硬件人的简历怎么写 #
76460次浏览 776人参与
# 华为开奖那些事 #
695608次浏览 5973人参与
# 简历中的项目经历要怎么写 #
423101次浏览 7205人参与
# 秋招开了，你想投哪些公司呢 #
115306次浏览 3234人参与
# 我想象的工作vs实际工作 #
90354次浏览 1526人参与
# 五一之后，实习真的很难找吗？ #
17382次浏览 109人参与
# 如何一边实习一边秋招 #
244180次浏览 4584人参与
# 你投了多少份简历，才拿到offer？ #
5448次浏览 60人参与
# 你已经投递多少份简历了 #
286737次浏览 4346人参与
# 浅聊一下我实习的辛苦费 #
78863次浏览 728人参与
# 我的上岸简历长这样 #
157605次浏览 3132人参与
# 我的成功项目解析 #
80251次浏览 2345人参与
# 数据人的面试交流地 #
182020次浏览 3835人参与
# 我的实习日记 #
441148次浏览 7907人参与
牛客网
牛客企业服务