吉林省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;
}