当前位置： 代码迷 >> 综合 >> NOI Online 2020 Round1 准备计划
  详细解决方案

NOI Online 2020 Round1 准备计划

热度：47   发布时间：2023-10-22 20:58:15.0

3月7日，CCF会进行一次NOI Online的测试。
NOI Online 2020毕竟是网赛，它并没有非常大的参考性。
但是将它作为NOIP的一次全真模拟是非常有价值的。
所以我还是准备了一个比较详细的复习计划。
UPD:又考崩了，总结被我咕到3.20写去了。

赛况预测

UPD:考完了，预测的一个也没中…大家可以来看个笑话…
经历上一次联赛的失败后，我得到了许多教训，希望这次的复习能够有效果，不要重蹈覆辙。
由于本次考试是第一次举办[可能也是最后一次:)]，难度也无法准确地估计[官网上玄乎地写了一个模拟NOIP的考试系统和环境？？？]。
关于NOI Online 2020的无数种瞎想：

  • (最有可能) 由于本次比赛参考性肯定不强，服务器能否承受3万人的考试也是一个问号，THU可能被要求出题放水，CCF仅仅是拿这次比赛来测试系统:
    这时候对拍能力就相当的重要，正解打的快准稳是关键（鬼知道CCF最后几分钟系统会不会卡死…）。至于与APOI,CTS的关系大概是进了前25%都没什么问题的，主要还是参考CSP2019成绩。
  • THU按照出NOIP的习惯尽量减少AK人数，所以就有可能出现T1,T2-格雷码，T3-树上的数的情况:
    这时候最后一题的部分分得分就很重要。众所周知THU的题目子任务花样超多，一道题大概会有6-9个子任务，你可能需要打超级长的代码，当然，代码通常来说都很基础，甚至会有许多重合的部分。
  • CCF真的刻意要把这套题用来选拔APIO/CTSC的参赛选手，题目难度大(T1可能还会是签到题,大概像CTSC2018那个样子)[不太可能…毕竟作弊行为总会出现的…]:
    就跟打WC/APIO/CTSC差不多，尽量的选简单，分数多，代码量少的的子任务来做，但是这并不意味着分值小的代码量大的就不做，去年WC也就是因为少打了4分暴力而丢了银牌。

总的来说这次NOI Online的大概会存在2左右的简单题，可能有1道困难(甚至相当困难的)的拉分题（但是区分度也不会特别大）。大概会是在第2题的位置出现区分联赛一等能力(或者更高)的选手的题目。
总的来说，做对第2题，尽力在第3题拿高分，并且千万千万不要写挂代码应该是本次比赛的关键。

策略

当然，在考试的时候，并没有人告诉我们题目难度该是怎么样子的，一切都要靠自己去评判。每道题目在赛前就应该评估好时间，如果代码一直都没有调出，千万不要惊慌，我们需要马上将这道题比较简单的子任务写一遍。这样做不仅是为了保底，而且因为THU设计的子任务通常都有极大的关联性和提示性，它可以纠正你在解决这个问题时的思维漏洞（这也是我在CSP中失利的重要原因）。
[之后会再补一些…例如网络炸了，题目又出锅了之类的…]

漏洞

实时更新一下这几天我发现的问题:

  • STL用的很不熟练，需要再复习一遍。
  • 一直代码能力都不强，遇到上百行的代码就要调试半天，这几天会加强对这方面的练习。
  • 调试能力，具体来说是完全找不到代码问题的时候，自己手造数据或者是与暴力代码的对拍能力.

学习安排

面对这种偏向于考验基础能力的考试，我更觉得这是一个水到渠成的过程。
一味的求知识点的广度肯定是会出问题的。
THU永恒不变的四大主题:树,数据结构,dp,结论题肯定是本次考试复习的重点，它也是最有可能出现在压轴题位置的算法。
[凭借THU先是CSP植树大赛再是THUWC数据结构王朝复辟…我严重怀疑就只会考这几个内容…]

  • 2020.2.29 模拟赛+改题总结
  • 2020.3.1 DP&数据结构杂题选做

day 1

2020.2.29 模拟赛+改题总结
总结在此

day 2

2020.3.1 数据结构小练习

day 3

2020.3.2 Codeforces 虚拟赛练习

day 4

2020.3.3 部分分训练day1

Problems：

「九省联考 2018」IIIDX
「九省联考 2018」秘密袭击

今天其实是考试…但是题目是我出的…

「九省联考 2018」IIIDX

1-6:
O(n!?n)O(n!·n)O(n!?n)暴力。
30分。
did_idi?互不相同
简单树形dp即可。
100分:
基本上想到了正解…不过好像有点不一样的地方…自闭了…

day 5

2020.3.4 部分分训练day2

「九省联考 2018」秘密袭击

真的万万没想到他们都是用O(n3)O(n^3)O(n3)暴力过的
没错这题废了…因为O(n3)O(n^3)O(n3)做法实在是太简单了…
其实感觉挺可惜的…如果模数出成998244353的话用NTT，也许标程就比暴力快了。
当我没说，正解是拉格朗日插值插出来的…

「九省联考 2018」制胡窜

算了口胡懒得写了

「THUPC2018」城市地铁规划

一开始以为是构造一个图，然后自闭了。
明天再补

day 6

2020.3.5 “押"题+代码上手day1

「THUPC 2019」大碗宽面

Yazid 出的的一道小清新数据结构题。
跟树上的树属于一个类型——想不到系列。
题解大概考后会补。

/*Lower_Rating*/
/*data_struct*/
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stack>
#include<vector>
#include<queue>
#include<bitset>
#include<map>
using namespace std;#define LL long long
#define DB double
#define MOD 1000000007
#define Pr pair<int,int>
#define X first
#define Y second
#define MAXN 10000
#define MAXM 500
#define eps 1e-10
#define INF 1000000000
#define inf 100000000000000000LL
#define mem(x,p) memset(x,p,sizeof(x))LL read(){
    LL x=0,F=1;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){
    x=(x<<3)+(x<<1)+c-'0';c=getchar();}return x*F;
}
int add(int a,int b){
    return (a+b>=MOD)?a+b-MOD:a+b;}
int dec(int a,int b){
    return (a-b<0)?a-b+MOD:a-b;}
int mul(int a,int b){
    return 1LL*a*b%MOD;}
int fst_pow(int a,int b){
    int res=1;while(b){
    if(b&1)res=mul(res,a);a=mul(a,a);b>>=1;}return res;
}
int inv(int a){
    return fst_pow(a,MOD-2);}int m,n[MAXN+5],cnt,np[MAXN+5],ans[MAXN+5];
Pr num[MAXN*MAXM+5];struct List{
    struct node{
    int pre,nxt;}d[MAXN+5];int head[MAXN*2+5];void del(int x){
    if(d[x].pre)d[d[x].pre].nxt=d[x].nxt;else head[np[x]+MAXN]=d[x].nxt;if(d[x].nxt)d[d[x].nxt].pre=d[x].pre;}void Insert(int x,int pos){
    d[x].pre=0;d[x].nxt=head[pos];if(head[pos])d[head[pos]].pre=x;head[pos]=x;}
}L;int main(){
    m=read();for(int i=1;i<=m;i++){
    n[i]=read();for(int j=1;j<=n[i];j++)num[++cnt]=Pr(read(),i);}sort(num+1,num+cnt+1);for(int i=1;i<=m;i++)np[i]=-n[i],L.Insert(i,np[i]+MAXN);for(int i=1;i<=cnt;i++){
    int val=num[i].X,u=num[i].Y;L.del(u),np[u]+=2;if(np[u]==0||np[u]==1)ans[u]^=(val+u+u);for(int v=L.head[-np[u]+MAXN];v;v=L.d[v].nxt)ans[u]^=(val+u+v),ans[v]^=(val+u+v);for(int v=L.head[-np[u]+1+MAXN];v;v=L.d[v].nxt)ans[u]^=(val+u+v),ans[v]^=(val+u+v);L.Insert(u,np[u]+MAXN);}for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
}

「THUPC2018」城市地铁规划

一个重要的结论:

prufer序列中某个编号出现的次数就等于这个编号的节点在无根树中的度数-1

因此我们可以利用这个性质，问题转化为容量为n?2n-2n?2的背包dp问题。
如何输出方案，其实很简单。
我们先连上1?n1-n1?n然后从111开始在pufer出现多少次就新增一个点与它相连即可。
注意n=1,n=2n=1,n=2n=1,n=2特判…

/*Lower_Rating*/
/*data_struct*/
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stack>
#include<vector>
#include<queue>
#include<bitset>
#include<map>
using namespace std;#define LL long long
#define DB double
#define MOD 59393
#define Pr pair<int,int>
#define X first
#define Y second
#define MAXN 10000
#define MAXM 500
#define eps 1e-10
#define INF 1000000000
#define inf 100000000000000000LL
#define mem(x,p) memset(x,p,sizeof(x))LL read(){
    LL x=0,F=1;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){
    x=(x<<3)+(x<<1)+c-'0';c=getchar();}return x*F;
}
int add(int a,int b){
    return (a+b>=MOD)?a+b-MOD:a+b;}
int dec(int a,int b){
    return (a-b<0)?a-b+MOD:a-b;}
int mul(int a,int b){
    return 1LL*a*b%MOD;}
int fst_pow(int a,int b){
    int res=1;while(b){
    if(b&1)res=mul(res,a);a=mul(a,a);b>>=1;}return res;
}
int inv(int a){
    return fst_pow(a,MOD-2);}int n,k,dp[MAXN+5],a[MAXN+5],val[MAXN+5],puf[MAXN+5];
int id,cnt,du[MAXN+5];
void dfs(int x){
    for(int i=1;i<=du[x];i++){
    ++id;printf("%d %d\n",x,id);dfs(id);}
}
int main(){
    n=read(),k=read();for(int i=0;i<=k;i++)a[i]=read();for(int i=0;i<=n;i++)for(int j=k;j>=0;j--)val[i]=add(mul(val[i],i),a[j]);if(n==1){
    printf("0 %d\n",val[0]);return 0;}if(n==2){
    printf("1 %d\n1 2\n",2*val[1]);return 0;}dp[0]=val[1]*n;for(int i=2;i<=n;i++)for(int j=i-1;j<=n-2;j++)if(dp[j]<dp[j-i+1]+val[i]-val[1]){
    dp[j]=dp[j-i+1]+val[i]-val[1];puf[j]=j-i+1;}printf("%d %d\n",n-1,dp[n-2]);for(int i=n-2;i;i=puf[i])du[++cnt]=i-puf[i];du[1]++,dfs(id=1);
}

「CTSC2018」暴力写挂

题目没选好，被弃掉了。

day 7

2020.3.6 “押"题+代码上手day2
今天全是水题。

「CSP-S 2019」括号树

(special mission)

/*Lower_Rating*/
/*data_struct*/
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stack>
#include<vector>
#include<queue>
#include<bitset>
#include<map>
using namespace std;#define LL long long
#define DB double
#define MOD 1000000007
#define Pr pair<int,int>
#define X first
#define Y second
#define MAXN 500000
#define eps 1e-10
#define INF 1000000000
#define inf 100000000000000000LL
#define mem(x,p) memset(x,p,sizeof(x))LL read(){
    LL x=0,F=1;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){
    x=(x<<3)+(x<<1)+c-'0';c=getchar();}return x*F;
}
int add(int a,int b){
    return (a+b>=MOD)?a+b-MOD:a+b;}
int dec(int a,int b){
    return (a-b<0)?a-b+MOD:a-b;}
int mul(int a,int b){
    return 1LL*a*b%MOD;}
int fst_pow(int a,int b){
    int res=1;while(b){
    if(b&1)res=mul(res,a);a=mul(a,a);b>>=1;}return res;
}
int inv(int a){
    return fst_pow(a,MOD-2);}int n,f[MAXN+5],cnt[MAXN+5],dep;
char s[MAXN+5];LL res,ans[MAXN+5];
vector<int> G[MAXN+5];void dfs(int x){
    int pred=dep,prec=cnt[dep];ans[x]=ans[f[x]];if(s[x]=='(')cnt[dep]++,dep++;else cnt[dep]=0,dep=max(dep-1,0),ans[x]+=cnt[dep];for(int i=0;i<G[x].size();i++)dfs(G[x][i]);cnt[dep=pred]=prec;
}int main(){
    freopen("brackets.in","r",stdin);freopen("brackets.out","w",stdout);n=read();scanf("%s",s+1);for(int i=2;i<=n;i++){
    f[i]=read();G[f[i]].push_back(i);}dfs(1);for(int i=1;i<=n;i++)res^=(i*ans[i]);printf("%lld",res);
}

「CSP-S JX 2019」多叉堆

据说这题本来是CSP-S Day1T2…
如果当时考的是这道题目的话…我就不会连THUWC都去不了了[无奈]。
组合数学水题。
插一句话，我觉得JXCSP的题目风格才是原来的NOIP风格吧…

/*Lower_Rating*/
/*data_struct*/
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stack>
#include<vector>
#include<queue>
#include<bitset>
#include<map>
using namespace std;#define LL long long
#define DB double
#define MOD 1000000007
#define Pr pair<int,int>
#define X first
#define Y second
#define MAXN 300000
#define eps 1e-10
#define INF 1000000000
#define inf 100000000000000000LL
#define mem(x,p) memset(x,p,sizeof(x))LL read(){
    LL x=0,F=1;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){
    x=(x<<3)+(x<<1)+c-'0';c=getchar();}return x*F;
}
int add(int a,int b){
    return (a+b>=MOD)?a+b-MOD:a+b;}
int dec(int a,int b){
    return (a-b<0)?a-b+MOD:a-b;}
int mul(int a,int b){
    return 1LL*a*b%MOD;}
int fst_pow(int a,int b){
    int res=1;while(b){
    if(b&1)res=mul(res,a);a=mul(a,a);b>>=1;}return res;
}
int inv(int a){
    return fst_pow(a,MOD-2);}int n,q,lans;
int fa[MAXN+5],siz[MAXN+5],L[MAXN+5],R[MAXN+5];
int fac[MAXN+5];int xfind(int x){
    return (fa[x]==x)?x:fa[x]=xfind(fa[x]);
}
int main(){
    n=read(),q=read();fac[0]=1;for(int i=1;i<=n;i++)fac[i]=mul(fac[i-1],i);for(int i=0;i<n;i++)fa[i]=i,siz[i]=1,L[i]=1,R[i]=1;while(q--){
    int op=read(),x=(read()+lans)%n,y;if(op==1){
    y=(read()+lans)%n;x=xfind(x),y=xfind(y);int ps=siz[y]-1;fa[x]=y,siz[y]+=siz[x];L[y]=mul(mul(mul(L[y],inv(fac[ps])),fac[siz[y]-1]),inv(fac[siz[x]]));R[y]=mul(R[y],mul(L[x],R[x]));}else{
    x=xfind(x);printf("%d\n",lans=mul(L[x],R[x]));}}
}

「CodePlus 2018 4 月赛」喵呜

练一下基础题。

/*Lower_Rating*/
/*data_struct*/
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stack>
#include<vector>
#include<queue>
#include<bitset>
#include<map>
using namespace std;#define LL long long
#define DB double
#define MOD 1000000007
#define Pr pair<int,int>
#define X first
#define Y second
#define MAXN 300000
#define eps 1e-10
#define INF 1000000000
#define inf 100000000000000000LL
#define mem(x,p) memset(x,p,sizeof(x))LL read(){
    LL x=0,F=1;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){
    x=(x<<3)+(x<<1)+c-'0';c=getchar();}return x*F;
}
int add(int a,int b){
    return (a+b>=MOD)?a+b-MOD:a+b;}
int dec(int a,int b){
    return (a-b<0)?a-b+MOD:a-b;}
int mul(int a,int b){
    return 1LL*a*b%MOD;}
int fst_pow(int a,int b){
    int res=1;while(b){
    if(b&1)res=mul(res,a);a=mul(a,a);b>>=1;}return res;
}
int inv(int a){
    return fst_pow(a,MOD-2);}int T;LL n,h,x,a,y,b;
LL dl[2],dr[2],ans;int main(){
    T=read();while(T--){
    ans=inf;n=read(),h=read(),x=read(),y=read(),a=read(),b=read();if((n-x)%a==0)dl[0]=(n-x)/a;else dl[0]=-1;if((x-1)%a==0)dl[1]=(x-1)/a;else dl[1]=-1;if((h-y)%b==0)dr[0]=(h-y)/b;else dr[0]=-1;if((y-1)%b==0)dr[1]=(y-1)/b;else dr[1]=-1;for(int i=0;i<=1;i++)for(int j=0;j<=1;j++)if(dl[i]!=-1&&dr[j]!=-1&&(dl[i]-dr[j])%2==0)ans=min(ans,max(dl[i],dr[j]));if(ans==inf)printf("-1\n");else printf("%lld\n",ans);}
}
  相关解决方案

代码迷 - 您身边的软件异常，代码异常，编程异常助手（发现，解决，分享）
Copyright © 2009-2013 DAIMAMI.COM. All rights reserved.