头像

大头th


访客:526

离线:17小时前



dijkstra算法不是 n*n级别的,这里这道题我的想法是 求出每一个村庄 到商店的最短距离取最小, 那么光dijkstra算法就是 10^10级别,还要求 M(村庄数) * 询问个数次

朴素和堆优化都会TLE 堆优化的也会tle

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

typedef pair<int,int> PII;

const int N = 1e5 + 10;
const int M = 1e5 + 10;

int n,m,k;
bool st[N];
int dis[N];
int h[N],e[N],ne[N],w[N],idx;

void add(int a, int b, int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}

 int dijkstra(int x, int y)
 {
     memset(dis,0x3f,sizeof dis);
     memset(st,false, sizeof st);
     dis[x] = 0;

     priority_queue<PII,vector<PII>,greater<PII>> heap;
     heap.push({0,x});

     while(heap.size())
     {
         auto t = heap.top();
         heap.pop();

         int ver = t.second;
         int distance = t.first;

         if(st[ver]) continue;

         st[ver] = true;

         for(int i = h[ver]; i != -1; i=ne[i])
         {
             int j = e[i];
             if(dis[j] > distance + w[i])
             {
                 dis[j] = distance + w[i];
                 heap.push({dis[j],j});
             }
         }
     }
     return dis[y];
 }


int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while(m--)
    {
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c);
        add(b,a,c);
    }
    /*
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            cout << g[i][j] << " ";
        }
        cout << endl;
    }
    */
    cin >> k;
    int c[k + 1];
    for(int i = 1; i <= k; i++)
    {
        cin >> c[i];

    }
    int Q = 0;
    cin >>Q;
    for(int i = 0; i < Q; i++)
    {
        int a = 0;
        cin >> a;
        int min_ = 0x3f3f3f3f;
        for(int j = 1; j <= k; j++)
        {
            min_ = min(min_,dijkstra(a,c[j]));
        }
        cout << min_ << endl;
    }
}




i我最近刷二分的题,但是搞不明白什么时候用left <= right,什么时候用模板,模板不是万能的吧。求大佬们给个指点,愁死孩子了,



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

借鉴的别人的思路

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

typedef pair[HTML_REMOVED] PII;

const int N = 5;

char g[N][N];
vector[HTML_REMOVED] ans, tmp;

void turn_one(int x, int y)
{
if (g[x][y] == ‘+’) g[x][y] = ‘-‘;
else g[x][y] = ‘+’;
}

void turn_all(int x, int y)
{
for (int i = 0; i < 4; i++)
{
turn_one(x, i);
turn_one(i, y);
}
turn_one(x, y);
}

void dfs(int x, int y)
{
// 如果说所有的把手都操作完了就看看冰箱能否打开
if (x == 3 && y == 4) // y执行到最后一个位置.
{
bool success = true;
for (int i = 0; i < 4; i)
for (int j = 0; j <4; j
)
if (g[i][j] == ‘+’)
{
success = false;
goto end;
}
end:
if (success)
if (ans.empty() || tmp.size() < ans.size())
ans = tmp;
return;
}
// 判断边界,如果y出界了就往下一行移动
if (y == 4) x++, y = 0;

// 操作把手(x, y)
turn_all(x, y);
tmp.push_back({ x, y });
dfs(x, y + 1);
// 恢复现场
tmp.pop_back();
turn_all(x, y);

// 不操作把手(x, y)
dfs(x, y + 1);

}

void dfs1(int x, int y)
{

if(x == 3 && y == 4)
{
    bool successful = true;
    for(int i = 0; i < 4; i++)
    {
        for(int j = 0; j < 4; j++)
        {
            if(g[i][j] == '+')
            {
                successful = false;
                break;
            }
        }
        if(successful == false)
            break;
    }
    if(successful)
    {
        if(ans.size() == 0 || tmp.size() < ans.size())
        {
            ans = tmp;
        }
    }
    return;
}


if(y == 4 && x != 3)
{
    x++; 
    y = 0;
}
turn_all(x,y);
tmp.push_back({x,y});
dfs(x, y + 1);

turn_all(x,y);
tmp.pop_back();

dfs(x,y+1);

}

int main()
{
for (int i = 0; i < 4; i++) scanf(“%s”, g[i]);

// 从(0, 0)开始DFS
dfs1(0, 0);

cout << ans.size() << endl;
for (int i = 0; i < ans.size(); i++) 
    printf("%d %d\n", ans[i].first + 1, ans[i].second + 1);

return 0;

}




class Solution {
public:
int longestSubarray(vector[HTML_REMOVED]& nums) {
int right = 0;
int left = 0;
int max_ = 0;
int index = 0;
while(right < nums.size())
{
if(nums[right] == 0)
index;
while(index > 1)
{
if(nums[left] == 0)
{
index–;
}
left
;

        }

        max_ = max(max_,right - left + 1);
        right++;

    }
    return max_ - 1;
}

};




class Solution {
public:
int kthFactor(int n, int k) {
int index = 0;
int i = 1;
while(index != k)
{
if(n % i == 0)
{
index;
}
i
;

        if(i - 1 == n && index < k)
            return -1;
    }
    return i - 1;
}

};




class Solution {
public:
double average(vector[HTML_REMOVED]& salary) {
sort(salary.begin(),salary.end());
int sum = 0;
for(int i = 1; i < salary.size() - 1; i++)
{
sum += salary[i];
}
return ((double) sum / (salary.size() - 2) );
}
};




经典栈 这个还比较好只有 + 和 *

#include <iostream>
#include <stack>
#include <string>
using namespace std;


int n = 0;

int main()
{
    string str;
    cin >> str;
    stack<int> s;
    stack<char> op;
    for(int i = 0; i < str.size(); i++)
    {
        if(str[i] >= '0' && str[i] <= '9')
        {
            int num = 0;
            while(i < str.size()&& str[i] >= '0' && str[i] <= '9')
            {
                num = num* 10 + str[i] - '0';
                i++;
            }
            i -= 1;
            if(!op.empty() && op.top() == '*')
            {
                num = (num%10000 * s.top()) % 10000;
                op.pop();
                s.pop();
                s.push(num);
            }
            else
                s.push(num%10000);
        }
        else if(str[i] == '+')
        {
            op.push('+');
        }
        else if(str[i] == '*')
        {
            op.push('*');
        }
    }
    while(!op.empty())
    {
        int a = s.top();
        s.pop();
        op.pop();
        int b = s.top();
        s.pop();
        a = (a + b) % 10000;
        s.push(a);
    }
    cout << s.top() <<endl;

}




#include <iostream>
#include <unordered_set>
#include <queue>

using namespace std;

const int N = 21;
char a[N][N];
int n,m;
bool st[N][N];
unordered_set<char> s;


static int pos[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
void bfs()
{
    queue<pair<int,int>> q;
    q.push({0,0});
    st[0][0] = true;

    while(!q.empty())
    {
        auto tmp = q.front();
        q.pop();
        s.insert(a[tmp.first][tmp.second]);

        for(int i = 0; i < 4; i++)
        {
            int nx = pos[i][0] + tmp.first;
            int ny = pos[i][1] + tmp.second;
            if(nx < 0 || nx >= m || ny < 0 || ny >= n ||
            s.count(a[nx][ny]) || st[nx][ny])
            continue;

            q.push({nx,ny});
            s.insert(a[nx][ny]);
            st[nx][ny] = true;
        }
    }
}


int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            cin >>a[i][j];
        }
    }
    cout << s.size() << endl;
}




来自弱鸡的标准dfs

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;
const int N = 310;
char a[N][N];
int dis[N][N];
bool st[N][N];
int T,x,y,endx,endy,n,m;

static int pos[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};

int bfs()
{

    memset(dis, 0, sizeof dis);
    memset(st,false,sizeof st);
    queue<pair<int,int>> q;
    q.push({x,y});
    dis[x][y] = 0;

    while(!q.empty())
    {
        auto tmp = q.front();
        q.pop();

        if(tmp.first == endx && tmp.second == endy)
        {
            return dis[tmp.first][tmp.second];
        }

        for(int i = 0; i < 4; i++)
        {
            int nx = tmp.first + pos[i][0];
            int ny = tmp.second + pos[i][1];
            if(nx < 0 || nx >= n || ny < 0 || ny >=m 
            || st[nx][ny] == true || a[nx][ny] == '#')
                continue;
            q.push({nx,ny});
            dis[nx][ny] = dis[tmp.first][tmp.second] + 1;
            st[nx][ny] = true;
        }
    }
    return -1;
}
int main()
{
    while(cin >> n >> m, n || m)
    {

        for(int i = 0; i < n; i++)
        {
            for(int j =0; j < m; j++)
            {
                cin >> a[i][j];
                if(a[i][j] == '@')
                {
                    x = i;
                    y = j;
                }
                if(a[i][j] == '*')
                {
                    endx = i;
                    endy = j;
                }
            }
        }
        cout << bfs() <<endl;

    }
}



O(1) 时间复杂度

class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) {

        if(nums.size() == 0)
            return 0;
        int curTimes = 0;
        int curValue = nums[0];
        for(int i = 1; i < nums.size(); i++)
        {
            if(curValue == nums[i])
            {
                curTimes++;
            }
            else
            {
                curTimes--;
            }

            if(curTimes < 0)
            {
                curValue = nums[i];
                curTimes = 1;
            }
        }
        curTimes = 0;
        for(int i = 0; i < nums.size(); i++)
        {
            if(nums[i] == curValue)
            {
                curTimes++;
            }
        }
        if(curTimes >= nums.size()/2)
            return curValue;
        else
            return 0;
    }
};