整体来说,比赛到一半的时候感觉还好,也就是填空时间用的挺多,感觉代码量挺大的,可能是我思路太复杂?但到了后面心态挺炸的,脑子里乱乱的,集中不了注意力,可能还是因为最近没怎么刷题吧,呜呜呜,最后留了俩题基本没做。回忆一下题目,手里没题面也没代码,只能靠回忆想一下赛中的思路、代码和题目,做的代码、答案可能也是错的,反正仅供参考吧。

更新了题面

省一了!

<>A 卡片

<>题目描述

分别给出2021个0-9,问从一开始最多能拼到几。

<>思路简述

简单模拟

<>代码
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef
unsigned long long uLL; const int inf=0x3f3f3f3f; const int maxn=1e5+5; const
int N=6e6+5; const LL mod=998244353; const double pi=acos(-1); int n,ans,cnt[15]
,f=1; int main() // 3181 { scanf("%d",&n); //2021 for(int i=0;i<=9;i++) cnt[i]=n
; for(int i=1;i<=inf&&f;i++) { int now=i; while(now) { if(cnt[now%10]) cnt[now%
10]--; else f=0; now/=10; } if(f) ans=i; } printf("%d\n",ans); return 0; }
<>参考结果

3181

<>B 直线

<>题目描述

二维平面给出20*21个点,问构成的直线数。

<>思路简述

我是两两枚举点,再用set去重记录y=kx+b,x=a,这两种直线,最后结果就是s.size();
赛后写的代码输出结果 48953;赛中 57561…
我感觉写的一模一样的。可能都错了?估计是爆精度了吧。

<>代码
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef
unsigned long long uLL; const int inf=0x3f3f3f3f; const int maxn=5e6+5; const
int N=1e7+15; const LL mod=998244353; const double eps=1e-7; const double pi=
acos(-1); int n,m; struct node{ double k,b; node(double kk,double bb) { k=kk,b=
bb; } friend bool operator < (node x,node y){ if(fabs(x.k-y.k)<eps) return x.b<y
.b; return x.k<y.k; } }; set<node>s; void solve(int a,int b,int c,int d) { if(a
==c&&b==d) return; if(a==c)//x=a; { if(s.find(node(1.0*inf,1.0*a))!=s.end())
return; s.insert(node(1.0*inf,1.0*a)); } else //y=kx-ka+b; { double kk=1.0*(d-b)
/(c-a); double bb=1.0*kk*a-b; if(s.find(node(kk,bb))!=s.end()) return; s.insert(
node(kk,bb)); } } int main() //20 21 { scanf("%d%d",&n,&m); for(int a=0;a<n;a++)
for(int b=0;b<m;b++) for(int c=0;c<n;c++) for(int d=0;d<m;d++) solve(a,b,c,d);
printf("%d\n",s.size()); return 0; }
<>参考结果

48953 ? 应该错了

<>C 货物摆放

<>题目描述

给定n=2021041820210418(队友提醒才知道是日期),求分成 a ∗ b ∗ c a*b*c a∗b∗c的方案数
比如 n=4的时候
1 1 4;1 4 1;1 1 4;1 2 2;2 1 2;2 2 1 六种分法

<>思路简述

刚拿到这题,感觉数好大,但想了一下分解之后应该没什么很大的质数,就写了因数分解,分解之后是
2021041820210418
2 3 3 3 17 131 2857 5882353
那后面就是写搜索了,还需要写个set去重。

<>代码
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef
unsigned long long uLL; const int inf=0x3f3f3f3f; const int maxn=5e6+5; const
int N=1e7+15; const LL mod=998244353; const double pi=acos(-1); struct node{ int
a,b,c; node(int aa,int bb,int cc) { a=aa,b=bb,c=cc; } friend bool operator < (
node x,node y){ if(x.a==y.a) { if(x.b==y.b) return x.c<y.c; return x.b<y.b; }
return x.a<y.a; } }; set<node>s; LL n,x[5]; int cnt,prime[maxn],res; bool
is_prime[N],f[maxn]; vector<LL>mid; void __prime() { for(int i=1;i<=N-5;i++)
is_prime[i]=1; is_prime[1]=0; for(int i=2;i<=N-5;i++) if(is_prime[i]) { prime[++
cnt]=i; for(int j=i;j<=N-5;j+=i) is_prime[j]=0; } } /* 2021041820210418 2 3 3 3
17 131 2857 5882353 */ void fen(){ LL now=n; for(int i=1;i<=cnt;i++) while(n%
prime[i]==0) n/=prime[i],mid.push_back(1LL*prime[i]); } void dfs(int ff,int now,
LL mul) { if(now==mid.size()) { x[ff]=mul; if(ff==1) { x[2]=n/x[1]/x[0]; if(s.
find(node(x[0],x[1],x[2]))!=s.end()) return; s.insert(node(x[0],x[1],x[2])); res
++; } else dfs(ff+1,0,1); return; } if(f[now]==0) { f[now]=1; dfs(ff,now+1,mul*
mid[now]); f[now]=0; dfs(ff,now+1,mul); } else dfs(ff,now+1,mul); } int main() {
__prime(); scanf("%lld",&n); fen(); for(int i=0;i<mid.size();i++) printf("%d ",
mid[i]); printf("\n"); dfs(0,0,1); printf("%d\n",res); return 0; }
<>参考结果

2430

<>D 路径

<>问题描述

两数绝对值之差小于等于21有边,边权为lcm(i,j);
一共有2021一个点
问从1到2021的最短路

<>思路简述

模拟建图,后面直接跑最短路就行。
我队友赛前还跟我说Bellon-Ford来着

结果他写了弗洛伊德哈哈哈哈哈哈
太秀了

<>代码
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef
unsigned long long uLL; const int inf=0x3f3f3f3f; const int maxn=1e5+5; const
int N=6e6+5; const LL mod=998244353; const double pi=acos(-1); int gcd(int a,int
b){ if(b==0) return a; return gcd(b,a%b); } struct node{ int u,v,w; node(int uu
,int vv,int ww) { u=uu,v=vv,w=ww; } }; int n,dis[maxn]; vector<node>g; int main(
) { scanf("%d",&n); for(int i=1;i<=n;i++) dis[i]=inf; dis[1]=0; for(int i=1;i<=n
;i++) for(int j=i+1;j<=n;j++) { if(j-i>21) continue; g.push_back( node( i , j ,
i*j/gcd(i,j) ) ); } for(int i=1;i<=n-1;i++) { bool f=0; for(int j=0;j<g.size();j
++) { int u=g[j].u,v=g[j].v,w=g[j].w; if(dis[v]>dis[u]+w) f=1,dis[v]=dis[u]+w; }
if(f==0) break; } printf("%d\n",dis[n]); return 0; }
<>参考结果

10266837

<>E 回路计数

没做,本来以为能做的,想着做做大题回来,结果后面做炸了,一去不返。

马上更马上更,在写了在写了
写大题的时候心态有点崩,感觉题意可能读的都有问题。
大题题意好像真不记得了。。。
只能大体想起来思路和代码,也不知道读没读对题

<>F 砝码称重

<>问题描

有一个天平和一堆砝码,砝码可以放左边也可以放右边。他现在知道每个砝码的重量。问根据上述条件,能测出多少组不同的重量。

<>思路简述

动态规划?
感觉就是写了简单的递推,直接看代码就好了

重要的点是要存下来-sum到sum吧,所以下标都加sum。

<>代码
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef
unsigned long long uLL; const int inf=0x3f3f3f3f; const int maxn=1e3+5; const
int N=3e5+5; const LL mod=998244353; const double pi=acos(-1); vector<int>mid;
int n,res,a[maxn],sum,f[N]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++)
scanf("%d",&a[i]),sum+=a[i]; for(int i=1;i<=n;i++) { mid.clear(); mid.push_back(
sum+a[i]); mid.push_back(sum-a[i]); for(int j=0;j<=2*sum;j++) if(f[j]) { if(j-a[
i]>=0) mid.push_back(j-a[i]); mid.push_back(j+a[i]); } for(int j=0;j<mid.size();
j++) f[mid[j]]=1; } for(int i=sum+1;i<=2*sum;i++) if(f[i]) res++; printf("%d\n",
res); return 0; }
<>G 异或数列

<>问题描述

题意说错了别打我,那说明我也读错了

A和B两个人在玩游戏,初始时两人分别有一个数a、b,给出一个数组x,每回合轮到的那人可以做两种操作,选出来一个数异或a或者异或b,每个数只能用一次。A先手,多组输入输出。
在最优策略下,选完所有数,谁的数大谁赢,否则平局。

<>思路简述

把所有数按二进制表示,按位计数。如果最高位只有一个的话,肯定先手的A赢了,如果最高位有两个的话,应该去找次高位。所以就只和数位的奇偶有关,但按这样想先手的A根本不会输啊,我也不知道是不是想得太简单了。。阿巴阿巴阿巴,太菜了。

错了
先手必输样例 2 2 2 1
省一无了

<>代码
#include<bits/stdc++.h> //样例都没得测 using namespace std; typedef long long LL;
typedef unsigned long long uLL; const int inf=0x3f3f3f3f; const int maxn=1e5+5;
const int N=6e6+5; const LL mod=998244353; const double pi=acos(-1); int cnt[30]
,bit[30],n,t,x; int solve() { for(int i=25;i>=0;i--) if(cnt[i]%2) return 0*
printf("1\n"); return 0*printf("0\n"); } int main() { scanf("%d",&t); for(int i=
0;i<=25;i++) bit[i]=1<<i; while(t--) { scanf("%d",&n); memset(cnt,0,sizeof(cnt))
; for(int i=1;i<=n;i++) { scanf("%d",&x); for(int i=25;i>=0;i--) if(x>=bit[i]) x
-=bit[i],cnt[i]++; } solve(); } return 0; }
<>H 左孩子右兄弟

<>问题描述

把一颗树按照左儿子右兄弟转化成二叉树。树的根高度为0,求转化之后二叉树的最高高度。

<>思路简述

构造、树的递归遍历

<>代码

数据范围、样例和题目细节都想不起来了,代码仅供参考
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int
inf=0x3f3f3f3f; const int maxn=2e5+5; int n; vector<int>g[maxn]; int dfs(int u)
{ int mx=0,sz=g[u].size(); for(int i=0;i<sz;i++) mx=max(mx,dfs(g[u][i])+sz-1);
return mx+1; } int main() { scanf("%d",&n); for(int i=2,u;i<=n;i++) { scanf("%d"
,&u); g[u].push_back(i); } printf("%d\n",dfs(1)-1); return 0; }
<>I 括号序列

最气的一道题,一直感觉自己能做,写了一个多小时,还是没的写,最后简化成许多取值的线段取点的题。
比如样例 ((()
最后出来就是从[1,2]、[1,3]两线段上取两个点的方案数,分别是(1,1),(1,2),(1,3),(2,2),(2,3)五种。
再比如(((()

就是从[1,2]、[1,3]、[1,4]上取点,分别是(1,1,1),(1,1,2),(1,1,3),(1,1,4),(1,2,2),(1,2,3),(1,2,4),(1,3,3),(1,3,4),(2,2,2),(2,2,3),(2,2,4),(2,3,3),(2,3,4)十四种。
但就是不知道怎么推出来公式,最后打表都没推出来,绝了,最后写了个爆搜。写完这题的暴力就剩不到半小时了,还有J和E没碰。

不想写这道题…

<>J 分果果

<>问题描述

分糖果
n种糖果,m个人,每种糖果最多分两次,最少分一次,每个人都要分到,且只能分到连续的糖果。

<>思路简述

没时间了,看完题还剩十来分钟,写了最暴力的暴力

爆搜
初始化cnt数组都是2

搜的时候枚举起点终点,再遍历看一下起点到终点,出现cnt[i]=0这组起点终点就不合法,合法的话就继续搜,一直递归完m个人,在从1到n判断一下cnt[i]==2也不合法,爆搜所有情况求个res=min(res,mx-mn)

时间复杂度已经不敢想了
可能n=10都难跑出来吧,但确实没时间了…

<>代码

这么暴力的代码不想再写一遍了
等着有时间仔细想想这题。

技术
©2019-2020 Toolsou All rights reserved,
Vue.js入门(五)---在vue中使用echarts词云Pandas统计分析基础_数据处理(DataFrame常用操作)element UI dialog点击dialog区域外会关闭dialog应届毕业生看过来!Java面试经典77问,看完离工作就不远了关于蓝桥杯大赛,你应该了解的那些事!mysql 分区-key分区(五)海康威视-嵌入式软件笔试题PHP Redis 监听过期的 key 事件C语言循环语句笔记详解以及练习-折半查找算法、猜数字游戏JVM概述