目錄

1.Saruman's Army

2.Catch That Cow

3.Drying

4.P3386 【模板】二分圖最大匹配

5. Swap Dilemma

---

1.Saruman's Army

3069 -- Saruman's Army (poj.org)

這道題就是要求我們在給的的位置放入?palantir，每個?palantir有R大小的射程范圍，要求求出最少需要安裝多少個?palantir，才能將讓所有的軍隊在射程范圍內。

思路：

先將軍隊的位置排序，為二分做準備。

先枚舉第一個位置，二分找到小于等于這個位置+R的位置，在此位置安裝一個?palantir。

再從這個位置開始重復上述操作。直到索引i>n。

#include<iostream>
#include<algorithm>
#define ll long long
#define TEST int T;cin>>T;while(T--)
#define lowbit(x) x&(-x) 
using namespace std;
const int N = 1500;
const int M = 1e9 + 2;
int base1 = 131, base2 = 13311;
ll a[N];
void solve()
{ll n,k;while(cin>>k>>n){if(k==-1) break;for(int i=1;i<=n;i++) cin>>a[i];ll ans=0;sort(a+1,a+1+n);int i=1;while(i<=n){ans++;//找安裝的位置int pos=upper_bound(a+1,a+1+n,a[i]+k)-a-1;pos=upper_bound(a+1,a+1+n,a[pos]+k)-a;i=pos;}cout<<ans<<"\n";}
}
int main()
{solve();return 0;
}

2.Catch That Cow

3278 -- Catch That Cow (poj.org)

給出我們起點和終點，要求我們求出從起點到終點最少需要幾個操作。

操作1：當前位置+1

操作2：當前位置-1

操作3：傳送到當前位置*2的位置

思路：

用bfs算法去搜索答案。注意不能亂搜索：

當當前位置大于終點位置，不能入隊操作1和3

當當前位置小于0，不能入隊操作3

當當前位置大于終點位置，才能入隊操作2

#include<iostream>
#include<algorithm>
#include<queue>
#define ll long long
#define TEST int T;cin>>T;while(T--)
#define lowbit(x) x&(-x) 
using namespace std;
const int N = 1500;
const int M = 200010;
int base1 = 131, base2 = 13311;
ll a[N],v[M];
struct node
{ll v,st;
};
void solve()
{ll n,k;cin>>n>>k;queue<node>q;node start,nextt;start.st=0,start.v=n;q.push(start);while(!q.empty()){node t=q.front();q.pop();if(t.v==k){cout<<t.st<<"\n";return;}if(t.v>0&&!v[t.v-1])nextt.v=t.v-1,nextt.st=t.st+1,q.push(nextt),v[t.v-1]=1;if(t.v<k&&!v[t.v+1])nextt.v=t.v+1,nextt.st=t.st+1,q.push(nextt),v[t.v+1]=1;if(t.v>0&&t.v<k&&!v[2*t.v])nextt.v=t.v*2,nextt.st=t.st+1,q.push(nextt),v[2*t.v]=1;}
}
int main()
{solve();return 0;
}

3.Drying

3104 -- Drying (poj.org)

要求求出全部衣物都干的最短時間。

二分答案去求解，L為1，R為最濕的衣服的濕潤度。

如何判斷mid可行？

對衣服的濕潤度排序，找到大于mid的衣服，將它減去，再除以烘干片每分鐘可以減少的濕潤度，向上取整。最后這個值要是小于mid，則這個值可行。

#include<iostream>
#include<algorithm>
#include<queue>
#include<math.h>
#define ll long long
#define TEST int T;cin>>T;while(T--)
#define lowbit(x) x&(-x)
using namespace std;
const int N = 150000;
const int M = 200010;
int base1 = 131, base2 = 13311;
ll n, k, a[N];
bool check(ll x) {ll ans = x;int pos = upper_bound(a + 1, a + 1 + n, x) - a;for (int i = pos; i <= n; i++) {ans -= (a[i] - x + k - 2) / (k - 1);if (ans < 0) return false;}return true;
}
void solve() {scanf("%lld", &n);for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);scanf("%lld", &k);sort(a + 1, a + 1 + n);if (k == 1) {cout << a[n] << "\n";return ;}ll l = 1, r = a[n], mid;while (l < r) {mid = l + r >> 1;if (check(mid)) { //這段時間可以烘干,再試試更短的時間r = mid;} else {l = mid + 1;}}cout << r << "\n";
}
int main() {solve();return 0;
}

4.P3386 【模板】二分圖最大匹配

P3386 【模板】二分圖最大匹配 - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)

匈牙利算法的板子題。

#include<iostream>
#include<algorithm>
#include<queue>
#include<math.h>
#include<cstring>
#define ll long long
#define TEST int T;cin>>T;while(T--)
#define lowbit(x) x&(-x)
using namespace std;
const int N = 100010;
const int M = 16000101;
int base1 = 131, base2 = 13311;
ll colour[N], head[N];
struct Node {int u, v, net;
} e[N << 2];
ll n, m, cnt = 0;
ll v[N];
vector<vector<ll> >f;
bool dfs(int x, int co) {if (v[x] == co) return false;v[x] = co;for (auto k : f[x]) {if (!head[k] || dfs(head[k], co)) {head[k] = x;return true;}}return false;
}
void solve() {cin >> n >> m >> cnt;f.resize(n + m + 1);for (int u, v; cnt; cnt--) {cin >> u >> v;f[u].push_back(v);}ll ans = 0;for (int i = 1; i <= n; i++) {if (dfs(i, i)) ans++;}cout << ans << "\n";
}
int main() {solve();return 0;
}

5. Swap Dilemma

Problem - D - Codeforces

先將兩個數組排序，再判斷這兩個數組是否相同，相同再進行下一步，反之直接輸出NO。

求逆序對，分別討論兩個逆序對的奇偶性，奇偶性相同則輸出YES，反之輸出NO。

#include<iostream>
#include<algorithm>
#include<queue>
#include<math.h>
#include<cstring>
#include<map>
#define ll long long
#define TEST int T;cin>>T;while(T--)
#define lowbit(x) x&(-x)
using namespace std;
const int N = 100010;
const int M = 200010;
int base1 = 131, base2 = 13311;
ll n, rak1[N], rak2[N];
struct Node {ll v, id;
} e1[N], e2[N];
map<ll,ll>f1,f2;
bool cmp(Node a, Node b) {if (a.v == b.v) return a.id < b.id;return a.v < b.v;
}
void add1(int pos) {for (int i = pos; i <= n; i += lowbit(i)) f1[i]++;
}
void add2(int pos) {for (int i = pos; i <= n; i += lowbit(i)) f2[i]++;
}
ll ask1(int pos) {ll ans = 0;for (int i = pos; i >= 1; i -= lowbit(i)) ans += f1[i];return  ans;
}
ll ask2(int pos) {ll ans = 0;for (int i = pos; i >= 1; i -= lowbit(i)) ans += f2[i];return  ans;
}
void solve() {scanf("%lld", &n);f1.clear();f2.clear();for (int i = 1; i <= n; i++) {scanf("%lld", &e1[i].v), e1[i].id = i;}for (int i = 1; i <= n; i++) {scanf("%lld", &e2[i].v), e2[i].id = i;}sort(e1 + 1, e1 + 1 + n, cmp);sort(e2 + 1, e2 + 1 + n, cmp);for (int i = 1; i <= n; i++) {if (e1[i].v != e2[i].v) {cout << "NO\n";return;}rak1[e1[i].id] = i;rak2[e2[i].id] = i;}ll ans1 = 0, ans2 = 0;for (int i = 1; i <= n; i++) {int pos1, pos2;pos1 = rak1[i];pos2 = rak2[i];ans1 += ask1(n) - ask1(pos1);ans2 += ask2(n) - ask2(pos2);add1(pos1);add2(pos2);}if (abs(ans1 - ans2) % 2 != 0) {cout << "NO\n";} else {cout << "YES\n";}
}
int main() {TESTsolve();return 0;
}