牛客训练赛40 A,C
。。。谨以此篇，纪念我的爆0(wa~~~~TT!!!)
A:
思路：想到了应该用dp做，想用数位。可是状态转移方程写不出。。。
其实简单的。。。d[i][j][k](//表示当前为第i位,最后两个是j,k)=can[l][j][k]*d[i-1][l][j],(l遍历1,49);
代码如下：
/*
*/
#define LOCAL
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#include<cmath>
#include<vector>
#include<set>
using namespace std;
#define maxn 3000000
#define inf 40000000
#define LL long long
LL d[505][50][50];//现在第i位，i位为j，i-1位为k
int can[50][50][50];//不合法为0，合法为1
int mod=1e9+7;
int main()
{
#ifdef LOCAL
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
#endif
int n,q;
scanf("%d%d",&n,&q);
int a,b,c;
int i,j,k,u;
for(i=0;i<50;i++)
for(j=0;j<50;j++)
for(k=0;k<50;k++)
can[i][j][k]=1;
LL ans=0;
while(q--)
{
scanf("%d%d%d",&a,&b,&c);
can[a][b][c]=0;
can[a][c][b]=0;
can[b][a][c]=0;
can[b][c][a]=0;
can[c][a][b]=0;
can[c][b][a]=0;
}
for(int i=1;i<=2;i++)
for(int j=1;j<50;j++)
for(int k=1;k<50;k++)
d[i][j][k]=1;
for(int i=3;i<=n;i++)
{
for(int j=1;j<50;j++)
{
for(int k=1;k<50;k++)
{
for(int l=1;l<50;l++)
{
d[i][j][k]+=can[l][j][k]*d[i-1][l][j];
//最后两位为j,k时，倒数第三位l一定要满足(l,j,k)合法，如果合法加上i-1位时，最后两位是l,j的情况
d[i][j][k]%=mod;
}
}
}
}
for(int i=1;i<50;i++)
for(int j=1;j<50;j++)
ans+=d[n][i][j],ans%=mod;
cout<< ans%mod <<endl;
return 0;
}
C:从一个点出发，到终点，要遍历每一条边，并且每条边只走一次，那么主路(从起点到终点的路径)只走一次，别的遍历路径都要走两次；也就是要让主路最长(树的直径)；
代码如下：
/*
c: 只有一条路径可以只走一次，别的都要走两次，所以选最长的路径走一次，别的走两次
ans=边权和*2-直径
*/
#define LOCAL
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#include<cmath>
#include<vector>
#include<set>
using namespace std;
#define maxn 3000000
#define inf 40000000
#define LL long long
vector<int > G[maxn];//邻接表
struct nod
{
int u,v,w;
}edge[maxn];//边
bool vis[maxn];//判断i点是否遍历过
int maxx=0;//距1点最远点
LL len;//当前长度
int len_max;
void dfs(int now)
{
int flag=0;//没有出边,即到达终点
int l=G[now].size();
for(int i=0;i<l;i++)
{
if(!vis[edge[G[now][i]].v])
{
vis[edge[G[now][i]].v]=1;
len+=edge[G[now][i]].w;
dfs(edge[G[now][i]].v);
vis[edge[G[now][i]].v]=0;
len-=edge[G[now][i]].w;
flag++;
}
}
if(flag==0)
{
if(len>len_max)
{
len_max=len;
maxx=now;
}
}
}
int main()
{
#ifdef LOCAL
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
#endif
int n,u,v,w;
LL ans=0;
cin>>n;
for(int i=0;i<n-1;i++)
{
cin>>edge[i].u>>edge[i].v>>edge[i].w;
edge[i+n].u=edge[i].v,edge[i+n].v=edge[i].u,edge[i+n].w=edge[i].w;
G[edge[i].u].push_back(i);//u的出边
G[edge[i].v].push_back(i+n);//v的出边
ans+=edge[i].w;
}
vis[1]=1;
dfs(1);
LL len1=len_max;
memset(vis,0,sizeof(vis));
vis[maxx]=1;
len=0;
len_max=0;
dfs(maxx);
LL len2=len_max;
//cout<<len1<<" "<<len2<<endl;
cout<<ans*2-len2<<endl;
return 0;
}
相关知识
报名 | 7月·越野跑训练赛-黑战：无训练，不越野！（坐标北京）
北京 | 凯乐石·VTRAIL2020跑山训练赛-香山站火热报名中！
路够野 心更亮 | 2019越野跑训练赛-香山站等你来挑战！
愤怒的牛
饥荒怎么训牛
青苹果蜗牛、五基因暴牛、除臭技术牛……这届亚宠展还挺“牛”
《饥荒》训牛相关知识讲解
宠物牛铃厂家
饥荒宠物牛
法牛个人领养 家养纯种法牛 奶油色黑色蓝色法牛 宠物狗 疫苗驱虫已做
网址: 牛客训练赛40 A,C https://m.mcbbbk.com/newsview180157.html
| 上一篇: 国内宠物电子设备市场尚处于空白， |
下一篇: 部队训练通用地桩网 |
