Preface
这几天里打的最好的一场了,虽然后面写I唐的不行浪费了好多时间
但好在最后都改出来了并且最后Rush出了L题,4h57min绝杀,9题收场
只能说恰好在祁神缺席的这场没有几何,没有被腐乳
而且这场打完发现只有韩文题解没有英文题解,这下直接不用补题了爽歪歪
A. Autonomous Vehicle
大力模拟题,但被徐神1h斩于马下
由于数据范围不大,直接干就完事,但要注意可能会多次走回起点因此需要对循环走的部分取个模
#include <bits/stdc++.h>
struct Line {
int bx, by, ex, ey;
std::vector<std::pair<int, int> > crs;
};
std::vector<Line> lines;
bool crs(const Line &a, const Line &b) {
int abx = std::min(a.bx, a.ex), aex = std::max(a.bx, a.ex);
int aby = std::min(a.by, a.ey), aey = std::max(a.by, a.ey);
int bbx = std::min(b.bx, b.ex), bex = std::max(b.bx, b.ex);
int bby = std::min(b.by, b.ey), bey = std::max(b.by, b.ey);
return
abx == aex && bbx < abx && aex < bex && aby < bby && bey < aey ||
aby == aey && bby < aby && aey < bey && abx < bbx && bex < aex;
}
int main(void) {
std::ios::sync_with_stdio(false);
int n, t;
std::cin >> n >> t;
lines.resize(n);
for(auto &[bx, by, ex, ey, crs]: lines)
std::cin >> bx >> by >> ex >> ey;
for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) {
Line &a = lines[i], &b = lines[j];
if(a.bx == a.ex && b.bx == b.ex) continue;
if(a.by == a.ey && b.by == b.ey) continue;
if(!crs(a, b)) continue;
if(a.bx == a.ex) a.crs.push_back({b.by, j});
else a.crs.push_back({b.bx, j});
}
for(int i = 0; i < n; ++i) std::sort(lines[i].crs.begin(), lines[i].crs.end());
int vx, vy, sta = 0, cx = lines[0].bx, cy = lines[0].by;
if(lines[0].bx == lines[0].ex) vx = 0, vy = (lines[0].by < lines[0].ey ? 1 : -1);
else vy = 0, vx = (lines[0].bx < lines[0].ex ? 1 : -1);
int T = t, ch = 0;
int *vc, *cc, be, ed;
for(;;) {
if(sta == 0 && cx == lines[0].bx && cy == lines[0].by) {
ch += 1;
if(ch == 2) t %= T - t;
}
// std::cerr << "current: " << cx << ' ' << cy << ' ' << vx << ' ' << vy << ' ' << t << char(10);
auto [bx, by, ex, ey, crs] = lines[sta];
if(vx) vc = &vx, cc = &cx, be = std::min(bx, ex), ed = std::max(bx, ex);
else vc = &vy, cc = &cy, be = std::min(by, ey), ed = std::max(by, ey);
if(*vc > 0) {
int l = 0, r = crs.size(), mid;
while(l < r) {
mid = (l + r) >> 1;
if(crs[mid].first > *cc) r = mid;
else l = mid + 1;
}
if(l == crs.size()) {
int ts = ed - *cc;
if(t > ts) {
*cc += ts;
t -= ts;
*vc = -*vc;
} else {
*cc += t;
break;
}
} else {
int ts = crs[l].first - *cc;
if(t > ts) {
*cc += ts;
t -= ts;
int temp = vx;
vx = -vy;
vy = temp;
sta = crs[l].second;
} else {
*cc += t;
break;
}
}
} else {
int l = -1, r = crs.size() -1, mid;
while(l < r) {
int mid = (l + r + 1) >> 1;
if(crs[mid].first < *cc) l = mid;
else r = mid - 1;
}
if(l == -1) {
int ts = *cc - be;
if(t > ts) {
*cc -= ts;
t -= ts;
*vc = -*vc;
} else {
*cc -= t;
break;
}
} else {
int ts = *cc - crs[l].first;
if(t > ts) {
*cc -= ts;
t -= ts;
int temp = vx;
vx = -vy;
vy = temp;
sta = crs[l].second;
} else {
*cc -= t;
break;
}
}
}
}
std::cout << cx << ' ' << cy << std::endl;
return 0;
}
B. Commemorative Dice
签到,直接枚举即可
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
int a[10],b[10],wins;
int main()
{
RI i,j; for (i=1;i<=6;++i) scanf("%d",&a[i]);
for (i=1;i<=6;++i) scanf("%d",&b[i]);
for (i=1;i<=6;++i) for (j=1;j<=6;++j)
if (a[i]>b[j]) ++wins; int g=__gcd(wins,36);
return printf("%d/%d",wins/g,36/g),0;
}
C. Dessert Café
不难发现边权是没有意义的,最后good
的点一定在所有关键点之间的路径上
而维护这些路径可以类似于虚树,每次拿出两个关键点然后把它们之间的路径标记,并且将LCA也标为关键点
但由于这题只要统计一次所以可以直接暴力往上跳,同时标记经过的点,最后复杂度还是对的
注意特判\(k=1\)的情形
#include <bits/stdc++.h>
constexpr int $n = 100000 + 10;
std::vector<int> out[$n];
int dep[$n], isRed[$n], fa[$n];
std::priority_queue<std::pair<int, int> > pq;
void dfs(int now) {
dep[now] = dep[fa[now]] + 1;
for(auto ch: out[now]) if(ch != fa[now]) fa[ch] = now, dfs(ch);
}
int main() {
std::ios::sync_with_stdio(false);
int n, k;
std::cin >> n >> k;
for(int i = 1, f, t, v; i < n; ++i) {
std::cin >> f >> t >> v;
out[f].push_back(t);
out[t].push_back(f);
}
dfs(1);
for(int i = 1, a; i <= k; ++i) {
std::cin >> a;
pq.push({dep[a], a});
}
while(pq.size() > 1) {
auto[curDep, cur] = pq.top(); pq.pop();
if(isRed[cur]) continue;
isRed[cur] = 1;
if(cur != 1) pq.push({dep[fa[cur]], fa[cur]});
}
int ans = 0;
for(int i = 1; i <= n; ++i) ans += isRed[i];
std::cout << ans + (k == 1) << std::endl;
return 0;
}
D. Electric Vehicle
不可做题,弃疗
E. Imprecise Computer
Easy题,不难发现对于某个\(i\),只有它和\(i-1,i+1\)的比赛状况是不确定的
而我们从\(1\)的情况开始,就可以顺推出所有数的胜负情况,最后检验下\(n\)的情况是否合法即可
#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=1e6+5;
int n,a[N],b[N],d[N];
int main()
{
RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&d[i]);
bool flag=1; for (i=1;i<n&&flag;++i)
{
bool sign=0;
for (RI p=0;p<2&&!sign;++p) for (RI q=0;q<2&&!sign;++q)
if (abs((a[i]+p)-(b[i]+q))==d[i]) sign=1,a[i+1]=p,b[i+1]=q;
if (!sign) flag=0;
}
if (abs(a[n]-b[n])!=d[n]) flag=0;
return puts(flag?"YES":"NO"),0;
}
F. Ink Mix
题目都没看,弃疗
G. Mobile Robot
被徐神一眼秒了
不妨设一号点最后的位置为\(x\),则答案为\(\max |x-[a_i+d\times (i-1)]|\)
不妨令\(b_i=a_i+d\times (i-1)\),那么最优的\(x\)一定取在\(\{b_i\}\)两个极值的中点处
但这题还有个坑点就是最后的顺序除了\(1\sim n\),还可以是\(n\sim 1\),因此需要把所有坐标取反再跑一次
#include <bits/stdc++.h>
#define Tp template <typename T>
class FileInputOutput
{
private:
static const int S=1<<21;
#define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)
char Fin[S],*A,*B;
public:
Tp inline void read(T& x)
{
x=0; char ch; int flag=1; while (!isdigit(ch=tc())) if (ch=='-') flag=-1;
while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc())); x*=flag;
}
}F;
int64_t solve(std::vector<int64_t> a, int64_t d) {
for(int i = 0; i < a.size(); ++i) a[i] -= int64_t(i) * d;
std::sort(a.begin(), a.end());
return a.back() - a[0];
}
int main(void) {
int64_t n, d; F.read(n); F.read(d);
std::vector<int64_t> a(n);
for(int i = 0; i < n; ++i) F.read(a[i]);
int64_t ans = solve(a, d);
for(int i = 0; i < n; ++i) a[i] = -a[i];
ans = std::min(ans, solve(a, d));
std::cout << (ans >> 1ll);
std::cout << ((ans & 1ll) ? ".5" : ".0");
std::cout << std::endl;
return 0;
}
H. Needle
这题题意我没看,徐神告诉我就是给三个数组\(\{a_i\},\{b_i\},\{c_i\}\),然后求满足\(a_i+c_k=2\times b_j\)的三元组\((i,j,k)\)个数
做法也很简单,注意到数的值域很小,因此直接把每个数有多少个记下来,大力FFT对\(\{a_i\},\{c_i\}\)卷积即可
#include<cstdio>
#include<iostream>
#include<cmath>
#define RI register int
#define CI const int&
using namespace std;
typedef long double LDB;
const int N=1<<20;
namespace Poly
{
const LDB PI=acosl(-1);
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);
}
}; int lim,p,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 FFT(Complex *f,CI opt)
{
RI i,j,k; for (i=0;i<lim;++i) if (i<rev[i]) swap(f[i],f[rev[i]]);
for (i=1;i<lim;i<<=1)
{
Complex D(cosl(PI/i),opt*sinl(PI/i));
for (j=0;j<lim;j+=(i<<1))
{
Complex W(1,0);
for (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 (i=0;i<lim;++i) f[i].x/=lim,f[i].y/=lim;
}
}
}
using namespace Poly;
const int S=30000;
int la,lb,lc,x,B[N]; long long ans; Complex A[N],C[N];
int main()
{
RI i; for (scanf("%d",&la),i=1;i<=la;++i)
scanf("%d",&x),A[x+S].x+=1;
for (scanf("%d",&lb),i=1;i<=lb;++i)
scanf("%d",&x),++B[2*(x+S)];
for (scanf("%d",&lc),i=1;i<=lc;++i)
scanf("%d",&x),C[x+S].x+=1;
for (init(60001*2),FFT(A,1),FFT(C,1),i=0;i<lim;++i) A[i]=A[i]*C[i];
for (FFT(A,-1),i=0;i<=4*S;++i) ans+=(long long)(A[i].x+0.5)*B[i];
return printf("%lld",ans),0;
}
I. Stock Analysis
很有趣味的一个题,又卡时间又卡空间,最后被徐神的智慧之作线段树套分块给干过去了
首先注意到\(n\)的范围很小,因此不妨先大力找出所有的区间,求出其贡献后记为三元组\((l,r,val)\)
同时对于某个询问也记作三元组\((S,E,U)\),然后将所有三元组一起按第三维从小到大排序,并依次处理
这样的好处就是保证了对于某个询问,我们查询出的结果一定满足其贡献\(\le U\)
因此这题只需要维护一个支持单点赋值,矩形求\(\max\)的数据结构即可,一眼可以二维线段树
好家伙但写完发现刚好爆空间,同时这题由于是求\(\max\)也不好用树状数组来解决
危难之际徐神提出不妨将内层的数据结构改成分块,对应的就是一维的单点赋值和区间求\(\max\),这样可以把空间变成原来的\(\frac{1}{4}\)
同时我在写的时候还发现这种写法还完美的利用了分块\(O(1)\)修改\(O(\sqrt n)\)查询的性质,因为这题修改次数远多于询问次数,因此恰好取得了复杂度的完美平衡
最终也是极限的1248ms卡过
#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
typedef long long LL;
const int N=2005,S=50;
const LL INF=1e18;
struct ifo
{
int x,y,id; LL val;
friend inline bool operator < (const ifo& A,const ifo& B)
{
return A.val!=B.val?A.val<B.val:A.id<B.id;
}
}o[4200005]; int n,m,a[N],cnt,blk[N]; LL pfx[N],ans[200005];
class Segment_Tree_X
{
private:
struct BLOCKS
{
LL val[N],tag[S];
inline void updata(CI pos,const LL& mv)
{
val[pos]=mv; tag[blk[pos]]=max(tag[blk[pos]],mv);
}
inline LL query(CI l,CI r,LL ret=-INF)
{
if (blk[l]==blk[r])
{
for (RI i=l;i<=r;++i) ret=max(ret,val[i]); return ret;
}
RI i; for (i=l;i<=blk[l]*S;++i) ret=max(ret,val[i]);
for (i=(blk[r]-1)*S+1;i<=r;++i) ret=max(ret,val[i]);
for (i=blk[l]+1;i<blk[r];++i) ret=max(ret,tag[i]);
return ret;
}
}T[N<<2];
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 init(CI n)
{
RI i,j; for (i=1;i<=n;++i) blk[i]=(i-1)/S+1;
for (i=0;i<=(n<<2);++i)
{
for (j=1;j<=blk[n];++j) T[i].tag[j]=-INF;
for (j=1;j<=n;++j) T[i].val[j]=-INF;
}
}
inline void updata(CI x,CI y,const LL& mv,TN)
{
T[now].updata(y,mv); if (l==r) return; int mid=l+r>>1;
if (x<=mid) updata(x,y,mv,LS); else updata(x,y,mv,RS);
}
inline LL query(CI beg,CI end,TN)
{
if (beg<=l&&r<=end) return T[now].query(beg,end); int mid=l+r>>1; LL ret=-INF;
if (beg<=mid) ret=max(ret,query(beg,end,LS)); if (end>mid) ret=max(ret,query(beg,end,RS)); return ret;
}
#undef TN
#undef LS
#undef RS
}SEG;
int main()
{
RI i,j; for (scanf("%d%d",&n,&m),i=1;i<=n;++i)
scanf("%d",&a[i]),pfx[i]=pfx[i-1]+a[i];
for (i=1;i<=m;++i)
scanf("%d%d%lld",&o[i].x,&o[i].y,&o[i].val),o[i].id=i;
for (cnt=m,i=1;i<=n;++i) for (j=i;j<=n;++j)
o[++cnt]=(ifo){i,j,-1,pfx[j]-pfx[i-1]};
sort(o+1,o+cnt+1); SEG.init(n);
for (i=1;i<=cnt;++i)
if (o[i].id==-1) SEG.updata(o[i].x,o[i].y,o[i].val);
else ans[o[i].id]=SEG.query(o[i].x,o[i].y);
for (i=1;i<=m;++i) if (ans[i]==-INF) puts("NONE"); else printf("%lld\n",ans[i]);
return 0;
}
J. Switches
经典没看题就被徐神秒了
好像就是对原01矩阵求个逆就完事,可以直接上bitset
高斯消元会好写很多
#include <bits/stdc++.h>
std::bitset<1000> a[500];
int main() {
int n; std::cin >> n;
for(int i = 0; i < n; ++i) {
for(int j = 0, t; j < n; ++j)
std::cin >> t, a[i][j] = t;
a[i][i + n] = 1;
}
for(int i = 0; i < n; ++i) {
int t;
for(t = i; t < n; ++t) if(a[t][i]) break;
if(t == n) return std::cout << "-1\n", 0;
std::swap(a[i], a[t]);
for(int j = i + 1; j < n; ++j) if(a[j][i]) a[j] ^= a[i];
}
for(int i = n - 1; i >= 0; --i)
for(int j = i - 1; j >= 0; --j)
if(a[j][i]) a[j] ^= a[i];
for(int i = 0; i < n; ++i) {
std::vector<int> ans;
for(int j = n; j < 2 * n; ++j) if(a[i][j]) ans.push_back(j - n + 1);
for(size_t j = 0; j < ans.size(); ++j)
std::cout << ans[j] << char(j == ans.size() - 1 ? 10 : 32);
}
return 0;
}
K. Tiling Polyomino
做不来捏
L. Two Buildings
最刺激的一集,灵光一现证出决策单调性然后手速Rush完最后卡点通过
首先常规的做法都不好处理,我们考虑分治求解,考虑怎么快速计算跨过中点的区间的贡献
有个trivial的想法就是从中点向两端维护单调栈,保证从\(l\sim mid\)中选出的元素单调递增,从\(mid+1\sim r\)中选出的元素单调递减,显然答案只能在这些元素间产生
但只是这样的话还是不好处理,后面一直隐隐觉得在求出的两个数组中会不会有决策单调性,后面发现果然可以证明
(PS:这题的证明比较巧妙,但由于篇幅原因不便说明,如关心证明方法者可以私聊我)
而决策单调性的题目一旦证出来后就很套路了,这题的话直接上整体二分即可
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=1e6+5;
int n,a[N],ans;
#define Tp template <typename T>
class FileInputOutput
{
private:
static const int S=1<<21;
#define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)
char Fin[S],*A,*B;
public:
Tp inline void read(T& x)
{
x=0; char ch; int flag=1; while (!isdigit(ch=tc())) if (ch=='-') flag=-1;
while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc())); x*=flag;
}
}F;
inline void devide(vector <int>& L,CI l,CI r,vector <int>& R,CI ll,CI rr)
{
if (l>r) return; int mid=l+r>>1,mx=0,pos=0;
for (RI i=ll;i<=rr;++i)
{
int tmp=(a[L[mid]]+a[R[i]])*(R[i]-L[mid]);
if (tmp>mx) mx=tmp,pos=i;
}
ans=max(ans,mx); devide(L,l,mid-1,R,ll,pos); devide(L,mid+1,r,R,pos,rr);
}
inline void solve(CI l,CI r)
{
if (l>=r) return; int mid=l+r>>1;
solve(l,mid); solve(mid+1,r);
vector <int> L,R; RI i;
for (i=mid;i>=l;--i)
{
while (!L.empty()&&a[i]>=a[L.back()]) L.pop_back();
L.push_back(i);
}
for (i=mid+1;i<=r;++i)
{
while (!R.empty()&&a[i]>=a[R.back()]) R.pop_back();
R.push_back(i);
}
reverse(L.begin(),L.end());
devide(L,0,L.size()-1,R,0,R.size()-1);
}
signed main()
{
RI i; for (F.read(n),i=1;i<=n;++i) F.read(a[i]);
return solve(1,n),printf("%lld",ans),0;
}
PS:写完后看同校其它队伍的代码才发现其实不需要分治套整体二分的,先求出两个方向的单调栈后直接上整体二分就行
Postscript
明天就要开始线上2+1训练了,看看效果如何
- ACM-ICPC Regional Contest Seoul 2020acm-icpc regional contest seoul acm-icpc regional contest nanjing programming acm-icpc american regional the universal acm-icpc regional subregional programming acm-icpc contest regional contest macau 2021 regional central contest europe programming shenyang regional contest regional contest nanjing 2022 programming regional contest 2023