报名网站建设,安徽 网站开发,课程培训,免费主机空间网站目录 1.Sarumans Army
2.Catch That Cow
3.Drying
4.P3386 【模板】二分图最大匹配
5. Swap Dilemma 1.Sarumans Army
3069 -- Sarumans Army (poj.org) 这道题就是要求我们在给的的位置放入 palantir#xff0c;每个 palantir有R大小的射程范围#xff0c;要求求出最少…目录 1.Sarumans Army
2.Catch That Cow
3.Drying
4.P3386 【模板】二分图最大匹配
5. Swap Dilemma 1.Sarumans Army
3069 -- Sarumans Army (poj.org) 这道题就是要求我们在给的的位置放入 palantir每个 palantir有R大小的射程范围要求求出最少需要安装多少个 palantir才能将让所有的军队在射程范围内。
思路
先将军队的位置排序为二分做准备。
先枚举第一个位置二分找到小于等于这个位置R的位置在此位置安装一个 palantir。
再从这个位置开始重复上述操作。直到索引in。
#includeiostream
#includealgorithm
#define ll long long
#define TEST int T;cinT;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(cinkn){if(k-1) break;for(int i1;in;i) cina[i];ll ans0;sort(a1,a1n);int i1;while(in){ans;//找安装的位置int posupper_bound(a1,a1n,a[i]k)-a-1;posupper_bound(a1,a1n,a[pos]k)-a;ipos;}coutans\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
#includeiostream
#includealgorithm
#includequeue
#define ll long long
#define TEST int T;cinT;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;cinnk;queuenodeq;node start,nextt;start.st0,start.vn;q.push(start);while(!q.empty()){node tq.front();q.pop();if(t.vk){coutt.st\n;return;}if(t.v0!v[t.v-1])nextt.vt.v-1,nextt.stt.st1,q.push(nextt),v[t.v-1]1;if(t.vk!v[t.v1])nextt.vt.v1,nextt.stt.st1,q.push(nextt),v[t.v1]1;if(t.v0t.vk!v[2*t.v])nextt.vt.v*2,nextt.stt.st1,q.push(nextt),v[2*t.v]1;}
}
int main()
{solve();return 0;
}
3.Drying
3104 -- Drying (poj.org) 要求求出全部衣物都干的最短时间。
二分答案去求解L为1R为最湿的衣服的湿润度。
如何判断mid可行
对衣服的湿润度排序找到大于mid的衣服将它减去再除以烘干片每分钟可以减少的湿润度向上取整。最后这个值要是小于mid则这个值可行。
#includeiostream
#includealgorithm
#includequeue
#includemath.h
#define ll long long
#define TEST int T;cinT;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) 匈牙利算法的板子题。
#includeiostream
#includealgorithm
#includequeue
#includemath.h
#includecstring
#define ll long long
#define TEST int T;cinT;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];
vectorvectorll 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。
#includeiostream
#includealgorithm
#includequeue
#includemath.h
#includecstring
#includemap
#define ll long long
#define TEST int T;cinT;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];
mapll,llf1,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;
}
