头像

Ncik




离线:1小时前


活动打卡代码 AcWing 1344. 转换

Ncik
15小时前
#include<bits/stdc++.h>

using std::string;

const int MaxN = 10 + 5;
/* tempBeforeSquare是这样用的:一开始和beforeSquare相同,
   但在执行4时,就让它成为before的镜像,然后到第5个判断时会方便一些 */
string beforeSquare[MaxN], afterSquare[MaxN], tempBeforeSquare[MaxN];
int N;
/* N为原本读入的矩阵大小*/
/*后来发现一大堆地方N要-1,否则会越界,(话说C++越界跑起来连
  运行时错误都没有,差评)这是个很隐蔽的错误,Warning
 */

void debug1() {
    std::cerr << "temp\n";
    for (int i = 0; i < N; ++i) std::cerr << tempBeforeSquare[i] << "\n";
    std::cerr << "after\n";
    for (int i = 0; i < N; ++i) std::cerr << afterSquare[i] << "\n";
}

/*顺时针反转90度,看不懂的可以在纸上画一下*/
bool check_1() {
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            /* 这下面的N-1非常重要,差点调不出来……C++内存泄漏照常运行 */
            if (tempBeforeSquare[(N - 1) - j][i] != afterSquare[i][j]) {
                return false;
            }
        }
    }
    return true;
}
/*翻转180度*/
bool check_2() {
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (tempBeforeSquare[(N - 1) - i][(N - 1) - j] != afterSquare[i][j]) return false;
        }
    }
    return true;
}
/*顺时针反转270度*/
bool check_3() {
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (tempBeforeSquare[(N - 1) - j][i] != afterSquare[i][j]) {
                // std::cerr << i << (N - 1) - j << j << (N - 1) - i << tempBeforeSquare[i][(N - 1)- j] << afterSquare[j][(N - 1) - i] << "\n";
                return false;
            }  
        }
    }
    return true;
}

/*在上面的操作中,不会对数据进行变动,只是进行检测*/



/* 在下面的check_4中,我并没有复制上面的模块,加了一个isImage,
 * 因为在之后的check_5,我们将要“水平翻转后”再进行1/2/3操作。
 * 这后面的双重循环直接进行翻转
 */
bool check_4() {
    bool isImage = true;
    // std::cerr << tempBeforeSquare[2][0];
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {

                if (tempBeforeSquare[i][(N - 1) - j] != afterSquare[i][j]){
                    isImage = false;
                    // std::cerr << i << (N - 1) - j << j << tempBeforeSquare[i][(N - 1) - j] << afterSquare[i][j] <<  "\n";                     
                }

        }
    } 
    for (int i = 0; i < N; ++i) 
        for (int j = 0; j < N; ++j) 
                tempBeforeSquare[i][j] = beforeSquare[i][(N - 1) - j];            
    return isImage;
}

bool check_5() {
    bool f = (check_1() || check_2() || check_3()) ? true : false;
    return f;
}

bool check_6() {
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (beforeSquare[i][j] != afterSquare[i][j]) return false;
        }
    }
    return true;
}

void Init() {
    std::cin >> N;
    for (int i = 0; i < N; ++i) {
        std::cin >> beforeSquare[i];
        tempBeforeSquare[i] = beforeSquare[i];
    }
    for (int i = 0; i < N; ++i) std::cin >> afterSquare[i]; 
}

void Work() {
    // debug1();
    if (check_1() == true) {
        std::cout << 1 << std::endl;
        return;
    }
    if (check_2() == true) {
        std::cout << 2 << std::endl;
        return;
    }
    if (check_3() == true) {
        std::cout << 3 << std::endl;
        return;
    }
    // debug1();    
    if (check_4() == true) {
        std::cout << 4 << std::endl;
        return;
    }
    if (check_5() == true) {
        std::cout << 5 << std::endl;
        return;
    }
    if (check_6() == true) {
        std::cout << 6 << std::endl;
        return;
    }
    std::cout << 7 << std::endl;
}

int main() {
    Init();
    Work();
    return 0;
}


活动打卡代码 AcWing 1343. 挤牛奶

Ncik
15小时前
#include <bits/stdc++.h>
using namespace std;
int N; 
struct node{
    int begin, end;
}m[5005];
bool cmp(node a, node b){
    return a.begin < b.begin;
}
int main(){
    scanf("%d", &N);
    for(register int i = 1; i <= N; ++ i)
        scanf("%d%d", &m[i].begin, &m[i].end);
    sort(m + 1, m + 1 + N, cmp);
    int begin = m[1].begin;
    int end = m[1].end;
    int ans1 = 0, ans2 = 0;
    for(register int i = 2; i <= N; ++ i){
        if(m[i].begin <= end)
            end = max(end, m[i].end);
        else{
            ans1 = max(ans1, end - begin);
            ans2 = max(ans2, m[i].begin - end);
            begin = m[i].begin;
            end = m[i].end;
        }
    }
    ans1 = max(ans1, end - begin);
    printf("%d %d", ans1, ans2);
    return 0;
}


活动打卡代码 AcWing 1342. 断开的项链

Ncik
15小时前
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,let,las=0,cw=0;
char s[2000];
int main(){
    int i,ans=0;
    memset(s,0,sizeof(s));
    scanf("%d",&n);
    scanf("%s",s);
    char cp;
    for(i=0;i<n;i++){
        s[i+n]=s[i];
    }
    let=1;
    cp=s[0];
    for(i=1;i<2*n;i++){
        if(cp=='w') cp=s[i];
        if(s[i]==cp||s[i]=='w'){
            let++;
            if(s[i]=='w') cw++;
            else cw=0;
        }else{
            ans=max(ans,let+las);
            las=let-cw;
            let=cw+1;
            cw=0;
            cp=s[i];
        }
        //printf("c=%c  let=%d las=%d\n",s[i],let,las);
    }
    ans=max(ans,let+las);
    ans=min(ans,n);
    printf("%d",ans);
}


活动打卡代码 AcWing 1341. 十三号星期五

Ncik
16小时前
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
int main()
{
    int a[12]={3,3,0,3,2,3,2,3,3,2,3,2};//已经减去7的倍数,第一个是12月步进值
    int sum[7];//保存每天出现次数
    int i,j,n,day=4;//为四是保证第一次保存正确,从去年(1989-12-13)开始计算的,第一次保存在sum[0]即周六
    //memset(a,0,sizeof(a));//一定要注释,要不赋值就丢了
    memset(sum,0,sizeof(sum));//保证初始值为零
    scanf("%d",&n);//输入年份
    for(i=0;i<n;i++)
    {
        for(j=0;j<12;j++)
        {
            if(j==2 && ((((i+1900)%4==0) && ((i+1900)%100)) || ((i+1900)%400==0)))//对闰年且二月的判定
            {
                day=(day+a[j]+1)%7;//二月多一天
                sum[day]++;
            }
            else
            {
                day=(day+a[j])%7;
                sum[day]++;
            }
        }
    }
    for(i=0;i<7;i++)
    {
        printf("%d ",sum[i]);
    }
    return 0;
}


活动打卡代码 AcWing 1340. 贪婪的送礼者

Ncik
17小时前
#include<map>
#include<string>
#include<vector>
#include<iostream>
using namespace std;
int NP,money,num;
map<string,int> m;//存钱数 
vector<string> id;//存人名 
int main(){
    cin>>NP;
    string tmp;
    for(int i=1;i<=NP;i++){
        cin>>tmp;
        id.push_back(tmp);//人名加进数组里(为了最后有序输出) 
    }
    for(int i=1;i<=NP;i++){
        cin>>tmp>>money>>num;//人 钱 送的人数 
        if(money==0||num==0)continue;//不送礼的直接跳 
        m[tmp]-=money;//送走了这么多钱 
        m[tmp]+=money%num;//多的还回来 
        for(int j=1;j<=num;j++){
            cin>>tmp;
            m[tmp]+=money/num;//得到钱数 
        }
    }
    for(vector<string>::iterator i=id.begin();i!=id.end();i++)
        cout<<*i<<" "<<m[*i]<<endl;//遍历输出 
    return 0;
}



Ncik
20小时前
#include <iostream>
#include <cstring>

using namespace std;

int main() {
    char a[10], b[10];
    int sa = 1, sb = 1;
    cin >> a >> b;
    for (int i = 0; i < strlen(a); i++) {
        sa *= (a[i] - 'A' + 1);
    }
    for (int i = 0; i < strlen(b); i++) {
        sb *= (b[i] - 'A' + 1);
    }
    if (sa % 47 == sb % 47) cout << "GO" << endl;
    else cout << "STAY" << endl;
    return 0;
}



Ncik
1天前

算法

(模拟) $O(n^2)$

首先替换的下标必定递增,否则会出现逆序对,那么从前往后模拟一遍,检查是否排好序就行了。

C++ 代码

#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::vector;
using std::swap;

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n, x;
        cin >> n >> x;
        vector<int> a(n);
        for (auto& it : a) cin >> it;
        int cnt = 0;
        for (int i = 0; i < n && !is_sorted(a.begin(), a.end()); ++i) {
            if (a[i] > x) {
                swap(a[i], x);
                cnt++;
            }
        }
        cout << (!is_sorted(a.begin(), a.end()) ? -1 : cnt) << '\n';
    }

    return 0;
}



Ncik
2天前

算法

(二分) $O(n\log n)$
  • 顶峰的左边是一段连续的子序列,并且是递增的子序列;顶峰的右边是一段连续的子序列,并且是递减的子序列。
  • 显然最少删除次数,就是让左右的子序列越长越好。
  • 那么我们用最长上升子序列算法 $O(n\log n)$ 算出以每个元素为右端点的最长上升子序列长度 ls[i],和以每个元素为左端点的最长下降组序列长度 rs[i],答案就是最小的 n - 1 - ls[i] - rs[i]

C++ 代码

class Solution {
public:
    int minimumMountainRemovals(vector<int>& a) {
        int n = a.size();
        vector<int> ls(n, 0), rs(n, 0), dp(n, 0x3f3f3f3f);
        for(int i = 0; i < n; ++i) {
            int p = lower_bound(dp.begin(), dp.end(), a[i]) - dp.begin();
            dp[p] = a[i];
            ls[i] = p;
        }
        fill(dp.begin(), dp.end(), 0x3f3f3f3f);
        for(int i = n - 1; i >= 0; --i) {
            int p = lower_bound(dp.begin(), dp.end(), a[i]) - dp.begin();
            dp[p] = a[i];
            rs[i] = p;
        }
        int ans = n;
        for(int i = 1; i < n - 1; ++i) {
            ans = min(ans, n - 1 - ls[i] - rs[i]);
        }
        return ans;
    }
};



Ncik
3天前
class Solution {
public:
    int minimumMountainRemovals(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n + 1), f(n + 1);
        nums.insert(nums.begin(), 0);
        for (int i = 1; i <= n; ++i) {
            dp[i] = 1;
            for (int j = 1; j < i; ++j) {
                if (nums[j] < nums[i]) dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        for (int i = n; i >= 1; --i) {
            f[i] = 1;
            for (int j = i + 1; j <= n; ++j) {
                if (nums[i] > nums[j]) f[i] = max(f[i], f[j] + 1);
            }
        }
        int ans = INT_MAX;
        for (int i = 2; i + 1 <= n; ++i) {
            int x = n - dp[i] - f[i] + 1;
            ans = min(ans, x);
        }
        return ans;
    }
};




Ncik
3天前
class FrontMiddleBackQueue {
public:
    vector<int> v;
    FrontMiddleBackQueue() {
        v.clear();
        v.push_back(0);
    }

    void pushFront(int val) {
        v.insert(v.begin() + 1, val);
    }

    void pushMiddle(int val) {
        v.insert((v.size() + 1) / 2 + v.begin(), val);
    }

    void pushBack(int val) {
        v.push_back(val);
    }

    int popFront() {
        if (v.size() == 1) return -1;
        int x = v[1];
        v.erase(v.begin() + 1);
        return x;
    }

    int popMiddle() {
        if (v.size() == 1) return -1;
        int x = v[v.size() / 2];
        v.erase(v.begin() + v.size() / 2);
        return x;
    }

    int popBack() {
        if (v.size() == 1) return -1;
        int x = v.back();
        v.pop_back();
        return x;
    }
};