头像

方攵飛夢想




在线 


最近来访(102)
用户头像
L-China
用户头像
yxc的小迷妹1
用户头像
张_
用户头像
hnsqls
用户头像
摸鱼ing
用户头像
终极殺人王
用户头像
小马哒哒
用户头像
华尔街之狼
用户头像
2457226050
用户头像
她说万幸得以相识
用户头像
鹤云116
用户头像
-楠朋友
用户头像
不要卷我
用户头像
-浪漫主义狗-
用户头像
游四方
用户头像
Andy2035
用户头像
HF_7
用户头像
acwing_0298
用户头像
一枝黎花压海棠
用户头像
洛白さん


https://www.acwing.com/problem/content/2774/

#include<bits/stdc++.h>
using namespace std;

#define int unsigned long long
int n, m, c, k;
int ans;
int as[64][2];
int cnt;
int cntt;

int pow(int a1, int b1)
{
    int cntt1 = 1;
    for(int i = 1; i <= b1; i++)
    {
        cntt1 *= a1;
    }
    return cntt1;
}

signed main()
{
    cin >> n >> m >> c >> k;

    if(n == 0 && m == 0 && k == 64)
    {
        cout << "18446744073709551616";
        return 0;
    }

    for(int i = 0; i < n; i++)
    {
        int x;
        scanf("%llu", &x);
        ans = (ans | x);
    }
//  cout << ans << endl;
    int k1 = 0;
    while(ans)
    {
        if(ans & 1) as[k1][0] = 1;
        ans = (ans >> 1);
        k1++;
    }

    for(int i = 0; i <= 63; i++) as[i][1] = 1;
    for(int i = 0; i < m; i++)
    {
        int x, y;
        scanf("%llu%llu", &x, &y);
        if(as[x][0] != 1) as[x][1] = 0;
    }

    for(int i = 0; i < k; i++)
    {
        if(as[i][1] == 0) 
        {
            cntt ++;
        }
    }

    //cnt = (pow(2, cntt) - 1 ) * pow(2, k - cntt);

    int ab1;
    ab1 = (1ull << (k));
    ab1 -= n;
    //ab1 += (1ull << (k - 1));
    ab1 -= ((1ull << cntt) - 1) * (1ull << (k - cntt));

    cout << ab1 << endl;
}


分享 1109

https://www.acwing.com/problem/content/1111/

#include<bits/stdc++.h>
using namespace std;

#define int long long
int n, m;
const int N = 1010;
int a[N];
int s[60][2];

int get_min(int i)
{
    int ans = 0;
    for(int k = i; k >= 0; k--)
    {
        ans += min(s[k][0], s[k][1]);
    }

    return ans;
}

signed main()
{
    int T;
    cin >> T;
    for(int C = 1; C <= T; C++)
    {
        cin >> n >> m;
        for(int i = 0; i < n; i++) cin >> a[i];

        memset(s, 0, sizeof(s));
        for(int i = 0; i < 50; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(a[j] >> i & 1)
                {
                    s[i][0] += 1ll << i;
                }
                else
                {
                    s[i][1] += 1ll << i;
                }
            }
        }
        int ans = 0, sum = 0;
        if(get_min(49) > m) ans = -1;
        else
        {
            for(int i = 49; i >= 0; i--)
            {
                if(sum + get_min(i - 1) + s[i][1] <= m)
                {
                    ans += 1ll << i;
                    sum += s[i][1];
                }
                else
                {
                    sum += s[i][0];
                }
            }
        }
        printf("Case #%lld: %lld\n", C, ans);
    }

    return 0;
}


活动打卡代码 AcWing 116. 飞行员兄弟

#include<bits/stdc++.h>
using namespace std;

int a[4][4];
int b[4][4];
const int N = 65536;
vector<pair<int,int>> daan;

void cyl(int x, int y)
{
    a[x][0] = (a[x][0] + 1) % 2;
    a[x][1] = (a[x][1] + 1) % 2;
    a[x][2] = (a[x][2] + 1) % 2;
    a[x][3] = (a[x][3] + 1) % 2;
    a[0][y] = (a[0][y] + 1) % 2;
    a[1][y] = (a[1][y] + 1) % 2;
    a[2][y] = (a[2][y] + 1) % 2;
    a[3][y] = (a[3][y] + 1) % 2;
    a[x][y] = (a[x][y] + 1) % 2;
}

int cnt;
int sum;

signed main()
{
    for(int i = 0; i < 4; i++)
    {
        for(int j = 0; j < 4; j++)
        {
            char c;
            cin >> c;
            if(c == '-') a[i][j] = 0;
            else a[i][j] = 1;
            b[i][j] = a[i][j];
        }
    }
    for(int i = 0; i < 65536; i++)
    {
        int m = 0;
        int m1 = 0;
        while(m <= 15)
        {
            if((i >> m) & 1)
            {
                int x = m / 4;
                int y = m % 4;
                cyl(x, y);
                m1++;
            }
            m++;
        }
        bool flag = 1;
        for(int i1 = 0; i1 < 4; i1++)
        {
            for(int j1 = 0; j1 < 4; j1++)
            {
                if(a[i1][j1] == 1) flag = 0;
            }
        }
        if(flag != 0) 
        {
            daan.push_back({m1, i});
        }
        for(int i1 = 0; i1 < 4; i1++)
        {
            for(int j1 = 0; j1 < 4; j1++)
            {
                a[i1][j1] = b[i1][j1];
            }
        }
    }
    sort(daan.begin(), daan.end());
    cout << daan[0].first << endl;
    int m = 0;
    while(m <= 15)
    {
        if((daan[0].second >> m) & 1)
        {
            int x = m / 4;
            int y = m % 4;
            cout << x + 1 << ' ' << y + 1 << endl;
        }
        m++;
    }
    return 0;
}


活动打卡代码 AcWing 116. 飞行员兄弟

#include<bits/stdc++.h>
using namespace std;

int a[4][4];
int b[4][4];
const int N = 65536;
vector<pair<int,int>> daan;

void cyl(int x, int y)
{
    a[x][0] = (a[x][0] + 1) % 2;
    a[x][1] = (a[x][1] + 1) % 2;
    a[x][2] = (a[x][2] + 1) % 2;
    a[x][3] = (a[x][3] + 1) % 2;
    a[0][y] = (a[0][y] + 1) % 2;
    a[1][y] = (a[1][y] + 1) % 2;
    a[2][y] = (a[2][y] + 1) % 2;
    a[3][y] = (a[3][y] + 1) % 2;
    a[x][y] = (a[x][y] + 1) % 2;
}

int cnt;
int sum;

signed main()
{
    for(int i = 0; i < 4; i++)
    {
        for(int j = 0; j < 4; j++)
        {
            char c;
            cin >> c;
            if(c == '-') a[i][j] = 0;
            else a[i][j] = 1;
            b[i][j] = a[i][j];
        }
    }
    for(int i = 0; i < 65536; i++)
    {
        int m = 0;
        int m1 = 0;
        while(m <= 15)
        {
            if((i >> m) & 1)
            {
                int x = m / 4;
                int y = m % 4;
                cyl(x, y);
                m1++;
            }
            m++;
        }
        bool flag = 1;
        for(int i1 = 0; i1 < 4; i1++)
        {
            for(int j1 = 0; j1 < 4; j1++)
            {
                if(a[i1][j1] == 1) flag = 0;
            }
        }
        if(flag != 0) 
        {
            daan.push_back({m1, i});
        }
        for(int i1 = 0; i1 < 4; i1++)
        {
            for(int j1 = 0; j1 < 4; j1++)
            {
                a[i1][j1] = b[i1][j1];
            }
        }
    }
    sort(daan.begin(), daan.end());
    cout << daan[0].first << endl;
    int m = 0;
    while(m <= 15)
    {
        if((daan[0].second >> m) & 1)
        {
            int x = m / 4;
            int y = m % 4;
            cout << x + 1 << ' ' << y + 1 << endl;
        }
        m++;
    }
    return 0;
}


活动打卡代码 AcWing 90. 64位整数乘法

#include<iostream>
using namespace std;

#define int long long
int ans;

signed main()
{
    int a, b, p;
    cin >> a >> b >> p;
    int x = 1;
    while(b)
    {
        if(b & 1) ans = (ans + a) % p;
        a = (a + a) % p;
        b = (b >> 1);
    }
    cout << ans % p << endl;
    return 0;
}


活动打卡代码 AcWing 89. a^b

#include<iostream>
using namespace std;
#define int long long

int qmi(int a, int b, int p)
{
    int res = 1;
    while(b)
    {
        if(b & 1) res = res * a % p ;
        b = (b >> 1);
        a = a * a % p;
    }
    return res;
}


signed main()
{
    int a, b, p;
    cin >> a >> b >> p;
    cout << qmi(a, b, p) % p << endl;

    return 0;
}


活动打卡代码 AcWing 4721. 排队

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;
int h[N], f[N];
int n;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);

    f[n] = h[n];
    for (int i = n - 1; i; i -- ) f[i] = min(h[i], f[i + 1]);

    for (int i = 1; i <= n; i ++ )
    {
        int x = h[i];
        int l = i, r = n;
        while(l < r)
        {
            int mid = l + r + 1 >> 1;
            if(f[mid] < x) l = mid;
            else r = mid - 1;
        }
        cout << l - i - 1 << ' ';
    }
    return 0;
}



差分+离散化

#include<bits/stdc++.h>
using namespace std;

#define int long long
int n, x, y, z;
vector<int> temp;
struct heat
{
    int l, r;
}ht[40040];
int da[40040];
int sn[40040];

int find(int x)
{
    int l = 0, r = temp.size() - 1;
    while(l < r)
    {
        int mid = l + r + 1 >> 1;
        if(temp[mid] <= x) l = mid;
        else r = mid - 1;
    }
    return l + 1;
}

signed main()
{
    cin >> n >> x >> y >> z;
    for(int i = 1; i <= n; i++)
    {
        int lt, rt;
        cin >> lt >> rt;
        temp.push_back(lt);
        temp.push_back(rt);
        ht[i].l = lt;
        ht[i].r = rt;
    }
    sort(temp.begin(), temp.end());
    temp.erase(unique(temp.begin(), temp.end()), temp.end());

    for(int i = 1; i <= n; i++)
    {
        da[0] += x;
        da[find(ht[i].l)] += y - x;
        da[find(ht[i].r) + 1] += z - y;
        da[40039] -= z;
    }

    int cnt = -1;
    for(int i = 0; i <= temp.size(); i++)
    {
        if(i - 1 >= 0) sn[i] = sn[i - 1] + da[i];
        else sn[i] = da[i];
    }
    for(int i = 1; i <= temp.size(); i++)
    {
        if(cnt < sn[i]) cnt = sn[i];
    }
    cout <<  cnt << endl;
    return 0;
}


活动打卡代码 AcWing 103. 电影

#include<bits/stdc++.h>
using namespace std;

#define int long long
int n, m;
const int N = 6e5 + 60;
vector<int> lge;
vector<int> kxj;
vector<pair<int, int>> mov;
int lg[N];

int findd(int x)
{
    int lt = 0, rt = lge.size() - 1;
    while(lt < rt)
    {
        int mid = lt + rt + 1>> 1;
        if(lge[mid] <= x) lt = mid;
        else rt = mid - 1;
    }
    return lt;
}

signed main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        kxj.push_back(x);
        lge.push_back(x);
    }

    cin >> m;
    for(int i = 0; i < m; i++)
    {
        int x;
        cin >> x;
        lge.push_back(x);
        mov.push_back({x, 0});
    }
    for(int i = 0; i < m; i++)
    {
        int x;
        cin >> x;
        lge.push_back(x);
        mov[i].second += x;
    }

    sort(lge.begin(), lge.end());
    lge.erase(unique(lge.begin(), lge.end()), lge.end());

    for(int i = 0; i < kxj.size(); i++)
    {
        int x = findd(kxj[i]);
        lg[x] ++;
    }

    int max1 = lge[lge.size() - 1];

    int yuyan = 0;
    int yyting = lg[findd(mov[yuyan].first)];
    int yykan = lg[findd(mov[yuyan].second)];

    for(int i = 1; i < m; i++)
    {
        if(lg[findd(mov[i].first)] > lg[findd(mov[yuyan].first)]) yuyan = i;
        else if(lg[findd(mov[i].first)] == lg[findd(mov[yuyan].first)] && lg[findd(mov[i].second)] > lg[findd(mov[yuyan].second)]) yuyan = i; 
    }
    cout << yuyan + 1 << endl;

    return 0;
}


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

二分

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1e5 + 10;
int n;
int a[N], b[N], c[N];
int cnt;

signed main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    for(int i = 1; i <= n; i++) scanf("%lld", &b[i]);
    for(int i = 1; i <= n; i++) scanf("%lld", &c[i]);
    sort(a + 1, a + n + 1);
    sort(b + 1, b + n + 1);
    sort(c + 1, c + n + 1);
    for(int i = 1; i <= n; i++)
    {
        int x = b[i];
        int l = 1, r = n;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(a[mid] >= x) r = mid;
            else l = mid + 1;
        }
        int l1;
        if(a[l] == x) l1 = l - 1;
        else 
        {
            if(a[l] < x) l1 = l;
            else l1 = l - 1; 
        } 
        l = 1, r = n;
        while(l < r)
        {
            int mid = l + r + 1 >> 1;
            if(c[mid] <= x) l = mid;
            else r = mid - 1;
        }
        int l2;
        if(c[l] == x) l2 = n - l;
        else
        {
            if(c[l] > x) l2 = n - (l - 1);
            else
            {
                if(l == n) l2 = 0;
                else l2 = n - l;
            }
        }
        cnt += l1 * l2;
        l1 = 0, l2 = 0;
    }
    cout << cnt << endl;
    return 0;
}