还是太菜了啊，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; } |