P7831[CCO2021] Travelling Merchant 题解
考虑出度为0的点显然不行
随后，进行一个类似于拓扑排序的过程即可
注意到需要建反图
原图也得保留
注意判-1
代码：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
struct edge{
int a,b,r,p,id;
edge(int a = 0,int b = 0,int r = 0,int p = 0,int id = 0):a(a),b(b),r(r),p(p),id(id){}
bool operator<(edge o) {
return r > o.r;
}
}E1[200010];
int ans[200010],vis[200010],out[200010],n,m,cnt;
vector<pair<pair<int,int>,pair<int,int> > > E[200010];
queue<int> q;
int main()
{
cin >> n >> m;
for(int i = 1;i <= m;i++) {
cin >> E1[i].a >> E1[i].b >> E1[i].r >> E1[i].p;
E1[i].id = i;
E[E1[i].b].push_back({{E1[i].a,E1[i].id},{E1[i].r,E1[i].p}});
out[E1[i].a]++;
}
for(int i = 1;i <= n;i++) {
if(!out[i]) q.push(i);
}
sort(E1 + 1,E1 + m + 1);
memset(ans,0x3f,sizeof(ans));
for(int i = 1;i <= m;i++) {
while(!q.empty()) {
int u = q.front();
q.pop();
//cout << u << " ";
for(auto j:E[u]) {
int v = j.first.first,id = j.first.second,r = j.second.first,p = j.second.second;
if(vis[id]) continue;
if(ans[u] != 0x3f3f3f3f) ans[v] = min(ans[v],max(r,ans[u] - p));
vis[id] = true;
out[v]--;
if(!out[v]) {
q.push(v);
}
//cout << v << " ";
}
}
if(!vis[E1[i].id]) {
vis[E1[i].id] = true;
ans[E1[i].a] = min(ans[E1[i].a],E1[i].r);
out[E1[i].a]--;
if(!out[E1[i].a]) q.push(E1[i].a);
}
}
for(int i = 1;i <= n;i++) {
cout << (ans[i] == 0x3f3f3f3f ? -1 : ans[i]) << " ";
}
cout << "\n";
}
P7261[COCI2009-2010#3] PATULJCI 题解
首先对每个颜色开一个vector<int>保存其位置，随后对于一段区间\([l,r]\)和一个颜色\(c\)，可以很快速的求出\([l,r]\)内\(c\)出现的次数。
然后进行随机化，每次随机一个元素并查看他的出现次数。
若随机\(t\)次，那么随机不到的概率是\(\frac{1}{2 ^ t}\)，当\(t\)取50时约等于\(10 ^ {-15}\)，可以认为几乎不可能。
代码：
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int t = 50;
int a1[300010],n,c,m,a,b;
vector<int> E[30010];
int query(int l,int r) {
for(int i = 1;i <= t;i++) {
int p = l + rand() % (r - l + 1);
int res = upper_bound(E[a1[p]].begin(),E[a1[p]].end(),r) - lower_bound(E[a1[p]].begin(),E[a1[p]].end(),l);
if(res > (r - l + 1) / 2) {
return a1[p];
}
}
return -1;
}
int main()
{
cin >> n >> c;
for(int i = 1;i <= n;i++) {
cin >> a1[i];
E[a1[i]].push_back(i);
}
for(int i = 1;i <= c;i++) {
E[i].push_back(n + 1);
}
cin >> m;
for(int i = 1;i <= m;i++) {
cin >> a >> b;
int ans = query(a,b);
if(~ans) cout << "yes" << " " << ans << "\n";
else cout << "no" << "\n";
}
}