abc248_a

题目翻译

有一个字符串 $s$，找出 $0$ 到 $9$ 中没出现的数。

题目思路

直接开数组存出现次数。

AC 代码

int a[10];
void solve()
{
    string s;
    cin>>s;
    for(int i=0;i<9;i++)
    {
        a[s[i]-'0']++;
    }
    for(int i=0;i<=9;i++)
    {
        if(a[i]==0)
        {
            cout<<i;
            return;
        }
    }
}

abc248_b

题目翻译

$a\times k^{x-1}\geq b$，问 $x$ 最小是几。

题目思路

模拟，while 循环。

AC 代码

void solve()
{
    long long a,b,k,ans=0;
    cin>>a>>b>>k;
    while(a<b)
    {
        ans++;
        a*=k;
    }
    cout<<ans<<endl;
}

abc248_c

题目翻译

从 $m$ 里选 $n$ 个数，保证 $\sum\limits_{i=1}^na_i\leq k$，问方案数。

题目思路

考虑 $f_{i,j}$ 记录 $i$ 个数和为 $j$ 的方案数。

AC 代码

const int mod=998244353;
int f[55][2505];
void solve()
{
    int n,m,k;
    cin>>n>>m>>k;
    f[1][1]=1;
    for(int i=1;i<=m;i++)
    {
        f[1][i]=1;
    }
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            for(int kk=0;kk<k;kk++)
            {
                if(kk+j<=k)
                {
                    f[i][kk+j]+=f[i-1][kk];
                }
                else
                {
                    break;
                }
                f[i][kk+j]%=mod;
            }
        }
    }
    int ans=0;
    for(int i=0;i<=k;i++)
    {
        ans+=f[n][i];
        ans%=mod;
    }
    cout<<ans<<endl;
}

abc248_d

题目翻译

$q$ 个询问，问 $[l,r]$ 中，有多少数 $=k$。

题目思路

lower_bound 和 upper_bound 找一下。

值和位置一起排序，两次二分，找到符合要求的区间。

AC 代码

vector<int>v[200005];
int a[200005];
void solve()
{
    int n,q;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        v[a[i]].push_back(i);
    }
    cin>>q;
    while(q--)
    {
        int l,r,k;
        cin>>l>>r>>k;
        long long ans=upper_bound(v[k].begin(),v[k].end(),r)-lower_bound(v[k].begin(),v[k].end(),l);
        cout<<ans<<endl;
    }
}

abc248_e

题目翻译

输入 $n$ 个点的坐标和一个整数 $k$，问有多少条直线通过其中恰好 $k$ 个点，如果无穷多个输出 Infinity。

题目思路

$n$ 个点一共可以生成至多 $\frac{n*(n-1)}{2}$ 个直线，每个直线判断一下。

AC 代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<climits>
typedef long long ll;
using namespace std;
const int mod=998244353;
int x[305],y[305];
int check(int i,int j,int k)
{
    return (x[j]-x[i])*(y[k]-y[i])-(x[k]-x[i])*(y[j]-y[i])==0;
}
void solve()
{
    int n,k,ans=0;
    cin>>n>>k;
    if(k==1)
    {
        puts("Infinity");
        return;
    }
    for(int i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            int sum=0;
            for(int kk=1;kk<=n;kk++)
            {
                if(check(i,j,kk))
                {
                    if(kk!=i&&kk<j)
                    {
                        sum=0;
                        break;
                    }
                    sum++;
                }
            }
            if(sum>=k)
            {
                ans++;
            }
        }
    }
    cout<<ans<<endl;
}
int main()
{
//  freopen("example.in","r",stdin);
//  freopen("example.out","w",stdout);
//  std::ios::sync_with_stdio(false);
//  cin.tie(nullptr);cout.tie(nullptr);
    int t=1;
    while(t--)
    {
        solve();
    }
    return 0;
}