牛客练习赛82

[Mocha的字符串]

/*
一点点小思考：
本来我来存有字符串 Mocha 的初始位置
但是我的循环写的是 for(int i=1;i<=n-4;i++)...
如果引用(s.substr ....)下标的位置会错 

然后学到了可以用一个数组或者(vector)
来存 字符串 Mocha 的初始位置
通过比较vector的长度 与 k 的关系
*/ 


#include<bits/stdc++.h>
using namespace std;

int n,k;
vector<int> v;
string s;

int main(){
    cin >> n >>k;
    getchar();
    cin >> s;
    for(int i=1;i<=n-4;i++){
         if(s[i]=='m'&&s[i+1]=='o'&&s[i+2]=='c'&&s[i+3]=='h'&&s[i+4]=='a')
            v.push_back(i);
    }
    if(v.size()<k){
        cout<<"poor Mocha"<<endl;
    }
    else {
        cout<<"Mocha suki!"<<endl;
        int ans= n;
        for(int i =0;i+k-1<v.size();i++){
            ans=min(ans,v[i+k-1]-v[i]+5);
        } 
        cout<<ans<<endl;
    }

    return 0;
}

牛客小白月赛33

[字符统计]

/*
题意：输出每个样例共有几句字符串，几个单词，多少个字符

难点：怎么算多少个单词
    考虑字符和空格 1 vs 1抵消的次数  

*/ 

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin >> n;
    getchar();
    while(n--){//有几组数据 
        int sum1=0,n=0,w=0;//每种个数 
        string s;
        while(getline(cin,s)){
            if(s=="=====") break;
            sum1++;//计算有多少句字符串 
            int len=s.size();
            int m=0,x=0;//记得把x清零 
            n+=len;//计算字符 

            for(int i=0;i<len;i++){
                if(s[i]!=' ') x++;
                else{
                    if(x!=0){
                        x=0;
                        w++;
                    }
                }
            }
            if(x!=0) w++;

        }
        cout<<sum1<<' '<<w<<' '<<n<<endl; 
    }
    return 0;
}

2021牛客寒假算法基础集训营6

[I-贪吃蛇]

有个小细节：
提示：Redefinition of ‘y1’ as different kind of symbol
重定义了y1。
此次定义的y1变量与C语言函数库<math.h>中定义的y1重名了，把变量名字y1换掉

/*
求最短路径 bfs 
*/
#include<bits/stdc++.h>
using namespace std;
int n,m;
int x,y,nx,ny;
const int N = 400;
char a[N][N];
#define CHECK(x,y) (x>=1&&x<=n&&y>=1&&y<=m)

int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int vis[N][N];
struct node{
    int x;
    int y;
}now,nxt;

int dist[N][N];
int bfs(){
    queue<node> q;
    memset(dist,-1,sizeof(dist));
    now.x=x;
    now.y=y;
    q.push(now);
    vis[now.x][now.y]=1;
    dist[now.x][now.y]=0;
    while(!q.empty()){
        now = q.front();
        q.pop();    
        for(int i=0;i<4;i++){
            nxt.x=now.x+dir[i][0];
            nxt.y=now.y+dir[i][1];
            if(CHECK(nxt.x,nxt.y)==true && vis[nxt.x][nxt.y]!=1 && a[nxt.x][nxt.y]!='#'){
                dist[nxt.x][nxt.y] = dist[now.x][now.y]+1;
                vis[nxt.x][nxt.y]=1;
                if(nxt.x==nx && nxt.y==ny) return dist[nxt.x][nxt.y]*100;
                q.push(nxt);
            }
        }
        }
        return -1;
    } 


int main(){
    cin >> n >> m;
    cin>>x>>y>>nx>>ny;
    getchar();

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            cin >> a[i][j]; 
    }
    cout<<bfs()<<endl;
}

牛客小白月赛34

[F-dd爱框框]

inline int read()
{
    int X=0; bool flag=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
    while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
    if(flag) return X;
    return ~(X-1);
}

//快读：
inline int read(int &x){
    x = 0; int f = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')  x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return x * f;
}
//快输：
inline void write(int n){
    if(n<0){putchar('-');n=-n;} 
    if(n>9)write(n/10);
    putchar(char(n%10+'0'));
}

//用法:
read(n)；
write(n);

ios::sync_with_stdio(false);
//取消scanf 和 cin 同步，可加速cin cout速度 但是不能再用scnaf printf


#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10;
int a[N];
int main(){
    int n,x;scanf("%d%d",&n,&x);
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    int s=0;
    int len=1e9,tl=-1,tr=-1;
    for(int l=1,r=1;l<=n;l++){
        while(s<x&&r<=n)s+=a[r++];
        if(s>=x&&r<=n&&r-l<len){
            len=r-l,tl=l,tr=r-1;
        }
        s-=a[l];
    }
    cout<<tl<<' '<<tr;
} 


#include <cstdio>
using namespace std;
void read(int &x) {
    x = 0; char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
}

const int N = 1e7 + 100;

int n, x;
int sa[N];
int main() {
    scanf("%d%d", &n, &x);
    for (int i = 1; i <= n; i++) read(sa[i]);
    int ql = 0, qr = n, sum = 0;
    for (int r = 1, l = 1; r <= n; r++) {
        sum += sa[r];
        if (sum < x) continue;
        while (sum - sa[l] >= x) sum -= sa[l++];
        if (r - l < qr - ql) qr = r, ql = l;
    }
    printf("%d %d\n", ql, qr);
    return 0;
}

[dd爱科学]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int lis(vector<int> a) {
    vector<int> dp;
    for(int i : a) {
        if(dp.empty() || dp.back() <= i) dp.push_back(i);
        else dp[upper_bound(dp.begin(), dp.end(), i) - dp.begin()] = i;
        //这一行！假如样例ACBBEF 必须要把加入的C替换成B
    }
    return dp.size();
}
int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> a;
    for(char c : s) a.push_back(c - '0');
    cout << a.size() - lis(a) << '\n';
}


#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
char s[N];
int n,dp[30],ans;
int main(){
    scanf("%d",&n);
    scanf("%s",s);
    for(int i=0;i<n;++i){
        int v=s[i]-'A',x=dp[v];
        for(int j=0;j<v;++j){
            dp[v]=max(dp[v],dp[j]+1);
        }
        dp[v]=max(dp[v],x+1);//计算首字母为 0 ，或者有重复元素++
        ans=max(ans,dp[v]);
    }
    printf("%d\n",n-ans);
    return 0;
}

[dd爱旋转]

无论是第一种方式还是第二种方式
只要旋转两次就恢复与哪来的状态
然后注意两种方式坐标的交换
#include<bits/stdc++.h>
using namespace std;

int n,q,cnt,t,cnt1=0,cnt2=0;
const int N = 1005;
int a[N][N];

int main(){
    cin >> n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++) {
            scanf("%d",&a[i][j]);
        }
    }
    cin >>q;
    while(q--){
        cin >> t;
        if(t==1) cnt1++;
        if(t==2) cnt2++;
    }
    cnt1%=2;
    cnt2%=2;

    if(cnt1){
        for(int i=0;i<n;i++){
            for(int j = 0;j<i;j++) 
                swap(a[i][j],a[n-i-1][n-j-1]); 
        }
        for(int i=0;i<n/2;i++) 
            swap(a[i][i],a[n-i-1][n-i-1]);
    }
    if(cnt2){
        for(int i=0;i<n/2;i++){
            for(int j=0;j<n;j++)
                swap(a[i][j],a[n-i-1][j]);
        } 
    }
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            if(j!=0) printf(" ");
            printf("%d",a[i][j]);
        }
        printf("\n");
    }

    return 0;
}

兰州大学第一届『飞马杯』程序设计竞赛（同步赛）

[C-★★生命的游戏★★]

#include<bits/stdc++.h>
using namespace std;
#define maxn 105
int T, n, k, ans, a[maxn][maxn], now[maxn][maxn], s[maxn][maxn], di[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dj[] = {-1, 0, 1, -1, 1, -1, 0, 1};
inline bool Check() {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (a[i][j] != now[i][j]) return 0;
    return 1;
}
inline void Solve() {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            s[i][j] = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (now[i][j]) {
                for (int k = 0; k < 8; k++) {
                    int ni = (i + di[k] + n) % n, nj = (j + dj[k] + n) % n;
                    s[ni][nj]++;
                }
            }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (s[i][j] == 3) now[i][j] = 1;
            else if (s[i][j] < 2 || s[i][j] > 3) now[i][j] = 0;
}
int main()
{
    cin >> T;
    while (T--) {
        cin >> n >> k;
        ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                cin >> a[i][j];
                now[i][j] = a[i][j];
            }
        do {
            Solve();
            ans++;
        }
        while (!Check() && --k);
        if (k) cout << "YES" << endl << ans << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

牛客小白月赛35

[B-我不是酸菜鱼]

注意 $ai$的数据范围很大，注意输入

题目求的是把所有数乘起来对 2 取余的最大值 k，
那么 k 可以看作是每一个数贡献了多少个 2
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n,a;
int main(){
    scanf("%lld",&n);
    ll cnt = 0;
    for(int i =1;i<=n;i++){
        scanf("%lld",&a);
        while(a%2==0){
            ++cnt;
            a/=2;
    }
}
    printf("%lld",cnt);
}

[C-杨辉的行积]

第 0 行 1
第 1 行 1 1
第 2 行 1 2 1
第 3 行 1 3 3 1
第 4 行 1 4 6 4 1
第 5 行 1 5 10 10 5 1 

1. 每一行的系数和 $11^n$ 有关
$ 1 = 11^0$
$ 11 = 11^1$
$121 = 11^2$

2.每一行的每一个系数 $（x+y)^2$
3.每一行的系数之和是 $2^n$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 1000005;
const int mod = 1e9+7;
ll f[maxn],rf[maxn];
ll fpow(ll a,ll b){//幂函数 
    ll r=1;
    for(a%=mod;b;b>>=1){
        if(b&1)r=r*a%mod;a=a*a%mod;
        }
        return r;
    }
void init(int n) {//初始化 
    f[0] = 1;
    for(int i=1;i<=n;++i) f[i]=f[i-1]*i%mod;
    rf[n] = fpow(f[n],mod-2);
    for(int i=n-1;i>=0;--i) rf[i]=rf[i+1]*(i+1)%mod;
}
ll comb(ll n,ll k){//求从 n 个数取出 k个进行排列组合 
    if(n<k||k<0)return 0;
    return f[n]*rf[k]%mod*rf[n-k]%mod;
    }

int main() {
    int n;
    cin>>n;
    --n;
    init(n);
    ll ans=1;
    for(int i=1;i<=n;++i) 
        ans=ans*comb(n,i)%mod;
    cout<<ans<<endl;
}

牛客小白月赛32

[C-消减整数]

#include<bits/stdc++.h>
using namespace std;

/* 
相同或者是两倍 
3 = 1 +2；
5 = 1+2+2；
7 = 1+2+4 
*/ 
int main(){
    int t,a;cin >> t;
    while(t--){
        cin >>a;
        int now =1 ,ans= 0;
        while(a){
            a-=now,ans++;
            if(a%(now*2)==0) now*=2;//更新now的值 
        }
        cout<<ans<<endl;
    } 
    return 0;
}

[E-春游]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t ,n ,a,b;
int main(){
    cin >>t;
    while(t--){
        cin >> n >> a >> b;
        if (n <= 2) {
        cout<<min(a,b)<<endl;
        continue;
    }
    ll val1 = a / 2, val2 = b / 3;
    ll ans;
    if (val1 < val2) {
        ans = (n / 2) * a;
        if (n & 1) {//有余数，比较再加一艘船，或者去掉一艘两人船加上三人船 
            ans = min( ans + min(a,b),ans - a + b );
        }
    }
    else {
        ans = (n / 3) * b;
        if (n % 3 == 1) {
            ans = min( ans + min(a,b),ans - b + 2 * a );
        }
        else if (n % 3 == 2) {
            ans = min( ans + min(a,b),ans - b + 3 * a );
        }
    }
            cout<<ans<<endl;
    }

    return 0;
} 

[拼三角]

/*
题意：六个数字组成两个三角形
注意next_permutation(..) 需要sort排序
然后关于check函数
先找的反例，因为一个三角形任意两条边都大于第三边
不满足条件就false 
但是如果能够确定三个个数字中国最大值，
也可以直接用两边之和大于第三边（正向思考） 

*/ 

#include<bits/stdc++.h>
using namespace std;

int t,a[7];
int check(int a,int b,int c){
    if(a+b<=c ||a+c<=b ||b+c<=a) return 0;
    return 1;
}
int main(){
    cin >>t;
    while(t--){
        for(int i=0;i<6;i++) cin >>a[i];
        sort(a,a+6);
        int flag=0;
    do{
        if(check(a[0],a[1],a[2]&&check(a[3],a[4],a[5]))){
            flag=1;
            break;
        }
    }while(next_permutation(a,a+6));
    if(flag) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    }
    return 0;
}

2021牛客暑期多校训练营1

[B-Ball Dropping]

在C语言的math.h或C++中的cmath中有两个求反正切的函数atan(double x)与atan2(double y,double x)  他们返回的值是弧度

前者接受的是一个正切值（直线的斜率）得到夹角，但是由于正切的规律性本可以有两个角度的但它却只返回一个，因为atan的值域是从-90~90 也就是它只处理一四象限，所以一般不用它。

第二个atan2(double y,double x) 其中y代表已知点的Y坐标 同理x ,返回值是此点与远点连线与x轴正方向的夹角，这样它就可以处理四个象限的任意情况了，它的值域相应的也就是-180~180了

#include<bits/stdc++.h>
using namespace std;
int main(){
    double r,a,b,h;cin >> r>> a>> b>>h;
    if(2*r<=b) {
        cout<<"Drop"<<endl;
    } 
    else{
        cout<<"Stuck"<<endl;
        double x = b*h/(a-b);
        double t = sqrt((b*b/4)+x*x);
        double y = r*t/(b/2);
        printf("%.10f\n",y-x);
    }
}
/* 
关于三角函数的写法 
    double x=atan2(h,(a-b)/2.0);
    double h1=r/cos(x);
    double h2=b/2.0*tan(x);
    cout<<"Stuck\n";
    printf("%.10f\n",h1-h2);
*/ 

牛客小白月赛41

[小红的数组]

#include <bits/stdc++.h>
using namespace std;
int a[300005];
typedef long long ll;
int main() {
//  ios::sync_with_stdio(false);
//  cin.tie(nullptr);
    int n;
    ll k;
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    sort(a, a + n);
    ll x = 0, y = 0, z = 0;
    for (int i = 0; i < n; ++i) {
        int p = lower_bound(a + i + 1, a + n, 1.0 * k / a[i]) - a - i - 1;
        int q = upper_bound(a + i + 1, a + n, 1.0 * k / a[i]) - a - i - 1;
        x += p, y += q - p, z += n - i - 1 - q;
    }
    cout << z << ' ' << y << ' ' << x;//大 中 小
    return 0;
}

[小红的rpg游戏]

/*
vis 标记数组为三维(当前坐标xy+当前血量值) 
ok函数的构造 

*/

#include<bits/stdc++.h>
using namespace std;
int n,m,h;
string g[55];
int dir[][2]={{0,1},{0,-1},{1,0},{-1,0}};
bool vis[55][55][55];
struct node{
    int x,y,hp,cnt;
};

int ok(int x,int y,int hp){//是否可以继续前行的判断 
    if(x<0||x>=n||y<0||y>=m||g[x][y]=='*') return -1;
    if(g[x][y]>='0'&&g[x][y]<='9')
        return hp-(g[x][y]-'0');
    return hp;
}
int main(){
    cin >> n >> m >> h;
    for(int i=0;i<n;i++) cin >>g[i];
    queue<node> q;
    q.push((node){0,0,h,0});
    vis[0][0][h] = 1;
    while(!q.empty()){
        node u = q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int sx = u.x+dir[i][0];
            int sy = u.y+dir[i][1];
            int xx = ok(sx,sy,u.hp);
            if(xx>0 && !vis[sx][sy][xx]){
                vis[sx][sy][xx] = 1;
                q.push((node){sx,sy,xx,u.cnt+1});
                if(sx==n-1&&sy==m-1) {
                    cout<<u.cnt+1<<endl;
                    return 0;
                }
            }
        }
    }
    cout<<"-1"<<endl;
    return 0; 
}

进制转化

其他进制转化为十进制
ll get(string n,int r){
    ll ans = 0;
    for(int i=0;i<n.size();i++){
        ans = ans*r+(n[i]-'0');
    }
    return ans;
}

十进制转其他进制
while (cin >> n) {
        cnt = 0;
        do {
            a[cnt++] = n % 2;
            n /= 2;
        } while (n != 0);
        for (int i = cnt - 1; i >= 0; i--) {
            cout << a[i];
        }
    }

转成16进制
char h[17] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'}; // 记录十六进制的各个数
do {
            a[cnt++] = n % 16;
            n /= 16;
        } while (n != 0);
        for (int i = cnt - 1; i >= 0; i--) {
            int k = a[i];
            cout << h[k];
        }
    }