今天题目还好,这两天的体验比以前好了不少,可能是因为讲师团察觉到我们很菜了吧,A、C两题做的比较快,H题想的有点多,div2版本其实直接建树就可以了,结果想到div1的方法去了,这我绝对百分之百想不出来啊,还好最后试了一发,侥幸过了。
A Cactus Draw
div1:仙人掌,把仙人掌中的环横着放。
div2:一棵树,快乐的一匹。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=100005;
ll a;
int main()
{
ios::sync_with_stdio(false);
int n,k;
cin>>n>>k;
int num=0;
priority_queue<ll> Q;
for(int i=1;i<=n;i++)
{
cin>>a;
num+=log(a)+1;
Q.push(a);
}
if(k>num){cout<<'0'<<endl;return 0;}
for(int i=1;i<=k;i++)
{
a=Q.top();
Q.pop();
a/=2;
Q.push(a);
}
ll ans=0;
while(!Q.empty())
{
ans+=Q.top();
Q.pop();
}
cout<<ans<<endl;
}
B Diameter
unsolved
C Division
div1:主席树,各凭本事卡内存。(完全听不懂)
div2:又是快乐的一匹。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a;
int main()
{
ios::sync_with_stdio(false);
int n,k;
cin>>n>>k;
int num=0;
priority_queue<ll> Q;
for(int i=1;i<=n;i++)
{
cin>>a;
num+=log(a)+1;
Q.push(a);
}
if(k>num){cout<<'0'<<endl;return 0;}
for(int i=1;i<=k;i++)
{
a=Q.top();
Q.pop();
a/=2;
Q.push(a);
}
ll ans=0;
while(!Q.empty())
{
ans+=Q.top();
Q.pop();
}
cout<<ans<<endl;
}
D Doppelblock
爆搜+剪枝
剪枝:
- 数不重复。
- 两个X之外的和不超过数的总和减线索值,两个X之内的和不超过线索。
- 两个X之间能放的数字个数被线索值限制。
E Fast Kronecker Transform
暴力
求一个奇怪的卷积。
FFT
F Kropki
与汉密尔顿路径的状压dp相似。
考虑容斥,
dp[]
40的无序拆分大约30000左右,50大约200000左右。
G Least Common Multiple
unsolved
H Nested Tree
div1:
- 把所有树串串起来之后,某些边的两端的大小会变。
- 我们可以⽤用虚树/树链剖分解决。(我又不会emmmm)
div2:可以把整个树建出来,对于⼀一条边,对答案的贡献 是两端size乘积的和(上网搜了个dfs过了)。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2000005;
const int mod=1e9+7;
int vis[N]={0};
int Next[N],head[N],ver[N],tot=0;
int n,m;
void add(int x,int y)
{
tot++;
ver[tot]=y;
Next[tot]=head[x];
head[x]=tot;
}
ll ans=0;
void dfs(ll u,ll nu){
ll num=nu;
for(ll i=head[u];i;i=Next[i]){
ll v=ver[i];
if(vis[v]) continue;
vis[v]=1;
tot++;
dfs(v,tot);
ans=(ll)(ans+((n*m-(tot-num))*(tot-num)%mod)%mod)%mod;
num=tot;
}
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n-1;i++)
{
int u,v;
cin>>u>>v;
for(int j=0;j<=m-1;j++)
{
add(u+j*n,v+j*n);
add(v+j*n,u+j*n);
}
}
for(int i=1;i<=m-1;i++)
{
int a,b,v,u;
cin>>a>>b>>u>>v;
add(u+(a-1)*n,v+(b-1)*n);
add(v+(b-1)*n,u+(a-1)*n);
}
ans=0;tot=1;vis[1]=1;
dfs(1,1);
cout<<ans%mod<<endl;
}
I Sorting
区间中大于x的数字相对位置不变,小于等于x的数字也不会变。
把<=x的数字看为0,>x的看成1。
可以通过找第几个0或1找到原来的数字。
1,维护区间里有几个0几个1。
2,区间求和就相当于搞出这是第几个0到第几个0,第几个1到第几个1,然后前缀和即可。
J Special Judge
没有公共端点就是不规范相交。
有就判断是否是一个方向。
一个方向重合则不合法。
用叉积=0,点积>0。