头像

GRID




离线:3小时前



GRID
8小时前

某寺庙中有老和尚、小和尚若干。庙内有一水缸,由小和尚提水入缸,供老和尚饮用。水缸可容纳30桶水,每次入水、取水仅为1桶,不可同时进行。水取自同一井中,水井径窄,每次只能容纳一个水桶取水。设水桶个数为5个,试用信号量和P、V操作给出小和尚和老和尚的活动。

分析:

小和尚进程分析:小和尚开始工作时,先看一下水缸有没有空位(empty),如果有,就去打水,打水需要桶,所以需要申请使用水桶,有了桶之后开始到水井打水,打完水后要把水倒入水缸,此时缸中多了一桶水;
老和尚进程分析:老和尚要喝水,先看一下水缸里有没有水(full),如果有,就去喝水,喝水需要桶,所以需要申请使用水桶,有了桶之后开始到水缸喝水,喝完水后缸中少了一桶水。

设置如下信号量:

semaphore empty=30;  // 缸中可装水桶数的空位
semaphore full=0;    //表示缸中水量,初始时没有水
semaphore buckets=5; //可用桶数
semaphore mw=1; //实现对井的互斥
semaphore mj=1; //实现对缸的互斥

伪代码:

semaphore empty=30;  // 缸中可装水桶数的空位
semaphore full=0;    //表示缸中水量,初始时没有水
semaphore buckets=5; //可用桶数
semaphore mw=1; //实现对井的互斥
semaphore mj=1; //实现对缸的互斥
main()
{
    cobegin
    little_monk();
    old_monk();
    coend
}
little_monk(){
    while(1)
    {
        P(empty);       //水缸有没有空位
        P(buckets);     //申请使用水桶
          去井边
        P(mw);          //申请使用水井
          打水
        V(mw);
          打完水回去
        P(mj);          //申请往水缸倒水
         倒水入缸;
        V(mj);          
        V(buckets);     //结束使用水桶
        V(full);        //缸中多了一桶水(变满了,所以是full)
    } 
}
old_monk()
{
    while(1)
    {
        P(full);        //水缸里有没有水
        P(buckets);     //申请使用水桶
        P(mj);          //申请从水缸喝水
          从缸里取水;
        V(mj);
        V(buckets);     //结束使用水桶
        V(empty);       //缸中少了一桶水(变少了,所以是empty)
    }
}



活动打卡代码 AcWing 1116. 马走日

GRID
10小时前
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
int dx[]={-2,-2,-1,-1,1,1,2,2};
int dy[]={1,-1,-2,2,-2,2,-1,1};
int n,m,x_0,y_0,cnt,k,ans,t;
bool st[10][10];
void dfs(int x,int y,int cnt)
{
    if(cnt==k)
    {
        ans++;
        return ;
    }
    for(int i=0;i<8;i++)
    {
        int xx=x+dx[i],yy=y+dy[i];
        if(xx>=0 && xx<n && yy>=0 && yy<m && !st[xx][yy])
        {
            st[xx][yy]=true;
            dfs(xx,yy,cnt+1);
            st[xx][yy]=false;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        cin>>n>>m>>x_0>>y_0;
        k=n*m,ans=0;
        memset(st,false,sizeof st);
        st[x_0][y_0]=true;
        dfs(x_0,y_0,1);
        cout<<ans<<endl;
    }
    return 0;
}



GRID
10小时前

分析

dfs相关题目,每次判断坐标能否跳到,若能就继续dfs,最终所有棋子都达到,ans++。
为了让代码更快执行,可以开启优化:

#pragma GCC optimize(2)
#pragma GCC optimize(3)

能使程序的编译效率大大提升。

也可以对cin,cout优化:

ios::sync_with_stdio(false);

这种优化可以来打消iostream的输入、输出缓存,可以节省许多时间,使效率与scanf与printf相差无几。

优化效果展示:
opt.png

可见优化后将近快了3倍。

C++ 代码

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
int dx[]={-2,-2,-1,-1,1,1,2,2};
int dy[]={1,-1,-2,2,-2,2,-1,1};
int n,m,x_0,y_0,cnt,k,ans,t;
bool st[10][10];
void dfs(int x,int y,int cnt)
{
    if(cnt==k)  //所有棋子都可以跳到,ans++
    {
        ans++;
        return ;
    }
    for(int i=0;i<8;i++)
    {
        int xx=x+dx[i],yy=y+dy[i];
        if(xx>=0 && xx<n && yy>=0 && yy<m && !st[xx][yy])
        {
            st[xx][yy]=true;
            dfs(xx,yy,cnt+1);
            st[xx][yy]=false;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);    //输入输出优化
    cin>>t;
    while(t--)
    {
        cin>>n>>m>>x_0>>y_0;
        k=n*m,ans=0;
        memset(st,false,sizeof st);
        st[x_0][y_0]=true;
        dfs(x_0,y_0,1);
        cout<<ans<<endl;
    }
    return 0;
}



GRID
16小时前

分析

  1. 具有大小的并查集的考查。
  2. 第一次把账户的归属利用哈希表mp存起来。
  3. 第二次使用一个集合哈希表把每一个账户的所有邮件地址存进来,用set是因为要去掉重复的邮件地址。
  4. 最后把集合哈希表的元素加入到答案数组中。

C++ 代码

class Solution {
public:
    int find(int x)
    {
        if(fa[x]!=x) return fa[x]=find(fa[x]);
        return fa[x];
    } 
    void uni(int a,int b)
    {
        int faa=find(a),fbb=find(b);
        if(faa!=fbb)
        {
            if(siz[faa]>siz[fbb])       //账户a比账户b大,把b加入到a里面
            {
                fa[fbb]=faa;
                siz[faa]+=siz[fbb];
            }   
            else{                       //反之把a加入到b里面
                fa[faa]=fbb;
                siz[fbb]+=siz[faa];
            }
        }
    }
    vector<int> fa,siz;
    unordered_map<string,int> mp;
    vector<vector<string>> ans;
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        int n=accounts.size();
        fa = vector<int>(n,0);
        siz = vector<int>(n,1);
        for(int i=0;i<n;i++) fa[i]=i;
        for(int i=0;i<n;i++)
        {
            for(int j=1;j<accounts[i].size();j++)
            {
                if(!mp.count(accounts[i][j]))   //邮件没有出现,就在哈希表中存一下
                {
                    mp[accounts[i][j]]=i;
                }
                else{                           //邮件之前出现过,合并两个账户
                    uni(i,mp[accounts[i][j]]);
                }
            }
        }
        unordered_map<int,set<string> > user;   //账户哈希表,set用于去重
        for(int i=0;i<n;i++)
        {
            fa[i]=find(i);  
            for(int j=1;j<accounts[i].size();j++)   
            {
                user[fa[i]].insert(accounts[i][j]); //把同一账户的所有邮件地址加入到该账户里
            }
        }
        for(auto x:user)    //遍历账户哈希表,加入到答案数组中
        {
            vector<string> temp;
            temp.push_back(accounts[x.first][0]);   //先把名字加入到每个容器中
            for(auto mail: x.second)    //把所有地址加入到临时数组temp中
            {
                temp.push_back(mail);
            }
            ans.push_back(temp);
        }
        return ans;
    }
};



GRID
1天前

分析

参考八数码问题,每个相邻的字符是否翻转其实是已经确定的。统计翻转总数即可。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
string s1,s2;
int ans=0;
int main()
{
    cin>>s1>>s2;
    for(int i=0;i<s1.size()-1;i++)
    {
        if(s1[i]!=s2[i])    //当前串和目标串的字符不同,就翻转相邻的字符
        {
            ans++;
            if(s1[i]=='*') s1[i]='o';
            else s1[i]='*';
            if(s1[i+1]=='*') s1[i+1]='o';
            else s1[i+1]='*';
        }
    }
    cout<<ans;
    return 0;
}


活动打卡代码 AcWing 1208. 翻硬币

GRID
1天前
#include<bits/stdc++.h>
using namespace std;
string s1,s2;
int ans=0;
int main()
{
    cin>>s1>>s2;
    for(int i=0;i<s1.size()-1;i++)
    {
        if(s1[i]!=s2[i])
        {
            ans++;
            if(s1[i]=='*') s1[i]='o';
            else s1[i]='*';
            if(s1[i+1]=='*') s1[i+1]='o';
            else s1[i+1]='*';
        }
    }
    cout<<ans;
    return 0;
}



GRID
1天前

分析

哈希表计数,然后把数对用公式求总数:
fo.png

C++ 代码

class Solution {
public:
    unordered_map<int,int> mp;
    int ans;
    int tupleSameProduct(vector<int>& nums) {
        int n=nums.size();
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                mp[nums[i]*nums[j]]++;
            }
        }
        for(auto& [p,k]:mp)
        {
            ans+=k*(k-1)/2*8;
        }
        return ans;
    }
};



GRID
1天前

分析

求斜率问题,每个相邻坐标求一下斜率,不相同返回false
k.png

C++ 代码

class Solution {
public:
    bool static cmp(vector<int> &a,vector<int> &b)
    {
        if(a[0]!=b[0]) return a[0]<b[0];
        return a[1]<b[1];
    }
    bool checkStraightLine(vector<vector<int>>& coordinates) {
        int n=coordinates.size();
        sort(coordinates.begin(),coordinates.end(),cmp);
        double k=-1e9;
        for(int i=1;i<n;i++)
        {
            double temp=(1.0*(coordinates[i][1]-coordinates[i-1][1]))/(coordinates[i][0]-coordinates[i-1][0]);
            if(k==-1000000000) k=temp;
            else{
                if(temp!=k) return false;
            }
        }
        return true;
    }
};


活动打卡代码 AcWing 429. 奖学金

GRID
1天前

结构体应用

#include<bits/stdc++.h>
using namespace std;
int n;
struct stu{
    int hao,yu,shu,ying,sum;

    bool operator < (const stu& p){
        if(sum!=p.sum) return sum>p.sum;
        if(yu!=p.yu) return yu>p.yu;
        return hao<p.hao;
    }
}score[310];
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        score[i].hao=i+1;
        cin>>score[i].yu>>score[i].shu>>score[i].ying;
        score[i].sum=score[i].yu+score[i].shu+score[i].ying;
    }
    sort(score,score+n);
    int k=n;
    if(n>=5)
        k=5;
    for(int i=0;i<k;i++)
    {
        cout<<score[i].hao<<" "<<score[i].sum<<endl;
    }
    return 0;
}



GRID
1天前

分析

结构体经典应用。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int n;
struct stu{ //构造学生结构体
    int hao,yu,shu,ying,sum;

    bool operator < (const stu& p){     //构造排序函数
        if(sum!=p.sum) return sum>p.sum;
        if(yu!=p.yu) return yu>p.yu;
        return hao<p.hao;
    }
}score[310];
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        score[i].hao=i+1;
        cin>>score[i].yu>>score[i].shu>>score[i].ying;
        score[i].sum=score[i].yu+score[i].shu+score[i].ying;
    }
    sort(score,score+n);
    int k=n;
    if(n>=5)
        k=5;
    for(int i=0;i<k;i++)
    {
        cout<<score[i].hao<<" "<<score[i].sum<<endl;
    }
    return 0;
}