Preface
因为最近大家都有考试啥的，实在太久没训练了，只好在成都到郑州的火车上 VP 了一场
顶着喧闹的车厢以及电脑只能放在腿上打的巨大 Debuff，成功打出 7 题巨大罚时
不过可惜的是 4h 后就没出题了，剩下的 C,F 瞪了半天是一个不会，甚至赛后看 C 的题解也搞不明白，只能说计数苦手是这样的
B. Birthday Gift
被徐神一眼秒了，好像就是只和 \(0,1\) 奇偶位置上的数量有关，然后 \(2\) 可以拿去补任何一边，因此代码很好写
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
void work() {
int cnt0[2] {0, 0}, cnt1[2] {0, 0}, cnt2[2] {0, 0};
std::string s; std::cin >> s;
int n = s.size();
for(int i = 0; i < n; ++i) switch(s[i]) {
case '0': cnt0[i & 1]++; break;
case '1': cnt1[i & 1]++; break;
case '2': cnt2[i & 1]++; break;
}
int a = std::abs(cnt0[0] - cnt0[1]) + std::abs(cnt1[0] - cnt1[1]);
int c2 = cnt2[0] + cnt2[1];
if(c2 <= a) a -= c2;
else a = (c2 - a & 1);
std::cout << a << char(10);
}
int main() {
std::ios::sync_with_stdio(false);
int T; std::cin >> T; while(T--) work();
}
E. Left Shifting 3
签到题，直接双指针一下即可
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
int work() {
int n, k;
std::cin >> n >> k;
k = std::min(n, k);
std::string S; std::cin >> S;
if(n < 7) return 0;
S += S.substr(0, k);
int l = S.size();
std::vector<int> s(l, 0);
for(int i = 0; i <= l - 7; ++i) s[i] = (S.substr(i, 7) == "nanjing");
for(int i = 1; i < l; ++i) s[i] += s[i - 1];
int ans = s.at(n - 7);
for(int i = 0, j = n - 6; j < l; ++i, ++j) ans = std::max(ans, s.at(j) - s.at(i));
return ans;
}
int main() {
std::ios::sync_with_stdio(false);
int T; std::cin >> T; while(T--) std::cout << work() << char(10);
return 0;
}
G. Binary Tree
树上 \(\log\) 级别的操作，一眼想到点分治
考虑对于当前分治中心 \(x\)，找出其孩子中子树大小较大的两个 \(u,v\)，询问 \(u,v\) ：
- 返回 \(0\)，则说明 \(s\) 在 \(u\) 的子树内；
- 返回 \(2\)，则说明 \(s\) 在 \(v\) 的子树内；
- 返回 \(1\)，则说明 \(s\) 在 \(x\) 的子树除去 \(u,v\) 的子树剩下的部分内；
由于题目保证是二叉树，因此返回 \(1\) 是剩下部分至多为一个子树加上原来的分治中心，故每次操作点规模减半
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cassert>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n,x,y,sz[N],mx[N],vis[N],rt,ots; vector <int> v[N];
inline int ask(CI u,CI v)
{
printf("? %d %d\n",u,v); fflush(stdout);
int res; scanf("%d",&res); return res;
}
inline void answer(CI x)
{
printf("! %d\n",x); fflush(stdout);
}
inline void getrt(CI now=1,CI fa=0)
{
sz[now]=1; mx[now]=0;
for (auto to:v[now]) if (to!=fa&&!vis[to])
{
getrt(to,now); sz[now]+=sz[to];
mx[now]=max(mx[now],sz[to]);
}
mx[now]=max(mx[now],ots-sz[now]);
if (mx[now]<=mx[rt]) rt=now;
}
inline void solve(int now)
{
vector <int> son;
for (auto to:v[now]) if (!vis[to]) son.push_back(to);
if (son.empty()) return answer(now);
if (son.size()==1)
{
int res=ask(now,son.back());
assert(res!=1);
if (res==0) answer(now); else answer(son.back());
return;
}
if (son.size()==2)
{
int res=ask(son[0],son[1]);
if (res==0)
{
vis[now]=1; mx[rt=0]=ots=sz[son[0]];
getrt(son[0],now); getrt(rt); solve(rt);
} else
if (res==2)
{
vis[now]=1; mx[rt=0]=ots=sz[son[1]];
getrt(son[1],now); getrt(rt); solve(rt);
} else answer(now);
return;
}
auto cmp=[&](CI x,CI y)
{
return sz[x]>sz[y];
};
sort(son.begin(),son.end(),cmp);
int res=ask(son[0],son[1]);
if (res==0)
{
vis[now]=1; mx[rt=0]=ots=sz[son[0]];
getrt(son[0],now); getrt(rt); solve(rt);
} else
if (res==2)
{
vis[now]=1; mx[rt=0]=ots=sz[son[1]];
getrt(son[1],now); getrt(rt); solve(rt);
} else
{
vis[son[0]]=vis[son[1]]=1; getrt(now);
mx[rt=0]=ots=sz[now];
getrt(now); getrt(rt); solve(rt);
}
return;
}
int main()
{
for (scanf("%d",&t);t;--t)
{
scanf("%d",&n);
for (RI i=1;i<=n;++i) vis[i]=0,v[i].clear();
for (RI i=1;i<=n;++i)
{
scanf("%d%d",&x,&y);
if (x!=0) v[i].push_back(x),v[x].push_back(i);
if (y!=0) v[i].push_back(y),v[y].push_back(i);
}
mx[rt=0]=ots=n; getrt(); getrt(rt); solve(rt);
}
return 0;
}
I. Bingo
式子优化不来怎么办，直接扔给徐神然后一会就能得到做法了，真是太神奇了
考虑 min-max 容斥，本来是先求每行每列的 max，然后再一起求个 min 作为贡献
现在等价于对 \(x\in[0,n]\) 行 \(y\in[0,m]\) 列求一个整体 max 作为贡献，这个十分经典
将 \(\{a_i\}\) 升序排序后，令 \(f(i,j)\) 表示选出恰好 \(j\) 个有贡献的数，这些数的 \(\max\) 为 \(a_i\) 的排列数
显然有 \(f(i,j)=C_{i-1}^{j-1}\times j!\times (nm-j)!\)，即钦定 \(a_i\) 必选后再挑 \(j-1\) 个小于 \(a_i\) 的数放入贡献区
此时我们需要知道一个 \(G(j)=\sum_{i=1}^{nm} f(i,j)\)，有了这个后我们再套一个容斥的壳这题就做完了
把到这部分的问题扔给徐神后徐神发现 \(f(i,j)\) 的式子化简后是个差卷积的形式，然后教了我一种很神秘的方法
（大致流程为，令 \(A(i)=a_i\times (i-1)!,B(i)=\frac{1}{(nm-i)!},C=A\ast B\)，则 \(G(i)=i\times (nm-i)\times C(nm+i)\)）
虽然我是一整个没有听懂，但按部就班地实现了徐神的教诲后写完就一遍过样例然后交上去一遍 AC
#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=1<<20,mod=998244353;
int t,n,m,a[N],fact[N],ifac[N],f[N],g[N],lim,p;
inline void inc(int& x,CI y)
{
if ((x+=y)>=mod) x-=mod;
}
inline void dec(int& x,CI y)
{
if ((x-=y)<0) x+=mod;
}
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;
}
namespace Poly
{
int rev[N];
inline void init(CI n)
{
for (lim=1,p=0;lim<=n;lim<<=1,++p);
for (RI i=0;i<lim;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<p-1);
}
inline void NTT(int *f,CI opt)
{
RI i; for (i=0;i<lim;++i) if (i<rev[i]) swap(f[i],f[rev[i]]);
for (i=1;i<lim;i<<=1)
{
int m=i<<1,D=quick_pow(3,opt==1?(mod-1)/m:mod-1-(mod-1)/m);
for (RI j=0;j<lim;j+=m)
{
int W=1; for (RI k=0;k<i;++k,W=1LL*W*D%mod)
{
int x=f[j+k],y=1LL*f[i+j+k]*W%mod;
f[j+k]=f[i+j+k]=x; inc(f[j+k],y); dec(f[i+j+k],y);
}
}
}
if (!~opt)
{
int Inv=quick_pow(lim); for (i=0;i<lim;++i) f[i]=1LL*f[i]*Inv%mod;
}
}
};
int main()
{
for (scanf("%d",&t),init(2e5);t;--t)
{
scanf("%d%d",&n,&m);
for (RI i=1;i<=n*m;++i) scanf("%d",&a[i]);
sort(a+1,a+n*m+1); Poly::init(2*n*m);
for (RI i=1;i<=n*m;++i) f[i]=1LL*a[i]*fact[i-1]%mod;
f[0]=0; for (RI i=n*m+1;i<lim;++i) f[i]=0;
for (RI i=0;i<=n*m;++i) g[i]=ifac[n*m-i];
for (RI i=n*m+1;i<lim;++i) g[i]=0;
Poly::NTT(f,1); Poly::NTT(g,1);
for (RI i=0;i<lim;++i) f[i]=1LL*f[i]*g[i]%mod;
Poly::NTT(f,-1);
for (RI i=0;i<=n*m;++i) g[i]=1LL*i*fact[n*m-i]%mod*f[n*m+i]%mod;
int ans=0;
for (RI x=0;x<=n;++x) for (RI y=0;y<=m;++y)
{
int tmp=1LL*C(n,x)*C(m,y)%mod*g[n*m-(n-x)*(m-y)]%mod;
if ((x+y)&1) inc(ans,tmp); else dec(ans,tmp);
}
printf("%d\n",ans);
}
return 0;
}
J. Social Media
签到题，先统计出初始时能看到的评论数量，然后对于每个人 \(i\) 求出将其选为朋友后能立刻增加的评论数 \(c_i\)
考虑最后选择的人是 \(i,j\)，则贡献为 \(c_i+c_j\)，再额外加上仅由 \(i,j\) 构成的评论数量
可以枚举定下其中一个，枚举另一个的时候分两种情况，一种是 \(i,j\) 作为评论出现过的，这种情况的总数是 \(O(m)\) 的；否则剩下的就是在没出现过的中选一个最大的，拿个 multiset 维护下即可
#include<cstdio>
#include<iostream>
#include<set>
#include<map>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,n,m,k,x,f[N],a[N],b[N],c[N],key[N]; map <int,int> v[N];
int main()
{
// freopen("J.in","r",stdin);
for (scanf("%d",&t);t;--t)
{
scanf("%d%d%d",&n,&m,&k);
for (RI i=1;i<=k;++i) f[i]=c[i]=key[i]=0,v[i].clear();
for (RI i=1;i<=n;++i)
scanf("%d",&x),f[x]=1;
int ans=0;
for (RI i=1;i<=m;++i)
{
scanf("%d%d",&a[i],&b[i]);
if (a[i]==b[i])
{
if (f[a[i]]) ++ans; else ++c[a[i]];
continue;
}
int tmp=f[a[i]]+f[b[i]];
if (tmp==2) ++ans; else
if (tmp==1)
{
if (f[a[i]]) ++c[b[i]]; else ++c[a[i]];
} else v[a[i]][b[i]]+=1,v[b[i]][a[i]]+=1;
}
if (n+2>=k) { printf("%d\n",m); continue; }
multiset <int> st;
for (RI i=1;i<=k;++i) if (!f[i]) st.insert(c[i]);
int sum=0;
for (RI i=1;i<=k;++i)
{
if (f[i]) continue;
int ret=c[i]; st.erase(st.find(c[i]));
for (auto [to,w]:v[i])
{
st.erase(st.find(c[to]));
ret=max(ret,c[i]+c[to]+w);
}
if (!st.empty()) ret=max(ret,c[i]+*st.rbegin());
for (auto [to,w]:v[i]) st.insert(c[to]);
sum=max(sum,ret); st.insert(c[i]);
}
printf("%d\n",ans+sum);
}
return 0;
}
K. Strips
把所有相邻的黑色位置之间的部分单独拿出来，显然每个都是独立的问题
考虑一个 naive 的贪心，为了尽可能减少纸条的数量，我们总是把纸条尽可能地偏左摆放，直到不能 cover 为止
但这样会有个问题，即最后一张纸条可能会超出右边界，就可能会把有解的情况判成无解
要解决这个问题也很简单，我们对每个红色格子维护出要覆盖它对应的最左端点，以及上一个无法覆盖的红色格子，从后往前再推一遍即可
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <functional>
#include <cassert>
bool solve(int L, const std::vector<int> &a, int R, int w, std::function<void(int)> callback) {
int n = a.size();
std::vector<int> p(n), pre(n);
// std::cerr << "debug: ";
// for(int i = 0; i < n; ++i) std::cerr << a[i] << char(i == n - 1 ? 10 : 32);
int l = -1;
for(int r = 0; r < n; ++r) {
while(a[l + 1] <= a[r] - w) l++;
if(l < 0) p[r] = std::max(L + 1, a[r] - w + 1);
else p[r] = std::max(p[l] + w, a[r] - w + 1);
pre[r] = l;
}
if(p[n - 1] + w - 1 >= R) return false;
for(int i = n - 1; i >= 0; i = pre[i]) callback(p[i]);
return true;
}
void work() {
int n, m, k, w;
std::cin >> n >> m >> k >> w;
std::vector<std::pair<int, int>> c(n + m + 2);
for(int i = 0; i < n; ++i) std::cin >> c[i].first, c[i].second = 1;
for(int i = n; i < n + m; ++i) std::cin >> c[i].first, c[i].second = 0;
c[n + m] = {w + 1, 0};
c[n + m + 1] = {0, 0};
std::sort(c.begin(), c.end());
int ans = 0, l = 0;
std::vector<int> strip;
while(l < c.size()) {
int pre_l = l; l++;
while(l < c.size() && c[l].second) l++;
if(l == c.size()) break;
assert(!c[pre_l].second && !c[l].second);
if(pre_l == l - 1) continue;
if(c[l].first - c[pre_l].first - 1 < k) {
std::cout << "-1\n";
return ;
}
std::vector<int> a(l - pre_l - 1);
for(int i = pre_l + 1; i < l; ++i) a[i - pre_l - 1] = c[i].first;
bool flag = solve(c[pre_l].first, a, c[l].first, k, [&](int pos) {
ans++;
strip.push_back(std::min(pos, c[l].first - k));
});
if(!flag) return std::cout << "-1\n", void(0);
// pre = c[l].first;
}
std::cout << ans << char(10);
for(int i = 0; i < strip.size(); ++i) std::cout << strip[i] << char(i == strip.size() - 1 ? 10 : 32);
return ;
}
int main() {
std::ios::sync_with_stdio(false);
int T; std::cin >> T; while(T--) work();
return 0;
}
M. Ordainer of Inexorable Judgment
唉几何，直接扔给祁神然后坐等过题，我题目都没看
#include<bits/stdc++.h>
using namespace std;
#define int long long
using LD = long double;
const LD eps = 1e-8;
const LD PI = acosl(-1.0L);
LD sqr(LD x) {return x*x;}
int sgn(LD x) {return fabs(x)<=eps ? 0 : (x>eps ? 1 : -1);}
struct Point {
LD x, y;
LD operator^(const Point &b) const {return x*b.y - y*b.x;}
LD operator*(const Point &b) const {return x*b.x + y*b.y;}
bool operator<(const Point &b) const {return sgn((*this)^b) > 0;}
Point operator*(const LD &b) const {return Point{x*b, y*b};}
Point operator+(const Point &b) const {return Point{x+b.x, y+b.y};}
Point operator-(const Point &b) const {return Point{x-b.x, y-b.y};}
LD len() const {return sqrtl(x*x+y*y);}
LD len2() const {return x*x+y*y;}
Point rot(const LD &cosr, const LD &sinr) {
return {x*cosr - y*sinr, x*sinr + y*cosr};
}
LD ang(const Point &a) const {
return atan2l((*this)^a, (*this)*a);
}
};
LD p_seg_dis2(Point p, Point a, Point b) {
if (sgn((p-a)*(b-a))<=0 || sgn((p-b)*(a-b))<=0)
return min((a-p).len2(), (b-p).len2());
Point v = b-a;
LD res = abs(v ^ (p-a)) / v.len();
return sqr(res);
}
struct Circle {
Point c;
LD r;
pair<Point, Point> tangent(const Point &a) const {
Point e = a-c;
e = e * (r / e.len());
const LD costh = r / (c-a).len(), sinth = sqrtl(1 - sqr(costh));
const Point t1 = c + e.rot(costh, -sinth), t2 = c + e.rot(costh, sinth);
return {t1, t2};
}
};
int n, xx0, yy0, d;
LD t;
Circle cir;
vector<Point> conv;
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
cout << setiosflags(ios::fixed) << setprecision(12);
cin >> n >> xx0 >> yy0 >> d >> t;
cir = Circle{{0.0L, 0.0L}, (LD)d};
conv.reserve(n);
for (int i=0; i<n; ++i) {
int x, y; cin >> x >> y;
conv.push_back(Point{(LD)x, (LD)y});
}
bool ok = false;
for (int i=0; i<n; ++i) {
if (sgn(sqr(d) - p_seg_dis2({0, 0}, conv[i], conv[(i+1)%n])) >= 0) {
ok = true; break;
}
}
bool flag = true;
for (int i=0; i<n; ++i) {
if (sgn((conv[(i+1)%n]-conv[i])^(Point{0, 0}-conv[i])) < 0) {
flag = false; break;
}
}
if (flag) ok=true;
if (ok) {
cout << t << '\n';
return 0;
}
vector<Point> vt1, vt2;
for (int i=0; i<n; ++i) {
auto [t1, t2] = cir.tangent(conv[i]);
vt1.push_back(t1);
vt2.push_back(t2);
}
auto findmn = [&](vector<Point> &vec){
auto res = vec[0];
for (auto p : vec) res = min(res, p);
return res;
};
auto findmx = [&](vector<Point> &vec){
auto res = vec[0];
for (auto p : vec) res = max(res, p);
return res;
};
auto t1 = findmx(vt1);
auto t2 = findmn(vt2);
auto rt1 = t1.rot(0, 1), rt2 = t2.rot(0, -1);
LD ang = rt2.ang(rt1);
LD ans = 0.0L;
int round = floor(t / (2*PI) + eps);
ans += round * ang;
t -= round*2*PI;
Point v = Point{xx0, yy0};
LD th2 = v.ang(rt2); if (sgn(th2) < 0) th2 = 2*PI+th2;
LD th1 = v.ang(rt1); if (sgn(th1) < 0) th1 = 2*PI+th1;
// printf("th2=%Lf th1=%Lf\n", th2, th1);
if (sgn(rt2^v)>0 && sgn(v^rt1)>0) {
if (t < th1) ans += t;
else ans += th1 + (sgn(t-th2)>=0 ? t-th2 : 0);
} else {
if (t > th2) ans += min(th1, t) - th2;
}
cout << ans << '\n';
return 0;
}
Postscript
评价是感觉又是啥都没干被队友带飞了，希望这周的 CCPC 郑州能躺块 Au 吧
标签：std,include,const,Contest,int,Regional,Nanjing,return,now From： https://www.cnblogs.com/cjjsb/p/18548805