有用的题型！
The 2021 ICPC Asia Shanghai Regional Programming Contest
https://codeforces.com/gym/103446/problem/H
//kruskal重构树！
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+9;
typedef long long ll;
int n,m,q,node;
int w[N],p[N],fa[N][22],deep[N];
ll sum[N],maxNum[N][22];
vector<int> to[N];
struct E {
int a,b,c;
bool operator < (const E &O) const {
return c < O.c;
}
}e[N];
int find(int x) {
if(x != p[x]) return p[x] = find(p[x]);
return x;
}
void Merge(int x,int y,int z) {
int px = find(x),py = find(y),pz = find(z);
p[px] = pz;
p[py] = pz;
}
void dfs(int u,int father) {
if(u <= n) sum[u] = w[u];
deep[u] = deep[father] + 1; //预处理倍增及sum的值！
for(int i=1; (1 << i) <= deep[u]; i++) {
fa[u][i] = fa[fa[u][i-1]][i-1];
}
for(auto v : to[u]) {
if(v == father) continue;
fa[v][0] = u;
dfs(v,u);
sum[u] += sum[v];
}
}
void dfs2(int u,int father) {
maxNum[u][0] = w[fa[u][0]] - sum[u]; //预处理u开始的2的i次幂的maxNum，maxNum为最大的障碍！
for(int i=1; (1 << i) <= deep[u]; i++) {
maxNum[u][i] = max(maxNum[u][i - 1], maxNum[fa[u][i - 1]][i - 1]);
}
for(auto v : to[u]) {
if(v == father) continue;
dfs2(v,u);
}
}
ll query(int x,int k) {
for(int i = 19; i >= 0; --i)
if(fa[x][i] && maxNum[x][i] <= k)
x = fa[x][i];
return sum[x] + k;
}
int main() {
cin >> n >> m >> q;
for(int i=1; i<=n; i++) scanf("%d",&w[i]);
for(int i=1; i<N; i++) p[i] = i;
for(int i=1; i<=m; i++) scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].c);
sort(e+1,e+m+1);
node = n;
for(int i=1; i<=m; i++) {
int a = e[i].a,b = e[i].b,c = e[i].c;
int px = find(a),py = find(b);
if(px != py) {
node++;
w[node] = c;
to[node].push_back(px);
to[px].push_back(node);
to[py].push_back(node);
to[node].push_back(py);
Merge(px,py,node);
}
}
dfs(node,0);
dfs2(node,0);
while(q--) {
int x,k;
scanf("%d%d",&x,&k);
printf("%lld\n",query(x,k));
}
return 0;
}
2019 China Collegiate Programming Contest Qinhuangdao Onsite
https://codeforces.com/gym/102361/problem/F
DFS有向图找环
#include <iostream>
#include <vector>
using namespace std;
const int N = 2e6 + 9;
typedef long long ll;
vector<int> to[N];
const int MOD = 998244353;
int vis[N];
int n, m;
int Size[N], tot, h[N];
void dfs(int u, int father)
{
vis[u] = 1;
h[u] = h[father] + 1;
for (auto v : to[u])
{
if (!vis[v])
dfs(v, u);
else if (vis[v] == 1 && v != father)
{
Size[++tot] = h[u] - h[v] + 1;
}
}
vis[u] = 2;
}
ll fpow(ll a, ll b, ll c)
{
ll ans = 1;
b %= c;
while (b)
{
if (b & 1)
ans = ans * a % c;
a = a * a % c;
b >>= 1;
}
return ans;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int a, b;
scanf("%d%d", &a, &b);
to[a].push_back(b);
to[b].push_back(a);
}
for (int i = 1; i <= n; i++)
{
if (!vis[i])
dfs(i, 0);
}
ll ans = 1;
for (int i = 1; i <= tot; i++)
{
ans = ans * (fpow(2, Size[i], MOD) - 1) % MOD;
m -= Size[i];
}
ans = ans * fpow(2, m, MOD) % MOD;
cout << ans << endl;
return 0;
}
2019 China Collegiate Programming Contest Qinhuangdao Onsite
https://codeforces.com/gym/103409/problem/E
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4+9;
typedef pair<int,int> PII;
typedef long long ll;
int n,m,c;
int head[N],numE,dist[N];
bool st[N];
struct E {
int next,to,w;
}e[N];
void add(int a,int b,int c) {
e[numE] = {head[a],b,c};
head[a] = numE++;
}
bool Dijkstra(int start) {
priority_queue<PII,vector<PII>,greater<PII>> qu;
for(int i=1; i<=n; i++) dist[i] = 0x3f3f3f3f,st[i] = false;
dist[start] = 0;
qu.push({0,start});
while(!qu.empty()) {
auto t = qu.top();
qu.pop();
int ver = t.second;
if(st[ver]) continue;
st[ver] = true;
for(int i=head[ver]; ~i; i=e[i].next) {
int v = e[i].to;
if(v == start && dist[ver] + e[i].w <= c) return true;
if(dist[v] > dist[ver] + e[i].w) {
dist[v] = dist[ver] + e[i].w;
qu.push({dist[v],v});
}
}
}
return false;
}
int main() {
memset(head,-1,sizeof head);
cin >> n >> m >> c;
int minn = 2e9;
for(int i=1; i<=m; i++) {
int a,b,c;
cin >> a >> b >> c;
add(a,b,c);
minn = min(minn,c);
}
if(c < minn) puts("0");
else {
int ans = 1;
for(int i=1; i<=n; i++) {
if(Dijkstra(i)) ans = 2;
}
cout<<ans<<endl;
}
return 0;
}
P1525 [NOIP2010 提高组] 关押罪犯
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+9;
int n,m;
int p[N],vis[N];
struct E {
int a,b,c;
bool operator < (const E &O) const {
return c > O.c;
}
}e[N];
int find(int x) {
if(x != p[x]) return p[x] = find(p[x]);
return x;
}
void Merge(int x,int y) {
int px = find(x),py = find(y);
if(px != py) p[px] = py;
}
int main() {
cin >> n >> m;
for(int i=0; i<=n; i++) p[i] = i;
for(int i=1; i<=m; i++) {
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
e[i] = {a,b,c};
}
sort(e+1,e+m+1);
int ans = 0;
for(int i=1; i<=m; i++) {
int a = e[i].a,b = e[i].b,c = e[i].c;
int px = find(a),py = find(b);
if(px == py) {
ans = c;
break;
} else {
if(!vis[a]) vis[a] = b;
else {
Merge(vis[a],b);
}
if(!vis[b]) vis[b] = a;
else {
Merge(vis[b],a);
}
}
}
cout<<ans<<endl;
return 0;
}
逆十字代码%%%%！
https://ac.nowcoder.com/acm/contest/24577/M
#include<bits/stdc++.h>
using namespace std;
const int N = 5005;
int nd,ans;
int n,m;
struct node {
map<string,int> mp;
int s0,s1;
void clear() {
s0 = 0,s1 = 0;
mp.clear();
}
int get_id(string s) {
if(mp.count(s)) return mp[s];
return mp[s] = ++nd;
}
}t[N];
void insert(int v) {
int p = 1;
char ss[N];
string s = "";
scanf("%s",ss+1);
for(int i=1; ss[i]; i++) {
if(ss[i] != '/') s += ss[i];
else {
p = t[p].get_id(s);
s = "";
}
}
p = t[p].get_id(s);
v == 1 ? t[p].s1++:t[p].s0++;
}
void dfs(int u) {
for(auto v : t[u].mp) {
int x = v.second;
dfs(x);
t[u].s1 += t[x].s1;
t[u].s0 += t[x].s0;
}
if(u == 1) return;
if(t[u].s1 && !t[u].s0) {
ans++;
for(auto v : t[u].mp) {
--ans;
}
}
}
int main() {
int _;
cin >> _;
while(_--) {
for(;nd;--nd) t[nd].clear();
nd = 1;
ans = 0;
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++) insert(1);
for(int i=1; i<=m; i++) insert(0);
dfs(1);
cout<<ans<<"\n";
}
return 0;
}
//https://codeforces.com/gym/102900/problem/D
#include <iostream>
using namespace std;
typedef long double LD;
int main()
{
int _;
scanf("%d", &_);
while (_--)
{
LD n, p1, v1, p2, v2;
scanf("%LF%LF%LF%LF%LF", &n, &p1, &v1, &p2, &v2);
if (p1 > p2) //保证第一个人再前面！
{
swap(p1, p2);
swap(v1, v2);
}
LD ans = 0;
ans = min((n + min(p1, n - p1)) / v1, (n + min(p2, n - p2)) / v2); //较快的那个自己跑完全程的人的时间！
ans = min(ans, max((n - p1) / v1, p2 / v2)); //两个各自到对面的终点的最大值！
LD l = p1, r = p2; // 应该既可以二分也可以三分mid！ 左边那个人跑完(0 ~ mid),右边跑完(mid,n);
while (r - l >= 1e-10)
{
LD mid = (l + r) / 2;
LD t1 = (p1 + (mid - p1) * 2) / v1;
t1 = min(t1, (2 * p1 + mid - p1) / v1);
LD t2 = (2 * (p2 - mid) + n - p2) / v2;
t2 = min(t2, ((n - p2) * 2 + p2 - mid) / v2);
ans = min(ans, max(t1, t2));
if (t1 > t2) //如果左边人花费的时间长，那就让他少跑一段距离，所有r = mid！
r = mid;
else
l = mid;
}
printf("%.10LF\n", ans);
}
return 0;
}
//三分版本!
#include <iostream>
using namespace std;
typedef long double LD;
int main()
{
int _;
scanf("%d", &_);
while (_--)
{
LD n, p1, v1, p2, v2;
scanf("%LF%LF%LF%LF%LF", &n, &p1, &v1, &p2, &v2);
if (p1 > p2) //保证第一个人再前面！
{
swap(p1, p2);
swap(v1, v2);
}
LD ans = 0;
ans = min((n + min(p1, n - p1)) / v1, (n + min(p2, n - p2)) / v2); //较快的那个自己跑完全程的人的时间！
ans = min(ans, max((n - p1) / v1, p2 / v2)); //两个各自到对面的终点的最大值！
LD l = p1, r = p2; // 应该既可以二分也可以三分mid！ 左边那个人跑完(0 ~ mid),右边跑完(mid,n);
while (r - l >= 1e-10)
{
LD lmid = l + (r - l) / 3,rmid = r - (r - l) / 3;
LD ltime,rtime;
LD t1 = (p1 + (lmid - p1) * 2) / v1;
t1 = min(t1, (2 * p1 + lmid - p1) / v1);
LD t2 = (2 * (p2 - lmid) + n - p2) / v2;
t2 = min(t2, ((n - p2) * 2 + p2 - lmid) / v2);
ltime = max(t1,t2);
/*************************/
t1 = (p1 + (rmid - p1) * 2) / v1;
t1 = min(t1, (2 * p1 + rmid - p1) / v1);
t2 = (2 * (p2 - rmid) + n - p2) / v2;
t2 = min(t2, ((n - p2) * 2 + p2 - rmid) / v2);
rtime = max(t1,t2);
ans = min(ans,min(ltime,rtime));
if(ltime > rtime) l = lmid;
else r = rmid;
}
printf("%.10LF\n", ans);
}
return 0;
}
https://codeforces.com/gym/104059/problem/C
考察STL二分！
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e6+9;
typedef long long ll;
typedef pair<int,int> PII;
unordered_map<int,int> mp;
set<int> st;
int a[N];
int main() {
int n,q;
cin >> n >> q;
for(int Case=1; Case<=q; Case++) {
char s[2];
scanf("%s",s);
if(s[0] == '+') {
int a;
scanf("%d",&a);
st.erase(a);
} else if(s[0] == '-') {
int a;
scanf("%d",&a);
st.insert(a);
} else {
int a,b;
scanf("%d%d",&a,&b);
if(a > b) swap(a,b);
bool ok = true;
if(st.size() > 0) {
if(st.count(a) || st.count(b)) ok = false;
else if(*st.begin() < a) {
auto p = st.upper_bound(a);
if(p != st.end() && *p < b) ok = false;
}
else if(*st.begin() > a && *st.begin() < b) {
auto p = st.upper_bound(b);
if(p != st.end() && *p > b) ok = false;
}
}
if(!ok) cout<<"impossible\n";
else cout<<"possible\n";
}
}
return 0;
}
https://codeforces.com/contest/1760/problem/D
//双指针当然也可以unique函数去重！
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6+9;
int a[N];
int n;
bool check(int l,int r) {
if(l > 1 && r < n) {
if(a[l-1] > a[l] && a[r] < a[r+1]) return true;
return false;
} else {
if(l == 1 && r == n) return true;
else if(l == 1) {
if(a[r] < a[r+1]) return true;
return false;
} else {
if(a[l-1] > a[l]) return true;
return false;
}
}
}
int main() {
int _;
scanf("%d",&_);
while(_--) {
scanf("%d",&n);
for(int i=1; i<=n; i++) scanf("%d",&a[i]);
int cnt = 0;
for(int i=1; i<=n; i++) {
int j = i;
while(j <= n && a[j] == a[i]) j++; //j出来后是不满足条件的第一个！
if(check(i,j-1)) {
cnt++;
}
i = j-1; //i在此之后还得自增;
}
if(cnt == 1) puts("YES");
else puts("NO");
}
return 0;
}
京公网安备 11010502036488号