kotori和氣球

題目鏈接

題解

1. 數學-排列組合
2. 每次乘完之后對109取模

代碼

#include<iostream>using namespace std;int main()
{int n,m;cin >> n >> m;int ans = n;int k = m - 1;while(k--){ans *= (n-1);// 每次乘完之后對109取模ans %= 109;}cout << ans << '\n';return 0;
}

走迷宮

題目鏈接

題解

1. bfs其實都是一個模版

代碼

#include <iostream>
#include<cstring>
#include<queue>
using namespace std;int n,m;
int x1,y1,x2,y2;
const int N = 1010;
char arr[N][N];
int vis[N][N];// 既表示當前點的步數又表示當前點是否已經走過了int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};int bfs()
{// 沒有終點,終點是墻if(arr[x2][y2] == '*') return -1;// 沒有走過的點初始都是-1memset(vis,-1,sizeof(vis));queue<pair<int,int>> q;q.push({x1,y1});// 起點入隊vis[x1][y1] = 0;while(q.size()){auto[a,b] = q.front();// 結構化綁定,把pair的first賦給a,second賦給bq.pop();for(int i = 0;i < 4;i++){int x = a + dx[i],y = b + dy[i];if(arr[x][y] == '.' && x >= 1 && x <= n && y >= 1 && y <= m &&vis[x][y] == -1){q.push({x,y});vis[x][y] = vis[a][b] + 1;// 如果已經搜到了返回這個點if(x2 == x && y2 == y) return vis[x][y];} }}return -1;
}
int main()
{cin >> n >> m;cin >> x1 >> y1 >> x2 >> y2;for(int i = 1;i <= n;i++){for(int j = 1;j <= m;j++){cin >> arr[i][j];}}cout << bfs() << '\n';return 0;
}

主持人調度（二）（難題）

題目鏈接

題解

1. 優先級隊列，小根堆+排序
2. 先把區間按照左端點排序，左端點排序后可以確保當前是該活動是最早開始的，如果不排序就有活動可能錯誤地加上主持人
3. 然后先把第一個端點加入堆中，從第二個點比較，第二個點的左端點如果比第一個點的右端點大就可以更新堆，把第二個點的右端點入堆，不需要加新的主持人，否則有重疊部分，第二個點的左端點跟最小的右端點比都小，就要新加入主持人，入堆

代碼

class Solution 
{
public:int minmumNumberOfHost(int n, vector<vector<int>>& startEnd){sort(startEnd.begin(),startEnd.end());priority_queue<int,vector<int>,greater<int>> pq;// 小根堆pq.push(startEnd[0][1]);for(int i = 1;i < n;i++){if(startEnd[i][0] >= pq.top()){pq.pop();pq.push(startEnd[i][1]);}else{pq.push(startEnd[i][1]);}}return pq.size();}
};