首页 > 其他分享 >牛客周赛 Round 36(A~F)

牛客周赛 Round 36(A~F)

时间：2024-03-11 11:47:34浏览次数：22  
标签：int rep 36 long 牛客 second mp Round define

A

签到直接\(/1000\)输出即可

#include <bits/stdc++.h>

#define int long long
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define fep(i, a, b) for(int i = (a); i >= (b); --i)
#define _for(i, a, b) for(int i=(a); i<(b); ++i)
#define pii pair<int, int>
#define pdd pair<double,double>
#define ll long long
#define db double
#define endl '\n'
#define fs first
#define sc second
#define pb push_back
#define vi vector<int>

using namespace std;


void solve() {
    int n;
    cin>>n;
    cout<<n/1000<<'\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
//	freopen("C:\\Users\\24283\\CLionProjects\\untitled2\\1.in", "r", stdin);
    solve();
    return 0;
}

B

B题主要是一个异或和的概念
异或和是一些数连续异或。
直接按题意模拟即可。


#include <bits/stdc++.h>

#define int long long
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define fep(i, a, b) for(int i = (a); i >= (b); --i)
#define _for(i, a, b) for(int i=(a); i<(b); ++i)
#define pii pair<int, int>
#define pdd pair<double,double>
#define ll long long
#define db double
#define endl '\n'
#define fs first
#define sc second
#define pb push_back
#define vi vector<int>

using namespace std;
int a[110][110];

void solve() {
    int n,m,x;
    cin>>n>>m>>x;
    int res=0;
    rep(i,1,n){
        rep(j,1,m){
            cin>>a[i][j];
            res+=a[i][j];
        }
    }
    if(res!=x){
        cout<<"wrong answer\n";
        return;
    }
    //判断行得和
    int hy=0,ly=0;
//    rep(i,1,m)  hy^=a[1][i];
//    rep(i,1,n)  ly^=a[i][1];
    rep(i,1,n){
        int ans=0;
        rep(j,1,m){
            ans^=a[i][j];
        }
        hy+=ans;
    }

    rep(i,1,m){
        int ans=0;
        rep(j,1,n){
            ans^=a[j][i];
        }
        ly+=ans;
    }
    if(ly!=hy){
        cout<<"wrong answer\n";
        return;
    }
    cout<<"accepted\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
// 	freopen("C:\\Users\\24283\\CLionProjects\\untitled2\\1.in", "r", stdin);
    solve();
    return 0;
}

C

贪心、构造
考虑对答案的贡献。
如果一个数是小写字母对答案是没有贡献的后面只要出现一个大写字母就会对答案贡献1。
\(i\)是大写字母,如果\(i+1\)是大写字母对答案会贡献1
如果\(i+1\)是小写字母对答案

#include <bits/stdc++.h>

#define int long long
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define fep(i, a, b) for(int i = (a); i >= (b); --i)
#define _for(i, a, b) for(int i=(a); i<(b); ++i)
#define pii pair<int, int>
#define pdd pair<double,double>
#define ll long long
#define db double
#define endl '\n'
#define fs first
#define sc second
#define pb push_back
#define vi vector<int>

using namespace std;
int a[110][110];

void solve() {
    string s;
    cin>>s;
    int ans=0;
    rep(i,0,s.size()-2){
        if(islower(s[i])&&isupper(s[i+1])){
            ans++;
            i++;
            continue;
        }
        if(isupper(s[i])&& isupper(s[i+1])){
            ans++;
            i++;
            continue;
        }
    }
    cout<<ans<<'\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
// 	freopen("C:\\Users\\24283\\CLionProjects\\untitled2\\1.in", "r", stdin);
    solve();
    return 0;
}

D

昨天调了好久
之前一直没有注意入队出队的标记的问题
\(bfs一定要在入队的时候标记\)，如果一个点在出队的时候标记可能会出现下面情况
262612440b17542695a202b5c7c8f12.jpg

#include <bits/stdc++.h>

#define int long long
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define fep(i, a, b) for(int i = (a); i >= (b); --i)
#define _for(i, a, b) for(int i=(a); i<(b); ++i)
#define pii pair<int, int>
#define pdd pair<double,double>
#define ll long long
#define db double
#define endl '\n'
#define fs first
#define sc second
#define pb push_back
#define vi vector<int>

using namespace std;
int vis[1010][1010],d[1010][1010];
char mp[1010][1010];
int n,m;
int dx[]={0,0,0,1,-1};
int dy[]={0,1,-1,0,0};

void solve()
{
    cin>>n>>m;
    rep(i,1,n){
        cin>>(mp[i]+1);
    }
    queue<pii>q;
    q.push({1,1});
    d[1][1]=0;
    vis[1][1]=1;
    while(q.size()){
        auto u=q.front();
        q.pop();
//        vis[u.first][u.second]=1;
        if(u.first==n&&u.second==m){
            cout<<d[n][m]<<'\n';
            return;
        }
//         vis[u.first][u.second]=1;
        rep(i,1,4){
            int xx=u.first+dx[i];
            int yy=u.second+dy[i];
            if(xx<1||xx>n||yy<1||yy>m||vis[xx][yy])  continue;
            if(mp[xx][yy]==mp[u.first][u.second]) continue;
            q.push({xx,yy});
            vis[xx][yy]=1;
            d[xx][yy]=d[u.first][u.second]+1;
        }
    }
    cout<<-1<<'\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
//	freopen("C:\\Users\\24283\\CLionProjects\\untitled2\\1.in", "r", stdin);
    solve();
    return 0;
}

E

瞎搞的题目只需要构造3 * 3的矩阵其他随机就行

#include <bits/stdc++.h>

#define int long long
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define fep(i, a, b) for(int i = (a); i >= (b); --i)
#define _for(i, a, b) for(int i=(a); i<(b); ++i)
#define pii pair<int, int>
#define pdd pair<double,double>
#define ll long long
#define db double
#define endl '\n'
#define fs first
#define sc second
#define pb push_back
#define vi vector<int>

using namespace std;
int mp[1010][1010];
int n,m;

const unsigned zseed=time(0);
mt19937_64 zgen{zseed};
struct UI{
    //随机数的分布器
    //产生随机数的区间是[a,b]
    uniform_int_distribution<int>u;
    //随机数的生发器
    mt19937_64& gen{zgen};
    int get()
    {
        return u(gen);
    }
    UI(int a=0,int b=1):u(a,b){};
};

void solve() {
    UI u{0,26};
    int n,m;
    cin>>n>>m;
    mp[1][1]=mp[1][2]=3;
    mp[2][1]=mp[3][1]=2;
    mp[2][2]=mp[2][3]=mp[3][2]=1;
    rep(i,1,n){
        rep(j,1,m){
            if(!mp[i][j]){
                mp[i][j]=u.get();
            }
        }
    }
    rep(i,1,n){
        rep(j,1,m){
            cout<<(char)(mp[i][j]+'a');
        }
        cout<<'\n';
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
// 	freopen("C:\\Users\\24283\\CLionProjects\\untitled2\\1.in", "r", stdin);
    solve();
    return 0;
}

F

不包含长度不小于 2 的回文子串这个性质比较重要
先来看一下长度为2的回文串有哪些
aa
aba
abba
abcba
可以观察到一些性质
就是长度大于3的回文串会包含长度为2或3的回文串
所以好串的含义就是不包含长度为3的回文串
接着考虑假设第一个是r
那个第二个只能是e/d第三个就只能是d/e
这就启发我们修改成好串的情况只有3 * 2种
然后我们只需要在查询的时候比较一下6种那种是最小的
如何快速查询的这个可以用前缀和处理
但是设计到修改操作，所以这一需要一点点数据结构去维护
可以用树状数组去维护，线段树也是可以的.

#include <bits/stdc++.h>

#define int long long
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define fep(i, a, b) for(int i = (a); i >= (b); --i)
#define _for(i, a, b) for(int i=(a); i<(b); ++i)
#define pii pair<int, int>
#define pdd pair<double,double>
#define ll long long
#define db double
#define endl '\n'
#define fs first
#define sc second
#define pb push_back
#define vi vector<int>

using namespace std;
const int maxn = 2e5 + 10;
int tr[6][maxn];
int n,q;
string s;
string c[6]={"red","erd","dre","rde","edr","der"};
void add(int op,int x, int d){
    for(;x<=2e5;x+=x&-x)   tr[op][x]+=d;
}

int query(int op,int x){
    int res=0;
    for(;x;x-=x&-x) res+=tr[op][x];
    return res;
}

int ask(int op,int l,int r){
    return query(op,r)- query(op,l-1);
}

void solve() {
    cin>>n>>q;
    cin>>s;
    s=" "+s;
//    rep(i,1,n){
//        cout<<s[i];
//    }
//    cout<<'\n';
//    rep(i,1,n){
//        cout<<c[0][(i-1)%3];
//    }
//    cout<<'\n';
    //初始化树状数组
    rep(j,0,5){
        rep(i,1,n){
            int wei=i%3;
            int x=(s[i]!=c[j][wei]);
//            cout<<i<<' '<<x<<'\n';
            add(j,i,x);
        }
    }
    //q次操作
    while(q--){
        int op;
        cin>>op;
        if(op==1){//修改
            int x;
            char chr,lst;
            cin>>x>>chr;
            lst=s[x];
            //维护树状数组
            rep(i,0,5){
                int wei=x%3;
                if(s[x]!=c[i][wei]){
                    add(i,x,-1);
                }
                //修改
                s[x]=chr;
                if(s[x]!=c[i][wei]){
                    add(i,x,1);
                }
                s[x]=lst;
            }
            s[x]=chr;
        }else{//查询
            int res=1e9;
            int l,r;
            cin>>l>>r;
            rep(i,0,5){
                res=min(res,ask(i,l,r));
            }
            cout<<res<<'\n';
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
// 	freopen("C:\\Users\\24283\\CLionProjects\\untitled2\\1.in", "r", stdin);
    solve();
    return 0;
}

标签：int,rep,36,long,牛客,second,mp,Round,define
From： https://www.cnblogs.com/cxy8/p/18065708

相关文章

  • 洛谷题单指南-线性表-P3613 【深基15.例2】寄包柜
    原题链接：https://www.luogu.com.cn/problem/P3613题意解读：此题很容易想成用二维数组求解，但是最多有10^5*10^5个寄包柜格子，二维数据会爆空间，题目明确各自一共不超过10^7，所以需要动态数据结构vector。解题思路：vector的问题在于需要提前明确空间大小，才能进行随即访问操作，否则可......
  • 牛客周赛 Round 36 (小白练习记)
    A.小红的数位删除思路：这题简单输出即可Code:#include<bits/stdc++.h>usingnamespacestd;intmain(){strings;cin>>s;for(inti=0;i<s.size()-3;i++){cout<<s[i];}return0;}B.小红的小红矩阵构造思路:......
  • 牛客小白月赛88D
    不是很裸的01背包但是被卡了半天，所以记一下思路（？）对环的计算一般是从0-n-1，这样子转完一圈%n原位置就还是0，方便计算。然后二维dp，第一维表示第几次，第二维表示多少度。 #include<iostream>usingnamespacestd;intn,m;inta[5010];intf[5010][5010];intmain(){cin>......
  • 36. 人物动画
    人物动画状态机设置变量isParry 是否在防御isSleep 是否正在睡觉isDead 是否已经死亡attack 攻击hit 受伤skill 技能状态stand 站立parry_stand 防御hurt 受伤attack_pillow 攻击sleep 睡眠wake 醒来skill 技能death 死亡状态切换站立状态可以......
  • CF387B George and Round 题解
    考虑采用双指针法解决此题。首先需要对\(a,b\)数组排序，并且维护两个指针\(l,r\)，分别指向\(a,b\)两个数组中的元素。接着循环移动\(r\)指针，每次都尝试匹配\(a_l\)和\(b_r\)：若\(a_l\leb_r\)，则说明\(a_l=b_r\)或可以采用减少\(b_r\)的方式使\(a_l=b_r\)，这......
  • P3670 [USACO17OPEN] Bovine Genomics S 题解
    题意给定\(2\)组字符串，每组\(n\)个，每个字符串包含\(m\)个字符。我们称一个三元组\((i,j,k)\)是合法的，当且仅当第二组的每个字符串中下标为\((i,j,k)\)的字符拼成的字符串与第一组的每个字符串中下标为\((i,j,k)\)的字符拼成的字符串均不相等。现在需要你对于给定的......
  • 牛客小白月赛88补题D
    D-我不是大富翁题意：做法：一开始是往贪心方面想，但是很明显，贪不了。又因为走的步先后顺序没影响，可以用dp来写。暴力也差不多。值得注意的点是动力序列可以一边读入一边处理，省了点空间。如果dp[5005][5005]这样开的话会MLE，实际上在dp的过程中，用到的只是i和i-1两行，其余都是多余的。......
  • 牛客小白月赛88 (小白来了)
    A.超级闪光牛可乐思路:n个不同名称第i种提高Wi的诱惑值,之和不小于x就可以捕捉零食不超过1000个超过输出-1不超过输出字符串即可看一眼数据你会发现根本不需要考虑因为Wi的最小值是1所有直接输出任意的即可所有你只要一个ch即可后面直接输出即可不用管其他的Code:#includ......
  • Codeforces Round 656 (Div. 3) F. Removing Leaves
    ProblemDescription给出一棵\(n\)个节点的无根树。你可以进行以下操作：选择\(k\)个共同父节点的叶子节点，将\(k\)个节点和与父节点相连的边删去。求最大操作次数。Input第一行输入一个整数\(t\)\((1\let\le2\times10^4)\)，表示测试组数。接下来每组测试数据第......
  • 2023牛客暑期多校训练营2 B Link with Railway Company
    ProblemDescription给你一个\(n\)个节点的树状铁路网络，维护一条边每天需要花费\(c_i\)代价。现在有\(m\)条从\(a_i\)到\(b_i\)，每天的盈利为\(x_i\)，维护花费为\(y_i\)的路线可以运营。你可以选择一部分路线运营，求每日的最大收益。Input第一行输入两个整数\(n,......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99