头像

仅存老实人

$SJTU$ $\href{https://leopoldacc.github.io/Blogs/}{\text{My Blog}}$




离线:16小时前


活动打卡代码 AcWing 3502. 不同路径数

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

int a[6][6];
set<int> s;
int n,m,K;
int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};

void dfs(int x,int y,int k, int num)
{
    if(k==K)
    {
        s.insert(num);
        return ;
    }
    for(int i=0;i<4;i++)
    {
        int nx = x+dirs[i][0], ny = y+dirs[i][1];
        if(nx>=0&&nx<n&&ny>=0&&ny<m)
        {
            dfs(nx, ny, k+1, num*10+a[nx][ny]);
        }
    }
}

int main()
{
    cin>>n>>m>>K;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>a[i][j];
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            dfs(i,j,0,a[i][j]);

    cout<<s.size();
    return 0;
}


活动打卡代码 AcWing 3499. 序列最大收益

/*
状态表示:
    f[i][k] 只考虑前i个数 共删除了k个数 且第i个数保留的所有方案集合
    子集 从第i个数保留--则倒数第二个保留的数j作为划分条件
         同时可以发现这样的约束下[j,i]之间的数都被删完了
                                则[j,i]删掉了i-j-1个数
         [1,j] 删掉了 k - (i - j -1) 个数
状态转移 
    总收益 = [1,j]收益 + j和i相邻的收益
    f[i][k] = f[j][k-(i-j-1)] + w[a[i]][a[j]]
*/
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=210;

int w[N][N],a[N],f[N][N];
int n,K,m;

int main()
{
    cin>>n>>K>>m;
    for(int i=1;i<=m;i++)cin>>a[i];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>w[i][j];
    memset(f,0,sizeof f);
    // 第一个数一定在最优解中被保留,所以直接从第二个数枚举
    for(int i=2;i<=m;i++)
        for(int k=0;k<=K;k++)
            for(int j=1;j<i;j++)
                if(k>=i-j-1)
                    f[i][k] = max(f[i][k],f[j][k-(i-j-1)]+w[a[i]][a[j]]);
    int res=0;
    for(int i=0;i<=K;i++)
        res=max(res,f[m][i]);
    cout<<res;
    return 0;
}


活动打卡代码 AcWing 3493. 最大的和

#include<iostream>
#include<cstring>
typedef long long ll;
using namespace std;

const int N=100010;

ll n,k,a[N],s[N],b[N];

int main()
{
    memset(a,0,sizeof a);
    memset(b,0,sizeof b);
    memset(s,0,sizeof s);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        s[i] = s[i-1]+a[i];
    }
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        b[i] = b[i-1] + x*a[i];
    }
    ll res = b[n];
    for(int i=1;i<=n;i++)
    {
        ll tmp = i>=k ? b[n] - (b[i]-b[i-k]) + s[i] - s[i-k] : b[n] - b[i] + s[i];//边界条件
        res = max(res,tmp);
    }
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 3485. 最大异或和

#include<iostream>
#include<cstring>

using namespace std;

const int N=100010;

int ne[N*33][33],tot,cnt[N*33],s[N];

void insert(int x)
{
    int p=0;
    for(int i=30;i>=0;i--)
    {
        int u=x>>i&1;
        if(!ne[p][u])ne[p][u]=++tot;
        p = ne[p][u];
        cnt[p]++;
    }
}

void del(int x)
{
    int p=0;
    for(int i=30;i>=0;i--)
    {
        int u=x>>i&1;
        p=ne[p][u];
        cnt[p]--;
    }
}

int find(int x)
{
    int p = 0,res = 0;
    for(int i=30;i>=0;i--)
    {
        int u=x>>i&1;
        if(ne[p][u^1] && cnt[ne[p][u^1]])
        {
            res+=1<<i;
            p=ne[p][u^1];
        }
        else
        {
            p=ne[p][u];
        }
        if(!p)return res;
    }
    return res;
}

int main()
{
    int n,m;
    cin>>n>>m;
    int res = 0;
    insert(s[0]);//边界条件
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        s[i] ^= s[i-1];
        insert(s[i]);
        if(i>m)del(s[i-m-1]);
        res = max(res,find(s[i]));
    }
    cout<<res;
    return 0;
}


活动打卡代码 AcWing 435. 传球游戏

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

const int N=50;
int f[N][N];
//f[i][j] 传j次到第i个人的方案数

int main()
{
    int n,m;
    cin>>n>>m;
    f[0][0]=1;
    for(int j=1;j<=m;j++)
    {
        for(int i=0;i<n;i++)
        {
            f[i][j]+=f[(i+1+n)%n][j-1]+f[(i-1+n)%n][j-1];
        }
    }
    cout<<f[0][m];
    return 0;
}


活动打卡代码 LeetCode 1473. 粉刷房子 III

const int INF = 0x3f3f3f3f;
int f[110][22][110];
class Solution {
public:
    int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
        memset(f,0x3f,sizeof f);
        for(int j=0;j<n;j++)f[0][j][0]=0;
        for(int i=1;i<=m;i++)
        {
            int cur = houses[i-1];
            for(int j=0;j<n;j++)
            {
                for(int k=1;k<=target;k++)
                {
                    if(k>i)
                    {
                        f[i][j][k]=INF;
                        continue;
                    }
                    if(cur!=0)//不需要涂第i个
                    {
                        if(j==cur-1)//则第i个只能涂cur
                        {
                            //第i个和第i-1个不同
                            for(int p=0;p<n;p++)
                            {
                                if(p!=j)f[i][j][k]=min(f[i][j][k],f[i-1][p][k-1]);
                            }
                            //第i个和第i-1个相同
                            f[i][j][k]=min(f[i][j][k],f[i-1][j][k]);
                        }
                        else f[i][j][k]=INF;
                    }
                    else//需要涂第i个
                    {
                        //第i个和第i-1个不同
                        for(int p=0;p<n;p++)
                        {
                            if(p!=j)f[i][j][k]=min(f[i][j][k],f[i-1][p][k-1]+cost[i-1][j]);
                        }
                        //第i个和第i-1个相同
                        f[i][j][k]=min(f[i][j][k],f[i-1][j][k]+cost[i-1][j]);
                    }
                }
            }
        }
        int res = INF;
        for(int j=0;j<n;j++)
        {
            res = min(res,f[m][j][target]);
        }
        return res == INF?-1:res;
    }
};


活动打卡代码 LeetCode 5733. 最近的房间

class Solution {
public:
    vector<int> closestRoom(vector<vector<int>>& rooms, vector<vector<int>>& queries) {
        sort(rooms.begin(),rooms.end(),[](vector<int> &a,vector<int> &b){
            if(a[1]!=b[1])
            {
                return a[1]<b[1];
            }
            return a[0]<b[0];
        });
        int tot=0;
        for(auto &q:queries)q.push_back(tot++);
        sort(queries.begin(),queries.end(),[](vector<int> &a,vector<int> &b)
        {
            if(a[1]!=b[1])
            {
                return a[1]<b[1];
            }
            return a[0]<b[0];
        });
        int m=rooms.size(),n=queries.size();
        int i=m-1,j=n-1,INF=1e9;
        vector<int> res(n);
        set<int> s{-INF,INF};
        for(int j=n-1;j>=0;j--)
        {
            while(i>=0&&rooms[i][1]>=queries[j][1])
            {
                s.insert(rooms[i--][0]);
            }
            if(s.size()==2)
            {
                res[queries[j][2]]=-1;
            }
            else
            {
                int id = queries[j][0],resid=queries[j][2];
                auto up=s.lower_bound(id);
                auto lo=up;
                lo--;
                if(abs(*up-id)==abs(*lo-id))
                {
                    res[resid]=*lo;
                }
                else if(abs(*up-id)<abs(*lo-id))
                {
                    res[resid]=*up;
                }
                else{
                    res[resid]=*lo;
                }
                if(abs(res[resid])==INF)res[resid]=-1;
            }
        }
        return res;
    }
};




并查集 染色 最短覆盖区间模板

class Solution {
public:
    vector<int> nums,f,lens;
    int find(int x)
    {
        if(x!=f[x])f[x]=find(f[x]);
        return f[x];
    }
    int get(int x)
    {
        return lower_bound(nums.begin(),nums.end(),x)-nums.begin();
    }
    vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
        for(int i=0;i<intervals.size();i++)nums.push_back(intervals[i][0]),nums.push_back(intervals[i][1]);
        for(int i=0;i<queries.size();i++)nums.push_back(queries[i]);
        sort(nums.begin(),nums.end());
        nums.erase(unique(nums.begin(),nums.end()),nums.end());
        // 并查集初始化,n+1是为了让第n个点能有祖宗节点可以赋值
        int n=nums.size();
        f.resize(n+1),lens.resize(n+1,-1);
        for(int i=0;i<n+1;i++)f[i]=i;
        // 区间长度从小到大排序
        sort(intervals.begin(),intervals.end(),[](vector<int> &a,vector<int> &b){
            return a[1]-a[0]<b[1]-b[0];
        });
        // 从最短的区间染色,找当前区间右边最近的第一个没有被染过色的点
        for(auto &interval:intervals)
        {
            int l = get(interval[0]),r=get(interval[1]),len=interval[1]-interval[0]+1;//>=interval[0]的第一个点的索引
            while(find(l)<=r)//如果>=l的右边第一个没被染过色的点小于r 则说明这个点可以被当前区间染色 直到点超过区间右边界
            {
                l=find(l);
                lens[l] = len;
                //把当前点删去(怎么理解:之后但凡有点通过find找到l,都不会停在l,而会继续到l+1及之后直到f[l]==l),同时方便继续find(l) 
                f[l] = l + 1;//当[interval[0],interval[1]]中间的点之前都没被染过时,f[k]=k,则相当于继续染下一个点-第l+1个点
            }
        }
        // 由于我们是从最短的区间开始染的,则queries里的点此时染上的lens就是其对应的最短区间长度
        vector<int> res;
        for(auto &i:queries)res.push_back(lens[get(i)]);//第i个点的染色(长度)
        return res;
    }
};

优先队列

struct Q
{
    int val;
    int len;
    int idx;
    bool operator<(const Q &t)const
    {
        return val < t.val;
    }
};
// 包含当前值val的区间一定是 区间左端点t[0]<val中 右端点>val的 
// 并且我们只要只pop出比右端点当前q.val小的区间就一定不会影响到后面的q
struct I
{
    int right;
    int len;
    bool operator<(const I &t)const
    {
        return len > t.len;//默认大顶堆(len<t.len),所以想取小顶堆就要反着排序(len>t.len)
    }
};
class Solution {
public:
    static bool cmp(const vector<int> &a,const vector<int> &b)
    {
        if(a[0]==b[0])return a[1]<b[1];
        return a[0]<b[0];
    }
    vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
        sort(intervals.begin(),intervals.end(),cmp);
        vector<int> res(queries.size());
        vector<Q> myq;
        for(int i=0;i<queries.size();i++)
        {
            myq.push_back({queries[i],0,i});
        }
        sort(myq.begin(),myq.end());
        int cur = 0;
        priority_queue<I> h;
        for(auto q:myq)
        {
            while(cur<intervals.size()&&intervals[cur][0]<=q.val)
            {
                h.push({intervals[cur][1],intervals[cur][1]-intervals[cur][0]+1});
                cur++;
            }
            while(h.size()&&h.top().right<q.val)
            {
                h.pop();
            }
            if(!h.size())res[q.idx]=-1;
            else
            {
                res[q.idx]=h.top().len;
            }
        }
        return res;
    }
};



将问题转化为逆序对问题
a 
↓  
b
的映射关系 c = 5,4,1,2,3
            则我们要交换的次数=逆序对个数
class Solution {
public:
    int getMinSwaps(string a, int k) {
        string b = a;
        int n=a.size();
        vector<int> c(n);
        while(k--)next_permutation(b.begin(),b.end());
        int cnt[10]={0};
        for(int i = 0; i < n; i++)
        {
            int x = b[i] - '0';
            ++cnt[x];
            int y = cnt[x];
            for(int j = 0;j < n; j++)
            {
                if(a[j]-'0' == x)
                {
                    y--;
                    if(y==0)
                    {
                        c[i]=j;//a中第i个数在b中是第j个数
                        break;
                    }
                }
            }
        }
        int res=0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(c[j]>c[i])res++;
            }
        }
        return res;
    }
};

直接交换

class Solution {
public:
    int getMinSwaps(string a, int k) {
        string b = a;
        while(k--)next_permutation(b.begin(),b.end());
        int res = 0, n = a.size();
        for(int i=0;i<n;i++)
        {
            if(b[i]!=a[i])
            {
                int j=i;
                while(a[j]!=b[i])j++;
                while(j>i)
                {
                    swap(a[j],a[j-1]);
                    res++;
                    j--;
                }
            }
        }
        return res;
    }
};


活动打卡代码 AcWing 78. 左旋转字符串

class Solution {
public:
    string leftRotateString(string str, int n) {
        return str.substr(n,str.size())+str.substr(0,n);
    }
};