A U193219 混乱的小镇
题目大意:
E小镇是个混乱的地方,一开始每个人自成帮派(即每个人是自己的老大),有时候会发生团体与团体的混战,胜利一方的老大会成为两个帮派的所有人的老大,并将两个帮派合并。
负责治安的警官Eden会记录下每次混战中不同团体的两个人以及胜利者。但需要注意有时候两个人可能属于同一个帮会,此时属于帮会内战,老大是不会发生任何变化的。有时Eden还需要回答来自上司的检查,即询问某个人的老大是谁,Eden想请你写个程序帮帮他。
题解:
并查集模板,数据强度好像比洛谷官方的要大,之前写模板题的路径压缩在这会超时
代码:
#include<bits/stdc++.h>
#define N 100100
using namespace std;
int a[N];
int find(int x) {
return x == a[x] ? a[x] : a[x] = find(a[x]);
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
a[i] = i;
}
while (m--) {
int o;
scanf("%d", &o);
if (o == 0) {
int x, y;
scanf("%d%d", &x, &y);
int c = find(x);
int d = find(y);
a[d] = c;
}
if (o == 1) {
int x;
scanf("%d", &x);
printf("%d\n", find(x));
}
}
return 0;
}
B P1706 全排列问题
题目大意:
按照字典序输出自然数 1 到 n 所有不重复的排列,即 n 的全排列,要求所产生的任一数字序列中不允许出现重复的数字。
题解:
DFS+回溯直接扫就行了,n的范围很小很小。
也可以用STL内置的全排列函数(std::next_permutation)。
关于std::next_permutation的介绍可以参考这里:
https://en.cppreference.com/w/cpp/algorithm/next_permutation
代码:
DFS+回溯:
#include<bits/stdc++.h>
#define N 100100
using namespace std;
vector<int> v;
int vis[20];
void dfs(int begin, int n) {
if (begin == n) {
for (int i = 0; i < n; i++) {
printf("%5d", v[i]);
}
printf("\n");
return;
}
int l = v.size();
for (int i = 1; i <= n; i++) {
int flag = 1;
for(int j = 0; j < l; j++){
if(v[j] == i){
flag = 0;
}
}
if(flag){
v.push_back(i);
dfs(begin + 1, n);
v.pop_back();
}
}
return;
}
int main() {
int n;
cin >> n;
dfs(0, n);
return 0;
}
STL:
#include<bits/stdc++.h>
using namespace std;
vector<int> nums;
int main()
{
int n;
cin>>n;
for(int i = 1; i <= n; i++){
nums.push_back(i);
}
do {
for(int i = 0; i < n; i++){
printf("%5d", nums[i]);
}
printf("\n");
} while(std::next_permutation(nums.begin(), nums.end()));
return 0;
}
C P1102 A-B 数对
题目大意:
给出一串数以及一个数字 C,要求计算出所有 A−B=C 的数对的个数
题解:
先移一下,变成 A - C = B,然后排序之后二分上下界找B的个数就好了。
代码:
#include<bits/stdc++.h>
using namespace std;
long long nums[200010];
int main(){
int n,c;
cin>>n>>c;
for(int i = 0; i < n; i++){
scanf("%lld", &nums[i]);
}
long long ans = 0;
sort(nums, nums + n);
for(int i = 0; i < n; i++){
int k = nums[i] - c;
ans += upper_bound(nums, nums + n, k) - lower_bound(nums, nums + n, k);
}
printf("%lld", ans);
}
D U193113 子串和
题目大意:
给一个长度为n的序列,问有多少子串的和为0?
题解:
先算了前缀和。
最开始算完之后双层for遍历,果断超时,毕竟n^2
已经十个零了= =
然后转用map去记前缀和相同的个数,因为子串和为0等同于两个前缀和相等
$$b{c} = a{1} + a{2} + ... + a{c}$$
$$b{d} = a{1} + a{2} + ... + a{d}$$
$$b{c} - b{d} = a{d+1} + ... + a{c} = 0$$
$$b{c} - b{d} = 0$$ 等同于 $$b{c} = b{d}$$
然后还要算个排列组合,因为任意两个相同的前缀和都可以代表一段相加为0的子段。
代码:
#include<bits/stdc++.h>
#define N 200100
using namespace std;
long long a[N];
long long b[N];
long long C(int d, int n){
long long u = 1;
for(int i = n - d + 1; i <= n; i++){
u *= i;
}
for(int i = 1; i <= d; i++){
u /= i;
}
return u;
}
map<int, int> m;
int main() {
int n;
cin>>n;
for(int i = 1; i <= n; i++){
scanf("%lld", &a[i]);
}
for(int i = 1; i <= n; i++){
b[i] = b[i - 1] + a[i];
}
long long ans = 0;
for(int i = 0; i <= n; i++){
auto it = m.find(b[i]);
int x = 0;
if(it != m.end()){
x = it->second;
m.erase(it);
}
m.insert(make_pair(b[i], x + 1));
}
for(auto it = m.rbegin(); it != m.rend(); it++){
if(it->second > 1){
ans += C(2, it->second);
}
}
printf("%lld", ans);
return 0;
}
E U193234 矩形覆盖
题目大意:
给出二维平面上的n个边与坐标轴平行的矩形,求被它们覆盖过的地方总面积。
0<=x1,y1,x2,y2<=100000
题解:
还不会做,看标签好像是离散化,等会了再来填坑。
之前好像有遇见过类似的但是是求最后一次覆盖的是第几个矩形....应该不太一样。顺便一说好像Leetcode上喜欢出这种,没记错有好几道= =
F P1824 进击的奶牛
题意:
x轴上N个点中选择c个点,问每两个点的最小距离最大时候的值(= =反正就是最小情况的最大值)
题解:
易得具有单调性,考虑二分答案。
代码:
#include<bits/stdc++.h>
using namespace std;
int nums[100010];
int m, l, r;
int main() {
int n, c;
cin>>n>>c;
for (int i = 0; i < n; i++) {
scanf("%d", &nums[i]);
}
sort(nums, nums + n);
l = 0;
r = nums[n - 1] - nums[0] + 10;
for (int i = 0; i < 100; i++) {
m = l + ((r - l) >> 1);
int les = nums[0] + m, ct = 1;
for (int i = 1; i < n; i++) {
if (nums[i] >= les) {
les = nums[i] + m;
ct++;
}
}
if (ct >= c) {
l = m + 1;
} else {
r = m - 1;
}
}
printf("%d", r);
}
G P1396 营救
题意:
一个无向图,要求求出s点到t点的路径中每一个线段的最大值最小的情况是多少。
题解:
emmmmm
开始想的是最短路径魔改,写了个dijk发现好像不是很好改,然后又写了个最小生成树,生成完之后再dfs从起点沿着树的路径到扫到终点就好了。
最开始偷懒用二维数组来标记数是否经过某个线段,然后果断MEL了,然后又改了用vector存才过的...
代码:
#include<bits/stdc++.h>
using namespace std;
int n, m, s, t, u, v, total;
struct edge {
int start, to;
int val;
bool operator<(edge b) {
return val < b.val;
}
} bian[20010];
int f[20010];
int x[20010];
long long ans = 0;
vector<int> vis[20010];
int find(int x) {
return x == f[x] ? f[x] : f[x] = find(f[x]);
}
inline void kruskal() {
for (int i = 1; i <= m; i++) {
u = find(bian[i].start);
v = find(bian[i].to);
if (u == v) continue;
vis[bian[i].start].push_back(bian[i].to);
vis[bian[i].to].push_back(bian[i].start);
f[u] = v;
total++;
if (total == n - 1) break;
}
}
void dfs(int q, int mx, int from) {
if (q == t) {
ans = mx;
return;
}
if (ans != 0) {
return;
}
while (!vis[q].empty()) {
int v = vis[q].back();
if (v != from) {
for (int j = 1; j <= m; j++) {
if ((bian[j].start == q && bian[j].to == v) || (bian[j].to == q && bian[j].start == v)) {
dfs(v, max(mx, bian[j].val), q);
break;
}
}
}
vis[q].pop_back();
}
}
int main() {
scanf("%d%d%d%d", &n, &m, &s, &t);
for (int i = 1; i <= n; i++) f[i] = i;
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &bian[i].start, &bian[i].to, &bian[i].val);
}
sort(bian + 1, bian + m + 1);
kruskal();
dfs(s, -1, s);
printf("%lld", ans);
}
H P1144 最短路计数
题目大意:
给出一个N个顶点M条边的无向无权图,顶点编号为1到N。问从顶点1开始,到其他每个点的最短路有几条。
题解:
其实写个dijk就好了,如果d[e.to] > d[v] + 1那么e.to的路径数就等于v的路径数,如果d[e.to] == d[v] + 1那么e.to的路径数就要加上v的路径数。(此时已确定要进行松弛操作)
代码:
#include<bits/stdc++.h>
#define MAXV 2000010
#define INF 0x3f3f3f3f
using namespace std;
struct edge{
int to,cost;
};
int n;
vector<edge> G[MAXV];
int d[1000010];
int nums[1000010];
typedef pair<int, int> P;
const int mod = 100003;
void dijk(int s){
priority_queue<P, vector<P>, greater<P> > que;
memset(d, INF, sizeof(d));
d[s] = 0;
nums[s] = 1;
que.push(P(0, s));
while(!que.empty()){
P p = que.top();
que.pop();
int v = p.second;
if(d[v] < p.first) continue;
for(int i = 0; i < G[v].size(); i++){
edge e = G[v][i];
if(d[e.to] > d[v] + e.cost){
d[e.to] = d[v] + e.cost;
nums[e.to] = nums[v];
que.push(P(d[e.to], e.to));
} else if(d[e.to] == d[v] + e.cost){
nums[e.to] += nums[v];
nums[e.to] %= mod;
}
}
}
}
int main(){
int n,m;
scanf("%d %d", &n, &m);
for(int i = 0; i < m; i++){
int u,v;
scanf("%d%d", &u, &v);
G[u].push_back({v,1});
G[v].push_back({u,1});
}
dijk(1);
for(int i = 1; i <= n; i++){
printf("%d\n", nums[i]);
}
return 0;
}
后面还有两题暂时都不会做,摆烂
叨叨几句... NOTHING