Codeforces Round #359 (Div. 1)
A. Robbers’ watch
可以先算出n-1,m-1所需的位数
如果位数和超过7，根据抽屉原理，则一定会存在相同的数字
特判一下输出 0 后，位数小等于 7 的情况暴力即可
枚举 i<n , j < m，七进制拆分一下看有没有相同数字
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
#include<map> #include<set> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define mod 998244353 #define N 100005 #define pi acos(-1) #define inf 0x7fffffff #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,ans; int a,b; int bin[20]; int cal(int n) { if(n==0)return 1; ll tot=1; for(int i=1;tot<=n;i++) { if(tot*7>n)return i; tot*=7; } } int st(int x,int d) { int s=0; for(int i=1;i<=d;i++,x/=7) { if(s&bin[x%7])return -1; s|=bin[x%7]; } return s; } int main() { bin[0]=1;for(int i=1;i<=10;i++)bin[i]=bin[i-1]*2; n=read();m=read(); n--;m--; a=cal(n);b=cal(m); if(a+b>7) { puts("0"); return 0; } for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) { int s1=st(i,a),s2=st(j,b); if(s1!=-1&&s2!=-1&&(s1&s2)==0) ans++; } printf("%d\n",ans); return 0; } |
B. Kay and Snowflake
题意是询问一棵树某些子树的重心
树的重心定义为，删去这个结点后，剩下的连通块大小不超过1/2*（总结点数）
用yi表示x结点的儿子
预处理size[x]和mx[x]表示树的大小，yi树的最大结点数，用于判断一个结点是不是重心
根据性质，x的重心应该在yi的重心之间的路径上
转移的时候只要把每个树yi的重心到x的路径从下往上暴力判断一下，发现重心就退出
复杂度相当于从每个叶子走向根，也就是遍历一棵树，显然是O（n）的
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
#include<map> #include<set> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define mod 998244353 #define N 100005 #define pi acos(-1) #define inf 0x7fffffff #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m; int size[300005],mx[300005]; int ans[300005],fa[300005]; vector<int> e[300005]; void dfs(int x) { size[x]=1; for(int i=0;i<e[x].size();i++) { dfs(e[x][i]); size[x]+=size[e[x][i]]; mx[x]=max(mx[x],size[e[x][i]]); } } void dp(int x) { if(!e[x].size())ans[x]=x; for(int i=0;i<e[x].size();i++) { int y=e[x][i]; dp(y); int t=ans[y]; while(1) { if(max(mx[t],size[x]-size[t])<=size[x]/2) { ans[x]=t; break; } if(t==x)break; t=fa[t]; } } } int main() { n=read();m=read(); for(int i=2;i<=n;i++) { int x=read(); fa[i]=x; e[x].push_back(i); } dfs(1); dp(1); for(int i=1;i<=m;i++) { int x=read(); printf("%d\n",ans[x]); } return 0; } |
计数器 9774736
OI 课件=>
OI 课件=>
B题复杂度应该是Σ(每个叶子到整棵树的重心的距离)
能不能证明这是O(n)的
并不是这样的，每个结点从它儿子的重心开始往上找，也就是说重心移动不会重复走一条边
懂了，每个点的儿子中，只有重儿子会有代价，其他儿子无关
相当于树链剖分一样分成很多条链，重心最多经过链上每条边一次