前言
- 比赛链接。
团队成绩，最后打铜，获得薯片一包（Shadow 没抢到泡面），抢了两个首 A，获得两包魔芋爽（Shadow 不愧是“原”神），但是 \(T_A\) 也是 STA_OI 原题，我还做过，可惜 Shadow 说晚了，不然就三包魔芋爽了。
没错那个 \(-95\) 又是我贡献的，和上次衬衫比赛不同的是这次到最后也没有 A 掉，先是找循环节（把数组存成哈希压进去）T 掉了，然后直接输出答案下界得到 \(78pts\)，可惜没有部分分，到最后没想出正解。
那个 \(-6\) 是我交错题了>_<。
A 树构造
- 签到题，P10678 『STA - R6』月。
STA_OI 原题，按照度数从大到小排序再挨着连即可，但那题是强化版，还要求直径最小，这题不需要，但这是一个合法构造方案。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=2e5+10,B=1e9+7;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
int n,fa[N],sum;
struct aa {int du,id;}e[N];
bool cmp(aa a,aa b) {return a.du>b.du;}
signed main()
{
read(n);
for(int i=1;i<=n;i++)
{
read(e[i].du),e[i].id=i;
sum+=e[i].du;
}
if(sum!=2*n-2)
{
puts("-1");
return 0;
}
sort(e+1,e+1+n,cmp);
for(int i=1,j=2;i<=n;)
{
if(e[i].du>0)
{
fa[e[j].id]=e[i].id;
e[i].du--,e[j].du--;
j++;
}
else i++;
}
for(int i=2;i<=n;i++)
if((fa[e[i].id]==0&&i!=1)||e[e[i].id].du!=0)
{
puts("-1");
return 0;
}
for(int i=2;i<=n;i++)
{
write(fa[e[i].id],e[i].id);
puts("");
}
}
B 长途巴士
- 不可做题。
C 你是黄金奖杯
- 不可做题。
D 地主斗
- 大模拟，不可做题。
E Grouping
- 貌似可做？但是不想做了。
F Pivot
- 同名原题。
发现不论如何操作，满足 \(a_i-a_j\) 的值恒不变，设 \(d=a_n-a_1\)。
钦定序列为升序排序，若另 \(s=a_i\)，则有 \(a_1'=2\times a_i-a_n\)。
对于 \(a_1\ge 0\) 的限制，不放直接求 \(a_1\bmod d\)，最后答案为 \(a_n'=a_1'\bmod d+d\)。
由此 \(a_1\equiv a_n\pmod d\)，所以有 \(2a_i-a_n\equiv 2(a_i-a_1)\)，固有 \(a_1'=a_1+2(a_i-a_1)\)，其中 \(a_i-a_1\) 恒不变。
对于一个 \(a_i\)，只需另下一次操作不再取 \(a_i\) 为 \(s\) 就不会恢复原来状态，故 \(a_i\) 可以贡献任意个 \(2(a_i-a_1)\)。
考虑每个 \(a_i\) 的贡献，设 \(a_1+x\times 2(a_i-a_1)=rd+c\)，\(r\) 为任意倍数，\(c\) 表示最后的 \(a_1'\bmod d\)，移项有 \(rd-x\times 2(a_i-a_1)=a_1-c\)，根据裴蜀定理，有 \(\gcd(2(a_i-a_1),d)|(a_1-c)\)，为使 \(c\) 最小取最大倍数的 \(\gcd(2(a_i-a_1),d)\) 即可。循环 \(a_i\) 取最小值，答案初始值为 \(a_n\)。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=2e5+10,B=1e9+7;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
int n,a[N],ans;
signed main()
{
read(n);
for(int i=1;i<=n;i++) read(a[i]);
int d=a[n]-a[1];
ans=a[n];
for(int i=1;i<=n;i++)
{
int s=__gcd(2*(a[i]-a[1]),d);
int x=a[1]/s;
ans=min(ans,a[1]-s*x+d);
}
write(ans);
}
G 11 : 23
- 学长打的游戏，符合欢乐赛主题了，但我没做。
H 烙印融合
- 签到题，单调栈板子，原题一抓一大把，不想说啥了。
I 魔术刻印
- 不可做题。
J persona
- 能发现结论就是签到题。
发现最后状态一定可以是连续一段长度为 \(k\) 的连续区间选择选或不选，其余的随便拿，从贪心的角度其余的只拿正的即可，枚举是哪块区间即可。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=2e5+10,B=1e9+7;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
ll n,k,a[N],sum[N],s[N],ans=0;
signed main()
{
read(n),read(k);
for(int i=1;i<=n;i++)
{
read(a[i]);
sum[i]=sum[i-1]+(a[i]>0)*a[i];
s[i]=s[i-1]+a[i];
}
for(int i=k;i<=n;i++)
ans=max(ans,max(0ll,s[i]-s[i-k])+sum[i-k]+sum[n]-sum[i]);
write(ans);
}
K 可持久化非确定性有穷状态决策自动机
- 魔怔题，因为
Shadow足够魔怔，我选择粘他的“题解”。
首先忽略题目背景和名称。
现在 HZOI 构建了一个自动机，但很巧的是他只能接受一个长度为 8 的字符串。
猜测与 HZOI 有关。
他是你们的某位学长的学长的学长的学长......
bobo 说过 huge 是 HZ 毕业的。
他暑假的出场方式是回宿舍整改。
huge 查宿查的最严了，feifei 最多算“帮凶”。
表达你对他的爱，答案为 \(8\) 个字符。
所以答案为 woaihuge。没做出来的反省一下自己。
L 随
设 \(f_{i,j}\) 表示当前数为 \(i\)，进行了 \(j\) 轮的概率，有 \(f_{i\times j\bmod P,k}+=f_{i,l}\times f_{j,k-l}\)。于是考虑倍增优化。
再次设 \(f_{i,j}\) 表示当前数为 \(i\)，进行了 \(2^j\) 轮时的概率，有 \(f_{i\times j\bmod P,k}+=f_{i,k-1}\times f_{j,k-1}\)，最后对 \(m\) 二进制拆分统计期望即可。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=1e5+10,M=1010,P=1e9+7;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
ll n,m,mod,a[N],sum[M],pos[31],s,f[31][M],g[31][M],ans,tot;
ll qpow(ll a,ll b)
{
ll ans=1;
for(;b;b>>=1)
{
if(b&1) (ans*=a)%=P;
(a*=a)%=P;
}
return ans;
}
signed main()
{
read(n,m,mod);
for(int i=1;i<=n;i++) read(a[i]),sum[a[i]]++;
for(int i=0;i<=mod-1;i++) f[0][i]=sum[i]*qpow(n,P-2)%P;
for(int k=1;k<=__lg(m);k++)
for(int i=0;i<=mod-1;i++)
for(int j=0;j<=mod-1;j++)
(f[k][i*j%mod]+=f[k-1][i]*f[k-1][j]%P)%=P;
for(int i=0;i<=__lg(m);i++)
if(m&(1<<i)) pos[++tot]=i;
for(int i=0;i<=mod-1;i++) g[1][i]=f[pos[1]][i];
for(int k=2;k<=tot;k++)
for(int i=0;i<=mod-1;i++)
for(int j=0;j<=mod-1;j++)
(g[k][i*j%mod]+=g[k-1][i]*f[pos[k]][j]%P)%=P;
for(int i=0;i<=mod-1;i++) (ans+=g[tot][i]*i%P)%=P;
write(ans);
}