目錄
- 備戰
- 2021.10.18
- 2021.10.19
- 2021.10.20
- 2021.10.21
- 2021.10.22
- 比賽當日
- 早上
- 線下見面
- 正文
- 比賽后
- 賽后總結與講解
- 簡單總結
- Candy
- 小結
- 題解
- 參考代碼
- 賽時代碼（可能有錯）
- 優點：
- 缺點
- Sort
- 小結&題解
- 第一種
- 第二種
- 正解：第三種
- 參考代碼：
- 優點：
- 缺點
- 小結&題解
- Network
- 小結&題解
- 優點：
- 缺點
- Fruit
- 小結
- 賽時代碼
- 正解
- 優點：
- 缺點
- 總結
備戰
2021.10.18
下午班主任找到我，告訴了我一個訊息——這一周的下午和晚修全部上資訊
我當時十分高興，但三秒后....
媽耶，我文化課要垮了QAQ
到機房時，老師開始講強連通分量，太監（tarjan)演算法
我傻掉了QAQ
（初賽都這么變態，base64四毛子，復賽怕會普及出黑題.....)
后來晚上初一幾個自學三角函式，這是我奮斗的足跡
2021.10.19
在Panda的幫助下搞懂了太監演算法，然后做比賽
提高難度，我們進復賽的四個初一全部西內
當中最高是教授和某兔子愛好者，切了一題105
我和王梓燁墊底了QAQ
有一題我以為是樹狀陣列，結果是模擬，痛失15分
不過沒事，我們與其他初一又一起做了牛客的模擬賽
（當然并不是同步賽）
然后....全員200可還行
我突然覺得一等無望了....
晚上突然對魔法豬學院起了興趣.....
72,A* 過不了啊！！
于是暫時放下，安心復習
2021.10.20
又做了做魔法豬學院
發了個貼
想不到有個犇犇告訴我有A* 能過的
秒切
偶然發現中山原來有這么多普及紅名大佬？我被暴踩
搞了一會博客園，投入到學習中
老師開了幾個復習專題，我先做了高精，切了幾道
資料結構，我不會銀河英雄傳說,我太菜了
在這里復習一下種類并查集
比如食物鏈
我們用x與y+n有關系表示x吃y
x與y+2*n表示y吃x
這樣去連，到時候判斷即可
好的，然后是數論，exgcd忘干凈了，趕緊復習
推了幾次式子，會求\(ax+by=1\)了，不會\(ax+by=c\)
2021.10.21
上午剛好有節資訊課，拿來復習
歐拉函式搞懂了！！！又A兩道，Great！
復習歐拉函式
中午去做核酸，和王梓燁和教授聊天，不亦樂乎
(我還說我是IFW——International Feet Washing (世界洗腳大賽)的冠軍哈哈哈)
下午繼續刷題
Panda梅開二度，教我\(ax+by=c\),Orz
復習了哈希
好緊張呀，加油！！！
2021.10.22
參加模擬賽，倒數第二
重測一次，倒數第一
難受,晚飯沒吃
然后在vjudge做練習,還是太監演算法
我被虐菜
晚上回班收拾作業，好...多...
路上看見一個同學，說，只要我AK了，就請他喝燉湯
怎么可能（AK）?
比賽當日
早上
\(5:50\)醒了，去吃早餐
\(6:45\)出發
\(7:25\)左右到了
想進去看看，結果XC不讓進，于是各個學校的OIer就閑聊
線下見面
見到了洛谷上兩個大佬！！
之前在洛谷上約好的，終于見面了
非常尬：
“你平常登洛谷嗎”
“哦，你是xx”
“啊哈啊哈”
“額哈額啊哈”
正文
開始前上了個廁所，結果xc大聲說：
“你干嘛進進出出的”
“我...才出去一次”
然后xc對考官說：
“這種出去的一定要好好查一下”
我 被 搜 身
好強的壓迫感....
比賽開始后，老師讓我們輸密碼（結果老師自己打錯了）
謝謝JZ提供了一個卡死的Linux模擬機，還沒windows穩定....
第一題不是很確定，沒想出來（我太菜了）
然后打了一個能過樣例的公式，先做其他題
第二題真就題如其名，
一開始以為是樹狀陣列，浪費10分鐘
其實不是很難，個人認為最簡單（Because 不會第一題）
做完第二題，出去喝了杯牛奶，回去做第三題
第三題其實就是輸入惡心，
我調了50分鐘的輸入
結果靈光一閃————不就scanf的妙用嗎
但為了判斷前導零，要用sscanf
然后半個小時切了
這時差不多\(11:15\)
啊！！要不是這里浪費了太多時間，第一題我可能就調出來了！！！！
第四題我用了鏈表做，節省時間
感徑訓超時.....
（P.S：我有一個朋友說他用并查集，不知道怎么做的，樣例全過Orz）
只對了一下樣例，沒來得及對拍
然后看第一題，改了一下，搞了一個對拍
對到\(11:45\)，老師收各種東西，然后去打文操了
發現第二題除錯沒刪，差點爆零....
比賽后
回家了
測了一下第四題，70分TLE QAQ
一等沒了
結果一測其他題:\(100+100+100+70=370\)？！
其他網站都差不多，第四題不同
xx小靈通：第四題50，其他AC
計蒜客：第四題90，其他AC
詭異啊！！！大佬都說我第一題公式不對，對拍也不對，但各個網站都過了？
如果準的話，一等了.....（2021.10.30：說的真準）
估計實際第一題70左右(2021.10.31:其實是60）
賽后總結與講解
2021.10.30:Ohhhhhh!!360!!
感謝教練！！感謝Diyin School！！
三年了！！我出息了！！
簡單總結
| 題目名 | 得分 | 個人定位 | 檢查 | 暴力 | 資料全過 |
|---|---|---|---|---|---|
| candy | \(100\) | 數學，思維 | YES | NO | YES |
| sort | \(100\) | 時間復雜度，排序，模擬 | YES | NO | YES |
| network | \(100\) | 模擬，哈希，輸入技巧 | YES | NO | YES |
| fruit | \(60\) | 鏈表，模擬 | YES | YES | MAYBE |
一開始先把題都看了，所以沒有因小失大
第二,第三題發揮穩定，但第三題輸入想了\(50min\)，是一個巨大的失誤
第一題未能推出正解，對排每20個測驗點錯1個
但是，資料，它！！過！！了！！
第四題暴力順利水到60分
Candy
小結
第一題未能推出正解，對排每20個測驗點錯1個
但是，資料，它！！過！！了！！
（感謝CCF出了這么水的資料點！！）
題解
我還是認為我會被強資料hack,不拿自己的trash思路忽悠人了
這是別的犇犇的思路：
其實我們想，最優情況是拿\(n-1\)個——再拿一個就又要分了
但有時不足\(n-1\)，我們拿不到那么多，怎么辦呢？
我們拿\(r\)個就好了，
因為拿不到\(n-1\)就說明\([ l , r ]\)能拿到的是一個\([1,n-2]\)的一個子區間
也就是說，越往后越優
所以保證拿\(r\)個是最優解
（我考場沒想出來QAQ）
參考代碼
#include<bits/stdc++.h>
using namespace std;
long long n,l,r;
int main()
{
cin>>n>>l>>r;
if(l%n+r-l>=n)//如果能拿n-1個
{
cout<<n-1;
}
else
{
cout<<r%n;
}
}
賽時代碼（可能有錯）
只可意會，不可言傳
很垃圾，自己看吧.....
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
long long n,l,r;
inline long long read()//手打小垃圾快讀
{
char c=getchar();
int f=1;
long long sum=0;
while(c!='-'&&(c<'0'||c>'9'))c=getchar();
if(c=='-')
{
f=-1;
c=getchar();
}
do
{
sum=(sum<<3)+(sum<<1)+c-'0';
c=getchar();
}while(c>='0'&&c<='9');
return sum*f;
}
int main()
{
n=read(),l=read(),r=read();
long long mn=l/n,mx=(l+n-1)/n;
mn*=n,mx*=n;
long long ans=r-mn,ans2=r-mx;
//printf("%d %d %d\n",mn,ans,r);
if(ans>=n||ans2>=n)
{
printf("%d",n-1);
}
else
{
printf("%d",max(ans,max(0*1ll,ans2)));
}
}
優點：
-
該放手時就放手，在作不出時換題，保證了比賽的 節奏穩定 ，是一個 很好的習慣
-
最后回來對排，但未找出正解，對排是個好習慣
缺點
- 思維題能力欠缺 ，尤其是這種打卡題
Sort
小結&題解
考前蒙對了，猜中有 時間復雜度 的題
各位想想，有三種做法（正常的）
第一種
暴力，每次修改排一次序，用一個陣列記錄
這個陣列的第x項表示第x項排序后到了哪里，查詢\(O(1)\)
復雜度約為：
\(O(mnlog_n+m)\)
但修改最多5000次，所以更正為
\(O(5000nlog_n+m)\)
顯然TLE
第二種
對于修改，直接改，\(O(1)\)
對于查詢，找一遍所有小于它的，\(O(n)\)
復雜度：
\(O(nm)\)甚至慢過暴力
正解：第三種
先用sort排，
然后對于每次修改，去重新定位這個修改的數，跟插入排序差不多，復雜度\(O(n)\)
查詢，只需要輸出準備好的一個陣列，同做法一，復雜度\(O(1)\)
注意看題，修改最多\(5000\)次，盲猜一堆人以為我這個修改會超，因為他們以為極端資料會修改\(200000\)次，
復雜度：
\(O(nlog_n+5000n+m)\)不會超
所以要 好好看題 呀！！！
話說貌似每年的第二題都要估算時間復雜度....大家可以專門練一下這種題
參考代碼：
#include<bits/stdc++.h>
using namespace std;
struct node
{
int num,no;
}b[8005];
long long x,y,z,n,m,a[8005],c[8005];
int cmp(node x,node y)//如果相等，比較編號
{
if(x.num==y.num)
{
return x.no<y.no;
}
return x.num<y.num;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[i].num=a[i];
b[i].no=i;
}
sort(b+1,b+n+1,cmp);
for(int i=1;i<=n;i++)
{
c[b[i].no]=i;//預處理陣列
}
b[n+1].num=1e10,b[0].num=-1e10;//用來回傳的邊界
for(int i=1;i<=m;i++)
{
cin>>x>>y;
if(x==2)
{
cout<<c[y]<<endl;
continue;
}
if(x==1)
{
cin>>z;
b[c[y]].num=z;
for(int j=c[y];j<=n;j++)//調整位置
{
if(b[j].num>b[j+1].num||(b[j].num==b[j+1].num&&b[j].no>b[j+1].no))
{
swap(b[j],b[j+1]);
c[b[j].no]--;
}
else
{
c[y]=j;
break;
}
}
for(int j=c[y];j>=1;j--)//注意兩邊都要試
{
if(b[j].num<b[j-1].num||(b[j].num==b[j-1].num&&b[j].no<b[j-1].no))
{
swap(b[j],b[j-1]);
c[b[j].no]++;//交換后，預處理陣列也要更改
}
else
{
c[y]=j;
break;
}
}
}
}
}
優點：
-
仔細看題，找出解題的關鍵要素，不漏每個細節，這也是我能AC本題的原因
-
百折不撓，認真除錯，在比賽時，有一個好的心態，去進行復雜的除錯
-
在發現正解，有敢于推翻舊解的心態，我發現正解后立刻洗掉了舊代碼，
毫無感情
缺點
- 一言不合暴力，開局打了一個樹狀陣列+離散化，顯然不對
Network
小結&題解
這道題是可以\(20min\)搞定的水題
But我浪費了很多時間
難點是輸入
但仔細想想也不難
單獨發在博客了，會投稿題解
放個網址：
博客園：THIS
Luogu博客：THIS
優點：
- 無，如果非說有，知道的函式(sscanf)救了自己一命
缺點
- 花了太多時間，\(1h10min\)本場比賽最大失誤
- 在耗費大量時間時，沒有及時跳題，與第一題相反
Fruit
小結
打了暴力
用鏈表模擬
賽時代碼
#include<bits/stdc++.h>
using namespace std;
int n,s,t,sum;
struct node
{
int num,l,next;
}a[200005];
inline long long read()
{
char c=getchar();
int f=1;
long long sum=0;
while(c!='-'&&(c<'0'||c>'9'))c=getchar();
if(c=='-')
{
f=-1;
c=getchar();
}
do
{
sum=(sum<<3)+(sum<<1)+c-'0';
c=getchar();
}while(c>='0'&&c<='9');
return sum*f;
}
int main()
{
n=read();
s=1,t=n;
for(int i=1;i<=n;i++)
{
a[i].num=read();
a[i].l=i-1;
a[i].next=i+1;
}
while(sum!=n)
{
int k=-1;
for(int i=s;i<=t;i=a[i].next)
{
if(a[i].num!=k)
{
k=a[i].num;
sum++;
cout<<i<<' ';
a[a[i].next].l=a[i].l;
a[a[i].l].next=a[i].next;
if(i==s)
{
s=a[i].next;
}
if(i==t)
{
t=a[i].l;
}
}
}
cout<<endl;
}
}
正解
其實大概想到了，但沒時間打，
再加一個鏈表，每項表示一個“水果鏈”，
每次直接跳下一個水果鏈，快很多，
優點：
- 能水一分是一分，一種良好的比賽態度
缺點
- 正解很好推，但時間不夠（第三題的鍋）
總結
根據上述，下次要做到：
- 該放手時就放手，在作不出時換題
- 強化思維題能力
- 仔細看題，找出解題的關鍵要素，不漏每個細節
- 百折不撓，認真除錯
- 在發現正解，有敢于推翻舊解的心態
- 不要一言不合暴力
- 能水一分是一分
- 還是要說——誠信考試!!!
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/342983.html
標籤：C++
上一篇：抓取的連接問題：僅開始2次抓取中的1次（另一個被忽略并僅每5-6次嘗試開始糾正）
下一篇：大一C語言學習筆記（7）---指標篇--什么是指標？什么是指標變數？取地址符“&”的作用是什么？地址運算子“*”的作用是什么，怎么理解兩者？