题解
蓝桥杯第一次参赛
蓝桥杯第二次参赛
第一年,国三,今年河南省一中游吧,目前一直准备考研,当时都没怎么准备,都是靠以前基础来打,cb填空就对了一个五分,大题做的差不多吧,估分也就60多貌似。总结一下,填空真的拉裤,第一题不是不会写,少除了1024(基础不扎实,没办法),还有最后一题用BellF也写出来了,就是当时傻逼题意读错了,以为是求多源最短路,大题前两道做出来了,后面都是骗分。国赛估计也不会去训练了,xcpc老师也让参加,因为大三考研,没时间搞了,结果也没那么重要了,hh,哎,就是打着玩
来复盘一下hh
后面几道都是暴力,待更新hh
第十二届省赛
C直线
考试的时候没想到精度问题,实际上保存斜率和截距。然后因为是double,就需要通过fabs(k1-k2)>1e-8来判断不同的直线
#include <bits/stdc++.h>
#define pb push_back//vector,deque
#define INF 0x3f3f3f3f
#define scd(n) scanf("%d",&n)
#define prd(n) printf("%d",n)
using namespace std;
typedef long long ll;
const int N=1e6+5;
pair<double,double>pi[N];
int cot;
int main() {
int x=20,y=21;
for(int i=0;i<x;i++){
for(int j=0;j<y;j++){
for(int k=0;k<x;k++){
for(int m=0;m<y;m++){
int x1=i,y1=j,x2=k,y2=m;
if(x2-x1==0)continue;
double kk=(double)(y2-y1)/(x2-x1);
double b=y2-kk*x2;
pi[cot++]=make_pair(kk,b);
}
}
}
}
int res=1;//假设以k来找k={1,1,2,3,3,5}=1,2,3,5所以一开始res=1
sort(pi,pi+cot);
for(int i=1;i<cot;i++){
if(fabs(pi[i].first-pi[i-1].first)>1e-8||fabs(pi[i].second-pi[i-1].second)>1e-8)
res++;
}
cout<<res+x<<'\n';
return 0;
}
D货物摆放
把约数求出来进行组合,约数个数很小,所以 O ( n 3 ) O(n^3) O(n3)可做
#include <bits/stdc++.h>
#define pb push_back//vector,deque
#define INF 0x3f3f3f3f
#define scd(n) scanf("%d",&n)
#define prd(n) printf("%d",n)
using namespace std;
typedef long long ll;
void solve()
{
int t;
cin>>t;
while(t--){
}
}
int cot;
int main() {
ll n=2021041820210418;
vector<ll>v;
for(ll i=1;i*i<=n;i++){
if(n%i==0){
v.push_back(i);
if(n/i!=i)v.push_back(n/i);
}
}
int res=0;
for(auto a:v){
for(auto b:v){
for(auto c:v){
if(a*b*c==n)res++;
}
}
}
cout<<res<<'\n';
// for(auto it:v){
// cout<<it<<'\n';
// }
return 0;
}
E 路径
我人傻了,我理解成多源最短路了。跑半天跑不出来,原来就是简单地求1到2021的最短路径。BF自己写了,算出来了,最后填了个错的,我tm服了自己
#include <bits/stdc++.h>
#define pb push_back//vector,deque
#define INF 0x3f3f3f3f
#define scd(n) scanf("%d",&n)
#define prd(n) printf("%d",n)
using namespace std;
typedef long long ll;
const int N=1e5+5;
int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);
}
struct node{
int u,v,w;
};
vector<node>e;
int dis[2025];
void init()
{
for(int i=1;i<=2021;i++){
for(int j=i+1;j<=2021;j++){
if(abs(i-j)<=21){
e.push_back({i,j,i*j/gcd(i,j)});
e.push_back({j,i,i*j/gcd(i,j)});
}
}
}
cout<<e.size()<<'\n';
}
void BF(int n)
{
for(int i=1;i<=n;i++)dis[i]=0x3f3f3f3f;
dis[1]=0;
for(int i=1;i<=n-1;i++){
for(int j=0;j<e.size();j++){
int u=e[j].u,v=e[j].v,w=e[j].w;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
}
}
}
cout<<dis[2021]<<'\n';
}
void solve()
{
int t;
cin>>t;
while(t--){
}
}
int main() {
// solve();//10266837
init();
BF(2021);
return 0;
}
G 砝码称重
牛客上的一道题,记得是某高校的校赛,只是求的不一样。不过也是原题了hhh
#include<bits/stdc++.h>
using namespace std;
int f[500005],a[505];
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
f[0]=1;
for(int i=0;i<n;i++){
for(int j=500000;j>=a[i];j--)
f[j]|=f[j-a[i]];
}
for(int i=0;i<n;i++){
for(int j=0;j+a[i]<=500000;j++)
f[j]|=f[j+a[i]];
}
int res=0;
for(int i=1;i<=500000;i++)
if(f[i]){
res++;
//cout<<i<<'\n';
}
cout<<res<<'\n';
return 0;
}
J括号序列
相似题:传送门
hhh不会写这题
class Solution {
public:
int minAddToMakeValid(string S) {
int left=0,right=0;
for(auto it:S){
if(it=='(')
left++;
else left --;
if(left==-1){
right++;
left=0;
}
}
return left+right;
}
};
第十二届国赛
待更新hhh