第一题

打卡题

#include<bits/stdc++.h>
using namespace std;
int n,a[105],ans;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        ans+=a[i];
    }
    printf("%d",ans);
    return 0;
}

第二题

首先根据题目，我们可以看出：如果能造 $mid$ 台机器，则一定能造少于 $mid$ 台机器

考虑二分，每次统计需要多少个未加工原料，如果需要的多，就减少机器制造的数量，否则就多造几台机器

注意最多能造 $2000000000$ 台机器（样例1），最少可以一台机器不造（样例2）

但直接统计是会爆long long的，因此一旦需要的原料数量大于 $k$ 我们就立马停止循环。

记得开long long

#include<bits/stdc++.h>
using namespace std;
int n,a[100005],b[100005];
long long k,l=0,r=2000000000,res;
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
    while(l<=r)
    {
        long long sum=0,mid=l+r>>1;
        for(int i=1;i<=n;i++)
        {
            if(b[i]<mid*a[i]) sum+=mid*a[i]-b[i];
            if(sum>k) break;
        }  
        if(sum>k) r=mid-1;
        else res=mid,l=mid+1;
        //printf("%lld %lld %lld %lld\n",l,r,mid,sum); 
    }
    printf("%lld",res);
    return 0;
}

第三题

拓扑排序的题

首先根据字符串的大小顺序排出字符的大小顺序，然后让小的字符向大的字符连边

根据拓扑排序的性质，比它小的字符的拓扑序一定在它前面

如果有环的话就是类似 $a>b b>c c>a$ 的大小顺序，那这样肯定是不合法的，输出Impossible

但是还有一种情况需要注意：

2
sight
sigh

这样是要直接输出Impossible的，因为不可能有解

我用的是链式前向星，但这题规模很小，用领接矩阵也是可以的

#include<bits/stdc++.h>
using namespace std;
int n,len[105],in[35],cou[35],g;
string a[105];
struct bian
{
    int v,nxt;
}edge[105];
int head[35],idx=1;
void add_bian(int u,int v)
{
    edge[idx].v=v;
    edge[idx].nxt=head[u];
    head[u]=idx++;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        len[i]=a[i].size();
    }
    for(int i=1;i<n;i++)
    {
        bool duan=false;
        for(int j=0;j<min(len[i],len[i+1]);j++)
        {
            if(a[i][j]==a[i+1][j]) continue;
            add_bian(int(a[i][j]-'a'+1),int(a[i+1][j]-'a'+1));
            in[int(a[i+1][j]-'a'+1)]++;
            duan=true;
           // cout<<a[i][j]<<'<'<<a[i+1][j]<<'\n';
            break;
        }
        if(!duan && len[i]>len[i+1]) 
        {
            printf("Impossible");
            return 0;
        }
    }
    queue<int> q;
    for(int i=1;i<=26;i++)
        if(in[i]==0) q.push(i);
    while(!q.empty())
    {
        int t=q.front();
        cou[++g]=t;
        q.pop();
        for(int i=head[t];i;i=edge[i].nxt)
        {
            int v=edge[i].v;
            in[v]--;
            if(in[v]==0) q.push(v);
        }
    }
    if(g!=26) {printf("Impossible");return 0;}
    for(int i=1;i<=g;i++)
        cout<<char(cou[i]+'a'-1);
    return 0;
}

求点赞(凑个150行)