Preface
难得没有发疯的一场，但只能说是症状减轻了，感觉离痊愈还有一定距离
这场基本就跟着榜慢慢开题，中期下机的时候才发现 J 我把题意读假了然后让队友推了快 3h 的假结论，还好最后把 J 过了不然铁战犯
A. Golden Spirit
签到分讨题，但也需要一些细心
大致思路就是在 \(2nt\) 那个时间点判断当前人所在的那一侧的人是否休息够了，如果可以答案就是 \(4nt\)
否则分两种情况，即人在这一侧等第一个休息够了的人；或者走到另一侧等第一个休息够了的人
#include<cstdio>
#include<iostream>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
int T,n,x,t;
signed main()
{
for (scanf("%lld",&T);T;--T)
{
scanf("%lld%lld%lld",&n,&x,&t);
if (2*(n-1)*t>=x) { printf("%lld\n",4*n*t); continue; }
int ret=x+2*t+2*n*t;
if (2*n*t>=x) ret=min(ret,(4*n+1)*t);
else ret=min(ret,x+t+2*n*t);
printf("%lld\n",ret);
}
return 0;
}
B. Labyrinth
首先特判不用绕路的情况，即如果起点和终点所在的矩形内没有黑洞则答案为它们间的曼哈顿距离
否则考虑曼哈顿距离的性质，只要走的方向是对的就一定是最短路
因此我们把一个黑洞四周的点当作关键点拿出来，在这些点之间连边跑个最短路即可
从关键点出发到棋盘中任意一个位置的距离可以简单 BFS 预处理得出，复杂度 \(O(nmk)\)
#include <bits/stdc++.h>
int dis[168][200000], s[200000];
std::vector<std::pair<int, int>> idv, hole;
int main() {
std::ios::sync_with_stdio(false);
memset(dis, 0x3f, sizeof(dis));
int n, m, k, q; std::cin >> n >> m >> k >> q;
auto hkr = [&](int i, int j) { return i * m + j; };
hole.resize(k);
for(int i = 0; i < k; ++i) {
auto &[x, y] = hole[i];
std::cin >> x >> y; x--, y--;
s[hkr(x, y)] += 1;
}
for(auto [x, y]: hole) {
if(x && !s[hkr(x - 1, y)]) idv.emplace_back(x - 1, y);
if(x < n - 1 && !s[hkr(x + 1, y)]) idv.emplace_back(x + 1, y);
if(y && !s[hkr(x, y - 1)]) idv.emplace_back(x, y - 1);
if(y < m - 1 && !s[hkr(x, y + 1)]) idv.emplace_back(x, y + 1);
}
// for(auto [x, y]: idv) std::cerr << x << " " << y << char(10);
for(int id = 0; id < idv.size(); ++id) {
auto [i, j] = idv[id];
// std::cerr << "i, j = " << i << ", " << j << char(10);
std::queue<std::pair<int, int>> q;
dis[id][hkr(i, j)] = 0;
q.push({i, j});
while(!q.empty()) {
auto [x, y] = q.front(); q.pop();
for(auto [nx, ny]: (int[4][2]){{x + 1, y}, {x - 1, y}, {x, y + 1}, {x, y - 1}}) {
if(nx < 0 || nx >= n || ny < 0 || ny >= m || s[hkr(nx, ny)]) continue;
if(dis[id][hkr(nx, ny)] == 0x3f3f3f3f) {
dis[id][hkr(nx, ny)] = dis[id][hkr(x, y)] + 1;
q.push({nx, ny});
}
}
}
}
for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j) {
if(i) s[hkr(i, j)] += s[hkr(i - 1, j)];
if(j) s[hkr(i, j)] += s[hkr(i, j - 1)];
if(i && j) s[hkr(i, j)] -= s[hkr(i - 1, j - 1)];
}
while(q--) {
int x1, y1, x2, y2, f, t;
std::cin >> x1 >> y1 >> x2 >> y2; x1--; x2--; y1--; y2--;
int xmin = std::min(x1, x2), xmax = std::max(x1, x2);
int ymin = std::min(y1, y2), ymax = std::max(y1, y2);
int S = s[hkr(xmax, ymax)];
if(xmin) S -= s[hkr(xmin - 1, ymax)];
if(ymin) S -= s[hkr(xmax, ymin - 1)];
if(xmin && ymin) S += s[hkr(xmin - 1, ymin - 1)];
// std::cerr << "S = " << S << char(10);
if(S == 0) {
std::cout << xmax + ymax - xmin - ymin << char(10);
continue;
}
f = hkr(x1, y1);
t = hkr(x2, y2);
int ans = 0x3f3f3f3f;
for(int i = 0; i < idv.size(); ++i) ans = std::min(ans, dis[i][f] + dis[i][t]);
if(ans == 0x3f3f3f3f) std::cout << "-1\n";
else std::cout << ans << char(10);
}
return 0;
}
C. Rencontre
很典的一个题
考虑树上三点 \(x,y,z\) 到带权重心的距离就是 \(\frac{dis(x,y)+dis(x,z)+dis(y,z)}{2}\)，显然我们可以拆贡献，单独计算每两个点集的点对的树上距离的期望
树上距离一眼拆成到根路径上的前缀和，即 \(dis(x,y)=dep(x)+dep(y)-2\times dep(\operatorname{LCA}(x,y))\)
前面的部分很容易计算，后面的部分在树上 DFS 一遍然后合并贡献即可
#include<cstdio>
#include<iostream>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
typedef pair <int,int> pi;
const int N=200005;
int n,x,y,z,dis[N],sza[N],szb[N]; vector <pi> v[N];
inline void DFS1(CI now=1,CI fa=0)
{
for (auto [to,w]:v[now]) if (to!=fa) dis[to]=dis[now]+w,DFS1(to,now);
}
inline void DFS2(double& ret,CI now=1,CI fa=0)
{
ret-=2.0*sza[now]*szb[now]*dis[now];
for (auto [to,w]:v[now]) if (to!=fa)
{
DFS2(ret,to,now);
ret-=2.0*szb[now]*sza[to]*dis[now];
ret-=2.0*sza[now]*szb[to]*dis[now];
sza[now]+=sza[to]; szb[now]+=szb[to];
}
}
inline double solve(vector <int> A,vector <int> B)
{
double ret=0;
for (RI i=1;i<=n;++i) sza[i]=szb[i]=0;
for (auto x:A) ret+=1.0*dis[x]*B.size(),sza[x]=1;
for (auto x:B) ret+=1.0*dis[x]*A.size(),szb[x]=1;
DFS2(ret); return ret;
}
int main()
{
scanf("%d",&n); for (RI i=1;i<n;++i)
scanf("%d%d%d",&x,&y,&z),v[x].push_back(pi(y,z)),v[y].push_back(pi(x,z));
vector <int> vec[3];
for (RI i=0;i<3;++i)
{
int m; scanf("%d",&m);
for (RI j=1;j<=m;++j) scanf("%d",&x),vec[i].push_back(x);
}
double ret=0; DFS1();
ret+=solve(vec[0],vec[1])*vec[2].size();
ret+=solve(vec[0],vec[2])*vec[1].size();
ret+=solve(vec[1],vec[2])*vec[0].size();
ret/=2.0;
printf("%.15lf",1.0*ret/(1.0*vec[0].size()*vec[1].size()*vec[2].size()));
return 0;
}
D. ABC Conjecture
根据样例大力猜测，只要 \(n\) 有平方质因子则一定有解，否则无解
要验证的话可以先枚举 \(10^6\) 以内的质因数，将其从 \(n\) 中全部消去后，若剩下的部分有 \(10^6\) 以外的平方质因子，则其一定是完全平方数
这种情况直接开方然后检验是否为质数即可，单组数据复杂度 \(O(n^{\frac{1}{3}})\)
#include<cstdio>
#include<iostream>
#include<cmath>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=1e6+5;
int T,c,vis[N],pri[N],cnt;
inline void init(CI n)
{
for (RI i=2;i<=n;++i)
{
if (!vis[i]) pri[++cnt]=i;
for (RI j=1;j<=cnt&&i*pri[j]<=n;++j)
if (vis[i*pri[j]]=1,i%pri[j]==0) break;
}
}
inline bool is_prime(CI x)
{
if (x==1) return 0;
for (RI i=2;i*i<=x;++i)
if (x%i==0) return 0;
return 1;
}
signed main()
{
for (scanf("%lld",&T),init(1e6);T;--T)
{
scanf("%lld",&c);
if (c==1) { puts("no"); continue; }
bool flag=0;
for (RI i=1;i<=cnt&&pri[i]<=c;++i)
if (c%pri[i]==0)
{
int cnt=0;
while (c%pri[i]==0) ++cnt,c/=pri[i];
if (cnt>=2) flag=1;
}
int x=(int)sqrt(c);
if (x*x==c&&is_prime(x)) flag=1;
puts(flag?"yes":"no");
}
return 0;
}
E. So Many Possibilities...
神秘 DP 题，祁神正在绝赞补题中，我已经白兰了
F. Skeleton Dynamization
神秘东西，题都没看
G. Caesar Cipher
一眼大力 Hash，虽然有取模操作但由于只有区间 \(+1\)，因此每个数超出的次数只有 \(\frac{q}{65536}\) 级别，可以接受每个点暴力处理
用经典的势能分析线段树，记录区间 \(\max/\min\)，复杂度 \(O(n\log n)\)
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
#define fi first
#define se second
using namespace std;
const int N=500005;
const int mod1=998244353,mod2=1e9+7;
struct Hasher
{
int x,y;
inline Hasher(CI X=0,CI Y=0)
{
x=X; y=Y;
}
friend inline bool operator == (const Hasher& A,const Hasher& B)
{
return A.x==B.x&&A.y==B.y;
}
friend inline Hasher operator + (const Hasher& A,const Hasher& B)
{
return Hasher((A.x+B.x)%mod1,(A.y+B.y)%mod2);
}
friend inline Hasher operator - (const Hasher& A,const Hasher& B)
{
return Hasher((A.x-B.x+mod1)%mod1,(A.y-B.y+mod2)%mod2);
}
friend inline Hasher operator * (const Hasher& A,const Hasher& B)
{
return Hasher(1LL*A.x*B.x%mod1,1LL*A.y*B.y%mod2);
}
}pw[N],base[N];
const Hasher seed=(233333,2333333);
int n,q,opt,x,y,z,a[N];
typedef pair <Hasher,int> ifo;
inline ifo operator + (const ifo& A,const ifo& B)
{
return {A.fi*pw[B.se]+B.fi,A.se+B.se};
}
class Segment_Tree
{
private:
ifo h[N<<2]; int mx[N<<2],mn[N<<2],tag[N<<2],len[N<<2];
inline void pushup(CI now)
{
mx[now]=max(mx[now<<1],mx[now<<1|1]);
mn[now]=min(mn[now<<1],mn[now<<1|1]);
h[now]=h[now<<1]+h[now<<1|1];
}
inline void apply(CI now,CI mv)
{
h[now].fi=h[now].fi+base[len[now]]*Hasher(mv,mv);
mx[now]+=mv; mn[now]+=mv; tag[now]+=mv;
}
inline void pushdown(CI now)
{
if (tag[now]) apply(now<<1,tag[now]),apply(now<<1|1,tag[now]),tag[now]=0;
}
public:
#define TN CI now=1,CI l=1,CI r=n
#define LS now<<1,l,mid
#define RS now<<1|1,mid+1,r
inline void build(TN)
{
len[now]=r-l+1; if (l==r)
{
h[now]={Hasher(a[l],a[l]),1};
mn[now]=mx[now]=a[l]; return;
}
int mid=l+r>>1; build(LS); build(RS); pushup(now);
}
inline void reduce(CI now,CI l,CI r)
{
//printf("reduce (now=%d, l=%d, r=%d)\n",now,l,r);
//printf("mx = %d, mn = %d\n",mx[now],mn[now]);
if (mx[now]<65536) return;
if (mn[now]==mx[now]) return apply(now,-65536);
int mid=l+r>>1; pushdown(now);
reduce(LS); reduce(RS); pushup(now);
}
inline void modify(CI beg,CI end,TN)
{
if (mx[now]>=65536) reduce(now,l,r);
if (beg<=l&&r<=end) return apply(now,1);
int mid=l+r>>1; pushdown(now);
if (beg<=mid) modify(beg,end,LS);
if (end>mid) modify(beg,end,RS);
pushup(now);
}
inline ifo query(CI beg,CI end,TN)
{
if (mx[now]>=65536) reduce(now,l,r);
if (beg<=l&&r<=end) return h[now];
int mid=l+r>>1; pushdown(now);
if (end<=mid) return query(beg,end,LS);
if (beg>mid) return query(beg,end,RS);
return query(beg,end,LS)+query(beg,end,RS);
}
#undef TN
#undef LS
#undef RS
}SEG;
int main()
{
scanf("%d%d",&n,&q);
for (RI i=1;i<=n;++i) scanf("%d",&a[i]);
pw[0]=Hasher(1,1); for (RI i=1;i<=n;++i) pw[i]=pw[i-1]*seed;
base[0]=Hasher(0,0); for (RI i=1;i<=n;++i) base[i]=base[i-1]*seed+Hasher(1,1);
for (SEG.build();q;--q)
{
scanf("%d%d%d",&opt,&x,&y);
if (opt==1) SEG.modify(x,y); else
{
scanf("%d",&z);
puts(SEG.query(x,x+z-1).fi==SEG.query(y,y+z-1).fi?"yes":"no");
}
}
return 0;
}
H. Message Bomb
祁神开场写的签到，我题目都没看
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int n, m, q, cnt[N], ans[N];
map<int, int> group[N];
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m >> q;
while (q--){
int t, x, y; cin >> t >> x >> y;
if (1==t){
group[y][x] = -cnt[y];
}else if (2==t){
ans[x] += cnt[y]+group[y][x];
auto it = group[y].find(x);
group[y].erase(it);
}else{
group[y][x] -= 1;
++cnt[y];
}
// printf("q=%d:", q); for (int i=1; i<=m; ++i) cout << ans << '\n';
}
for (int i=1; i<=n; ++i){
for (auto [x, c] : group[i]){
ans[x] += cnt[i]+c;
}
}
for (int i=1; i<=m; ++i) cout << ans[i] << '\n';
return 0;
}
I. Sean the Cuber
怎么又有魔方题，看来很有必要在机房买个魔方放着了
祁神和徐神比赛的时候讨论了这题的很多细节，感觉已经可以开写了，坐看队友补题
J. Steins;Game
首先是检讨环节，开场看了这个题然后和队友说每次是黑白都要取一次，直接骗队友想了好久的假做法
理解正确题意后不难发现只要对黑白两种游戏分别求出 SG 函数，然后讨论异或起来为 \(0\) 的方案数即可
白色部分的 SG 函数就是 Nim 游戏的结论；而黑色部分祁神手玩了一波发现胜负和 \(1\) 的个数以及数量的奇偶性有关
然后我爬上去写了个暴力打表发现它的 SG 函数为 \(\min a_i-(\operatorname{cnt}(\min a_i)+[all\_same])\bmod 2\)，其中 \(\operatorname{cnt}(\min a_i)\) 表示最小值出现的次数；\([all\_same]\) 在序列中所有数都相同时为 \(1\)，否则为 \(0\)
有了这个结论我们可以枚举黑色部分的最小值以及其数量，小于这个数的一定是白色部分，否则剩下的可以任意分配
人为地讨论 \([all\_same]\) 的值后，不难发现题目被转换为从一堆数中选出若干个数使得其异或值为某个值的方案数
这个也是经典线性基问题了，若该值不能被线性基表示出则方案数为 \(0\)；否则设线性基中自由变量的个数 为 \(free\)，则方案数为 \(2^{free}\)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<map>
#include<cstring>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=100005,mod=1e9+7;
int n,a[N],pre[N],suf[N],cnt[N],fact[N],ifac[N],ans; map <int,int> rst;
struct LB
{
int p[60],free;
inline void clear(void)
{
memset(p,0,sizeof(p)); free=0;
}
inline void insert(int x)
{
for (RI i=59;i>=0;--i) if ((x>>i)&1)
{
if (!p[i]) return (void)(p[i]=x); x^=p[i];
}
++free;
}
inline bool count(int x)
{
for (RI i=59;i>=0;--i) if ((x>>i)&1)
{
if (!p[i]) return 0; x^=p[i];
}
return 1;
}
}L;
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void init(CI n)
{
fact[0]=1; for (RI i=1;i<=n;++i) fact[i]=1LL*fact[i-1]*i%mod;
ifac[n]=quick_pow(fact[n]); for (RI i=n-1;i>=0;--i) ifac[i]=1LL*ifac[i+1]*(i+1)%mod;
}
inline int C(CI n,CI m)
{
if (n<0||m<0||n<m) return 0;
return 1LL*fact[n]*ifac[m]%mod*ifac[n-m]%mod;
}
signed main()
{
scanf("%lld",&n); init(n);
for (RI i=1;i<=n;++i) scanf("%lld",&a[i]),++rst[a[i]];
sort(a+1,a+n+1);
for (RI i=1;i<=n;++i) pre[i]=pre[i-1]^a[i];
for (RI i=n;i>=1;--i) suf[i]=suf[i+1]^a[i];
for (RI i=n;i>=1;--i)
if (a[i]!=a[i+1]) cnt[i]=1; else cnt[i]=cnt[i+1]+1;
for (RI i=n;i>=1;--i)
{
int ret=0,black=a[i]-(cnt[i]+1)%2;
if ((pre[i-1]^black^suf[i+cnt[i]])==0) ++ret;
black=a[i]-(cnt[i])%2;
if ((pre[i-1]^black)==suf[i+cnt[i]]) ret=(ret-1+mod)%mod;
if (L.count(pre[i-1]^black)) (ret+=quick_pow(2,L.free))%=mod;
(ans+=1LL*ret*C(rst[a[i]],cnt[i])%mod)%=mod;
if (a[i]!=a[i-1]) L.insert(a[i]),L.free+=rst[a[i]]-1;
}
if (suf[1]==0) (ans+=1)%=mod;
return printf("%lld",ans),0;
}
K. Tree Tweaking
题目太长了不想看，直接弃疗
L. Clock Master
徐神开场秒的一个题，我题目都没看
#include <bits/stdc++.h>
int is_prime[30001];
double dp[30001];
int main() {
int n = 30000;
memset(is_prime, 1, sizeof(is_prime));
is_prime[0] = is_prime[1] = 0;
for(int i = 1; i <= 30000; ++i) dp[i] = -1e300;
for(int i = 2; i <= n; ++i) if(is_prime[i]) {
double logi = std::log(i);
int64_t j, k;
double logj;
for(k = n; k >= 0; --k) {
for(j = i, logj = logi; j <= n && k - j >= 0; j *= i, logj += logi)
dp[k] = std::max(dp[k], dp[k - j] + logj);
}
for(j = i + i; j <= n; j += i) is_prime[j] = 0;
}
for(int i = 1; i <= n; ++i) dp[i] = std::max(dp[i], dp[i - 1]);
std::cout << std::fixed << std::setprecision(10);
int T; std::cin >> T; while(T--) {
std::cin >> n; std::cout << dp[n] << char(10);
}
return 0;
}
Postscript
做多了构式多校题后做区域赛的真题都感觉清新了很多，鉴定为这辈子就是被多校害了
标签：std,CI,const,Weihai,int,Contest,Programming,hkr,now From： https://www.cnblogs.com/cjjsb/p/18341002