头像

Logos




离线:7小时前


分享 11.21 普及

Logos
8天前

T1

题目描述

地上有2N个石头,排成了一条线,相邻的石头距离为1,石头之间有着不同的大小,有N种大小不同 的石头,即相同大小的石头有2个,现将石头按照从小到大的顺序依次编号为1到N,有2个石头共享 相同的编号,现在小武和小林要同时从最左边的石头出发,按照石头大小依次捡起编号为1到N的石 头,并且相同编号的石头同一个人只能捡起来一次,现在他们想把地上的石头都捡完,求两个人的行 走的最短距离和为多少?

模拟!

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int x,y;
}a[1000010];

bool cmp(node l,node r)
{
    if(l.x==r.x) return l.y<r.y;
    return l.x<r.x;
}

int main()
{   
    freopen("stone.in","r",stdin);
    freopen("stone.out","w",stdout);
    int n;
    cin>>n;

    for(int i=1;i<=2*n;i++)
    {
        cin>>a[i].x;
        a[i].y=i;
    }

    stable_sort(a+1,a+2*n+1,cmp);

    int ans=a[1].y-1+a[2].y-1;

    for(int i=3;i<=2*n;i++)
    {
        ans+=abs(a[i].y-a[i-2].y);
    }

    cout<<ans<<endl;

    return 0;
}

T2

题目描述

小武的实验室里有一种魔法药水,这个药水有个很奇怪的性质,它只能在盛放的体积为2的幂次时保 持稳定,例如1,2,4,8。所以小武在实验室里放置了很多容积为2的幂次的瓶子,其中N瓶放有魔法药 水,第i瓶魔法药水的体积为2的L[i]次方。这天小武想要收拾一下实验室,小武想知道最少用多少个瓶 子能把实验室的药水装完。
假设小武有任意2的幂次容积的瓶子,并且每种瓶子的数量足够使用。

用桶记录当前幂的值 每两个可以组成一个更大的

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,a[10000005],maxi;
ll ans;
int main()
{
    scanf("%d",&n);
    for(register int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        a[x]++;
        maxi=max(maxi,x);
    }
    for(register int i=0;i<=maxi;i++)
    {
        if(a[i]>1)
        {
            a[i+1]+=a[i]/2;  
            a[i]%=2;
            if(i==maxi) maxi++;
        }
    }
    for(register int i=0;i<=maxi;i++)
        if(a[i]) ans++;
    printf ("%lld",ans);
    return 0;
}

T3

题目描述

小武有n个数字,这天小武想将数字理的顺一点,小武要把数字分组,每组的个数都是m,并且这m个 数字连续,小武想知道可以做到吗?

#include <bits/stdc++.h>
using namespace std;
int a[1000010],t,m,n,k;
bool f[12];
int main() 
{
    freopen("group.in","r",stdin);
    freopen("group.out","w",stdout);


    memset(f,0,sizeof(f));
    int i;
    cin>>t;
    for(i=0; i<t; i++) 
    {
        cin>>n>>m;
        memset(a, 0, sizeof(a));
        for (int j=0; j<n; j++) 
        {
            cin>>k;
            a[k]++; 
        }
        f[i] = true;
        while (n>0 && f[i]) 
        { 
            for (int j=0; j<1000; j++) 
            { 
                if (a[j]>0) 
                { 
                    for (k=j; k<j+m; k++) 
                    {
                        if (a[k]<=0) 
                        { 
                            f[i] = false; 
                            break;
                        }
                        a[k]--; 
                        n--; 
                    }
                    break; 
                }
            }
        }
    }
    char ans[][12] = {"false", "true"};
    for(i=0;i<t;i++) 
    { 
        cout<<ans[f[i]]<<endl;
    }

    return 0;
}

T4

题目描述

小武有2个方程,x|y=A,x+y=B,其中|为二进制或符号,x和y是未知数,A和B已知,小武想知道这个 方程是否有非负整数解。

解题思路

① B必大于A,因为x和y同一位上都是1的话,A当前位是1,而B则进位了
于是可以得出B - A就是x和y同为1位的和
比如:A = 5(101), B = 6(110), B - A = 1(001), 那么x和y的第0位必为1,其它位没有条件限制
A=2(010), B=5(101), B - A = 3(011),
那么x和y第0位和第1位必为1,但是A的第0位并不是1,所以A,B不成立
② A | (B - A)判断必为1位是不是1,如果求出的依旧是A,那么必为1位是1

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    freopen("solution.in","r",stdin);
    freopen("solution.out","w",stdout);

    int t;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        ll a,b;
        cin>>a>>b;

        ll ans=a|(b-a);

        if(a==ans && b>=a)
            cout<<"Possible"<<endl;
        else
            cout<<"Impossible"<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 9. 分组背包问题

Logos
18天前
#include <bits/stdc++.h>
using namespace std;
const int N=110;
int f[N],v[N][N],w[N][N],s[N];
int n,m;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];

        for(int j=1;j<=s[i];j++)
        {
            cin>>v[i][j]>>w[i][j];

        }
    }

    for(int i=1;i<=n;i++)
        for(int j=m;j>=0;j--)
            for(int k=s[i];k>=1;k--)
            {
                if(j>=v[i][k])
                    f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
            }

    cout<<f[m];
}


活动打卡代码 AcWing 154. 滑动窗口

Logos
18天前
#include <bits/stdc++.h>
using namespace std;
int a[1000010],q[1000010],hh,tt=-1;
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];

        if(i-k+1>q[hh]) hh++;

        while(hh<=tt && a[i]<=a[q[tt]]) tt--;

        q[++tt]=i;

        if(i+1>=k) cout<<a[q[hh]]<<' ';
    }
    cout<<endl;
    hh=0;
    tt=-1;
    for(int i=0;i<n;i++)
    {
        if(i-k+1>q[hh]) hh++;

        while(hh<=tt && a[i]>=a[q[tt]]) tt--;

        q[++tt]=i;

        if(i+1>=k) cout<<a[q[hh]]<<' ';
    }
    return 0;
}



Logos
20天前

T1

#include<bits/stdc++.h>
using namespace std;
int cnt=0,a[100005][3];
int q,w;
int y[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int qy[13]={0,31,29,31,30,31,30,31,31,30,31,30,31};
int sy[13]={0,31,28,31,30,31,30,31,31,30,21,30,31};
void month(int now,int rem,int run)
{
    if(run==1)
    {   
        if(rem>=qy[now]) 
            month(now+1,rem-qy[now],run);
        else if(rem<qy[now]) 
            a[cnt][1]=now,a[cnt][2]=rem+1;
    }

    if(run==0)
    {
        if(rem>=y[now]) 
            month(now+1,rem-y[now],run);
        else if(rem<y[now])  
            a[cnt][1]=now,a[cnt][2]=rem+1;
    }

    if(run==2)
    {
        if(rem>=sy[now]) 
            month(now+1,rem-sy[now],run);
        else if(rem<sy[now]&&now==10) 
            a[cnt][1]=now,a[cnt][2]=(rem<=3)?rem+1:11+rem;
        else 
            a[cnt][1]=now,a[cnt][2]=rem+1;
    }
}
void ask(int now,int rem)
{
    int y;
    int run=0;
    if(now>1582) 
    {
        if( (now%400==0) || ((now%4==0) && (now%100!=0)) ) 
            y=366,run=1;
        else 
            y=365,run=0;
    }

    if(0<now<1582) 
    {
        if(now%4==0) 
            y=366,run=1;
        else 
            y=365,run=0;
    }

    if(now<0) 
    {
        if((now+1)%4==0) 
            y=366,run=1;
        else 
            y=365,run=0;
    }

    if(now==1582) 
    {
        y=355,run=2;
    }

    if(rem>=y) 
    {
        if(now==-1) 
            ask(1,rem-y);
        else 
            ask(now+1,rem-y);
    }

    if(rem<y)
    {
        a[++cnt][0]=now;
        month(1,rem,run);
    }
    return;
}

int main()
{
    //freopen("julian.in","r",stdin);
    //freopen("julian.out","w",stdout);
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        cin>>w;
        ask(-4713,w);
        if(a[cnt][0]>0) 
            cout<<a[cnt][2]<<" "<<a[cnt][1]<<" "<<a[cnt][0]<<endl;
        else 
            cout<<a[cnt][2]<<" "<<a[cnt][1]<<" "<<-a[cnt][0]<<" BC"<<endl;
    }

    return 0;
}

nowcoder自测:40

T2

#include <bits/stdc++.h>
using namespace std;
int n,m,c,k,sum;
int dig[70], ned[70]; 
int main()
{
    //freopen("zoo.in", "r", stdin);    
    //freopen("zoo.out", "w", stdout);
    cin>>n>>m>>c>>k;
    if (n <= 30)
    {
        long long num;
        cin >> num;
        int cnt = 0;
        while (num)
        {
            if (num & 1)
                dig[cnt] = 1;
            cnt++;
            num >>= 1;
        }
    }

    else 
    {
        for (int i = 1; i <= n; i++)
        {
            long long num;
            cin>>num;
            int cnt = 0;
            while (num)
           {
                if (num & 1)
                    dig[cnt] = 1;
                cnt++;
                num >>= 1;
            }
        }
    }

    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin>>a>>b;
        ned[a] = 1;
    }

    for (int i = 0; i < k; i++)
        if (dig[i] || (!ned[i]))
            sum++;

    long long ans = 1;

    while (sum--)
        ans <<= 1;

    cout <<ans-n<<endl;;

    return 0;
}

nowcoder自测:20



活动打卡代码 AcWing 867. 分解质因数

Logos
22天前
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a;
        cin>>a;

        for(int i=2;i<=a/i;i++)
        {
            if(a%i==0)
            {
                int s=0;
                while(a%i==0)
                {
                    a/=i;
                    s++;
                }
                cout<<i<<" "<<s<<endl;  
            }

        }

        if(a>1) cout<<a<<' '<<1<<endl;
        cout<<endl;
    }
    return 0;    
}


活动打卡代码 AcWing 5. 多重背包问题 II

Logos
22天前
#include <bits/stdc++.h>
using namespace std;
int f[2010],n,m;
struct fun
{
    int w,v;
};

int main()
{
    cin>>n>>m;
    vector<fun> ark;
    fun tmp;

    for(int i=1;i<=n;i++)
    {
        int v,w,s;

        cin>>v>>w>>s;

        for(int j=1;j<=s;j*=2)
        {
            s-=j;
            ark.push_back({j*w,j*v});
        }

        if(s>0) ark.push_back({s*w,s*v});
    }

    for(auto t:ark)
        for(int j=m;j>=t.v;j--)
            f[j]=max(f[j],f[j-t.v]+t.w);

    cout<<f[m]<<endl;

    return 0;
}



Logos
22天前
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int MAX=150000+5;
int h[MAX], e[MAX], ne[MAX], idx;
int w[MAX]; 
int dist[MAX];
bool st[MAX];

int n, m;

void add(int x, int y, int c)
{
    w[idx] = c;
    e[idx] = y; 
    ne[idx] = h[x]; 
    h[x] = idx++;
}

int dij()
{
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push(make_pair(0,1)); 
    while(heap.size())
    {
        PII k = heap.top(); 
        heap.pop();
        int ver = k.second, distance = dist[ver];

        if(st[ver]) continue;
        st[ver] = true;

        for(int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i]; 
            if(dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({ dist[j], j });
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}

int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &m);

    while (m--)
    {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        add(x, y, c);
    }

    cout << dij() << endl;

    return 0;
}




Logos
22天前
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int MAX=150000+5;
int h[MAX], e[MAX], ne[MAX], idx;
int w[MAX]; 
int dist[MAX];
bool st[MAX];

int n, m;

void add(int x, int y, int c)
{
    w[idx] = c;
    e[idx] = y; 
    ne[idx] = h[x]; 
    h[x] = idx++;
}

int dij()
{
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push(make_pair(0,1)); 
    while(heap.size())
    {
        PII k = heap.top(); 
        heap.pop();
        int ver = k.second, distance = dist[ver];

        if(st[ver]) continue;
        st[ver] = true;

        for(int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i]; 
            if(dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({ dist[j], j });
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}

int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &m);

    while (m--)
    {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        add(x, y, c);
    }

    cout << dij() << endl;

    return 0;
}




Logos
22天前
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int MAX=150000+5;
int h[MAX], e[MAX], ne[MAX], idx;
int w[MAX]; 
int dist[MAX];
bool st[MAX];

int n, m;

void add(int x, int y, int c)
{
    w[idx] = c;
    e[idx] = y; 
    ne[idx] = h[x]; 
    h[x] = idx++;
}

int dij()
{
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push(make_pair(0,1)); 
    while(heap.size())
    {
        PII k = heap.top(); 
        heap.pop();
        int ver = k.second, distance = dist[ver];

        if(st[ver]) continue;
        st[ver] = true;

        for(int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i]; 
            if(dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({ dist[j], j });
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}

int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &m);

    while (m--)
    {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        add(x, y, c);
    }

    cout << dij() << endl;

    return 0;
}



活动打卡代码 AcWing 830. 单调栈

Logos
23天前
#include <bits/stdc++.h>
using namespace std;
int s[100010],tt,n;
int main()
{
    cin>>n;
    while(n--)
    {
        int x;
        cin>>x;

        while(tt && s[tt]>=x) tt--;

        if(tt) cout<<s[tt]<<' ';
        else cout<<"-1"<<' ';

        s[++tt]=x;
    }

    return 0;
}