链接：http://acm.hdu.edu.cn/listproblem.php?vol=56来源：hdu 6555-6566

文章目录

The Fool(规律)The World(模拟)Justice(思维)The Hermit(思维)Strength(贪心)

The Fool(规律)

  题意：判断所给表达式的奇偶性  思路：打表发现1-3为奇数，4-8为偶数，9-15为奇数，16-24为偶数，25-35为奇数

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; const int Max_n=5e4+10; int a[Max_n]; int main(){ /**for(int i=1;i<=100;i++){ ll ans=0; for(int j=1;j<=i;j++){ ans+=i/j; } if(ans%2==1) printf("%d ",i); if(i==0) printf("\n"); }*/ int T; scanf("%d",&T); for(int i=1;i<=T;i++){ int n;scanf("%d",&n); int ans=sqrt(n); printf("Case %d: ",i); if(ans%2) printf("odd\n"); else printf("even\n"); } return 0; }

The World(模拟)

  题意：给了一些地方的时间，我们输入一个时间，输入两个字符串，第一个代表本地时间，第二个代表要转换成的城市的时间。输出转换后的时间。  思路：一开始用12小时制，同时判断AM/PM和天数是否发生了改变，这样过于复杂，我们可以把我们得到的时间先转换成24小时制，然后我们根据24小时制判断天数是否发生了变化，最后判断是否这个时间是上午还是下午，输出即可。

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; const int Max_n=5e4+10; int val[5]; map<char,int>m; map<int,int>m1[5]; void init(){ m['B']=1;val[1]=8; m['W']=2;val[2]=-5; m['L']=3;val[3]=0; m['M']=4;val[4]=3; for(int i=1;i<=4;i++){ for(int j=1;j<=4;j++){ m1[i][j]=val[j]-val[i]; } } } int main(){ int T;init(); cin>>T;getchar(); for(int i=1;i<=T;i++){ char a[20],b[20],c[20]; cin.getline(a,20); cin.getline(b,20); cin.getline(c,20); int hh;string time,mm; if(a[2]==':'){ hh=(a[0]-'0')*10+a[1]-'0'; time[0]=a[6];time[1]=a[7]; mm[0]=a[3];mm[1]=a[4]; }else{ hh=a[0]-'0'; time[0]=a[5];time[1]=a[6]; mm[0]=a[2];mm[1]=a[3]; } if(time[0]=='A'&&hh==12) hh=0; if(time[0]=='P'&&hh!=12) hh+=12; string day; int valb=m[b[0]],valc=m[c[0]]; if(m1[valb][valc]==0){ day="Today"; }else if(m1[valb][valc]>0){ hh+=m1[valb][valc]; if(hh>=24){ hh-=24; day="Tomorrow"; }else{ day="Today"; } }else{ hh+=m1[valb][valc]; if(hh<0){ hh+=24; day="Yesterday"; }else{ day="Today"; } } if(hh==0){ hh=12; time[0]='A'; }else if(hh>0&&hh<12){ time[0]='A'; }else if(hh==12){ time[0]='P'; }else{ hh-=12; time[0]='P'; } cout<<"Case "<<i<<": "; cout<<day<<" "<<hh<<":"<<mm[0]<<mm[1]<<" "<<time[0]<<time[1]<<endl; } return 0; }

Justice(思维)

  题意:给你n个数，第i个数为k[i]，如果把每个数变成1/2^k[i]，我们把这些数一共分成两组，问这两组数能否全部大于等于1/2。  思路：我们可以发现，如果要满足题意的话，对于其中的一组，我们需要1个1(1/2),2个2(1/4),4个3(8/1)，8个4(1/16)，1个1(1/2)就是2个2(1/4),1个2就是2个(1/4)，那么我们就可以用cnt1，cnt2分别表示两个组个需要多少个now，刚开始的时候，全部初始化为1，表示两个组分别需要1(1/2)1个，我们对输入的数组排序，然后遍历数组，如果数组中剩余数的个数>=cnt1+cnt2，说明能够凑够那么多数满足题意，否则就不能凑够输出NO，如果能够凑够还要满足当前需要的数是什么，如果当前需要的数发生改变，那么两组需要这个数的数量也需要发生改变。

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; const int Max_n=1e5+10; int vis[Max_n]; struct Node{ int val,pos; bool operator<(const Node &a)const{ if(pos!=a.pos) return val<a.val; return pos<a.pos; } }a[Max_n]; int main(){ int T; scanf("%d",&T); for(int cnt=1;cnt<=T;cnt++){ int n; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i].val); a[i].pos=i; } bool flag=true; sort(a+1,a+n+1); int cnt1=1,cnt2=1,now=1;//当前1每组各需要多少 for(int i=1;i<=n;i++){ while(cnt1+cnt2<=n-i+1&&now<a[i].val){//当前够这么多数，并且修改当前数需要的数量 cnt1*=2;cnt2*=2; now++; } if(cnt1+cnt2>n-i+1){ flag=false; break; } if(cnt1){ cnt1--;vis[a[i].pos]=1; }else{ cnt2--;vis[a[i].pos]=0; } if(!cnt1&&!cnt2) break; } printf("Case %d: ",cnt); if(!flag) printf("NO\n"); else{ printf("YES\n"); for(int i=1;i<=n;i++) printf("%d",vis[i]); printf("\n"); } } return 0; }

The Hermit(思维)

  题意：给我们n个电台，每个电台有一个值rad_i，每个电台能够发射信号的范围是[i-rad_i+1,i+rad_i-1]，我们下面的信号为完美信号，k<i并且k能够接收i点的信号，k<=j<i,k和j能够接收到i的信号，并且k到j的距离一定大于等于j到i的距离，问所有电台有的完美信号的个数异或和的结果是什么。  思路：题意表示：i+rad_i-1 >= i-rad_i+1,我们可以得到rad_i>=1，从而得到i+rad_i-1>=i，根据题意我们可以找到的完美信号一定在i的左边，并且这个电台和它前面一个电台一定不是完美信号，剩下的都是完美信号。那么我们就可以计算完美信号的个数:i-(i-a[i]+1)+1-2,就得到了对于每个电台完美信号的个数为：a[i]-2，如果这个数小于零说明没有完美信号，反之则有a[i]-2个完美信号。

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; const int Max_n=1e6+10; ll a[Max_n]; int main(){ int T; scanf("%d",&T); for(int cnt=1;cnt<=T;cnt++){ int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); ll ans=0; for(int i=1;i<=n;i++){ if(a[i]-2<0) a[i]=0; else ans^=a[i]-2; } printf("Case %d: ",cnt); printf("%lld\n",ans); } return 0; }

Strength(贪心)

  题意：Alice和Bob玩游戏，这个游戏是这样的，Alice有n只怪兽，Bob有m只怪兽，Alice的怪兽可以攻击Bob的怪兽，但是Bob有些怪兽处于防御状态。这个游戏的掉血规则如下：怪兽攻击力大的一方获胜，并且这个怪兽的攻击力不变，弱的一方怪兽消失，并且输的一方掉血为两只怪兽攻击力的差值，如果某一方怪兽处于防御状态，那么这只怪兽只能被摧毁，输的一方不掉血。  思路：我们有两种选择：第一种：我们不管防御的怪兽，直接去攻击没有防御的怪兽。第二种：摧毁所有有防御的怪兽，然后去攻击没有防御的怪兽。最后比较两种情况的最大值即可。

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; const int Max_n=1e5+10; int a[Max_n]; struct Node{ int val,status; bool operator<(const Node &a)const{ if(status==a.status) return val<a.val; return status<a.status; } }b[Max_n]; int main(){ int T; scanf("%d",&T); for(int cnt=1;cnt<=T;cnt++){ int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=m;i++) scanf("%d",&b[i].val); for(int i=1;i<=m;i++) scanf("%d",&b[i].status); sort(a+1,a+n+1,greater<int>()); sort(b+1,b+m+1); int index=-1;//记录怪兽是否防御的临界点 ll ans1=0,ans2=0; for(int i=1;i<=m;i++){ if(b[i].status){ index=i-1; } if(!b[i].status&&i==m){ index=m; } }//直接攻击没有防御的怪兽 for(int i=1;i<=index;i++){ if(a[i]>b[i].val) ans1+=(ll)(a[i]-b[i].val); } //Bob没有怪兽可用，那么可以直接攻击Bob if(index==m){ for(int i=index+1;i<=n;i++) ans1+=(ll)a[i]; } sort(a+1,a+n+1); int j=n; bool flag=true; //摧毁所有怪兽的防御 for(int i=m;i>=index+1;i--){ if(a[j]>=b[i].val) j--; else{flag=false;break;} if(j<0){flag=false;break;} } //如果全部摧毁，则可以攻击无防御的怪兽 if(flag){ //攻击没有防御的怪兽 for(int i=1;i<=index;i++){ if(a[j]>b[i].val){ ans2+=(ll)(a[j]-b[i].val); j--; } } //如果Bob没有怪兽可用，可以直接攻击Bob for(int i=1;i<=j;i++) ans2+=(ll)a[j]; } //输出二者中最大的即可 printf("Case %d: ",cnt); printf("%lld\n",max(ans1,ans2)); } return 0; }