时隔9个月，终于想起补题了
编程题
A. 卡片（5分）
答案：3181
分析： 简单题，直接从1开始处理每一个数，直到出现某一种卡片不够为止。
#include
using namespace std;
int main(){
int cnt[10],ans=1,flag=1;
for(int i=0;i<=9;i++) cnt[i]=2021;
while(flag){
int x=ans;
while(x){
int y=x%10; cnt[y]--;
if(cnt[y]<0) flag=0;
x/=10;
}
if(!flag) break;
ans++;
}
cout< return 0; } B. 直线（5分） 答案：40257 分析： 通过两点式我们知道（x-x1)/(x2-x1)=(y-y1)/(y2-y1)。将x1= =x2和y1==y2的情况分离出来单独讨论，显然这种情况的结果是20+21，其它的通过化简可知最后的直线方程为 (y2-y1)* x+(x1-x2)* y+(x2* y1-x1* y2)。只要我们求出了三个参数A=y2-y1，B=x1-x2以及C=x2* y1-x1* y2，我们便可以化简后放在一个容器中vector中，然后再将容器vector放在集合set中，最后的结果就是集合的大小+20+21。 #include using namespace std; inline int gcd(int a,int b){ if(b==0) return a; return a%b?gcd(b,a%b):b; } struct Point{ int x,y; }; set vector int main(){ int ans,m=20,n=21; for(int i=0;i for(int j=0;j for(int i=0;i for(int j=i+1;j Point p1=e[i],p2=e[j]; int x1=e[i].x,y1=e[i].y,x2=e[j].x,y2=e[j].y; if(x1==x2||y1==y2) continue; int a=y2-y1,b=x1-x2,c=x2*y1-x1*y2; int temp=gcd(a,gcd(b,c)); vector f.push_back(b/temp); f.push_back(c/temp); s.insert(f); } } ans=s.size()+m+n; cout< return 0; } C.货物摆放（10分） 答案：2430 分析： 一个10的16次方的数，它的因子数最多不超过两百，所以我们可以用O(sqrt(n))的时间复杂度求出它的所有的因子（个数假设为x），然后直接三重循环O(x^3) 遍历每一种情况，要是符合则cnt++。 #include using namespace std; typedef long long ll; int main(){ ll n=2021041820210418,cnt=0; vector for(ll i=1;i*i<=n;i++){ if(n%i==0) { g.push_back(i); g.push_back(n/i); } } for(int i=0;i for(int j=0;j for(int k=0;k if(g[i]*g[j]*g[k]==n) cnt++; } } cout< return 0; } D.路径（10分） 答案：10266837 分析： 很显然是一道Dijkstra算法的模板题。由于节点个数n=2021，所以最普通的时间复杂度为O(n^2)的Dijkstra算法就可以得出结果；当然我习惯使用优先队列优化后的时间复杂度为O(mlog n)的Dijkstra算法。以下题解为优化后的算法。而对于两个数a和b的最小公倍数来说，我们可以通过求出最大公因数gcd(a,b)，然后最小公倍数lcm(a,b)便是a*b/gcd(a,b)。 #include using namespace std; #define INF 0x7fffffff const int maxn=1e4+10; typedef long long ll; struct Edge{ int v,w; bool operator < (const Edge&b)const{ return w>b.w; } }; ll d[2050],vis[2050]; vector inline gcd(int a,int b){ return a%b?gcd(b,a%b):b; } inline lcm(int a,int b){ return a*b/gcd(a,b); } void Dijkstar(){ priority_queue q.push({1,0}); d[1]=0; while(!q.empty()){ Edge x=q.top();q.pop(); int u=x.v; if(vis[u]) continue; vis[u]=1; for(int i=0;i int v=g[u][i].v,w=g[u][i].w; if(d[u]+w d[v]=d[u]+w; q.push({v,d[v]}); } } } cout< } int main(){ int n=2021; for(int i=1;i<=2021;i++) d[i]=INF,vis[i]=0; for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ if(j-i<=21) {g[i].push_back({j,lcm(j,i)});g[j].push_back({i,lcm(j,i)});} } } Dijkstar(); return 0; } E. 回路计数（15分） 答案：881012367360 分析： 一道很难的状压DP。 f[i][j]用来表示以结点j结尾得到状态i的方案数。状态i的二进制表示即目前已经过的结点。 #include using namespace std; #define INF 0x3f3f3f3f #define endl '\n' #define rep(i,a,n) for(int i=a;i<=n;i++) #define PII pair #define pb(x) push_back(x) typedef long long LL; const int maxn=1e5+100; const int N=1e5+100; const int mod=1e9+7; int n=21,m=(1< LL ans=0; LL f[(1<<22)][24],a[30][30]; int gcd(int a,int b){ return b?gcd(b,a%b):a; } int main(){ memset(a,0,sizeof(a)); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(gcd(i,j)==1) a[i][j]=1; } } f[1][1]=1; for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ if(i&(1<<(j-1))){ for(int k=1;k<=n;k++){ if(a[j][k]&&((1< } } } } for(int i=1;i<=n;i++) ans+=f[m][i]; cout< return 0; } F. 砝码称重（15分） 分析： 第一道编程题，肯定不会太难，直接暴力。 由于砝码的总重量w为1~100000，我们可以开一个标记数组visit[100010]，记录是否某一个重量 i 可以达到。由于砝码的个数n为1~100，我们可以遍历每一个砝码，并且开通辅助动态数组vector< int > g,g用来存储现在可以称出的重量 。对每一个砝码进行以下三种处理： 1. 只称当前砝码重量，若未标记则加入g中。 2. 将当前砝码重量与g中每一个可能出现的砝码放在不同的两边，即重量相减，并取绝对值，若未标记则加入g中。 3. 将当前砝码重量与g中每一个可能出现的砝码放在同一边，即重量相加，若未标记则加入g中。 时间复杂度为：O(n*w) #include #include #include #include using namespace std; #define INF 0x7fffffff const int maxn = 1e5 + 10; int a[105]; bool visit[maxn]; vector int main(){ int n; cin >> n; for (int i = 1; i <= maxn-10; i++) visit[i] = false; for (int i = 1; i <= n; i++) cin >> a[i]; sort(a + 1, a + 1 + n); g.push_back(a[1]); visit[a[1]] = true; for (int i = 2; i <= n; i++) { int len=g.size(); for (int j = 0; j < len; j++) { int temp1 = a[i], temp2 = abs(a[i] - g[j]), temp3 = a[i] + g[j]; if (temp1 > 0 && !visit[temp1]) visit[temp1] = true, g.push_back(temp1); if (temp2 > 0 && !visit[temp2]) visit[temp2] = true, g.push_back(temp2); if (temp3 > 0 && !visit[temp3]) visit[temp3] = true, g.push_back(temp3); } } cout << g.size(); return 0; } G. 异或数列（20分） 分析： 一道位运算的题。首先，假设Alice的最后数字为A,Bob是B,如果是平局的话，那么A= =B,即A^B==0 。所以当所有的输入进行异或结果是0的话，则平局，否则不是平局。 我们用一个数字cnt[maxn]来记录二进制从高位到低位的每一个数字出现次数；不难发现，若最高位只出现一次，结果一定是Alice赢，因为Alice先手。 其他情况我们分开讨论： 1. 若最高位出现奇数次，且n为奇数：则一定是先手赢 2. 若最高位出现奇数次，且n为偶数，则一定是后手赢 3. 若最高位出现偶数次，则分析次高位，以此类推。 #include using namespace std; typedef long long ll; const int maxn=1e5+10; int cnt[maxn]; int main() { int t; cin>>t; while(t--){ memset(cnt,0,sizeof(cnt)); int n,ans=0; cin>>n; for(int i=1;i<=n;i++){ int x; cin>>x; for(int i=0;i<20;i++){ if(x&(1< } ans=ans^x; } bool flag=false; if(ans==0) cout<<0< else{ for(int i=19;i>=0;i--){ if(cnt[i]==1) { ans=1; break; } else if(cnt[i]&1){ if(n&1) ans=1; else ans=-1; break; } else continue; } cout< } } return 0; } H.左孩子右兄弟（20分） 分析： 一道简单深搜（dfs）题。对于每一棵子树的父节点u而言，他的最大长度就是子树v的个数加上它所有子树中所能达到的最大长度;所以我们只需要对每一个子节点dfs一次，记录它的最大长度，最后结果相加即可。 时间复杂度：O(n) #include using namespace std; typedef long long ll; const int maxn=1e5+10; vector int ans=0; int dfs(int u){ int res=0; for(int i=0;i int v=g[u][i]; res=max(res,dfs(v)); } res+=g[u].size(); return res; } int main() { int n;cin>>n; for(int i=2;i<=n;i++){ int x; cin>>x; g[x].push_back(i); } cout< return 0; } I.括号序列（25分） 相关阅读
您阅读本篇文章共花了：
发表评论