HDU 1713（相遇周期）求分数的最小公倍数！
题目分析：题目输入c1/t1 c2/t2 ,也就是速度的分数形式，转换成：c1*t2/(t1*t2), c2*t1/( t1*t2 ); 这时候我们只需要求出分子的最小公倍数k,然后k/( t1*t2 )就是题目求的周期
代码+部分注释：
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
__int64 gcd(__int64 a,__int64 b){
__int64 c;
if(a<b){
c=a; a=b;
b=c;
}
while(b){
c=b;
b=a%b;
a=c;
}
return a;
}
__int64 min_times(__int64 x1,__int64 x2){
__int64 c=gcd(x1,x2);
return x1*x2/c;
}
int main(){
__int64 cas,c1,c2,t1;
__int64 t2,p,k,m,n,h;
cin>>cas;
while(cas--){
scanf("%I64d/%I64d",&c1,&t1);
//在这里提醒一下，用long long型的过不了！
//因为这个WA的好多次！
scanf("%I64d/%I64dd",&c2,&t2);
k=t1*t2;
m=t2*c1;
n=t1*c2;
p=min_times(m,n);
h=gcd(p,k);
if(h==k){
printf("%I64d\n",p/h);
}
else{
printf("%I64d/%I64d\n",p/h,k/h);
}
}
return 0;
}
HDU 2138(求素数的个数，容易超时！提醒自己)
题目分析：这里不能打表，然后要用到求素数的 优化!也就是我 前面一篇文章提到的。代码直接注释一下就可以了 还是看代码吧
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
bool prime(int x){
if(x%2==0&&x!=2)
return false;
//偶数肯定不是素数！
double k=sqrt(x);
//切记这里一定要用k记录他的开方
//如果写成for(int i=3;i*i<=x;i+=2)
//就超时！
for(int i=3;i<=k;i+=2)//枚举奇数！
if(x%i==0)
return false;
return true;
}
int main(){
int cas,n,flag,ans=0;
while(~scanf("%d",&cas)){
ans=0;
while(cas--){
scanf("%d",&n);
if(prime(n))
ans++;
}
printf("%d\n",ans);
}
return 0;
}
ZOJ 3498(Javabeans)
题目分析：把每个盒子看成集合。有n个集合，分别有1…n个元素。具体每种集合有多少个是没意义的，因为我们可以把具有相同元素的集合同时操作，所以我们可以用集合的种类代替集合的个数。假设，每次选取k个集合。从这k个集合里拿东西，则这k个集合拿过之后还是k个不同的集合（有可能有一个成空集），所以至少还有(k-1)个不同的集合，而除这k个外还有(n-k)个不同的集合。所以拿完之后不同集合的个数至少变为了r=max(k-1,n-k)。考虑当n是偶数时当k=n/2时，r取最小值，max(k-1,n-k)=n/2，当n为奇数时，k=(n+1)/2时,r取最小值max(k-1,n-k)=(n-1)/2。这个最小值是剩余集合数的一个下界。
其实这个下界是可以达到的：
n是偶数时，从元素个数不少于n/2的全部集合里都拿n/2个，则，剩余集合元素个数变为了1,2……n/2，问题规模缩小了一半。
n是奇数时，从元素个数不少于(n+1)/2的集合里都拿(n+1)/2个，则剩余集合元素个数变为了1,2,…(n-1)/2，问题规模也缩小了一半。
而在c语言中，除以2是下取整的，所以无论n为奇数还是偶数，一次操作之后集合个数至少变成了n/2,并且有办法可以达到这个最小值。
于是，最少拿的次数就是每次把n不断除以2，除到0为止。即n的2进制表示
代码：
#include<iostream>
#include<cstdio>
typedef long long ll;
int main(){
ll n,ans,times;
scanf("%lld",×);
while(times--){
scanf("%lld",&n);
ans=0;
while(n){
ans++;
n/=2;
}
printf("%lld\n",ans);
}
return 0;
}
HDU 1492（求一个数的倍数）
题目大意：
首先 2，3，5，7是互质的！可以把 N 写成 (2^a)*(3^b)*(5^c)*(7^d) （a,b,c,d >= 0）!
每次从a ,b,c,d中选出一组数就是一个因数
举例说明一下：12=2^2*3
因为1也是他的倍数！2能够构成的倍数有（1，1*2,2*2） 3构成的倍数有（1，1*3）
也就是把（a+1）*(b+1)*....(n+1)就是能整除他的个数
代码+部分注释：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int pri[5];
long long times[5];
int pricount(long long num){
pri[1]=2;
pri[2]=3;
pri[3]=5;
pri[4]=7;
memset(times,0,sizeof(times));
long long i;
for(i=1;i<=4;i++){
while(num%pri[i]==0){
times[i]++;
num/=pri[i];
}
}
return 0;
}
int main(){
long long n,sum;
long long i;
while(cin>>n,n){
sum=1;
pricount(n);
for(i=1;i<=4;i++)
sum=sum*(times[i]+1);
//注意要+1，上面已经分析了！
cout<<sum<<endl;
}
}
HDU 1496（求多次方程的个数）
再2重循环把s = c*x3*x3+d*x4*x4 看做下标，开始查找，如果有hash[1000000-s]跟他对应，说明他们两个值加起来等于0，即为方程的解。因为解可正可负，所以最后要乘16（2的四次方）！
代码+部分注释：
#include<iostream>
#include<cstring>
#include<stdio.h>
using namespace std;
int a,b,c,d,ans;
int s[2000000];
int solve(){
int i,j;
if((a>=0&&b>=0&&c>=0&&d>=0)||(a<=0&&b<=0&&c<=0&&d<=0))
return 0;
memset(s,0,sizeof(s));
//初始化放在这里 可以避免TLE因为，如果解不合法就没必要
//初始化，7位数的初始化 很可怕的！
for(i=1;i<=100;i++)
for(j=1;j<=100;j++)
s[1000000+(a*i*i+b*j*j)]+=1;
for(i=1;i<=100;i++)
for(j=1;j<=100;j++)
ans+=s[1000000-(c*i*i+d*j*j)];
return 0;
}
int main(){
while(scanf("%d %d %d %d",&a,&b,&c,&d)!=EOF){
ans=0;
solve();
printf("%d\n",ans*16);
}
return 0;
}
USTC 1151（Shortest Subsequence）
题目大意：题意很简单,就是在一串数字中找到一个子串,使得这个子串包含 1~n 的每一个数至少一次且长度最短。解法复
杂度是 O(n)的,做一次从左往右的扫描即可
题目分析：这道题刚开始不知道怎么做，后来请教别人 然后看完解题报告终于明白这个精妙的维护过程！
首先在sim[]数组里存放各个输入的数据，flag[i],表示i在子串里出现的次数！然后用两个指标i,j分别从第一位扫描！
在这里j是代表一个子串的开头，i代表一个子串的结尾，用i遍历完一次就可以求出最短子串，
for i : 1->t
1） 如果sim[i]是1~n里的数，进一步判断他是不是第一次出现在这个子串里，如果是total++（total是记录有多少个1～n里的数出现过的变量）
然后把 flag [ sim[ i ] ] + 1(不管是不是第一次出现，这里都要+1！),
2) 在j不超过i的前提下，对j的位置进行优化，首先如果j位上的数在子串里出现了2次或者2次以上说明我们最短子串里不需要包括
j位上的数，把j向右移动一位。
3） 判断子串里是不是包括里所有1~m里的数，并且判断这个子串的长度是不是比上一个满足条件的子串短，如果两个条件都满足，我们分别更新记录最短子串的开头和结尾的两个变量：sn,en；
源程序+部分注释：
#include<iostream>
#include<cstdio>
using namespace std;
int sim[1000020],n,t;
bool init(){
scanf("%d %d",&n,&t);
if(n==0&&t==0)
return false;
for(int i=1;i<=t;i++)
scanf("%d",∼[i]);
return true;
}
void solve(){
int i,j,sn,en,total;
sn=1; en=t;
int flag[5020]={};
total=0;
for(i=1,j=1;i<=t;i++){
if(sim[i]>=1&∼[i]<=n){
if(flag[sim[i]]++==0)
total++;
}
while(j<=i){
if(flag[sim[j]]==1)
break;
flag[sim[j]]--;
j++;
}
if(total==n&&i-j<en-sn){
sn=j;
en=i;
}
}
if(en==t)
printf("-1\n");
else
printf("%d %d\n",en-sn+1,en);
}
int main(){
while(init()){
solve();
}
return 0;
}
单调队列
一直弄不明白单调队列是什么，在网上也找不到易懂的介绍。最后结合别人博客上的介绍和程序看才理解是怎么回事。
我们从最简单的问题开始：
给定一个长度为N的整数数列a(i),i=0,1,...,N-1和窗长度k.
要求：
f(i) = max{a(i-k+1),a(i-k+2),..., a(i)},i = 0,1,...,N-1
问题的另一种描述就是用一个长度为k的窗在整数数列上移动，求窗里面所包含的数的最大值。
解法一：
很直观的一种解法，那就是从数列的开头，将窗放上去，然后找到这最开始的k个数的最大值，然后窗最后移一个单元，继续找到k个数中的最大值。
这种方法每求一个f(i),都要进行k-1次的比较，复杂度为O(N*k)。
那么有没有更快一点的算法呢？
解法二：
我们知道，上一种算法有一个地方是重复比较了，就是在找当前的f(i)的时候，i的前面k-1个数其它在算f(i-1)的时候我们就比较过了。那么我们能不能保存上一次的结果呢？当然主要是i的前k-1个数中的最大值了。答案是可以，这就要用到单调递减队列。
单调递减队列是这么一个队列，它的头元素一直是队列当中的最大值，而且队列中的值是按照递减的顺序排列的。我们可以从队列的末尾插入一个元素，可以从队列的两端删除元素。
1.首先看插入元素：为了保证队列的递减性，我们在插入元素v的时候，要将队尾的元素和v比较，如果队尾的元素不大于v,则删除队尾的元素，然后继续将新的队尾的元素与v比较，直到队尾的元素大于v,这个时候我们才将v插入到队尾。
2.队尾的删除刚刚已经说了，那么队首的元素什么时候删除呢？由于我们只需要保存i的前k-1个元素中的最大值，所以当队首的元素的索引或下标小于 i-k+1的时候，就说明队首的元素对于求f(i)已经没有意义了，因为它已经不在窗里面了。所以当index[队首元素]<i-k+1时，将队首 元素删除。
从上面的介绍当中，我们知道，单调队列与队列唯一的不同就在于它不仅要保存元素的值，而且要保存元素的索引（当然在实际应用中我们可以只需要保存索引，而通过索引间接找到当前索引的值）。
为了让读者更明白一点，我举个简单的例子。
假设数列为：8，7，12，5，16，9，17，2，4，6.N=10,k=3.
那么我们构造一个长度为3的单调递减队列：
首先，那8和它的索引0放入队列中，我们用（8，0）表示，每一步插入元素时队列中的元素如下：
0：插入8，队列为：（8，0）
1：插入7，队列为：（8，0），（7，1）
2：插入12，队列为：（12，2）
3：插入5，队列为：（12，2），（5，3）
4：插入16，队列为：（16，4）
5：插入9，队列为：（16，4），（9，5）
。。。。依此类推
那么f(i)就是第i步时队列当中的首元素：8，8，12，12，16，16，。。。
PKU 2192 Zipper 的解题报告
题目分析：题目大致意思是让你判断字符串三是否可以由字符串1,2组合而成，前提是字符串1,2的字母前后顺序不改变。
又是一个动态规划题目，用dp[i][j]表示字符串a的前i个和字符串b的前j个和字符串c的前i+j-1段匹配的逻辑值。分析可知：要求得dp[i][j]，可以划分为两个子问题：1
dp[i-1][j]&&a[i-1]==c[j+i-1] or 2:dp[i][j-1]&&b[j-1]==c[i+j-1]。 如果这两个任何一个可以满足，则dp[i][j]=true;否则dp[i][j]=false.
状态转移方程：dp[i][j]=( (dp[i-1][j]and a[i-1]==c[i+j-1]) or (dp[i][j-1] and b[j-1]==c[i+j-1]) );
源程序：
#include<iostream>
#include<cstring>
using namespace std;
int main(){
char a[201],b[201],c[401];
int dp[201][201];
int n;
cin>>n;
for(int k=1;k<=n;k++){
scanf("%s%s%s",a,b,c);
int len1=strlen(a),len2=strlen(b);
for(int i=0;i<=len1;i++)
for(int j=0;j<=len2;j++)
if(i==0||j==0)
dp[i][j]=1;
else
if( (dp[i-1][j]&&a[i-1]==c[i+j-1]) || (dp[i][j-1] && b[j-1]==c[i+j-1]))
dp[i][j]=1;
else
dp[i][j]=0;
if(dp[len1][len2]==1)
printf("Data set %d: yes\n",k);
else
printf("Data set %d: no\n",k);
}
}
总结：在写代码的时候注意i，j是从0开始遍历到len1,len2，因为计算第一个是以前一个为真为前提的，所以i==0或者j==0时，应该赋真值。
PKU_2081 Recaman's Sequence
题目分析：也属于动态规划的 一个题目，当求得的a[m]为正值并且在前面的序列中未曾出现过 a[m]=a[m-1]-m。反之a[m]=a[m-1]+m；由于处理的数据非常多 非常容易超时，所以必须一次性计算出0<=i<500000内所有a[i]的值，然后输入i的时候直接输出就可以了。
提示：因为数据非常多所以要用个数组记录a[i]是否出现过，切忌用来记录的数组一定要开的大一点 不然你会发现一直编译过不了，出现很奇怪的错误。
源程序：
#include<iostream>
using namespace std;
bool sim[3500000]={false};
int a[500001]={0};
int main(){
int i,s,n;
for(i=1;i<500000;i++){
s=a[i-1]-i;
if(s>0&&!sim[s])
a[i]=s;
else
a[i]=a[i-1]+i;
sim[a[i]]=true;
}
while(cin>>n&&n!=-1)
cout<<a[n]<<endl;
return 0;
}
总结：只要细心点，注意数组开的合适点，还有先把所有的0<=i<500000的都计算好，然后直接读取输出就可以AC了^_^.
PKU 1088滑雪解题报告
题 目分析：这个题目需要求出每个阶段的最大滑雪长度，状态转移的选择条件有两个：一：这个阶段的四个方向的数有比他本身小的，另一个条件：选择出满足条件一 的几个数中滑雪长度最大的那个。这样就完成了一次状态转移。这样不断递推下去就可以求出每个阶段的滑雪最大长度，然后遍历每个节点，找出最大的那个长度就 可以了。
提示：要用到记忆搜索，这样能避免重复递归。
源程序：
#include<iostream>
using namespace std;
int h[101][101];
int sim[101][101];
int r,c;
int dp(int i,int j){
int dir[2][4]={-1,0,1,0,0,1,0,-1};
int m,max=0;//如果上下左右没有一个比自己小，这时候h[i][j]=max+1=1;这就是为什么要把max初始为0。
if(h[i][j]!=0)
return h[i][j];
else{
for(int k=0;k<4;k++){
if(i+dir[0][k]>=0&&i+dir[0][k]<r&&j+dir[1][k]>=0&&j+dir[1][k]<c)
if(sim[i][j]>sim[i+dir[0][k]][j+dir[1][k]]){
m=dp(i+dir[0][k],j+dir[1][k]);
if(max<m)//这个是用来在相邻的四个元素中（有时候没有四个）选择滑雪长度最大的 路径作为h[i][j]的路径。
max=m;
}
else
continue;
}
return max+1;//因为在这里max是上下左右几个元素的最大滑雪长度，而h[i][j]的值为包括了自己，所以要加上1。^_^注意这些相信你会AC了。
}
}
int soulve(){
int max=0;
for(int i=0;i<r;i++)
for(int j=0;j<c;j++){
h[i][j]=dp(i,j);
if(max<h[i][j])
max=h[i][j];
}
return max;
}
int main(){
while(cin>>r>>c){
for(int i=0;i<r;i++)
for(int j=0;j<c;j++){
cin>>sim[i][j];
h[i][j]=0;
}
cout<<soulve()<<endl;
}
}
总结：在这里值得注意的就是，记忆化搜索。在计算每个节点的滑雪最大值时要注意，用于比较上下左右的最大滑雪长度的语句应该紧跟递归其后。