Winter vacation daily question 2022 [week1 not finished]

2058. Clumsy fingers 【 enumeration 】

#include<bits/stdc++.h>
using namespace std;
string a,b;
typedef long long int LL;
bool check(int sum) 
{
    
	string temp;
	if(sum==0) temp="0";
	while(sum) temp=to_string(sum%3)+temp,sum/=3;
	int cnt=0;
	for(int i=0;i<b.size();i++) if(temp[i]!=b[i]) cnt++;
	if(temp.size()==b.size()&&cnt==1) return true;
	return false;
}
int main(void)
{
    
	cin>>a>>b;
	for(int i=0;i<a.size();i++)// Enumerate which bit is wrong 
	{
    
		LL sum=0;
		for(int j=0;j<a.size();j++)
		{
    
			if(i==j) sum=sum*2+!(a[j]-'0');
			else sum=sum*2+a[j]-'0';
		}
		if(check(sum)) 
		{
    
			cout<<sum<<endl;
			return 0;
		}
	}
	return 0;
}

2041. Haystack 【 Difference 】

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int c[N],n,m;
vector<int>ve;
void add(int l,int r,int w)
{
    
	c[l]+=w;
	c[r+1]-=w;
}
int main(void)
{
    
	cin>>n>>m;
	while(m--)
	{
    
		int a,b; cin>>a>>b;
		add(a,b,1);
	}
	for(int i=1;i<=n;i++)
	{
    
		c[i]+=c[i-1];
		ve.push_back(c[i]);
	}
	sort(ve.begin(),ve.end());
	cout<<ve[n/2];
	return 0;
}

2060. Cow beauty pageant 【dfs + thinking 】

Let's talk about the points of different connected blocks , Store in two sets .
Then enumerate the points of the two sets , Find the distance between any two points of two sets .
The shortest distance between two points , Must be Manhattan distance , But the distance between two points in Manhattan may have some obstacles .
But the problem must change to the distance between these two points . Therefore, directly enumerate points to find all Manhattan distances and take one min that will do .

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=155;
string s[N];
int n,m,cnt;
int dx[4]={
    -1,0,0,1};
int dy[4]={
    0,-1,1,0};
vector<PII> ve[15];
void dfs(int x,int y,int k)
{
    
    ve[k].push_back({
    x,y});
    s[x][y]='.';
    for(int i=0;i<4;i++)
    {
    
        int tempx=x+dx[i];
        int tempy=y+dy[i];
        if(tempx<0||tempx>=n||tempy<0||tempy>=m) continue;
        if(s[tempx][tempy]!='X') continue;
        dfs(tempx,tempy,k);
    }
}
int solve(PII a,PII b)
{
    
    return abs(a.first-b.first)+abs(a.second-b.second)-1;
}
int main(void)
{
    
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>s[i];
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(s[i][j]=='X') dfs(i,j,cnt++);
    int ans=1e9;
    for(int i=0;i<ve[0].size();i++)
        for(int j=0;j<ve[1].size();j++)
                ans=min(ans,solve(ve[0][i],ve[1][j]));
    cout<<ans;
    return 0;
}

2019. Tractor 【 deque 】

Turn it into a graph theory problem to find the shortest path , Because only the edge power 0 and 1, So you can use two-way search directly ,0 Add to the opposite ,1 Join the back of the line .

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int g[N][N],dist[N][N],st[N][N],n,stx,sty;
int dx[4]={
    -1,0,0,1};
int dy[4]={
    0,-1,1,0};
int bfs(int x,int y)
{
    
    memset(dist,0x3f,sizeof dist);
    dist[x][y]=0;
    deque<pair<int,int>>q; q.push_back({
    x,y});
    while(q.size())
    {
    
        auto temp=q.front(); q.pop_front();
        x=temp.first,y=temp.second;
        if(!x&&!y) return dist[x][y];
        if(st[x][y]) continue;
        st[x][y]=1;
        for(int i=0;i<4;i++)
        {
    
            int tempx=x+dx[i];
            int tempy=y+dy[i];
            if(tempx<0||tempx>=N||tempy<0||tempy>=N) continue;
            int w=0;
            if(g[tempx][tempy]) w=1;// obstacle 
            if(dist[tempx][tempy]>dist[x][y]+w)
            {
    
                dist[tempx][tempy]=dist[x][y]+w;
                if(w) q.push_back({
    tempx,tempy});
                else q.push_front({
    tempx,tempy});
            }
        }
    }
    return -1;
}
int main(void)
{
    
    cin>>n>>stx>>sty;
    while(n--)
    {
    
        int a,b; cin>>a>>b;
        g[a][b]=1;
    }
    cout<<bfs(stx,sty);
    return 0;
}