科普基地国庆集训测试题总结
Day1
D1T1 剪刀石头布(stone)
我一开始还真的以为模拟题的D1T1就是真的noipD1T1难度呢，现在想来还是太naive了。
最开始我没有注意到只能取最大或最小，以为都可以取，那么这道题就真的是D1T1难度了。当然，因为两位数要么最大，要么最小，所以这样我们也就解决了40%的点了。
对于每个一位数，直接取完就可以获胜，而只有10可以取到一位数，所以轮到10就输了，而如果要取到10只能选11~19。这样推下去，我们发现：
- 当n%10!=0时，小明肯定会将它取到%10=0来让自己获胜
- 当n%10==0时，小明只能把它取到第一种情况，小头就可以照1中小明的做以获胜
综上，我们得出结论：
当n%10!=0，输出”NO”; 当n%10==0，输出”YES”
然后我很开心地写完了， 很开心的得了40分。
while (t--)
{
n=read();
if (n%10==0) printf("NO\n");
else printf("YES\n");
}
后来讲评的时候发现似乎只有1人AC，还有1人做法和我一样，但他没有看错题，就是铁了心要得40分的。
然后告诉我们正解竟然是搜索？！做法就是直接dfs，因为只要存在一种让小明胜利的方法，小明就一定能胜利（先手真好），所以搜到以后直接退出就行了。WTF？
当然，对于搜到每一个数，结果一定是一样的，所以我们可以用个记忆化来优化。不加记忆化40，加了就A了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
inline int read()
{
char ch=getchar();
int f=1,x=0;
while (ch<'0' || ch>'9')
{
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0' && ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
int n,t,f[1000005];
bool dfs(int x)
{
if (f[x]!=-1) return f[x];
int y=x,mx=0,mn=1e9;
while (y)
{
int res=y%10;
mx=max(mx,res);
if (res) mn=min(mn,res);
y/=10;
}
if (dfs(x-mx) && dfs(x-mn)) f[x]=0;
else f[x]=1;
return f[x];
}
int main()
{
t=read();
memset(f,-1,sizeof(f));
f[0]=0;
while (t--)
{
n=read();
if (dfs(n)) printf("YES\n");
else printf("NO\n");
}
return 0;
}
D1T2 n染色(color)
我在考场上推了整整两张草稿纸也没搞出个什么名堂，虽然似乎在数学上是个对的结论，但全部TLE。
正解就是个dp，$ f[i][j][k] $ 表示画到第i条边，用的是颜色j，上一条边的颜色是k。很显然，对于100%的数据肯定爆。
优化就是将后两维看成一个矩阵，因为不管是画到第几条边后两维的转移都是一样的，然后矩阵快速幂就行了。
代码先咕咕咕了，我真的会补上的。
先放个标程吧，我有时间再写。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 55,Mo = int(1e9) + 7;
typedef long long LL;
typedef int Matrix[MAXN][MAXN];
Matrix G,F,Tmp;
LL N;
int M;
void Mul(Matrix &a,Matrix &b,Matrix &c)
{
for(int i = 0;i < M;i ++)
for(int j = 0;j < M;j ++)
Tmp[i][j] = 0;
for(int i = 0;i < M;i ++)
for(int k = 0;k < M;k ++)
if (a[i][k])
for(int j = 0;j < M;j ++)
if (b[k][j])
Tmp[i][j] = (Tmp[i][j] + a[i][k] * 1ll * b[k][j]) % Mo;
for(int i = 0;i < M;i ++)
for(int j = 0;j < M;j ++)
c[i][j] = Tmp[i][j];
}
int main()
{
freopen("color.in","r",stdin);
scanf("%lld%d", &N, &M);
for(int i = 0;i < M;i ++)
for(int j = 0;j < M;j ++)
if (i != j)
G[i][j] = 1;
for(int i = 1;i < M;i ++) F[0][i] = 1;
N -= 2;
for(;N;N >>= 1)
{
if (N & 1) Mul(F,G,F);
Mul(G,G,G);
}
int ans = 0;
for(int i = 1;i < M;i ++) ans = (ans + F[0][i]) % Mo;
printf("%d\n", ans * 1ll * M % Mo);
return 0;
}
D1T3 Stree(stree)
这道题是这套题唯一一道我有AC代码的题，不过我是在测完后20分钟后才A的。
对于30%的数据，很容易想到直接暴力。当然，我们也可以预处理一遍最小生成树，如果这条边在树里就直接输出，否则在跑一遍最小生成树。
其实这样我们就已经完成了正解的第一步了，也就是预处理最小生成树，而且在树里就直接输出。如果这条边不在最小生成树里，就意味着我们需要加上这条边，并且一定要删掉一条在树里的边。我们设加上的这条边的两端点为u和v，那么加上这条边后就一定会以这条边和u和v之前在树里的路径形成一个环，我们只需要在u和v原来的路径里找到一条边删掉就行了。
为了让权值和最小，我们肯定会选择删u和v路径中最大的边。这里可以用倍增LCA之类的方法解决，我用的是树剖。一般涉及到LCA的问题我都用树剖，主要是常数小。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;
inline ll read()
{
char ch=getchar();
ll f=1,x=0;
while (ch<'0' || ch>'9')
{
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0' && ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
struct Edge{
ll stat,end,w,id;
} edge[200005];
struct Edge2{
ll next,to,w,id;
} e[400005];
struct Tree{
ll left,right,mx;
} tree[800005];
ll fa[200005],n,m,cnt=1,dfsord,head[200005],deep[200005],w[200005],wnew[200005],id[200005],f[200005],son[200005],top[200005],siz[200005];
bool intree[200005];
inline bool cmp(Edge x,Edge y) //第一次按边权从大到小
{
return x.w<y.w;
}
inline bool cmp2(Edge x,Edge y) //第二次按原来顺序还原
{
return x.id<y.id;
}
ll getfa(ll x)
{
if (x==fa[x]) return fa[x];
fa[x]=getfa(fa[x]);
return fa[x];
}
inline void add(ll u,ll v,ll w)
{
e[cnt].to=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt++;
}
inline void pushup(int x) //线段树
{
tree[x].mx=max(tree[x*2].mx,tree[x*2+1].mx);
}
void build(int x,int l,int r)
{
tree[x].left=l;
tree[x].right=r;
if (r-l==1) tree[x].mx=wnew[l];
else
{
build(x*2,l,(l+r)/2);
build(x*2+1,(l+r)/2,r);
pushup(x);
}
}
ll query(int x,int l,int r)
{
if (l<=tree[x].left && r>=tree[x].right) return tree[x].mx;
else
{
ll ans=0,mid=(tree[x].left+tree[x].right)/2;
if (l<mid) ans=max(ans,query(x*2,l,r));
if (r>mid) ans=max(ans,query(x*2+1,l,r));
return ans;
}
}
void dfs1(int x,int fath,int dep)
{
f[x]=fath;
deep[x]=dep;
siz[x]=1;
int mx=-1;
for (int i=head[x];i;i=e[i].next)
{
int y=e[i].to;
if (y==fath) continue;
w[y]=e[i].w;
dfs1(y,x,dep+1);
siz[x]+=siz[y];
if (siz[y]>mx)
{
mx=siz[y];
son[x]=y;
}
}
}
void dfs2(int x,int topf)
{
top[x]=topf;
id[x]=++dfsord;
wnew[dfsord]=w[x];
if (!son[x]) return;
dfs2(son[x],topf);
for (int i=head[x];i;i=e[i].next)
{
int y=e[i].to;
if (y==f[x] || y==son[x]) continue;
dfs2(y,y);
}
}
inline ll qRangeMax(int u,int v) //查找路径最大
{
ll ans=0;
while (top[u]!=top[v])
{
if (deep[top[u]]<deep[top[v]]) swap(u,v);
ans=max(ans,query(1,id[top[u]],id[u]+1));
u=f[top[u]];
}
if (deep[u]>deep[v]) swap(u,v);
ans=max(ans,query(1,id[u]+1,id[v]+1));
return ans;
}
int main()
{
freopen("stree.in","r",stdin);
freopen("stree.out","w",stdout);
ll ans=0;
n=read(); m=read();
for (int i=1;i<=m;i++)
{
edge[i].stat=read(); edge[i].end=read(); edge[i].w=read();
edge[i].id=i;
}
sort(edge+1,edge+m+1,cmp);
for (int i=1;i<=n;i++) fa[i]=i;
for (int i=1;i<=m;i++)
{
ll st=edge[i].stat,ed=edge[i].end,w=edge[i].w;
ll gfa=getfa(st),gfb=getfa(ed);
if (gfa==gfb) continue;
fa[gfa]=gfb; //最小生成树过程
ans+=w;
intree[edge[i].id]=1; //判断是否已在树里
add(st,ed,w);
add(ed,st,w);
}
dfs1(1,0,1);
dfs2(1,1);
build(1,1,n+1);
sort(edge+1,edge+m+1,cmp2);
for (int i=1;i<=m;i++)
{
if (intree[i]) //在树里直接输出
{
printf("%lld\n",ans);
continue;
}
ll st=edge[i].stat,ed=edge[i].end,w=edge[i].w,mx;
mx=qRangeMax(st,ed);
printf("%lld\n",ans-mx+w);
}
fclose(stdin);
fclose(stdout);
return 0;
}
Day2
每天都有人催我写，我还是今天把它赶出来吧。咕咕咕？
D2T1 景点中心(scene)
题目链接: https://vijos.org/p/1487
其实这道题很水，稍微推一下就可以出来，我在考场上不知道是脑子抽了还是怎么的竟然打了树剖。
我们一开始可以直接将1号点作为集合点，然后用一遍dfs将每个点到一号点的耗费算出来。我们在这里用dis[]表示。
很容易得到，对于每一个节点x的子节点y，所有点到它集合的耗费和dis[y]可以用如下的式子算出来：
s[i]代表第i个点的人数
dis[y]=dis[x]+w*(s[1]-2*s[y]);
然后再跑一遍dfs就行了。当然树上dp也可以做，但我dp太菜了就没写。
#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
inline ll read()
{
char ch=getchar();
ll f=1,x=0;
while (ch<'0' || ch>'9')
{
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0' && ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
struct Edge{
ll next,to,w;
} edge[200005];
ll head[100005],dis[100005],n,m,a,b,c,cnt=1,s[100005];
inline void add(int u,int v,int w)
{
edge[cnt].to=v;
edge[cnt].next=head[u];
edge[cnt].w=w;
head[u]=cnt++;
}
void dfs1(int x,int f)
{
for (int i=head[x];i;i=edge[i].next)
{
ll y=edge[i].to,w=edge[i].w;
if (y==f) continue;
dfs1(y,x);
s[x]+=s[y];
dis[x]+=dis[y]+s[y]*w;
}
}
void dfs2(int x,int f)
{
for (int i=head[x];i;i=edge[i].next)
{
ll y=edge[i].to,w=edge[i].w;
if (y==f) continue;
dis[y]=dis[x]+w*(s[1]-2*s[y]);
dfs2(y,x);
}
}
int main()
{
n=read();
for (int i=1;i<=n;i++) s[i]=read();
for (int i=1;i<n;i++)
{
a=read(); b=read(); c=read();
add(a,b,c);
add(b,a,c);
}
dfs1(1,0);
dfs2(1,0);
ll mn,mnsum=1e18;
for (int i=1;i<=n;i++)
{
if (dis[i]<mnsum)
{
mnsum=dis[i];
mn=i;
}
}
printf("%lld\n%lld",mn,mnsum);
return 0;
}
D2T2 方格游戏(fang)
大水题，就是道入门难度的题强行套一个高精。
递推式如下:
if (j==0) dp[i][j]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2];
else if (j==1) dp[i][j]=dp[i-1][0]+dp[i-1][1];
else if (j==2) dp[i][j]=dp[i-1][0]+dp[i-1][2];
其实这道题用__uint128_t就可以刚好水过。如果只知道__int128的话到100就会爆，但是大样例给了100，那么就可以特判水过了。
只是__uint128_t和__int128需要自己写个输出，不过写过快速io的话那就没什么问题。
void print(__uint128_t x)
{
if (x==0) return;
print(x/10);
putchar(x%10+'0');
}
这个东西只有64位系统下的gcc可以用，至于32位的ccf老爷机就别想了。我怎么感觉扯了这么多废话。
这道题大家都AC了，就不放代码了。
D2T3 运算符(calc)
提交这道题请至: https://www.luogu.org/problemnew/show/U44496
说明：版权不归我所有，此题上传仅为学习，若有侵权请联系我删除
其实也很水，只需要掌握线性筛即可。就算不会线性筛小于1000的最多也就168个质数，打表即可。
我们用 $ f[i][j][k] $ 表示 $ i!j $ 中第k个质数的个数。递推式就是：
初始值就是分解一下每个i，然后将结果存入*f[i][0]中即可。
inline void work(ll x)
{
ll y=x;
for (int i=1;i<=cnt && zs[i]<=y;i++)
{
while (x%zs[i]==0)
{
f[y][0][i]++;
x/=zs[i];
}
}
}
for (int i=1;i<=n;i++)
work(i);
全部代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define ll long long
#define ha 1000000009
using namespace std;
inline ll read()
{
char ch=getchar();
int f=1,x=0;
while (ch<'0' || ch>'9')
{
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0' && ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
bool ss[1005];
int zs[170],cnt,n,k,f[1005][105][170],mx;
inline void getprime()
{
memset(ss,1,sizeof(ss));
ss[0]=ss[1]=0;
for (int i=2;i<=mx;i++)
{
if (ss[i]) zs[++cnt]=i;
for (int j=1;j<=cnt && zs[j]*i<=mx;j++)
{
ss[zs[j]*i]=0;
if (i%zs[j]==0) break;
}
}
}
inline void work(ll x)
{
ll y=x;
for (int i=1;i<=cnt && zs[i]<=y;i++)
{
while (x%zs[i]==0)
{
f[y][0][i]++;
x/=zs[i];
}
}
}
int main()
{
n=read(); k=read();
mx=max(n,k);
getprime();
for (int i=1;i<=n;i++)
work(i);
for (int i=1;i<=n;i++)
for (int j=1;j<=k;j++)
for (int k=1;k<=cnt;k++)
f[i][j][k]=(f[i][j-1][k]+f[i-1][j][k])%ha;
ll ans=1;
for (int i=1;i<=cnt;i++)
ans=(ans*(f[n][k][i]+1))%ha;
printf("%lld",ans);
return 0;
}
总结
这两天题都很水，除了D1T3需要点简单的数据结构以外都是PJ难度的水题。但是每道题思维难度都比较高，都很难想到，或者说想复杂了（像我）。
我感觉可能noip就像这样，看了题解都会打，但是真正考场上能想出来并且能够AC的人又有多少呢？一直都是只要把暴力打好，打稳，并不需要学多少的辣鸡数据结构就可以拿一等奖甚至是高分。
所以我不应该再去搞些神仙算法和数据结构了，而就是应该把基础练稳练熟练扎实，争取每一次把自己能力所能拿到的分都拿到，我相信这样的成绩也一定会令人满意了。当然先过初赛最重要。
最后用一句lxl大佬的名言作结：
不要沉迷数据结构，会退役的。
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
This work is licensed under a CC BY-NC-SA 4.0 International License.
本文链接：https://llf0703.com/p/contest-summary-2.html