吉林省CCPC與全國邀請賽（東北地區賽）游記

總述：

? ? ? ? 本次賽段共獲得一銀（吉林省賽）、一銅（東北地區賽）、一鐵（全國邀請賽的成績）。總體成績跟校內賽的情況相比隊伍狀態與發揮水準都有提升），但也體現出很多不足（

吉林省賽：

Day -5

????????隊伍經歷了兩次校內賽的實力后，所有人都放的比較開（感覺校內賽的時候，思維有些過于保守了）。作為隊長校內賽最后一場我發揮的十分不佳，一道題的關鍵性思路也沒有切掉，而且對于本應該過掉的題犯了一些重大的低級錯誤導致隊伍失利。回去后我們隊內開了一次會，大家把自己對隊內的問題都提了出來（隊內交流不佳，開題入wa掉后沒有入能夠接上思路幫忙改錯等等），之后大家把最近的在水平范圍內沒能賽時過掉的題目都補掉了，大家也沒什么壓力，平常練手感的同時，就是心平氣和的等待比賽。

Day 0

? ? ? ? 熱身賽當場：賽內的交流相較于之前流暢了許多，過掉兩道簽到后，大家一起吧我看出C有規律，之后GJ在我寫上的暴力代碼上面找到循環節，我再優化了一下就過掉了。熱身賽也是23名收尾，感覺狀態十分火熱

? Day 1

? ? ? ? 省賽正式賽當天：我先上來秒掉了簽到題，之后LCM大哥交了兩發過掉了F（沒開long long）同時注意到隊伍沒有寫底板，于是乎我花了2分鐘寫了個泛用性較強的底板，方便大家后續開題，之后GJ直接口胡了一遍G我們聽完沒問題后，就給他一遍過了。這時候看到大量隊伍都開出來了D（萌萌小數論），這是我的長相但是看了半個小時都沒什么思路，打完一遍表沒看出什么規律，LCM突然提出了一個“大膽的設想”：答案不會與左區間相差4，我覺得不對，但是照著這個方向去努力，發現答案不會與左區間不會相差1000，于是就寫個一個萌萌小暴力，在GJ與LCM包括我yan_jun的質疑下通過了

我嘞個奇跡與你

之后準備開L，GJ首先證出來了都是奇數的情況是 $2^{n+m-2}$ ，而我證出來了一奇一偶的情況是 $2^{even-1}$ ，之后和并一下再寫出全是偶數是為 1，L就順利通過了。

最后的C我想出了不管怎么樣，所有的數都會以和或積的形式出現，GJ有之后把環裝公式補完C就給切了。

之后LCM與GJ在開A，而我去寫E的矩陣快速冪的暴力，最后一個小時他倆都沒有討論出什么，這時候我臨去撤碩前瞟一眼GJ與LCM的草紙，感覺可以輾轉相除來做，就和他倆簡單交流了下思路，突然發現芝士天才想法，之后由GJ操刀，可惜最后沒能碼過去。

最后滾榜后取得了29名的成績（銀牌），感覺大家更自信粒，但是對day 2也是充滿敬意。

Day 2

先放排名

你敢信這是一個隊打的（詩人握持）

依舊是我先開的簽到；

然后GJ開B，但是熬了40分鐘沒能過掉，此時我看完K已經有了完整貪心思路，但是LCM開出了F說也是小范圍模擬簽到，就讓他先寫了。

? ? ?轉折點開始了

之后我和GJ開出了I題，但是LCM這是已經wa了2發了，其實已經打兩天了，對于我這種身體不是很好的入來說，有點折磨了（右胸開始劇烈疼痛，耳鳴的厲害），這時候我的心態有點崩了，但看著隊友確實比較愧疚也沒好說什么就是把讓GJ和他再看看代碼，我單獨開K，一發就過掉了。心情好了不少，于是又單開I，這時候已經過去塊兩個小時了，我承認我忌炎了，掛了兩發，之后賽方說題面有問題和GJ又討論了一下就過掉了。

最后兩個半小時，我開出了A的線段樹二分的全部思路，和H的二分的部分想法（這時候已經入已經快沒了）。LCM和GJ還在開F，最后是交了8發也沒能過去，這時候隊內有點慌了，我認為F一定有很大問題他們沒發現，就去單開A（code blocks崩了導致我疼的更厲害了），但是沒能過掉，賽后發現是我在區間范圍上的處理有點糙了，導致區間算重了。之后讓LCM開H，但是這時我才發現LCM其實對于二分問題的處理是存在很大問題，導致我們眼前一黑，又掛了4發，day 2的比賽遺憾一銅一鐵。

總結：

day 2后第二天隊內又開了一場小會，隊友覺得隊內訓練不足，但我覺得是我們在賽時的對問題的處理過于糙了，而且day 2的賽時進程相較于day 1其實交流上少了許多，導致了有隊友單開題被反殺沒人能補傷害的局面，再加上一共3天奔波，大家確實累了，賽內的一些內容以及突發的狀況（身體不適，選擇開題錯誤以及開題人員選擇錯誤等等）都沒有處理好導致了隊伍失利，身為隊長這是我的失職。

寫在最后：

相較于高中那個天天將暴力寫到極致都不去寫正解的yan_jun來說，現在的yan_jun越來越勇敢了，敢于去大膽的開正解，并敢于在賽場上去凹正解，一次次突破在賽場上去寫那些之前之前想都不敢想的算法，這正是我這一年來的改變。

也許就如艾克說的：“我寧愿犯錯，也不愿什么都不做。”ACM的競賽模式更能激發選手去突破自我，雖然我們有時要為這種所謂的勇敢去復出代價，但這種能力與體驗是成績無法與之比擬的

最后補題：

A - GD 終極節奏實驗室：

將線段樹優化為st表，跑的更快了（少了一層log），優化了區間重復問題，改成左大右等即可，很巧妙

#include<bits/stdc++.h>
#define ll long long
#define inl inline
#define re register
using namespace std;
inl int read() {int sum=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}while(isdigit(c)) {sum=(sum<<3)+(sum<<1)+(c^48);c=getchar();}return sum*f;
}
const int N=1e5+10;
int minn[N][20];
int mygcd[N][20];
inl int gcd(int a,int b) {if(a%b==0) return b;return gcd(b,a%b);
}
int Log[N];
struct node{int minn,mygcd;
}tree[N<<2];
int a[N],n;
inl int queryminn(int k,int l,int r) {if(l>r) return 2e9;int tmp=Log[r-l+1];return min(minn[l][tmp],minn[r-(1<<tmp)+1][tmp]);
}
inl int querygcd(int k,int l,int r) {if(l>r) return 1000000007;int tmp=Log[r-l+1];return gcd(mygcd[l][tmp],mygcd[r-(1<<tmp)+1][tmp]);
}
ll ans=0;
inl void solve(int i) {int l1,r1;int l=i,r=n;while(l<=r) {int mid=(l+r)>>1;int tmp1=queryminn(1,i,mid);int tmp2=querygcd(1,i,mid);if(tmp1==a[i]&&tmp1==tmp2) {r1=mid;l=mid+1;}else {r=mid-1;}}l=1,r=i;while(l<=r) {int mid=(l+r)>>1;int tmp1=queryminn(1,mid,i-1);int tmp2=querygcd(1,mid,i);if(tmp1>a[i]&&tmp2==a[i]) {l1=mid;r=mid-1;}else {l=mid+1;}}ans=ans+1ll*(i-l1+1)*(r1-i+1);return;
}
inl void init() {for(re int i=1;i<=n;i++) {minn[i][0]=a[i];mygcd[i][0]=a[i];}for(re int i=1;i<=Log[n];i++) {for(re int j=1;j+(1<<i)-1<=n;j++) {minn[j][i]=min(minn[j][i-1],minn[j+(1<<(i-1))][i-1]);mygcd[j][i]=gcd(mygcd[j][i-1],mygcd[j+(1<<(i-1))][i-1]);}}
}
int main() {n=read();for(re int i=1;i<=n;i++) a[i]=read();Log[0]=-1;for(re int i=1;i<=100000;i++) Log[i]=Log[i/2]+1;init();for(re int i=1;i<=n;i++) {solve(i);}cout<<ans<<endl;return 0;
}

F - 年少的誓約Ⅱ

問題不難，就是簽到題，但是出題人的巧在于如果我們拿角度去老老實實做就沒問題，而如果我們使用百分比去操作就會被卡精度導致掛掉（我做的時候也掛了一發），而隊友是太著急了導致對于目標時間的處理有問題（雖然改過來也是wa）

#include<bits/stdc++.h>
#define ll long long
#define inl inline
#define re register
using namespace std;
inl int read() {int sum=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}while(isdigit(c)) {sum=(sum<<3)+(sum<<1)+(c^48);c=getchar();}return sum*f;
}
inl void solve() {int x0=read(),y0=read(),x1=read(),y1=read(),x2=read(),y2=read();pair<int,int> tmp1={x1,y1},tmp2={x2,y2},ans1;double ans=2e9;double init1=(x0*30+y0*0.5),init2=y0*6.0;while(tmp1<=tmp2) {int a=tmp1.first,b=tmp1.second;double res1=((a*30.0)+b*0.5);double res2=(b*6.0);double yan=min(abs(init1-res1),abs(360-abs(init1-res1)));double jun=min(abs(init2-res2),abs(360-abs(init2-res2)));if(yan+jun<ans) {ans=yan+jun;ans1={a,b};}tmp1.second++;if(tmp1.second==60) {tmp1.first++;tmp1.second=0;}}cout<<ans1.first<<" "<<ans1.second<<endl;return;
}
int main() {int T=read();while(T--) {solve();}
}

H - 王國------遷移

這道題我看來沒什么好說的，就是加強二分的處理就過了(要開long long)

#include<bits/stdc++.h>
#define int long long
#define inl inline
#define re register
using namespace std;
inl int read() {int sum=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}while(isdigit(c)) {sum=(sum<<3)+(sum<<1)+(c^48);c=getchar();}return sum*f;
}
const int N=2e5+10;
int n,a[N],b[N],c[N],sum;
inl bool check(int tot) {int tmp=0;for(re int i=1;i<=n;i++) {tmp+=tot/c[i];}if(sum>tmp) return 0;for(re int i=1;i<=n;i++) {if(b[i]>tmp-tot/c[a[i]]) return 0;}return 1;
}
inl void solve() {sum=0;n=read();for(re int i=1;i<=n;i++) a[i]=read();for(re int i=1;i<=n;i++) b[i]=read(),sum+=b[i];for(re int i=1;i<=n;i++) c[i]=read();int l=0,r=1e18;while(l<r) {int mid=(l+r)>>1;if(check(mid)) {r=mid;}else {l=mid+1;}}cout<<r<<endl;
}
signed main() {int T=read();while(T--) {solve();}return 0;
}