Preface
最坐牢的一集,前3h狂出10题然后最后2h坐牢,祁神写J怒调2h最后喜提MLE
赛后我Rush了个H的做法常数太大又喜提TLE,评价是不如去写E题的模拟退火
A. Assessment Disruption
挺精巧的构造题,刚开始以为是构造数据不卡掉想歪了好久,后面仔细一想还是挺简单的
我们将原序列分成两块,前\(\frac{n}{2}\)个元素放的全是两两之间不能比较的,而后\(\frac{n}{2}\)个元素只要从小到大放上可比较的即可(要求后半部分的所有元素均大于前半部分)
不难发现这样每次只会在后半部分删除一个元素,因此保底有\(\frac{n}{2}\)轮
然后每一轮前\(\frac{n}{2}\)个数可以卡满比较次数,大致为\(\frac{n}{2}\times \frac{n}{2}\times \frac{1}{2}\),因此总体来看可以做到\(\frac{n^3}{16}\)次比较,可以通过此题
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=1005;
int n,m,W,w[N];
int main()
{
RI i; for (scanf("%d%d",&n,&W),m=n>>1,i=1;i<=n;++i)
if (W-i>=0) w[i]=W-i; else if (W+i<=10000) w[i]=W+i;
for (i=1;i<=n-m;++i) printf("%d %d\n",w[m+i],i);
for (i=1;i<=m;++i) printf("%d %d\n",w[m-i+1],n-m+i);
return 0;
}
B. Boat Commuter
签到题,对于每张卡模拟一下即可(妈的这题刚开始看错题了WA了一发后红温了好久)
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int n,m,k,x,y,lst[N],ans[N];
int main()
{
RI i,j; for (scanf("%d%d%d",&n,&m,&k),i=1;i<=k;++i)
{
scanf("%d%d",&x,&y);
if (lst[y]==0) lst[y]=x,ans[y]+=100; else
{
ans[y]+=abs(x-lst[y]);
if (x!=lst[y]) ans[y]-=100; lst[y]=0;
}
}
for (i=1;i<=m;++i) printf("%d ",ans[i]);
return 0;
}
C. Clearing Space
ORZ祁神秒了此题
注意到我们可以先枚举钦定一个点强制选,然后从这个点向后可以设计一个DP状态
\(f_{i,j}\)表示向后考虑了\(i\)个点,其中一共选了\(j\)个点时得到的最大面积,转移的话枚举下上次选的是哪个点即可
总复杂度\(O(n^4)\),因为常数极小因此可以跑过
#include<bits/stdc++.h>
#define LD long double
using namespace std;
const LD eps = 1e-8;
int sgn(LD x){return (fabs(x)<=eps ? 0 : (x>eps ? 1 : -1));}
const int N = 105;
struct Pt{
LD x, y;
// Pt operator-(Pt b)const{return Pt{x-b.x, y-b.y};}
// Pt operator+(Pt b)const{return Pt{x-b.x, y-b.y};}
LD crs(Pt b)const{return x*b.y-y*b.x;}
}pt[N];
const LD R = 1000;
const LD PI = acos(-1.0L);
int n, p;
LD A[N];
LD dp[N][N];
signed main(){
cout << setiosflags(ios::fixed) << setprecision(10);
cin >> n;
cin >> p;
for (int i=0; i<n; ++i){
cin >> A[i];
pt[i].x = R*cos(1.0L*A[i]/180*PI);
pt[i].y = R*sin(1.0L*A[i]/180*PI);
}
LD ans = 0.0L;
for (int x=0; x<n; ++x){
dp[0][0] = 0;
for (int i=1; i<=n; ++i){
for (int k=1; k<=min(i, p); ++k){
dp[i][k] = 0.0L;
for (int j=k-1; j<i; ++j){
dp[i][k] = max(dp[i][k], dp[j][k-1] + pt[(x+j)%n].crs(pt[(x+i)%n]));
}
}
}
ans = max(ans, dp[n][p]);
}
cout << ans*0.5L << endl;
return 0;
}
D. Delivery Forces
签到,不难发现最优策略就是拿一个最小值和两个最大值配对
#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]; long long ans;
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
RI i,j; for (cin>>n,i=1;i<=n;++i) cin>>a[i];
for (sort(a+1,a+n+1),i=1,j=n-1;i<=n/3;++i,j-=2) ans+=a[j];
return printf("%lld",ans),0;
}
E. Enchanted Fortress
比赛的时候徐神提出了很多乱搞做法,但由于机时没有去写
后面看题解发现是个meet in middle
或者退火,但都没想清楚怎么写,先坑着
F. Fast Forward
被徐神一眼秒了的题
首先可以用双指针求出每首歌后面第一次插入广告的位置
不难发现这个东西可以套个倍增在外面,表示插入\(2^j\)个广告后的位置,然后就做完了
#include <bits/stdc++.h>
using llsi = long long signed int;
constexpr int $n = 2000000 + 10;
int n, c;
int d[$n];
int nxt[$n][21];
int main(void) {
std::ios::sync_with_stdio(false);
std::cin >> n >> c;
for(int i = 1; i <= n; ++i) std::cin >> d[i], d[i + n] = d[i];
{
int sum = 0;
for(int i = 1; i <= n; ++i) sum += d[i];
if(sum <= c) {
for(int i = 1; i <= n; ++i) std::cout << '0' << char(i == n ? 10 : 32);
return 0;
}
}
int l = 1, r = 1, sum = 0, dn = n << 1;
while(l <= dn) {
while(r <= dn && sum < c) sum += d[r++];
nxt[l][0] = r;
sum -= d[l++];
}
for(int j = 0; j <= 20; ++j) nxt[dn + 1][j] = dn + 1;
for(int i = dn; i; --i) for(int j = 1; j <= 20; ++j)
nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
for(int i = 1; i <= n; ++i) {
int cur = i, ans = 0;
for(int j = 20; j >= 0; --j) {
if(nxt[cur][j] - i < n) {
ans |= 1 << j;
cur = nxt[cur][j];
}
}
std::cout << ans << char(i == n ? 10 : 32);
}
return 0;
}
G. Glacier Travel
又又又又又又被徐神秒了的题
首先当两点在同一线段上移动时显然不是最小值,因此我们总可以拆出两点在不同线段上移动的情况
注意到此时两者之间的距离关于时间是单峰函数,因此可以三分求最小值(证明的话考虑用速度的合成,问题等价于一条直线到某个点的距离,这个显然是单峰的)
但实际写起来感觉细节很多,但徐神好像没一会就写完一遍过了
#include <bits/stdc++.h>
using real = long double;
struct vivi {
real x, y;
inline vivi(real x = 0.0L, real y = 0.0L): x(x), y(y) {}
inline vivi operator +(const vivi &b) const { return vivi {x + b.x, y + b.y}; }
inline vivi operator -(const vivi &b) const { return vivi {x - b.x, y - b.y}; }
inline vivi operator *(const real &b) const { return vivi {x * b, y * b}; }
inline real len2() const { return x * x + y * y; }
inline real len() const { return std::sqrt(x * x + y * y); }
inline real dist(const vivi &b) const { return (*this - b).len(); }
inline friend std::istream& operator >> (std::istream& in, vivi &v) {
return in >> v.x >> v.y;
}
};
int main() {
std::ios::sync_with_stdio(false);
std::cout << std::fixed << std::setprecision(10);
int n; real s;
std::cin >> s >> n;
std::vector<vivi> p(n);
for(auto &[x, y]: p) std::cin >> x >> y;
auto res = [&] (size_t st, real offset) {
return (p[st + 1] - p[st]).len() - offset;
};
auto fwd = [&] (size_t st, real offset) {
auto ll = (p[st + 1] - p[st]).len();
return p[st] + (p[st + 1] - p[st]) * (offset / ll);
};
size_t as = 0, bs = 0;
real af = 0.0L, bf = 0.0L;
while(as < n - 1) {
real r = res(as, af);
if(s > r) {
s -= r;
as += 1;
af = 0;
} else {
af = s;
break;
}
}
if(as == n - 1) {
std::cout << (p.back() - p.front()).len() << char(10);
return 0;
}
real ans = 1e30L;
while(as < n - 1) {
// std::cerr << as << ' ' << af << ' ' << bs << ' ' << bf << char(10);
real ar = res(as, af), br = res(bs, bf);
real l = 0, r = std::min(ar, br);
while(r - l > 1e-8) {
real m1 = (l + l + r) / 3, m2 = (l + r + r) / 3;
vivi ap1 = fwd(as, af + m1);
vivi ap2 = fwd(as, af + m2);
vivi bp1 = fwd(bs, bf + m1);
vivi bp2 = fwd(bs, bf + m2);
if((ap1 - bp1).len() < (ap2 - bp2).len()) r = m2;
else l = m1;
}
vivi ap = fwd(as, af + l);
vivi bp = fwd(bs, bf + l);
ans = std::min(+ans, real((ap - bp).len()));
if(ar < br) {
bf += ar;
as += 1;
af = 0;
} else {
af += br;
bs += 1;
bf = 0;
}
}
std::cout << ans << char(10);
return 0;
}
H. History in Numbers
很裸的一个线段树维护奇奇怪怪的东西的题,但我的写法好像常数太大了就是跑不过
不妨用线段树来维护一个区间内所有有用的信息,朴素的想法是要维护以下三者:
- 该区间是否合法
- 该区间在去重后得到的序列
- 该区间在去重后所有minimum元素构成的序列
但稍作思考我们会发现后两者完全不需要知道整个序列的值,只需要知道至多左边两个、右边两个元素的值即可
因此这题的难点就在于合并区间,耐心讨论下即可,最后修改套个Lazy Tag即可
估计可能是我操作的时候全部大力用vector
来搞了因此常数巨大,但后面换了deque
后又喜提MLE直接给我整不会了
这里扔一份能过对拍正确性没问题的代码供参考
#include<cstdio>
#include<iostream>
#include<vector>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=300005,INF=1e18;
int n,a[N],m;
class Segment_Tree
{
private:
struct segment
{
bool ok; int tag; vector <int> num,mi;
inline void init(void)
{
ok=1; tag=0; num.clear(); mi.clear();
}
friend inline segment operator + (segment A,segment B)
{
segment C; C.init(); C.ok=A.ok&&B.ok;
if (!C.ok) return C;
int LL=A.num.size()>1?A.num[A.num.size()-2]:INF;
int RR=B.num.size()>1?B.num[1]:INF;
int L=A.num.back(),R=B.num[0];
if (L==R)
{
if (LL==INF&&RR==INF)
{
C.num.push_back(L); return C;
}
B.num.erase(B.num.begin());
if (B.mi.size()&&B.mi[0]==R) B.mi.erase(B.mi.begin());
if (L<LL&&L<RR)
{
if (A.mi.empty()||A.mi.back()!=L) A.mi.push_back(L);
}
} else
{
if (A.mi.empty()||A.mi.back()!=L)
{
if (L<LL&&L<R)
{
A.mi.push_back(L);
if (A.mi.size()>=2&&A.mi[A.mi.size()-2]>=A.mi.back()) C.ok=0;
}
} else
{
if (!(L<LL&&L<R)) A.mi.pop_back();
}
if (B.mi.empty()||B.mi[0]!=R)
{
if (R<L&&R<RR)
{
B.mi.insert(B.mi.begin(),R);
if (B.mi.size()>=2&&B.mi[0]>=B.mi[1]) C.ok=0;
}
} else
{
if (!(R<L&&R<RR)) B.mi.erase(B.mi.begin());
}
}
if (A.mi.size()&&B.mi.size()&&A.mi.back()>=B.mi[0]) C.ok=0;
if (!C.ok) return C;
auto merge=[&](vector <int> A,vector <int> B)
{
vector <int> vec;
for (auto x:A) vec.push_back(x);
for (auto x:B) vec.push_back(x);
if (vec.size()<=4) return vec;
vector <int> nvec;
nvec.push_back(vec[0]); nvec.push_back(vec[1]);
nvec.push_back(vec[vec.size()-2]); nvec.push_back(vec.back());
return nvec;
};
C.num=merge(A.num,B.num); C.mi=merge(A.mi,B.mi);
return C;
}
}O[N<<2];
inline void pushup(CI now)
{
O[now]=O[now<<1]+O[now<<1|1];
}
inline void apply(CI now,CI mv)
{
O[now].tag+=mv;
for (auto& x:O[now].num) x+=mv;
for (auto& x:O[now].mi) x+=mv;
}
inline void pushdown(CI now)
{
if (O[now].tag) apply(now<<1,O[now].tag),apply(now<<1|1,O[now].tag),O[now].tag=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)
{
if (l==r)
{
O[now].init(); O[now].num.push_back(a[l]); return;
}
int mid=l+r>>1; build(LS); build(RS); pushup(now);
}
inline void modify(CI beg,CI end,CI mv,TN)
{
if (beg<=l&&r<=end) return apply(now,mv); int mid=l+r>>1; pushdown(now);
if (beg<=mid) modify(beg,end,mv,LS); if (end>mid) modify(beg,end,mv,RS); pushup(now);
}
inline segment query(CI beg,CI end,TN)
{
if (beg<=l&&r<=end) return O[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,mid,LS)+query(mid+1,end,RS);
}
inline bool Query(CI l,CI r)
{
return query(l,r).ok;
}
#undef TN
#undef LS
#undef RS
}SEG;
signed main()
{
//freopen("H.in","r",stdin); freopen("H.out","w",stdout);
ios::sync_with_stdio(false); cin.tie(0);
RI i; for (cin>>n,i=1;i<=n;++i) cin>>a[i];
for (SEG.build(),cin>>m,i=1;i<=m;++i)
{
string opt; int l,r,x; cin>>opt>>l>>r;
if (opt=="check") cout<<(SEG.Query(l,r)?"YES":"NO")<<endl;
else cin>>x,SEG.modify(l,r,x);
}
return 0;
}
I. International Travel
疑似又是个几何题,但过的人极少鉴定为做不了一点
J. Journey of Recovery
祁神被这题狠狠地腐乳了,比赛时没想清楚去写了个复杂的单调队列做法,后面发现直接建图DFS就行了
这题大致思路就是按照地点画出一些轴,然后每个航班可以看作轴上的一些点,同时将同一个轴上的点按时间顺序排列,并将同一个轴上的相邻的点之间也连上边,在上面跑DFS即可
具体代码留着祁神填坑
K. Kernel Scheduler
思博题,徐神刚开始提了很多繁琐的做法
后面我被B搞红温后仔细想了下发现是个经典trick,我们不妨把图中的边分为两类
- \(u\to v\and u<v\),称为A类边
- \(u\to v\and u>v\),称为B类边
不难发现若仅保留A,B类边的一种则得到的图一定无环,因此保留数量较多的一类边即可
#include <bits/stdc++.h>
int main() {
std::ios::sync_with_stdio(false);
int n, m; std::cin >> n >> m;
std::vector<int> e1, e2;
for(int i = 0, f, t; i < m; ++i) {
std::cin >> f >> t;
(f > t ? &e1 : &e2)->push_back(i);
}
std::vector<int> *e = (e1.size() > e2.size() ? &e1 : &e2);
std::cout << "YES\n" << e->size() << char(10);
for(size_t i = 0; i < e->size(); ++i)
std::cout << (*e)[i] + 1 << char(i == e->size() ? 10 : 32);
return 0;
}
L. Last One Standing
祁神写的一个Easy题,我连题目都没看
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
int h1, d1, t1; cin >> h1 >> d1 >> t1;
int h2, d2, t2; cin >> h2 >> d2 >> t2;
int T1 = (h1 + d2-1)/d2*t2 -t2, T2 = (h2 + d1-1)/d1*t1 -t1;
if (T1 > T2) cout << "player one\n";
else if (T1 < T2) cout << "player two\n";
else cout << "draw\n";
return 0;
}
M. Mini-Tetris 3023
签到讨论题,不难发现拿两个Corner可以和所有的S-tile拼成矩形,然后多余的Corner两两配对即可
#include <bits/stdc++.h>
int main(void) {
int a, b, c;
std::cin >> a >> b >> c;
std::swap(b, c);
int ans = a << 1;
if(b >= 2) {
ans += (c << 1) + 3;
ans += (b - 2 >> 1) * 3;
}
std::cout << ans << char(10);
return 0;
}
N. Naming Wine Bottles
签到题,先给每种瓶子分配一个整形编号,然后把这个编号转化成\(26\)进制的数即可保证命名的唯一性
#include<bits/stdc++.h>
#define LD long double
using namespace std;
const int N = 1e4+5;
int n;
LD A[N];
int idx=0;
string calc(int x){
string str;
while (x>0){
str += 'a'+x%26;
x/=26;
}
return str;
}
signed main(){
map<LD, int> mp;
string str("a");
scanf("%d", &n);
for (int i=1; i<=n; ++i){
scanf("%LfL", &A[i]);
if (!mp.count(A[i])) mp[A[i]] = ++idx;
}
for (int i=1; i<=n; ++i) cout << calc(mp[A[i]]) << '\n';
return 0;
}
Postscript
感觉今天没啥存在感啊,被徐神和祁神带飞了
- 2023 Programming Kingdom Ireland Contest2023 programming kingdom ireland programming regional contest 2023 contest 2023 2022 programming 2023 programming collegiate contest contest programming beginner atcoder programming collegiate provincial contest subregional programming acm-icpc contest programming collegiate jiangsu contest contest programming securities beginner international programming collegiate contest