版权原因,题目不公开。


DEC

把$A-B=C$的条件转化为$A=B+C$,每个数映射到$map$里面,完事再过一遍看加上$C$是否出现。注意映射到$int$并记录个数,这样才符合题意(不同位置算不同组)。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[500010];
map<ll,int> m;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*f; 
}
int main()
{
    freopen("dec.in","r",stdin);
    freopen("dec.out","w",stdout);
    ll n,c;
    scanf("%lld%lld",&n,&c);
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        m[a[i]]++;
    }
    ll ans=0;
    for(int i=1;i<=n;i++)
        ans+=m[a[i]+c];
    printf("%lld\n",ans);
    return 0;
}

CARGO

水。二进制扫一遍进位就完了。

#include<bits/stdc++.h>
using namespace std;
int v[2000010];
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*f; 
}
int main()
{
    freopen("cargo.in","r",stdin);
    freopen("cargo.out","w",stdout);
    int n,ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int a=read();
        v[a]++;
    }
    for(int i=0;i<=1000005;i++)
    {
        v[i+1]+=(v[i]/2);
        v[i]%=2;
        if(v[i])ans++;
    }
    printf("%d\n",ans);
    return 0;
}

FISH

考试时没看懂题...

看懂了其实挺简单,维护一个栈来模拟。0就放进栈,1就把里面比它小的都吃掉。如果吃空了累计起来,这条鱼会存活。

最后的答案就是栈的size加上吃空栈的鱼。

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*f; 
}
stack<int> s;
int main()
{
    int n=read(),ans=0;
    for(int i=1;i<=n;i++)
    {
        int a=read(),b=read();
        if(b)s.push(a);
        else
        {
            while(!s.empty()&&s.top()<a)s.pop();
            if(s.empty())ans++;
        }
    }
    printf("%d\n",ans+s.size());
    return 0;
}

PROGRAM

稍微找找规律。

发现$\lfloor \frac{a+b}{a*b} \rfloor$的值在$a>2,b>2$时恒为0。

并且当$a,b$有一个值为1的时候,就会对答案贡献1。

如果$a,b$两个都是1,就会贡献2。

特殊地,两个2也会对答案贡献1。

那么答案就是1的个数乘上$(n-1)$再加上$c*(c-1)/2$(c为2出现的次数),因为每两个2都会对答案贡献1。

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*f; 
}
signed main()
{
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    int n=read(),ans=0;
    int cnt_2=0;
    for(int i=1;i<=n;i++)
    {
        int q=read();
        if(q==2)cnt_2++;
        if(q==1)ans+=(n-1);
    }
    printf("%lld\n",ans+(cnt_2*(cnt_2-1)/2));
    return 0;
}

DISH

发现每一层有效的宽度为$min\{a[i-1],q\}$。于是就得到了一个单调递减的序列$a[]$。

二分找一下每个圆盘能放下的位置。然后模拟就完了。

#include<bits/stdc++.h>
using namespace std;
const int INF=1e9;
int a[100010]={INF};
int n;
int ef(int x)
{
    int l=1,r=n;
    int m=l+r>>1;
    while(l!=r)
    {
        if(a[m]>=x)l=m+1;
        else r=m;
        m=l+r>>1;
    }
    return m;
}
int main()
{
    int m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int q;
        scanf("%d",&q);
        a[i]=min(a[i-1],q);
    }
    int top=n,cnt=0;//从上至下分为1-n 
    while(m--)
    {
        int q;
        scanf("%d",&q);
        top=min(top-1,ef(q)-1);
        if(top<1)
            break;
        cnt++;
    }
    printf("%d\n",cnt==n-1?n:cnt);
    return 0;
}

PERM

最后一题晚点补qaq

最后修改:2020 年 08 月 29 日 05 : 18 PM