头像

自律

吹灭读书灯 一身都是月




在线 


最近来访(252)
用户头像
ヅ天使ぺ嫙嵂
用户头像
Froggy
用户头像
夜消梦未消
用户头像
小明_3
用户头像
xueshenwudi
用户头像
CodeWater
用户头像
向北
用户头像
yufuyufu
用户头像
少年梦_6
用户头像
Bestlifee
用户头像
梧榠
用户头像
颠勺
用户头像
levelna
用户头像
yxc
用户头像
Thalf
用户头像
IER
用户头像
侦探
用户头像
limie
用户头像
52Hertz_49
用户头像
金属


自律
1天前

关于在vim粘贴时开头字符丢失的问题


原因:进入粘贴模式后(:set paste),要按 i 进入插入模式,进入插入模式后粘贴则不会丢失字符。




自律
1天前

奶牛棒球

如果直接暴力时间复杂度为 $n^3$ ,$n<=1000$,达到1e9规模,所以要考虑优化。

思路:由题可知第三头牛的位置范围由第一头牛和第二头牛的位置决定
所以枚举第一头牛和第二头牛的位置,二分找到第三头牛的范围,累加范围内牛的个数即为答案。

注意边界问题

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

const int N = 1010;
int q[N];
int n;

int find1(int x)
{
    int l = 0,r = n - 1;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(q[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l;
}

int find2(int x)
{
    int l = 0,r = n - 1;
    while(l < r)
    {
        int mid = l + r + 1 >> 1;
        if(q[mid] <= x) l = mid;
        else r = mid - 1;
    }
    return l;
}

int main()
{
    cin>>n;
    for(int i = 0;i < n;i ++) cin>>q[i];
    sort(q,q + n);

    int ans = 0;
    for(int i = 0;i < n;i ++)
        for(int j = i + 1;j < n;j ++)
        {
            int len = q[j] - q[i];
            int x = 0,y = 0;
            if(q[j] + len <= q[n - 1]) x = find1(q[j] + len);   //处理边界问题
            if(q[j] + 2*len >= 0) y = find2(q[j] + 2*len);
            if((x && y) && y >= x) ans += y - x + 1;
        }

    cout<<ans<<endl;
    return 0;
}


活动打卡代码 AcWing 1945. 奶牛棒球

自律
1天前
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;

const int N = 1010;
int q[N];
int n;

int find1(int x)
{
    int l = 0,r = n - 1;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(q[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l;
}

int find2(int x)
{
    int l = 0,r = n - 1;
    while(l < r)
    {
        int mid = l + r + 1 >> 1;
        if(q[mid] <= x) l = mid;
        else r = mid - 1;
    }
    return l;
}

int main()
{
    cin>>n;
    for(int i = 0;i < n;i ++) cin>>q[i];
    sort(q,q + n);

    int ans = 0;
    for(int i = 0;i < n;i ++)
        for(int j = i + 1;j < n;j ++)
        {
            int len = q[j] - q[i];
            int x = 0,y = 0;
            if(q[j] + len <= q[n - 1]) x = find1(q[j] + len);
            if(q[j] + 2*len >= 0) y = find2(q[j] + 2*len);
            if((x&&y) && y >= x) ans += y - x + 1;
        }

    cout<<ans<<endl;
    return 0;

}



分享 异或

自律
2天前
  • 如果 a^b = c 那么 a^c = b, b^c = a
  • 交换两个数 a=a^b; b=b^a; a=a^b;



自律
2天前

差分 + 离散化

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

const int INF = 2e9;

int n,x,y,z;
map<int,int> b;

int main()
{
    cin>>n>>x>>y>>z;
    for(int i = 0;i < n;i ++)
    {
        int l,r;
        cin>>l>>r;
        b[-INF] += x;
        b[l] += y - x;
        b[r + 1] += z - y;
        b[INF] -= z;
    }

    int ans = -INF,sum = 0;    //sum做前缀和使差分数组变为原数组
    for(auto item : b)
    {
        sum += item.second;
        ans = max(ans,sum);
    }

    cout<<ans<<endl;
    return 0;
}



自律
2天前

闪烁


  • 总共有 $2^n$ 次方个状态,n 最大为16,所以总共有 6w 多个状态,而变化次数 m 为 10的15次方远远大于 6w ,所以要找环优化
  • 二进制用十进制表示后,右边第一位表示第一个灯泡,与题目中左边为第一个灯泡表示状态相反,所以题目中灯泡按照左边相邻灯泡的状态切换在代码中表示为按照右边相邻灯泡的状态切换状态
  • 注意位运算符号优先级
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long LL;

const int N = 1 << 16;
int p[N];   //p记录此状态是第几次变化
int n;
LL m;

int update(int state)   //发现灯泡变化有关异或的规律
{
    int res = 0;
    for(int i = 0;i < n;i ++)
    {
        int j = (i - 1 + n) % n;    //取出右边的一位  
                                    //因为灯带是成环状的 (x+n) % n 保证链中最右边灯泡后边为最左边的灯泡
        int x = state >> i & 1,y = state >> j & 1;
        res |= (x ^ y) << i;
    }
    return res;
}

void print(int state)
{
    for(int i = 0;i < n;i ++)
        cout<<(state >> i & 1)<<endl;
}

int main()
{
    cin>>n>>m;
    int state = 0;      //用十进制表示二进制状态
    for(int i = 0;i < n;i ++)
    {
        int x;
        cin>>x;
        state |= x << i;
    }

    p[state] = 0;   //初始状态是第0次变化
    memset(p,-1,sizeof p);  //初始化表示当前状态未出现
    for(int i = 1; ;i ++)
    {
        state = update(state);
        if(i == m)
        {
            print(state);
            break;
        }

        if(p[state] == -1) p[state] = i;
        else 
        {
            int len = i - p[state];
            int r = (m - i) % len;  //(m-i)剩余的次数
            while(r --)
                state = update(state);
            print(state);
            break;
        }
    }
    return 0;
}


活动打卡代码 AcWing 1960. 闪烁

自律
2天前
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long LL;

const int N = 1e6;
int p[N];   //p记录此状态是第几次变化
int n;
LL m;

int update(int state)   //发现灯泡变化有关异或的规律
{
    int res = 0;
    for(int i = 0;i < n;i ++)
    {
        int j = (i - 1 + n) % n;    //取出右边的一位  
                                    //因为灯带是成环状的 (x+n) % n 保证链中最右边灯泡后边为最左边的灯泡
        int x = state >> i & 1,y = state >> j & 1;
        res |= (x ^ y) << i;
    }
    return res;
}

void print(int state)
{
    for(int i = 0;i < n;i ++)
        cout<<(state >> i & 1)<<endl;
}

int main()
{
    cin>>n>>m;
    int state = 0;      //用十进制表示二进制状态
    for(int i = 0;i < n;i ++)
    {
        int x;
        cin>>x;
        state |= x << i;
    }

    p[state] = 0;   //初始状态是第0次变化
    memset(p,-1,sizeof p);  //初始化表示当前状态未出现
    for(int i = 1; ;i ++)
    {
        state = update(state);
        if(i == m)
        {
            print(state);
            break;
        }

        if(p[state] == -1) p[state] = i;
        else 
        {
            int len = i - p[state];
            int r = (m - i) % len;  //(m-i)剩余的次数
            while(r --)
                state = update(state);
            print(state);
            break;
        }
    }
    return 0;
}



自律
3天前

烽火传递

DP + 单调队列优化

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

const int N = 2e5 + 10;
int f[N],w[N],q[N];     //q维护单调队列 存的是数组下标值 
int n,m;

int main()
{
    cin>>n>>m;
    for(int i = 1; i <= n; i ++) cin>>w[i];

    int l = 0,r = 0;    //初始化q队列中有一个元素表示 f[0]=0 
    for(int i = 1;i <= n;i ++)
    {
        while(q[l] < i - m) l ++;
        f[i] = f[q[l]] + w[i];

        while(l <= r && f[q[r]] > f[i]) r --;   //注意 l <= r 保证队列不空  
        q[++ r] = i;
    } 

    int ans = 1e9;
    for(int i = n - m + 1;i <= n;i ++) ans = min(ans,f[i]);     //在最后m个元素中选最小值 

    cout<<ans<<endl;
    return 0;
} 


活动打卡代码 AcWing 1969. 品种邻近

自律
3天前
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

const int N = 1e6 + 10;
int cnt[N];
int n,k;

int main()
{
    queue<int> q;
    cin>>n>>k;
    int ans = -1;
    for(int i = 0;i < n;i ++)
    {
        int id;
        cin>>id;
        if(cnt[id] > 0) ans = max(ans,id);
        cnt[id] ++;
        q.push(id);
        if(q.size() > k)
        {
            cnt[q.front()] --;  //先减再弹出
            q.pop();
        }
    }
    cout<<ans<<endl;
    return 0;
}


活动打卡代码 AcWing 1978. 奶牛过马路

自律
4天前
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1e5 + 10,INF = 1e7;
#define x first
#define y second
typedef pair<int,int> PII;
PII q[N];
int smax[N],smin[N];
int n;

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

    sort(q + 1,q + 1 + n);

    smax[0] = -INF,smin[n + 1] = INF;
    for(int i = 1; i <= n; i ++) smax[i] = max(smax[i - 1],q[i].y);
    for(int i = n; i >= 1; i --) smin[i] = min(smin[i + 1],q[i].y);

    int ans = 0;
    for(int i = 1;i <= n;i ++)
        if(q[i].y > smax[i - 1] && q[i].y < smin[i + 1])
            ans ++;

    cout<<ans<<endl;
    return 0;
}