头像

道谛




离线:12小时前


最近来访(185)
用户头像
AcWing2AK
用户头像
陈老师的粉丝
用户头像
SC_Ning
用户头像
Dovis_9
用户头像
notfound@f
用户头像
PrinceS
用户头像
_IO_
用户头像
RyanMoriarty
用户头像
白马金羁侠少年
用户头像
算法就要笑着学QvQ
用户头像
AC.god
用户头像
mystifying


道谛
12天前

本来想用dp的,但是想了一下有点麻烦,
再说了第一题应该不至于这么难,应该是有规律的,所以找了一下
这道题用的是单调性求解
我们知道N是一个确定的数字。
a+b=N;
a只要确定了那么b也就确定了
然后下面的工作就是发现a的范围。
1:我们不难发现只要N-b是小于等于0的数,那么a就可以从零开始,到min(a,c)结束
2:如果N-b是大于0的数,那么a的开始的地方就应该是(n-b)的位置,到min(a,c)结束
所以说直接就出来了。
复杂度应该是O(1)的
include [HTML_REMOVED]
include [HTML_REMOVED]
include [HTML_REMOVED]

using namespace std;
int a,b,c;
int main()
{
cin >> a>>b>>c;
int t=c-b;
if(t<=0)
{
cout << min(a,c)+1;
}

else
{
int mi=c-b;
int w=min(c,a);
cout << w-mi+1;
}

}



活动打卡代码 AcWing 1219. 移动距离

道谛
4个月前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=100000;
int n,m,t;

int chect(int x,int y)
{
    if(n==10000) return abs(y-x);
    int h1=x/n;
    int h2=y/n;
    int l1=0,l2=0;
    if(h1%2!=0)
    {
        if(n==2)
        {
            l1=(n-(x%n))-1;
        }
        else l1=(n-(x%n))+1;
    }
    else l1=x%n;

    if(h2%2!=0)
    {
        if(n==2)
        {
            l2=(n-(y%n))-1;
        }
        else l2=(n-(y%n))+1;
    }
    else l2=y%n;

    int res=abs(h1-h2)+abs(l1-l2);
    return res;

}
int main()
{

    cin >> n>>m>>t;
    cout << chect(m,t);
}


活动打卡代码 AcWing 787. 归并排序

道谛
4个月前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int a[100010];
int main()
{
    int n;
    cin >> n;
    for(int i=0;i<n;i++)
    {
        cin >> a[i];
    }
    sort(a,a+n);
    for(int i=0;i<n;i++)
    {
        cout << a[i]<<' ';
    }
}


活动打卡代码 AcWing 1204. 错误票据

道谛
4个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> q;
int a[100010];
int main()
{
    int n;
    cin >> n;
    int ma=-1e9,mi=1e9;
    while (n -- )
    {
        int x;
        while(cin>>x && x)
        {

            q.push_back(x);
            ma=max(ma,x);
            mi=min(mi,x);
        }
    }
    int len=q.size();
    for(int i=0;i<len;i++)
    {
        int x=q[i];
        a[x]++;
    }
    //cout << a[9];
    int left=0,right=0;
    for(int i=mi;i<=ma;i++)
    {
        if(a[i]==0) left=i;
        if(a[i]==2) right=i;
    }
    //if(left>right) swap(left,right);
    cout << left<<" "<<right<<endl;
}


活动打卡代码 AcWing 1245. 特别数的和

道谛
4个月前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N];
int n;
int main()
{
    cin >> n;
    int res=0;
    for(int i=1;i<=n;i++)
    {
        int x=i;
        while(x>0)
        {
            int g=x%10;
            if(g==2 || g==0 || g==1 || g==9) 
            {
                res+=i;
                break;
            }
            x/=10;
        }
    }
    cout << res;
}


活动打卡代码 AcWing 1236. 递增三元组

道谛
4个月前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=100010;
typedef long long LL;
int a[N],b[N],c[N],ant1[N],ant2[N];
LL sum1[N],sum2[N];

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
    }
    for(int i=1;i<=n;i++)
    {
        cin >> b[i];
    }
    for(int i=1;i<=n;i++)
    {
        cin >> c[i];
    }
    for(int i=1;i<=n;i++)
    {
        ant1[a[i]]++;
        ant2[c[i]]++;
    }

    for(int i=0;i<=100010;i++)
    {
        sum1[i]=sum1[i-1]+ant1[i];
        sum2[i]=sum2[i-1]+ant2[i];
    }
    //cout << sum2[0];
    LL res=0;
    //cout << n;
    for(int i=1;i<=n;i++)
    {

        LL r1=sum1[b[i]-1];

        LL r2=n-sum2[b[i]];
        //cout << r2<<' '<<endl;
        LL r3=r1*r2;
        res+=r3;
    }

    cout << res;

}


活动打卡代码 AcWing 1210. 连号区间数

道谛
4个月前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=100010,INT=1e9;
int a[N];
int main()
{
    int n;
    cin >> n;
    int res=0;
    for(int i=0;i<n;i++)
    {
        cin >> a[i];
    }
    for(int i=0;i<n;i++)
    {
        int maxv=-INT,minv=INT;
        for(int j=i;j<n;j++)
        {
            maxv=max(maxv,a[j]);
            minv=min(minv,a[j]);
            if(maxv-minv==j-i) res++;
        }
    }
    cout << res;
}


活动打卡代码 AcWing 1227. 分巧克力

道谛
4个月前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n,m;
int h[N],w[N];
int chack(int mid)
{
    int res=0;
    for(int i=0;i<n;i++)
    {
        res+=((h[i]/mid)*(w[i]/mid));
    }
    return res;
}
int main()
{
    cin >> n>>m;
    for(int i=0;i<n;i++)
    {
        cin >> h[i]>>w[i];
    }

    int l=0,r=100000;
    while(l<r)
    {
        int mid=(l+r+1)/2;
        if(chack(mid)>=m) l=mid;
        else r=mid-1;
    }
    cout << l;

}


活动打卡代码 AcWing 4071. 国际象棋

道谛
5个月前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=10;
int g[N][N];
bool st[N][N];
char a[2],b[2];
int dx[8]={-1,-2,-2,-1,1,2,2,1},dy[8]={-2,-1,1,2,2,1,-1,-2};
int main()
{
    cin >> a>>b;
    memset(st, 0, sizeof st);
    int x1=a[0]-'a',y1=a[1]-'1';
    int x2=b[0]-'a',y2=b[1]-'1';
    st[x1][y1]=true,st[x2][y2]=true;
    for(int i=0;i<8;i++)
    {
        int x=x2+dx[i],y=y2+dy[i];
        if(x<0 && x>=8 && y<0 && y>=8) continue;
        if(st[x][y]==true) continue;
        st[x][y]=true;

    }

     for(int i=0;i<8;i++)
    {
        int x=x1+dx[i],y=y1+dy[i];
        if(x<0 && x>=8 && y<0 && y>=8) continue;
        if(st[x][y]==true) continue;
        st[x][y]=true;

    }

    for(int i=0;i<8;i++)
    {
        st[i][y1]=true;
        st[x1][i]=true;
    }



    int res=0;
    for(int i=0;i<8;i++)
    {
        for(int j=0;j<8;j++)
        {
            if(st[i][j]==false) res++;
        }

    }
    cout << res;
}


活动打卡代码 AcWing 4072. 习题册

道谛
5个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int N=200010;
typedef pair <int ,int >PII;
priority_queue<PII,vector<PII>,greater<PII>> h[3];
int p[N];
bool st[N];
int main()
{
    int n;
    cin >> n;
    for(int i=0;i<n;i++)
    {
        cin >> p[i];
    }

    for(int j=0;j<2;j++)
    {
        for(int i=0;i<n;i++)
        {
            int x;
            cin >> x;
            x--;
            h[x].push({p[i],i});
        }
    }

    int m;
    cin >> m;
    while (m -- )
    {
        int x;
        cin >> x;
        x--;
        while(h[x].size() && st[h[x].top().second]) h[x].pop();
        if(h[x].size()==0) cout << -1<<' ';
        else 
        {
            auto t=h[x].top();
            cout << t.first<<' ';
            h[x].pop();
            st[t.second]=true;
        }
    }

}