Day -1
上午在洛谷上看到了个结论题的帖子,就去做了几道,感觉还行。剩下的时间就看自己做过的题,还有打打月赛之类的比赛里面的简单题。(太菜了
上午还跟徐妈扯了5min,终于成功把明早的集合时间从6:50改到7:10(我平时都是7:05才出寝室的说
昨天还计划今天21:20就去跑,跑个8km,结果下雨了(rp++
于是在这写游记日记。
还是惯例 NOIP2020 RP++
晚上从机房走的时候,想到这真的是最后一次在机房学竞赛了,突然有点触景生情。
晚上情绪不太好,还在群里发了一些感慨的话,感觉不太好就不放了。
Day 1
上午到校门口,发现徐妈给我们买了(除了早饭)一大袋吃的,有水、牛奶还有2条巧克力一条士力架,实名表白徐妈。
7:26就到了,本来以为要7:40才能进去,结果大概7:30就可以了,不过到了楼下还是排了半天队,在那听大佬们扯。
这次考号是按学校排的,还以为可以坐一起,进去以后才发现是竖着的顺序,然后我这个SC-0012
就苦逼的坐到了最后一排。然后不准动键盘鼠标,就在那发呆。看着前面的那些人,想到自己再也不会作为选手出现在这了,就感到不是滋味。
先看T1,竟然一时间没想到拓扑,不过一看边数、层数 $\le 10$ ,写个爆搜跑了。想到了int
不够,但没有算极限数据,也就没有写高精。
T2先想了个 $O(n^4)$ 的做法,然后前缀和优化掉了一维,码完一测发现1000的数据都能过,遂震惊的去上了个厕所。回来才发现复杂度算错了。然后回来写了个只有一种字母的情况,56分跑了。
坐我右边那个老哥最早提出T3数据范围有问题,改了以后放在投影上,我坐在最后一排看都看球不到;后来还说要用c11编译spj,当然编译命令也看不到(当然这点命令还是会的)。不过反正都做不来,输了个0滚了。
T4考虑极限状况对每个位置的贡献,打了个30分暴力。还剩的1h本来想写正解然后发现不会,只能写链的情况,不过貌似还写炸了。
考完估计 $100+56+0+40=196$ 。
下午15:13徐妈就把程序发给我了,我:???这么快的吗
oitiku上测的是 $100+56+0+30$,洛谷是 $90+56+?+?$(T3没测,T4还没数据)。大众分吧,自己感觉还行了。
剩下的时间颓,看皇室战争职业联赛全球总决赛,两支中国队NOVA和EDG都出局了,哎。
晚上一边循环Euphoria,一边完成了这篇游记。
那么,就这样结束了吧。
后记
出分了 $80+56+0+35=171$ ,T1有个地方没先除后乘挂了10分,不过也还可以了。
某天去机房填问卷的时候徐妈在场,告诉我很遗憾,差了4分,不过也在预料之中。
总的来说还是把自己垃圾的水平考出来了,没什么遗憾。接下来就专心搞文化课啦。
附录
附一下代码吧。
water.cpp
:
#include<bits/stdc++.h>
#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;
}
const ll N=1e5+5;
vector <ll> e[N];
ll n,m,a,b,c,resp[N],resq[N];
// long long
ll gcd(ll x,ll y) { return y ? gcd(y,x%y) : x; }
void dfs(ll x,ll p,ll q)
{
if (!e[x].size())
{
if (!resq[x] || !resp[x])
{
resq[x]=q; resp[x]=p;
return;
}
ll curq=resq[x]*q;
ll curp=resp[x]*q+resq[x]*p;
ll g=gcd(curq,curp);
curq/=g; curp/=g;
resq[x]=curq; resp[x]=curp;
return;
}
ll sz=e[x].size();
ll g=gcd(p,sz);
p/=g; sz/=g;
ll nxtq=q*sz;
for (ll i=0;i<sz;i++)
{
ll y=e[x][i];
dfs(y,p,nxtq);
}
return;
}
int main()
{
freopen("water.in","r",stdin);
freopen("water.out","w",stdout);
n=read(); m=read();
for (ll i=1;i<=n;i++)
{
a=read();
for (ll j=1;j<=a;j++) e[i].push_back(read());
}
for (ll i=1;i<=m;i++)
{
//init();
dfs(i,1,1);
}
for (ll i=1;i<=n;i++) if (!e[i].size()) printf("%lld %lld\n",resp[i],resq[i]);
return 0;
}
string.cpp
:
#include<bits/stdc++.h>
#define ll long long
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;
}
const int N=(1<<20)+5;
int t,n,cntC[26],cntA[26],canSum[1005][1005],jiA[1005];
char s[N];
//bool can[1005][1005];
//long long
inline void init()
{
memset(cntA,0,sizeof(cntA));
memset(jiA,0,sizeof(jiA));
for (int i=1;i<=n;i++)
{
int cur=s[i]-'a';
cntA[cur]++;
if (cntA[cur]&1) jiA[i]=jiA[i-1]+1;
else jiA[i]=jiA[i-1]-1;
}
memset(cntC,0,sizeof(cntC));
memset(canSum,0,sizeof(canSum));
int jiC=0;
for (int i=n;i;i--) //Cl
{
int cur=s[i]-'a';
cntC[cur]++;
if (cntC[cur]&1) jiC++;
else jiC--;
for (int j=1;j<i;j++)
{
canSum[i][j]=canSum[i][j-1];
if (jiA[j]<=jiC) canSum[i][j]++;
}
}
//for (int i=1;i<n;i++) cout<<i<<" "<<canSum[n][i]<<endl;
}
inline bool check(int Br,int l,int r)
{
for (int i=1,j=l;i<=Br;i++,j++) if (s[i]!=s[j]) return 0;
return 1;
}
int main()
{
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
t=read();
while (t--)
{
scanf("%s",s+1);
n=strlen(s+1);
if (n<=1000)
{
init();
ll ans=0;
for (int Br=2;Br<n;Br++)
{
int maxi=1;
for (int r=(Br<<1);r<n;maxi++,r+=Br)
{
if (!check(Br,r-Br+1,r)) break;
}
for (int i=1;i<=maxi;i++)
{
int Cl=i*Br+1;
ans+=canSum[Cl][Br-1];
}
}
printf("%lld\n",ans);
}
else
{
bool flag=1;
for (int i=2;i<=n;i++) flag&=s[i]==s[i-1];
if (flag) //13~14
{
ll ans=0;
for (int Cl=n;Cl>2;Cl--)
{
int Br=Cl-1;
for (int i=1;i*i<=Br;i++)
{
if (Br%i) continue;
int maxAr=Br/i-1;
if ((n-Cl+1)&1) ans+=maxAr;
else ans+=maxAr>>1;
if (i==1 || i*i==Br) continue;
int i2=Br/i;
maxAr=Br/i2-1;
if ((n-Cl+1)&1) ans+=maxAr;
else ans+=maxAr>>1;
}
}
printf("%lld\n",ans);
}
else
{
puts("19260817");
}
}
}
return 0;
}
ball.cpp
:
#include<bits/stdc++.h>
#define ll long long
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 main()
{
freopen("ball.in","r",stdin);
freopen("ball.out","w",stdout);
cout<<0<<endl;
return 0;
}
//I love OI forever
//Llf0703 NOIP2016~NOIP2020 AFO
walk.cpp
:
#include<bits/stdc++.h>
#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;
}
const ll N=5e5+5,K=15,ha=1e9+7;
ll n,k,w[K],c[N],d[N],mx[N],mn[N],cur[N],T[K];
// long long
int main()
{
freopen("walk.in","r",stdin);
freopen("walk.out","w",stdout);
n=read(); k=read();
ll ans=1,maxW=0;
for (ll i=1;i<=k;i++) w[i]=read(),ans=1ll*ans*w[i]%ha,maxW=max(maxW,w[i]);
for (ll i=1;i<=n;i++) c[i]=read(),d[i]=read(),T[c[i]]+=d[i];
bool flag=1;
for (ll i=1;i<=k;i++) flag&=T[i]==0;
if (flag) return !printf("-1");
if (k==1 && maxW>1000)
{
bool flag=1; ll res_sum=0;
for (ll i=1;i<=n;i++)
{
if (i==n+1) i=1;
cur[c[i]]+=d[i];
mx[c[i]]=max(mx[c[i]],cur[c[i]]);
mn[c[i]]=min(mn[c[i]],cur[c[i]]);
ll res=1;
for (ll j=1;j<=k;j++)
{
flag&=((w[j]-mx[j])-(1-mn[j])+1)>0;
res=1ll*res*((w[j]-mx[j])-(1-mn[j])+1)%ha;
}
if (!flag) break;
(ans+=res)%=ha;
(res_sum+=res)%=ha;
}
if (!flag) return !printf("%lld",ans);
ll minT=min((w[1]-mx[1])/T[1],(w[1]+mn[1])/T[1]);
for (ll t=1;t<=minT;t++) ans+=(res_sum-(1ll*n*T[1]%ha)*t%ha+ha)%ha;
mx[1]=max(mx[1],mx[1]+T[1]*minT);
mn[1]=min(mn[1],mn[1]+T[1]*minT);
cur[1]+=T[1]*minT;
for (ll i=1;i<=n;i++)
{
cur[c[i]]+=d[i];
mx[c[i]]=max(mx[c[i]],cur[c[i]]);
mn[c[i]]=min(mn[c[i]],cur[c[i]]);
ll res=1;
for (ll j=1;j<=k;j++)
{
flag&=((w[j]-mx[j])-(1-mn[j])+1)>0;
res=1ll*res*((w[j]-mx[j])-(1-mn[j])+1)%ha;
}
if (!flag) break;
(ans+=res)%=ha;
}
return !printf("%lld",ans);
}
for (ll i=1;;i++)
{
if (i==n+1) i=1;
cur[c[i]]+=d[i];
mx[c[i]]=max(mx[c[i]],cur[c[i]]);
mn[c[i]]=min(mn[c[i]],cur[c[i]]);
ll res=1; bool flag=1;
for (ll j=1;j<=k;j++)
{
flag&=((w[j]-mx[j])-(1-mn[j])+1)>0;
res=1ll*res*((w[j]-mx[j])-(1-mn[j])+1)%ha;
}
if (!flag) break;
(ans+=res)%=ha;
}
return !printf("%lld",ans);
}
llf 加油!