Preface
唉最近天天前期犯病，读错题占用大量机时还红温，纯在靠队友兜底
H板题但刚开始因为没打印自己的KM板子就写个了MCMF上去，然后直接TLE飞，后面找了个别人的板子抄上去才过，I题一个傻逼题题意读错爆WA两发
最后1h把L题扔给队友然后跑去看ECF滚榜直播了，只能说从此清北电的格局打开了，明年估计能吸引一批银牌✌来电专
A. Ancient Towers
徐神好像有个\(O(n^3\log n)\)的做法，但不太好写后面没时间就弃疗了
B. Because, Art!
ORZ徐神秒了此题，直接挽救我们队于水火之中
首先仅需考虑最大值如何处理，最小值的情况可以通过将其中一个数组全部取反后跑最大值的算法，然后再取反输出
不难想到以下贪心，先将两个数组都排序，然后每次挑选两个最大的正数相乘或者两个绝对值最大的负数相乘
但这样做下去会遇到只剩下一种符号的数和另一种符号的数相乘的情况（即不管怎么乘都是负的）
手玩一下会发现最优的策略就是类似卷积一样将绝对值较大的和另一个符号的绝对值较小的相乘
因此写个FFT维护下这个卷积过程即可，总复杂度\(O(n\log n)\)
#include <bits/stdc++.h>
using llsi = long long signed int;
std::vector<llsi> poly_mul(const std::vector<llsi> &a, const std::vector<llsi> &b);
std::vector<llsi> solve(
const std::vector<llsi> &f,
const std::vector<llsi> &t
) {
std::vector<llsi> a = f, b = t;
std::sort(a.begin(), a.end()); std::sort(b.begin(), b.end());
int l = 0, r = a.size() - 1;
std::vector<llsi> res;
llsi cur = 0;
while(l <= r) {
llsi pl = a[l] * b[l];
llsi pr = a[r] * b[r];
if(pl < 0 && pr < 0) break;
if(pl > pr) cur += pl, l += 1;
else cur += pr, r -= 1;
res.push_back(cur);
}
if(l > r) return res;
std::vector<llsi> sa(a.begin() + l, a.begin() + r + 1);
std::vector<llsi> sb(b.begin() + l, b.begin() + r + 1);
if(sa.front() < 0) std::reverse(sa.begin(), sa.end());
else std::reverse(sb.begin(), sb.end());
// std::cerr << "debug\n";
// for(int i = 0; i < sa.size(); ++i) std::cerr << sa[i] << char(i == sa.size() - 1 ? 10 : 32);
// for(int i = 0; i < sb.size(); ++i) std::cerr << sb[i] << char(i == sb.size() - 1 ? 10 : 32);
auto mul = poly_mul(sa, sb);
// for(int i = 0; i < mul.size(); ++i) std::cerr << mul[i] << char(i == mul.size() - 1 ? 10 : 32);
for(int i = 0; res.size() < a.size(); ++i) res.push_back(mul[i] + cur);
return res;
}
int main(void) {
std::ios::sync_with_stdio(false);
// std::vector<llsi> a = {1, 2, 1}, b = poly_mul(a, a);
int n; std::cin >> n;
std::vector<llsi> f(n), c(n);
for(auto &f: f) std::cin >> f; for(auto &c: c) std::cin >> c;
auto max_value = solve(f, c);
for(auto &c: c) c = -c;
auto min_value = solve(f, c);
for(int i = 0; i < n; ++i) std::cout << -min_value[i] << ' ' << max_value[i] << char(10);
return 0;
}
const int NN=400005;
typedef long double LDB;
struct Complex
{
LDB x,y;
inline Complex (const LDB& X=0,const LDB& Y=0)
{
x=X; y=Y;
}
inline Complex conj(void)
{
return Complex(x,-y);
}
friend inline Complex operator + (const Complex& A,const Complex& B)
{
return Complex(A.x+B.x,A.y+B.y);
}
friend inline Complex operator - (const Complex& A,const Complex& B)
{
return Complex(A.x-B.x,A.y-B.y);
}
friend inline Complex operator * (const Complex& A,const Complex& B)
{
return Complex(A.x*B.x-A.y*B.y,A.x*B.y+A.y*B.x);
}
}A[NN],B[NN];
namespace Poly
{
const LDB PI=acosl(-1);
int lim,p,rev[NN];
inline void init(const int& n)
{
for (lim=1,p=0;lim<=n;lim<<=1,++p);
for (int i=0;i<lim;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<p-1);
}
inline void FFT(Complex *f,const int& opt)
{
for (int i=0;i<lim;++i) if (i<rev[i]) std::swap(f[i],f[rev[i]]);
for (int i=1;i<lim;i<<=1)
{
Complex D(cosl(PI/i),sinl(PI/i)*opt);
for (int j=0;j<lim;j+=(i<<1))
{
Complex W(1,0);
for (int k=0;k<i;++k,W=W*D)
{
Complex x=f[j+k],y=W*f[i+j+k];
f[j+k]=x+y; f[i+j+k]=x-y;
}
}
}
if (!~opt)
{
for (int i=0;i<lim;++i) f[i].x/=lim;
}
}
};
std::vector<llsi> poly_mul(const std::vector<llsi> &a, const std::vector<llsi> &b) {
int n=a.size(),m=b.size(); Poly::init(n+m-1);
for (int i=0;i<n;++i) A[i]=Complex(a[i],0);
for (int i=n;i<Poly::lim;++i) A[i]=Complex();
for (int i=0;i<m;++i) B[i]=Complex(b[i],0);
for (int i=m;i<Poly::lim;++i) B[i]=Complex();
Poly::FFT(A,1); Poly::FFT(B,1);
for (int i=0;i<Poly::lim;++i) A[i]=A[i]*B[i];
Poly::FFT(A,-1); std::vector<llsi> c;
for (int i=0;i<n+m-1;++i) c.push_back(llsi(std::round(A[i].x)));
return c;
}
C. Cyclists versus Clouds
不可做题，题目都没看
D. Daily Turnovers
没看*2，这场前半部分好多题都没写的说
E. Expedition Plans
没看*3，写不了一点
F. Fields Division
签到，不难发现\(2^n\)一个的权值就比所有人都大，因此最优策略是把\(n\)分给A，并把\(n-1\)分给B
然后剩下的点尽可能地都分给B，分不了了再分给A
#include<cstdio>
#include<iostream>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=300005;
int n,m,x,y,bel[N]; vector <int> v[N];
inline void DFS(CI now)
{
bel[now]=1; for (auto to:v[now]) if (to!=n&&!bel[to]) DFS(to);
}
int main()
{
RI i; for (scanf("%d%d",&n,&m),i=1;i<=m;++i)
scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
for (DFS(n-1),i=1;i<=n;++i) putchar(bel[i]?'B':'A');
return 0;
}
G. Generator Tree
没看*4，yysy这场难度比之前打的两场拉美的都大啊
H. Hamilton - The Musical
很一眼的题，刚开始想了个错误的Flow的做法，后面发现犯病了就是个trivial的匹配问题
首先我们把所有奇数点取出来，不难发现目标序列中也恰好有数量相同的空位留以匹配
稍微讨论一下很容易得到每个数放在每个空位带来的代价，注意边界的情况
然后大力跑二分图最小权完美匹配即可，这题用一般的网络流做法会被卡，只能上\(O(n^3)\)的KM
#include<cstdio>
#include<iostream>
#include<queue>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=505,INF=1e18;
int n,a[N][N];
namespace KM
{
int w[N][N],kx[N],ky[N],py[N],vy[N],slk[N],pre[N];
inline void addedge(CI x,CI y,CI z)
{
w[(x+1)/2][(y+1)/2]=-z;
}
inline int solve(CI n)
{
RI i,j,k; for (i=1;i<=n;++i) for (j=1;j<=n;++j) kx[i]=max(kx[i],w[i][j]);
for (i=1;i<=n;++i)
{
for (j=0;j<=n;++j) vy[j]=pre[j]=0,slk[j]=INF;
int k=0,p=-1; for (py[k=0]=i;py[k];k=p)
{
int d=INF; vy[k]=1; int x=py[k];
for (j=1;j<=n;++j) if (!vy[j])
{
int t=kx[x]+ky[j]-w[x][j];
if (t<slk[j]) slk[j]=t,pre[j]=k;
if (slk[j]<d) d=slk[j],p=j;
}
for (j=0;j<=n;++j)
if (vy[j]) kx[py[j]]-=d,ky[j]+=d; else slk[j]-=d;
}
for (;k;k=pre[k]) py[k]=py[pre[k]];
}
int ret=0; for (i=1;i<=n;++i) ret+=kx[i]+ky[i];
return -ret;
}
};
using namespace KM;
signed main()
{
RI i,j; scanf("%lld",&n);
for (i=1;i<=n;++i) for (j=1;j<=n;++j) scanf("%lld",&a[i][j]);
int m=(n+1)/2; for (i=1;i<=2*m;i+=2) addedge(2,i,a[2][i]);
if (n%2==1)
{
for (i=1;i<=2*m;i+=2) addedge(2*m,i,a[n-1][i]);
for (i=4;i<=2*m-2;i+=2) for (j=1;j<=2*m;j+=2)
addedge(i,j,a[i-2][j]+a[i][j]);
} else
{
for (i=4;i<=2*m;i+=2) for (j=1;j<=2*m;j+=2)
addedge(i,j,a[i-2][j]+a[i][j]);
}
return printf("%lld",solve(m)),0;
}
I. Invested Money
妈的题意杀，因为没看清题意爆吃两发WA，最后还滚去重写了一遍
这题只要确定\(d_i\)天之前存钱的那天是星期几就简单了，手玩一下我们会发现存在以下的循环\(1\to 3\to 5\to 1\)，共\(91\)天，但同时还有\(2\to 4\to 1\)的情况需要特判
然后发现\(d_i=0\)的情形不好处理，建议是直接特判
#include<cstdio>
#include<iostream>
#include<string>
#define RI register int
#define CI const int&
using namespace std;
string Date; int n,x,d;
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
cin>>Date>>n; int ans=2e9;
if (Date=="Mon") d=0; else
if (Date=="Tue") d=1; else
if (Date=="Wed") d=2; else
if (Date=="Thu") d=3; else
if (Date=="Fri") d=4; else
if (Date=="Sat") d=5; else
if (Date=="Sun") d=6;
for (RI i=1;i<=n;++i)
{
cin>>x; int st=(d-x%7+7)%7;
if (x==0)
{
if (d<=2) ans=min(ans,30);
else ans=min(ans,d==3?32:31);
continue;
}
auto solve=[&](int x)
{
x%=91; if (x==0) { ans=min(ans,0); return; }
if (x<=30) ans=min(ans,30-x); else
if (x<=60) ans=min(ans,60-x); else
ans=min(ans,91-x);
};
if (st==0) solve(x); else
if (st==1)
{
if (x<=62)
{
if (x<=30) ans=min(ans,30-x); else
ans=min(ans,62-x); continue;
}
x-=62; solve(x);
} else
if (st==2)
{
if (x<=61)
{
if (x<=30) ans=min(ans,30-x); else
ans=min(ans,61-x); continue;
}
x-=61; solve(x);
} else
if (st==3)
{
if (x<=32)
{
ans=min(ans,32-x); continue;
}
x-=32; solve(x);
} else
if (st==4)
{
if (x<=31)
{
ans=min(ans,31-x); continue;
}
x-=31; solve(x);
}
}
return printf("%d",ans),0;
}
J. Joining Pairs
这题没一点参与，纯被队友秒了
注意到只要两个点有一个不在边界上，那么这对点不论怎样都能连上
因此只要判断边界上的点之间是否会交叉即可，这里可以沿顺时针方向将边界离散成一维的
然后用一个栈来维护所有点，每次判断栈顶和当前点是否配对，若配对则弹出栈顶；否则将当前元素入栈，最后看剩余在栈中的元素是否构成回文串即可
#include <bits/stdc++.h>
#define int int64_t
int32_t main(void) {
std::ios::sync_with_stdio(false);
int w, h; std::cin >> w >> h;
int n; std::cin >> n;
std::vector<std::pair<int, int> > ps;
for(int i = 0, x1, y1, x2, y2; i < n; ++i) {
std::cin >> x1 >> y1 >> x2 >> y2;
auto add = [&](int x, int y) -> long long {
if(x == 0) return y;
if(y == h) return x + h;
if(x == w) return w + h + h - y;
if(y == 0) return w + h + w + h - x;
return -1L;
};
int t1 = add(x1, y1), t2 = add(x2, y2);
if(t1 >= 0 && t2 >= 0)
ps.push_back({t1, i}),
ps.push_back({t2, i});
}
std::sort(ps.begin(), ps.end());
std::vector<int> stack;
for(auto [p, i]: ps) {
if(stack.size() && stack.back() == i) stack.pop_back();
else stack.push_back(i);
}
for(int i = 0, j = stack.size() - 1; i < j; ++i, --j)
if(stack[i] != stack[j]) return std::cout << 'N' << std::endl, 0;
std::cout << 'Y' << std::endl;
return 0;
}
K. KIARA is a Recursive Acronym
签到题，暴力验证每个单词即可
#include<cstdio>
#include<iostream>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int N=1e6+5;
int n,ext[N][30],all[30]; char s[N];
int main()
{
RI i,j; for (scanf("%d",&n),i=1;i<=n;++i)
{
scanf("%s",s+1); int m=strlen(s+1);
for (j=1;j<=m;++j) ext[i][s[j]-'A']=1;
all[s[1]-'A']=1;
}
for (i=1;i<=n;++i)
{
bool flag=1; for (j=0;j<26;++j)
if (ext[i][j]&&!all[j]) { flag=0; break; }
if (flag) return puts("Y"),0;
}
return puts("N"),0;
}
L. Leaving Yharnam
ORZ这题又是被队友秒了，那么问题来了我这场比赛在干嘛，原来是在红温占机时啊
这题首先发现可以大力枚举easygoing的人初始时恰好坐了\(k\)对座位的情况，这个概率就是
\[\frac{C_n^k\times 2^{G-2k}\times C_{n-k}^{G-2k}}{C_{2n}^G} \]主要要注意\(2^{G-2k}\)不要忘记乘了，因为剩下单独坐的人可以选择坐某对座位中的任意一个
然后确定了\(k\)后可以发现后面两种人的做法其实就唯一确定了，然后就大力分类讨论即可
祁神比赛的时候写了种计数的写法但一直WA，赛后先写了个模拟的做法过了后再对拍改出了计数的做法
模拟CODE
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1e9+7;
void mul(int &x, int a){x=x*a%MOD;}
void add(int &x, int a){if ((x+=a)>=MOD) x-=MOD;}
void sub(int &x, int a){if ((x-=a)<0) x+=MOD;}
int powe(int x, int p){
int res=1;
while (p>0){if (p&1) mul(res, x); mul(x, x); p>>=1;}
return res;
}
const int N = 2e6+5;
int fac[N], invf[N];
int C(int n, int m){return fac[n]*invf[n-m]%MOD*invf[m]%MOD;}
signed main(){
fac[0]=fac[1]=invf[0]=invf[1]=1;
for (int i=2; i<N; ++i) fac[i] = i*fac[i-1]%MOD;
invf[N-1] = powe(fac[N-1], MOD-2);
for (int i=N-1; i>2; --i) invf[i-1] = i*invf[i]%MOD;
int n, G0, I0, E0;
cin >> n >> G0 >> I0 >> E0;
int ans=0;
if (E0+G0>=2*n) cout << 2*n << '\n';
else{
for (int k=max(0LL, G0-n); k<=min(G0/2, n); ++k){
int P = C(n, k)*powe(2, G0-2*k)%MOD*C(n-k, G0-2*k)%MOD*powe(C(2*n, G0), MOD-2)%MOD;
int G=G0, I=I0, E=E0;
int res=G;
int cntG=G-2*k, cntI=0, cntE=0, cnt0=n+k-G;
int tmp=min(cntG, E);
cntG-=tmp, E-=tmp, add(res, tmp);
if (E>0){
cnt0-=E/2, res+=E/2*2;
if (E%2) --cnt0, ++cntE;
}
tmp = min(cnt0, I);
cnt0-=tmp, I-=tmp, cntI+=tmp, add(res, tmp);
if (I>0){
if (cntE>0) --cntE, --I, add(res, 1);
else if (cntG>0){
tmp = min(cntG, I);
I-=tmp, cntG-=tmp;
}
tmp = min(cntI, I);
cntI-=tmp, I-=tmp, sub(res, tmp);
}
add(ans, res*P%MOD);
}
// printf("sum=%lld\n", sum);
cout << ans << '\n';
}
return 0;
}
计数CODE
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1e9+7;
void mul(int &x, int a){x=x*a%MOD;}
void add(int &x, int a){if ((x+=a)>=MOD) x-=MOD;}
int powe(int x, int p){
int res=1;
while (p>0){if (p&1) mul(res, x); mul(x, x); p>>=1;}
return res;
}
const int N = 2e6+5;
int fac[N], invf[N];
int C(int n, int m){return fac[n]*invf[n-m]%MOD*invf[m]%MOD;}
int n, G, I, E;
signed main(){
fac[0]=fac[1]=invf[0]=invf[1]=1;
for (int i=2; i<N; ++i) fac[i] = i*fac[i-1]%MOD;
invf[N-1] = powe(fac[N-1], MOD-2);
for (int i=N-1; i>2; --i) invf[i-1] = i*invf[i]%MOD;
cin >> n >> G >> I >> E;
int ans=0;
if (E+G>=2*n) cout << 2*n << '\n';
else{
int sum=0;
for (int k=max(0LL, G-n); k<=min(G/2, n); ++k){
int P = C(n, k)*powe(2, G-2*k)%MOD*C(n-k, G-2*k)%MOD*powe(C(2*n, G), MOD-2)%MOD;
add(sum, P);
int res=0;
if (E<=G-2*k){
res = E+G;
if (I<=n-k-E) add(res, min(I, n+k-G));
else add(res, max(0LL, 2*n-E-G-I));
}else{
res = (G+E)/2*2;
int col = n-(G+E)/2;
// printf("I=%lld col=%lld\n", I, col);
// if (I>=col) add(res, max(0LL, 2*col-I));
// else add(res, I);
if (0==(G+E)%2){
if (I>col) add(res, max(0LL, 2*col-I));
else add(res, I);
}else{
if (I>col-1) add(res, max(1LL, 2*col-I));
else add(res, I);
}
}
// printf("k=%lld res=%lld\n", k, res);
add(ans, res*P%MOD);
}
// printf("sum=%lld\n", sum);
cout << ans << '\n';
}
return 0;
}
M. Most Ordered Way
这类字典序最小的题目的思路都是一样的，从前往后依次贪心确定每一位
这题由于模型非常典，经典的贪心做法就是根据结束时间排序然后依次做即可
但如果直接暴力先枚举位置，再枚举填哪个数，最后贪心check的话复杂度是\(O(n^3)\)的，无法通过
后面徐神发现可以再具体再某一位填数之前先预处理一下所有可用的数，每次填数过程相当于是一个删除一个元素并判断剩下的元素是否可行的过程，手玩一下发现是可以维护的
总复杂度\(O(n^2)\)
#include <bits/stdc++.h>
using llsi = long long signed int;
int main(void) {
int n; std::cin >> n;
std::vector<llsi> t(n), d(n), s(n);
for(int i = 0; i < n; ++i) std::cin >> t[i] >> d[i];
std::vector<int> wr(n);
for(int i = 0; i < n; ++i) wr[i] = i;
std::sort(wr.begin(), wr.end(), [&](const int &a, const int &b) {
return d[a] < d[b];
});
auto upds = [&] (const int &i) {
s[wr[i]] = t[wr[i]];
if(i) s[wr[i]] += s[wr[i - 1]];
};
for(int i = 0; i < n; ++i) {
for(int j = std::max(0, i - 10); j < n; ++j) {
upds(j);
if(d[wr[j]] < s[wr[j]]) {
std::cout << '*' << std::endl;
return 0;
}
}
int min_id = i;
llsi min_delta = d[wr[i]] - s[wr[i]];
for(int j = i + 1; j < n; ++j) {
int S = t[wr[j]];
if(i) S += s[wr[j - 1]];
if(t[wr[j]] <= min_delta && S <= d[wr[j]] && wr[j] < wr[min_id]) min_id = j;
min_delta = std::min(min_delta, d[wr[j]] - s[wr[j]]);
}
while(min_id > i) std::swap(wr[min_id], wr[min_id - 1]), min_id -= 1;
upds(i);
}
for(int i = 0; i < n; ++i) std::cout << wr[i] + 1 << char(i == n - 1 ? 10 : 32);
return 0;
}
Postscript
本来徐神说找场拉美的放松一下，结果还是被腐乳了
明天就要回衢州了，后面的训练都要三人三机网上连线打了的说
标签：std,Latin,const,Contest,int,res,Regional,vector,include From： https://www.cnblogs.com/cjjsb/p/17964037