青岛澄润国际贸易有限公司

现在的位置: 主页 > 联系方式 > 文章列表

文章正文

Andrew Stankevich#39;s Contest #补题

作者:青岛澄润国际贸易有限公司 来源:wwww.usabcc.com 发布时间:2017-09-07 12:41:50
Andrew Stankevich#39;s Contest #补题

ACdream 1210 Chinese Girls' Amusement (规律+数学)

【题意】:

求最大的k<=n/2使得gcd(n,k)=1。

如果n是2m+1形式的,那么k=m就是答案;
如果n是4m形式的,那么k=2m-1就是答案;
如果n是4m+2形式的,那么k=2m-1就是答案。
证明略,需要简单的高精度。

java代码:

//感觉就是暴力 从n/2 开始减 ,直到互素为止, import java.io.*; import java.util.*; import java.math.BigInteger;//声明BigInteger大数类 import java.lang.*; public class Main { public static void main(String args[]) { Scanner cin = new Scanner(System.in); BigInteger n,k; n=cin.nextBigInteger(); k=n.divide(new BigInteger(2)); while(n.gcd(k).compareTo(BigInteger.ONE)!=0) { k=k.subtract(BigInteger.ONE); } System.out.println(k); } }
ACdream 1211 Reactor Cooling【上下界网络流 + 输出流量】

题意:

给n个点,及m根pipe,每根pipe用来流躺液体的,单向的,每时每刻每根pipe流进来的物质要等于流出去的物质,要使得m条pipe组成一个循环体,里面流躺物质。

并且满足每根pipe一定的流量限制,范围为[Li,Ri].即要满足每时刻流进来的不能超过Ri(最大流问题),同时最小不能低于Li。

例如:

46(4个点,6个pipe)
12 1 3 (1->2上界为3,下界为1)
23 1 3
3 4 1 3
4 1 1 3
1 3 1 3
4 2 1 3

可行流:

\

再如:所有pipe的上界为2下界为1的话,就不能得到一种可行流。

题解:

上界用ci表示,下界用bi表示。

下界是必须流满的,那么对于每一条边,去掉下界后,其自由流为ci– bi。

主要思想:每一个点流进来的流=流出去的流

对于每一个点i,令

Mi= sum(i点所有流进来的下界流)– sum(i点所有流出去的下界流)

如果Mi大于0,代表此点必须还要流出去Mi的自由流,那么我们从源点连一条Mi的边到该点。

如果Mi小于0,代表此点必须还要流进来Mi的自由流,那么我们从该点连一条Mi的边到汇点。

如果求S->T的最大流,看是否满流(S的相邻边都流满)。

满流则有解,否则无解。

\

代码: /* *上下界的网络流,用上界减去下界 * Problem: ACdream 1211 * Running time: 16MS * Complier: G++ * Author: herongwei * Create Time: 19:59 2015/10/8 星期四 */ #include #include #include #include #include

企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:武汉网站推广 https://www.feimao666.com

COPYRIGHT © 2015 青岛澄润国际贸易有限公司 ALL RIGHTS RESERVED.

网站地图 技术支持:肥猫科技
精彩专题:网站建设
购买本站友情链接、项目合作请联系客服QQ:2500-38-100