K - Kingdom‘s Power 贪心,E-奇环_牛客练习赛106 二分图 鸽笼原理,F-座位_概率期望,G-交换_dp​​​​​​
admin
2024-03-16 00:24:52
0

K - Kingdom's Power 贪心

一开始想的是要想路程最小,那么他一定是先去征服size最小的子树是最好的,然后就wa了,正解应该是按照深度来贪心,对于一个节点u的子节点,按照u走完子节点的步数进行排序,先从步数小的走,然后走下一个节点时看看是直接走根节点再派一个军队还是让刚才走的那个军队再来征服这个,去一个最小值即可,题解代码的实现还是挺巧的

CCPC2020秦皇岛K题K. Kingdom's Power(贪心) - 高级牛头人 - 博客园 (cnblogs.com)

#include
//#pragma-GCC-optimize("-Ofast");
#define int long long
//#define ll long long
#define lowbit(x) ((x)&(-x))
#define endl '\n'
#define pause system("pause")
using namespace std;
const int N=2e6+5;
const int mod=1e9+7;
const int inf=1e17;
const double pi=acos(-1);
int qpow(int a,int b)
{int res=1;while(b){if(b&1) res=res*a%mod;a=a*a%mod;b>>=1;}return res;
}
int getinv(int a){return qpow(a,mod-2);}
int head[N],cnt;
struct Edge
{int next,to;
}e[N];
void addedge(int from,int to)
{e[++cnt].next=head[from];e[cnt].to=to;head[from]=cnt;
}
int t,ans,n,dep[N];
struct node
{int id,dis;bool operator<(const node &a)const{return a.disq[N];
int dfs1(int u,int fa)
{dep[u]=dep[fa]+1;int res=0,maxx=0;for(int i=head[u];i;i=e[i].next){int j=e[i].to;if(j==fa) continue;res=dfs1(j,u)+1;q[u].push(node{j,res});maxx=max(maxx,res);}return maxx;
}
int dfs2(int u,int dist)
{int flag=q[u].size();while(!q[u].empty()){int v=q[u].top().id;q[u].pop();dist=dfs2(v,dist+1)+1;}if(u!=1&&flag<=0){ans+=min(dist,dep[u]);dist=0;}return dist;
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>t;int ca=0;while(t--){cin>>n;for(int i=1;i<=cnt;i++) e[i].next=e[i].to=0;for(int i=1;i<=n;i++) head[i]=0;cnt=0;for(int i=2;i<=n;i++){int u;cin>>u;addedge(u,i);addedge(i,u);}dep[0]=-1;ans=0;dfs1(1,0);dfs2(1,0);cout<<"Case #"<<++ca<<": "<

E-奇环_牛客练习赛106 二分图 鸽笼原理

二分图是没有奇数环的,所以可以把图看作是一个二分图,左边有n1个点,右边有n2个点,那么不存在奇数环的情况下最多有n1*n2条边,可以列出一些式子

n1+n2=n

\frac{n(n-1)}{2}-m<=n1*n2

通过基本不等式可以得出\frac{n^2}{4}-\frac{n}{2}<=m,m最大是2e5,可以得出n<=896,当n大于896或者

\frac{n^2}{4}-\frac{n}{2}>m时是一定有奇数环的,其他情况直接判有没有就行

题解 | #E-G#_牛客博客 (nowcoder.net)

#include
//#pragma-GCC-optimize("-Ofast");
#define int long long
//#define ll long long
#define lowbit(x) ((x)&(-x))
#define endl '\n'
#define pause system("pause")
using namespace std;
const int N=2e6+5;
const int mod=1e9+7;
const int inf=1e17;
const double pi=acos(-1);
int qpow(int a,int b)
{int res=1;while(b){if(b&1) res=res*a%mod;a=a*a%mod;b>>=1;}return res;
}
int getinv(int a){return qpow(a,mod-2);}
int head[N],cnt;
struct Edge
{int next,to;
}e[N];
void addedge(int from,int to)
{e[++cnt].next=head[from];e[cnt].to=to;head[from]=cnt;
}
int t,n,m,vis[N],dep[N],flag;
map,bool>mp;
void dfs(int u,int fa)
{if(flag) return;dep[u]=dep[fa]+1;vis[u]=1;for(int i=head[u];i;i=e[i].next){if(flag) return;int j=e[i].to;if(j==fa) continue;if(vis[j]==1){int siz=dep[u]-dep[j]+1;//cout<<"u="<>t;while(t--){cin>>n>>m;mp.clear();for(int i=1;i<=cnt;i++) e[i].next=e[i].to=0;for(int i=1;i<=n;i++) head[i]=vis[i]=dep[i]=0;cnt=0;for(int i=1;i<=m;i++){int u,v;cin>>u>>v;if(u>v) swap(u,v);mp[{u,v}]=1;}if(n>896||m<(n*n/4-n/2-100)){cout<<"YES\n";continue;}for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){if(!mp[{i,j}]) addedge(i,j),addedge(j,i);}flag=0;for(int i=1;i<=n;i++){if(!vis[i]) dfs(i,0);}if(flag) cout<<"YES\n";else cout<<"NO\n";}return 0;
}

F-座位_概率期望

会有两种情况,前i-1个人把第i个座位占掉之后,第i个人可以选前i-1中的一个座位或者第i+1个座位;或者前i-1个人把前i-1个座位占掉之后第i个人可以选择第i个或者是第i+1个座位;可以看出如果第i个人不选第i+1个座位的话那么就形成了前i个人占掉前i个座位的局面,这样的概率是0.5,那么第i个人占掉第i个座位的情况就是前i-1个人占掉前i-1个座位且第i个人选了第i个座位,这样的概率就是0.5*0.5=0.25,那么第i个人占掉第i个座位的期望就是0.25*1+0*(1-0.25)=0.25,由于第1个人和第n个人只能占第1个和第n个所以期望是0.5,所以n个人的期望就是0.5+0.5+(n-2)/4,当n==1的时候特判一下就可以

题解 | #E-G#_牛客博客 (nowcoder.net)

#include
//#pragma-GCC-optimize("-Ofast");
#define int long long
//#define ll long long
#define lowbit(x) ((x)&(-x))
#define endl '\n'
#define pause system("pause")
using namespace std;
const int N=2e6+5;
const int mod=998244353;
const int inf=1e17;
const double pi=acos(-1);
int qpow(int a,int b)
{int res=1;while(b){if(b&1) res=res*a%mod;a=a*a%mod;b>>=1;}return res;
}
int getinv(int a){return qpow(a,mod-2);}
int n;
signed main()
{//ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;if(n==1) cout<<"1\n";else{int inv4=getinv(4);int ans=(1+(n-2)*inv4%mod)%mod;cout<

G-交换_dp​​​​​​

将题意转化成一共有m个1,n-m个0,不断向数组里放数使得1都互不相邻;

设dp[i][j][0/1]表示前i个位置放了j个1第i个位置是0或者1,是0的情况那就是dp[i][j][0]=min(dp[i-1][j][0],dp[i-1][j][1]),是1的情况那就是将第j个1移动到第i个位置上去,花费是abs(p[j]-i),即dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][0]+abs(p[j]-i))

题解 | #E-G#_牛客博客 (nowcoder.net)

#include
//#pragma-GCC-optimize("-Ofast");
#define int long long
//#define ll long long
#define lowbit(x) ((x)&(-x))
#define endl '\n'
#define pause system("pause")
using namespace std;
const int N=2e6+5;
const int mod=998244353;
const int inf=1e17;
const double pi=acos(-1);
int qpow(int a,int b)
{int res=1;while(b){if(b&1) res=res*a%mod;a=a*a%mod;b>>=1;}return res;
}
int getinv(int a){return qpow(a,mod-2);}
int p[505],n,dp[505][505][2];
char s[505];
signed main()
{//ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;cin>>(s+1);int m=0;for(int i=1;i<=n;i++)if(s[i]=='1') p[++m]=i;for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)dp[i][j][0]=dp[i][j][1]=inf;for(int i=0;i<=n;i++)dp[i][0][0]=0;for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){dp[i][j][0]=min(dp[i-1][j][0],dp[i-1][j][1]);dp[i][j][1]=min(dp[i][j][1],dp[i-1][j-1][0]+abs(p[j]-i));}}int ans=min(dp[n][m][1],dp[n][m][0]);if(ans>n*n) ans=-1;cout<

相关内容

热门资讯

怎么解除订阅安卓系统,安卓系统... 你是不是也和我一样,手机里订阅了好多服务,结果现在想解除订阅,却一头雾水?别急,今天就来手把手教你如...
安卓系统停用怎么开启,轻松恢复... 亲爱的手机控们,你是否曾经遇到过安卓系统突然停用的情况,让你手忙脚乱,不知所措?别担心,今天就来教你...
安卓系统电池健康度,电池健康度... 你有没有发现,你的安卓手机最近是不是有点儿不给力了?电池续航能力大不如前,充电速度也慢了不少?别急,...
安卓系统按键怎么截图,安卓系统... 你是不是也和我一样,有时候想截个图分享给朋友,却发现安卓手机的截图功能有点神秘呢?别急,今天就来手把...
购票系统安卓源代码,架构设计与... 你有没有想过,那些我们每天离不开的购票系统,它们背后的秘密是什么呢?今天,就让我带你一探究竟,揭开购...
安卓手机系统后台测试,深度解析... 你有没有发现,你的安卓手机后台总是悄悄地忙碌着?别小看了这些后台程序,它们可是手机系统稳定运行的关键...
安卓系统重启的图标,解锁设备新... 手机突然重启,是不是心里有点慌?别急,今天就来和你聊聊安卓系统重启的图标,让你一眼就能认出它,再也不...
车载智慧屏安卓系统,智能出行新... 你有没有发现,现在的车载智慧屏越来越智能了?尤其是那些搭载了安卓系统的,简直就像是个移动的小电脑,不...
安卓系统连上网权限,解锁设备无... 你有没有发现,你的安卓手机里有些应用总是偷偷连上网?别小看这个小小的网络权限,它可是能影响你隐私、消...
安卓谷歌操作系统,探索安卓谷歌... 你知道吗?在智能手机的世界里,有一个操作系统可是无人不知、无人不晓,那就是安卓谷歌操作系统。它就像一...
安卓系统手写%怎样调出,具体实... 你有没有遇到过这种情况:在使用安卓手机的时候,突然想用手写输入法来记录一些灵感或者重要信息,可是怎么...
安卓手机重置 系统设置,轻松恢... 手机用久了是不是感觉卡顿得厉害?别急,今天就来教你怎么给安卓手机来个大变身——重置系统设置!想象你的...
win如何安装安卓系统,Win... 哇,你有没有想过,让你的Win系统也能玩转安卓应用?没错,就是那种在手机上轻松自如的安卓系统,现在也...
苹果qq和安卓系统,跨平台体验... 你有没有发现,现在手机市场上,苹果和安卓的较量可是越来越激烈了呢!咱们就来聊聊这个话题,看看苹果QQ...
显示最好的安卓系统,探索最新旗... 你有没有想过,为什么安卓系统那么受欢迎呢?它就像一个魔法盒子,里面装满了各种神奇的魔法。今天,就让我...
安卓app怎么降级系统,系统版... 你有没有发现,有时候安卓手机的系统更新后,新功能虽然炫酷,但老系统用起来更顺手呢?别急,今天就来教你...
雷军脱离安卓系统,引领科技变革... 你知道吗?最近科技圈可是炸开了锅,因为我们的雷军大大竟然宣布要脱离安卓系统,这可真是让人大跌眼镜啊!...
安卓系统自动开网络,安卓系统自... 你有没有发现,手机里的安卓系统有时候会自动开启网络连接,这可真是让人又爱又恨啊!有时候,你正专心致志...
安卓系统怎样控制后台,因为服务... 手机里的安卓系统是不是感觉越来越卡了?后台程序太多,不仅耗电还影响性能。别急,今天就来教你怎么巧妙地...
安卓系统打游戏推荐,一触即达! 你有没有发现,现在手机游戏越来越好玩了?不管是休闲小游戏还是大型MMORPG,都能在手机上畅玩。但是...