AtCoder Beginner Contest 249

A - Jogging

没读好，题面有点问题20分钟后才了改题面。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
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);
    int a, b, c, d, e, f,x,res1,res2;
    cin >> a >> b >> c >> d >> e >> f>> x;
    res1= (a*b) * (x / (a + c));
    res2= (d*e) * (x / (d + f));
    res1 += min(x % (a + c) * b, a * b);
    res2 += min(x % (d + f) * e, d * e);
    if(res1==res2)
        cout << "Draw";
    else if(res1>res2)
        cout << "Takahashi";
    else
        cout << "Aoki";

    return 0;
}

B - Perfect String

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=1e5+10,INF=1e9;
map<char, int> vis;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin >> s;
    int f = 0, f1 = 0, f2 = 0;
    for (int i = 0; i < s.length();i++)
    {
        if(vis[s[i]])
        {
            f2 = 1;
        }
        vis[s[i]] = 1;
        if(islower(s[i]))
        {
            f = 1;
        }
        if(isupper(s[i]))
        {
            f1 = 1;
        }
    }
    if(f1==1&&f==1&&f2==0)
    {
        cout << "Yes\n";
    }
    else
        cout << "No\n";

        return 0;
}

C - Just K

比赛时没读懂题面，看了别人的翻译才知道，给你n个字符串和一个k，你可以任意选择字符串，求在选择的这些字符串中恰好出现k次的字母有多少个。直接dfs枚举字符串选还是不选，最后更新最大值。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=1e5+10,INF=1e9;
int a[30],n,k,ans;
string s[20];
void dfs(int now)
{
    if(now==n+1)
    {
        int res = 0;
        for (int i = 0; i < 26;i++)
        {
            if(a[i]==k)
            {
                res++;
            }
        }
        ans = max(ans, res);
        return;
    }
    for (int i = 0; i < s[now].length();i++)
    {
        a[s[now][i] - 'a']++;
    }
    dfs(now + 1);
    for (int i = 0; i < s[now].length();i++)
    {
        a[s[now][i] - 'a']--;
    }

    dfs(now + 1);

    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n;i++)
    {
        cin >> s[i];
    }
    dfs(1);
    cout << ans;
    return 0;
}

D - Index Trio

直接暴力枚举是n^2肯定会超时，考虑优化暴力的代码，枚举（i,j，k）里后两位，能由排列组合可以知道组合的方案数就是这三个数有多少个依次相乘。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=2e5+10,INF=1e9;
int a[N];
map<int, int> mp;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, mmax = 0;
    cin>>n;
    for (int i = 1; i <= n;i++)
    {
        cin >> a[i];
        mp[a[i]]++;
        mmax = max(mmax, a[i]);
    }
    ll ans = 0;
    for (int i = 1; i <=200005;i++)
    {
        for (int j = 1; j <=200005;j++)
        {
            if(1ll*i*j>mmax)
            {
                break;
            }
            if(mp[i*j])
            {
                ans+=1ll*mp[i*j]*mp[i]*mp[j];
            }
        }
    }
    cout << ans;
    return 0;
}

F - Ignore Operations

有两种操作，第一是把x替换成y，第二是x+y。可以发现如果第i次是替换操作那么前面1-i-1的操作都是无效的，因此我们可以从后往前枚举每一个替换操作，把它当成是最后一次替换操作，假设第i次是选择的最后一次替换操作，那么结果就为i-n之间的操作的和，需要注意如果i-n有替换操作k需要--，因为i是最后一次操作所以需要跳过操作，如果y>=0则把2的操作的和加上，否则丢进优先队列，每次判断如果队列大小k的话就必须要加上了，初始化op[0]=1,即一次都不选择替换操作

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=2e5+10,INF=1e9;
int a[N], op[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n;i++)
    {
        cin >> op[i] >> a[i];
    }
    ll ans = -1e18,sum=0;
    op[0] = 1;
    priority_queue<int> que;
    for (int i = n; i >= 0;i--)
    {
        if(op[i]==1)
        {
            ans = max(ans, a[i] + sum);
            k--;
            if(k<0)
                break;
        }
        else
        {
            if(a[i]>=0)
            {
                sum += a[i];
            }
            else
                que.push(a[i]);
        }
        while(que.size()>k)
            sum += que.top(),que.pop();
    }
    cout << ans;
    return 0;
}