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

1.小明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

[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

[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

[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

[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.

[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

[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]