整體來說，比賽到一半的時候感徑訓好，也就是填空時間用的挺多，感覺代碼量挺大的，可能是我思路太復雜？但到了后面心態挺炸的，腦子里亂亂的，集中不了注意力，可能還是因為最近沒怎么刷題吧，嗚嗚嗚，最后留了倆題基本沒做，回憶一下題目，手里沒題面也沒代碼，只能靠回憶想一下賽中的思路、代碼和題目，做的代碼、答案可能也是錯的，反正僅供參考吧，
更新了題面
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都難跑出來吧，但確實沒時間了…
代碼
這么暴力的代碼不想再寫一遍了
等著有時間仔細想想這題，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/278124.html
標籤：其他