第一个题
首先这个题 我没做出来
我在这里还是要总结下基环树喜欢考什么
我以前做过一个交互题 题目大意忘了
反正考的是基环树最重要的一个性质 两个点之间一定存在两个走法，一个是正常走 另一个是走环
反正就是一定有两条路过来
那这个题就是考虑这个性质
还有就是正常树的 要找到>=1的这个路径很明显 任何两个点之间都行 就是
\(C_n^2\) ,那很明显答案就是那些环上的可以*2 别的其实都是 1 ，于是我们大不了把所有人都认为是2 然后减去不是环的子树就行了 非常巧妙
我们使用tarjan求出那个环 然后对环上的每一个点进行dfs 求得子树 即可 此题是一个很有意思的题目
点击查看代码
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
//必须写题解 就是基环树的两种走法的那个知识
//写tarjan坏了一定要注意
//是不是 你h数组没有初始化或者又变成0了？（-1）的时候
using namespace std;
#define debug cout<<endl<<"----------"<<endl;
const int range=3e5+100;
int n,m,a,b;
vector<int> v[range];
int dfn[range],low[range],tot;
int stk[range],instk[range],top;
int scc[range],siz[range],cnt;
int ne[range*2];
int h[range*2];
int e[range*2];
int flag;
int idx;
void add(int a,int b)
{
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
void cclear()
{
top=0;cnt=0;idx=0;tot=0;
flag=0;
for(int i=0;i<=n;i++)h[i]=-1;
for(int i=1;i<=n;i++)
{ v[i].clear();
siz[i]=0;
instk[i]=ne[i]=e[i]=stk[i]=scc[i]=dfn[i]=low[i]=0;
}
}
void tarjan(int x,int fa)
{
dfn[x]=low[x]=++tot;
stk[++top]=x;
for(int i=h[x];i!=-1;i=ne[i])
{
int j=e[i];
if(!dfn[j]){
tarjan(j,i);
low[x]=min(low[x],low[j]);
}
else if(i!=(fa^1)){
low[x]=min(low[x],dfn[j]);
}
}
if(dfn[x]==low[x])
{
++cnt;
int y;
do{
y=stk[top--];
v[cnt].push_back(y);
scc[y]=cnt;
++siz[cnt];
}while(y!=x);
}
}
int dfs(int x,int fa)
{
int g=0;
g++;
for(int i=h[x];i!=-1;i=ne[i])
{
int j=e[i];
if(j==fa||scc[j]==flag)continue;
g+=dfs(j,x);
}
return g;
}
void solve(){
cin>>n;
cclear();
int ans=n*(n-1);
for(int i=1,x,y;i<=n;i++)
{
cin>>x>>y;
add(x,y);add(y,x);
}
for(int i=1; i<=n; i++)
if(!dfn[i]) tarjan(i,0);
for(int i=1;i<=cnt;i++)
if(siz[i]>1) {
flag=i;break;
}
for(auto i:v[flag])
{
int h=dfs(i,0);
ans-=(h*(h-1)/2);
}
cout<<ans<<endl;
cclear();
}
signed main()
{
int t;
cin>>t;
while(t--)
solve();
}
第二题
这题4月做的 重新写了一遍
是一个线性dp的好题 噢，我昨天晚上做了一个计数dp的题目 做了很久 看题解看来一个多小时还是没看懂 于是这题被我扔了
题目
回到这里
这题要怎么写？
首先得明确知道这个只好用dp去写了
如果写呢？
注意到数据1e9 可以发现最多用30把坏钥匙 再用了都是0
我们可以发现可以用二维数组记录钥匙使用数量 进行转移即可 于是朴素得写法就是dp[2e5][30]这样就行 然后转移方程式
max:
dp[i][j]=dp[i-1][j-1]+a[i]>>j
dp[i][j]=dp[i-1][j]+a[i]>>j-k
然后就可以去做了
不过这里其实还是可以优化的 进行降维 让我们回顾一下降维的原则
为什么在01背包逆序可以做到降维呢
因为j是逆序循环的
所以dp[j]会优先于dp[j-a[i]]更新
也就是说dp[j-a[i]]就相当于dp[i-1][j-a[i]
于是就相当于dp[i-1][j-a[i]+w[i]
相当于用上一行的dp[j-w[i]]去更新dp[j]
dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i]+w[i])
dp[j]=max(dp[j],dp[j-a[i]+w[i])
好好对比下就明白了
所以我们对这个题进行降维书写
然后一定要注意到 当n>30时 我们一定要多加一句
if (i >= 30)dp[i][30]
= max(dp[i - 1][30] + 0, dp[i][30]);
为什么呢 因为你会发现 他这个30如果只是在for循环更新永远不能从dp[i-1][]30]就行更新 都是29
而在后面的那个代码
dp[i - 1][j] + (a[i] >> j) - k)
它是指此刻用的好钥匙 而我们其实是想用30多把坏的呢
for(int i=1;i<=n;i++)
{int maxn=0;int flag;
for(int j=30;j>=0;j--)
{
if(j>=1)dp[j]=max(dp[j]+(a[i]>>j)-k,dp[j-1]+(a[i]>>j));
else dp[j]=dp[0]+a[i]-k;
if(dp[j]>maxn){
maxn=dp[j];
flag=j;
}
}
}
第三个题
这道题考的很好
首先需要仔细审题
如果两个圆舞可以通过选择第一个参与者转化为另一个圆舞，则两个圆舞没区别
我忽视了这句话
这句话是什么意思 就是 12 3 4 和2 1 3 4 是没区别的 我以为什么了你知道吗 我以为 12 3 4 的全排列都没区别。。。。
然后这其实是个圆排列 由于是圆 没有头区分 所以是n!/n=(n-1)!
然后这个题可以分成多少组就是
\(C_n^\frac{n}{2}\)*\(\frac{1}{2}\) 然后这个圆排列的方案是\((\frac{n}{2}-1)!^2\) 因为有两组嘛
圆排列：
有5对夫妻参加一场婚礼，他们被安排在一张10个座位的圆桌就餐，
但是操办者不知道他们之间的关系，随机安排座位，问5对夫妻恰好相邻而坐的概率是多少?
要研究圆桌排列，就必须知道它和直线排列组合的区别，
举个例子，5个人排成一排有多少种方式?同学们都知道A(5,5)=5!,但是当5个人坐成一圈时，
有多少种方式?很多同学会陷入死胡同，
其实两个题目关键区别在于直线排列时排列之前相对位置已经被确定，
但是圆桌问题时每个位置都不确定，但是这种题目我们只需要先找寻任意一人A坐下，
其余人相对位置也就确定了，
比如我们可以说一个在A左面，或者是A对 面等等，所以当5个人坐成一圈时， 有A(4,4)=4!
以上来源于百度文库
没有队头区分
这个题我没想到是DP
你会发现很多题 我都想不到是dp
因为我不会dp
再者是这道题真的很难 四维背包dp
这个数据很小的 应该考虑dp的
好了 让我们来思考下做法吧
首先看到一般元素我们可以思考到其中一维应该表示选取元素 在看到是倍数 想到取模对吧！
于是这个四维就诞生了
这道题真的很有意思 你会发现这种不同层之间有关联的 如何进行转移呢
官方代码给了一个很有创意的办法
下面一起讲到
我们假设第三维是选取的个数c
第四维是余数r
然后考虑转移公式
我们思考下对于i,j他来源于前一个i，j-1对吧
那么它可以怎么转移呢
第一种可能 我们可以不选
\(a_{i,j}\)这个元素 那么
转移中可以这样写
dp[i][j][c][r]=dp[i][j-1][c][r]
但是一定要注意了 对于dp[i][j][c][r]而言 他不仅仅是只由dp[i][j-1][c][r]转移过来的 比如说此时的c是2表示选了两个元素
那我们由j-1的选了2个的元素转过来了 也可以是j-1-1-1的选了两个元素转移过来 当然了这里都是一样的
所以这里是要取max处理的
我当时这里琢磨了半天
我是对代码每一个细节都不许放过的！
然后我们再思考 如果要用这个元素的
话
我们该怎么推导这个状态转移方程呢
很明显一旦选取了元素 那么注定会导致余数的改变
int t=r+\(a_{i,j}\)%k
转移方程应该是这样的
我们该思考转移前这二者的关系
dp[i][j][c+1][t]
dp[i][j-1][c][r]+\(a_{i,j}\)
对吧
很明显 我如果选了这个元素他太是这个转移过来的
然后大家肯定会想到 我们是取max的
为什么呢 而不是直接等于他呢
因为dp[i][j-1][c+1][t]可能也很大 我们还是要做一个对比的 如果很大的话就取他了
然后我们可以得出（就在我写这话的时候我还是错误的理解，突然开窍了，也可以看出我做这个题也不是全懂的 这也是写题解的好处）
这个c是表示整行的选取！表示本行已经选取了c个元素了，不是这个人做第c个选取（这个人做第c个的结尾）的意思，我之前一直这么认为！
那么我们总结得出
dp[i][j][c+1][t]=max(dp[i][j-1][c][r]+\(a_{i,j}\),dp[i][j-1][c+1][t])
写错了 知道哪里吗
dp[i][j-1][c+1][t]
这里错了 为什么？
我们是说来到j的时候表示现在取了c个 但是你能不能保证之前的j-1没有取到c+1个吗 并且余数还不等于t？对吧
然后供上我的错解
我是这么随便的认为可能
整个for循环0-k-1
+\(a_{i,j}\)会导致余数重复为某个值了 实际上是不会的
\(a_{i,j}\)+x=t 那这个t是不会说
会重复的
简单证明下
(0+x)%k
(1+x)%k
....
会重复吗？不会 只是所有人都+了个x%k而已 你可以理解为整体右移动！
所以说我的理解是站不住脚的
所以这里是
dp[i][j][c+1][t]=max(dp[i][j-1][c][r]+\(a_{i,j}\),dp[i][j][c+1][t]
你以为就结束了吗？
不是的
终于写完了----单行的情况了