RT, 即将退役的人懒得一篇篇写题解, 于是有了这个东西
CF1004E
树上选一条不超过 k 个点的链, 最小化其余点到链上点的最大距离
这个思路很有意思, 不像平时一般的树上问题, 是从叶子开始一点点贪心合并直到合得只剩一条链, 这条链就是最后的答案
用优先队列完成, 复杂度 $O(n\log n)$
- #include<set>
- #include<queue>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- const int N=200005;
- struct a{int pts,len;};
- bool operator <(a x,a y)
- {
- return x.len>y.len;
- }
- set<pair<int,int>> st[N];
- priority_queue<a> hp;
- int n,k,t1,t2,t3,siz,ans;
- int main()
- {
- scanf("%d%d",&n,&k),siz=n;
- for(int i=1;i<n;i++)
- {
- scanf("%d%d%d",&t1,&t2,&t3);
- st[t1].insert(make_pair(t2,t3));
- st[t2].insert(make_pair(t1,t3));
- }
- for(int i=1;i<=n;i++)
- if(st[i].size()==1)
- hp.push((a){i,(*st[i].begin()).second});
- while(hp.size()>2||k<siz)
- {
- a mn=hp.top(); hp.pop(),siz--,ans=mn.len;
- int p=mn.pts,nxt=(*st[p].begin()).first;
- st[nxt].erase(st[nxt].lower_bound(make_pair(p,0)));
- if(st[nxt].size()==1)
- hp.push((a){nxt,ans+(*st[nxt].begin()).second});
- }
- printf("%d",ans);
- return 0;
- }
- View Code
- CF772D
题面看题吧
感觉这题没啥意义, 因为考场不太可能想出来
这个东西可以理解为十进制下的 "与"(=.=???), 记录每个权值出现的次数, 出现的和, 出现的平方和, 搞一个十进制 FWT 来做
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- const int N=1e6+60,M=1e6,mod=1e9+7;
- int n,rd,a[N],b[N],c[N],f[N],pw2[N]; long long ans;
- void Add(int &x,int y)
- {
- x+=y;
- if(x>=mod) x-=mod;
- }
- void Trans(int *arr,int typ)
- {
- if(~typ)
- {
- for(int i=1;i<M;i*=10)
- for(int j=M-1;~j;j--)
- if(j/i%10) Add(arr[j-i],arr[j]);
- }
- else
- {
- for(int i=1;i<M;i*=10)
- for(int j=0;j<M;j++)
- if(j/i%10) Add(arr[j-i],mod-arr[j]);
- }
- }
- int main()
- {
- scanf("%d",&n),pw2[0]=1;
- for(int i=1;i<=n;i++) pw2[i]=2ll*pw2[i-1]%mod;
- for(int i=1;i<=n;i++)
- {
- scanf("%d",&rd);
- a[rd]++,Add(b[rd],rd),Add(c[rd],1ll*rd*rd%mod);
- }
- Trans(a,1),Trans(b,1),Trans(c,1);
- for(int i=0;i<M;i++)
- if(a[i]) f[i]=(a[i]==1)?c[i]:1ll*pw2[a[i]-2]*(1ll*b[i]*b[i]%mod+c[i])%mod;
- Trans(f,-1);
- for(int i=0;i<M;i++) ans^=1ll*i*f[i];
- printf("%lld",ans);
- return 0;
- }
- View Code
CF 咕德拜 2017 集合 (雾
D.New Year and Arbitrary Arrangement
据 yjc 说是 NOIP 前留的题, 然而我并不会, wsl
设 $dp[i][j]$ 表示前缀中有 i 个 a 和 j 个 ab 的期望, 在 i+j>=k 时到达边界, 用高中数学讲的 等差数列 * 等比数列 算一算
答案是 dp[1][0], 因为 dp[0][0] 在没有 a 的时候会自己转移自己
代码咕咕了
E.New Year and Entity Enumeration
来源: http://www.bubuko.com/infodetail-2997425.html