还是太菜了啊,120名GG,D题想了一个多小时影响了后面题思考时间,中间过程还需反思,先把做题时的思考过程记录一下,题解等后续补题后再完善
A 数字
100分,直接100~999暴力枚举即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#include<bits/stdc++.h> using namespace std; typedef long long LL; LL aa,b,len; int ans; int main() { scanf("%lld%lld",&aa,&b); LL x=aa; while (x) ++len,x/=10; for (int i=100;i<=999;++i) { x=(LL)(i)*(LL)pow(10,len)+aa; if (x%b==0) ++ans; } return printf("%d",ans),0; } |
B 网格
100分,这题卡了一小会,一开始想的是贪心地走魔法格子,把贪心的判断条件写错了,后来发现贪心并不是最优解,我们需要的是全局最优,也就是针对一个序列,选择最长上升子序列,因为k值最大是2000,直接上的DP即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#pragma GCC optimize(3) #include<bits/stdc++.h> using namespace std; typedef long long LL; int n,k,w1,w2,dp[2010]; struct data { int X,Y; }a[2010]; LL ans; bool cmp(data x,data y) { return x.X==y.X?x.Y<y.Y:x.X<y.X; } int main() { scanf("%d%d%d%d",&n,&k,&w1,&w2); for (int i=1;i<=k;++i) scanf("%d%d",&a[i].X,&a[i].Y),dp[i]=1; if (w2>=2*w1) ans=(LL)n*(LL)w1*2LL; else { int count=0; sort(a+1,a+k+1,cmp); for (int i=k;i;--i) for (int j=i+1;j<=k;++j) if (a[j].X>a[i].X && a[j].Y>a[i].Y) dp[i]=max(dp[i],dp[j]+1); for (int i=1;i<=k;++i) count=max(count,dp[i]); ans=(LL)count*(LL)w2+((LL)2*n-(LL)count*2)*(LL)w1; } return printf("%lld",ans),0; } |
C 有向无环图
60分,直接枚举构造,不牵扯边之间的复用,后续补题解
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include<bits/stdc++.h> using namespace std; typedef long long LL; int N; LL k; int n,m,s[100010],t[100010],tot; LL a[21]={0,1,2,4,9,24,76,279,1156,5296,26443,142418,820988,5034585,} void solve1() { n=1000,s[++tot]=1,t[tot]=1000,--k,++m; for (int i=2;i<n;++i) { s[++tot]=1,t[tot]=i,s[++tot]=i,t[tot]=n,m+=2,--k; if (k==0) break; } cout<<n<<" "<<m<<endl; for (int i=1;i<=tot;++i) cout<<s[i]<<" "<<t[i]<<endl; } void solve2() { } int main() { scanf("%lld%d",&k,&N); if (k==1 && N==2) cout<<"2 1\n1 2"; else if (k==3 && N==4) cout<<"4 5\n1 4\n1 2\n1 3\n2 4\n3 4"; else if (k<=500 && N==1000) solve1(); else solve2(); return 0; } |
UPD.其实是一道水题啊→_→,考场上手玩5个点数错数了,要不然肯定能想到规律的
我们发现每个点往后面点连的时候,假如所有有向无环图全部边都连接,设除了1和n以外的所有中间点的个数为x,则最终路径数为,通过手玩我们可以找到每个中间点对答案的贡献,故我们可以根据k的二进制来决定每个中间点是否向n连边,另外k的范围应该在unsigned long long范围内,会爆long long
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include<bits/stdc++.h> using namespace std; typedef unsigned long long LL; int N; LL k; int n,m,s[100010],t[100010],tot; void solve1() { n=1000,s[++tot]=1,t[tot]=1000,--k,++m; for (int i=2;i<n;++i) { s[++tot]=1,t[tot]=i,s[++tot]=i,t[tot]=n,m+=2,--k; if (k==0) break; } cout<<n<<" "<<m<<endl; for (int i=1;i<=tot;++i) cout<<s[i]<<" "<<t[i]<<endl; } void solve2() { int i=0; n=N; while (k) { if (k&1) s[++tot]=i+2,t[tot]=N,++m; k>>=1,++i; } --i; for (int j=2;j<=i+2;++j) s[++tot]=1,t[tot]=j,++m; for (int j=2;j<i+2;++j) for (int k=j+1;k<=i+2;++k) s[++tot]=j,t[tot]=k,++m; cout<<n<<" "<<m<<endl; for (int i=1;i<=tot;++i) cout<<s[i]<<" "<<t[i]<<endl; } int main() { scanf("%llu%d",&k,&N); if (k==1 && N==2) cout<<"2 1\n1 2"; else if (k==3 && N==4) cout<<"4 5\n1 4\n1 2\n1 3\n2 4\n3 4"; else if (k<=500 && N==1000) solve1(); else solve2(); return 0; } |
D 分数
100分,其实一开始思路没有错只是没有想得太全面,O(n)的欧拉筛筛素数,然后分情况讨论,任意整数可被质因数唯一分解,我们手玩前20个数发现,像16这种分解出来是这种,在筛的时候循环首先是在i循环到8时,prime[j]为2的时候把16这个合数筛掉的,然而在8时的q为2,说明还需要乘以2,我们可以得到结论如果除以最小质因子的q值等于该最小质因子而不为1时说明我们这里的q值也为该最小质因子,这是特殊的情况,另外平方数的q值也是最小质因子,除了以上两种情况如果合数能够表示为两个质因子的乘积的形式,说明这里q值为1,最后直接统计答案即可,时间复杂度O(n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#pragma GCC optimize(3) #include<bits/stdc++.h> using namespace std; typedef long long LL; #define N 5000000 #define MAXN 80000000 #define mod (LL)4294967296 int n,prime[N],tot,num[MAXN]; LL a,b; bool vis[MAXN]; int main() { scanf("%d%lld%lld",&n,&a,&b); for (int i=1;i<=n;++i) num[i]=i; for (int i=2;i<=n;++i) { if (!vis[i]) prime[++tot]=i; for (int j=1;j<=tot && i*prime[j]<=n;++j) { vis[i*prime[j]]=true; if (i==prime[j]) num[i*prime[j]]=i; else if (!vis[i]) num[i*prime[j]]=1; else if (num[i]==prime[j]) num[i*prime[j]]=prime[j]; else num[i*prime[j]]=1; if (i%prime[j]==0) break; } } for (int i=1;i<=n;++i) if (num[i]!=1) a=(a*(LL)num[i]%mod+b)%mod; return printf("%lld",a),0; } |
E 树数数
20分暴力,后续补题解
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#include<bits/stdc++.h> using namespace std; typedef long long LL; #define N 200010 int n,m,cnt,h[N],father[N],son[N],color[N],a[N],tot,deep[N]; vector<int>G[N]; void dfs1(int x) { for (int i=0;i<G[x].size();++i) deep[G[x][i]]=deep[x]+1,dfs1(G[x][i]); } void dfs2(int x) { son[++tot]=x; for (int i=0;i<G[x].size();++i) dfs2(G[x][i]); } int lca(int x,int y) { if (deep[x]<deep[y]) swap(x,y); while (deep[x]>deep[y]) x=father[x]; while (x!=y) x=father[x],y=father[y]; while (!color[x]) { if (x==1) break; x=father[x],y=father[y]; } return x; } LL query(int x) { LL ans=0; memset(son,0,sizeof(son)),tot=0,dfs2(x); for (int i=1;i<tot;++i) for (int j=i+1;j<=tot;++j) { int y=lca(son[i],son[j]); if (color[y]==1) ans+=(LL)a[y]; } return ans; } int main() { int x,y; char s[3]; scanf("%d%d",&n,&m); for (int i=2;i<=n;++i) scanf("%d",&father[i]),G[father[i]].push_back(i); for (int i=1;i<=n;++i) scanf("%d",&a[i]); dfs1(1); while (m--) { scanf("%s%d",s,&x); if (s[0]=='Q') printf("%lld\n",query(x)); if (s[0]=='F') color[x]=1; if (s[0]=='M') scanf("%d",&y),a[x]=y; } return 0; } |