Java的算法————A&B&C&D&E&F&六人中随机抽取3人中奖
4.采用递归的方式得到数组中最大的数
import java.io.*;
import java.util.*;
public class test2
&public static void main(String[] args) throws
IOException
array[]={0,34,67,90,21,-9,98,1000,-78};
&&System.out.println(findMax
(array, 0));
&public static int findMax(int a[],int
if(a==null||a.length ==0)
0;&&&&&&&&&&&&&&&&&&&&&&&
//判断该数组是否存在，或者是否存在值，没有的话返回0
max=0;&&&&&&&&&&&&&&&&&&&&&&
//为变量付一初值
if(index&a.length
-1)&&&&&&&&&&&
//判断当前索引是否超出数组的范围
&max=findMax(a,index+1);&&&&&
//采用递归的方式取得当前后一位值，并将返回值赋到max
if(max&a[index])&&&&&&&&&&//将返回来的值与当前数组中index的值相比较，得出较大的值覆盖max
&max=a[index];
//if(max&a[index])&&&&&&&&
//将返回来的值与当前数组中index的值相比较，得出较小的值覆盖max
&//max=a[index];
s = “011”
public class test5
&public static void main(String as[])
System.out.println(getMaxContinuity(a));
&public static int getMaxContinuity(String
//变量max_*用来保存得出的数据，n_*用来计算个数
max_0=0;//定义接收0和1个数的变量
&&int max_1=0;
&&int n_1=0;// 当前1连续的次数
&&int n_0 = 0;&
// 当前0连续的次数
i=0;i&s.length() ;i++)
&&&if(s.charAt(i)=='0')
//当取出的字符是0的话就将0连续的次数的变量加1
&&&&n_0++;
&&&&n_1=0;&&&&&&&&&&&&
//当前加的是0连续的次数的变量，就让1连续的次数的变量变为初值
if(s.charAt(i)=='1')
&&&&n_1++;
&&&&n_0=0;
&&&if(n_0&max_0)&&&&&&&
//分别得出0和1的个数
&&&&max_0=n_0;
&&&if(n_1&max_1)
&&&&max_1=n_1;
max_0&max_1?max_0:max_1;&
//将其中更大的值返回
public class test6
&public static void main(String as[])
&&System.out
.print(jin_zhi_16_3("F"));
&private static int getRealValue(char x)
//将16进制字符转化为整型
&&if(x&='0'
&& x&='9') return
&&if(x&='a'
&& x&='f') return
&&if(x&='A'
&& x&='F') return
&&return 0;
&public static String jin_zhi_16_3(String x)
n=0;&&&&&&&&&&&&&&&&&&&&&&
//用于接收16进制转化为10进制的变量，设初值0
i=0;i&x.length() ;i++) //16进制转化为10进制
&&&n=n*16+getRealValue(x.charAt(i));
&&String a="";
&&while(true)&&&&&&&&&&&&&&&&&&&&
// 10进制转化为3进制
&&&if(n==0)
&&&a=(n%3)+a;&&&&&&&&&&&&&&&&&&
//a取得n的余数并注意将（n%3）转化为字符串+a；
&public static void main(String as[])
&&int v,m,i,n,q;
i=100;i&1000;i++)//取所有的三位数
q=i*i;&&&&&&&&&&&
&&&for(int
k=0;k&3;k++)
&&&&m=q%v;&&&&&&&&&&&
//求余取当前数值的尾巴
&&&&n=i%v;
&&&&v=v*10;
&&&&if(m==n)&&&&&&&&&
//将尾巴三位数分别拿出来比较
&&&&&if(k==2)&&&&&&&
//都后三位都相等的话就输出，并退出当前循环
&&&&&&System.out.println(i);
a^3 + b^3 = c^3 + d^3
1b=12c=9d=10
11217299101729
a=12b=1c=9d=10
import java.util.*;
public class test8
&public static void main(String[] args)
&&int max=0;
&&int a[]=new int[4];
&&Vector b = new Vector();
i=0;i&30;i++)
&&&for(int
j=0;j&30;j++)
&&&&for(int
k=0;k&30;k++)
&&&&&for(int
m=0;m&30;m++)
&&&&&&if((i*i*i)+(j*j*j)==(k*k*k)+(m*m*m))
&&&&&&&if(i!=j&&i!=k&&i!=m&&j!=k&&j!=m&&k!=m)
&&&&&&&&a[0]=i;
&&&&&&&&a[1]=j;
&&&&&&&&a[2]=k;
&&&&&&&&a[3]=m;
&&&&&&&&&for(int
n=0;n&a.length
//从小到大的排序
&&&&&&&&&{
&&&&&&&&&&for(int
r=n;r&a.r++)
&&&&&&&&&&{
&&&&&&&&&&&if(a[n]&a[r])
&&&&&&&&&&&{
&&&&&&&&&&&&
&&&&&&&&&&&&a[n]=a[r];
&&&&&&&&&&&&a[r]=
&&&&&&&&&&&}
&&&&&&&&&&}
&&&&&&&&&&
&&&&&&&&&}
&&&&&&&&&for(int
t=0;t&a.t++)
&&&&&&&&&{
&&&&&&&&&&System.out.print(a[t]+"，");
&&&&&&&&&}
&&&&&&&&&System.out.println();
4+2, 4+1+1
3+3, 3+2+1, 3+1+1+1
2+2+2, 2+2+1+1, 2+1+1+1+1
1+1+1+1+1+1+1
代码如下：
import java.io.*;
import java.util.*;
public class test9
&static int& x,y;
&public static void main(String[] args) throws
IOException
&&//BufferedReader br = new
BufferedReader(new InputStreamReader(System.in));
&&//String s = br.readLine();
&&Scanner in=new
Scanner(System.in );
&&System.out.println("输入1~10的数：");
&&int a=in.nextInt() ;
&&String str="";
i=a;i&0;i--)
&&&if(i==a)
&&&&System.out.println(a);
&&&&Create(i+str,i,(a-i));
&&&&System.out.println();
&//a:保存原来的字符，orign：分解后还需要分解的数。other：分解后的数还需0ther数相加才能等于原来的数
&public static void Create(String a,int orig,int
&&if(other==0)
&&&System.out.print(a+",");
i=i&0;i--)
&&&if(i&=orig)//确保减一的数大于还需要分解的数
&&&&Create(a+"+"+i,i,other-i);
import java.util.*;
import java.text.*;
public class test3
&public static void main(String []a)
&&Scanner in=new
Scanner(System.in);
&&String str=in.nextLine()
&&DateFormat dt=new
SimpleDateFormat("yyyy-M-D");
oldday="";
x=dt.parse(oldday);
y=dt.parse( str);
&&&System.out.print((y.getTime()
- x.getTime() )/(24*));
&&catch(Exception e)
System.out.println("輸入的不是有效日期");
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。当前位置：
＞＞＞将A，B，C，D，E，F六个字母排成一排，且A，B均在C的同侧，则不同..
将A，B，C，D，E，F六个字母排成一排，且A，B均在C的同侧，则不同的排法共有______种（用数字作答）
题型：填空题难度：偏易来源：浙江
按C的位置分类，在左1，左2，左3，或者在右1，右2，右3，因为左右是对称的，所以只看左的情况最后乘以2即可．当C在左边第1个位置时，有A&55，当C在左边第2个位置时A&24A&33，当C在左边第3个位置时，有A&23A&33+A&22A&33，共为240种，乘以2，得480．则不同的排法共有 480种．故答案为：480．
马上分享给同学
据魔方格专家权威分析，试题“将A，B，C，D，E，F六个字母排成一排，且A，B均在C的同侧，则不同..”主要考查你对&&排列与组合&&等考点的理解。关于这些考点的“档案”如下：
现在没空？点击收藏，以后再看。
因为篇幅有限，只列出部分考点，详细请访问。
排列与组合
1、排列的概念：从n个不同元素中取出m（m≤n）个元素，按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列。 2、全排列：把n个不同元素全部取出的一个排列，叫做这n个元素的一个全排列。 3、排列数的概念：从n个不同元素中取出m（m≤n）个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号表示。 4、阶乘：自然数1到n的连乘积，用n!=1×2×3×…×n表示。 规定：0！＝1 5、排列数公式：=n（n-1）（n-2）（n-3）…（n-m+1）=。
1、组合的概念：从n个不同元素中取出m个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合。 2、组合数的概念：从n个不同元素中取出m个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数用符号表示。 3、组合数公式：； 4、组合数性质：（1）；（2）。 5、排列数与组合数的关系：。 &排列与组合的联系与区别：
从排列与组合的定义可以知道，两者都是从n个不同元素中取出m个（m≤n，n，m∈N）元素，这是排列与组合的共同点。它们的不同点是：排列是把取出的元素再按顺序排列成一列，它与元素的顺序有关系，而组合只要把元素取出来就可以，取出的元素与顺序无关．只有元素相同且顺序也相同的两个排列才是相同的排列，否则就不相同；而对于组合，只要两个组合的元素相同，不论元素的顺序如何，都是相同的组合，如a，b与b，a是两个不同的排列，但却是同一个组合。排列应用题的最基本的解法有：
（1）直接法：以元素为考察对象，先满足特殊元素的要求，再考虑一般元素，称为元素分析法，或以位置为考察对象，先满足特殊位置的要求，再考虑一般位置，称为位置分析法；（2）间接法：先不考虑附加条件，计算出总排列数，再减去不符合要求的排列数。
排列的定义的理解：
①排列的定义中包含两个基本内容，一是取出元素；二是按照一定的顺序排列；②只有元素完全相同，并且元素的排列顺序也完全相同时，两个排列才是同一个排列，元素完全相同，但排列顺序不一样或元素不完全相同，排列顺序相同的排列，都不是同一个排列；③定义中规定了m≤n，如果m&n，称为选排列；如果m=n，称为全排列；④定义中“一定的顺序”，就是说排列与位置有关，在实际问题中，要由具体问题的性质和条件进行判断，这一点要特别注意；⑤可以根据排列的定义来判断一个问题是不是排列问题，只有符合排列定义的说法，才是排列问题。
排列的判断：
判断一个问题是否为排列问题的依据是是否与顺序有关，与顺序有关且是从n个不同的元素中任取m个(m≤n)不同元素的问题就是排列问题，否则就不是排列的问题，而检验一个问题是否与顺序有关的依据就是变换不同元素的位置，看其结果是否有变化，若有变化就与顺序有关，就是排列问题；若没有变化，就与顺序无关，就不是排列问题．
写出一个问题中的所有排列的基本方法:
写出一个问题中的所有排列的基本方法是字典排序法或树形图法或框图法。
组合规律总结：
①组合要求n个元素是不同的，被取出的m个元素也是不同的，即从n个不同元素中进行m次不放回的抽取；②组合取出的m个元素不讲究顺序，也就是说元素没有位置的要求，无序性是组合的本质属性；③根据组合的定义，只要两个组合中的元素完全相同，那么不论元素的顺序如何，都是相同的组合，而只有两个组合中的元素不完全相同，才是不同的组合．
排列组合应用问题的解题策略：
1.捆绑法：把相邻的若干特殊元素“捆绑”成一个“大元素”，然后再与其余“普通元素”全排列，而后“松绑”，将特殊元素在这些位置上全排列，这就是所谓相邻问题“捆绑法”．2.插空法：对于不相邻问题用插空法，先排其他没有要求的元素，让不相邻的元素插产生的空．3.优先排列法：某些元素（或位置）的排法受到限制，列式求解时，应优先考虑这些元素，叫元素分析法，也可优先考虑被优待的位置，叫位置分析法．4.排除法：这种方法经常用来解决某些元素不在某些位置的问题，先总体考虑，后排除不符合条件的。5.特殊元素优先考虑，特殊位置优先安排的策略；6.合理分类和准确分步的策略；7.排列、组合混合问题先选后排的策略；8.正难则反，等价转化的策略；9相邻问题捆绑处理的策略；10.不相邻问题插空处理的策略；11.定序问题除法处理的策略；12.分排问题直接处理的策略；13.构造模型的策略，
&排列的应用：
(1)-般问题的应用：求解排列问题时，正确地理解题意是最关键的一步，要善于把题目中的文字语言翻译成排列的相关术语；正确运用分类加法计数原理和分步乘法计数原理也是十分重要的；还要注意分类时不重不漏，分步时只有依次做完各个步骤，事情才算完成，解决排列应用题的基本思想是：&解简单的排列应用问题，首先必须认真分析题意，看能否把问题归结为排列问题，即是否有顺序，如果是，再进一步分析n个不同的元素是指什么以及从n个不同的元素中任取m个元素的每一种排列对应着什么事情，最后再运用排列数公式求解．(2)有限制条件的排列问题：在解有限制条件的排列应用题时，要从分析人手，先分析限制条件有哪些，哪些是特殊元素，哪些是特殊位置，识别是哪种基本类型，在限制条件较多时，要抓住关键条件（主要矛盾），通过正确地分类、分步，把复杂问题转化为基本问题，解有限制条件的排列问题的常用方法是：&常见类型有：①在与不在：在的先排、不在的可以排在别的位置，也可以采用间接相减法；②邻与不邻：邻的用”，不邻的用”；③间隔排列：有要求的后排（插空）．
组合应用题：
解决组合应用题的基本思想是“化归”，即由实际问题建立组合模型，再由组合数公式来计算其结果，从而得出实际问题的解．（1）建立组合模型的第一步是分析该实际问题有无顺序，有顺序便不是组合问题．（2）解组合应用题的基本方法仍然是“直接法”和“间接法”．（3）在具体计算组合数时，要注意灵活选择组合数的两个公式以及性质的运用．
排列、组合的综合问题：
(1)应遵循的原则：先分类后分步；先选后排；先组合后排列，有限制条件的优先；限制条件多的优先；避免重复和遗漏．(2)具体途径：在解决一个实际问题的过程中，常常遇到排列、组合的综合性问题．而解决问题的关键是审题，只有认真审题，才能把握问题的实质，分清是排列问题，还是组合问题，还是综合问题，分清分类与分步的标准和方式，并且要遵循两个原则：①按元素的性质进行分类；②按事情发生的过程进行分析．(3)解排列、组合的综合问题时要注意以下几点：①分清分类计数原理与分步计数原理：主要看是，还是分步完成；②分清排列问题与组合问题：主要看是否与序；③分清是否有限制条件：被限制的元素称为特殊元素，被限制的位置称为特殊位置。解这类问题通常从以下三种途径考虑：a．以元素为主考虑，即先满足特殊元素的要求，再考虑其他元素；b．以位置为主考虑，即先满足特殊位置的要求，再考虑其他位置；c．先不考虑限制条件，计算出排列或组合数，再减去不合要求的排列或组合数．前两种叫直接解法，后一种叫间接解法，不论哪种，都应“特殊元素（位置）优先考虑”．④要特别注意既不要重复，也不要遗漏．
(4)排列、组合应用问题的解题策略：①特殊元素优先考虑，特殊位置优先安排的策略；②合理分类和准确分步的策略；③排列、组合混合问题先选后排的策略；④正难则反，等价转化的策略；⑤相邻问题捆绑处理的策略；⑥不相邻问题插空处理的策略；⑦定序问题除法处理的策略；⑧分排问题直接处理的策略；⑨；⑩构造模型的策略，
发现相似题
与“将A，B，C，D，E，F六个字母排成一排，且A，B均在C的同侧，则不同..”考查相似的试题有：
811070558992328398793915772770809905Problem A: An easy problem
Description
&&& Peter Manson owned a small house in an obscure street. It was a weather-beaten tenement of wood, containing some six or eight rooms, all of which, with one exception, were given over to dirt, cobwebs, gloom, and desolation. Peter might readily have let the rooms which he did not require for his own use, but so profound was his distrust of human nature, that not even the prospect of receiving rent for the empty rooms could overcome his apprehension of being robbed by neighbors under the same roof. For Peter trusted not his money to banks or railroads, but wanted to have it directly under his own eye or within his reach. As for investing his gold in the luxuries of life, or even in what were generally considered its absolute necessaries, we have already seen that Peter was no such fool as that. A gold eagle was worth ten times more to him than its equivalent in food or clothing.
&&& With more than his usual alacrity, old Peter Manson, bearing under his cloak the fresh loaf which he had just procured from the baker on such advantageous terms, hastened to his not very inviting home.
&&& Drawing from his pocket a large and rusty door-key, he applied it to the door. It turned in the lock with a creaking sound, and the door yielding to Peter's push he entered.
&&& The room which he appropriated to his own use was in the second story. It was a large room, of some eighteen feet square, and, as it is hardly necessary to say, was not set off by expensive furniture. The articles which came under this denomination were briefly these,&a cherry table which was minus one leg, whose place had been supplied by a broom handle three hard wooden chairs
an old wash- a rusty stove which Peter had picked up cheap at an auction, after finding that a stove burned out less f a few articles of crockery of different[18] patterns, som a few tin dishes, such as Peter found esse and a low truckle bedstead with a scanty supply of bedclothes.
&&& Are you tired of reading this long passage?Now,I&m giving you a task which is nothing to do with the passage.ahhh~Please sort this string &cpteca&,make the first letter be upper-letter.
Sample Input
Sample Output
题目链接：http://gdutcode.sinaapp.com/problem.php?cid=1053&pid=0
分析：标准签到题，(⊙o⊙)&，直接输出Accept，A不大写的人不知道什么心态
下面给出AC代码：
1 #include &cstdio&
2 #include &cstring&
3 #include &algorithm&
4 #include &cmath&
5 #include &iostream&
6 #include &vector&
7 #include &queue&
8 #include &string&
9 #include &set&
10 #include &stack&
11 #include &map&
12 using namespace
13 int main()
puts("Accept");
Problem B: Tmk吃汤饭
Description
前段时间天气寒冷，所以tmk喜欢上了吃汤饭。
众所周知，三饭二楼的汤饭分点餐和取餐两个窗口，一位蜀黍负责点餐窗口，一位蜀黍负责煮汤，一位蜀黍负责打饭，点餐需要1分钟，每一份需要煮5分钟，同一时间最多可以煮4份。
有一天，tmk来到三饭二楼，发现汤饭取餐窗口没人，但点餐窗口却排满了人，原来卖汤饭的蜀黍刚刚开始工作，tmk无聊的数了数排队人数，刚好n个人。
Tmk想知道如果这个时候自己排到队尾，需要多久才能取到汤饭，由于我们广工大学生素质比较高，所以没人插队，当然tmk也不会插队，而且他们意志坚定，所以不会中途而废。
现在，假设除了点餐和煮汤的时间，其他时间忽略不计，tmk想让你算一下他需要等多久才能取到汤饭。
第一行一个T(0&T&=10000)，表示有多少组数据。
接着每行有一个n(0&=n&=10000)，表示tmk到三饭二楼时点餐窗口排队的人数。
对于每个n，输出一个整数表示tmk多久能取到汤饭。
Sample Input
Sample Output
题目链接：http://gdutcode.sinaapp.com/problem.php?cid=1053&pid=1
分析：很有规律的一个序列，我没去推公式而是直接打的表&公式应该是 (n/4+1)*5+(n%4+1)
下面给出AC代码：
1 #include &cstdio&
2 #include &cstring&
3 #include &algorithm&
4 #include &cmath&
5 #include &iostream&
6 #include &vector&
7 #include &queue&
8 #include &string&
9 #include &set&
10 #include &stack&
11 #include &map&
12 using namespace
13 const int maxn = 10050;
14 int a[maxn];
15 int main()
for(int i=1;i&i++)
a[i] = a[i-1]+1;
if(i%4==0)
scanf("%d",&t);
while(t--)
scanf("%d",&n);
printf("%d\n",a[n]);
Problem C: 进击的调查兵团
Description
自从Wall.Rose被钢铁巨人再次攻陷之后，人类圈只剩下最后一道防线Wall.Sina。司令官终于按耐不住，决定下达三笠将军直接从105期和106期的训练兵团中召集一批毕业生进入调查兵团进行对巨人的反击战。
105期的毕业生有N个人，106期的有M个人。为了方便三笠将军的挑选，两个训练团的教官都提交了当时毕业生的毕业成绩，成绩按从小到大排行。即105期第i成绩小的毕业生的成绩为A[i]，106期第j成绩小的毕业生的成绩为B[j]，满足A[0]&A[1]&&&A[N-2]&A[N-1]，B[0]&B[1]&&B[M-2]&B[M-1]。而且为了体现历届毕业生成绩的差异，保证了A[i] != B[j]{0&=i&N, 0&=j&m}.
现在三笠将军对这A，B两份成绩单中挑选Q次人员。在每次挑选中，会从A[L1..R1]和B[L2..R2]中选出成绩第k小的毕业生出来。三笠这样的挑选纯粹为了好玩，所以那Q次挑选的人中有可能存在重复。
为了能尽快选出反击战人员，司令官决定派你尽快得出人员名单。
第一行输入一个整数T，表示有T组数据，对于每组数据
第一行包含3个整数，105期毕业生人数N(&=10^5)，106期毕业生人数M(&=10^5)，三笠的挑选次数Q(&=10^4)。
第二行包含N个整数A[i](0&=A[i]&2^31)，
第三行包含M个整数B[i](0&=B[i]&2^31)。
第4..Q+3行中，每行有5个整数，L1，R1，L2，R2，k& (0&=L1&=R1&N, 0&=L2&=R2&M, 1&=k&=R1-L1+R2-L2+2)。
对于每次挑选，输出一个整数，表示A[L1..R1]和B[L2..R2]中第k小的成绩。
Sample Input
2 4 6 9 10
Sample Output
题目链接：http://gdutcode.sinaapp.com/problem.php?cid=1053&pid=2
二分答案，二分答案出来以后在二分查找在每个序列里有多少个小于等于他的，stl是个好东西
下面给出AC代码：
1 #include &cstdio&
2 #include &cstring&
3 #include &algorithm&
4 #include &cmath&
5 #include &iostream&
6 #include &vector&
7 #include &queue&
8 #include &string&
9 #include &set&
10 #include &stack&
11 #include &map&
12 using namespace
13 const int maxn = 1e5+100;
14 int a[maxn];
15 int b[maxn];
16 int main()
scanf("%d",&t);
while(t--)
int n,m,q;
scanf("%d %d %d",&n,&m,&q);
for(int i=0;i&n;i++)
scanf("%d",&a[i]);
for(int i=0;i&m;i++)
scanf("%d",&b[i]);
while(q--)
int l1,r1,l2,r2,k;
scanf("%d %d %d %d %d",&l1,&r1,&l2,&r2,&k);
int l = min(a[l1],b[l2]),r = max(a[r1],b[r2]);
while(l&r)
int mid = l+((r-l)/2);
int pos1 = lower_bound(a+l1,a+r1+1,mid)-a;
if(a[pos1]==mid)
int pos2 = lower_bound(b+l2,b+r2+1,mid)-b;
if(b[pos2]==mid)
if(pos1+pos2&k+l1+l2)
l = mid+1;
printf("%d\n",l);
Problem D: TMK的航拍图像
Description
& 这下糟了，TMK他竟然获得了一次玩无人机的机会，TMK兴奋得像个孩子，拿着无人机摆弄了起来。
于是TMK的无人机上天了，飞得非常高，偏偏今天天气还很好，无人机的航拍非常清晰。TMK把他的无人机开到了最高，从上帝视角拍下了照片，然后结束了他年轻的无人机生涯。
TMK发现这张照片上，所有的建筑物都变成了点，这些点能描述成二维平面上的点，有些点会在同一条直线上，于是TMK想要求出在这张照片上能画出多少条不同的直线，使得这些直线经过至少两个点。TMK把这个问题扔给了Maple，Maple把这个问题扔给了YFQQ。现在，YFQQ把这个问题扔给了你。
第一行有一个整数T，代表有T组数据(1&=T&=50)
每组数据一开始有一个整数n，表示照片上有n个二维坐标点(0&=n&=200)
接下来n行，每行有两个整数x,y，代表点的坐标，保证点不重合(-10000&=x,y&=10000)
每组数据输出一个整数，为不同的直线的数量
Sample Input
Sample Output
题目链接：http://gdutcode.sinaapp.com/problem.php?cid=1053&pid=3
没有重点，那么所有可能的线段是n*(n-1)/2,由于问的是直线，所以枚举两个点，判断是否和其他点相交如果相交就ans&&
下面给出AC代码：
1 #include &cstdio&
2 #include &cstring&
3 #include &algorithm&
4 #include &cmath&
5 #include &iostream&
6 #include &vector&
7 #include &queue&
8 #include &string&
9 #include &set&
10 #include &stack&
11 #include &map&
12 using namespace
13 const int maxn = 2e5+10;
14 struct point
17 }a[maxn];
18 int n,m;
19 int x_mul(point p0,point p1,point p2)
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
23 int main()
//freopen("a.in","r",stdin);
scanf("%d",&t);
while(t--)
scanf("%d",&n);
for(int i=0;i&n;i++)
scanf("%d %d",&a[i].x,&a[i].y);
int ans = n*(n-1)/2;
for(int i=0;i&n;i++)
for(int j=i+1;j&n;j++)
for(int k=0;k&n;k++)
if(k&=i && k&=j)
if(x_mul(a[k],a[i],a[j])==0)
printf("%d\n",ans);
Problem E: 绕远路
Description
TMK他果然又迟到了，虽然YFQQ已经习惯了，但是Maple还是毅然决然地跑去实验室要走回宿舍去。
Maple来到了楼下，当即决定要走一条足够长的路回宿舍去。Maple给他可以走的n个点从1到n分别编号，其中实验室在点1，宿舍在点n。这n个点中由m条双向通行的道路相连。
Maple规定，当他到达某个点时，他不会再走到比这个点编号小的点，而当他选择了一条路后，他会径直沿着这条路走直到到达这条路的终点。有一些路会从一个点连向自己，代表Maple可以从这个点出发绕一圈回来，两个点钟可能会有多条不同的路。Maple想要走这些路直到到达宿舍，当他到达宿舍时，他会马上停下来。但是，因为Maple有体力的限制，他走的路的总长度不能超过k，否则他就会累死。
现在给出了这些双向路相连的点和他的长度，求问Maple从实验室走到宿舍在不累死的前提下最长能走多长。
第一行一个整数T，代表有T组数据(1&=T&=20)
每组数据一开始有三个整数n,m,k，代表有n个点，m条路，Maple最多能走的长度为k
接下来有m行，每一行三个整数u,v,l，代表点u到点v有一条双向路，长度为l
(2&=n&=2000,0&=m&=3000,1&=k&=3000)(1&=u,v&=n,1&=l&=6000)
每组数据输出一个整数，为题目所求。
若Maple回不了宿舍或回宿舍之前一定会累死，那么输出-1。
Sample Input
Sample Output
题目链接：http://gdutcode.sinaapp.com/problem.php?cid=1053&pid=4
dp题，dp[i][n]表示到点i长度为n是否可行，状态转移方程为：dp[tmp.v][tt] |= dp[i][tt-tmp.w],tmp.v到i之间有条长度为tmp.w的边
下面给出AC代码：
1 #include &cstdio&
2 #include &cstring&
3 #include &algorithm&
4 #include &cmath&
5 #include &iostream&
6 #include &vector&
7 #include &queue&
8 #include &string&
9 #include &set&
10 #include &stack&
11 #include &map&
12 using namespace
13 const int maxn = 5000+40;
14 struct node
node(int _v,int _w)
24 vector&node&G1[maxn],G2[maxn];
25 int dp[maxn][maxn];
26 int main()
scanf("%d",&t);
while(t--)
memset(dp,0,sizeof(dp));
int n,m,k;
scanf("%d %d %d",&n,&m,&k);
for(int i=1;i&=n;i++)
G1[i].clear(),G2[i].clear();
while(m--)
int u,v,l;
scanf("%d %d %d",&u,&v,&l);
swap(u,v);
G1[u].push_back(node(v,l));
G2[u].push_back(node(v,l));
dp[1][0] = 1;
for(int i=1;i&=n;i++)
for(unsigned j=0;j&G2[i].size();j++)
node tmp = G2[i][j];
for(int tt=tmp.w;tt&=k;tt++)
dp[i][tt] |= dp[i][tt-tmp.w];
for(unsigned j=0;j&G1[i].size();j++)
node tmp = G1[i][j];
for(int tt=tmp.w;tt&=k;tt++)
dp[tmp.v][tt] |= dp[i][tt-tmp.w];
int ans = -1;
for(int i=0;i&=k;i++)
if(dp[n][i])
printf("%d\n",ans);
Problem F: 密码锁
Description
tmk听说小黄车可以包学期，于是兴奋了把小黄车包了，为了赚回本，所以tmk天天骑。
最近小黄车换了新锁，每次开锁都需要把数字旋转到对应的密码位置(每个位置都是0~9的循环，9的下一位是0，可以顺着转也可以逆着转)，比如原始的数字为&1234&，而密码是&5678&，那么每一圈移动的格数之和最少等于4+4+4+4=16次，由于tmk比较聪明，所以tmk每次开锁都让每一圈移动的格数之和最小。
tmk的记忆力也是十分了得，他记住了这段时间骑过的所有小黄车的密码和原始数字，他想知道他总共转了多少格，但是tmk很懒，所以这个艰巨的任务就交到了你的手里。
第一行一个整数T(0&T&=100)，表示有多少组数据。
每组数据第一行一个整数n(0&=n&=100)，表示tmk最近骑了多少次小黄车。
接着n次骑车的数据：
Ai，Bi，Ci，Di，中间有空格隔开，表示密码锁的密码。
ai，bi，ci，di，中间有空格隔开，表示密码锁的原始数字。
其中0&= Ai，Bi，Ci，Di，ai，bi，ci，di &=9，且均为整数
对于每组数据，输出一个数字，表示tmk总共转了多少格。
Sample Input
Sample Output
题目链接：http://gdutcode.sinaapp.com/problem.php?cid=1053&pid=5
每个齿轮转到想要的位置最少步数为：min((Ai-ai+10)%10,(ai-Ai+10)%10)
下面给出AC代码：
1 #include &cstdio&
2 #include &cstring&
3 #include &algorithm&
4 #include &cmath&
5 #include &iostream&
6 #include &vector&
7 #include &queue&
8 #include &string&
9 #include &set&
10 #include &stack&
11 #include &map&
12 using namespace
13 const int maxn = 10050;
14 int a[maxn];
15 int main()
scanf("%d",&t);
while(t--)
scanf("%d",&n);
int ans = 0;
while(n--)
int a1,b1,c1,d1;
int a2,b2,c2,d2;
scanf("%d %d %d %d",&a1,&b1,&c1,&d1);
scanf("%d %d %d %d",&a2,&b2,&c2,&d2);
ans += min((a1-a2+10)%10,(a2-a1+10)%10);
ans += min((b1-b2+10)%10,(b2-b1+10)%10);
ans += min((c1-c2+10)%10,(c2-c1+10)%10);
ans += min((d1-d2+10)%10,(d2-d1+10)%10);
printf("%d\n",ans);
Problem G: 知识来源于分解
Description
有东西在乱窜。我往下看，发现了一只小个的白色生物，用后腿站立着，嗅闻着我的躯体。它吸引了我的注意。
你有什么用途？
我分析这个生物。品红色热能光束一闪而过，它曾颤动的地方扬起尘埃。
哺乳动物...夜行习性...无可挑剔的听觉。难以置信的弱小。但它们的繁殖能力如此强大。
&唔，&我喃喃自语。希望能发现更加复杂的物体；那些东西把我给迷住了。
消化并学习：这是我的目的。和我一起旅行的其它来客都很原始：杀死并吃掉，杀死并吃掉。我需要收集所有可用的信息&&收获更多有价值的资源。
终于，我们偶然发现了一座被摧毁的城市，仅有一座古朴的塔楼还完好地保留着。这座塔楼似乎受到了保护&&或者是有意留下的。我解构了废墟的成分。我的分析指出，这个地区曾经是一个强大的魔法国度；如此强大的破坏力以它为目标，我丝毫不感到意外。有某些东西对这座塔楼感兴趣。在其它来客正在四散搜刮时，我进入了城堡。
神秘的仪器散落各处。我检测了一件。又一道品红色热能光束一闪而过，尘埃再次扬起。
时光机器...启动需要解开谜题...天呐，我需要仔细瞧瞧。
&Given a string s of length n, and integer k, return the length of the longest substring that contains exactly k distinct characters.&
T组数据...string只包含大小写字母...找不到返回0。这道题成功吸引了我。
第一行输入一个整数T，表示有T组数据，
接下来T行，每一行一个字符串s和一个整数k(T&=666, length(s)&=10^6, 0=&k&=52)
对于每一组数据，输出一个答案。
Sample Input
aaabbbcc 2
Sample Output
题目链接：http://gdutcode.sinaapp.com/problem.php?cid=1053&pid=6
分析：尺取维护答案
下面给出AC代码：
1 #include &cstdio&
2 #include &cstring&
3 #include &algorithm&
4 #include &cmath&
5 #include &iostream&
6 #include &vector&
7 #include &queue&
8 #include &string&
9 #include &set&
10 #include &stack&
11 #include &map&
12 using namespace
13 const int maxn = 1e6+10;
14 char a[maxn];
15 int vis[100];
16 int main()
while(t--)
scanf("%s %d",a,&k);
n = strlen(a);
int ans = 0;
int l = 0,r = 0,cnt = 0;
memset(vis,0,sizeof(vis));
while(n-l&ans)
while(r&n)
if(vis[a[r]-'A'])
vis[a[r]-'A']++;
if(cnt+1&k)
vis[a[r]-'A']++;
if(cnt == k)
ans = max(ans,r-l);
vis[a[l]-'A']--;
if(vis[a[l]-'A']==0)
printf("%d\n",ans);
Problem H: 找正方形
Description
在一个字符地图中，能否找到有#围成的正方形的，如果找到则输出YES，没有则NO。（正方形内部无需填满#，面积至少是4，地图大小不超过20*20）
合法情况1:
合法情况2:
不合法情况
第一行一个整数T，表示有多少组数据
对于每组数据：
第一行为两个整数n，m表示地图大小n行和m列(0&n,m&=20)
如果找到，输出&YES&(不包括引号)，否则输出&NO&(不包括引号)
Sample Input
Sample Output
题目链接：http://gdutcode.sinaapp.com/problem.php?cid=1053&pid=7
分析：找到一点&#&，枚举正方形长度，判断是否合法
下面给出AC代码：
1 #include &cstdio&
2 #include &cstring&
3 #include &algorithm&
4 #include &cmath&
5 #include &iostream&
6 #include &vector&
7 #include &queue&
8 #include &string&
9 #include &set&
10 #include &stack&
11 #include &map&
12 using namespace
13 const int maxn = 1e6+10;
14 char a[25][25];
15 bool slove(int x,int y,int n)
for(int i=x;i&=x+n;i++)
if(a[i][y]!='#')
return false;
if(a[i][y+n]!='#')
return false;
for(int i=y;i&=y+n;i++)
if(a[x][i]!='#')
return false;
if(a[x+n][i]!='#')
return false;
return true;
33 int main()
scanf("%d",&t);
while(t--)
scanf("%d %d",&n,&m);
for(int i=0;i&n;i++)
scanf("%s",a[i]);
int flag = 0;
for(int i=0;i&n;i++)
for(int j=0;j&m;j++)
if(a[i][j]=='#')
for(int k=1;k&=n-1-i;k++)
if(i+k&=n || j+k&=n)
if(slove(i,j,k))
puts("YES");
puts("NO");
阅读(...) 评论()