刷刷刷——蒟蒻的刷水题计划(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]

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注