2022.5.14(2022.5.14)

AtCoder Beginner Contest 251

A – Six Characters

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=1e5+10,INF=1e9;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin>>s;
    int pos=0,cnt = 0;
    while(cnt<6)
    {
        cout << s[pos];
        cnt++;
        pos++;
        if(pos==s.length())
        {
            pos = 0;
        }
    }
    return 0;
}

B – At Most 3 (Judge ver.)

这件事情告诉我不要乱用map。。。查询是O(logn),会超时。。。以后能开数组尽量开数组。。。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=3e6+10,INF=1e9;
bool vis[N];
int a[310];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,w;
    int cnt = 0;
    cin >> n >> w;
    for (int i = 1; i <= n;i++)
    {
        cin >> a[i];
        if(!vis[a[i]]&&a[i]<=w)
        {
            vis[a[i]] = 1;
            cnt++;
        }
    }
    for (int i = 1; i <= n;i++)
    {
        for (int j = i + 1; j <= n;j++)
        {
            if(i==j)
                continue;
            if(!vis[a[i]+a[j]]&&a[i]+a[j]<=w)
            {
                vis[a[i] + a[j]] = 1;
                cnt++;
            }
            for (int k = j + 1;k<=n;k++)
            {
                if(!vis[a[i]+a[j]+a[k]]&&a[i]+a[j]+a[k]<=w)
                {
                    vis[a[i] + a[j] + a[k]] = 1;
                    cnt++;
                }
            }
        }
    }
    cout << cnt;
    return 0;
}

C – Poem Online Judge

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=1e5+10,INF=1e9;
map<string, int> vis;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    int ans = -1;
    int pos = 0;
    for (int i = 1; i <= n;i++)
    {
        string s;
        cin >> s;
        int res;
        cin >> res;
        if(!vis[s])
        {
            vis[s] = 1;
            if(res>ans)
            {
                ans = res;
                pos = i;
            }
        }
    }
    cout << pos;
    return 0;
}

D – At Most 3 (Contestant ver.)

想到了构造的思路,但仅限于用1-3000,看完题解发现只需要1-100以及它们乘100,1000就可以了,巧妙

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=1e5+10,INF=1e9;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<300<<'\n';
    for (int i = 1; i <= 100;i++)
    {
        cout << i << ' ' << i * 100 << ' ' << i * 10000  << ' ';
    }
        return 0;
}

E – Tahakashi and Animals

有点像力扣的环形打家劫舍问题,对于第一个点我们选择选或者不选,对于后面的2-n个点,假设当前为第i个点,如果第i-1个点没有选那么我们必须要选,如果第i-1个点选了,我们可以选择第i个点选或者不选,此时取二者的最小值。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=3e5+10,INF=1e9;
ll a[N],dp[N][2];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    for (int i = 1; i <= n;i++)
    {
        cin >> a[i];
    }
    ll ans = 1e18;
    dp[1][1] = a[1],dp[1][0] = 1e18;
    for (int i = 2; i <= n;i++)
    {
        dp[i][0] = dp[i - 1][1];
        dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + a[i];
    }
    ans = min({ans,dp[n][0],dp[n][1]});
    memset(dp, 0, sizeof dp);
    dp[1][1] = 1e18, dp[1][0] = 0;
    for (int i = 2; i <= n;i++)
    {
        dp[i][0] = dp[i - 1][1];
        dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + a[i];
    }
    ans = min(ans, dp[n][1]);
    cout<<ans;
    return 0;
}
————————

AtCoder Beginner Contest 251

A – Six Characters

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=1e5+10,INF=1e9;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin>>s;
    int pos=0,cnt = 0;
    while(cnt<6)
    {
        cout << s[pos];
        cnt++;
        pos++;
        if(pos==s.length())
        {
            pos = 0;
        }
    }
    return 0;
}

B – At Most 3 (Judge ver.)

This thing tells me not to use map… If the query is O (logn), it will timeout… If you can open the array in the future, try to open the array…

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=3e6+10,INF=1e9;
bool vis[N];
int a[310];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,w;
    int cnt = 0;
    cin >> n >> w;
    for (int i = 1; i <= n;i++)
    {
        cin >> a[i];
        if(!vis[a[i]]&&a[i]<=w)
        {
            vis[a[i]] = 1;
            cnt++;
        }
    }
    for (int i = 1; i <= n;i++)
    {
        for (int j = i + 1; j <= n;j++)
        {
            if(i==j)
                continue;
            if(!vis[a[i]+a[j]]&&a[i]+a[j]<=w)
            {
                vis[a[i] + a[j]] = 1;
                cnt++;
            }
            for (int k = j + 1;k<=n;k++)
            {
                if(!vis[a[i]+a[j]+a[k]]&&a[i]+a[j]+a[k]<=w)
                {
                    vis[a[i] + a[j] + a[k]] = 1;
                    cnt++;
                }
            }
        }
    }
    cout << cnt;
    return 0;
}

C – Poem Online Judge

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=1e5+10,INF=1e9;
map<string, int> vis;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    int ans = -1;
    int pos = 0;
    for (int i = 1; i <= n;i++)
    {
        string s;
        cin >> s;
        int res;
        cin >> res;
        if(!vis[s])
        {
            vis[s] = 1;
            if(res>ans)
            {
                ans = res;
                pos = i;
            }
        }
    }
    cout << pos;
    return 0;
}

D – At Most 3 (Contestant ver.)

Thought of the idea of construction, but only limited to 1-3000. After reading the problem solution, I found that it only needs 1-100 and they multiply by 1001000. It’s ingenious

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=1e5+10,INF=1e9;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<300<<'\n';
    for (int i = 1; i <= 100;i++)
    {
        cout << i << ' ' << i * 100 << ' ' << i * 10000  << ' ';
    }
        return 0;
}

E – Tahakashi and Animals

It’s a bit like the ring beating and robbing problem of force buckle. For the first point, we choose to choose or not. For the next 2-N points, it’s assumed that the current point is the i-th point. If the i-1st point is not selected, we have to choose. If the i-1st point is selected, we can choose the i-th point to choose or not to choose, and the minimum value of the two is taken at this time.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=3e5+10,INF=1e9;
ll a[N],dp[N][2];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    for (int i = 1; i <= n;i++)
    {
        cin >> a[i];
    }
    ll ans = 1e18;
    dp[1][1] = a[1],dp[1][0] = 1e18;
    for (int i = 2; i <= n;i++)
    {
        dp[i][0] = dp[i - 1][1];
        dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + a[i];
    }
    ans = min({ans,dp[n][0],dp[n][1]});
    memset(dp, 0, sizeof dp);
    dp[1][1] = 1e18, dp[1][0] = 0;
    for (int i = 2; i <= n;i++)
    {
        dp[i][0] = dp[i - 1][1];
        dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + a[i];
    }
    ans = min(ans, dp[n][1]);
    cout<<ans;
    return 0;
}