比赛地址：https://www.hpuoj.com/contest/16/
赛后总结：
代码基本功真的很重要！简单题总是不能一发过，模拟总是会出细节问题，debug花很长时间，天梯赛也是，大模拟总是卡在小细节上卡到心态爆炸。还是要多练，巩固基础。还有，数学好差，求极限都忘了。。。。
题目解析：
A
签到题
B
二进制转十六进制 模拟 倒着遍历 四位换一位 不足补0
代码（赛时代码 比较丑）
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<math.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+7;
char s[maxn];
typedef struct{
char ch[5];char c;
}node;
node a[20];
int w;
char q[maxn];
void check(int x){
char r[5];
r[0]=s[x-3]; r[1]=s[x-2]; r[2]=s[x-1]; r[3]=s[x];
for(int i=1;i<=16;i++){
if(a[i].ch[0]==r[0]&&a[i].ch[1]==r[1]&&a[i].ch[2]==r[2]&&a[i].ch[3]==r[3]){
q[w++]=a[i].c;break;
}
}
return ;
}
int T;
int main(){
scanf("%d",&T);
strcpy(a[1].ch,"0000");a[1].c='0';
strcpy(a[2].ch,"0001");a[2].c='1';
strcpy(a[3].ch,"0010");a[3].c='2';
strcpy(a[4].ch,"0011");a[4].c='3';
strcpy(a[5].ch,"0100");a[5].c='4';
strcpy(a[6].ch,"0101");a[6].c='5';
strcpy(a[7].ch,"0110");a[7].c='6';
strcpy(a[8].ch,"0111");a[8].c='7';
strcpy(a[9].ch,"1000");a[9].c='8';
strcpy(a[10].ch,"1001");a[10].c='9';
strcpy(a[11].ch,"1010");a[11].c='a';
strcpy(a[12].ch,"1011");a[12].c='b';
strcpy(a[13].ch,"1100");a[13].c='c';
strcpy(a[14].ch,"1101");a[14].c='d';
strcpy(a[15].ch,"1110");a[15].c='e';
strcpy(a[16].ch,"1111");a[16].c='f';
while(T--){
scanf("%s",s);
int l=strlen(s);
for(int i=l-1;i>=0;){
if(i-3>=0){check(i);i=i-4;}
else{
char r[5];int j;
for(j=3;i>=0;i--){r[j]=s[i];j--;}
while(j>=0){r[j]='0';j--;}
for(int k=1;k<=16;k++){
if(a[k].ch[0]==r[0]&&a[k].ch[1]==r[1]&&a[k].ch[2]==r[2]&&a[k].ch[3]==r[3]){
q[w++]=a[k].c;break;
}
}
}
}
for(int i=w-1;i>=0;i--){
printf("%c",q[i]);
}
w=0;//多组数据 需要初始化
printf("\n");
}
return 0;
}
C
这题不难 思维题
由于障碍物不同行也不同列 所以只有下图这种 封死了的情况 才会NO
障碍物坐标排个序 判断下有没有这样的序列
代码
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
int T,x,y,n,m;
typedef struct{
int xx,yy;
}node;
node d[10007];
bool cmp(node a,node b){
return a.xx<b.xx;
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
int v[10];
memset(v,0,sizeof(v));
for(int i=0;i<m;i++){
scanf("%d%d",&d[i].xx,&d[i].yy);
}
sort(d,d+m,cmp);
int f=0;
if(d[0].xx==1){
for(int i=1;i<m;i++){
if(d[i].xx==d[i-1].xx+1&&d[i].yy==d[i-1].yy-1){
if(d[i].yy==1) {
f=1;break;
}
}
else break;
}
}
if(f==1){
printf("No\n");
}
else printf("Yes %d\n",n+n-2);
}
return 0;
}
D
不会写
E
我开了个二维数组，52行（26+26） 两列（一个存最小距离 一个存遍历到的位置）
遍历字符串 更新每个字符的最小距离 以及位置
代码：
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
typedef long long ll;
const int maxn=1e6+7;
using namespace std;
int dp[60][3];
char s[maxn];
int v[60];
int main(){
scanf("%s",s);
int l=strlen(s);
int x;
for(int i=1;i<=52;i++)dp[i][1]=-1;
for(int i=0;i<l;i++){
if(s[i]>='a'&&s[i]<='z') x=s[i]-'a'+1;
else x=s[i]-'A'+1+26;
v[x]=1;
if(dp[x][1]==-1) dp[x][1]=i;
else{
int cha=i-dp[x][1];
if(cha<dp[x][0]||dp[x][0]==0)dp[x][0]=cha;
dp[x][1]=i;
}
}
for(int i=1;i<=52;i++){
if(!v[i]) continue;
if(i<=26)printf("%c:",i-1+'a');
else printf("%c:",i-1-26+'A');
if(dp[i][0]==0)printf("0\n");
else{
printf("%d\n",l-dp[i][0]);
}
}
return 0;
}
F
最后还有一个半小时的时间，模拟多项式写了两遍都写炸了，可能是到最后了，脑子不清楚吧，随后这个题要补
基本功还是太差。。。
G
没看题 过的人挺多的 随后看看
H
矩形面积并 不会写 套了个板子。。。。内疚ing+自责ing
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int SIZE=505;
int add[SIZE<<2];
double x[SIZE<<2],sum[SIZE<<2];
struct node{
int ss;
double l,r,h;
node(){}
node(double a,double b,double c,int d):l(a),r(b),h(c),ss(d){}
friend bool operator<(node p,node q){
return p.h<q.h;
}
}s[SIZE];
void pushup(int rt,int l,int r){
if(add[rt])
sum[rt]=x[r+1]-x[l];
else if(l==r)
sum[rt]=0;
else
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void update(int L,int R,int c,int l,int r,int rt){
int m;
if(L<=l&&r<=R){
add[rt]+=c;
pushup(rt,l,r);
return;
}
m=(l+r)>>1;
if(L<=m)
update(L,R,c,l,m,rt<<1);
if(R>m)
update(L,R,c,m+1,r,rt<<1|1);
pushup(rt,l,r);
}
int main(){
int n,i,k,l,m,r,cas;
double a,b,c,d,ans;
cas=1;
k=1,ans=m=0;
for(i=0;i<2;i++){
scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
x[m]=a;
s[m++]=node(a,c,b,1);
x[m]=c;
s[m++]=node(a,c,d,-1);
}
sort(x,x+m);
sort(s,s+m);
for(i=1;i<m;i++)
if(x[i]!=x[i-1])
x[k++]=x[i];
memset(add,0,sizeof(add));
memset(sum,0,sizeof(sum));
for(i=0;i<m-1;i++){
l=lower_bound(x,x+k,s[i].l)-x;
r=lower_bound(x,x+k,s[i].r)-x-1;
update(l,r,s[i].ss,0,k-1,1);
ans+=(sum[1]*(s[i+1].h-s[i].h));
}
printf("%.0f",ans);
return 0;
}
I
防AK 那没多大佬都没过 我就不用看了。。。。
J
水题 递归转预处理 O(1)查询
K
贪心
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
typedef long long ll;
const int maxn=1e5+7;
ll a[maxn];
using namespace std;
ll n,m;
int main(){
scanf("%lld%lld",&n,&m);
m=m*n;
ll sum=0;
for(int i=0;i<n;i++){
scanf("%lld",&a[i]);
sum+=a[i];
}
sort(a,a+n);
int cnt=0;
for(int i=0;i<n;i++){
if(sum>=m){
printf("%d\n",cnt);break;
}
sum+=1000-a[i];cnt++;
}
return 0;
}
L
最小生成树 Kruscal
我先把修好的边加进去 然后没修的 排序 加边并且计算权值和 最后扫一遍并查集 是不是都加进去了
wa了test19 因为 求和需要开longlong
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
#define INF 0x3f3f3f3f
int fa[maxn];
int init(int n){
for(int i=0;i<=n;i++)fa[i]=i;
}
int Find(int x){
return fa[x]==x?x:fa[x]=Find(fa[x]);
}
int Union(int a,int b){
int p1=Find(a),p2=Find(b);
fa[p2]=p1;
}
typedef struct edge{
int from,to,val;
}dege;
edge Edge[maxn];
edge dd[maxn];
bool cmp(edge a,edge b){
return a.val<b.val;
}
int n,m,s;
int main(){
scanf("%d%d%d",&n,&m,&s);
init(n);
for(int i=0;i<m;i++){
scanf("%d%d%d",&dd[i].from,&dd[i].to,&dd[i].val);
Union(dd[i].from,dd[i].to);
}
for(int i=0;i<s;i++){
scanf("%d%d%d",&Edge[i].from,&Edge[i].to,&Edge[i].val);
}
sort(Edge,Edge+s,cmp);
ll ans=0;
for(int i=0;i<s;i++){//依次选择最小的
if(Find(Edge[i].from)!=Find(Edge[i].to)){
Union(Edge[i].from,Edge[i].to);
ans+=Edge[i].val;
}
}
int cnt=0;
for(int i=1;i<=n;i++){
if(fa[i]==i)cnt++;
}
if(cnt>1) printf("Concubines can't do it.");
else printf("%lld",ans);
return 0;
}
京公网安备 11010502036488号