注：未登录正睿OI账号则看不了题目。
day 4
A
难度：蓝-紫
考虑贪心。
考虑优先选当前能连到了最小的点，但是这样会被样例卡疯。
考虑加一点策略。首先，若当前选到的点权大于其儿子的点权，那肯定把儿子也选上了，不然就不优了。
然后树上就会出现一些团。现在假设一个点下面连着两个团，考虑优先选那个团。
假设一个团A有两个点，点权为\((a_1,a_2)\);还有一个团B有三个点，点权为\((b_1,b_2,b_3)\)。
先选A再选B，结果为\(x_1=a_1*i+a_2*(i+1)+b_1*(i+2)+b_2*(i+3)+b_3*(i+4)\)。
先选B再选A，结果为\(x_2=b_1*i+b_2*(i+1)+b_3*(i+2)+a_1*(i+3)+a_2*(i+4)\)。
若\(x_1>x_2\)，则有\(3(a_1+a_2)<2(b_1+b_2+b_3)\)。
推广一下，若A有 \(s_1\) 个点，点权和为 \(m_1\)；B有 \(s_2\) 个点，点权和为 \(m_2\)；则比较 \(s_1*m_2\) 和 \(s_2*m_1\) 的大小来判断优劣。
合并用并查集维护一下，就做完了。
时间复杂度约 \(O(kn\log n)\)
#include<bits/stdc++.h>
#define ll long long
#define mxn 30010
#define pii pair<int,int>
#define mp make_pair
using namespace std;
ll n,val[mxn],rot[mxn];
ll fath[mxn],ans,f[mxn];
vector<int> t[mxn];
struct node{
ll num,val,sum,sze;
};
bool operator <(const node& a,const node& b){
return a.sum*b.sze>b.sum*a.sze;
}
bool operator >(const node& a,const node& b){
return b<a;
}
bool operator !=(const node& a,const node& b){
return (b.sum!=a.sum||b.val!=a.val||b.num!=a.num||b.sze!=a.sze);
}
priority_queue<node> q;
node tre[mxn];
fath[u]=f;
for(int i=0;i<t[u].size();i++){
int v=t[u][i];
if(v==f)continue;
dfs(v,u);
}
return;
}
ll fnd(ll x){
if(x==f[x])return x;
return f[x]=fnd(f[x]);
}
void joinn(ll x,ll y){
ll fx=fnd(x),fy=fnd(y);
f[fx]=fy;
return;
}
ll solve(int rt){
memset(fath,0,sizeof(fath));
dfs(rt,0);
while(q.size())q.pop();
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=n;i++)tre[i]=(node){i,val[i],val[i],1};
for(int i=1;i<=n;i++)q.push((node){i,val[i],val[i],1});//num,val,sum,sze
while(!q.empty()){
node u=q.top();
q.pop();
if(u!=tre[u.num]||u.num==rt)continue;
ll fa=fnd(fath[u.num]);
joinn(u.num,fa);
tre[fa].sum+=u.sum;
tre[fa].val+=u.val+u.sum*tre[fa].sze;
tre[fa].sze+=u.sze;
q.push(tre[fa]);
}
return tre[rt].val;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
t[u].push_back(v);
t[v].push_back(u);
}
for(int i=1;i<=n;i++)cin>>val[i]>>rot[i];
for(int i=1;i<=n;i++)
if(rot[i])
ans=max(ans,solve(i));
cout<<ans;
return 0;
}
B
难度：黄-绿
傻逼数学题。
\(p<q\) 时直接输出 \(-1\)；
\(p=q\) 时特判 \(1\)，然后输出。
\(p>q\) 时考虑二分。
计算 \(0\sim mid\) 里不同非负整数的数量 \(x\)。这里有一个式子：\(x=\lceil \frac{(mid+1)q}{p}\rceil-1\)，可以手推一下。
然后+1-1这种细节记得处理一下。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll T,p,q,k;
int main(){
cin>>T;
while(T--){
cin>>p>>q>>k;
if(p<q)cout<<-1<<endl;
else if(p==q){
if(k>1)cout<<-1<<endl;
else cout<<0<<endl;
}
else{
ll l=0,r=1e15;
while(l<r){
ll mid=(l+r)>>1;
ll cnt=((mid+1)*q-1)/p;
if(mid+1-cnt>=k)r=mid;
else l=mid+1;
}
cout<<r<<endl;
}
}
return 0;
}
C
难度：黄
弱智找规律题。
容易发现 \(>k\) 时方案数为 \((n-k)^{n-k}\)。\(\leq k\) 时暴搜记录就行了，方案数为 \(k^{k-1}\)。
还有一点要注意的是底数记得先取模。
#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;
ll n,k,di,mi;
ll quickpow(ll a,ll x){
ll ret=1,base=a;
while(x){
if(x&1==1)ret=base*ret%mod;
base=base*base%mod;
x>>=1;
}
return ret;
}
int main(){
cin>>n>>k;
di=(n-k)%mod;
cout<<quickpow(di,n-k)*quickpow(k,(k-1))%mod;
return 0;
}
D
难度：蓝-紫
傻逼阅读理解题，内含OI特色长难句和谜语人题面。
题面翻译：给出一个长度为 \(m\) 的序列 \(a\)，请你求出有多少种 \(1...n\) 的排列 \(S\)，满足 \(a\) 是它的唯一最长上升子序列。
考虑状压dp。
对于每一位，有三种状态：不在排列 \(S\) 中；在排列 \(S\) 中且不在排列 \(a\) 中；在排列 \(S\) 中且在排列 \(a\) 中。搞三进制状压dp即可。
#include<bits/stdc++.h>//状压dp
#define ll long long
#define mxn3 14350000
#define mxn2 33000
using namespace std;
ll n,k,a[20],dp[mxn3];
ll mi[20],poww=1,ans;
bool vis[mxn2][20];
void init(){
cin>>n>>k;
for(int i=1;i<=k;i++){
cin>>a[i];
a[i]--;
}
mi[0]=1;
for(int i=1;i<=n;i++)
mi[i]=mi[i-1]*3,poww=poww*3;
for(int i=0;i<(1<<n);i++){
for(int j=0;j<n;j++){
vis[i][j]=!((i>>j)&1);
//如果第i状态不包含j则为1
//意味着可以插数进去
int pos=0;
for(int l=1;l<=k;l++)
if(a[l]==j)
pos=l;//找到序列中值为j的位置记作pos
for(int l=1;l<pos;l++)
if(!((i>>a[l])&1))
vis[i][j]=0;
//若该状态不包含a_1~a_pos-1中的所有数，则不能插下一个数(j)
}
}
return;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
init();
dp[0]=1;
for(int i=0;i<poww;i++){
if(!dp[i])continue;
ll s=0,l=0,state=i,ok[20]={0},cnt=-1;
//三进制记录状态,若为0则不在S中,若为2则只在S中,若为1则既在S中又在S1中
for(int j=0;j<n;j++){
if(state%3){//三进制记录每一种状态
s|=(1<<j);
if(state%3==1)ok[++cnt]=j;
//id记录哪一位插过S1中的数
}
state/=3;
}
if(cnt>=k)continue;
//大于等于k直接退了
ok[cnt+1]=n+1;
for(int j=0;j<n;j++){
if(vis[s][j]==0)continue;
//如果第j位能插数
while(l<=cnt&&j>ok[l])l++;//找到下一个能插的数
int nxt=i+mi[ok[l]]+mi[j];//x[l]移掉j插上
dp[nxt]+=dp[i];
}
if(s==(1<<n)-1&&cnt==k-1)ans+=dp[i];
//若S为给定序列,且cnt长为|a|
}
cout<<ans<<'\n';
return 0;
}