Comet OJ - Contest #5

秒速五厘米 2021-11-01 10:56 239阅读 0赞

# Comet OJ - Contest \#5 #

总有一天,我会拿掉给\\(dyj\\)的小裙子的.

### A ###

显然

#### \\(ans = min(cnt\_1/3,cnt\_4/2,cnt5)\\) ####

### B ###

我们可以感性理解一下,最大的满足条件的\\(x\\)不会太大

因为当\\(x\\)越来越大时\\(f(x)\\)的增长速度比\\(x\\)的增长速度慢得多

其实可以证明,最大的满足的\\(x\\)不会超过\\(100\\)

因为没有任何一个三位数的各位之和大于等于\\(50\\)

所以我们就直接预处理\\(1-99\\)所有的合法的

暴力枚举即可

其实赛后题解说满足条件的\\(x\\)只有\\(17\\)和\\(18\\)

#include<cstdio> #include<cstring> #include<cctype> #include<iostream> #include<algorithm> using namespace std; //int a[N]; bool book[32131]; long long n; inline int work(int x){ int ans = 0; while(x){ ans += x % 10; x /= 10; } return ans; } int main(){ int T; for(int i = 2;i <= 100;++i){ if(work(i) == i / 2) book[i] = 1; } cin >> T; while(T--){ int res = 0; scanf("%lld",&n); for(int i = 2;i <= 100;++i) if(book[i] == 1 && n % i == 0) res++; printf("%d\n",res); } return 0; }

### C ###

一棵根为\\(1\\)的树,我们要给每个点染色,\\(a\_i\\)表示在第\\(i\\)的点染色前,所有深度大于\\(a\_i\\)的点都不能有颜色,求字典序最小的染色顺序.\\((n <=5\*10^5)\\)

保证\\(a\_i>=deep\_i\\)

我们抽象一下,发现你直接将所有的同深度的点看成一个,直接线段树优化建图跑\\(DAG\\)即可.但是我不会线段树优化建图

我们试想一下,将同深度的点看成一个点,跑\\(DAG\\)的大体思路是没有错的.问题就是如果不能线段树优化建图,就非常难做.因为我们不知道那个点的入度为\\(0\\)

之后发现,我们可以开树状数组维护每个点的度数,区间修改,单点查询.

我们发现,每次加入的点的深度一定是递增的.

因为如果\\(i\\)对\\(j\\)有限制,\\(i\\)对\\(j + 1\\)也一定有限制

之后我们可以维护一个指针,每次入队时查询当前深度是否入度为\\(0\\)

另外由于要求字典序最小,所以要用小根堆.

时间复杂度\\(O(nlogn)\\)

#include<cstdio> #include<cctype> #include<algorithm> #include<iostream> #include<cstring> #include<vector> #include<queue> using namespace std; const int N = 5e5 + 3; vector <int> G[N]; vector <int> g[N]; int deep[N]; int n,maxdeep; bool vis[N]; int fa[N]; int a[N]; //inline struct BIT{ int c[N]; inline void add(int x,int v){ for(;x <= n;x += x & -x) c[x] += v; } inline int query(int x){ int res = 0; for(;x;x -= x & -x) res += c[x]; return res; } }T; inline int read(){ int v = 0,c = 1;char ch = getchar(); while(!isdigit(ch)){ if(ch == '-') c = -1; ch = getchar(); } while(isdigit(ch)){ v = v * 10 + ch - 48; ch = getchar(); } return v * c; } inline void dfs(int x,int f,int dep){ deep[x] = dep; maxdeep = max(maxdeep,dep); fa[x] = f; for(int i = 0;i < (int)G[x].size();++i){ int y = G[x][i]; if(y == f) continue; dfs(y,x,dep + 1); } } inline void work(){ priority_queue <int,vector<int>,greater<int> > q; int now = 0; for(int i = 1;i <= n;++i) if(T.query(deep[i]) == 0) vis[i] = 1,q.push(i),now = max(now,deep[i]); now++; while(!q.empty()){ int k = q.top();q.pop(); printf("%d ",k); T.add(a[k] + 1,-1); while(now <= maxdeep && T.query(now) == 0){ for(int i = 0;i < (int)g[now].size();++i) q.push(g[now][i]); now++; } } } int main(){ n = read(); for(int i = 1;i < n;++i){ int x = read(),y = read(); G[x].push_back(y); G[y].push_back(x); } for(int i = 1;i <= n;++i) a[i] = read(); dfs(1,0,1); for(int i = 1;i <= n;++i) { T.add(a[i] + 1,1); g[deep[i]].push_back(i); } work(); return 0 ; }

转载于:https://www.cnblogs.com/wyxdrqc/p/11031656.html