月度归档:2016年01月

刷刷刷——蒟蒻的刷水题计划(2)

1.小明A+B

题目戳这里

另类的A+B

[cpp]
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>

using namespace std;
int a,b,Case;
int main()
{
while(scanf("%d",&Case)!=EOF){
while(Case–){
a=a%100;
b=b%100;
printf("%d",(a+b)%100);
}
}
}
[/cpp]

 

poj 3069 Saruman’s Army

题目戳这里

贪心的思想,把输入的左边先进行排序,找到最左边的点为起点,那么从该点开始往右距离为R以内的最远点,应该就是需要标记的点。那么把该点标记后,继续向右直到距离标记过的点超过了R,那么下一个点就是新的起点。看了书上的思路,感觉更清晰。

[cpp]
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#define maxn 1010
using namespace std;
int n,r;
int x[maxn];
void solve()
{
sort(x,x+n); //按照从左到右排序
int i=0,ans=0;
while(i<n){
int s=x[i++]; //最左端点的位置
while(i<n&&x[i]<=s+r) i++;
i–;
int t=x[i];
while(i<n&&x[i]<=t+r) i++; //找到距离t大于R的第一个点
ans++;
}
printf("%dn",ans);
}
int main()
{
while(scanf("%d %d",&r,&n)==2&&r!=-1&&n!=-1){
for(int i=0;i<n;i++)
scanf("%d",&x[i]);
solve();
}
}
[/cpp]

poj 3253 Fence Repair

题目戳这里

采用的是贪心的策略,切割的方法可以用二叉树来描述。每个叶子节点对应了切割出的一块块木板,叶子节点的深度对应所需切割的次数。因为要求最小的开支合计,所以最优解应该是最短板为深度最大的叶子节点之一,次短板为它的兄弟节点。所以可以通过递归的方式从最深处的叶子节点退回根(也就是只剩一块板的时候)。一开始图省事快排TLE了,想想其实根本不用排序。

[cpp]
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#define maxn 20010
using namespace std;
typedef long long ll;
int n,l[maxn];
ll sum,ans;
int main()
{
while(scanf("%d",&n)!=EOF){
for(int i=0;i<n;i++) {scanf("%d",&l[i]);sum+=l[i];} ans=0; while(n>1){
int mii1=0,mii2=1;
if(l[mii1]>l[mii2]) swap(mii1,mii2);
for(int i=2;i<n;i++){
if(l[i]<l[mii1]){
mii2=mii1;
mii1=i;
}
else if(l[i]<l[mii2]) {
mii2=i;
}
}
int t=l[mii1]+l[mii2];
ans+=t;
l[mii1]=t;
l[mii2]=l[n-1];
n–;
}

printf("%I64dn",ans);
}
}
[/cpp]

不过再查一下发现每一次都是自己写的比较出来最小的两个值,这样复杂度还是有些高。可以通过优先队列,保证越小的值优先级越高即可。
优先队列方法:

[cpp]
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <cstring>
#include <queue>

#define maxn 20010
using namespace std;
typedef long long ll;
int n,l[maxn];
ll sum,ans;
int main()
{
while(scanf("%d",&n)!=EOF){
memset(l,0,sizeof(l));
for(int i=0;i<n;i++) scanf("%d",&l[i]);
ans=0;
priority_queue<int,vector<int>,greater<int> > que; //优先最小
for(int i=0;i<n;i++) que.push(l[i]); while(que.size()>1){
int a=que.top();
que.pop();
int b=que.top();
que.pop();
ans+=a+b;
que.push(a+b);
}
printf("%I64dn",ans);
}
}
[/cpp]

poj 2431 Expedition
题目戳这里

同样的一道优先队列的题目,但是因为自以为输入是有序的所以WA了N次才知道数据不一定有序。定义了一个结构体来存储加油站距离起点的距离和油量。虽说在加油站才可以加油,但是在路上每路过一个加油站我们可以视为在之后的任何时候都可以加相应i单位的油。当油量为0的时候,才选择加油。同时我们应该选择油量最大的加油站,因此优先队列直接上。

[cpp]
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cctype>
#define maxn 10010
using namespace std;
struct Stop{
int pos;
int amout;
}stop[maxn];
int a[maxn];
bool cmp(Stop a,Stop b)
{
return a.pos<b.pos;
}
int n,l,p;
int main()
{
while(scanf("%d",&n)!=EOF){
memset(a,0,sizeof(a));
memset(stop,0,sizeof(stop));
bool flag=true;
for(int i=0;i<n;i++)
scanf("%d %d",&a[i],&stop[i].amout);
scanf("%d %d",&l,&p);
for(int i=0;i<n;i++){
stop[i].pos=l-a[i]; //距起点的距离
}
stop[n].pos=l;
stop[n].amout=0; //把终点视为一个加油站,现有n+1个油站
n+=1;
sort(stop,stop+n,cmp); //按照距离起点的距离排序
priority_queue<int>que;
int apos=0,tank=p,cnt=0;
for(int i=0;i<n;i++){
int d=stop[i].pos-apos;
while(tank<d){ //现有的油不够用
if(que.empty()){
flag=false;
break;
}
else{
tank+=que.top();
que.pop();
cnt++; //又加了一次油
}
}
if(!flag) break;
tank-=d;
apos=stop[i].pos; //移动到下一个加油站
que.push(stop[i].amout);

}
if(!flag) puts("-1");
else printf("%dn",cnt);
}
}
[/cpp]

uva 272

题目戳这里

[cpp]
#include <stdio.h>

int main()
{
int c,flag=1;
while((c=getchar())!=EOF){
if(c==’"’){
if(flag)
printf("%s","");
else printf("”");
flag=!flag;
}
else printf("%c",c);
}
return 0;
}[/cpp]

uva 10082

题目戳这里

[cpp]
#include <stdio.h>
char s[]="`1234567890-=QWERTYUIOP[]\ASDFGHJKL;’ZXCVBNM,./";
int main()
{
char c;
int i;
while((c=getchar())!=EOF){
for(i=0;i<sizeof(s)/sizeof(char)&&s[i]!=c;i++);
if(s[i]==c) printf("%c",s[i-1]);//判断是否因找到而跳出循环
else printf("%c",c);
}
return 0;
}[/cpp]

uva 401

题目戳这里

通过字符常量数组解决镜像转化。

[cpp]
#include <iostream>
#include <cctype>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;
const char rev[40]="A 3 HIL JM O 2TUVWXY51SE Z 8 ";
const string msg[4]={" — is not a palindrome."," — is a regular palindrome."," — is a mirrored string."," — is a mirrored palindrome."};
char change(char ch)
{
if(isalpha(ch)) return rev[ch-‘A’];
else return rev[ch-‘0’+25];
}
int main()
{
string s;
while(cin>>s){
int len=s.length();
int huiwen=1,jingxiang=1;
for(int i=0;i<(len+1)/2;i++){
if(s[i]!=s[len-i-1]) huiwen=0;
if(change(s[i])!=s[len-1-i]) jingxiang=0;
}
if(huiwen&&jingxiang) {cout<<s<<msg[3]<<endl;cout<<endl;}
else if(huiwen&&!jingxiang) {cout<<s<<msg[1]<<endl;cout<<endl;}
else if(!huiwen&&jingxiang) {cout<<s<<msg[2]<<endl;cout<<endl;}
else {cout<<s<<msg[0]<<endl;cout<<endl;}
}
return 0;
}
[/cpp]

uva 340

题目戳这里

答对位置的个数很容易计算出来,记为A。接下来比较答案和猜测的数组中1-9各个数字的个数,取最小值为数字在两个字符串中都出现的个数。减去A即可。

[cpp]
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#define maxn 1010
using namespace std;
int a[maxn],b[maxn]; //a答案,b猜测
int n;
int main()
{
int cas=1;
while(scanf("%d",&n)!=EOF&&n){
printf("Game %d:n",cas++);
for(int i=0;i<n;i++) scanf("%d",&a[i]);
while(1){
int A=0,B=0;
for(int i=0;i<n;i++){
scanf("%d",&b[i]);
if(a[i]==b[i]) A++;
}
if(b[0]==0) break; //全为0跳出循环
for(int i=1;i<=9;i++){
int c1=0,c2=0; //c1统计a中某个数字的个数,c2统计b中某个数字的个数
for(int j=0;j<n;j++){
if(a[j]==i) c1++;
if(b[j]==i) c2++;
}
B+=min(c1,c2);
}

printf(" (%d,%d)n",A,B-A);
}
}
}
[/cpp]

uva 1583

题目戳这里

预先打表查找。

[cpp]
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define maxn 100010
using namespace std;
int a[maxn];
int x;
int main()
{
int t;
for(int m=1;m<maxn;m++){ //打表
int sum=m,tmp=m; while(tmp>0){
sum+=tmp%10;
tmp/=10;
}
if(sum<maxn&&a[sum]==0) a[sum]=m;
}
while(scanf("%d",&t)!=EOF){
while(t–){
scanf("%d",&x);
printf("%dn",a[x]);
}
}
}
[/cpp]

 

Java的对象和类的一些笔记

1.尽量不要编写返回引用可变对象的访问器方法。这样会破坏封装性。举一个例子。

[java]
class Employee
{
private Date hireDay;

public Date getHireDay(){
return Date hireDay;
}

}
[/java]

如果我们现在执行下面的语句

Date d=tom.getHairday();,这时候d和tom.hireday引用了同一个对象,对d调用更改器方法,就会修改我们本来封装起来的数据。所以如果需要返回一个可变对象的引用,应该对它进行克隆。上面的访问器方法中的return语句需要修改一下return hireDay.clone();

2.final修饰符对于可变的类,例如final Date birthday这仅仅意味着birthday这个引用不能再重新指向一个新new出的Date类对象,我们可以通过setTime更改器方法修改birthday引用的对象的值。

3.Java的方法参数都是传值引用,这也就意味着通过方法调用我们无法修改基本类型数据变量的值。但是我们可以通过方法改变一个对象参数的状态,但是一个方法并无法让对象参数引用一个新的对象,这一点和C、C++的指针很不同。

4.如果类中提供了至少一个构造方法,但是没有提供无参数的构造方法。此时如果我们在构造对象的时候没有提供参数,就会被视为非法。

5.调用构造器(构造方法)的具体步骤:

1).所有数据都被初始化为默认值。

2).按照在类声明的顺序,依次执行所有域初始化语句和初始化块。

3).如果构造器第一行调用了第二个构造器,则执行第二个构造器主体。

4).执行这个构造器的主体

6.如果把域声明为static,每个类则只有这一个域。也就是说这个域不属于任何对象,只属于这个类。每一个对象的对于所有的实例域都有一份自己的拷贝,但是这些对象却共享静态域。只有在类第一次加载的时候才会初始化静态域。

7.标记为public的部分可以被任意的类使用,标记为private的部分只可以被定义它们的类使用,如果没有被指定public或者private,这个部分可以被同一个包的所有方法访问。

刷刷刷——蒟蒻的刷水题计划(1)

hoj 1684 Symmetric Order

In your job at Albatross Circus Management (yes, it’s run by a bunch of clowns), you have just finished writing a program whose output is a list of names in nondescending order by length (so that each name is at least as long as the one preceding it). However, your boss does not like the way the output looks, and instead wants the output to appear more symmetric, with the shorter strings at the top and bottom and the longer strings in the middle. His rule is that each pair of names belongs on opposite ends of the list, and the first name in the pair is always in the top part of the list. In the first example set below, Bo and Pat are the first pair, Jean and Kevin the second pair, etc.

Input

The input consists of one or more sets of strings, followed by a final line containing only the value 0. Each set starts with a line containing an integer, n, which is the number of strings in the set, followed by n strings, one per line, sorted in nondescending order by length. None of the strings contain spaces. There is at least one and no more than 15 strings per set.  Each string is at most 25 characters long.

Output

For each input set print “SET n on a line, where n starts at 1, followed by the output set as shown in the sample output.

Sample Input

Sample Output

[cpp]
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;

int main()
{
int n,T=1;
while(cin>>n&&n){
printf("SET %dn",T++);
string s[n];
for(int i=0;i<n/2;i++){
cin>>s[i];
cin>>s[n-i-1];
}
if(n%2==1) cin>>s[n/2];
for(int i=0;i<n;i++){
cout<<s[i]<<endl;
}
}
}
[/cpp]

poj 1852 Ants

Description

An army of ants walk on a horizontal pole of length l cm, each with a constant speed of 1 cm/s. When a walking ant reaches an end of the pole, it immediatelly falls off it. When two ants meet they turn back and start walking in opposite directions. We know the original positions of ants on the pole, unfortunately, we do not know the directions in which the ants are walking. Your task is to compute the earliest and the latest possible times needed for all ants to fall off the pole.

Input

The first line of input contains one integer giving the number of cases that follow. The data for each case start with two integer numbers: the length of the pole (in cm) and n, the number of ants residing on the pole. These two numbers are followed by n integers giving the position of each ant on the pole as the distance measured from the left end of the pole, in no particular order. All input integers are not bigger than 1000000 and they are separated by whitespace.

Output

For each case of input, output two numbers separated by a single space. The first number is the earliest possible time when all ants fall off the pole (if the directions of their walks are chosen appropriately) and the second number is the latest possible such time.

Sample Input

Sample Output

[cpp]
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
int temp[1000010];
int main()
{
int Case;
while(scanf("%d",&Case)!=EOF){
while(Case–){
memset(temp,0,sizeof(temp));
int l,n;
scanf("%d %d",&l,&n);
int minT=0,maxT=0;
for(int i=0;i<n;i++)
scanf("%d",&temp[i]);
/*蚂蚁相遇时可以看成并没有返回而是继续向前走直到端点*/
for(int i=0;i<n;i++)
{
minT=max(minT,min(temp[i],l-temp[i]));
maxT=max(maxT,max(temp[i],l-temp[i]));
}
printf("%d %dn",minT,maxT);
}
}
return 0;
}
[/cpp]

poj 2386 Lake Counting

Description

Due to recent rains, water has pooled in various places in Farmer John’s field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water (‘W’) or dry land (‘.’). Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors.

Given a diagram of Farmer John’s field, determine how many ponds he has.

Input

* Line 1: Two space-separated integers: N and M

* Lines 2..N+1: M characters per line representing one row of Farmer John’s field. Each character is either ‘W’ or ‘.’. The characters do not have spaces between them.

Output

* Line 1: The number of ponds in Farmer John’s field.

Sample Input

Sample Output

Hint

OUTPUT DETAILS:

There are three ponds: one in the upper left, one in the lower left,and one along the right side.

第一次写dfs,从任意的W开始dfs,并且通过递归把与它连通的W也转化为’.’。读取数据的时候有些要注意的地方。。

[cpp]
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#define MAXN 110
#define MAXM 110
using namespace std;
int N,M;
char field [MAXN][MAXM];
void dfs(int x,int y) //深度搜索
{
field[x][y]=’.’;
for(int dx=-1;dx<=1;dx++) //循环遍历八个方向
for(int dy=-1;dy<=1;dy++){
int nx=x+dx,ny=y+dy;
if(0<=nx&&nx<N&&ny>=0&&ny<M&&field[nx][ny]==’W’) dfs(nx,ny);
}
}
int main()
{

while(scanf("%d %d",&N,&M)==2){
getchar(); //读走回车
memset(field,0,sizeof(field));
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
scanf("%c",&field[i][j]); //储存
}
getchar();
}
int ans=0;
for(int i=0;i<N;i++){
for(int j=0;j<M;j++)
{
if(field[i][j]==’W’){ //有积水后开始dfs
dfs(i,j);
ans++;
}
}
}
printf("%dn",ans);
}
}
[/cpp]

hdu 1016 prime ring problme

Problem Description

A ring is compose of n circles as shown in diagram. Put natural number 1, 2, …, n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.

Note: the number of first circle should always be 1.

Input
n (0 < n < 20).
Output

The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. Print solutions in lexicographical order.

You are to write a program that completes above process.

Print a blank line after each case.

Sample Input
6 8
Sample Output
Case 1:
1 4 3 2 5 6
1 6 5 2 3 4
Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2

分析:dfs练习,加上了一些剪枝,还是不够熟练。

[cpp]
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;
int vis[22]; //数组下标代表对应的数字
int num[22]; //环
int n,Case=1;
bool isPrime(int n)
{
bool flag = true;
if(n==2) return true;
for(int i=2;i<=sqrt(n);i++){
if(n%i==0)
{
flag=false;
break;
}
}
return flag;
}
void Print()
{
for(int i=1;i<n;i++) printf("%d ",num[i]);
printf("%dn",num[n]);
}
void dfs(int c) //c代表圆环上的位置
{
if(c>n){
if(isPrime(num[1]+num[n]))
Print();
}
else{
for(int i=2;i<=n;i++){
if(vis[i]) continue; //使用过了的数跳过
if(isPrime(i+num[c-1])){
vis[i]=1;
num[c]=i;
dfs(c+1);
vis[i]=0;
num[c]=0; //恢复至原来情况,该情况已经遍历完
}

}
}
}

int main()
{

while(scanf("%d",&n)!=EOF){
memset(num,0,sizeof(num));
memset(vis,0,sizeof(vis));
vis[1]=1;
num[1]=1;
printf("Case %d:n",Case++);
dfs(2);
printf("n");
}
return 0;
}
[/cpp]

 Poj 3617 best cow line

思路,字典序最小,就是要开头部分的字母尽可能的小,贪心选择左边第一个字母和右边第一个字母中最小的那个,如果二者相同就继续往后面进行选择,直到可以判断…..

[cpp]
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define maxn 2010
using namespace std;
int n;
char s[maxn+1];
void solve()
{
int left=0,right=n-1,cnt=0;
for(int i=1;i<=n;i++){
bool flag=false;
for(int j=0;left+j<=right;j++){
if(s[left+j]<s[right-j]){ flag=true; break; //找到左边字符比右边字符小 }
else if(s[left+j]>s[right-j]){
flag=false;
break;
}
}
if(flag) {printf("%c",s[left++]);cnt++;}
else {printf("%c",s[right–]);cnt++;}
if(cnt%80==0||i==n) printf("n");
}
}
int main()
{
while(scanf("%d",&n)!=EOF){
getchar();
for(int i=0;i<n;i++) {scanf("%c",&s[i]);getchar();}
solve();
}
}
[/cpp]